数据结构总复习习题讲解教学课件

数结的习愿解2019年11月选择题1在一个长度为n的顺序表中,向第个元素(1sn+1)之前插入个新元素时,需向后移动B_个元素A.n-1Bn-i+1n2在一个具有n个单元的顺序栈中,假定以地址低端作为栈底以top作为栈顶指针,则当做出栈处理时,top变化为_CAtop不变B=-nc=top-1D=top+15若进栈序列为12,3,4进栈过程中可以出栈,则C不可能是个出栈序列。A.3,4,21B.2,4,31C.14123D.3,2,147.在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队首指针和队尾指针,则判断队满的条件是D_。Arear%n==frontb.rear-1%n==frontC(rear-1%n==rearD(rear+1)%n==front9在一个单链表中,已知*q结点是*p结点的前驱结点,若在*q和之间插入*s结点,则执行C_。Ap->next;p->next=s;B.p->next=s->next;s->next=pCq->next=s;s->next=pD.p->next=s;S->next=q10.向一个栈项指针为hs的链栈中插入一个*s结点时,则执行A.hs->next=s:Bs->next=hs->next:hs->next=s:Cs->next=hs:hs=s:DS->next=hs;hs=hs.>next1在一个链队列中,假定front和rear分别为队首指针和队尾指针则进行插入*s结点的操作时应执行_BA.front->next=sfront=s:B.rear->next=srear=:Cfront=front->nextDfront=rear->next4线性表采用链式存储时,其地址D。A.必须是连续的B.部分地址必须是连续的C一定是不连续的D.连续与否均可以15设单链表中指针p指着结点(数据域为m),指针f指着将要插入的新结点(数据域为x,当x插在结点m之后时,只要先修改B后修改p->ink=f即可A.f->link=pB.f->link=p->link;C.p->link=f->link;Df=ni;16在双向链表存储结构中,删除p所指的结点时需修改指针A(p->prior)->next)->prior=p;p->next=(p->next)->next;B(p->prior)->next=p->next;(p->next)->prior=p->prior;C.p->prior=(p->prior)->prior;((p->prior)->prior)->next=pD(p->prior)->prior)->next=p;p->prior=(p->prior)->prior7在双向链表存储结构中,删除p所指的结点的前趋结点(若存在)时需修改指针AA((p->llink)-llink)->rlink=p;p->llink=(p->llink)->llinkB((p->rlink)->rlink)->llink=p;p->rlink=(p->rlink)->rlinkC(p->link)->rlink=p->rlink;(p->rlink)->llink=p->llinkD.p->llink=(p->llink)->llink;(p-llink)-llink)->rlink=p;20.二分法查找A存储结构。A.只适用于顺序B.只适用于链式C.既适用于顺序也适用于链式D.既不适合于顺序也不适合于链式21在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上B_。A.一定相邻B.不一定相邻c.有时相邻2.设字符串s1=abcdefg,s2=pqrst',则运算s=concat(sub(s1,2len(s2)subs1len(s2),2)后串值为D。AbcdefB.bcdefgC.bcpgrst'D.bcdefef23假定在一棵二叉树中,双分支结点数为15个,单分支结点数为32个,则叶子结点数为BA.15B.16C.17D.4724假定一棵二叉树的结点数为18个,则它的最小高度B_。A.4C.6D.1825在一棵二叉树中第五层上的结点数最多为CA.8B.15C.16D.3226在一棵具有五层的满二叉树中,结点总数为A。A.31B.32C.33D.1627已知8个数据元素为(34、76、45、18、26、54、92、65)依次插入结点的方法生成一棵二叉排序树后,最后两层上的A.1B.2D.428由分别带权为92、5、7的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度为c。A.23B.37C.44D.4631如果结点A有三个兄弟,而且B是A的双亲,则B的出度是A.3C.5D.1·33在完全二叉树中,当为奇数且不等于1时,结点左兄弟是结点D,否则没有左兄弟。A.2i-1B.i+1C.2i+1D.i-134某二叉树T有n个结点,设按某种遍历顺序对T中的每个结点进编号,编号值为12…n且有如下性质:T中任一结点V,其编号等于左子树上的最小编号减1,而V的右子树的结点中,其最小编号等于V右子树上结点的最大编号加1。这时按B编号。A.中序遍历序列B.前序遍历序列C后序遍历序列D.层次遍历序列35在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的B倍。A.1/2B.1c.2D.436对于一个具有n个顶点和e条边的无向图,若采用邻接表表示则表头向量的大小为A_。AnB.n+1C.n-1Dn+e37具有n个顶点的无向完全图,边的总数为D条。A.n-1BD.n*(n-1》239最小代价生成树D。A是唯一的B不是唯一的C唯一性不确定D唯一性与原图边的权值有关40在无向图G的邻接矩阵A中,若A等于1,则A[等于cAi+jBi-jC1D04已知一个有序表为(12、18、24、35、47、50、62、83、9015、134),当二分查找值为90的元素时,B次比较后查找成功;当二分查找值为47的元素时,D次比较后查找成功A.1B.2C.3D.443散列函数有一个共同性质,即函数值应当以D取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率44设散列地址空间为0~m-1k为关键字,用p去除k,将所得的余数作为k的散列地址,即H(k)=k%p。为了减少发生冲突的频率一般取p为DA.小于m的最大奇数B.小于m的最大偶数C.mD.小于m的最大素数48.一组记录排序码为(46、79、56、38、40、84),则利用堆排序的方法建立的初始堆为_B_。A.(79、46、56、38、40、80)B.(84、79、56、38、40、46C.(84、79、56、46、40、38)D.(84、56、79、40、46、38)49.一组记录的关键码为(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、7950在平均情况下快速排序的时间复杂性为C,空间复杂性为_B_;在最坏情况下(如初始记录已有序),快速排序的时间复杂性为D,空间复杂性为A。Ao(n)Bo(log2n)Co(nlog2n)Do(n2)P276填空题3.一个数据结构用二元组表示时,它包括[11数据元素的集合K和K上[2]二元关系的集合R。·5对于顺序存储的线性表,当随机插入或删除一个元素时,约需平均移动表长「11一