数据结构自考题-10

1、数据结构自考题 -10( 总分： 100.00 ，做题时间： 90 分钟 )一、单项选择题 ( 总题数： 15，分数： 30.00)1. 当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为 ( )A. n2 B . n Iona n C . Iog2 n D . n-1(分数： 2.00 )A.B.C.D. V解析：查找2. 长度为 12 的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法， 则在等概率情况下， 失败时的ASL值是()A 37/1 2 B 62/13 C 39/12 D 49/13(分数： 2.00 )A.B. VC.D.解析：3. 对广义表 (a)

2、，(b) 进行下面的操作 head(head(a) ，(b) 后的结果是 ( )Aa B(a)C( ) D 不确定(分数： 2.00 )A. VB.C.D.解析：4. 顺序存储结构 ( )A. 仅适合于静态查找表的存储B. 仅适合干动态查找表的存储C. 既适合静态又适合动态查找表的存储D. 既不适合静态又不适合动态查找表的存储(分数： 2.00 )A.B.C. VD.解析：5. 将含有 83 个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、 从左到右的顺序对结点编号，那么编号为 41 的结点的双亲结点编号为 ( )A42 B40C21 D20(分数： 2.00 )A.B.C.D.

3、 V解析：6. 非空的单循环链表L的尾结点Pf,满足()A. Pf .next=NULL; B . P=NULL;CPf .next=L; D P=L(分数： 2.00 )A.B.C. VD.解析：7. 对长度为 n 的关键字序列进行堆排序的空间复杂度为 ( ) AO(log 2n) B O(1)C O(n) D O(n*log 2n)(分数： 2.00 )A.B. VC.D.解析： 解析 由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。堆排序是就地 排序,辅助空间为 0(1) ,但它是不稳定的。8. 堆排序的最坏时间复杂度为 ( )AO(n) B O(10g2n)C O(

4、nlog 2n) D O(n2) (分数： 2.00 )A.B.C. VD.解析：9. 在线性表的下列运算中,不改变数据元素之间结构关系的运算是( )A. 插入B .删除C .排序D .定位(分数： 2.00 )A.B.C.D. V解析：10. 深度为 k 的二叉树，所含叶子的个数最多为 ( ) A2K BKC 2K-1 D 2K-1(分数： 2.00 )A.B.C. VD.解析：11. 对关键字序列 (6,1,4,3,7,2,8,5) 进行快速排序时，以第 1 个元素为基准的一次划分的结果为 ( ) A (5,1,4,3,6,2,8,7) B(5,1,4,3,2,6,7,8)C (5,1,4

5、,3,2,6,8,7) D(8,7,6,5,4,3,2,1)(分数： 2.00 )A.B.B. VD.解析：12. 一个具有N个顶点的有向图最多有()条边。AN(N-1)/2 B N(N-1) C N(N+1) DN(N+1)/2(分数： 2.00 )A.B. VC.D.解析：13. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 ( )A. 数据元素具有同一特点B. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C. 每个数据元素都一样D. 数据元素所包含的数据项的个数要相等分数： 2.00 )A.B. VC.D.解析：14. 采用分治法进行排序的方法是 （

6、 ）A.快速排序B 插入排序C. 堆排序D 希尔排序（分数： 2.00 ）A. VB.C.D.解析：15. 下列说法中正确的是 （ ）A. 二叉树中任何一个结点的度都为2B. 二叉树的度为 2C. 任何一棵二叉树中至少有一个结点的度为2D. 棵二叉树的度可以小于2（分数： 2.00 ）A.B.C.D. V解析：二、填空题 （总题数： 10，分数： 20.00）16. 一个字符串相等的充要条件是 和（分数： 2.00 ）填空项 1: （正确答案：两个字符串的长度相等 对应位置的字符相等）解析：17. 当所有结点的权值都相等时，用这些结点构造的二叉排序树上只有1（分数： 2.00 ）填空项 1:（

7、正确答案：右子树）解析：18. 假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中1 。（分数： 2.00 ）填空项1: （正确答案：已有 m个同义词的记录（或：已有m个记录；或：已满）解析：19. 数组的长度是 ，线性表的长度是 。（分数:2.00 ）填空项1: （正确答案：固定的可变的）解析：20. 对表长为9000的索引顺序表进行分块查找，假设每一块的长度均为15,且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为1。（分数：2.00）填空项1: （正确答案：308.5）解析：21. 多维数组和广义表是一种非常复杂的非线

8、性结构，它们的逻辑特点是1（分数：2.00）填空项1： （正确答案：一个数据元素可能有多个直接前趋和多个直接后继）解析：22. 假设以列优先顺序存储二维数组A58，其中元素A00的存储地址为LOC（a。），且每个元素占4个存储单元，则数组元素Aij的存储地址为1。（分数：2.00）填空项 1: （正确答案：LOC（st0）+4（5j+i）解析：23. 一棵含999个结点的完全二叉树的深度为1。（分数：2.00）填空项1: （正确答案：10）解析：24. 控制区间和控制区域是 1文件的逻辑存储单位。（分数：2.00）填空项1: （正确答案：VSAM解析：25. 对于数组，通常具有的基本操作有 种

9、，它们分别是 （分数：2.00）填空项1: （正确答案：两 查找和修改）解析：三、解答题（总题数：4,分数：20.00）26. 对于下面用三元组表示的稀疏矩阵，请分别写岀它们所对应的稀疏矩阵。正确答案：（从三元组表还原稀疏矩阵时，首先根据表的第1行得岀稀疏矩阵的行数和列数，否则，我们无法确定所求的稀疏矩阵的维数，然后根据三元组表所提供的行号和列号在稀疏矩阵的对应位置上写上相应 的元素的值，在其他地方补零即可，根据上述原则，此题答案如图（1），（2）所示。解析：27. 图的邻接表的类型定义如下所示：#define MaxVertexNum 50typedef struct nodeint adj

10、vex;struct node*next;EdgeNode;typedef structVertexType vertex;EdgeNode*firstedge;VertexNode;typedef VertexNode A djListMaxVertexNum;typedef structAdjList adjiist;int n,e;ALGraph;为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如 下图所示，请写岀重新定义的类型说明。（分数：5.00 ） 正确答案：（typeclef struct ArcNodeVNode*adjvex; / 该

11、弧所指向的顶点的位置struct ArcNode*nextarc; / 指向下一条弧的指针ArcNode;typedef struct VNodeVertexType data; /顶点信息struct VNode*nextVertex; /指向下一个顶点的指针ArcNode*firstarc; / 指向第一条依附该顶点的弧VNode.*AdjList;typedef structAdjList adjList;int n,e;ALGraph;）解析：28. 假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析 二分查找的最坏性能和平均性能。正确答案：(假

12、设判定树的内部结点的总数为n=2h-1。则判定树是深度为h=lg(n+1)的满二叉树，树中第k层上的结点的个数为2h-1，查找它们所需要比较的次数是k。则在等概率下，二分查找成功时的平均查找长度为：，如果n很大，则可以用如下近似公式：lg(n+1)-1 ，作为二分查找成功时的平均查找长度。二分查找在查找失败时所需要比较的关键字的个数不超过判定树的深度，在最坏情况下查找成功的比较次 数也不超过判定树的深度。因为判定树中度数小于2的结点只可能在最下面的两层上，所以n个结点的判定树的深度和n个结点的完全二叉树的深度相同，即为lg(n+1)，所以，二分查找的最坏性能和平均性能十分接近。)解析：29.

13、某类物品的编号由一个大写英文字母及2位数字(09)组成，形如 E32。运用基数排序对下列物品编号序列进行按字典序的排序，写岀每一趟(分配和收集)后的结果。E13,A37,F43,B32,B47,E12,F37,B12第一趟：第二趟： 第三耥：(分数：5.00 ) 正确答案：(第一趟：B32,E12,B12,E13,F43,A37,B47,F37第二趟：E12,B12,E13,B32,A37,F37,F43,B47第三趟：A37,B12,B32,B47,E12,E13,F37,F43)解析：四、算法阅读题(总题数：3,分数：20.00)30. 求下面算法中变量 count的值：(假设n为2的乘幂

14、，并且n > 2) int Timeint ncount=0;x=2;while(x < n/2)x*=2;count+;return(count)(分数：5.00 ) 正确答案：(count=log 2n)解析：31. 请将下面的程序改成递归的过程。voide ditui(int n)int i;i=n;while(i > 1)prinft(i_);分数： 5.00 ) 正确答案： ( 此递推过程可以改写成如下递归过程：voide dkui(int j)if(i > 1)prind(j);digui(j-1);)解析：阅读下列算法，并回答问题：(1) 设串 s=&qu

15、ot;OneWorldOneDream"， t="One" ，pos 是一维整型数组，写出算法 f32(s,t,pos) 执行之后得到的 返回值和 pos 中的值；(2) 简述算法 f32 的功能。int strlen(char*s); /*返回串 S 的长度 */int index(char*st ，char*t);/* 若串 t 在串 st 中出现，则返回在串 st 中首次出现的下标值，否则返回 -1*/int f32(char*s,char*t,int pos)int i,j,k,ls,It;Is=strlen(s);lt=strlen(t);if(ls=0

16、| It=0)return-1;k=0;i=0;doj=index(s+i,t);if(j > =0)posk+=i+j;i+=j+it;while(i+it < =is&&j>=0);return k;(分数： 10.00 ) 正确答案： (2 ；pos0=0 ，pos1=8) 解析：正确答案：(返回串t在S中出现的次数，并将每次出现的位置依次存放在数组pos中。)解析：五、算法设计题 ( 总题数： 1，分数： 10.00)32. 有两个磁盘文件A、B,各存放一行字母，要求把这两个文件中的信息按字母顺序排列合并，输出到一 个新文件C中。正确答案：(可先分别将

17、A、B文件的内容读出放到数组C中，再对数组C排序，最后再将数组内容写到文件 C 中，程序为：#include < stdio.h >main()/* 合并A B文件内容到 C文件中*/ FILE*fp;int i,j,n,m;char c160,t,ch;if(fp=fopen("A","r")=Null) printf(" 文件 A can't open/n");exit(0);else printf("/n 文件 A的内容为/n") for(i=0;(ch=fgetc(fp)!=EOF:i+) Ci=oh;putchar(C-i);fclose(fp);m=i;if(fp=fopen("B","r")=Null) printf("B 文件 can't open/n");exit(0);else printf("/nB 文件内容是 /n");for(i=m;(ch=fgetc(f