[自学考试密押题库与答案解析]数据结构自考题模拟12

1、自学考试密押题库与答案解析数据结构自考题模拟12自学考试密押题库与答案解析数据结构自考题模拟12数据结构自考题模拟12一、单项选择题问题:1. 当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为A.n2B.nlonanC.log2nD.n-1答案:D问题:2. 长度为12的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的ASL值是A.37/12B.62/13C.39/12D.49/13答案:B问题:3. 对广义表(a)，(b)进行下面的操作head(head(a)，(b)后的结果是A.aB.(a)C.( )D.不确定答案:A问题:4.

2、顺序存储结构A.仅适合于静态查找表的存储B.仅适合干动态查找表的存储C.既适合静态又适合动态查找表的存储D.既不适合静态又不适合动态查找表的存储答案:C问题:5. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为A.42B.40C.21D.20答案:D问题:6. 非空的单循环链表L的尾结点P，满足A.P.next=NULL;B.P=NULL;C.P.next=L;D.P=L答案:C问题:7. 对长度为n的关键字序列进行堆排序的空间复杂度为A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)答案

3、:B解析 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为0(1)，但它是不稳定的。问题:8. 堆排序的最坏时间复杂度为A.O(n)B.O(10g2n)C.O(nlog2n)D.O(n2)答案:C问题:9. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是A.插入B.删除C.排序D.定位答案:D问题:10. 深度为k的二叉树，所含叶子的个数最多为A.2KB.KC.2K-1D.2K-1答案:C问题:11. 对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时，以第1个元素为基准的一次划分的结果为A.(5,1,4,3,6,2,8,7)

4、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)答案:C问题:12. 一个具有N个顶点的有向图最多有 条边。A.N(N-1)/2B.N(N-1)C.N(N+1)D.N(N+1)/2答案:B问题:13. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着A.数据元素具有同一特点B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等答案:B问题:14. 采用分治法进行排序的方法是A.快速排序B.插入排序C.堆排序D.希尔排序答案:A问题:15. 下

5、列说法中正确的是A.二叉树中任何一个结点的度都为2B.二叉树的度为2C.任何一棵二叉树中至少有一个结点的度为2D.一棵二叉树的度可以小于2答案:D二、填空题问题:1. 一个字符串相等的充要条件是_和_。答案:两个字符串的长度相等 对应位置的字符相等问题:2. 当所有结点的权值都相等时，用这些结点构造的二叉排序树上只有_。答案:右子树问题:3. 假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中_。答案:已有m个同义词的记录(或：已有m个记录；或：已满)问题:4. 数组的长度是_，线性表的长度是_。答案:固定的 可变的问题:5. 对表长为9000的索引顺序表进

6、行分块查找，假设每一块的长度均为15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为_。答案:308.5问题:6. 多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是_。答案:一个数据元素可能有多个直接前趋和多个直接后继问题:7. 假设以列优先顺序存储二维数组A58，其中元素A00的存储地址为LOC(a00)，且每个元素占4个存储单元，则数组元素Aij的存储地址为_ 。答案:LOC(a00)+4(5j+i)问题:8. 一棵含999个结点的完全二叉树的深度为_。答案:10问题:9. 控制区间和控制区域是_文件的逻辑存储单位。答案:VSAM问题:10.

7、 对于数组，通常具有的基本操作有_种，它们分别是_。答案:两 查找和修改三、解答题问题:1. 对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。 答案:从三元组表还原稀疏矩阵时，首先根据表的第1行得出稀疏矩阵的行数和列数，否则，我们无法确定所求的稀疏矩阵的维数，然后根据三元组表所提供的行号和列号在稀疏矩阵的对应位置上写上相应的元素的值，在其他地方补零即可，根据上述原则，此题答案如图(1)，(2)所示。 问题:2. 图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node int adjvex; struct node*

8、next; EdgeNode; typedef struct VertexType vertex; EdgeNode*firstedge; VertexNode; typedef VertexNode A djListMaxVertexNum; typedef struct AdjList adjiist; int n,e; ALGraph; 为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。 答案:typeclef struct ArcNode VNode*adjvex; /该弧所指向的顶点的位置 struct A

9、rcNode*nextarc; /指向下一条弧的指针 ArcNode; typedef struct VNode VertexType data; /顶点信息 struct VNode*nextVertex; /指向下一个顶点的指针 ArcNode*firstarc; /指向第一条依附该顶点的弧 VNode.*AdjList; typedef struct AdjList adjList; int n,e; ALGraph; 问题:3. 假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。答案:假设判定树的内部结点的总数为n=

10、2h-1。则判定树是深度为h=lg(n+1)的满二叉树，树中第k层上的结点的个数为2h-1，查找它们所需要比较的次数是k。则在等概率下，二分查找成功时的平均查找长度为：，如果n很大，则可以用如下近似公式：lg(n+1)-1，作为二分查找成功时的平均查找长度。二分查找在查找失败时所需要比较的关键字的个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。因为判定树中度数小于2的结点只可能在最下面的两层上，所以n个结点的判定树的深度和n个结点的完全二叉树的深度相同，即为lg(n+1)，所以，二分查找的最坏性能和平均性能十分接近。问题:4. 某类物品的编号由一个大写英文字母及2位

11、数字(09)组成，形如E32。运用基数排序对下列物品编号序列进行按字典序的排序，写出每一趟(分配和收集)后的结果。 E13,A37,F43,B32,B47,E12,F37,B12 第一趟： 第二趟： 第三耥： 答案: 第一趟：B32,E12,B12,E13,F43,A37,B47,F37 第二趟：E12,B12,E13,B32,A37,F37,F43,B47 第三趟：A37,B12,B32,B47,E12,E13,F37,F43 四、算法阅读题问题:1. 求下面算法中变量count的值：(假设n为2的乘幂，并且n2) int Time int n count=0;x=2; while(xn/2

12、) x*=2;count+; return(count) 答案:count=log2n问题:2. 请将下面的程序改成递归的过程。 voide ditui(int n) int i; i=n; while(i1) prinft(i-); 答案:此递推过程可以改写成如下递归过程： voide dkui(int j) if(i1) prind(j); digui(j-1); 阅读下列算法，并回答问题： (1)设串s=OneWorldOneDream，t=One，pos是一维整型数组，写出算法f32(s,t,pos)执行之后得到的返回值和pos中的值； (2)简述算法f32的功能。 int strle

13、n(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| It=0)return-1; k=0; i=0; do j=index(s+i,t); if(j=0) posk+=i+j; i+=j+it; while(i+it=is=0); return k; 3.答案:2；pos0=0，pos1=84.答案:返

14、回串t在S中出现的次数，并将每次出现的位置依次存放在数组pos中。五、算法设计题问题:1. 有两个磁盘文件A、B，各存放一行字母，要求把这两个文件中的信息按字母顺序排列合并，输出到一个新文件C中。答案:可先分别将A、B文件的内容读出放到数组C中，再对数组C排序，最后再将数组内容写到文件C中，程序为： #includestdio.h main() /*合并A、B文件内容到C文件中*/ FILE*fp; int i,j,n,m; char c160,t,ch; if(fp=fopen(A,r)=Null) printf(文件A cant openn); 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文件cant openn); exit(0); else printf(nB文件内容是n); for(i=m;(ch=fgetc