自考数据结构2007-10-2.doc

全天24小时服务咨询电话 [phone]　免费热线 4008135555

□ 自考名师全程视频授课，图像、声音、文字同步传输，享受身临其境的教学效果；
□ 权威专家在线答疑，提交到答疑板的问题在24小时内即可得到满意答复；
□ 课件自报名之日起可反复观看不限时间、地点、次数，直到当期考试结束后一周关闭；
□ 付费学员赠送1G超大容量电子信箱；及时、全面、权威的自考资讯全天24小时滚动更新；
□ 一次性付费满300元，即可享受九折优惠；累计实际交费金额500元或支付80元会员费，可
成为银卡会员，购课享受八折优惠；累计实际交费金额1000元或支付200元会员费，可成为金
卡会员，购课享受七折优惠（以上须在同一学员代码下）；
英语/高等数学预备班：英语从英文字母发音、国际音标、基本语法、常用词汇、阅读、写作等角度开展教学；数学针对有仅有高中入
学水平的数学基础的同学开设。通过知识点精讲、经典例题详解、在线模拟测验，有针对性而快速的提高考生数学水平。立即报名！
基础学习班：依据全新考试教材和大纲，由辅导老师对教材及考试中所涉及的知识进行全面、系统讲解，使考生从整体上把握该学科的
体系，准确把握考试的重点、难点、考点所在，为顺利通过考试做好知识上、技巧上的准备。立即报名！
冲刺串讲班：结合历年试题特点及命题趋势，规划考试重点内容，讲解答题思路，传授胜战技巧，为考生指出题眼，提供押题参考。配
合高质量全真模拟试题，让学员体验实战，准确地把握考试方向、将已掌握的应试知识融会贯通，并做到举一反三。立即报名！
习题班：自考365网校与北大燕园合作推出，共计390门课程，均涵盖该课程全部考点、难点，在线测试系统按照考试难度要求自动组
卷、全程在线测试、提交后自动判定成绩。我们相信经过反复练习定能使您迅速提升应试能力，使您考试梦想成真！立即报名！
论文答辩与毕业申请指导班：来自主考院校的指导老师全程视频授课，系统阐述申报自考论文的时间、论文的选题、论文的格式及内容、
与导师的沟通技巧等，并提供论文范例供学员参考。立即报名！
自考实验班：针对高难科目开设，签协议，不及格返还学费。全国限量招生，报名咨询 010-82335555 立即报名！
全国2007年10月高等教育自学考试
数据结构试题
课程代码：02331
一、单项选择题（本大题共15小题，每小题2分，共30分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.下面程序段的时间复杂度为( )
s=0；
for(i=1；i<n；i++)
for(j=1；j<i；j++)
s+=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={<a，b>， <a，c>，<b，c>，<b，d>，<c，d>，<e，c>，<e，d>}
(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的大小，当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的子串
阅读下列算法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)；

════════════════════════════════════════════════════════════════════
自考365（--）领先的专注于自学考试的网络媒体与服务平台 - 本套试题共分6页，当前页是第6页-