《自学考试-数据结构导论自考题模拟5》由会员分享，可在线阅读，更多相关《自学考试-数据结构导论自考题模拟5（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构导论自考题模拟5一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的。丄、算法的便于阅读和理解的特性称为()A正确性 B.易读性C.健壮性 D.时空性2、给定有n个元素，建立一个有序单链表的时间复杂度为()A 0(1) B 0(n)C 0(n) D. 0 (nlog2n)3、在双链表中某结点(已知其地址)前插入一新结点，其时间复杂度为()A 0(n)B 0(1)C 0(r)2)D 0(1og2n)4、顺序栈s中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为()A- selemtop=e;s.top=stop+1;B- s.el
2、emtop+1=e;stop=stop+1;C. s top=stop+1;selemtop+1=e;D. s . top=stop+1;s.elemtop=e;5、一个数组的第一个元索的存储地址是100,每个元素占2个存储单元，则第5个元素的存储地址是 ( )A 110B 108C 100D 1206、已知某完全二叉树采用顺序存储结构，结点数据的存放顺序依次为A、B、C、D、E、F、G、H,该完全二叉树的后序遍历序列为()A. HDBEFCGAB. HDEBFGCAC DHEBFGACAD DEHBFGCA7、除根结点外，树上每个结点()A可有任意多个孩子、一个双亲 B.可有任意多个孩子、任
3、意多个双亲C.可有一个孩子、任意多个双亲 D.只有一个孩子、一个双亲8、-棵完全二叉树上有1001个结点，其中叶子结点的个数是()A. 250 B. 500C 501 D 5059、设有6个结点的无向图，若要确保此图是一个连通图，则至少应有边的条数是()A5 B6C7 D810、在含有n个顶点e条边的无向图的邻接矩阵中，零元素的个数为()A. e B 2eC. n2-e D n2-2e11设有无向图G=(V, E.和(G,= (V, E1 ),如G，为G的生成树，则下面说法不正确的是()A. G，为G的子图 B. G，为G的连通分量C. G，为G的极小连通子图且Vf=VD. G，是G的无环子图
4、12、利用逐点插入法建立序列(50, 72, 43, 85, 75, 20, 35, 45, 65, 30)对应的二叉排序树 以后，查找元素35要进行元素间比较的次数是()A. 4次B. 5次C. 7次D10次23、采用二分查找法，若当前取得的中间位置MID的元素值小于被查找值，则表明待查元素可能在表 的后半部分，下次查找的起始位置通常应()A.从MID/2位置开始B.从MID位置开始C.从MID-1位置开始D.从MTD+l位置开始丄4、当待排序序列中记录数较少或基本有序时，最适合的排序方法为()A.直接插入排序法B快速排序法C堆排序法D归并排序法15、一组记录的关键码为(46, 79, 56
5、, 38, 40, 84),则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为()A. (38, 40, 46, 56, 79, 84)B(40, 38, 46, 79, 56, 84)C. (40, 38, 46, 56, 79, 84)D(40, 38, 46, 84, 56, 79)二、填空题16、算法的空间性能是指算法需要的o17、程序段Ai=l; while (i B解析本题主要考查的知识点是无向图。要点透析一个连通图的生成树，是含有该连通图的全部顶点的一个极小连通子图，但不一定含有 全部的边，也就不满足连通分量的定义。因此不能说L为G的连通分量。12、A解析本题主要考查的
6、知识点是二叉排序树的查找。要点透析建立起二叉排序树如图所示。查找元素35需要比较4次，所以选A。13、D14.A15、C解析木题主要考查的知识点是快速排序的方法。要点透析快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分 割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。初始序列：46 79 56 38 40 84第1次交换407956384684第2次交换404656387984第3次交换403856467984第4次交换403846567984二、填空题16、存储量17、O(log2n)Qrear=Q.front21 15726、n(n-l)2
7、7、直接选择排序三、应用题18 0(n)22、2528 n-119、假溢出20、23 n-124、后面25、29、先序序列为：ABCDEFGH,所求二叉树如图所示:p-next=p-nex t- nex t;(2)双向循环链表:30、(1)单向循环链表:p-nex t=p- next- next;p-next-prior=P;31、结点数的最大值为姑-1,最小值为2h-l (第一层根结点,其余每层均两个结点口互为兄弟)。结点最多时为满二叉树。h=5时最小值的情况之一：结点最少时是类似于上图的二叉树。Vx V5 V2 V3 V6 V432、有以下三个拓扑序列:Vi v5 v6 v2 v3 v4v
8、5 v6 Vi v2 v3 v433 (1)插入排序的每趟的结果:初始值键值序列12 5 9 20 6 31 24i=2 5 12 9 20 6i=3 5i=4 5i=5 5i=6 5i=7 52424242424313131319 12 20 61220 69 12209 12 203196669 12 20 2431排序结果5 6 9 12 20 24 31 (2)冒泡排序的每趟的结果：第一趟之后5 第二趟之后5 第三趟之后5 第四趟之后5初始键值序列12 5 9 20 6 31 249 12 6 20 24319 6 12 2024 316 9 1220 24 316 9 12 20 24 31四、算法设计题34、算法描述如下:void copy(node* headl, node*head2) node*p, *q;head2=(node*) malloc(sizeof(node)q=head2; p=headl-next; while(p!=NULL)s=(node*)malloc (sizeof(node);s-data=p-data;q-next=s;q=s；p=p-next;q-next=NULL;p=head2;head2=head2-next;free(p);35、算法描述如下：int level_count (BinTree bst, KeyTy
