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

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

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

2、将两个各有 N 个元素的有序表 归并成一个有序表，其最少的比 较次数是（ ）。
-1 -1
3、静态链 表中指 针表示的是（ ）。


组中的位置

4、下面关于串的叙述中，不正确的是（ ）。



顺序存储，也可以采用 链式存储
5、循 环队 列 A[0..m-1] 存放其元素值，用 front 和 rear 分别表示 队头 和队尾，则当前 队列
中的元素数是（ ）。
A.（rear-front+m ）%m
-front+1
-front-1
-front
2022年西安理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第1页 : .
2022年西安理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第2页
6、若一棵二叉 树的前序遍 历序列为 a，e，b，d，c，后序遍 历序列为 b， c，d，e，a，
则根结点的孩子 结点（ ）。
A．只有 e B．有 e、b C．有 e、c D．无法确定
7、下列选项中，不能构成折半 查找中关 键字比较序列的是（ ）。
A．500 ，200 ，450 ，180 B ．500 ，450 ，200 ，180
C．180 ，500 ，200 ，450 D ．180 ，200 ，500 ，450
8、有关二叉 树下列说法正确的是（ ）。
为 2
2
结点的度 为 2
结点的度都 为 2
9、一棵非空的二叉 树的前序序列和后序序列正好相反， 则该 二叉 树一定 满足（ ）。
结点均无左孩子
结点均无右孩子
结点
为 2 的结点最多 为一个
10 、数据序列（ 8，9，10 ，4，5，6，20 ，1，2）只能是下列排序算法中的（ ）的两
趟排序后的 结果。
C. 插入排序
二、填空题

11、顺序查找 n 个元素的 顺序表，若 查找成功， 则比较关键字的次数最多 为______次；当
使用监视哨时，若 查找失 败，则比较关键字的次数 为______。
12 、下面程序的功能是用 递归算法将一个整数按逆序存放到一个字符数 组中。如 123 存放
成 321 。请填空：
2022年西安理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第2页 : .
2022年西安理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第3页

13、外排序的基本操作 过程是______和______。
14 、设单链 表的结点结构为（data ，next ），next 为指针域，已知指 针 px 指向单链表中
data 为 x 的结点，指 针 py 指向 data 为 y 的新 结点，若将 结点 y 插入结点 x 之后， 则需
要执行以下 语句： ______
15 、在基于关 键字比较且时间为 O（nlog2n ）的排序中，若要求排序是 稳定的， 则可选用
______排序；若要求就地排序（及 辅助空间为 O（1）），则可选用______排序。
16 、设 T 和 P 是两个 给定的串，在 T 中寻找等于 P 的子串的 过程称为______，又称 P 为
______。
17 、已知链队列的 头尾指 针分别是 f 和 r，则将值 x 入队的操作序列是 ______。
18 、设有一个 10 阶对称矩 阵 A 采用 压缩 存储方式（以行 为主序存 储： a11=1 ）， 则 a85
的地址 为______。
三、判断题

19、哈希表与哈希文件的唯一区 别是哈希文件引入了“桶”的概念。（ ）
20 、对磁带机而言， ISAM 是一种方便的文件组织方法（ ）
21 、设栈 采用顺序存储结 构。若已有 i-1 个元素入栈，则将第 i 个元素入栈时，入 栈算法
的时间 复杂性为 O（i）。（ ）
22 、串是一种数据 对象和操作都特殊的线性表。（ ）
23 、中序遍 历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）
24 、二叉 树是一般 树的特殊情形。（ ）
2022年西安理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第3页 : .
2022年西安理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第4页
25、外部排序是把外存文件 调入内存，可利用内部排序的方法 进行排序，因此排序所花的
时间取决于内部排序的 时间 。（ ）
26 、顺序存 储方式的 优点是存 储密度大，且插入、 删除运算效率高。
（ ）
27 、对大小均 为 n 的有序表和无序表分 别进行顺序查找，在等概率 查找的情况下， 对于查
找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
（ ）
28、有向图中顶点 V 度等于其 邻接矩阵中第 V 行中的 1 的个数。（ ）
四、简答题

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

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




31 、已知 图的邻接矩阵为 ：

当用邻接表作 为图 的存 储结 构，且邻接点都按序号从大到小排列时，试写出：
2022年西安理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第4页 : .
2022年西安理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第5页
(1)以顶点 V1为出发点的唯一的深度 优先遍 历序列。
当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：
(1)以顶点 V1为出发点的唯一的深度优先遍历序列。
(2)以顶点 V1为出发点的唯一的广度优先遍历序列。
(3)该图唯一的拓扑有序序列。



五、算法设计题

32、设记录 R[i]的关键字为 R[i]。KEY（1≤i≤k ）， 树结 点 T[i]（1≤i≤K -1）指向 败者记录 ，
T[0] 为全胜记录 下标。写一算法 产生对应上述 R[f]（1≤f≤k ）的败者树，要求除 R[1..k] 和
Tr[0..k-1] 以外，只用 O（1）辅助空间。






33 、已知深度 为 h 的二叉树，以一维数组 BT[0..2 h-2]作为其存储结 构， 试编 写一算法，
求该二叉树中叶结点的个数， 为简单 起见，设二叉 树中元素 结点为非负整数，要求写出
算法基本思想及相 应的算法。





34 、设计算法将一个 带头结 点的 单链 表 A 分解 为两个具有相同 结构的链表 B、C，其中
B 表的结点为 A 表中值小于零的 结点，而 C 表的结点为 A 表中值大于零的 结点（链表 A
的元素类型为整型，要求 B、C 表利用 A 表的结点）。

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



35、请编写一个判 别给定二叉 树是否 为二叉排序 树的算法， 设二叉树用 llink —rlink 法存
储。







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

1、【答案】 C
2、【答案】 A
3、【答案】 C
4、【答案】 B
5、【答案】 A
6、【答案】 A
7、【答案】 A
8、【答案】 B
9、【答案】 C
10 、【答案】 C
二、填空题

11、【答案】 n；n+1
12 、【答案】 a+1 ；n%10
【解析】 通过递归 算法，首先找到最高位的 值，将其放到 str 对应 的数 组中，依次反向 获
取从高位到地位的 值，将其放到数 组中，完成了将整数逆序放到一个字符数 组中。
13 、【答案】生成有序 归并段（顺串）；归并
14 、【答案】 py->next=px->next ；px->next=py
15 、【答案】 归并；堆
16 、【答案】模式匹配；模式串
17 、【答案】 s=（LinkedList* ）ma11oc （sizeof （LNode ））；s->data=x ；s->next=r-
>next ；r->next=s ；r=s 。
18 、【答案】 33
2022年西安理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第7页 : .
2022年西安理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第8页
三、判断题