广东工业大学-数据结构试卷.doc

广东工业大学考试试卷 ( B )

课程名称: 数据结构 试卷满分 100 分
考试时间: 年 月 日 (第 周 星期 )
题 号
一
二
三
四
五
总分
评卷得分

评卷签名

复核得分

复核签名

一．单项选择题（共16分，每题2分）
1．设某数据结构的二元组形式表示为A=(D,S)，D={a,b,c,d,e,f}，
S ={<a,b>,<a,c>,<b,d>,<b,e>,<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] 层次遍历

6．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。
[A] G中有弧<Vi，Vj> [B] G中有一条从Vi到Vj的路径
[C] G中没有弧<Vi，Vj> [D] G中有一条从Vj到Vi的路径

学 院： 专 业： 学 号： 姓 名：

装 订 线

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。

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）执行升序排序。试根据堆排序原理，填写完整下列各步骤结果。
建立大顶堆结构：________________________
交换与调整：
（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;
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;
}
}

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为起点，对图进行深度优先遍历。请在空缺处填入合适内容，使其成为完整的算法。
void f4(ALGraph G, int v) {
AcrNode *p;
visited[v]=1; visit(v);
p = ① ;
while (p) {
v = p->adjvex;
if (!visited[v]) ② ;
p = ③ ;
}
}

五．算法设计题（8分）
假设二叉树T中结点值互不相同，并采用二叉链表存储结构
typedef struct node {
ElemType data;
struct node *lchild, *rchild;
} *BiTree;
编写算法，求元素值为x的结点在二叉树T中的层次。

广东工业大学试卷用纸，共6页，第6页