还剩14页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构考试内部题库含答案解析(全考点)一个元素和删除第一个元素,则采用存储方式最节省运若某线性表中最常用的操作是在最后一个元素之后插入
1.算时间・单链表•A:・:仅有头指针的单循环链表•B・:双链表•C・:仅有尾指针的单循环链表•D解析选项、单链表插入最后一个元素需要遍历链表到最后一个A元素选项、仅有头指针,删除第一个元素方便,但是末B尾插入一个元素同选项选项、双链表,方便来回遍历A C但是末尾插入一个元素依旧需要遍历整个链表选项、最D节约运算时间答案D、设某链表中最常用的操作是在链表的尾部插入或删除元素,2则选用下列—存储方式最节省运算时间・单向链表A:画出查找过程中构成的判定树,让最小的分支高度对应于最少的比较次数,让最大的分支高度对应于最多的比较次数,出现类似于长度为的顺序表时,判定树刚好是一棵满树,15此时最多比较次数与最少比较次数相等答案A,B具有个关键字的有序表中,对每个关键字的直找概率相
4.12同,折半杳找算法杳找成功的平均查找长度为,折半蛰找蛰找失败的平均杳找长度为・•A:37/12・•B:35/12・•C:39/13・•D:49/13解析假设有序表中元素为,不难画出对它进行折半查找A[0…11]的判定树如下图所示,圆圈是查找成功结点,方形是虚构的查找失败结点从而可以求出查找成功的ASL=1+22+34查找失败的+45/12=37/12,ASL=33+4*10/13=49/13O答案A,D、对有个记录的索引顺序表分块表进行查找,最理想52500的块长为・•A:50・•B:125・•C:
500..D Rog22500]解析设块长为索引表包含项,索引表的b,n/b块内的纵二索引ASL=n/b+l/2,ASL=b+l/2,ASL表的块内的其中对于ASL+ASL=b n/b+2/2,b+n/b,,由均值不等式知时有最小值此时则最理想块长为b=n/b‘250°=50答案A、设顺序存储的某线性表共有个元素,按分块查找的要6123,求等分为块若对索引表采用顺序直找法来确定子块,3且在确定的子块中也采用顺序杳找法,则在等概率情况下,分块查找成功的平均杳找长度为()O•A:21•B:23•C:41•D:62解析6+12)根据公式ASL=‘2+s=+\frac{s+l{2}S+1$2+2s+7122s二,其中二代入不b=n/s,s123/3,n=123难得出为.故选ASL23Bo答案B
7、为提高查找效率,对有65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素最多需要执行()次关键字比较・•A:10•C:16•D:21解析为使查找效率最高,每个索引块的大小应是,为每个块建立索引,则索引表中索引项的个V UU4U=255数为若对索引项和索引块内部都采用折半查找,则查找255效率最高,为og2255+1「几32255+1「屋答案C、在有个元素的升序数组中查找关键字查8nn1000A x,找算法的伪代码如下所示且且㊀k=0;whil kn A[k]x k=k+3;ifkn A查找成功;〈且㊀㊀[k]==x Is if k-l nA[k-1]==x查找成功;且查找成功;㊀㊀Isifk-2nA[k-2]==x查找失败;㊀㊀Is本算法与折半算法相比,有可能具有更少比较次数的情形是()・・当不在数组中A:x・当接近数组开头处•B:x・当接近数组结尾处•C:x・:当位于数组中间位置•D x解析答案B、设某链表中最常用操作是再链表尾部插入或删除元素,则9选用下列一存储方式最节省运算时间・:单项链表•A・:单向循环链表•B・双向链表•C::双向循环链表•D解析在链尾的末尾插入和删除一个结点时,需要修改其相邻结点的指针域而从头寻找尾结点及尾结点的前驱结点时,双向循环链表用时最少答案D在单链表中,若节点不是尾节点,在其后插入节点的
10.p S操作是—O・•A:s-next=p;p-next=s;・•B:s-next=p-next;p-next=s;・•C:s-next=p-next;p=s;・•D:p-next=s;s-next=p;解析)先要将节点的指向之后的节点(二,s next p s-nextp-next)然后将节点的指向《p nextp-next=so答案B・:单向循环链表•B・双向链表•C:・:双向循环链表•D解析某链表中最常用的操作是在链表的尾部插入或删除元素时双向循环列表最节省运算时间答案D、在含有个结点的二叉排序树中杳找某个关键字的结点时,3n最多进行次比较・•A:n/
2..B10g2log n+leC2・•D:n解析当输入序列是一个有序序列时,构造的二叉排序树是一个单支树,当查找一个不存在的关键字值或最后一个结点的关键字值时,需要次比较n答案D、含有个结点的平衡二叉树的最大深度为()420・•A:4・•B:5・•C:6・•D:7解析ni平衡二叉树结点数的递推公式为=1,=l,Ho Tlh72/7-1Tlh-2但…n〃〃(为平衡二叉树:2,=l+Z h高度,为构造此高度的平衡二叉树所需的最少结点数)通过递推公式可得,构造层平衡二叉树至少需要个结点,构512造层至少需要个结点620答案C、具有层结点的至少有()个结点55AVL・•A:10・•B:12•C:15•D:17解析Tlh设”表示高度为的平衡二叉树中含有的最少结点h一一九八九九12n/-i nh-oz数,则有乙=2,二几I,71斗由此求出,对应的如下图所示°=12AVL答案B、下列关于红黑树的说法中,不正确的是6一棵含有个结点的红黑树的高度至多为•A:n2log n+12:如果一个结点是红色的,则它的父结点和孩子结•B点都是黑色的:从一个结点到其子孙结点的所有路径上包含相同数•C量的黑结点・红黑树的查询效率一般要优于含有相同结点数的.D:树AVL解析选项、和都是红黑树的性质是高度平衡的二A BC AVL叉查找树,红黑树是适度平衡的二叉查找树,从这一点可以看出的查找效率往往更优AVL答案D、下列关于红黑树和树的描述中,不正确的是()7AVLo:两者都属于自平衡的二叉树•A:两者查找、插入、删除的时间复杂度都相同•B红黑树插入和删除过程至多有次旋转操作•C:2:红黑树的任一结点的左右子树高度之差不超过倍•D2解析自平衡的二叉排序树是指在插入和删除时能自动调整以保持其所定义的平衡性,红黑树和都属于自平衡二叉树,AVL A正确在红黑树中删除结点时,情况可能变为情况、或,情况12324会变为情况可能会出现旋转次数超过次的情况,故错3,2C误答案C)、下列关于红黑树的说法中,正确的是(8o:红黑树是一种特殊的平衡二叉树•A:如果红黑树的所有结点都是黑色的,那么它一定是一•B棵满二叉树:红黑树的任何一个分支结点都有两个非空孩子结点•C红黑树的子树也一定是红黑树•D:解析答案B、将关键字一次插入初始为空的红黑树91,23,4,5,6,7T,则中红结点的个数是()T关键字一次插入红黑树后的形态变化如下图所1,2,3,4,5,6,7示答案C将关键字一次插入初始为空的红黑树,则
10.5,4,3,2,1T的最终形态是()T解析关键字—次插入红黑树后的形态变化如下,5,4,3,2,1答案D、由介数据元素组成的两个表一个递增有序,一个无序1n采用顺序查找算法,对有序表从头开始查找,发现当前元素已不小于待杳元素时,停止直找,确定直找不成功,已知直找任一元素的概率是相同的,则在两种表中成功蛰找()・平均时间后者小•A:・:平均时间两者相同•B・:平均时间前者小•C・无法确定•D:解析对于顺序查找,不管线性表是有序的还是无序的,成功查找一个元素的比较次数为,成功查找第二个元素的比较次数为12,以此类推,即每个元素查找成功的比较次数只与其位置有关(与是否有序无关),因此查找成功的平均时间两者相同答案B]
2、在有11个元素的有序表A0,2,…,11中进行折半杳找()I low+high/2I w.](L13川」),查找元素AQl时,被比较的元素依次是()•A:6,8,10,11•B:6,9,10,11•C:6,7,9,11•D:6,8,9,11解析依据折半查找的思想,第一次mid=1+6+11]/2第三次二=9,mid[(1+11)/21=6,第二次mid1+9+11]/2第四次=10mid=llo答案B、已知一个长度为的顺序表其元素按关键字有序排列,316若采用折半查找算法杳找一个不存在的元素,则比较的次数至少是(),至多是()•A:4•B:5•C:6•D:7解析。