2022年复旦大学计算机科学与技术专业《数据结构与算法》科目期末试卷.pdfVIP

2022年复旦大学计算机科学与技术专业《数据结构与算法》科目期末

试卷A（有答案）

一、选择题

1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。

A.5B.6C.8D.9

2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-1

3、线性表的顺序存储结构是一种（）。

A.随机存取的存储结构顺序存取的存B.储结构

C.索引存取的存储结构D.Hash存取的存储结构

4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，

则在进行出队操作时（）。

A.仅修改队头指针

B.仅修改队尾指针

C.队头、队尾指针都可能要修改

D.队头、队尾指针都要修改

5、在下列表述中，正确的是（）

A.含有一个或多个空格字符的串称为空格串

B.对n（n0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树

C.选择排序算法是不稳定的

D.平衡二叉树的左右子树的结点数之差的绝对值不超过l

6、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1

A．只有Ⅰ．只B有ⅡC．Ⅰ和Ⅱ．DⅠ和Ⅲ

7、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字

3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19

B．3，5，12，19，20，15，22，8，28

C．3，8，12，5，20，15，22，28，19

D．3，12，5，8，28，20，15，22，19

8、在下述结论中，正确的有（）。

①只有一个结点的二叉树的度为0。

②二叉树的度为2。

③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相

同的满二叉树。

A.①②③

B.⑦③④

C.②④

D.①④

9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按

其关键字有序（）。

A.二叉排序树哈夫曼B.树树C.AVL堆D.

10、对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是：

A.05，46，13，55，94，17，42

B.05，13，17，42，46，55.94

C.42，13，94，05，55，46，17

D.05，13，46，55，17，42，94

二、填空题

11、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放

成321。请填空：

12、在哈希函数H（key）=key%p中，p值最好取______。

13、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用

______的排序方法。

14、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。

注：(1)图的顶点号从0开始计。

(2)indegree是有n个分量的一维数组，放顶点的入度，

(3)函数crein用于计算顶点入度。

(4)有三个函数push(data)，pop()，check()其含义为数据data入栈，出栈和测试栈是否空

(不空返回l，否则0)。

15、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点

中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该

结点中原有的关键字的个数是______。

16、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

17、模式串P=‘abaabcac’的next函数值序列为______。

18、已知一循环队列的存储空间为[m..n]，其中