2007年下半年全国自考（数据结构）真题试卷
一、1.单项选择题
0. 下面程序段的时间复杂度为 ( ) s=0; for(i=1;i＜n;i++) for(j=1;j＜i;j++) s+=i*j;
A．O(1)
B．O(log2n)
C．O(n)
D．O(n3)
1. 已知指针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;
2. 在计算机内实现递归算法时所需的辅助数据结构是 ( )
A．栈
B．队列
C．树
D．图
3. 假设以数组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
4. 通常将链串的结点大小设置为大于1是为了 ( )
A．提高串匹配效率
B．提高存储密度
C．便于插入操作
D．便于删除操作
5. 带行表的三元组表是稀疏矩阵的一种 ( )
A．顺序存储结构
B．链式存储结构
C．索引存储结构
D．散列存储结构
6. 表头和表尾均为空表的广义表是 ( )
A．()
B．(())
C．((()))
D．(()，())
7. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为 ( )
A．n-1
B．n
C．n+1
D．2n
8. 为便于判别有向图中是否存在回路，可借助于 ( )
A．广度优先搜索算
B．最小生成树算法
C．最短路径算
D．拓扑排序算法
9. 连通网的最小生成树是其所有生成树中 ( )
A．顶点集最小的生成树
B．边集最小的生成树
C．顶点权值之和最小的生成树
D．边的权值之和最小的生成树
10. 按排序过程中依据的原则分类，快速排序属于 ( )
A．插入类的排序方法
B．选择类的排序方法
C．交换类的排序方法
D．归并类的排序方法
11. 下列关键字序列中，构成小根堆的是 ( )
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}
12. 在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为( )
A．4
B．5
C．6
D．7
13. 假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为 ( )
A．n-1
B．n
C．n+i
D．n+2
14. 散列文件也称为 ( )
A．顺序文件
B．索引文件
C．直接存取文件
D．间接存取文件
二、2.填空题
0. 数据的逻辑结构描述数据元素之间的______，与存储方式无关。
1. 在一个长度为100的顺序表中删除第10个元素时，需移动______个元素。
2. 队列的队尾位置通常是随着______操作而变化的。
3. 两个空串联接得到的串的长度为______。
4. 设对称矩阵A压缩存储在一维数组B中，其中矩阵的第一个元素a11存储在B[0]，元素a52存储在B[11]，则矩阵元素a36存储在[B______]中。
5. 已知一棵哈夫曼树含有60个叶子结点，则该树中共有______个非叶子结点。
6. 如图所示的有向图中含有______个强连通分量。
7. 已知一组关键字为{15,36,28,97,24,78,47,52,13,86}，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是______。
8. 从空树起，依次插入关键字11,27,35,48,52,66和73构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为______。
9. 控制区间和控制区域是______文件的逻辑存储单位。
三、3.解答题
0. 利用广义表的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. 已知有向图G的定义如下：
G=(V,E)
V={a,b,c,d,e}
E={＜a,b＞，＜a,c＞，＜b,c＞，＜b,d＞，＜c,d＞，＜e,c＞，＜e,d＞)
(1)画出G的图形；
(2)写出G的全部拓扑序列。
3. 已知3阶B-树如图所示。
(1)画出将关键字88插入之后的B-树；
(2)画出将关键字47和66依次插入之后的B一树。
四、4.算法阅读题
0. 假设某个不设头指针的无头结点单向循环链表的长度大于1，S为指向链表中某个结点的指针。算法f30的功能是，删除并返回链表中指针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. 算法f31的功能是清空带头结点的链队列Q。请在空缺处填入合适的内容，使其成为一个完整的算法。
typedef struct node{
DataType data;
struct node *next;
}QueueNode;
typedef struet{
QueueNode*front; //队头指针
QueueNode*rear; //队尾指针
}LinkQueue;
void f31(LinkQueue*Q){
QueueNode*p,*s;
p= (1) ;
while(P!=NULL){
s=p;
p=p—＞next;
free(s);
}
(2) =NULL;
Q—＞rear= (3) ;
}
2. 假设采用动态存储分配的顺序串HString作为串的存储结构。该类型实现的串操作函数原型说明如下：
void strinit(HString s); //置s为空串
int strlen(HString s); //求串s的长度
void strcpy(HString to,HString from); //将串from复制到串to
void streat(HString to,HString from); //将串from联接到串to的末尾
int strcmp(HString s1,HString s2);
//比较串s1和s2的大小，当s1＜s2，s1=s2或s1＞s2时，
//返回值小于0，等于0或大于0
HString substr(HString s,int i,int m);
//返回串S中从第i(0≤i≤strlen(s)-m)个字符起长度为m的子串阅读下列算法f32，并回答问题：
(1)设串S="abcdabcd"，T="bcd"，V="bcda"，写出执行f32(S,T,V)之后的S；
(2)简述算法f32的功能。
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(strcmp(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);
}
3. 假设以二叉链表作为二叉树的存储结构，其类型定义如下：
typedef struct node{
char data;
struct node*lchild,*rchild; //左右孩子指针
}BinTNode,*BinTree;
阅读下列算法f33，并回答问题：
(1)已知如图所示的二叉树以T为指向根结点的指针，画出执行f33(T)后的二叉树；
(2)简述算法f 33的功能。
void f 33(BinTtee T){
if(T){
f 33(T—＞lchild);
f 33(T—＞rchild);
if((!T—＞lchild)&&L T—＞rchild){
T—＞lchild=T—＞rchild;
T—＞rchild=NULL;
}
}
}
五、5.算法设计题
0. 假设以带头结点的单链表表示有序表，单链表的类型定义如下：
typedef struct node{
int data;
struct node*next;
}LinkNode,*LinkList;
编写算法，输入n个整数构造一个元素值互不相同的递增有序链表(即相同的整数只取一
个)。算法的函数原型给定为
LinkList f 34(int n);
