大连理工大学网络教育学院2022年秋《数据结构》期末考试复习题.pdf

该【大连理工大学网络教育学院2022年秋《数据结构》期末考试复习题 】是由【小屁孩】上传分享，文档一共【19】页，该文档可以免费在线阅读，需要了解更多关于【大连理工大学网络教育学院2022年秋《数据结构》期末考试复习题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。 : .
不飞则已，一飞冲天；不鸣则已，一鸣惊人。——《韩非子》
大连理工大学网络教育学院
2022 年秋《数据结构》
期末考试复习题
一、单项选择题
1、在队列中存取数据的原则是（ A ）。
A．先进先出 B．后进先出
C．先进后出 D．随意进出
2、在下列链表中，不能从当前结点出发访问到其余各结点的是（ A ）。
A．单链表 B．单循环链表
C．双向链表 D．双向循环链表
3、在一棵二叉树上第 5 层的结点数最多为（ A ）设树根为第 1 层。
A．16 B．15 C．8 D．32
4、一棵有 124 叶子结点的完全二叉树，最多有（ C ）个结点。
A．247 B．249 C．248 D．125
5、具有 10 个叶子结点的二叉树中有（ B
）个度为 2 的结点。
A．8 B．9 C．10 D．11
6、若一棵二叉树的先序遍历序列为abdgcefh ，中序遍历的序列为dgbaechf ，则后序遍历的结果为
（ A ）。
A．gdbehfca B．bdgaechf
C．gdbecfha D．gcefhabd
7、对线性表进行顺序查找时，要求线性表的存储结构是（ C ）。
A．倒排表 B．索引表
C．顺序表或链表 D．散列表
8、对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用折半查找，则查找元素26的查找长度为
（ C ）。
A．2 B．3 C．4 D．5
9、在所有排序方法中，关键字比较的次数与记录的初始排序次序无关的是（ D ）。
A．希尔排序 B．起泡排序
《数据结构》课程期末复习题
: .
不飞则已，一飞冲天；不鸣则已，一鸣惊人。——《韩非子》
C．插入排序 D．选择排序
10、堆的形状是一棵（ C
）。
A．二叉排序树 B．满二叉树
C．完全二叉树 D．平衡二叉树
11、线性表采用顺序存储结构时，其地址（ A ）。
A．必须是连续的 B．部分地址必须是连续的
C．一定是不连续的 D．连续与否均可以
12、在栈中存取数据的原则是（ B ）。
A．先进先出 B．后进先出
C．后进后出 D．随意进出
13、插入和删除只能在一端进行的线性表，称为（ C ）。
A．队列 B．循环队列
C．栈 D．数组
14、一个基本线性表的第一个元素的存储地址是100 ，每个元素的长度是2，则第5 个元素的地址是
（ B ）。
A．110 B．108 C．100 D．120
15、算法分析的目的（ C
）。
A．找出数据结构的合理性 B．研究算法中的输入与输出的关系
C．分析算法的效率以求改进 D．分析算法的易懂性和文档性
16、结点前序为 xyz 的不同二叉树，那么它有（ C ）种不同状态。
A．3 B．4 C．5 D．6
17 、将一棵有 100 个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则
编号为 49 的结点的左孩子编号为（ A ）。
A．98 B．99 C．50 D．48
18 、设高度为 h 的二叉树上只有度为0 和度为2 的结点，则此类二叉树中所包含的结点数至少为
（ B ），设根结点的所在高度为 1。
A．2h B．2h-1
C．2h+1 D．h+1
19、在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。
: .
不飞则已，一飞冲天；不鸣则已，一鸣惊人。——《韩非子》
A．n B．n+1
C．n-1 D．n/2
20、存储在磁带上的顺序文件的查找只能用（ A ）。
A．顺序查找 B．二分查找
C．分块查找 D．树表查找

二、填空题
1、一个算法有五个特性： _______ 、_______ 、_______ 、有零个或多个输入、有一个或多个输出。
有穷性、确定性、可行性
2、栈 S 在进行出栈操作时首先要判断 _______ 。栈空否
3、在一棵二叉树中，度为零的结点的个数为 n ，度为 2 的结点的个数为 n ，则有 n =_______ 。n2+1
0 2 0
4、设 front 为队首指针， rear 为队尾指针，则循环队列 sq 是空队列的条件是 _______ 。sq->rear==sq->front
5、同一数组中各元素的长度 _______ 。相等
6、深度为 k 的二叉树共有 2k-1 个结点，该二叉树为 _______ 二叉树。 满
7、若图 G 中每条边都 _______ 方向，则称 G 为无向图。 没有
8、二叉树的按层次遍历类似于图的 _______ 遍历。 广度优先
9、选择排序算法的效率为 _______ 。O(nlogn)
10、冒泡排序算法的效率为 _______ 。O(n2)
三、判断题
1、数组的缺点是插入、删除运算效率低。（ √ ）
2、链表的优点是插入、删除运算效率高。（ √ ）
3、对图进行深度优先遍历时，应借助于一个队列。（ × ）
4、二叉树的深度优先遍历与先序序列一致。（ √ ）
5、归并排序算法是原地算法。( × )
6、堆数据结构可以看作是一个非完全二叉树。( × )
7、对图进行广度优先遍历时，应借助于一个队列。（ √ ）
8、二叉树的深度优先遍历与后序序列一致。（ × ）
9、对图进行广度优先遍历时，应借助于一个栈。（ × ）
四、 10、冒泡排序算法是原地算法。( √ )
五、 简答题
1、初始为空的队列中，元素 f,e,d,c,b,a 依次进队以后，连续进行了三次出队操作，此时的队首元素是什么？
: .
不飞则已，一飞冲天；不鸣则已，一鸣惊人。——《韩非子》
队尾元素是什么？队列操作应遵循的原则是什么？
答：
（1） 队首元素是 c
（2） 队尾元素是 a
（3） 队列操作应遵循的原则是先进先出
2、当为解决某一问题而选择数据结构时，应从哪些方法考虑？
答：
通常从两方法考虑；第一是算法所需的存储空间量，第二是算法所需的时间。
对算法所需的时又涉及以下几点：
1）程序运行时所需输入的数据总量
2）计算机执行每条指令所需的时间
3）程序中指令重复执行的次数
3、写出用直接插入法排序将数值序列 {33,23,8,41,68,64,50} 排序过程的每一趟结果。
答：（1）23 33 8 41 68 64 50
（2）8 23 33 41 68 64 50
（3）8 23 33 41 68 64 50
（4）8 23 33 41 68 64 50
（5）8 23 33 41 64 68 50
（6）8 23 33 41 50 64 68
4、简述顺序表特点。
答：优点：
可随机存取表中任意数据元素，算法简单，空间利用率高；
直接可获取线性表的长度。
缺点：
1）需要预先确定数据元素的最大个数；
2）数据元素的插入、删除相对麻烦，插入和删除时需要移动较多的数据元素。
5、简述逻辑结构和存储结构的关系。
答：在数据结构中，逻辑结构与计算机无关，存储结构是数据元素之间的逻辑关系在计算机中的表示。
存储结构不仅将逻辑结构中所有数据元素存储到计算机内存中，而且还要在内存中存储各种数据元素间的
逻辑关系。通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采用顺序存储或链式存
储结构表示。
6、简述线性表、栈和队列的异同。
答：线性表、栈和队列中元素这之间的逻辑关系都是线性关系。栈和队列是操作位置受限的线性表，
: .
不飞则已，一飞冲天；不鸣则已，一鸣惊人。——《韩非子》
即对播入和删除操作的位置加以限制，都只能在端点进行。栈是仅允许在表的一端进行插入和删除操作的
线性表，因而是后进先出表。队列是只允许在表的一端进行插入，另一端进行删除操作的线性表，因而是
先进先出表。
7、堆排序是否是一种稳定的排序方法？为什么？
答：堆排序是不种不稳定的排序方法。因为在堆的调整过程中，关键字进行比较和交换所走的是该节
点到叶子节点的一条路径，因此对相同的关键字而言，就可能出现排在后面的关键字补交换到前面来的情
况。
8、若频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构，为什么？
答：宜采用链式存储结构。因为采用链式结构存储线性表，在插入和删除操作时只修改相关节点的指
针域，不需要移动节点；而采用顺序结构存储线性表，插入和删除操作需要平均移动表中的一半元素。修
改指针域操作比移动元素操作花费的时间少得多。
9、对单链表设置头节点的作用是什么？
答：对于带头节点的单链表，在单链表的任何节点之前插入节点或删除节点，所要做的都是修改前一
个节点的指针域，因为任何节点都有前驱节点（若单链表没有头节点，则首节点没有前驱节点，在其前插
入节点和删除节点时操作复杂些） 。对于带头节点的链表，在表空时也存在一个头节点，因此空表与非空
表的处理是一样的。
五、算法题
1、简述冒泡排序算法的思想，并通过类Ｃ语言给出代码实现。
算法思想
1）不停地比较相邻的记录，如果不满足排序要求，就交换相邻记录，直到所有的记录都已经排好序。
2）检查每次冒泡过程中是否发生过交换，如果没有，则表明整个数组已经排好序了，排序结束。
void BubbleSort(Record Array[], int n) {
bool NoSwap; // 是否发生了交换的标志
int i, j;
for (i = 0; i < n-1; i++) {
NoSwap = true; // 标志初始为真
for (j = n-1; j > i; j--)
if (Array[j] < Array[j-1]) { // 判断是否逆置
swap(Array, j, j-1); // 交换逆置对
NoSwap = false; // 发生了交换，标志变为假
}
: .