份全国自考数据结构真题及答案.docx
《份全国自考数据结构真题及答案.docx》由会员分享，可在线阅读，更多相关《份全国自考数据结构真题及答案.docx（16页珍藏版）》请在冰点文库上搜索。
份全国自考数据结构真题及答案
更多优质自考资料尽在XX贴吧自考乐园俱乐部
（
2007年10月份全国自考数据结构真题
一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项
中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均
无分。
1.
A.A
B.B
C.C
D.D
答案：
D
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；
答案：
A
3.在计算机内实现递归算法时所需的辅助数据结构是（）
A.栈
B.队列
C.树
D.图
答案：
A
4.假设以数组A［m］存放循环队列的元素。
已知队列的长度为length，指针rear指向队尾元
素的下一个存储位置，则队头元素所在的存储位置为（）
A.（rear-length+m+1）％m
B.（rear-length+m+1）％m
C.（rear-length+m-1）％m
D.（rear-length）％m
答案：
B
5.通常将链串的结点大小设置为大于1是为了（）
A.提高串匹配效率
B.提高存储密度
C.便于插入操作
D.便于删除操作
答案：
B
6.带行表的三元组表是稀疏矩阵的一种（）
A.顺序存储结构
B.链式存储结构
C.索引存储结构
D.散列存储结构
答案：
A
7.表头和表尾均为空表的广义表是（）
A.（）
B.（（））
C.（（（）））
D.（（），（））
答案：
B
8.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为（）
A.n-1
B.n
C.n+l
D.2n
答案：
C
9.为便于判别有向图中是否存在回路，可借助于（）
A.广度优先搜索算法
B.最小生成树算法
C.最短路径算法
D.拓扑排序算法
答案：
D
10.连通网的最小生成树是其所有生成树中（）
A.顶点集最小的生成树
B.边集最小的生成树
C.顶点权值之和最小的生成树
D.边的权值之和最小的生成树
答案：
D
11.按排序过程中依据的原则分类，快速排序属于（）
A.插入类的排序方法
B.选择类的排序方法
C.交换类的排序方法
D.归并类的排序方法
答案：
C
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}
答案：
D
13.在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为（）
A.4
B.5
C.6
D.7
答案：
C
14.假设在构建散列表时，采用线性探测解决冲突。
若连续插入的n个关键字都是同义词，则
查找其中最后插入的关键字时，所需进行的比较次数为（）
A.n-1
B.n
C.n+1
D.n+2
答案：
B
15.散列文件也称为（）
A.顺序文件
B.索引文件
C.直接存取文件
D.间接存取文件
答案：
C
二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案
。
错填、不填均无分。
1.数据的逻辑结构描述数据元素之间的___，与存储方式无关。
答案：
逻辑关系（或关系）
2.在一个长度为100的顺序表中删除第10个元素时，需移动___个元素。
答案：
90
3.队列的队尾位置通常是随着___操作而变化的。
答案：
入队
4.两个空串联接得到的串的长度为___。
答案：
0
5.设对称矩阵A压缩存储在一维数组B中，其中矩阵的第一个元素a11存储在B［0］，元素
a52存储在B［11］，则矩阵元素a36存储在B［___］中。
答案：
17
6.已知一棵哈夫曼树含有60个叶子结点，则该树中共有___个非叶子结点。
答案：
59
7.如图所示的有向图中含有___个强连通分量。
答案：
2
8.已知一组关键字为{15，36，28，97，24，78，47，52，13，86}，其中每相邻两个关键字
构成一个有序子序列。
对这些子序列进行一趟两两归并的结果是___。
答案：
{15,28,36,97,24,47,52,78,13,86}
9.从空树起，依次插入关键字11，27，35，48，52，66和73构造所得的二叉排序树，在等概
率查找的假设下，查找成功时的平均查找长度为___。
答案：
4
10.控制区间和控制区域是___文件的逻辑存储单位。
答案：
VSAM
三、解答题（本大题共4小题，每小题5分，共20分）
1.利用广义表的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）
答案：
（1）head（tail（L1））（2分）
（说明:
每错一个操作扣1分,扣完2分为止）
（2）head（head（tail（head（L2））））（3分）
（说明:
每错一个操作扣1分,扣完3分为止）
2.
答案：
3.已知有向图G的定义如下：
G=（V，E）
V={a，b，c，d，e}
E={，，，，，，}
（1）画出G的图形；
（2）写出G的全部拓扑序列。
（1）
（2）
答案：
4.
答案：
四、算法阅读题（本大题共4小题，每小题5分，共20分）
1.
答案：
（1）p->next!
=s（2分）
（2）p=p->next（2分）
（3）s（或p->next）（1分）
2.
答案：
（1）Q->front->next（2分）
（2）Q->front->next（2分）
（3）Q->front（1分）
3.
答案：
（1）S=″abcdaabcda″（3分）
（2）串的置换操作，用串V置换串S中的子串T。
（2分）
4.
答案：
五、算法设计题（本大题10分）
1.假设以带头结点的单链表表示有序表，单链表的类型定义如下：
typedefstructnode{
intdata；
structnode*next；
}LinkNode，*LinkList；
编写算法，输入n个整数构造一个元素值互不相同的递增有序链表（即相同的整数只取一个）。
算
法的函数原型给定为
LinkListf34（intn）；
答案：
LinkListf34（intn）
{LinkListL,p,q,s;（初始化2分）
inte,i;
L=（LinkList）malloc（sizeof（LinkNode））;
L->next=NULL;
for（i=1;i<=n;i++）{（循环架构1分）
scanf（″%d″,&e）;（输入及查找准备2分）
p=L;
q=p->next;
while（q&&q->datap=q;
更多优质自考资料尽在XX贴吧自考乐园俱乐部
（
q=q->next;
}
if（!
q||q->data>e）{（插入2分）
s=（LinkList）malloc（sizeof（LinkNode））;
s->data=e;
s->next=q;
p->next=s;
}
}
returnL;（返回1分）
}
（说明：
算法描述如有差异，可参照相应评分标准）
升级会员 