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

该【2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案) 】是由【小屁孩】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。 : .
2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第1页
2022 年南京邮电大学计算机科学与技术专业《数据结构与算法》科目
期末试卷 A（有答案）
一、选择题

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

2、将两个各有 N 个元素的有序表 归并成一个有序表，其最少的比 较次数是（ ）。
-1 -1
3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和 删除第一个元素， 则
采用（ ）存储方式最 节省运算 时间。
表 针的单循环链 表
4、最大容量 为 n 的循环队 列， 队尾指 针是 rear ，队头：front ，则队 空的条件是（ ）。
A.（rear+1 ）MOD n=front
=front
+1=front
D.（rear-1 ）MOD n=front
5、在下列表述中，正确的是（ ）
为空格串
n（n>0 ）个 顶点的网，求出 权最小的 n-1 条边便可构成其最小生成树
稳定的
树的左右子 树的结点数之差的绝对值不超 过 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 依次 进栈，允 许进栈 、退 栈操作交替 进行，但不允 许连续 三
次进行退栈操作， 则不可能得到的出 栈序列是（ ）。
2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第1页 : .
2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第2页
8、已知一棵二叉 树的前序遍 历结果为 ABCDEF，中序遍 历结 果为 CBAEDF，则后序遍 历结
果为（ ）。

9、有 n（n>0 ）个分支 结点的满二叉 树的深度是（ ）。
-1
（n+1 ）+1
2
（n+1 ）
2
（n-l）
2
10、下列二叉排序 树中查找效率最高的是（ ）。
树

树的二叉排序 树
树的二叉排序 树
二、填空题

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

12 、无用 单元是指 ______，例______
13 、在一棵 m 阶 B-树中，若在某结点中插入一个新关 键字而引起 该结点分裂， 则此结点
中原有的关 键字的个数是 ______ ；若在某 结点中删除一个关 键字而导致结点合并， 则该
结点中原有的关 键字的个数是 ______ 。
14 、索引顺序文件既可以 顺序存取，也可以 ______存取。
2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第2页 : .
2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第3页
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 趟起泡
通常需要 进行多少次关 键字比较?在程序 设计 中如何 设置判断条件，有可能使起泡趟数可
以减少并且能完成排序。

2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第3页 : .
2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第4页



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




31 、设有 6 个有序表 A、B、C、D、E、F，分别含有 10、35、40、50、60 和 200 个数据
元素，各表中元素按升序排列。要求通 过 5 次两两合并，将 6 个表最 终合并成 1 个升序表，
并在最坏情况下比 较的总次数达到最小。 请回答下列 问题 。
（1） 给出完整的合并 过程，并求出最坏情况下比 较的总次数。
（2） 根据你的合并 过程，描述 n（n≥2 ）个不等 长升序表的合并策略，并 说明理由。




五、算法设计题

32、起泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡
的下沉）； 请给出上浮和下沉 过程交替的起泡排序算法。




2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第4页 : .
2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第5页
33、设计算法将一棵以二叉 链表存储的二叉 树按顺序方式存 储到一维数组中（注：按 层从
上到下，由左到右）。




34 、有二叉排序 树采用二叉 链表方式存放， 树中结点值各不相同，欲得到一个由大到小的
结点值递减序列， 简述处理方法思路，用非 递归形式写出算法。





35 、设键盘输 入 n 个英语单词，输入格式 为 n，w1 ，w2 ，…，wn ，其中 n 表示随后输入
英语单词个数，试编一程序，建立一个 单向链表， 实现 ：
（1）如果 单词重复出 现，则只在链表上保留一个。
（2）除满足（1）的要求外。 链表结点还应 有一个 计数域， 记录该单词 重复出 现的次数，
然后输出出 现次数最多的前 k（k<=n ）个 单词 。








2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第5页 : .
2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第6页
参考答案
一、选择题

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
2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第6页 : .
2022年南京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第7页
17、【答案】 33
18 、【答案】’ xyxyxywwy’
三、判断题

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