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

一、选择题

1、下述文件中适合于磁带存储的是（　　）。

A.顺序文件

B.索引文件

C.哈希文件

D.多关键字文件

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

A.N    B.2N-1    C.2N   D.N-1

3、以下与数据的存储结构无关的术语是（　　）。

A.循环队列 链表 哈希表 栈

4、下列关于AOE网的叙述中，不正确的是（　　）。

A.关键活动不按期完成就会影响整个工程的完成时间

B.任何一个关键活动提前完成，那么整个工程将会提前完成 

C.所有的关键活动提前完成，那么整个工程将会提前完成

D.某些关键活动若提前完成，那么整个工程将会提前完成

5、动态存储管理系统中，通常可有（　　）种不同的分配策略。

A.1     B.2    C.3      D.4

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

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

7、下列选项中，不能构成折半查找中关键字比较序列的是（　　）。

A．500，200，450，1．500，450，200，180

C．180，500，200，4．180，200，500，450

8、有关二叉树下列说法正确的是（　　）。

A.二叉树的度为2

B.一棵二叉树的度可以小于2

C.二叉树中至少有一个结点的度为2

D.二叉树中任何一个结点的度都为2

9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（　　）。

A.其中任意一个结点均无左孩子

B.其中任意一个结点均无右孩子

C.其中只有一个叶结点

D.其中度为2的结点最多为一个

10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次采用的增量是（　　）。

A.1           B.4              C.3               D.2

二、填空题

11、设m、n均为自然数，m可表示为一些不超过n的自然数之和，f（m， n）为这种表示方式的数目。例f（5，3）=5，有5种表示方式：3+2， 3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。

①以下是该函数的程序段，请将未完成的部分填入，使之完整。

②执行程序，f（6，4）=______。

12、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：

13、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。

14、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。

（2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

15、文件由______组成；记录由______组成。

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

17、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时， top[2]为______，栈满时为______。

18、已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。

三、判断题

19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（　　）

20、直接访问文件也能顺序访问，只是一般效率不高。（　　）

21、广义表（（（a，b，c），d，e，f））的长度是4。（　　）

22、串是一种数据对象和操作都特殊的线性表。（　　）

23、树形结构中元素之间存在一对多的关系。（　　）

24、若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（　　）

25、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（　　）

26、在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（　　）

27、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（　　）

28、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（　　）

四、简答题

29、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）。

30、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87， 95）进行折半查找，试回答下列问题：

（1）画出描述折半查找过程的判定树。

（2）若查找元素54，需依次与哪些元素比较?

（3）若查找元素90，需依次与哪些元素比较?

（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。

31、已知一个带有表头结点的单链表，结点结构为

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：

（1）描述算法的基本设计思想。

（2）描述算法的详细实现步骤。

（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C＋＋或JAVA语言实现），关键之处请给出简要注释。

五、算法设计题

32、给定n×m矩阵A[a..b，c..d]，并设

A[i，j]≤A[i+1，j]（a≤i≤b-1，c≤j≤d）。设计一算法判定x的值是否在A 中，要求时间复杂度为O（m+n）。

33、结点类型和存储结构如下：

试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。

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

35、编写算法，求二叉树的宽度。

参

一、选择题

1、【答案】A

2、【答案】A

3、【答案】D

4、【答案】B

5、【答案】C

6、【答案】A

7、【答案】A

8、【答案】B

9、【答案】C

10、【答案】B 

二、填空题

11、【答案】① 1；1；f（m，n-1）；n　② 9

12、【答案】a+1；n%10

【解析】通过递归算法，首先找到最高位的值，将其放到str对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。

13、【答案】f->next=p->next；f->prior=p；p->next->prior=f；p->next=f。

14、【答案】

(1)(0，3，1)；(3，5，4)；(5，2，2)；(3，1，5)；(1，4，3)

(2)① T[k]；toVex=i② min=MaxInt;③ mispos=i④ exit(0)⑤ T[i]； fromVex=v

【解析】Prim算法的执行类似于寻找图的最短路径的Dijkstra算法。假设 N={V，E}是连通图，ET是N上最小生成树边的集合。算法从VT={u0}， ET开始，重复执行下述操作：在所有u属于VT，v属于V-VT的边（u， v）属于E中找一条代价最小的边（u0，v0）加入集合ET，同时将v0并入VT，直到VT=V为止。

15、【答案】记录；数据项

16、【答案】01122312

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

18、【答案】（rear+1）%（n-m+1）==front

三、判断题

19、【答案】×

20、【答案】×

21、【答案】×

22、【答案】√

23、【答案】√

24、【答案】×

25、【答案】×

26、【答案】×

27、【答案】×

28、【答案】√

四、简答题

29、答：森林转换为二叉树分以下三步：

（1）连线（将兄弟结点相连，各树的根看作兄弟）。

（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。

（3）旋转（以最左边树的根为轴，顺时针向下旋转45度）。

所以由上面三棵树转换得到的二叉树如图所示：

30、答：（1）判定树如图所示：

（2） 若查找元素54，需依次和元素30、63、42、54比较，查找成功。

（3） 若查找元素90，需依次和元素30、63、87、95比较，查找失败。

（4）

31、答：（1）算法的基本设计思想定义两个指针变量p和q，初始时均指向头结点的下一个结点。p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表最后一个结点时，因为p和q相隔k，故q指针所指元素为倒数第k个结点。以上过程对链表仅进行一遍扫描。

（2）算法的详细实现步骤

① count＝0，p和q指向链表表头结点的下一个结点。

②若p为空，转⑤。

③若count等于k，则q指向下一个结点；否则，count＝count＋1。

④ p指向下一个结点，转步骤②。

⑤若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，查找失败，返回0。

⑥算法结束。

（3）算法实现

五、算法设计题

32、答：算法如下：

33、答：算法如下

34、答：算法如下：

35、答：算法如下：