2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)
- 格式：docx
- 大小：362.57 KB
- 文档页数：11
2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目
期末试卷A（有答案）
一、选择题
1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。
A.5
B.6
C.8
D.9
2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A.N
B.2N-1
C.2N
D.N-1
3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则
采用（）存储方式最节省运算时间。
A.单链表
B.仅有头指针的单循环链表
C.双链表
D.仅有尾指针的单循环链表
4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。
A.（rear+1）MOD n=front
B.rear=front
C.rear+1=front
D.（rear-1）MOD n=front
5、在下列表述中，正确的是（）
A.含有一个或多个空格字符的串称为空格串
B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树
C.选择排序算法是不稳定的
D.平衡二叉树的左右子树的结点数之差的绝对值不超过l
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，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三
次进行退栈操作，则不可能得到的出栈序列是（）。
8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。
A.CBEFDA
B.FEDCBA
C.CBEDFA
D.不定
9、有n（n>0）个分支结点的满二叉树的深度是（）。
A.n2-1
B.log2（n+1）+1
C.log2（n+1）
D.log2（n-l）
10、下列二叉排序树中查找效率最高的是（）。
A.平衡二叉树
B.二叉查找树
C.没有左子树的二叉排序树
D.没有右子树的二叉排序树
二、填空题
11、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
12、无用单元是指______，例______
13、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是______。
14、索引顺序文件既可以顺序存取，也可以______存取。
15、设有两个算法在同一机器上运行，其执行时闻分别为100n2和2n，要使前者快于后者，n至少为______。
16、设广义表L=（（），（）），则head（L）是______； tail（L）是______；L的长度是______；深度是______。
17、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储： a11=1），则a85的地址为______。
18、已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V， SUBSTR（S，INDEX（S，t），LEN（t）+1））； ASSIGN（m，’ww’），求REPLACE（S，V，m）
=______。
三、判断题
19、倒排序文件的优点是维护简单。
（）
20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。
（）
21、稀疏矩阵压缩存储后，必会失去随机存取功能。
（）
22、设栈采用顺序存储结构。
若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O（i）。
（）
23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。
（）
24、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。
（）
25、在任何情况下，归并排序都比简单插入排序快。
（）
26、归并排序辅助存储为O（1）。
（）
27、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。
（）
28、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。
（）
四、简答题
29、设有n个元素采用起泡排序法进行排序，通常需要进行多少趟排序? 对于第J趟起泡通常需要进行多少次关键字比较?在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。
30、下面程序段的时间复杂度是什么？
31、设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60 和200个数据
元素，各表中元素按升序排列。
要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。
请回答下列问题。
（1）给出完整的合并过程，并求出最坏情况下比较的总次数。
（2）根据你的合并过程，描述n（n≥2）个不等长升序表的合并策略，并说明理由。
五、算法设计题
32、起泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡
的下沉）；请给出上浮和下沉过程交替的起泡排序算法。
33、设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中（注：按层从上到下，由左到右）。
34、有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。
35、设键盘输入n个英语单词，输入格式为n，w1，w2，…，wn，其中n表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现：
（1）如果单词重复出现，则只在链表上保留一个。
（2）除满足（1）的要求外。
链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k（k<=n）个单词。
参考答案
一、选择题
1、【答案】A
2、【答案】A
3、【答案】D
4、【答案】B
5、【答案】C
6、【答案】A
7、【答案】D
8、【答案】A
9、【答案】C
10、【答案】A
二、填空题
11、【答案】
（1）p!=NULL //链表未到尾就一直进行
（2）q //将当前结点作为头结点后的第一元素结点插入
12、【答案】用户不再使用而系统没有回收的结构和变量； p=ma11oc（size）;…,p=nu11
13、【答案】
【解析】m阶B-树除根结点和叶子结点外，结点中关键字个数最多是m1，最少
14、【答案】随机
15、【答案】15
16、【答案】（）；（（））；2；2
17、【答案】33
18、【答案】’xyxyxywwy’
三、判断题
19、【答案】×
20、【答案】×
21、【答案】√
22、【答案】×
23、【答案】√
24、【答案】√
25、【答案】×
26、【答案】×
27、【答案】√
28、【答案】×
四、简答题
29、答：n个元素采用起泡排序法进行排序，通常需要进行n-1趟排序。
第j趟起泡排序要进行n-j次比较。
在一趟排序中，若没有记录交换，则表示排序完成。
因而，可通过设标记来控制排序结束，下面语句段说明了标记flag的使用。
30、答：赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O（m*n）。
3
1
、
答
（1）6个表的合并顺序如下图所示。
对应于合并过程的哈夫曼树根据上图中的哈夫曼树，6个序列的合并过程为：第1次合并：表A与表B合并，生成含45个元素的表AB。
第2次合并：表AB与表C合并，生成含85个元素的表ABC。
第3次合并：表D与表E合并，生成含110个元素的表DE。
第4次合并：表ABC与表DE合并，生成含195个元素的表ABCDE。
第5次合并：表ABCDE与表F合并，生成含395个元素的最终表。
由于合并两个长度分别为m和n的有序表，最坏情况下需要比较m＋n－1 次，故最坏情况下比较的总次数计算如下：第1次合并：最多比较次数＝10＋35－1＝44。
第2次合并：最多比较次数＝45＋40－1＝84。
第3次合并：最多比较次数＝50＋60－1＝109。
第4次合并：最多比较次数＝85＋110－1＝194。
第5次合并：最多比较次数＝195＋200－1＝394；比较的总次数最多为：44＋84＋109＋194＋394＝825。
（2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。
可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。
【解析】本题具有较强的综合性，主要考查了构造哈夫曼树的算法思想和过程、归并排序的过程等。
五、算法设计题
32、答：算法如下：
33、答：算法如下：
34、答：算法如下：
35、答：定义结点数据类型如下：
(1)算法如下：
(2)算法如下：。
