Question

求数据结构与算法分析高人帮忙做下这几道题目。（希望能给出正确答案，在此谢过！！！）

填空题
1、在具有n个元素的循环队列中，队满时具有___个元素。
2、在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于_____。
3、设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为11，则

队列中元素的个数为____。
4、判定一个有向图是否存在回路，可以利用_____。
5、根据一组记录（56，42，50，64，48）依次插入结点生成一棵AVL树，当插入到值为___

的结点时需要进行旋转调整。

判断题
（ T）1、顺序存储方式只能用于存储线性结构。
（ ）2、采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。
（ ）3、存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数

也有关。
（ ）4、快速排序在所有排序方法中最快，而且所需附加空间也最少。
（ ）5、直接插入排序是不稳定的排序方法。

选择题
1、在线性表的下列存储结构中，读取元素花费的时间最少的是（ ）。
A. 单链表 B. 双链表 C. 循环链表 D. 顺序表

2、一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的存储地址

是（ ）。
A. 98 B. 100 C. 102 D. 106

3、判定一个顺序栈S（栈空间大小为n）为空的条件是（ ）。
A. S->top==0 B. S->top!=0 C. S->top==n D. S->top!=n

4、下列关于图遍历的说法不正确的是（ ）。
A.连通图的深度优先搜索是一个递归过程 B. 图的广度优先搜索中邻接点的寻找

具有“先进先出”的特征
C.非连通图不能用深度优先搜索法 D. 图的遍历要求每一顶点仅被访问一次

5、在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
A. O(log2n) B. O(1) C. O(n) D. O(nlog2n)

6、表达式A*(B+C)/(D-E+F)的后缀表达式是（ ）。
A. A*B+C/D-E+F B. AB*C+D/E-F+
C. ABC+*DE-F+/ D. ABCDED*+/-+

7、对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序存储方式 B. 以链式存储方式
C. 以顺序存储方式，且数据元素有序 D. 以链式存储方式，且数据元素有序

8、设哈希表长m=14,哈希函数H(key)=key MOD 11。表中已有4个结点：addr(15)=4,addr

(38)=5,addr(61)=6,addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，则关键字为

49的地址为（ ）。
A.8 B. 3 C. 5 D. 9

9、在一个单链表中，若删除p所指向结点的后续结点，则执行（ ）。
A. p->next=p->next->next; B. p=p->next;p->next=p->next->next;
C. p =p->next; D. p=p->next->next;

Answer 1

填空题
1. n-1
因为队尾指针总是指向空。
2. 1
因为无向图的邻接矩阵是对称的。
3. 61
元素数量=
(rear+max-front) 当front > rear
(front+max-rear) 当rear > front
4. 深度优先搜索算法

5.

判断题
1. F
二叉树就可以用数组存储。
2. F
当发生冲突时，它要在下一个位置找，但如果该位置已被占用，仍需要继续向前。故同

义词不一定相邻。
3. F
图的邻接矩阵的行列数只取决于顶点数量。
4. F
没有最快的排序算法，只有特定条件下的相对较快。
5. T

选择题
1. D
2. B
Loc(a[6]) = Loc(a[1]) + (6-1)*2
= 90 + 10 =100
3. A
4. C
5. C
进堆排序时，每个元素在最底下的叶子层都有，然后较大的非叶子结点存储。

6. C
构造一棵二叉树：
/
* +
A + - F
B C D E
对该二叉树进行后序遍历即可。

7. C
折半查找要求查找表有序，并且可以根据下标定位，要求是直接存取。
顺序存储方式：可直接存取，但插入删除需耗时间
链式存储方式：只能顺序存取，插入删除方便

8. D
二次探测再散列法：
addr(key) = (初始哈希值+di)%表长
di=1、-1、4、-4、9、-9...

addr(15) = 15 % 11 = 4
addr(38) = 38 % 11 = 5
addr(61) = 61 % 11 = 6
addr(84) = 84 % 11 = 7

addr(49) = 49 % 11 = 5 有冲突
addr(49) = (5+1)%14=6 有冲突
addr(49) = (5-1)%14=4 有冲突
addr(49) = (5+4)%14=9

9. D
执行p的后继指针(next)指向p的直接后继结点(next)的下一个结点(next)即可