《2007年10月份全国自考数据结构真题及答案.pdf》由会员分享，可在线阅读，更多相关《2007年10月份全国自考数据结构真题及答案.pdf（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.2007年10月份全国自考数据结构真题 一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项 中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均 无分。1.A.A B.B C.C D.D 答案：D 2.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链 表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（）A.q-next=
2、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.假设以数组Am存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元 素的下一个存储位置，则队头元素所在的存储位置为（）欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！A.(rear-length+m+1)m B.(rear-length+m+
3、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
4、.广度优先搜索算法 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，5
5、8，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 欢迎您阅读并下载本文档，本文档来源于互联网
6、，如有侵权请联系删除！我们将竭诚为您提供优质的文档！二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。1.数据的逻辑结构描述数据元素之间的_，与存储方式无关。答案：逻辑关系（或关系）2.在一个长度为100的顺序表中删除第10个元素时，需移动_个元素。答案：90 3.队列的队尾位置通常是随着_操作而变化的。答案：入队 4.两个空串联接得到的串的长度为_。答案：0 5.设对称矩阵A压缩存储在一维数组B中，其中矩阵的第一个元素a11存储在B0，元素 a52存储在B11，则矩阵元素a36存储在B_中。答案：17 6.已知一棵哈夫曼树含有60个叶子结点
7、，则该树中共有_个非叶子结点。答案：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 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删
8、除！我们将竭诚为您提供优质的文档！三、解答题(本大题共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=(
9、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.欢迎您阅读并下载本文档，本文档来源于互联
10、网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！答案：(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分)欢迎您阅读并
11、下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！1.假设以带头结点的单链表表示有序表，单链表的类型定义如下：typedef struct node intdata；struct node*next；LinkNode，*LinkList；编写算法，输入n个整数构造一个元素值互不相同的递增有序链表(即相同的整数只取一个)。算 法的函数原型给定为 LinkList f 34(int n)；答案：LinkListf 34(int n)LinkList L,p,q,s;(初始化2分)int e,i;L=(LinkList)malloc(sizeof(LinkNode);L-next=NULL;for(i=1;inext;while(q&q-datanext;if(!q|q-datae)(插入2分)s=(LinkList)malloc(sizeof(LinkNode);s-data=e;s-next=q;p-next=s;return L;(返回1分)（说明：算法描述如有差异，可参照相应评分标准）