第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
武汉大学11年数据结构真题及答案.doc
武汉大学计算机学院
2011年－2012学年第一学期“数据结构”考试试题（A）
二、问答题（共3小题，每小题10分，共30分）
三、算法设计题（共3小题，每小题10分，共30分）
武汉大学计算机学院
2011年－2012学年第一学期“数据结构”考试试题参考答案（A）
二、问答题（共3小题，共30分）
三、算法设计题（每小题10分，共30分）
武汉大学计算机学院
2011 年－2012 学年第一学期“数据结构”考试试题（A）
要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都
要写上姓名和学号。
一、单项选择题（共 20 小题，每小题 2 分，共 40 分）
。
。
C.单链表
B.有序表
D.顺序表
1. 下列各选项中属于逻辑结构的是
A.哈希表
2. 对于数据结构，以下叙述中不正确的是
A.数据的逻辑结构与数据元素本身的形式和内容无关
B.数据的逻辑结构是数据的各数据项之间的逻辑关系
C.数据元素是数据的基本单位
D.数据项是数据的最小单位
3. 某算法的时间复杂度为 O(n2)，表明该算法的
A.问题规模是 n2
C.执行时间与 n2 成正比
4. 通常在单链表中增加一个头节点，其目的是为了
A.使单链表至少有一个节点
C.方便单链表运算的实现
5. 删除某个双链表中的一个节点（非首、尾节点），需要修改
A.1
6. 栈和队列是两种不同的数据结构，但它们中的元素具有相同的
A.抽象数据类型
C.存储结构
7. 元素 a、b、c、d、e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直
B.标识表节点中首节点的位置
D.说明单链表是线性表的链式存储
B.执行时间等于 n2
D.问题规模与 n2 成正比
B.逻辑结构
D.运算
个指针域。
D.4
C.3
B.2
。
。
。
到所有的元素都出栈，则所有可能的出栈序列中，以元素 d 开头的序列个数是
D.6
A.3
8. 设环形队列中数组的下标是 0～N-1，其头尾指针分别为 f 和 r（f 指向队列中队头
C.5
B.4
。
元素的前一个位置，r 指向队尾元素的位置），则其元素个数为
B.r-f-1
A.r-f
9. 已知循环队列存储在一维数组 A[0..n-1]中，且队列非空时 front 和 rear 分别指向队
头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在 A[0]处，则初
始时 front 和 rear 的值分别是
C.(r-f)％N+1
A.0，0
D.n-1，n-1
10. 对于 n 阶（n≥2）对称矩阵，采用压缩方法以行序优先存放到内存中，则需要
C.n-1，0
个
。
B.0，n-1
。
D.(r-f+N)％N
存储单元。
2
数据结构试题
A.n(n+1)/2
11. 一棵度为 4 的树 T 中，若有 20 个度为 4 的节点，10 个度为 3 的节点，1 个度为 2
B.n(n-1)/2
D.n2/2
C.n2
的节点，10 个度为 1 的节点，则树 T 的叶子节点个数是
。
A.41
12. 一个具有 n（n≥2）个顶点的无向图，至少有 ① 个连通分量，最多有 ② 个
D.122
C.113
B.82
连通分量。
B.1
C.n-1
A.0
13. 含有 n（n≥2）个顶点的无向图的邻接矩阵必然是一个
A.对称矩阵
14. 对如图 1 所示的无向图，从顶点 A 出发得到的广度优先序列可能是
A.ABECD
C.上三角矩阵
D.n
。
D.对角矩阵
D.ABDEC
C.ACDBE
B.ACBDE
B.零矩阵
。
图 1 一个无向图
15. 设有 100 个元素的有序顺序表，用折半查找时，成功时最大的比较次数是
A.25
16. 已知一个长度为 16 的顺序表，其元素按关键字有序排序，若采用折半查找法查找
C.10
B.50
。
D.7
一个不存在的元素，则平均关键字比较的次数是
。
。
B.70/16
C.60/17
D.60/16
A.70/17
17. 以下关于 m 阶 B-树的叙述中正确的是
A.每个节点至少有两棵非空子树
B.树中每个节点至多有m/2-1 个关键字
C.所有叶子节点均在同一层上
D.当插入一个关键字引起 B-树节点分裂时，树增高一层
18. 为提高散列（哈希）表的查找效率，可以采取的正确措施是
Ⅰ.增大装填（载）因子
Ⅱ.设计冲突（碰撞）少的散列函数
Ⅲ.处理冲突（碰撞）时避免产生聚集（堆积）现象
A.仅Ⅰ
C.仅Ⅰ、Ⅱ
19. 数据序列{8,9,10,4,5,6,20,1,2}只能是
A.简单选择排序
B.冒泡排序
20. 用某种排序方法对顺序表{24,88,21,48,15,27,69,35,20}进行排序，各趟元素序列的
的两趟排序后的结果。
C.直接插入排序
D.仅Ⅱ、Ⅲ
D.堆排序
B.仅Ⅱ
。
变化情况如下：
（1）{24,88,21,48,15,27,69,35,20}
（2）{20,15,21,24,48,27,69,35,88}
（3）{15,20,21,24,35,27,48,69,88}
（4）{15,20,21,24,27,35,48,69,88}
则所采用的排序方法是
A.快速排序
数据结构试题
。
3
B.简单选择排序
C.直接插入排序
D.归并排序
二、问答题（共 3 小题，每小题 10 分，共 30 分）
1. 一棵二叉排序树按先序遍历得到的关键字序列为：(50,38,30,45,40,48,70,60,75,80)。
回答以下问题：
（1）画出该二叉排序树。
（2）求在等概率条件下的查找成功的平均查找长度。
2. 有一个无向带权图如图 2 所示，采用 Dijkstra 算法求顶点 0 到其他顶点的最短路径
和最短路径长度，要求给出求解过程（即给出求最短路径中各步骤的 S、dist 和 path 值）。
图 2 一个无向图
3. 简要叙述堆和二叉排序树的区别，并给出关键字序列{3,26,12,61,38,40,97,75,53,87}
调整为大根堆后的结果（直接画出调整后的大根堆）。
三、算法设计题（共 3 小题，每小题 10 分，共 30 分）
1．有一个线性表(a1,a2,…,an)，采用带头节点的单链表 L 存储，设计一个就地算法将其
所有元素逆置。所谓就地算法是指算法的空间复杂度为 O(1)。
2．假设二叉树采用二叉链存储结构，设计一个算法把一棵含有 n 个节点的二叉树 b 复制到另
一棵二叉树t 中。给出你所设计算法的时间和空间复杂度。
3. 假设一个不带权的有向图 G 采用邻接表存储，设计一个算法判断图 G 中是否存在
顶点 i 到顶点 j 的边，若存在这样的边返回 1，否则返回 0。
4
数据结构试题
武汉大学计算机学院
2011 年－2012 学年第一学期“数据结构”考试试题参考答
案（A）
要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写
上姓名和序号。
一、单项选择题（每小题 2 分，共 40 分）
4. C
9. B
14. B
19. C
3. C
2. B
7. B
8. D
12. ①B ②D 13. A
17. C
18. D
1. B
6. B
11. B
16. A
5. B
10. A
15. D
20. A
二、问答题（共 3 小题，共 30 分）
1.答（1）先序遍历得到的序列为：(50,38,30,45,40,48,70,60,75,80)，中序序列是一个有
序序列，所以为：(30,38,40,45,48,50,60,70,75,80)，由先序序列和中序序列可以构造出对应
的二叉树，如下图所示。
（2）ASL 成功=(1×1+2×2+4×3+3×4)/10=2.9。
【评分说明】（1）占 8 分，（2）占 2 分。
2. 答：对应的邻接矩阵如下：
11 ∞ ∞ ∞
0
7
10 9 ∞ ∞
7
0
5
11 10 0
8
0 ∞ ∞
∞ 9
5
6
∞ ∞ 7 ∞ 0
∞ ∞ 8 ∞ 6
0
求解过程如下：
7
S
0
1
2
dist
3
4
5
0
1
path
2
3
4
5
数据结构试题
0
0
0
0
0
0
7
7
7
7
7
7
11 ∞ ∞ ∞
11 16 ∞ ∞
11 16 18 19
11 16 18 19
11 16 18 19
11 16 18 19
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1 -1 -1
-1 -1
1
1
2
2
1
2
2
1
2
2
2
2
1
{0}
{01}
{0 1 2}
{0 1 2 3}
{0 1 2 3 4}
{0 1 2 3 4 5}
求解结果如下：
从 0 到 1 的最短路径长度为:7 路径为:0,1
从 0 到 2 的最短路径长度为:11 路径为:0,2
从 0 到 3 的最短路径长度为:16 路径为:0,1,3
从 0 到 4 的最短路径长度为:18 路径为:0,2,4
从 0 到 5 的最短路径长度为:19 路径为:0,2,5
【评分说明】结果为 5 分,过程为 5 分。
3. 简要叙述堆和二叉排序树的区别，并给出关键字序列{3,26,12,61,38,40,97,75,53,87}
调整为大根堆后的结果（直接画出调整后的大根堆）。
答：以小根堆为例，堆的特点是双亲节点的关键字必然小于等于孩子节点的关键字，
而两个孩子节点的关键字没有次序规定。而二叉排序树中，每个双亲节点的关键字均大于
左子树节点的关键字，每个双亲节点的关键字均小于右子树节点的关键字，也就是说，每
个双亲节点的左、右孩子的关键字有次序关系。
关键字序列{3,26,12,61,38,40,97,75,53,87}调整为大根堆后的结果如下：
【评分说明】两小题各占 5 分。
三、算法设计题（每小题 10 分，共 30 分）
1．解：对应的算法如下：
void Reverse1(LinkList *&L)
LinkList *p=L->next,*q;
{
L->next=NULL;
while (p!=NULL)
q=p->next;
{
p->next=L->next;
L->next=p;
//p 指向开始节点
//将*p 节点插入到新建链表的前面
6
数据结构试题
p=q;
}
}
【评分说明】单链表类型可自行设计。
2．解：对应的递归算法如下：
void Copy(BTNode *b,BTNode *&t)
{
ArcNode *p;
p=G->adjlist[i].firstarc;
while (p!=NULL && p->adjvex!=j)
p=p->nextarc;
if (p==NULL)
return 0;
else
return 1;
}
【评分说明】邻接表类型可自行设计。
if (b==NULL)
else
{
t=NULL;
t=(BTNode *)malloc(sizeof(BTNode));
//复制一个根节点*t
t->data=b->data;
Copy(b->lchild,t->lchild);
//递归复制左子树
Copy(b->rchild,t->rchild)； //递归复制右子树
}
}
算法的时间复杂度为 O(n)，空间复杂度为 O(n)。
【评分说明】二叉链类型可自行设计。
【评分说明】算法的时间和空间复杂度各占 1 分。
3. 解：对应的算法如下：
int HasArc(AGraph *G,int i,int j) //判断图 G 中是否存在边
{
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
