2022年江西科技学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

期末试卷A（有答案）

一、选择题

1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。

A.快速排序 B.堆排序 C.归并排序 D.直接插入排序 2、下列排序算法中，占用辅助空间最多的是（ ）。 A.归并排序 B.快速排序 C.希尔排序D.堆排序 3、以下数据结构中，（ ）是非线性数据结构。 A.树 B.字符串 C.队 D.栈

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

5、下列关于AOE网的叙述中，不正确的是（ ）。 A.关键活动不按期完成就会影响整个工程的完成时间 B.任何一个关键活动提前完成，那么整个工程将会提前完成 C.所有的关键活动提前完成，那么整个工程将会提前完成 D.某些关键活动若提前完成，那么整个工程将会提前完成

6、已知关键字序列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

7、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（ ）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2

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、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。

A.（38，40，46，56，79，84） B.（40，38，46，79，56，84） C.（40，38，46，56，79，84） D.（40，38，46，84，56，79）

二、填空题

11、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

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

13、检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按______检索。也可以按______检索；按______检索又可以有 ______检索和______检索。

14、设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。在下面的算法中，free_tree（T）在对二叉排序树丁进行后序遍历时释放二又排序树T的所有结点；

delete_subtree（T，A），首先在二叉排序树 T中查找值为A的结点，根据查找情况分别进行如下处理：（1）若找不到值为A的结点，则返回根结点的地址（2）若找到值为A的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是查找树的根结点，删除后变成空的二叉树，则返null；否则返回根结点的地址。

15、外排序的基本操作过程是______和______。

16、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。

17、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。

18、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。

三、判断题

19、倒排文件的目的是为了多关键字查找。（ ） 20、文件系统采用索引结构是为了节省存储空间。（ ） 21、数组不适合作为任何二叉树的存储结构。（ ）

22、在链队列中，即使不设置尾指针也能进行入队操作。（ ）

23、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（ ） 24、任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ） 25、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ） 26、排序算法中的比较次数与初始元素序列的排列无关。（ ）

27、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（ ）

28、B-树中所有结点的平衡因子都为零。（ ）

四、简答题

29、调用下列C函数f（n），回答下列问题：

（1）试指出f（n）值的大小，并写出，f（n）值的推导过程。

（2）假定n=5，试指出，f（5）值的大小和执行，f（5）时的输出结果。 C函数：

30、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满／栈空的判断条件，并用C语言或PASCAL语言设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。

31、已知世界六大城市为：北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M)，下表给定了这六大城市之间的交通里程： 世界六大城市交通里程表(单位：百公里)

（1）画出这六大城市的交通网络图。

（2）画出该图的邻接表表示法。

（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。

五、算法设计题

32、串以静态存储结构存储，结构如下所述，试实现串操作equal算法。

33、已知P是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表（a1，a2，…，an-1，an）改造为（a1，a2，…， an-1，an，an-1，…，a2，a1）。

34、已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。

35、设给定关键字输入序列为（100，90，120，60，78，35，42，31， 15）用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少?

参

一、选择题

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

二、填空题

11、【答案】

（1）p!=NULL //链表未到尾就一直进行

（2）q //将当前结点作为头结点后的第一元素结点插入 12、【答案】n(n-1)/2

13、【答案】关键字；记录号；记录号；顺序；直接

14、【答案】free（T）；q&&q->data!=A；q=q->rchild；p->lchild=null；p->rchild=null 15、【答案】生成有序归并段（顺串）；归并 16、【答案】FEGHDCB；BEF

【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF。 17、【答案】

【解析】最大的分支结点是最后一个叶子结点的父结点。 18、【答案】

【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s和t，则结点i和j在同一层上的条件是

三、判断题

19、【答案】√ 20、【答案】× 21、【答案】× 22、【答案】√ 23、【答案】√ 24、【答案】× 25、【答案】× 26、【答案】× 27、【答案】√ 28、【答案】√

四、简答题

29、答：（1）第一层for循环判断n+1次，往下执行n次，第二层for执行次数为（n+（n-1）+（n-2）+…+1），第三层循环体受第一层循环和第二层循环的控制，其执行次数如表1-1所示。

执行次数为f(n)=（1+2+…+，n）+（2+3+…+，n）+…+n=n*n（n+1）/2-n（n2-1）/6。 （2）在n=5对，f（5）=55，执行过程中，输出结果为：

30、答：两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为一l，另一个

栈顶指针为MAX时，栈为空。用C语言写的入栈操作push（i，x）如下：

31、答：(1)这六大城市的交通网络图如图所示：

(2)该图的邻接表表示法如图所示：

(3)最小生成树有6个顶点与条边：V(G)={Pe，N，Pa，L，T，M} E(G)=｛(L，Pa，3)，(Pe，T，21)，(M，N，32)，(L，N，55)，(L， Pe，81)}

五、算法设计题

32、答：算法如下：

33、答：算法如下：

34、答：算法如下：

35、答：算法如下：

构造的哈希表如图9-7所示：

查找成功时的平均查找长度ASL=12/9。