课程名称： 数据结构A 学时： 56
考核方式：笔试闭卷
班级： 191091-4、192091-3、193091-2
任课教师：
一、单项选择题：1－20小题，每小题2分，共40分。在每小题给出的四个选项中，请选出一项最符合题目要求的选项。
1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（ D ）。
for(int i=1;i<n/2;)
i=2*i;
A.O(n2) B.O(n) C.O(nlog2n) D.O(log2n)
2.若某线性表最常用的操作是存取任意指定序号的元素和在表尾进行插入和删除运算，则利用（ A ）存储方式最节省时间。
A.顺序表 B.双链表
C.带头结点的双循环链表 D.单循环链表
3.某线性表中最常用的操作是在表尾插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。
A.单链表 B.仅有头指针的单循环链表
C.双链表 D.仅有尾指针的单循环链表
4.若进栈序列为123456，且进栈和出栈可以交替进行，则不可能出现的出栈序列为（ D ）。
A.125436 B.325641 C.342165 D.546231
5.若用数组A[60]存放循环队列的元素，已知头指针值为35，当前队列中有40个元素，则队列的尾指针值为( C )。约定头指针指向队头元素的前一个位置。
解答：(35+40)%60=15
A.75 B.20 C.15 D.5
6.深度为6的完全二叉树（根结点的深度为0）至少有（ B ）个结点。
A.32 B.64 C.127 D.128
解答：第0-5层全满，第6层1个，1+2+4+8+16+32+1=64个。
7.将一棵森林F转换为孩子兄弟链表表示的二叉树T，则F的后根遍历是T 的（ B ）。
A.前序遍历 B.中序遍历 C.后序遍历 D.层序遍历
8.假设使用图的深度优先搜索DFS算法从根开始遍历一棵二叉树，先访问左子树再访问右子树，则访问结点的顺序相当于二叉树的（ A ）序列。
A.前序遍历 B.中序遍历 C.后序遍历 D.层次遍历
9.下列线索二叉树中（用虚线表示线索），符合后序线索二叉树定义的是（ C ）。
a
c
b
d
NULL
NULL
a
c
b
d
NULL
a
c
b
d
NULL
a
c
b
d
A. B.
C.D.
10.下列关于图的叙述中，正确的是（ D ）
I．无向连通图中所有顶点的度之和为偶数
II．存储稀疏图，用邻接矩阵比邻接表更省空间
III．若有向图中存在拓扑序列，则该图不存在回路
A.只有II B.只有I和II C.只有III D.哈夫曼编码树的带权路径长度只有I和III
11.若无向图 G =（V，E）中含 7 个顶点，则保证图 G 在任何情况下都是连通的，则需要的边数最少是（ A ）。
A. 6 B. 15 C. 16 D. 21
12.对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（B）
a
e
d
c
b
A. 5 B. 4 C. 3 D. 2
13.已知一个长度为 8 的有序顺序表，若采用折半查法查一个不存在的元素， 则比较次数最多的是（ B ）
A. 3 B. 4 C. 5 D. 6
14.对于下列关键字序列，不可能构成某二叉排序树中一条查路径的序列是（ A ）。
A. 85, 12, 81, 14, 84, 61 B. 82, 10, 81, 24, 78, 25
C. 11, 79, 67, 19, 26, 28 D. 2, 15, 61, 58, 23, 24
15.下列二叉树中，不满足平衡二叉树定义的是（ A ）。
A. B. C. D.
16. 下列叙述中，不符合m阶B-树定义要求的是（ D ）。
A．根结点至多有m-1个关键字 B.所有叶结点都在同一层上
C．各结点内关键字均升序或降序排列 D.每个结点至少有两棵非空子树
17.为提高散列（Hash）表的查效率，可以采取的正确措施是（ D ）。
I．增大装载因子
II．设计冲突少的散列函数
III．处理冲突时尽量减少产生聚集（堆积）现象
A.只有I B.只有II C.只有I和II D.只有II和III
18. 若数据元素序列20，27，31，5，7，11，42，2，4是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ B ）。
A.冒泡排序 B.插入排序 C.选择排序 D.二路归并排序
19.为实现快速排序算法，待排序序列宜采用的存储方式是（ A ）。
A.顺序存储 B.散列存储 C.链式存储 D.索引存储
20.设有5000个无序记录，希望得到前10个最小元素，用（ C ）方法最快。
A.冒泡排序 B.快速排序 C.堆排序 D.简单选择排序
二、简答题。21－23小题。共35分。
21.（8分）假定用于通讯的电文仅由7个字母C1, C2, …, C7组成，各个字母在电文中出现的
次数分别为1, 3, 5, 6, 7，10, 12，试为这7个字母设计哈夫曼树，要求画出哈夫曼树，写出各个字符的哈夫曼编码略
答：哈夫曼树（略）构造成功5分，编码正确3分
22.（18分）已知6个顶点（顶点编号0~5）的有向带权图G，其邻接矩阵A为上三角矩阵，按“行”为主序（行优先）保存在如下的一维数组中。
3 | 5 | ∞ | ∞ | ∞ | 4 | ∞ | 5 | ∞ | 3 | 2 | ∞ | ∞ | 2 | 4 |
（1）写出图G的邻接矩阵A。（4分）
（2）画出有向带权图G。（2分）
（3）求图G的关键路径，并计算该关键路径的长度。（7分）
（4）采用Dijkstra算法求编号为0的顶点到其余各顶点的最短路径。（5分）
（3）关键路径为0—>1245，长度为3+4+2+4=13.
（4）01:<0,1>,3
02:<0,2>,5
04:<0,2,4>,7
03:<0,2,3>,8
05:<0,2,3,5>,10
23.（9分）将关键字序列(SUN, MON, TUE, WED, THU, FRI, SAT)散列存储到一个下标从0开始的一维数组中，散列函数为：H(key) = 关键字key中第一个字母在字母表中的序号 % 7，处理冲突采用二次探测再散列法（地址增量序列为1,-1,4,-4,9,-9,……），要求装载因子
为0.7。
（1）请画出所构造的散列表。（7分）
（2）计算等概率情况下，查成功的平均查长度。（2分）
答： （1）
关键字 | Mon | Tue | Wed | Thu | Fri | Sat | Sun |
13 | 20 | 23 | 20 | 6 | 19 | 19 | |
散列地址 | 6 | 6 | 2 | 6 | 6 | 5 | 5 |
探查次数 | 1 | 2 | 1 | 3 | 4 | 3 | 4 |
构造的散列表如下：（7分）
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
关键字 | FRI | WED | SAT | THU | MON | TUE | SUN | |||
【评分说明】所画的散列表长度正确（长度为10，下标从0到9），给1分。填写关键字正确，每个给1分。考生可以不写出计算过程。若解答部分正确，酌情给分。
（2）查成功的平均查长度：（2分）
因为查长度为1的关键字有4个，查长度为2的关键字有1个，查长度为3的关键字有2个，所以查成功的平均查长度：
ASL成功=（1次×2+2次×1+3次×2+4*1）/7=2（2分）
各位置对应的探查次数如下表所示：
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
探查次数 | 1 | 2 | 1 | 5 | 4 | 3 | 2 |
【评分说明】若分别采用公式（为装填因子）：
和
计算查成功，且计算正确，可共给2分。若解答部分正确，酌情给分。
三、算法设计题。24－25小题。共25分。每题要求：
24.（12分）给定有m个整数的递增有序数组a[m]和有n个整数的递减有序数组b[n]，试写出算法，将数组a和b归并为递增有序数组c[m+n] （要求算法的时间复杂度为O(m+n)）。
答：（1） 描述算法的基本设计思想（3分）
把b[n]逆置，然后两个递增有序数组归并成c数组。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论