(完整word版)广东工业大学数据结构试卷
- 格式：doc
- 大小：61.50 KB
- 文档页数：7
(完整word版)广东工业大学数据结构试卷
广东工业大学试卷用纸，共7页，第1页
学 院： 专 业： 学 号： 姓 名：
装 订 线 广东工业大学考试试卷 ( B )
课程名称： 数据结构 试卷满分 100
分
考试时间: 年 月 日 （第 周 星期 )
题 号 一 二 三 四 五 总分
评卷得分
评卷签名
复核得分
复核签名
一．单项选择题（共16分，每题2分)
1．设某数据结构的二元组形式表示为A=(D,S），D={a,b，c,d，e，f｝,
S =｛，,，〈c,e>，〈c,f>}，则数据结构A是( ）。
［A］ 线性结构 ［B］ 树型结构 [C] 集合结构 ［D]
图型结构
2．假设以数组A[60]存放循环队列的元素，如果当前的尾指针rear = 15，头指针front＝32，则当前循环队列的元素个数是（ ）。
[A] 43 [B] 16 [C] 17 [D]42
3．广义表A=(a,b，（c,d）)，执行Head(Head（Tail（Tail(A））））的结果是（ ）。
[A] （c） [B］ (d) [C] c [D］ d
4．下列有关二叉树的正确陈述是（ ）.
[A］ 二叉树中任何一个结点的度都为2 [B］ 一棵二叉树的度可以小于2
[C] 二叉树中至少有一个结点的度为2 [D］ 二叉树的度为2
5．若将一棵树t 转换为孩子—兄弟链表表示的二叉树h,则t的后根遍历是h的
（ ）.
[A］ 前序遍历 [B］ 中序遍历 [C] 后序遍历 [D］ 层次遍历 (完整word版)广东工业大学数据结构试卷
广东工业大学试卷用纸，共7页，第2页
7．散列表的地址区间为0—17，散列函数为H(K)=K mod 17，采用线性探测法处理冲突，并将关键字序列26,25,72，38,8,18，59依次存储到散列表中。元素59存放在散列表中的地址是（ ）。
［A］ 8 [B］ 9 [C］ 10
［D］ 11
8．ISAM文件和VASM文件属于（ )。
［A] 索引非顺序文件 [B］ 顺序文件 [C] 索引顺序文件 [D］ 散列文件
二．填空题（共12分,每空1分)
1．线性表L=（a1，a2，…，an）采用顺序存储表示，假定删除表中任一元素的概率相同,则删除一个元素需要移动元素的平均次数是___________。
2．在栈结构中，允许插入和删除的一端称为___________，另一端称为___________。
3．模式串P=’ababc’的next函数值序列为___________。
4．深度为6的完全二叉树的结点数至少有___________个。
5．线索二叉树的左线索指向其___________，右线索指向其___________.
6．已知无向图G =（V, E）,其中V={a， b, c, d， e},E=｛(a,b),（a，d),(a，c），（d,c）,(b，e）}，若从顶点a开始遍历图，得到的序列为a,b，e,c，d，则采用的是___________遍历方法.
7．动态查找表和静态查找表的重要区别在于前者包含有___________和___________运算，而后者不包含这两种运算。
8．简单选择排序的平均时间复杂度是___________，堆排序的平均时间复杂度是___________。
三．解答题（共40分)
1．（6分)假设电文中仅由a到e共5个字母组成，字母在电文中出现的频率依次为
0。2，0.15,0。32,0.28，0.05
请画出由此构造的哈夫曼树（要求树中所有结点的左右孩子必须是左大右小）,并计算该哈曼夫树的带权路径长度WPL.
(完整word版)广东工业大学数据结构试卷
广东工业大学试卷用纸，共7页，第3页 2．(8分)设对称矩阵A=
（1）若将A中包括主对角线的下三角元素按行的顺序压缩到数组S中，即S为
1 0 3 0 0 0 2 0 5 0
下标： 1 2 3 4 5 6 7 8 9
10
请求出A中任一元素的行列下标［i,j]（1<=i，j〈=4)与S中元素的下标K之间的关系;
（2）若将A［i,j]（1〈=i, j<=4）视为稀疏矩阵，画出其三元组表.
3．(10分）若带权无向图G的邻接矩阵如右图所示，顶点集是{V1， V2， V3， V4,
V5}，
（1)画出图G的邻接表，要求每个顶点的表结点序号都是按照从
小到大的次序链接；
（2）画出图G的最小生成树。
4．(8分）从空树开始构造一棵平衡二叉排序树，依次插入的关键字为（11, 13, 15, 17，
19, 20），请按下图要求画出该树的部分生成过程。
插入11,13，15后 插入17后 插入19后 插入20后
5．（8分）对序列（3, 87， 12, 61, 70， 97, 26, 45）执行升序排序。试根据堆排05025000003020014324453234212531(完整word版)广东工业大学数据结构试卷
广东工业大学试卷用纸，共7页，第4页 序原理,填写完整下列各步骤结果。
建立大顶堆结构：________________________
交换与调整：
（1）87, 70, 26， 61, 45， 12， 3, 97； (2）________________________；
(3)61， 45， 26， 3， 12, 70, 87， 97； (4）45， 12, 26， 3, 61， 70，
87, 97；
（5）26, 12, 3， 45, 61, 70， 87, 97； (6）________________________；
(7）3， 12, 26, 45， 61， 70, 87, 97；
四．算法阅读题（共24分）
1．(6分）阅读算法f1，并回答问题。
（1）设线性表L=(2， 3， 6， 5， 4)，并采用带头结点的单链表储存，写出执行算法f1(L）后的L;
（2）简述算法f1(L)对线性表L的操作意义.
void f1(LinkList ＆L) ｛
LinkList p, s；
p = L->next;
L—>next = NULL；
while (p!= NULL） ｛
s=p—〉next； (完整word版)广东工业大学数据结构试卷
广东工业大学试卷用纸，共7页，第5页 p-〉next=L->next;
L->next =p;
p=s;
｝
｝
2．（6分）假设以带头结点的循环链表表示队列,并且只设一个指针rear指向队尾元素（注意不设头指针），算法f2实现相应的出队列操作。请在空缺处填入合适内容，使其成为完整的算法。
Status f2（LinkList ＆rear, ElemType ＆x）｛
LinkList front;
if （ ① ) return ERROR；
else ｛
front = ② ;
rear—〉next—〉next = front—〉next；
if （ front == rear ) rear = ③ ；
x = front-〉data;
free（front）;
return OK；
｝
｝ (完整word版)广东工业大学数据结构试卷
广东工业大学试卷用纸，共7页，第6页 K
H
F
E
A
B
G
I
C
D
3．（6分）阅读下列算法，并回答问题
（1） 设二叉树bt如右图所示，请写出执行
int c=0； f3(bt， c）；
之后c的结果;
（2） 简述算法f3的功能.
void f3(BiTree bt, int &x) ｛
if (bt） {
if（ bt-〉lchild ｜| bt->rchild )
x++；
f3(bt-〉lchild， x);
f3（bt-〉rchild， x)；
｝
}
4．（6分)图的邻接表存储结构的类型定义如下：
typedef struct ArcNode ｛
int adjvex； // 该弧所指向的顶点的位置
ArcNode ＊nextarc; // 指向下一条弧的指针
｝ ArcNode； // 定义弧的结点
typedef struct {
VertexType data; // 顶点信息
ArcNode ＊firstarc; // 指向第一条依附该顶点的弧
} VNode， AdjList［MAX_VERTEX_NUM]; // 定义顶点数组
typedef struct {
AdjList vertices;
int vexnum, arcnum; // 图的当前顶点数和弧数
int kind；
} ALGraph; // 邻接表类型
算法f4（G, v）是以顶点v为起点，对图进行深度优先遍历。请在空缺处填入合适内容,使其成为完整的算法.
