2024年4月23日发(作者：郸慕蕊)
2022年河南财政金融学院计算机科学与技术专业《数据结构与算法》
科目期末试卷A（有答案）
一、选择题
1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组
表示该矩阵时，所需的字节数是（ ）。
A.60 B.66 C.18000 D.33
2、n个结点的完全有向图含有边的数目（ ）。
A.n*n B.n(n+1) C.n/2 D.n*(n-1)
3、链表不具有的特点是（ ）。
A.插入、删除不需要移动元素 B.可随机访问任一元素
C.不必事先估计存储空间 D.所需空间与线性长度成正比
4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（ ）。
A.h->next=s
B.s->next=h
C.s->next=h;h->next=s
D.s->next=h-next;h->next=s
5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（ ）。
A.543612 B.453126 C.346521 D.234156
6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。
假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，
下列判断队空和队满的条件中，正确的是（ ）。
A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M
B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）
C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M
D．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）
7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序
方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。
Ⅰ．简单选择排序Ⅱ．希尔排序 Ⅲ．快速排序 Ⅳ．堆排 Ⅴ．二路归并排序
A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ
8、有关二叉树下列说法正确的是（ ）。
A.二叉树的度为2
B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2
D.二叉树中任何一个结点的度都为2
9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A.其中任意一个结点均无左孩子
B.其中任意一个结点均无右孩子
C.其中只有一个叶结点
D.其中度为2的结点最多为一个
10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
A.（100，80，90，60，120，110，130）
B.（100，120，110，130，80，60，90）
C.（100，60，80，90，20，110，130）
D.（100，80，60，90，120，130，110）
二、填空题
11、阅读下列程序，指出其功能，并写出空格处应填上的语句。
12、属于不稳定排序的有______。
13、已知有序表为（12，18，24，35，47，50，62，83，90，115， 134）当用二分法查
找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确
定不成功。
14、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从
左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，
指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使
用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。
试填充算法中的空格，使算法完整。
15、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点
中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该
结点中原有的关键字的个数是______。
16、模式串P=‘abaabcac’的next函数值序列为______。
17、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为______。
18、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序
顺序存储，则元素a[45，68]的存储地址为______；若以列序为主序顺序存储，则元素a[45，
68]的存储地址为______。
三、判断题
19、文件系统采用索引结构是为了节省存储空间。（ ）
20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（ ）
21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）
22、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴
素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（ ）
23、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（ ）
24、任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ）
25、在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
26、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）
27、无环有向图才能进行拓扑排序。（ ）
28、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加
闲置空间的碎片。（ ）
四、简答题
29、s是字符数组，s[0]中存放的是该字符串的有效长度，假设s[1..7]中字符串的内容为
"abcabaa"，说明下列程序的功能及执行结果。
30、阅读下面的算法，说明算法实现的功能。
31、已知一个整数序列A＝（a
0
，a
1
，…，a
n
－
1
），其中0≤a
i
＜
n（0≤i≤n），若存在a
p1
＝a
p2
＝…＝a
pm
＝x且m＞n/2（0≤p
k
≤n， 1≤k≤m），则称x为A
的主元素。例如A＝（0，5，5，3，5，7，5， 5），则称5为主元素；又如A＝（0，5，
5，3，5，1，5，7）则A中没有主元素。假设A中的n个元素保存在一个一维数组中，
请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则
输出－1。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C＋＋或Java语言描述算法，关键之处给出注释。说明
你所设计算法的时间复杂度和空间复杂度。
五、算法设计题
32、假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树
的深度的算法（注：已知树中的结点数）。
33、设记录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）辅助空间。
34、在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中
具有度为1的结点数目的算法。
2024年4月23日发(作者：郸慕蕊)
2022年河南财政金融学院计算机科学与技术专业《数据结构与算法》
科目期末试卷A（有答案）
一、选择题
1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组
表示该矩阵时，所需的字节数是（ ）。
A.60 B.66 C.18000 D.33
2、n个结点的完全有向图含有边的数目（ ）。
A.n*n B.n(n+1) C.n/2 D.n*(n-1)
3、链表不具有的特点是（ ）。
A.插入、删除不需要移动元素 B.可随机访问任一元素
C.不必事先估计存储空间 D.所需空间与线性长度成正比
4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（ ）。
A.h->next=s
B.s->next=h
C.s->next=h;h->next=s
D.s->next=h-next;h->next=s
5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（ ）。
A.543612 B.453126 C.346521 D.234156
6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。
假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，
下列判断队空和队满的条件中，正确的是（ ）。
A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M
B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）
C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M
D．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）
7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序
方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。
Ⅰ．简单选择排序Ⅱ．希尔排序 Ⅲ．快速排序 Ⅳ．堆排 Ⅴ．二路归并排序
A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ
8、有关二叉树下列说法正确的是（ ）。
A.二叉树的度为2
B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2
D.二叉树中任何一个结点的度都为2
9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A.其中任意一个结点均无左孩子
B.其中任意一个结点均无右孩子
C.其中只有一个叶结点
D.其中度为2的结点最多为一个
10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
A.（100，80，90，60，120，110，130）
B.（100，120，110，130，80，60，90）
C.（100，60，80，90，20，110，130）
D.（100，80，60，90，120，130，110）
二、填空题
11、阅读下列程序，指出其功能，并写出空格处应填上的语句。
12、属于不稳定排序的有______。
13、已知有序表为（12，18，24，35，47，50，62，83，90，115， 134）当用二分法查
找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确
定不成功。
14、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从
左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，
指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使
用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。
试填充算法中的空格，使算法完整。
15、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点
中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该
结点中原有的关键字的个数是______。
16、模式串P=‘abaabcac’的next函数值序列为______。
17、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为______。
18、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序
顺序存储，则元素a[45，68]的存储地址为______；若以列序为主序顺序存储，则元素a[45，
68]的存储地址为______。
三、判断题
19、文件系统采用索引结构是为了节省存储空间。（ ）
20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（ ）
21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）
22、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴
素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（ ）
23、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（ ）
24、任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ）
25、在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
26、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）
27、无环有向图才能进行拓扑排序。（ ）
28、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加
闲置空间的碎片。（ ）
四、简答题
29、s是字符数组，s[0]中存放的是该字符串的有效长度，假设s[1..7]中字符串的内容为
"abcabaa"，说明下列程序的功能及执行结果。
30、阅读下面的算法，说明算法实现的功能。
31、已知一个整数序列A＝（a
0
，a
1
，…，a
n
－
1
），其中0≤a
i
＜
n（0≤i≤n），若存在a
p1
＝a
p2
＝…＝a
pm
＝x且m＞n/2（0≤p
k
≤n， 1≤k≤m），则称x为A
的主元素。例如A＝（0，5，5，3，5，7，5， 5），则称5为主元素；又如A＝（0，5，
5，3，5，1，5，7）则A中没有主元素。假设A中的n个元素保存在一个一维数组中，
请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则
输出－1。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C＋＋或Java语言描述算法，关键之处给出注释。说明
你所设计算法的时间复杂度和空间复杂度。
五、算法设计题
32、假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树
的深度的算法（注：已知树中的结点数）。
33、设记录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）辅助空间。
34、在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中
具有度为1的结点数目的算法。