数据结构考试题2.doc

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。
一、单项选择题（每小题1.5分，20小题，共计30分）
1.以下数据结构中属非线性结构。
A.栈 B.串 C.队列 D.平衡二叉树
2.以下算法的时间复杂度为。
voidfunc(intn)
{ inti=0,s=0;
while(s<=n)
{ i++;
s=s+i;
}
}
A.O(n) B.O()
C.O(nlog2n) D.O(log2n)
3.在一个双链表中，删除p所指节点（非首、尾节点）的操作是。
A.p->prior->next=p->next;p->next->prior=p->prior;
B.p->prior=p->prior->prior;p->prior->prior=p;
C.p->next->prior=p;p->next=p->next->next;
D.p->next=p->prior->prior;p->prior=p->prior->prior;
4.设n个元素进栈序列是1、2、3、…、n，其输出序列是p1、p2、…、pn，若p1=3，则p2的值为。
A.一定是2 B.一定是1 C.不可能是1 D.以上都不对
5.在数据处理过程中常需要保存一些中间数据，如果要实现后保存的数据先处理，则应采用来保存这些数据。
A.线性表 B.栈 C.队列 D.单链表
6.中缀表达式a*(b+c)-d的对应的后缀表达式是。
A.abcd*+- B.abc+*d- C.abc*+d- D.-+*abcd
7.设栈s和队列q的初始状态都为空，元素a、b、c、d、e和f依次通过栈s，一个元素出栈后即进入队列q，若6个元素出队的序列是b、d、c、f、e、a，则栈s的容量至少应该存多少个元素？
A.2 B.3 C.4 D.5
8.设循环队列中数组的下标是0～N-1，其队头队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），则其元素个数为。
A.r-f B.r-f-1 C.(r-f)％N+1 D.(r-f+N)％N
9.若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中，A中第一个非零元素a1,1存于B数组的b1中，则应存放到bk中的非零元素ai,j（1≤i≤n，1≤j≤i）的下标i、j与k的对应关系是。
A. B.
C. D.
10.一棵节点个数为n的m（m≥3）次树中，其分支数是。
A.nh B.n+h C.n-1 D.h-1
11.设森林F对应的二叉树为B，B中有m个节点，其根节点的右子树的节点个数为n，森林F中第一棵树的节点个数是。
A.m-n B.m-n-1 C.n+1 D.条件不足，无法确定
12.一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为。
A.CBEFDA B.FEDCBA C.CBEDFA D.不确定
13.在一个具有n个顶点的有向图中，构成强连通图时至少有条边。
A.n B.n+l C.n-1 D.n/2
14.对于有n个顶点的带权连通图，它的最小生成树是指图中任意一个。
A.由n-1条权值最小的边构成的子图
B.由n-l条权值之和最小的边构成的子图
C.由n-l条权值之和最小的边构成的连通子图
D.由n个顶点构成的极小连通子图，且边的权值之和最小
15.对于有n个顶点e条边的有向图，求单源最短路径的Dijkstra算法的时间复杂度为。
A.O(n) B.O(n+e) C.O(n2) D.O(ne)
16.一棵深度为k的平衡二叉树，其每个非叶子节点的平衡因子均为0，则该树共有个节点。
A.2k-1-1 B.2k-1 C.2k-1+1 D.2k-1
17.对线性表进行折半查找时，要求线性表必须。
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储，且节点按关键字有序排序
D.以链表方式存储，且节点按关键字有序排序
18.假设有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行次探测。
A.k-1 B.k C.k+1 D.k(k+1)/2
19.以下排序算法中，某一趟排序结束后未必能选出一个元素放在其最终位置上的是。
A.堆排序 B.冒泡排序 C.直接插入排序 D.快速排序
20.以下排序方法中，不需要进行关键字的比较。
A.快速排序 B.归并排序 C.基数排序 D.堆排序
二、问答题（共3小题，每