s+=i*j；
A.O
（1）B.O（n）
C.O（2n）D.O（n2）
2.假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是（）22
A.head==NULL；B.head->next==NULL；
C.head!
=NULL；D.head->next==head；
3.栈是一种操作受限的线性结构，其操作的主要特征是（）32
A.先进先出B.后进先出
C.进优于出D.出优于进
4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。
若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（）
A.（rear-front-1）％nB.（rear-front）％n
C.（front-rear+1）％nD.（rear-front+n）％n
5.判断两个串大小的基本准则是（）52
A.两个串长度的大小B.两个串中首字符的大小
C.两个串中大写字母的多少D.对应的第一个不等字符的大小
6.二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为（）60
A.1012B.1017
C.1034D.1036
a00
a01
a02
a03
a04
a32
7.高度为5的完全二叉树中含有的结点数至少为（）72
A.16B.17
C.31D.32
8.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为（）
A.5B.8
C.11D.18
9.下列所示各图中是中序线索化二叉树的是（）81A
10.已知含6个顶点（v0，v1，v2，v3，v4，v5）的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为（）108
A.（v0，v1，v2，v5，v4，v3）
B.（v0，v1，v2，v3，v4，v5）
C.（v0，v1，v5，v2，v3，v4）
D.（v0，v1，v4，v5，v2，v3）
11.如图所示有向图的一个拓扑序列是（）
A.ABCDEF
B.FCBEAD
C.FEDCBA
D.DAEBCF
12.下列关键字序列中，构成大根堆的是（）
A.5，8，1，3，9，6，2，7B.9，8，1，7，5，6，2，33
C.9，8，6，3，5，l，2，7D.9，8，6，7，5，1，2，3
13.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为（）172
A.
B.
C.
D.
14.已知一个散列表如图所示，其散列函数为H（key）=key％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为（）d197
15.数据库文件是由大量带有结构的（）206
A.记录组成的集合B.字符组成的集合
C.数据项组成的集合D.数据结构组成的集合
二、填空题（本大题共10小题，每小题2分，共20分）
请在每小题的空格中填上正确答案。
错填、不填均无分。
16.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的_________。
输入量8
17.在双向循环链表中插入一个新的结点时，应修改_________个指针域的值。
428
18.若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现_________个不同的出栈序列。
5
19.链串的结点大小定义为结点的_________中存放的字符个数。
数据域54
20.广义表（a，（d，（c）））的深度为_________。
367
21.在含有3个结点a，b，c的二叉树中，前序序列为abc且后序序列为cba的二叉树有_________棵。
4
22.若用邻接矩阵表示有向图，则顶点i的入度等于矩阵中_________。
第i列非零元素的个数107
23.对关键字序列（15，18，11，13，19，16，12，17，10，8）进行增量为5的一趟希尔排序的结果为_________。
15，12，11，10，8，16，18，17
24.索引顺序查找的索引表由各分块中的最大关键字及各分块的_________构成。
起始位置173
25.VSAM文件的实现依赖于操作系统中的_________存取方法的功能。
分页215
三、解答题（本大题共4小题，每小题5分，共20分）
26.假设有一个形如
的8×8矩阵，矩阵元素都是整型量（次对角线以上的元素都是0）。
若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组B中，请回答下列问题：
（1）B数组的体积至少是多少?
（2）若a18存储在B[0]中，a56存储在B[k]中，则k值为多少?
（1）（1+8）*8/2=36存放次对角线以上的零为37
（2）12
27.对关键字序列（5，8，1，3，9，6，2，7）按从小到大进行快速排序。
（1）写出排序过程中前两趟的划分结果；
（2）快速排序是否是稳定的排序方法?
（1）
第一趟划分结果；（2，3，1），5，（9，6，8，7）
第二趟划分结果；（1，2，3），5，（9，6，8，7）
第三趟划分结果；（1，2，3），5，（7，6，8，9）
第四趟划分结果；1，2，3，5，6，7，8，9
第一趟划分过程
2
3
1
5
9
6
8
7
1
2
3
5
9
6
8
7
1
2
3
5
7
6
8
9
1
2
3
5
6
7
8
9
↑j
↑i
（5，8，1，3，9，6，2，7）
1．（2，8，1，3，9，6，5，7）
2．（2，5，1，3，9，6，8，7）
3．（2，3，1，5，9，6，8，7）
4．（2，3，1，5，9，6，8，7）
第二趟划分过程
（2，3，1，5，9，6，8，7）
1．（1，2，3，5，7，6，8，9）
（2）非稳定
2
3
1
5
9
6
8
7
1
2
3
5
5
7
6
8
9
5
6
7
8
9
↑j
↑i
第一趟：
（2，3，1）5（9，6，8，7）
第二趟：
1，2，3，5（9，6，8，7）
第三趟：
1，2，3，5，（7，6，8），9
第四趟：
1，2，3，5，6，7，8，9
28.假设通信电文使用的字符集为{a，b，c，d，e，f，g，h}，各字符在电文中出现的频度分别为：
7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。
要求：
（1）画出你所构造的哈夫曼树（要求树中左孩子结点的权值不大于右孩子结点的权值）；
（2）按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码。
（1）
（2）
29.已知3阶B—树如图所示，
非根【1，2】P184
根【1，2】
（1）画出将关键字6插入之后的B—树；
（2）画出在
（1）所得树中插入关键字2之后的B—树。
四、算法阅读题（本大题共4小题，每小题5分，共20分）
30.假设以带头结点的单链表表示线性表，单链表的类型定义如下：
typedefintDataType;
typedefstructnode{
DataTypedata;
structnode*next;
}LinkNode,*LinkList;
阅读下列算法，并回答问题：
（1）已知初始链表如图所示，画出执行f30（head）之后的链表；
题30图
（2）简述算法f30的功能。
voidf30（LinkListhead）
{LinkListp,r,s;
if（head->next）{
r=head->next;
p=r->next;
r->next=NULL;
while（p）{
s=p;
p=p->next;
if（s->data%2==0）{
s->next=head->next;
head->next=s;
}else{
s->next=r->next;
r->next=s;
r=s;
}
}
}
}
（1）
（2）
31.假设以二叉链表表示二叉树，其类型定义如下：
typedefstructnode{
DataTypedata;
structnode*lchild,*rchild;//左右孩子指针
}*BinTree;
阅读下列算法，并回答问题：
（1）已知以T为根指针的二叉树如图所示，
写出执行f31（T）之后的返回值；
（2）简述算法f31的功能。
intf31（BinTreeT）
{intd;
if（!
T）return0;
d=f31（T->lchild）+f31（T->rchild）;
if（T->lchild&&T->rchild）
returnd+1;
else
returnd;
（1）3
（2）统计度为2的结点个数
32.设有向图邻接表定义如下：
typedefstruct{
VertexNodeadjlist[MaxVertexNum];
intn，e；／／图的当前顶点数和弧数
}ALGraph；／／邻接表类型
其中顶点表结点VertexNode
边表结点EdgeNode结构为：
阅读下列算法，并回答问题：
（1）已知某有向图存储在如图所示的邻接
表G中，写出执行f32（＆G）的输出；
（2）简述算法f32的功能。
intvisited[MaxNum];
voidDFS（ALGraph*G,inti）{
EdgeNode*p;
visited[i]=TRUE;
if（G->adjlist[i].firstedge==NULL）
printf（"%c",G->adjlist[i].vertex）；
else{
p=G->adjlist[i].firstedge;
while（p!
=NULL）{
if（!
visited[p->adjvex]）
DFS（G,p->adjvex）;
p=p->next;
}
}
}
voidf32（ALGraph*G）{
inti;
for（i=0;in;i++）
visited[i]=FALSE;
for（i=0;in;i++）
if（!
visited[i]）DFS（G,i）;
}
（1）ABECD
（2）图的深度优先搜寻
33.下列算法f33的功能是对记录序列进行双向冒泡排序。
算法的基本思想为，先从前往后通过交换将关键字最大的记录移动至后端，然后从后往前通过交换将关键字最小的记录移动至前端，如此反复进行，直至整个序列按关键字递增有序为止。
请在空缺处填入合适的内容，使其成为完整的算法。
#defineMAXLEN100
typedefintKeyType;
typedefstruct{
KeyTypekey;
InfoTypeotherinfo;
}NodeType;
typedefNodeTypeSqList[MAXLEN];
voidf33（SqListR,intn）
{inti,j,k;
NodeTypet;
i=0;
j=n-l;
while（ifor（
（1））k=i;kif（R[k].key>R[k+l].key）{
t=R[k];
R[k]=R[k+1];
R[k+1]=t;
}
j--;
for（k=j;k>i;k--）
if（
（2））{R[k].keyt=R[k];
R[k]=R[k-1];
R[k-1]=t;
}
（3）;i++
}
}
（1）
（2）
（3）
五、算法设计题（本大题10分）
34.假设以带头结点的单链表表示线性表，单链表的类型定义如下：
typedefintDataType;
typedefstructnode{
DataTypedata;
structnode*next;
}LinkNode,*LinkList;
编写算法，删除线性表中最大元素（假设最大值唯一存在）。
函数原型为：
voidf34（LinkListhead）
{
LinkNode*p,*max,*q;
P=head->next;
max=head->next;
while（P）
{
P=p->next;
If（p->data>max->data）max=p;
}
x=max->data;
}
}
delete_L（Lnode*L,inti）
{Lnode*p,*q;
intj;
Elemtypex;
P=L;j=0;
While（p->next!
=null&&j<=i-1）
{p=p->next;j++;}
If（!
P->next||i<1）
{Printf（"\n删除位置错误！
"）;return（-1）;}
Else{q=p->next;x=q->data;
P->next=q->next;free（q）;
Return（x）;
}
}/*delete_L*/
2009年10月全国自考数据结构真题
一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项
中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均
无分。
1.按值可否分解，数据类型通常可分为两类，它们是（）
A.静态类型和动态类型
B.原子类型和表类型
C.原子类型和结构类型
D.数组类型和指针类型
答案：
C
2.
A.A
B.B
C.C
D.D
答案：
C
3.指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程
序段是（）
A.p->next=r；q->next=r->next；r->next=q；
B.p->next=r；r->next=q；q->next=r->next；
C.r->next=q；q->next=r->next；p->next=r；
D.r->next=q；p->next=r；q->next=r->next；
答案：
A
4.若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列
个数是（）
A.3
B.5
C.6
D.7
答案：
B
5.假设以数组A［n］存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指
针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为（）
A.rear==front
B.（front+1）％n==rear
C.rear+1==front
D.（rear+1）％n==front
答案：
D
6.串的操作函数str定义为：
A.3
B.4
C.5
D.6
答案：
C
7.二维数组A［10］［6］采用行优先的存储方法，若每个元素占4个存储单元，已知元素
A［3］［4］的存储地址为1000，则元素A［4］［3］的存储地址为（）
A.1020
B.1024
C.1036
D.1240
答案：
A
8.对广义表L=（a，（））执行操作tail（L）的结果是（）
A.（）
B.（（））
C.a
D.（a）
答案：
B
9.已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（）
A.FEDCBA
B.ABCDEF
C.FDECBA
D.FBDCEA
答案：
A
10.已知森林F={T1，T2，T3，T4，T5}，各棵树Ti（i=1，2，3，4，5）中所含结点的个数分别
为7，3，5，1，2，则与F对应的二叉树的右子树中的结点个数为（）
A.2
B.3
C.8
D.11
答案：
D
11.若非连通无向图G含有21条边，则G的顶点个数至少为（）
A.7
B.8
C.21
D.22
答案：
B
12.如图所示的有向图的拓扑序列是（）
A.c，d，b，a，e
B.c，a，d，b，e
C.c，d，e，a，b
D.c，a，b，d，e
答案：
B
13.对关键字序列（6，1，4，3，7，2，8，5）进行快速排序时，以第1个元素为基准的一次划
分的结果为（）
A.（5，1，4，3，6，2，8，7）
B.（5，1，4，3，2，6，7，8）
C.（5，1，4，3，2，6，8，7）
D.（8，7，6，5，4，3，2，1）
答案：
C
14.分块查找方法将表分为多块，并要求（）
A.块内有序
B.块间有序
C.各块等长
D.链式存储
答案：
B
15.便于进行布尔查询的文件组织方式是（）
A.顺序文件
B.索引文件
C.散列文件
D.多关键字文件
答案：
二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）请
在每个空格中填上正确答案。
错填、不填均无分。
1.数据的链式存储结构的特点是借助___表示数据元素之间的逻辑关系。
答案：
指针
2.如果需要对线性表频繁进行___或___操作，则不宜采用顺序存储结构。
答案：
插入删除
3.如图所示，可以利用一个向量空间同时实现两个类型相同的栈。
其中栈1为空的条件是
top1=0，栈2为空的条件是top2=n-1，则“栈满”的判定条件是___。
答案：
top1>top2（或top2=top1-1或top1=top2+1）
4.静态存储分配的顺序串在进行插入、置换和___等操作时可能发生越界。
答案：
联接
5.广义表L=（a，（b，（）））的深度为___。
答案：
3
6.任意一棵完全二叉树中，度为1的结点数最多为___。
答案：
1
7.求最小生成树的克鲁斯卡尔（Kruskal）算法耗用的时间与图中___的数目正相关。
答案：
边
8.在5阶B树中，每个结点至多含4个关键字，除根结点之外，其他结点至少含___个关键字。
答案：
2
9.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是___的。
答案：
稳定
10.常用的索引顺序文件是___文件和___文件。
答案：
ISAMVSAM
三、解答题（本大题共4小题，每小题5分，共20分）
1.
答案：
2.由字符集{s，t，a，e，i}及其在电文中出现的频度构建的哈夫曼树如图所示。
已知某段电
文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。
答案：
eatst（说明：
每个字母1分）（5分）
3.已知无向图G的邻接表如图所示，
（1）画出该无向图；
（2）画出该图的广度优先生成森林。
（1）
（2）
答案：
（1）
（说明：
每错1个顶点或边，扣0.5分，
扣完3分为止）
（3分）
（2）
（说明：
每错1个顶点或边，扣0.5分，
扣完2分为止）
（2分）
4.对序列（48，37，63，96，22，31，50，55，11）进行升序的堆排序，写出构建的初始（大根
）堆及前两趟重建堆之后的序列状态。
初始堆：
第1趟：
第2趟：
答案：
初始堆：
（96，55，63，48，22，31，50，37，11）（2分）
第1趟：
（63，55，50，48，22，31，11，37，96）（2分）
第2趟：
（55，48，50，37，22，31，11，63，96）（1分）
四、算法阅读题（本大题共4小题，每小题5分，共20分）
1.阅读下列算法，并回答问题：
（1）无向图G如图所示，写出算法f30（&G）的返回值；
（2）简述算法f30的功能。
#defineMaxNum20
intvisited［MaxNum］；
voidDFS（Graph*g，inti）；
/*从顶点vi出发进行深度优先搜索，访问顶点vj时置visited［j］为1*/
intf30（Graph*g）
{inti，k；
for（i=0；in；i++）／*g->n为图g的顶点数目*／
visited［i］=0；
for（i=k=0；in;i++）
if（visited［i］==0）
{k++；
DFS（g，i）；
}
returnk；
}
（1）
（2）
答案：
（1）3（3分）
（2）返回无向图g中连通分量的个数。
（2分）
2.假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下：
typedefstructNode{
intid;/*学号*/
intscore；/*成绩*/
structNode*next；
}LNode，*LinkList；
阅读算法f31，并回答问题：
（2）简述算法f31的功能。
voidf31（LinkListA,LinkListB）
{LinkListp,q;
p=A->next;
q=B->next;
while（p&&q）
{if（p->idid）
p=p->next;
elseif（p->id>q->id
升级会员 