专升本数据结构2答案.doc
128 浏览量
2024-01-14
13:33:37
上传
评论
收藏 98KB DOC 举报
第 1 页 共 2 页
《数据结构》课程试题 2 参考答案及评分标准
一、单项选择题(每题 2 分，共 30 分)
1. D 2. C 3. B 4. C 5. D
6. B 7. A 8. A 9. A 10. B
11.①C②B③C 12.A 13. B
二、判断题(每题 1.5 分，共 10 分)
1．T
2. T
3. T
4. F
5. T
6. T
7. F
8. F
9. T
10.F
三、简答题（共 25 分）
1.（本题 6 分）
答：数据结构按逻辑结构可以分为集合、线性结构、树和图四种。（6 分）
2.（本题 6 分）
答：头指针： 指向链表的第一个结点（或为头结点或为首元结点）。（2 分）
头结点：为了方便操作，通常在链表的首元结点之前附设一个结点，该结点的数据中不存储
线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结
点进行统一处理。（2 分）
首元结点：指链表中存储线性表中的第一个数据元素的结点。（2 分）
若链表中附设头结点，不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头
指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储
结构表示同一逻辑结构的问题。
3．（本题 10 分）
答：如图所示 ，存在问题(设数组大小为 M)，则：
当 front=-1,rear=M-1 时，再有元素入队发生溢出——真溢出。
当 front�-1,rear=M-1 时，再有元素入队发生溢出——假溢出。（5
分）
解决方案
1 队首固定，每次出队剩余元素向下移动——浪费时间。（2 分）
2 循环队列（3 分）
基 本 思 想 ： 把 队 列 设 想 成 环 形 ， 让 sq[0] 接 在 sq[M-1] 之 后 ， 若
rear+1==M,则令 rear=0;
入队： rear=(rear+1)%M; sq[rear]=x;
出队： front=(front+1)%M; x=sq[front];
4． （本题 3 分）
答：树的带权路径长度：为树中所有叶子结点的带权路径长度之和，通常记作
WPL=
W
K
为每个叶子结点的权值，L
K
路径长度；其中带权路径长度 WPL 最小的二叉树称最优二叉树或哈夫曼树。
（3 分）
四、应用题(共 30 分)
1．（本题 15 分）
前序遍历结果为：124753689（5 分）
中序遍历结果为：742513869（5 分）
后序遍历结果为：745289631（5 分）
rear
1
2
3
4
5
0
J4
J5
J6
front
å
n
k k
k=1
WPL = w l
资源评论
