2022年华北电力大学(北京)计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

科目期末试卷A（有答案）

一、选择题

1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A.13 B.33 C.18 D.40

2、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（ ）方法是哈希文件的关键。 A.哈希函数 B.除余法中的质数 C.冲突处理

D.哈希函数和冲突处理

3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。

A.单链表 B.双向链表 C.单循环链表 D.顺序表

4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛，，，，， ，，，｝，G的拓扑序列是（ ）。

A.V1，V3，V4，V6，V2，V5，V7 B.V1，V3，V2，V6，V4，V5，V7 C.V1，V3，V5，V2，V6，V7 D.V1，V2，V5，V3，V4，V6，V7

5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（ ）。 A.3612 B.453126 C.346521 D.234156

6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（ ）。

A．只有e B．有e、b C．有e、c D．无法确定

7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。

Ⅰ．简单选择排序Ⅱ．希尔排序 Ⅲ．快速排序 Ⅳ．堆排 Ⅴ．二路归并排序 A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ

8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。

A.107 B.108 C.214 D.215

9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（ ）。 A.在树T中，X是其双亲的第一个孩子 B.在树T中，X一定无右兄弟 C.在树T中，X一定是叶结点 D.在树T中，X一定有左兄弟

10、就平均性能而言，目前最好的内排序方法是（ ）排序法。 A.起泡 B.希尔插入 C.交换 D.快速

二、填空题

11、若用n表示图中顶点数目，则有______条边的无向图成为完全图。

12、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。

13、在单链表L中，指针P所指结点有后继结点的条件是______。

14、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。 15、索引顺序文件既可以顺序存取，也可以______存取。

16、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。

17、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时， top[2]为______，栈满时为______。 18、设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为 l，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH， PUSH之后，输出序列是______，而栈顶指针值是______。设栈为顺序栈，每个元素占4个字节。

三、判断题

19、文件系统采用索引结构是为了节省存储空间。（ ）

20、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）

21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）

22、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若 ai=n（1≤i≤n）则有：ai>ai+1>…>an。（ ）

23、树形结构中元素之间存在一对多的关系。（ ） 24、对于有n个结点的二叉树，其高度为log2n。（ ） 25、为了很方便地插入和删除数据，可以使用双向链表存放数据。 （ ）

26、快速排序和归并排序在最坏情况下的比较次数都是O（nlog2n）。（ ） 27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ） 28、B-树中所有结点的平衡因子都为零。（ ）

四、简答题

29、请写出应填入下列叙述中（ ）内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序等。设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。

（ ）排序的结果为：12，13，15，18，20，60 （ ）排序的结果为：13，15，18，12，20，60 （ ）排序的结果为：13，15，20，18，12，60 （ ）排序的结果为：12，13，20，18，15，60

30、下面程序段的时间复杂度是什么？

31、二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T，采用二叉链表存储，节点结构为：

其中叶节点的weight域保存该结点的非负权值。设root为指向T的根节点的指针，设计求T的WPL的算法。要求： （1）给出算法的基本设计思想。

（2）使用C或C++语言，给出二叉树结点的数据类型定义。

（3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

五、算法设计题

32、令G=(V，E)为一个有向无环图，编写一个给图G中每一个顶点赋以一个整数序号的算法，并满足以下条件：若从顶点i至顶点j有一条弧，则应使i33、设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能察看一次，并且只允许交换操作来调整砾石的位置。

34、已知关键字序列（K1，K2，K3，…，Kn-1）是大根堆。

（1）试写出一算法将（K1，K2，K3，…，Kn-1，Kn）调整为大根堆。 （2）利用（1）的算法写一个建大根堆的算法。

35、已知二叉树采用二叉链表存储，设计算法以输出二叉树T中根结点到每个叶结点的路径。

参

一、选择题

1、【答案】B 2、【答案】D 3、【答案】D 4、【答案】A 5、【答案】C 6、【答案】A 7、【答案】A 8、【答案】B 9、【答案】D 10、【答案】D

二、填空题

11、【答案】n(n-1)/2 12、【答案】（n+1）/2 13、【答案】P->next!=NULL 14、【答案】O（1）；O（n） 15、【答案】随机

16、【答案】s=（LinkedList*）ma11oc（sizeof（LNode））；>next；r->next=s；r=s。

17、【答案】0；n+1；top[1]+1=top[2] 18、【答案】23；100CH

三、判断题

19、【答案】×

s->data=x；s->next=r-20、【答案】× 21、【答案】× 22、【答案】× 23、【答案】√ 24、【答案】× 25、【答案】√ 26、【答案】× 27、【答案】√ 28、【答案】√

四、简答题

29、答：①快速排序 ②起泡排序 ③直接插入排序 ④堆排序

30、答：赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O（m*n）。 31、答：（1）算法的基本思路是利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。

（2）

五、算法设计题

32、答：算法如下：

33、答：算法如下：

34、答：（1）算法如下：

35、答：算法如下：