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

一、单项选择题（本大题共15小题,每小题2分,共30分）
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.错选、多选或未选均无分.
1.下面程序段的时间复杂度为( )
s=0；
for(i=1；ifor(j=1；js+=i*j；
A.O(1)
B.O(logn)
C.O(n)
D.O(n2)

2.已知指针p和q分别指向某单链表中第一个结点和最后一个结点.假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为( )
A.q->next=s->next；s->next=p；
B.s->next=p；q->next=s->next；
C.p->next=s->next；s->next=q；
D.s->next=q；p->next=s->next；

3.在计算机内实现递归算法时所需的辅助数据结构是( )
A.栈
B.队列
C.树
D.图

4.假设以数组A[m]存放循环队列的元素.已知队列的长度为length,指针rear指向队尾元素的下一个存储位置,则队头元素所在的存储位置为( )
A.(rear-length+m+1)%m
B.(rear-length+m)%m
C.(rear-length+m-1)%m
D.(rear-length)%m

5.通常将链串的结点大小设置为大于1是为了( )
A.提高串匹配效率
B.提高存储密度
C.便于插入操作
D.便于删除操作

6.带行表的三元组表是稀疏矩阵的一种( )
A.顺序存储结构
B.链式存储结构
C.索引存储结构
D.散列存储结构

7.表头和表尾均为空表的广义表是( )
A.()
B.(())
C.((()))
D.((),())

8.用二叉链表表示具有n个结点的二叉树时,值为空的指针域的个数为( )
A.n-1
B.n
C.n+l
D.2n

9.为便于判别有向图中是否存在回路,可借助于( )
A.广度优先搜索算法
B.最小生成树算法
C.最短路径算法
D.拓扑排序算法

10.连通网的最小生成树是其所有生成树中( )
A.顶点集最小的生成树
B.边集最小的生成树
C.顶点权值之和最小的生成树
D.边的权值之和最小的生成树

11.按排序过程中依据的原则分类,快速排序属于( )
A.插入类的排序方法
B.选择类的排序方法
C.交换类的排序方法
D.归并类的排序方法

12.下列关键字序列中,构成小根堆的是( )
A.{84,46,62,41,28,58,15,37}
B.{84,62,58,46,41,37,28,15}
C.{15,28,46,37,84,41,58,62}
D.{15,28,46,37,84,58,62,41}

13.在长度为32的有序表中进行二分查找时,所需进行的关键字比较次数最多为( )
A.4
B.5
C.6
D.7

14.假设在构建散列表时,采用线性探测解决冲突.若连续插入的n个关键字都是同义
词,则查找其中最后插入的关键字时,所需进行的比较次数为( )
A.n-1
B.n
C.n+l
D.n+2

15.散列文件也称为( )
A.顺序文件
B.索引文件
C.直接存取文件
D.间接存取文件

二、填空题(本大题共10小题,每小题2分,共20分)
请在每小题的空格中填上正确答案.错填、不填均无分.
16.数据的逻辑结构描述数据元素之间的_________________,与存储方式无关.
17.在一个长度为100的顺序表中删除第10个元素时,需移动___________________个元素.
18.队列的队尾位置通常是随着______________操作而变化的.
19.两个空串联接得到的串的长度为___________________.
20.设对称矩阵A压缩存储在一维数组B中,其中矩阵的第一个元素a11存储在B[0],元素a52存储在B[11],则矩阵元素a36存储在B[______________]中.
21.已知一棵哈夫曼树含有60个叶子结点,则该树中共有________________个非叶子结点.
22.如图所示的有向图中含有_______________个强连通分量.

23.已知一组关键字为{15,36,28,97,24,78,47,52,13,86},其中每相邻两个关键字构成一个有序子序列.对这些子序列进行一趟两两归并的结果是______________.
24.从空树起,依次插入关键字1l,27,35,48,52,66和73构造所得的二叉排序树,在等概率查找的假设下,查找成功时的平均查找长度为____________________.
25.控制区间和控制区域是________________文件的逻辑存储单位.

三、解答题(本大题共4小题,每小题5分,共20分)
26.利用广义表的head和tail操作,可从广义表L=((a,b),(c,d))中分解得到原子c,其操作表达式为head(head(tail(L)))；
分别写出从下列广义表中分解得到b的操作表达式.
(1)L1=(a.,b,c,d)；
(2)L2=(((a),(b),(c),(d))).
(1)__________________________________________
(2)__________________________________________
27.画出与如图所示森林对应的二叉树. 
 
28.已知有向图G的定义如下:
G=(V,E)
V={a,b,c,d,e}
E={, ,,,,,}
(1)画出G的图形；
(2)写出G的全部拓扑序列.
(1)__________________________________________
(2)__________________________________________
29.已知3阶B-树如图所示.
(1)画出将关键字88插入之后的B-树；
(2)画出将关键字47和66依次插入之后的B-树.

(1)__________________________________________
(2)__________________________________________

四、算法阅读题(本大题共4小题,每小题5分,共20分)
30.假设某个不设头指针的无头结点单向循环链表的长度大于1,s为指向链表中某个结点的指针.算法f 30的功能是,删除并返回链表中指针s所指结点的前驱.请在空缺处填入合适的内容,使其成为完整的算法.
typedef struct node {
DataType data；
struct node *next；
}*LinkList；
DataType f 30(LinkList s) {
LinkList pre,p；
DataType e；
pre=s； ’
p=s->next；
while( (1) ){
pre=p;
____________(2) ;
}
pre ->next= (3) ;
e=p->data;
free(p);
return e;
}
(1)__________________________________________
(2)__________________________________________
(3)__________________________________________
31.算法f31的功能是清空带头结点的链队列Q.请在空缺处填入合适的内容,使其成为一个完整的算法.
typedef struct node{
DataType data；
struct node *next；
}QueueNode；
typedef struct {
QueueNode *front；／／队头指针
QueueNode *rear；／／队尾指针
}LinkQueue；
void f 31(LinkQueue*Q) {
QueueNode*p,*s；
p= (1) ；
while(p！=NULL) {
s=p；
p=p->next;
free (s);
________(2) =NULL;
Q->rear=_______(3)_______；
}
(1)__________________________________________
(2)__________________________________________
(3)__________________________________________
32.假设采用动态存储分配的顺序串HString作为串的存储结构.该类型实现的串操作函数原型说明如下:
void strinit(HString s)；／／置s为空串
int strlen(HString s)；／／求串s的长度
void strcpy(HString to,HString from)；／／将串from复制到串to
void strcat(HString to,HString from)；／／将串from联接到串to的末尾
int strcmp(HString sl,HString s2)；
／／比较串sl和s2的大小,当s1s2时,
／／返回值小于0,等于0或大于0
HString substr(HString s,int i,int m)；
／／返回串s中从第i(0≤I≤strlen(s)-m)个字符起长度为m的子串
阅读下列算法f 32,并回答问题:
(1)设串S=″abcdabcd″,T=″bcd″,V=″bcda″,写出执行f 32(S,T,V)之后的S；
(2)简述算法f 32的功能.
void f 32 (HString S, HString T, HString V) {
int m, n, pos, i;
HString news;
strinit (news) ;
n=strlen(S);
m=strlen(T);
pos=i=0;
while (i<=n-m) {
if( stremp(substr(S,i,m),T)! =0)i++;
else{
strcat(news,substr(S, pos, i-pos)) ;
strcat(news, V) ;
pos=i=i+m;
}
}
strcat(news,substr(S,pos,n-pos)) ;
strcpy(S,news)
}
(1)
(2)
33.假设以二叉链表作为二叉树的存储结构,其类型定义如下:
typedef struct node {
char data;
struct node *lchild, *rchild; ／／左右孩子指针
} BinTNode,*BinTree；
阅读下列算法f 33,并回答问题:
(1)已知如图所示的二叉树以T为指向根结点的指针,画出执行f 33(T)后的二叉树；
(2)简述算法f 33的功能.
void f33(BinTree T) {
if (T) {
f 33 (T - > lchild) ;
f 33(T - > rchild) ;
if ( ( !T - > lchild) && T->rchild) {
T - > lchild=T->rchild;
T - > rchild=NULL;
}
}
}

(1)__________________________________________
(2)__________________________________________

五、算法设计题(本大题10分)
34.假设以带头结点的单链表表示有序表,单链表的类型定义如下:
typedef struct node {
int data；
struct node*next；
} LinkNode,*LinkList；
编写算法,输入n个整数构造一个元素值互不相同的递增有序链表(即相同的整数只取一个).算法的函数原型给定为
LinkList f 34(int n)；