《数据结构》专插本考试真题.doc

（A卷）第 5 页 共 5 页
韩山师范学院专升本插班生考试样卷
计算机科学与技术 专业 数据结构 样卷

题号
一
二
三
四
五
六
七
八
九
十
总分
评卷人
得分

一、单项选择题（每题2分，共40分）。
题号
1
2
3
4
5
6
7
8
9
10
答案

题号
11
12
13
14
15
16
17
18
19
20
答案

1.关于线性表的描述，错误的是（ ）。
A. 线性表是线性结构
B. 线性表就是单链表
C. 线性表的顺序存储结构，必须占用一片连续的存储单元
D. 线性表的链式存储结构，不必占用连续的存储单元
2.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储( )。
A.数据的处理方法 B.数据元素的类型
C.数据元素之间的关系 D.数据的存储方法
3.与单链表相比，双链表的优点之一是( )。
A.插入、删除操作更简单 B.可以进行随机访问
C.可以省略表头指针或表尾指针 D.顺序访问相邻结点更灵活
4. 对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为( )。
A. n+1 B. n C. n-1 D. n(n-1)/2
5．如果结点A有3个兄弟，而且B为A的双亲，则B是度为（ ）
A．3 B．4 C．5 D．1
6．在具有N个单元的顺序存储循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（ ）。
A．front == rear B．(rear+1) % MAXSIZE == front
C．front - rear==1 D．rear % MAXSIZE == front
7. 某二叉树的前序遍历序列为 ABDGCEFH ，中序遍历序列为 DGBAECHF ，则后序遍历序列为（ ）。
A. BDGCEFHA B. GDBECFHA C. BDGAECHF D. GDBEHFCA
8．设无向图的顶点个数为n，则该图最多有（ ）条边。
A. n-1 B. n(n-1)/2 C．n(n+1)/2 D. 0
9. 在一个长度为N的线性表中顺序查找值为x的元素时，在等概率的情况下查找成功时的平均查找长度为（ ）。
A. N B. N/2 C. (N+1)/2 D. (N-1)/2
10．深度为5的二叉树至多有( )个结点。
A.16 B.32 C.31 D.10
11. 堆的形状是一棵( )。
A. 二叉排序树 B.满二叉树 C. 完全二叉树 D. 平衡二叉树
12．下列关于数据结构的叙述中，正确的是( )。
A. 数组是同类型值的集合
B. 树是一种线性结构
C. 递归算法的程序结构比迭代算法的程序结构更为精炼
D. 用一维数组存储二叉树，总是以先序遍历的顺序存储各结点
13. 在具有 n(n>1) 个结点的完全二叉树中，结点 i(2*i>n) 的左孩子结点是（ ）。
A. 2*i B. 2*i+1 C. 不存在 D. 2*i-1
14. 在有n个结点的二叉树中，值为非空的链域的个数为(     )。
A. n-1        B. 2*n-1   C. n+1      D. 2*n+1
15. 若对一个已排好序的序列进行排序，在下列四种方法中，哪种比较好（ ）。
A. 冒泡法 B. 直接选择法 C. 直接插入法 D. 归并法
16. 设单链表中指针p指向结点A，若A的后继结点存在，则删除该后继结点需要修改指针的操作为（ ）。
A．p->next=p->next->next B．p=p->next
C．p=p->next->next D．p->next=p
17. 队列操作的原则是(      )。
A. 先进先出  B. 后进先出  C. 只能进行插入  D. 只能进行删除
18. 对树进行层次遍历时，通常是采用( )作为辅助来实现算法的。
A．栈 B. 队列 C. 树 D. 图
19. ( )是顺序存储方式的优点。
A. 存储密度大 B. 插入运算方便
C. 删除运算方便 D. 可方便地用于各种逻辑结构的存储表示
20. 数组A[5][6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为(      )。
A. 1140     B. 1145   C. 1120    D. 1125
二、判断题（每题1分，共10分）。
以下各种说法，你认为对的在前面括号打√，错误的打×。
(     )1．队列只能采用链式存储方式。
(     )2.二叉树的度一定是2。
(     )3.线性结构也是一种树结构。
(     )4.有向图用邻接表表示后，顶点i的入度等于该顶点对应的单链表的元素个数。
(     )5．满二叉树一定有偶数个结点。
(     )6．直接插入排序的关键码比较次数与初始排列有关。
(     )7．顺序存储方式只能用于存储线性结构。
( )8. 给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。
(     )9．在对链队列作出队操作时，不会改变front指针的值。
( )10. 堆排序是不稳定排序。
三、填空题（每空2分，共18分）。
1．中缀算式（3+4）*2 /（8-5）所对应的后缀算式为______ __。
2. 某算法的时间复杂度为(5*n2+1000*n*log2n+4*n-8)/(10*n)，其数量级表示为______________。
3. 用1000个结点构造的二叉树，最少___________层，最多__________层。
4. 假定一个线性表为(12,23,74,55,63,40,82,36)，若按Key % 3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为____________________、___________________和_____________________。
5. 假定一棵二叉树广义表表示为a(b(c),d(e,f))，其中序遍历序列为____________________，层次遍历序列为_____________________。
四、程序填空题（每个语句2分，共12分）
1．下面是向以BST为树根指针的二叉搜索树上插入值为item的结点的递归算法。请将缺失语句填上。
void Insert(BTreeNode*& BST, const ElemType& item)
{
if( BST == NULL ) {
BTreeNode* p = new BTreeNode;
p->data = item;
_______________________;
BST = p;
}
else if( item < BST->data ) ___________________;
else ________________________;
}
2．下面是向单链表的末尾添加一个元素的算法。请将缺失的语句填上。
Void InsertRear( LNode*& HL, const ElemType& item )
{ LNode* newptr;
newptr = new LNode;
if ( newptr == NULL ){
cerr << "Memory allocation failare!" << endl;
exit( 1 );
}
newptr->data = item;
_________________
if ( HL == NULL ) HL = newptr;
else{
____________________;
while ( ) p = p->next;
p->next = newptr;
}
}
五、算法设计题（20分）
1．编写算法函数，把顺序表List原地置逆。(10分)
顺序表的数据结构如下：
typedef struct{
int data[100];
int last;//最后元素的下标
} SeqList;
函数原形为：void fnReverse( SeqList &List );
2.二叉树采用左右孩子指针存储结构：
Struct TreeNode{
Int data;//数据域
Struct TreeNode *left, *right;//指向其左右孩子结点
};
请编写一个递归函数，要在一棵树T中，找出值是x的结点的兄弟结点。(10分)
函数原形如下：
Struct TreeNode *fnGetBrother( Struct TreeNode *T, int x );
5