[自学考试密押题库与答案解析]数据结构导论自考题模拟5PAGE1/NUMPAGES1[自学考试密押题库与答案解析]数据结构导论自考题模拟5数据结构导论自考题模拟5一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的。问题:1.算法的便于阅读和理解的特性称为A.正确性B.易读性C.健壮性D.时空性答案:B[解析]本题主要考查的知识点是算法的易读性。[要点透析]算法的易读性是指易于阅读、理解和交流,便于调试、修改和扩充。问题:2.给定有n个元素,建立一个有序单链
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
的时间复杂度为A.O(1)B.O(n)C.O(n2)D.O(nlog2n)答案:B[解析]本题主要考查的知识点是建立有序单链表的时间复杂度。[要点透析]在创建有序单链表的过程中,每一次将新结点链接入有序表的时间分两部分,其一是查找插入的合适位置,其二是将元素插入。后者的时间复杂度是常量O(1),而前者的时间复杂度由比较元素的次数决定,由于元素比较的次数是不确定的,只能取平均比较次数,为(n+1)/2,故其时间复杂度为O(n)。由线性累加规则可得整个算法的时间复杂度为:O(n)。问题:3.在双链表中某结点(已知其地址)前插入一新结点,其时间复杂度为A.O(n)B.O(1)C.O(n2)D.O(log2n)答案:B问题:4.顺序栈s中top为栈顶指针,指向栈顶元素所在的位置,elem为存放栈的数组,则元素e进栈操作的主要语句为A.s.elem[top]=e;s.top=s.top+1;B.s.elem[top+1]=e;s.top=s.top+1;C.s.top=s.top+1;s.elem[top+1]=e;D.s.top=s.top+1;s.elem[top]=e;答案:D问题:5.一个数组的第一个元素的存储地址是100,每个元素占2个存储单元,则第5个元素的存储地址是A.110B.108C.100D.120答案:B问题:6.已知某完全二叉树采用顺序存储结构,结点数据的存放顺序依次为A、B、C、D、E、F、G、H,该完全二叉树的后序遍历序列为A.HDBEFCGAB.HDEBFGCAC.DHEBFGACAD.DEHBFGCA答案:B[解析]本题主要考查的知识点是完全二叉树的后序遍历。[要点透析]要求得二叉树的后序遍历序列。必须首先将二叉树构造出来。根据题意可求得二叉树如下图所示。对二叉树进行后序遍历,可知正确答案为B项。问题:7.除根结点外,树上每个结点A.可有任意多个孩子、一个双亲B.可有任意多个孩子、任意多个双亲C.可有一个孩子、任意多个双亲D.只有一个孩子、一个双亲答案:A问题:8.一棵完全二叉树上有1001个结点,其中叶子结点的个数是A.250B.500C.501D.505答案:C[解析]本题主要考查的知识点是完全二叉树。[要点透析]由二叉树结点的公式:n=n0十n1+n2=n0+n1+(n0-1)=2n0+n1-1,因为n=1001,所以1002=2n0+n1,在完全二叉树中,n1只能取0或1,在本题中只能取0(如果取1则n0=500.5是不可能的),故n=501。问题:9.设有6个结点的无向图,若要确保此图是一个连通图,则至少应有边的条数是A.5B.6C.7D.8答案:A[解析]本题主要考查的知识点是无向图的连通图。[要点透析]无向图的顶点数为n,则其含有全部顶点的连通图的边数最少为n-1。问题:10.在含有n个顶点e条边的无向图的邻接矩阵中,零元素的个数为A.eB.2eC.n2-eD.n2-2e答案:D问题:11.设有无向图G=(V,E)和(G'=(V',E'),如G'为G的生成树,则下面说法不正确的是A.G'为G的子图B.G'为G的连通分量C.G'为G的极小连通子图且V'=VD.G'是G的无环子图答案:B[解析]本题主要考查的知识点是无向图。[要点透析]一个连通图的生成树,是含有该连通图的全部顶点的一个极小连通子图,但不一定含有全部的边,也就不满足连通分量的定义。因此不能说G'为G的连通分量。问题:12.利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后,查找元素35要进行元素间比较的次数是A.4次B.5次C.7次D.10次答案:A[解析]本题主要考查的知识点是二叉排序树的查找。[要点透析]建立起二叉排序树如图所示。查找元素35需要比较4次,所以选A。问题:13.采用二分查找法,若当前取得的中间位置MID的元素值小于被查找值,则表明待查元素可能在表的后半部分,下次查找的起始位置通常应A.从MID/2位置开始B.从MID位置开始C.从MID-1位置开始D.从MID+1位置开始答案:D问题:14.当待排序序列中
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
数较少或基本有序时,最适合的排序方法为A.直接插入排序法B.快速排序法C.堆排序法D.归并排序法答案:A问题:15.一组记录的关键码为(46,79,56,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)答案:C[解析]本题主要考查的知识点是快速排序的方法。[要点透析]快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小。初始序列:467956384084第1次交换:407956384684第2次交换:404656387984第3次交换:403856467984第4次交换:403846567984二、填空题问题:1.算法的空间性能是指算法需要的______。答案:存储量问题:2.程序段“i=1;while(i<=n)i=i*2;”的时间复杂度T(n)=______。答案:O(log2n)问题:3.对顺序表执行删除操作,其删除算法的平均时间复杂度为______。答案:O(n)问题:4.顺序队的出、入队操作会产生______。答案:假溢出问题:5.若front和rear分别表示循环队列Q的头指针和尾指针,m0表示该队列的最大容量,则循环队列为空的条件是______。答案:Q.rear==Q.front问题:6.二维数组A[5][6]采用按列为主序的存储方式,每个元素占3个存储单元,若A[0][0]的存储地址是100,则A[4][3]的存储地址是______。答案:157问题:7.对一棵深度为10的满二叉树按层编号,则编号为51的结点,它的双亲结点编号为______。答案:25问题:8.对于一棵具有n个结点的二叉树,当进行链接存储时,其二叉链表中的指针域的总数为2n个,其中______个用于链接孩子结点。答案:n-1问题:9.设F、C是二叉树中的两个结点,若F是C的祖先结点,则在采用后序遍历方法遍历该二叉树时,F和C的位置关系为:F必定在C的______。答案:后面问题:10.在无向图G的邻接矩阵A中,若A[i][j]等于0,则A[j][i]等于______。答案:0问题:11.有n个顶点的强连通图最多有______条弧。答案:n(n-1)问题:12.先在所有的记录中选出键值最小的记录,将它与第一个记录交换;然后在其余的记录中再选出最小的记录与第二个记录交换,依此类推,直至所有记录排序完成。这种排序方法称为______。答案:直接选择排序问题:13.对n个元素进行冒泡排序时,第一趟排序的比较次数为______。答案:n-1三、应用题问题:1.已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA,试画出这棵二叉树,并给出其先序序列。答案:先序序列为:ABCDEFGH,所求二叉树如图所示:问题:2.分别写出删除单向和双向循环链表中指针P所指的结点的直接后继结点(非尾结点)对应的语句。(1)单向循环链表。(2)双向循环链表。答案:(1)单向循环链表:p->next=p->next->next;(2)双向循环链表:p->next=p->next->next;p->next->prior=P;问题:3.假设高度为h的二叉树上只有度为0和度为2的结点,问此类二叉树中的结点数可能达到的最大值和最小值各为多少?并说明是什么样的二叉树?答案:结点数的最大值为2h-1,最小值为2h-1(第一层根结点,其余每层均两个结点且互为兄弟)。结点最多时为满二叉树。h=5时最小值的情况之一:结点最少时是类似于上图的二叉树。问题:4.试写出下图的拓扑序列。答案:有以下三个拓扑序列:v1v5v2v3v6v4v1v5v6v2v3v4v5v6v1v2v3v4问题:5.已知数据序列为(12,5,9,20,6,31,24),对该数据序列进行排序,试写出插入排序和冒泡排序每趟的结果。答案:(1)插入排序的每趟的结果:初始值键值序列12592063124i=2[5]1292063124i=3[59]122063124i=4[5912]2063124i=5[56912]203124i=6[5691220]3124i=7[569122024]31排序结果[56912202431](2)冒泡排序的每趟的结果:初始键值序列[12592063124]第一趟之后[591262024]31第二趟之后[5961220]2431第三趟之后[56912]202431第四趟之后56912202431四、算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
题问题:1.设某带头结点的单链表的结点结构说明如下:typedefstructnodel{intdata;structnodel*next;}node;试设计一个算法:voidcopy(node*head1,node*head2),将以head1为头指针的单链表复制到一个不带有头结点且以head2为头指针的单链表中。答案:算法描述如下:voidcopy(node*head1,node*head2){node*p,*q;head2=(node*)malloc(sizeof(node))q=head2;p=head1->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);}问题:2.试编写算法求键值为k结点在给定的二叉排序树中所在的层数。答案:算法描述如下:intlevel_count(BinTreebst,KeyTypek)//求键值为k结点在给定的二叉排序树中所在//的层数{intlev=0;BSTNode*p=bst;while(p!=NULL){lev++;if(p->data==k)returnlev;//返回结果if(p->data<k);p=p->rchild;//向右走elsep=P->lchild;//向左走}return0;//没有对应结点}