云南开放大学数据结构网上作业8

一、单项选择题(共15题,共100分)
第1 题（7分）：
对线性表进行二分查找时，要求线性表必须(     )
A.以顺序方式存储     B.以顺序方式存储，且结点按关键字值有序排列
C.以链接方式存储     D.以链接方式存储，且结点按关键字值有序排列
正确答案: B
第2 题（7分）：
用二分查找法查找具有n个结点的顺序表时，查找每个结点的平均比较次数是(    )
A.O(n2)       B.O(nlog2n)       C.O(n)        D.O(log2n)
正确答案: D
第3 题（7分）：
对长度为4的顺序表进行查找，若查找第一个记录的概率为1/24, 查找第二个记录的概率为1/6, 查找第三个记录的概率为2/3, 查找第四个记录的概率为1/8,则查找任意一个记录的平均查找长度为(     )
A.23/8        B.20/8           C.17/8        D.14/8
正确答案: A
第4 题（7分）：
若有一个长度为64的有序表，现用二分查找方法查找某一记录，则查找不成功，最多需要比较(      )次。
A.9           B.7              C.5           D.3
正确答案: B
第5 题（7分）：
当采用分块查找时，数据的组织方式为(     )
A.数据必须有序
B.数据不必有序
C.数据分成若干块，每块内数据不必有序，但块间必须有序
D.数据分成若干块，每块内数据必须有序，但块间不必有序
正确答案: C
第6 题（7分）：
一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该平衡二叉树共有(    )个结点。
A.2k-1-1        B.2k-1+1           C.2k-1        D.2k+1
正确答案: C
第7 题（7分）：
具有5层结点的平衡二叉树至少有(       )个结点。
A.10           B.12             C.15          D.17
正确答案: B
第8 题（7分）：
若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为(      )
A.顺序存储结构   B.链式存储结构   C.索引存储结构   D.散列存储结构
正确答案: D
第9 题（7分）：
以下有关m阶B-树的叙述中，错误的是(     )。
A.根结点至多有m棵子树        B.每个结点至少有棵子树
C.所有叶子结点都在同一层上    D.每个结点至多有m-1个关键字
正确答案: B
第10 题（7分）：
哈希表的地址区间为0～17，哈希函数为h(key)=K%17。采用线性探测法处理冲突，并将关键字序列{26，25，72，38，8，18,59}依次存储到哈希表中，则在哈希表中查找元素59需要搜索的次数为(    )。
A.2             B.3             C.4           D.5
正确答案: C
第11 题（6分）：
对长度为n的线性表进行顺序查找，在等概率情况下，平均查找长度为（     ）。
A．n          B．（n+1）/2         C．2n             D．n-1
正确答案: B
第12 题（6分）：
线性表只要以（    ）方式存储就能进行折半查找。
A．链接         B．顺序          C．关键字有序的顺序     D．二叉树
正确答案: C
第13 题（6分）：
散列查找的原理是（     ）。
A．在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系
B．按待查记录的关键字有序的顺序方式存储
C．按关键字值的比较进行查找
D．基于二分查找的方法
正确答案: A
第14 题（6分）：
有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（    ）。
A．31/10     B．29/10          C．26/10      D．29/9
正确答案: B
第15 题（6分）：
在有序表{2，4，7，14，34，43，47，64，75，80，90，97，120}中，用折半查找法查找值80时，经（       ）次比较后查找成功。
A．2           B．3        C．4        D．5
正确答案: B