2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).pdf

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

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




2、将两个各有 N 个元素的有序表 归并成一个有序表，其最少的比 较次数是（ ）。
-1 -1
3、算法的 计算量的大小称 为计算的（ ）。
性
4、循环队 列 A[0..m-1] 存放其元素 值，用 front 和 rear 分别表示 队头 和队尾， 则当前 队列
中的元素数是（ ）。
A.（rear-front+m ）%m
-front+1
-front-1
-front
5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，
则在进行出 队操作 时（ ）。
指针

、队尾指 针都可能要修改
、队尾指 针都要修改
2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第1页 : .
2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第2页
6、已知字符串 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
7、排序 过程中， 对尚未确定最 终位置的所有元素 进行一遍处理称为一趟排序。下列排序
方法中，每一趟排序 结束时都至少能 够确定一个元素最 终位置的方法是（ ）。
Ⅰ． 简单选择 排序Ⅱ．希 尔排序 Ⅲ．快速排序 Ⅳ．堆排 Ⅴ．二路 归并排序
A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ
8、一棵哈夫曼 树共有 215 个结点， 对其进行哈夫曼 编码，共能得到（ ）个不同的 码
字。

9、一棵非空的二叉 树的前序序列和后序序列正好相反， 则该 二叉 树一定 满足（ ）。
结点均无左孩子
结点均无右
结点
为 2 的结点最多 为一个
10 、对序列{15 ，9，7，8，20 ，-1，4} 用希尔排序方法排序，经一趟后序列变为{15，-1，
4，8，20 ，9，7}则该 次采用的增量是（ ）。

二、填空题

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 。
① 以下是该函数的程序段，请将未完成的部分填入，使之完整。
2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第2页 : .
2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第3页

② 执行程序， f（6，4）=______ 。
12 、以下程序的功能是 实现带 附加头结点的 单链 表数据 结点逆序 连接，请填空完善之。

13 、已知有序表 为（12，18，24，35 ，47 ，50 ，62 ，83 ，90 ，115 ， 134 ）当用二分法 查
找 90 时，需______ 次查找成功， 查找 47 时______ 成功， 查找 100 时，需______ 次才能确
定不成功。
14 、应用 Prim 算法求解 连通网络的最小生成 树问题 。（1）针对如图所示的 连通网 络，
试按如下格式 给出在构造最小生成 树过程中 顺序选出的各条 边。

（2）下面是 Prim 算法的 实现 ，中 间有 5 个地方缺失， 请阅读 程序后将它 们补上。
2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第3页 : .
2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第4页


15、数据结构中评价算法的两个重要指 标是______。
16 、设 T 和 P 是两个 给定的串，在 T 中寻找等于 P 的子串的 过程称为______，又称 P 为
______。
17 、在顺序存储的二叉树中，编号为 i 和 j 的两个结点处在同一 层的条件是 ______ 。
18 、设有一个空 栈，栈顶 指针为 1000H （十六 进制）， 现有输入序列 为 l，2，3，4，5，
经过 PUSH，PUSH，POP，PUSH，POP，PUSH， PUSH 之后， 输出序列是 ______，而栈顶
指针值是______。设栈为顺 序栈，每个元素占 4 个字 节。
三、判断题

19、对磁带机而言， ISAM 是一种方便的文件 组织方法（ ）
2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第4页 : .
2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第5页
20、直接访问文件也能 顺序访问，只是一般效率不高。（ ）
21 、稀疏矩 阵压缩 存储后，必会失去随机存取功能。（ ）
22 、广义表（（（ a，b，c），d，e，f））的 长度是 4。（ ）
23 、任何二叉 树的后序线索树进行后序遍 历时都必 须用栈。（ ）
24 、对于有 n 个结点的二叉 树，其高度 为 log2n 。（ ）
25 、排序算法中的比 较次数与初始元素序列的排列无关。（ ）
26 、抽象数据 类型与计算机内部表示和 实现 无关。（ ）
27 、若一个有向 图的邻接矩 阵对 角线以下元素均 为零，则该图 的拓扑有序序列必定存在。
（ ）
28 、对两棵具有相同关 键字集合的而形状不同的二叉排序 树，按中序遍 历它们得到的序列
的顺序却是一致的。（ ）
四、简答题

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 、假定 对有序表：（3，4，5，7，24，30，42，54，63，72，87， 95）进行折半 查找，
试回答下列 问题 ：
（1）画出描述折半 查找过程的判定 树。
（2）若查找元素 54 ，需依次与哪些元素比 较?
（3）若 查找元素 90 ，需依次与哪些元素比 较?
（4）假定每个元素的 查找概率相等，求 查找成功 时的平均 查找长度。


2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第5页 : .
2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第6页


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

其中叶节点的 weight 域保存 该结点的非 负权值 。设 root 为指向 T 的根节点的指 针，设计
求 T 的 WPL 的算法。要求：
（1）给出算法的基本 设计 思想。
（2）使用 C 或 C++语言， 给出二叉 树结点的数据 类型定义。
（3）根据 设计思想，采用 C 或 C++语言描述算法，关 键之处给出注 释。





五、算法设计题

32、编写程序， 统计在输入字符串中各个不同字符出 现的频度并将 结果存入文件（字符
串中的合法字符 为 A～Z 这 26 个字母和 0～9 这 10 个数字）。





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





2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第6页 : .
2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第7页
34、已知指 针 p 指向 带表头的中根次序 线索二叉树中的某结点，试写一算法 FFA（p，
q），该算法 寻找结点 p 的父 亲结 点 q。设线 索二叉 树的结点结构、表 头结 点结构和空 树
结构分别为 （LTAG ，LLINK ，INFO ， RLlNK，RTAG ），且 规定线索树的最左下 结点
的 LLINK 域和最右下 结点的 RLINKt 域指向表 头。





35 、请运用快速排序思想， 设计递归 算法实现求 n（n>1 ）个不同元素集合中的第 f
（1≤i≤n ）小元素。






2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第7页 : .
2022年郑州工商学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第8页