全国2009年10月高等教育自学考试数据结构试题
课程代码:02331

一、单项选择题（本大题共15小题,每小题2分,共30分）
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.错选、多选或未选均无分.
1.按值可否分解,数据类型通常可分为两类,它们是（　　　）
A.静态类型和动态类型
B.原子类型和表类型
C.原子类型和结构类型
D.数组类型和指针类型

2.对于三个函数f(n)=2008n³+8n²+96000,g(n)=8n³+8n+2008和h(n)=8888nlogn+3n²,下列陈述中不成立的是（　　　）
A.f(n)是0(g(n))
B.g(n)是0(f(n))
C.h(n)是0(nlogn)
D.h(n)是0(n²)

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；

4.若进栈次序为a,b,c,且进栈和出栈可以穿插进行,则可能出现的含3个元素的出栈序列个数是（　　　）
A.3
B.5
C.6
D.7

5.假设以数组A［n］存放循环队列的元素,其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置,则在少用一个元素空间的前提下,队列满的判定条件为（　　　）
A.rear= =front
B.(front+1)％n= =rear
C.rear+1= =front
D.(rear+1)％n= =front
6.串的操作函数str定义为:
int str(char*s) {
char *p=s；
while (*p!=′′)p++；
return p-s；
}
则str(″abcde″)的返回值是（　　　）
A.3
B.4
C.5
D.6

7.二维数组A［10］［6］采用行优先的存储方法,若每个元素占4个存储单元,已知元素A［3］［4］的存储地址为1000,则元素A［4］［3］的存储地址为（　　　）
A.1020
B.1024
C.1036
D.1240

8.对广义表L= (a,())执行操作tail(L)的结果是（　　　）
A.()
B.(())
C.a
D.(a)

9.已知二叉树的中序序列和后序序列均为ABCDEF,则该二叉树的先序序列为（　　　）
A.FEDCBA
B.ABCDEF
C.FDECBA
D.FBDCEA

10.已知森林F={T₁,T₂,T₃,T₄,T₅},各棵树Ti(i=1,2,3,4,5)中所含结点的个数分别为7,3,5,l,2,则与F对应的二叉树的右子树中的结点个数为（　　　）
A.2
B.3
C.8
D.11

11.若非连通无向图G含有21条边,则G的顶点个数至少为（　　　）

A.7
B.8
C.21
D.22

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

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)

14.分块查找方法将表分为多块,并要求（　　　）
A.块内有序
B.块间有序
C.各块等长
D.链式存储

15.便于进行布尔查询的文件组织方式是（　　　）
A.顺序文件
B.索引文件
C.散列文件
D.多关键字文件 

 

 

二、填空题（本大题共10小题,每小题2分,若有两个空格,每个空格1分,共20分）
请在每个空格中填上正确答案.错填、不填均无分.
16.数据的链式存储结构的特点是借助________表示数据元素之间的逻辑关系.
17.如果需要对线性表频繁进行________或________操作,则不宜采用顺序存储结构.
18.如图所示,可以利用一个向量空间同时实现两个类型相同的栈.其中栈1为空的条件是top1=0,栈2为空的条件是top2=n-1,则"栈满"的判定条件是________.

19.静态存储分配的顺序串在进行插入、置换和________等操作时可能发生越界.
20.广义表L=（a,（b,( )））的深度为________.
21.任意一棵完全二叉树中,度为1的结点数最多为________.
22.求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中________的数目正相关.
23.在5阶B-树中,每个结点至多含4个关键字,除根结点之外,其他结点至少含________个关键字.
24.若序列中关键字相同的记录在排序前后的相对次序不变,则称该排序算法是________的.
25.常用的索引顺序文件是________文件和________文件.

 

三、解答题(本大题共4小题,每小题5分,共20分)
26.如图所示,在n×n矩阵A中,所有下标值满足关系式i+j＜n+l的元素a_ij的值均为0,现将A中其它元素按行优先顺序依次存储到长度为n(n+1)/2的一维数组sa中,其中元素a_1,n存储在sa［0］.
(1)设n=10,元素a_4,9存储在sa［p］,写出下标p的值；
(2)设元素a_i,j存储在sa［k］中,写出由i,j和n计算k的一般公式.

27.由字符集{s,t,a,e,I}及其在电文中出现的频度构建的哈夫曼树如图所示.已知某段电文的哈夫曼编码为111000010100,请根据该哈夫曼树进行译码,写出原来的电文.

28.已知无向图G的邻接表如图所示,
(1)画出该无向图；
(2)画出该图的广度优先生成森林.

29.对序列(48,37,63,96,22,31,50,55,11)进行升序的堆排序,写出构建的初始(大根)堆及前两趟重建堆之后的序列状态.
初始堆:
第1趟:
第2趟:

四、算法阅读题(本大题共4小题,每小题5分,共20分)
30.阅读下列算法,并回答问题:

(1)无向图G如图所示,写出算法
f30(&G)的返回值；
(2)简述算法f30的功能.
#define MaxNum 20
int visited[MaxNum]；
void DFS(Graph *g,int i)；
　　/*从顶点vi出发进行深度优先搜索,访问顶点vj时置visited[j]为1*/
int f30(Graph *g)
　　{ int i,k；
　　　for (i=0； i<g->n； i++)／*g->n为图g的顶点数目*／
　　　　　visited[i]=0；
　　　for (i=k=0； i<g->n; i++)
　　　　　if (visited[i]= =0)
　　　　　　　{ k++；
　　　　　　　　DFS(g,i)；
　　　　　　　}
　　　return k；
　　}
31.假设学生成绩按学号增序存储在带头结点的单链表中,类型定义如下:
typedef struct Node {
　　int id; /*学号*/
　　int score； /*成绩*/
　　struct Node *next；
　　} LNode, *LinkList；
阅读算法f31,并回答问题:
(1)设结点结构为