数据结构自考题

2£数据结构自考题-11(总分90,做题时间90分钟)一、单项选择题1.当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为 •****・lonan****SSS_SIMPLE_SINA B C D分值：2答案:D2.长度为12的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法,则在等概率情况下，查找失败时的ASL值是 •**/12TOC\o"1-5"\h\z**/13**/12**/13SSS_SIMPLE_SINA B C D分值：2答案:B3.对广义表((a),(b))进行下面的操作head(head((a),(b)))后的结果是 •**B.(a)C.()D.不确定SSS_SIMPLE_SINA B C D分值：2答案:A

4.顺序存储结构A.仅适合于静态查找表的存储B.仅适合干动态查找表的存储C.既适合静态又适合动态查找表的存储D.既不适合静态又不适合动态查找表的存储SSS_SIMPLE_SINA B C D分值：2答案:C5.将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为 •**•**•****SSS_SIMPLE_SINA B C D分值：2答案:D6.非空的单循环链表L的尾结点Pt,满足 **t.next二NULL;**=NULL;**t.next二L;**=LSSS_SIMPLE_SINA B C D分值：2SSS_SIMPLE_SINA B C D分值：2答案:C7.对长度为n的关键字序列进行堆排序的空间复杂度为 **(log2n)**(1)• **(n)**(n A. A.快速排序B.插入排序C.堆排序I |SSS_SIMPLE_SINA B C D分值：2答案:B［解析］由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为0(1),但它是不稳定的。8.堆排序的最坏时间复杂度为 **(n)**(10g2n)**(nlog2n)**(n2)SSS_SIMPLE_SINA B C D分值：2答案:C9.在线性表的下列运算中，不改变数据元素之间结构关系的运算是A.插入B.删除C.排序D.定位SSS_SIMPLE_SINA B C D分值：2答案:D10.深度为k的二叉树，所含叶子的个数最多为 ********SSS_SIMPLE_SINA B C D分值：2答案:C

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,3,2,6,8,7)D.(8,7,6,5,4,3,2,1)SSS_SIMPLE_SINA B C D分值：2答案:C12.一个具有N个顶点的有向图最多有 条边。**(N-1)/2**(N-1)**(N+1)**(N+1)/2SSS_SIMPLE_SINA B C D分值：2答案:B13.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A.数据元素具有同一特点B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等SSS_SIMPLE_SINA B C D分值：SSS_SIMPLE_SINA B C D分值：2答案:B14.采用分治法进行排序的方法是•D.希尔排序SSS_SIMPLE_SINA B C D分值：2答案:A15.下列说法中正确的是 A.二叉树中任何一个结点的度都为2B.二叉树的度为2C.任何一棵二叉树中至少有一个结点的度为2D.一棵二叉树的度可以小于2SSS_SIMPLE_SINA B C D分值：2答案:D二、填空题1.一个字符串相等的充要条件是 和 。SSS_FILL分值：2答案:两个字符串的长度相等 对应位置的字符相等2.当所有结点的权值都相等时，用这些结点构造的二叉排序树上只有 分值：2答案:右子树3.假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中 。SSS_FILL分值：2答案：已有m个同义词的记录（或：已有m个记录；或：已满）4.数组的长度是 ，线性表的长度是 。SSS_FILL分值：2答案:固定的可变的5.对表长为9000的索引顺序表进行分块查找，假设每一块的长度均为15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为 。分值：2答案:308.56.多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是 SSS_FILL分值：2答案:一个数据元素可能有多个直接前趋和多个直接后继7.假设以列优先顺序存储二维数组A[5][8]，其中元素A[0][0]的存储地址为LOC(a),且每个元素占4个存储单元，则数组元素A[i][j]的存储地址为00SSS_FILL分值：2答案:LOC(a00)+4(5j+i)8.一棵含999个结点的完全二叉树的深度为 。SSS_FILL答案：10控制区间和控制区域是 文件的逻辑存储单位。SSS_FILLd1分值:2答案:VSAM10.对于数组，通常具有的基本操作有 种，它们分别是 SSS_FILLd1分值：2答案:两查找和修改三、解答题1.对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。答案：从三元组表还原稀疏矩阵时，首先根据表的第1行得出稀疏矩阵的行数和列数，否则，我们无法确定所求的稀疏矩阵的维数，然后根据三元组表所提供的行号和列号在稀疏矩阵的对应位置上写上相应的元素的值，在其他地方补零即可，根据上述原则，此题答案如图(1),(2)所示。2.图的邻接表的类型定义如下所示：#defineMaxVertexNum50typedefstruetnode{intadjvex;struetnode*next;}EdgeNode;typedefstruet{VertexTypevertex;EdgeNode*firstedge;}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];typedefstruet{AdjListadjiist;intn,e;}ALGraph;为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。答案：typeclefstruetArcNode{VNode*adjvex; //该弧所指向的顶点的位置structArcNode*nextare; //指向下一条弧的指针}ArcNode;typedefstructVNode{VertexTypedata; //顶点信息structVNode*nextVertex; //指向下一个顶点的指针ArcNode*firstare; //指向第一条依附该顶点的弧}VNode.*AdjList;typedefstruct{AdjListadjList;intn,e;}ALGraph;3.假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。答案：假设判定树的内部结点的总数为n=2h-l。则判定树是深度为h=lg(n+l)的满二叉树，树中第k层上的结点的个数为2h-i,查找它们所需要比较的次数是k。则在等概率下，二分查找成功时的平均查找长度为：，如果n很大，则可以用如下近似公式：lg(n+1)-1，作为二分查找成功时的平均查找长度。二分查找在查找失败时所需要比较的关键字的个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。因为判定树中度数小于2的结点只可能在最下面的两层上，所以n个结点的判定树的深度和n个结点的完全二叉树的深度相同，即为lg(n+l),所以，二分查找的最坏性能和平均性能十分接近。

某类物品的编号由一个大写英文字母及2位数字(0・・・9)组成，形如E32。运用基数排序对下列物品编号序列进行按字典序的排序，写出每一趟(分配和收集)后的结果。E13,A37,F43,B32,B47,E12,F37,B12第一趟：第二趟：第三耥：SSS_TEXT_QUSTI彳| |分值：5答案：第一趟：B32,E12,B12,E13,F43,A37,B47,F37第二趟：E12,B12,E13,B32,A37,F37,F43,B47第三趟：A37,B12,B32,B47,E12,E13,F37,F43四、算法阅读题阅读下列算法，并回答问题：设串s二"OneWorldOneDream"，t二"One"，pos是一维整型数组，写出算法f32(s,t,pos)执行之后得到的返回值和pos中的值；简述算法f32的功能。intstrlen(char*s);/*返回串S的长度*/intindex(char*st，char*t);/*若串t在串st中出现，则返回在串st中首次出现的下标值，否则返回T*/intf32(char*s,char*t,intpos[]){inti,j,k,ls,It;Is=strlen(s);lt二strlen(t);if(ls==0||It二二0)return-1;k=0;i=0;do{j=index(s+i,t);if(j>=0){pos[k++]=i+j;i+=j+it;}}while(i+itV二is&&j>=0);returnk;}SSS_TEXT_QUSTI分值：5答案：2；pos[0]=0,pos[l]=8SSS_TEXT_QUSTI2.分值：5答案：返回串t在S中出现的次数，并将每次出现的位置依次存放在数组pos中。五、算法设计题1.有两个磁盘文件A、B,各存放一行字母，要求把这两个文件中的信息按字母顺序排列合并，输出到一个新文件C中。SSS_TEXT_分值：10答案：可先分别将A、B文件的内容读出放到数组C中，再对数组C排序，最后再将数组内容写到文件C中，程序为：#includeVstdio.h>main()/*合并A、B文件内容到C文件中*/{FILE*fp;inti,j,n,m;charc[160],t,ch;if((fp二fopen("A","r"))二二Null){printf("文件Acan'topen\n");exit(0);}else{printf("\n文件A的内容为\n")for(i=0;(ch=fgetc(fp))!=E0F:i++){C[i]=oh;putchar(C[-i]);}fclose(fp);m=i;}if((fp=fopen("B","r")==Null){printf("B文件can'topen\n");exit(0);}else{printf("\nB文件内容是\n");for(i=m;(ch=fgetc(fp))!=EOF;i++){