美文网首页
数据结构错题收录(十七)

数据结构错题收录(十七)

作者: 程序员丶星霖 | 来源:发表于2022-11-30 09:10 被阅读0次

    1、由n个数据元素组成的两个表:一个递增有序,一个无序。采用顺序查找算法,对有序表从头开始查找,发现当前元素已不小于待查元素时,停止查找,确定查找不成功,已知查找任一元素的概率是相同的,则在两种表中成功查找()。

    • A:平均时间后者小
    • B:平均时间两者相同
    • C:平均时间前者小
    • D:无法确定
    解析

    对于顺序查找,不管线性表是有序的还是无序的,成功查找一个元素的比较次数为1,成功查找第二个元素的比较次数为2,以此类推,即每个元素查找成功的比较次数只与其位置有关(与是否有序无关),因此查找成功的平均时间两者相同。

    答案:B

    2、在有11个元素的有序表A[1,2,...,11]中进行折半查找(\lfloor {(low+high)/2} \rfloor),查找元素A[11]时,被比较的元素依次是()。

    • A:6,8,10,11
    • B:6,9,10,11
    • C:6,7,9,11
    • D:6,8,9,11
    解析

    依据折半查找的思想,第一次mid=\lfloor (1+11)/2 \rfloor=6,第二次mid=\lfloor [(1+6)+11]/2 \rfloor=9,第三次mid=\lfloor [(1+9)+11]/2 \rfloor=10,第四次mid=11。

    答案:B

    3、已知一个长度为16的顺序表,其元素按关键字有序排列,若采用折半查找算法查找一个不存在的元素,则比较的次数至少是(),至多是()。

    • A:4
    • B:5
    • C:6
    • D:7
    解析

    画出查找过程中构成的判定树,让最小的分支高度对应于最少的比较次数,让最大的分支高度对应于最多的比较次数,出现类似于长度为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/13。

    在这里插入图片描述
    答案:A,D

    5、对有2500个记录的索引顺序表(分块表)进行查找,最理想的块长为()。

    • A:50
    • B:125
    • C:500
    • D:\lceil log_2{2500}\rceil
    解析

    设块长为b,索引表包含n/b项,索引表的ASL=(n/b+1)/2,块内的ASL=(b+1)/2,纵ASL=索引表的ASL+块内的ASL=(b
    n/b+2)/2,其中对于b+n/b,由均值不等式知b=n/b时有最小值,此时b=\sqrt{n}。则最理想块长为\sqrt{2500}=50。

    答案:A

    6、设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块,若对索引表采用顺序查找法来确定子块,且在确定的子块中也采用顺序查找法,则在等概率情况下,分块查找成功的平均查找长度为()。

    • A:21
    • B:23
    • C:41
    • D:62
    解析

    根据公式ASL=L_i+L_s=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s},其中b=n/s,s=123/3,n=123,代入不难得出ASL为23.故选B。

    答案:B

    7、为提高查找效率,对有65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素最多需要执行()次关键字比较。

    • A:10
    • B:14
    • C:16
    • D:21
    解析

    为使查找效率最高,每个索引块的大小应是\sqrt{65025}=255,为每个块建立索引,则索引表中索引项的个数为255。若对索引项和索引块内部都采用折半查找,则查找效率最高,为\lceil log_2{(255+1)} \rceil+\lceil log_2{(255+1)} \rceil=16。

    答案:C

    8、在有n(n>1000)个元素的升序数组A中查找关键字x,查找算法的伪代码如下所示。

    k=0;
    while(k<n 且 A[k]<x)  k=k+3;
    if(k<n 且A[k]==x) 查找成功;
    else if(k-1<n 且 A[k-1]==x) 查找成功;
        else if(k-2<n 且 A[k-2]==x) 查找成功;
            else 查找失败;
    

    本算法与折半算法相比,有可能具有更少比较次数的情形是()。

    • A:当x不在数组中
    • B:当x接近数组开头处
    • C:当x接近数组结尾处
    • D:当x位于数组中间位置
    解析
    答案:B

    9、设某链表中最常用操作是再链表尾部插入或删除元素,则选用下列____存储方式最节省运算时间。

    • A:单项链表
    • B:单向循环链表
    • C:双向链表
    • D:双向循环链表
    解析

    在链尾的末尾插入和删除一个结点时,需要修改其相邻结点的指针域。而从头寻找尾结点及尾结点的前驱结点时,双向循环链表用时最少。

    答案:D

    10、在单链表中,若p节点不是尾节点,在其后插入S节点的操作是____。

    • 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->next = p->next),然后将p节点的next指向s(p->next=s)。

    答案:B

    学海无涯苦作舟

    相关文章

      网友评论

          本文标题:数据结构错题收录(十七)

          本文链接:https://www.haomeiwen.com/subject/aqwjfdtx.html