华东理工大学数据结构(新)作业及期末复习题.pdf

一、判断(共计40分,每题2.5分)

1、线性表中的所有元素都有一个前驱元素和后继元素。（）

A.正确

B.错误

参考答案：【B】

2、入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。

()

A.正确

B.错误

参考答案：【A】

3、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间

复杂度均为O(n)。（）

A.正确

B.错误

参考答案：【A】

4、若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二

叉树的先序遍历序列中的最后一个结点。()

A.正确

B.错误

参考答案：【A】

5、如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）

A.正确

B.错误

参考答案：【A】

6、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点

是否被访问过。（）

A.正确

B.错误

参考答案：【A】

7、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情

况。（）

A.正确

B.错误

参考答案：【A】

8、哈夫曼树中没有度数为1的结点。（）

A.正确

B.错误

参考答案：【A】

9、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）

A.正确

B.错误

参考答案：【A】

10、调用一次深度优先遍历可以访问到图中的所有顶点。（）

A.正确

B.错误

参考答案：【B】

11、设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（）

A.正确

B.错误

参考答案：【A】

12、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。

（）

A.正确

B.错误

参考答案：【B】

13、带权无向图的最小生成树是唯一的。（）

A.正确

B.错误

参考答案：【B】

14、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）

A.正确

B.错误

参考答案：【A】

15、子串“ABC”在主串“AABCABCD”中的位置为2。()

A.正确

B.错误

参考答案：【A】

16、对链表进行插入和删除操作时不必移动链表中结点。()

A.正确

B.错误

参考答案：【A】

二、单选(共计60分,每题2.5分)

17、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()

A.O（1）

B.O（n）

C.O（1og2n）

D.O（n2）

参考答案：【C】

18、一个链栈的栈顶指针是top，则执行出栈操作时（栈非空），用x保存被删除

结点，则执行

A.x=top;top=top-next;

B.x=top-data;

C.top=top-next;x=top-data;

D.x=top-data;top=top-next;

参考答案：【D】

19、设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录

关键字45为基准而得到一趟快速排序的结果是（）。

A.40，42，45，55，80，83

B.42，40，45，80，85，88

C.42，40，45，55，80，85

D.42，40，45，85，55，80

参考答案：【C】

20、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结

点的个数分别为（）。

A.n，e

B.e，n

C.2n，e

D.n，2e

参考答案：【D】

21、设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择（）。

A.小于等于m的最大奇数

B.小于等于m的最大素数

C.小于等于m的最大偶数

D.小于等于m的最大合数

参考答案：【B】

22、设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素

是n，则输出序列中第i个输出元素是（）。

A.n-i

B.n-1-i

C.n+1-i

D.不能确定

参考答案：【C】

23、设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，

则按字母升序的第一趟冒泡排序结束后的结果是（