福建师范大学2021年8月课程考试《数据结构概论》作业考核试题

《数据结构概论》期末试卷
一、答案联系QQ:3326650399 微信：cs80188 熊猫奥鹏（www.188open.com） (请将答案填写在本大题后边的表格中，答案联系QQ:3326650399 微信：cs80188 熊猫奥鹏（www.188open.com）2分，共30分)
1.查找n个元素的有序表时，最有用的查找方法是( )
A.次序查找 B.分块查找
C.减半查找 D.二叉排序树查找

2.具有12个关键词的有序表，查找成功时减半查找的均匀查找长度是( )
A.3.1 B.4 C.2.5 D.5

3.在具有n个结点的有序单链表中刺进一个新结点并使链表依然有序的时刻杂乱度是( )
A.O(1) B.O(n)
C.O(nlogn) D.O(n2)

4.对均匀功能而言，以下最佳的内排序方法是( )。
A.冒泡排序 B.希尔排序
C.交流排序 D.疾速排序

5.链栈与次序栈比较，对比显着的长处是( )
A.刺进操作愈加便利 B.删去操作愈加便利
C.不会呈现下溢的状况 D.不会呈现上溢的状况

6.二叉树中第5层上的结点个数最多为( )
A.8 B.15
C.16 D.32

7.以下数据结构中，( )对错线性数据结构。
A.树 B.字符串
C.队 D.栈

8.一个向量的榜首个元素的地址是100，每个元素的长度是2 ，则第五个元素的地址是( )。
A.102 B.110
C.108 D.120

9.已知图的邻接表如下所示，依据算法，则从极点0动身按广度优先遍历的结点序列是( )
A. 0 3 2 1 B. 0 1 2 3
C. 0 1 3 2 D.0 3 1 2

（第9题配图：数组的下标为0,1,2,3）

10.关于哈希函数H(key)=key%13,被称为近义词的关键词是( )
A.35和41 B.23和39
C.15和44 D.25和51

11.有一个有序表为{ 1，3，9，12，32，41，45，62，77，88，92，100}，用减半查找法，若要找63，要通过( )次与63对比。
A.12 B.6
C.4 D.5

12.下述几种排序方法中，安稳的排序算法是( )
A.直接刺进排序 B.疾速排序
C.堆排序 D.希尔排序

13.具有n个极点的无向图至少要有( )条边才干保证是一个连通图。
A.n(n+1) B.n-1
C.n+1 D.n(n-1)

14.二叉树对错线性数据结构，所以 ( )
A.它不能用次序存储结构存储 B.它不能用链式存储结构存储
C.次序存储结构和链式存储结构都能存储 D.次序存储结构和链式存储结构都不能运用

15.有8个结点的无向图最多有( )条边。
A.14 B.28
C.56 D.112
　　答案联系QQ:3326650399 微信：cs80188 熊猫奥鹏（www.188open.com）答题表格（请将答案填写鄙人表中）
1
2
3
4
5
6
7
8
9
10










11
12
13
14
15






二、填空题（答案联系QQ:3326650399 微信：cs80188 熊猫奥鹏（www.188open.com）2分，共30分）

1. 下面程序段的时刻杂乱度为________。
sum=1; for(i=0;sum2. 设数组a[M](M为最大空间个数)作为循环行列Q的存储空间，front为队头指针(指向榜首个寄存数据的方位)，rear为队尾指针(指向最终一个寄存数据方位的下一个)，则断定Q行列的队满条件是_____________。
3. 若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是________。
4. 散列法存储的根本思想是由_______________决议数据的存储地址。

5.在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是________。

6. 设一棵彻底二叉树有700个结点，则共有____________个叶子结点 。

7. n个极点e条边的图选用邻接矩阵存储，深度优先遍历算法的时刻杂乱度为_______________；若选用邻接表存储时，该算法的时刻杂乱度为______________ 。

8. 在堆排序和疾速排序中，若初始记载挨近正序或反序，则选用______________；若初始记载根本无序，则最佳选用_______________。

9. 若要求一个稀少图G的最小生成树，最佳用_______________ 算法来求解。

10. 一棵深度为6的满二叉树有 ________________ 个分支结点和____________个叶子。

11.用5个权值{3, 2, 4, 5, 1}结构的哈夫曼（Huffman）树的带权途径长度是__________。

12. 有向图G用邻接矩阵存储，其第i行的一切元素之和等于极点i的____________。

三、回答题(答案联系QQ:3326650399 微信：cs80188 熊猫奥鹏（www.188open.com）9分，共27分)

1. 已知以下的有向图，用Dijkstra算法求出从极点1动身到各极点的最短途径（按步给分）。




2.待排序的序列为：25,47,36,21,90,84,62,78,15,32。写出用（大根）堆排序的每一趟的成果。







3.一棵度为2的有序树与一棵二叉树有何差异？







四、程序设计题（共13分）
1、已知r[]为一维数组，其间r[0]到r[n-1]为待排序的n个元素，排序好的元素仍放在r[0]到r[n-1]中，请写出对该数组进行非递归的直接刺进排序算法，取名为insertsort(elemtype r[],int n)。







1
福建师范大学试卷纸