数据结构自考题-8.doc

《数据结构自考题-8.doc》由会员分享，可在线阅读，更多相关《数据结构自考题-8.doc（9页珍藏版）》请在三一文库上搜索。

1、数据结构自考题-8（总分：100.00，做题时间：90分钟）一、单项选择题（总题数：15,分数：30.00）1. 在下面的程序中，语句S的执行次数为（）for（i=1;i< =n_1;i+）for（j=n;j> =i;j-）S;（分数：2.00 ）A.B. VC.D.解析：2. 数据结构是（）A. 种数据类型B. 数据的存储结构C. 一组性质相同的数据元素的集合D. 相互之间存在一种或多种特定关系的数据元素的集合（分数：2.00 ）A.B.C.D. V解析：3. 已知一个向量的第一个元素的存储地址是100，每个元素的长度为 2,则第6个元素的地址是（）A. 120 B . 112

2、C . 110 D . 114（分数：2.00 ）A.B.C. VD.解析：4. 线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相 同的特性，这意味着（）A. 每个结点所代表的数据元素都一样B. 每个结点所代表的数据元素包含的数据项的个数要相等C. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致D. 结点所代表的数据元素有同一特点（分数： 2.00 ）A.B.C. VD.解析：5. 若在文件中查询年龄在 60 岁以上的男性及年龄在 55 岁以上的女性的所有记录，则查询条件为 （ ）A. （性别="男"）0R（年龄

3、60）OR（性别="女"）0R（年龄55）B. （性别="男"）OR（年龄60）AND（性别="女"）OR（年龄55）C. （性别="男"）AND（年龄60）OR（性别="女"）AND（年龄55）D. （性别="男"）AND（年龄60）AND（性别="女'）AND（年龄55）（分数： 2.00 ）A.B.C. VD.解析：6. 已知二叉树的中序序列和后序序列均为ABCDE，F 则该二叉树的先序序列为（ ）A. FEDCBA B. ABCDEFC. FDECB

4、A D. FBDCEA（分数： 2.00 ）A. VB.C.D.解析： 解析 对于前序遍历、中序遍历和后序遍历，将结点按其访问的先后次序排列起来，所得到的结点 序列分别称为前序序列、中序序列和后序序列。7. 下面的查找方式中，可以对无序表进行查找的是 （ ）A. 顺序查找B .二分查找C .二叉排序树D . B-树上的查找（分数： 2.00 ）A. VB.C.D.解析：8. 在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p, q之间插入s结点，则执行（）操作。A. s> next=p > next;p > next=s; B . q > next=s;s &

5、gt; next=p;C. p> next=s > next;s > next=p; D . p> next=s;s > next=q;（分数： 2.00 ）A.B. VC.D.解析：9. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 （ ）A.不一定相同B 都相同C 都不相同D 互为逆序（分数： 2.00 ）A.B. VC.D.解析：10. 如果我们采用二分查找法查找一个长度为 n 的有序表，则查找每个元素的平均比较次数 （ ） 对应的判定 树的高度（假设树高h>2）。A.大于B .小于C 等于D .无法确定（分数： 2.00 ）A.B

6、. VC.D.解析：11. 按值可否分解，数据类型通常可分为两类，它们是 （ ）A.静态类型和动态类型B 原子类型和表类型C.原子类型和结构类型D .数组类型和指针类型（分数： 2.00 ）A.B.C. VD.解析： 解析 按“值”是否可分解，可将数据类型划分为两类：原子类型，其值不可分解；结构类型，其 值可分解为若干个成分。12. 带行表的三元组表是稀疏矩阵的一种 （ ）A.顺序存储结构B .链式存储结构C. 索引存储结构D 散列存储结构分数： 2.00 )A. VB.C.D.解析：13. 若用邻接矩阵表示一个有向图，则其中每一列包含的"1"的个数为（）A.图中每个顶点的

7、入度 B .图中每个顶点的出度C.图中弧的条数 D 图中连通分量的数目（分数：2.00 ）A. VB.C.D.解析：14. 如图所示的带权无向图的最小生成树的权为（）A. 51 B. 52C. 54 D . 56（分数：2.00 ）A.B.C. VD.解析：解析根据最小生成树的构造过程，可知在构造本题中无向图的最少生成树时，将选取权值分别为 10、14、12、18的边，所以此最小生成树的权即各边权值之和即54。15. 若进栈次序为a,b,e，且进栈和岀栈可以穿插进行，则可能岀现的含3个元素的岀栈序列个数是A. 3 B . 5C. 6 D. 7（分数：2.00 ）A.B. VC.D.解析：二、填

8、空题（总题数：10,分数：20.00）16. 设线性表（日1,日2，a500）元素的值由小到大排列。对一个给定的k值，用二分法检索查找表中与等的元素，在检索不成功的情况下，至多需比较1次。（分数：2.00 ）填空项1: （正确答案：9）解析：17. 删除双向循环链表中*p的前驱结点（存在）应执行的语句是 （分数:2.00 ）填空项 1: （正确答案: p> prior=p > prior > prior;p> prior > next=p;（或 p> prior > prior > next=p;p> prior=p > prior

9、> prior;）解析：18. 就文件而言，按用户的观点所确定的基本存储单元称为 。按外设的观点所确定的基本存储单元称为。（分数：2.00）填空项1: （正确答案：逻辑记录物理记录）解析：19. 广义表的深度是指1。（分数：2.00）填空项1： （正确答案：广义表展开后所含括号的最大层数）解析：20.ISAM文件采用 索引结构，而VSAM文件采用索引结构。（分数：2.00）填空项1： （正确答案：静态 动态）解析：21. 如图所示的有向图中含有 个强连通分量。（分数：2.00）填空项1： （正确答案：2）解析：22. 对快速排序来讲，其最好情况下的时间复杂度是 ，其最坏情况下的时间复杂度

10、是 （分数：2.00）填空项1： （正确答案：O（nlog2n） O（n 2）解析：23. 在按照顺序存储方式存储的数组中，元素aj的存储地址应该是数组的 1加上排在aj前面的元素所占用的单元数。（分数：2.00）填空项1: （正确答案：基地址）解析：24. 对无向图，其邻接矩阵是一个关于1对称的矩阵。（分数:2.00 ）填空项1： （正确答案：主对角线）解析：25. 在分块查找法中，首先查找 1，然后再查找相应的2。（分数:2.00）填空项1： （正确答案：索引表块）解析：三、解答题（总题数：4,分数：20.00）26. 请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图（顶点Vi表示）

11、（分数：5.00） 正确答案：（答：A，B，C对应的图分别为:解析：27. 在一棵二叉树中，度为O的结点个数与度为2的结点个数和度数之间有什么关系 ？在一棵完全二叉树中，如果共有200个结点，则能判断出叶结点的个数吗 ？如果能，请指出会有多少个叶结点，多少个度为2的结点？多少个度为1的结点？如果有201个结点呢？（分数：5.00）正确答案：（在一棵二叉树中，度数为 0的结点（叶结点）的个数总是比度为2的结点的个数多1。根据完全 二叉树的定义：若一棵二叉树至多只有最下面的两层上结点的度数可以小于2,并且最下一层上的结点都集中在该层最左边的若干住置上，则我们可以得岀这样一个结论：在一棵完全二叉树上

12、，或者没有度为1的结点。则根据以上分析，我们可以这样计算此题：设度数为2的结点有n个，则必有n+1个度为0的结点，即度数为2和度数为0的结点数之和为2n+1（是奇数），于是得出，如果一棵完全二叉树的结点总数为 奇数，则此树中必然不存在度为1的结点，若完全二叉树中结点总数为偶数，则必然有1个度为1的结点存在，于是若完全二叉树中有 200个结点，就必有100个对结点，99个度数为2的结点，12个度数为1的 结点，如果二叉树中有201个结点，则必有101个叶结点，100个度数为2的结点，没有度数为1的结点。） 解析：28. 已知有一关键字序列为 486,79,596,34,900,120,789,1

13、79,703,307），如果我们采用基数排序方法对此序列进行排序（按照升序排列），请给岀每一趟的排序结果。（分数：5.00 ）第 2 趟：（按十位进行排序）:307,703,900,120,34,79,179,486,789,596 第 3 趟：（按百位进行排序）：34,79,120,179,307,486,596,703,789,900） 解析：29. 已知连通图如下：分别以邻接矩阵的邻接表实现存储，试给岀该图的邻接矩阵和邻接表，若从顶点 分别给岀一个按深度优先搜索和广度优先搜索的顶点序列。B岀发对该图进行遍历,（分数：5.00 ）深度优先搜索顶点序列为:b a d f e c广度优先搜索顶

14、点序列为：b a c e d f）解析：四、算法阅读题（总题数：3,分数：20.00）（假设此栈中元素的类型是char）30. 写岀下列程序段的输岀结果。 voide main() stack s;char x,y;InitStack(s) x= '1' ,y= '0' push(s,x); push(s,x); push(s,y);push(s,x)； push(s, 'e'); push(s,x); pop(s,x); push(s, 'h'); while(!stackEmpty(s) pop(s,y);printf(y);

15、prinft(x)（分数：5.00 ） 正确答案：（此题的输出结果是hello o ） 解析：阅读下列算法，并回答问题: 无向图G如图所示，写出算法f30(&G)的返回值；简述算法f30的功能。#define MaxNum 20int visitedMaxNum;void DFS(Graph*g,int i);/*从顶点vi出发进行深度优先搜索，访问顶点vj时置visitedj 为1*/int f30(Graph*g)int i,k;for(i=0;iv g> N;l+)visitedi=0;if(visitedi=0)k+;DFS(g,i);return k;（分数：10.00

16、） 正确答案：（3）解析： 正确答案：(返回无向图g中连通分量的个数。) 解析：31. 简述一下算法的功能：status A (1inkedlist L)L是无表头结点的单链表if (L&&L > next)Q=L;L=L> next;P=L; while(P > next)P=P > next;P> next=Q;Q > next=NULL;return ok;)/A（分数：5.00 ）正确答案：（本程序实现的功能就是：如果 L的长度不小于2,则将首元结点删去并插入到表尾。）解析：五、算法设计题（总题数：1,分数：10.00）32. 写岀向

17、某个有序文件中插入一个记录的程序。(分数：10.00 )正确答案： (所谓有序文件是指文件的记录按关键字由小到大 (或由大到小 )顺序存放。 为方便起见，可设文 件的每一个记录是一个整数，文件上数据是按由小到大顺序存放。设插入数据是命令行的第 3 个参数，且 设为d。若原文件中没有数据，则d写入文件；若有数据，则找到第1个比d大的数据i，先写入d,再将i 和其后各数据写回文件中，可通过调用 fseek 函数采实现插入。相应程序为：#include < stdio.h >#include < stdlib.h >#include < io.h >#includ

18、e < fcntl.h >#define LEN sizeof(int)void main(int argi,char*argc) int fp,i,d;if(argi < 3) printf("filename int/11")exit(0);d=atoi(argc2);fp=open(argc1,O_GREAT| O_RDWRI O_BINARY,s_IREAD| S_IWRITE);while(1) if( read(fp,&I,LEN)!=LEN)write(fp , &d,LEN):/*文件结束，d添加到文件尾端*/break;)if(i > =d) /*文件中读出数据i，若i > =d,则先存d*/ do fseek(fp,-1L*lan,SEEK_CUR); /* 文件指针后退 1 个记录 */write(fp,&d,LEN); /*d 写到文件中 */d=i; /* 原i作d,以便处理其他数据*/while(read(fp,&i,LEN)=LEN);write(fp ， &d,LEN);/* 继续读数据，并判别文件是否结束 */break;close(fp); /*main*/)解析：