Ch9查
一、单项选择题
1．顺序查法适合于存储结构为B的线性表..
A．散列存储        B．顺序存储或链接存储      C．压缩存储        D．索引存储
2．对线性表进行二分查时;要求线性表必须C..
A．以顺序方式存储      B．以链接方式存储
C．以顺序方式存储;且结点按关键字有序排序      D．以链接方式存储;且结点按关键字有序排序
3．采用顺序查方法查长度为n的线性表时;每个元素的平均查长度为C..
A．n        B．n/2        C．n+1/2      D．n-1/2
4． 采用二分查方法查长度为n的线性表时;每个元素的平均查长度为D..
A．On2      B． Onlog2n      C．On      D．Olog2n
5．二分查和二叉排序树的时间性能B..
A．相同        B．不相同
就平均时间性能而言;二叉排序树上的查和二分查差不多..
就维护表的有序性而言;二叉排序树无须移动结点;只需修改指针即可完成插入和删除操作;且其平均的执行时间均为Olog2n;因此更有效..二分查所涉及的有序表是一个向量;若有插入和删除结点的操作;则维护表的有序性所花的代价是On..当有序表是静态查表时;宜用向量作为其存储结构;而采用二分查实现其查操作；若有序表里动态查表;则应选择二叉排序树作为其存储结构..
6．有一个有序表为{1;3;9;12;32;41;45;62;75;77;82;95;100};当二分查值82为的结点时;C次比较后查成功..
A．1    B．2    C．4      D．8
7．有一个长度为12的有序表;按二分查法对该表进行查;在表内各元素等概率情况下查成功所需的平均比较次数为B..
A．35/12        B．37/12        C．39/12        D．43/12
8．根据一组记录  56; 42; 50; 64; 48  依次插入结点生成一棵AVL树高度平衡的二叉搜索树时;当插入到值为 50 的结点时需要进行旋转调整..
9．向一棵二叉搜索树中插入一个新元素时;若该新元素的值大于根结点的值;则应把它插入到根结点 右子树上..
10．根据一组记录  56; 42; 73; 50; 64; 48; 22  依次插入结点生成一棵AVL树高度平衡的二叉搜索树时;当插入到值为 48 的结点时才出现不平衡;需要进行旋转调整..
11．以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素时;其时间复杂度为 On ..
12．在一棵AVL树高度平衡的二叉搜索树中;每个结点的左子树高度与右子树高度之差的绝对值不超过 1 ..
13．在线性表的散列存储中;装载因子 a 又称为装载系数;若用m表示散列表的长度;n表示待散列存储的元素的个数;则 a 等于 n/m ..
14．以折半搜索方法从长度为n的有序表中搜索一个元素时;时间复杂度为 Olog2n..
15．假定一个顺序表的长度为40;并假定搜索每个元素的概率都相同;则在搜索成功情况下的平均搜索长度为 20.5 ..
16．假定要对长度n = 100的线性表进行散列存储;并采用开散列法处理冲突;则对于长度m = 20的散列表;每个散列地址的同义词子表单链表的长度平均为 5 ..
17．假定对长度n = 50的有序表进行折半搜索;则对应的判定树中最后一层的结点数为 19 个..
1 2 4 8 16 19
18．根据n个元素建立一棵二叉搜索树二叉排序树的时间复杂度性大致为 Onlog2n ..
19．从一棵二叉搜索树中搜索一个元素时;若给定值小于根结点的值;则需要向 左子树 继续搜
索..
20．假定一个线性表为 ”abcd”; ”baabd”; ”bcef”; ”cfg”; ”ahij”; ”bkwte”; ”ccdt”; ”aayb”;若按照字符串的第一个字母进行划分;使得第一个字母相同的字符串被划分在一个子表中;则得到的以a为第一个字母的子表长度 3 ..
21．假设在有序线性表A1．．20上进行二分查;则比较一次查成功的结点数为1;则比较二次查成功的结点数为2;则比较三次查成功的结点数为4;则比较四次查成功的结点数为8;则比较五次查成功的结点数为5;平均查长度为3．7..
22．对于长度为n的线性表;若进行顺序查;则时间复杂度为On；若采用二分法查;则时间复杂度为Olog2n ..
23、  对长度为3的顺序表进行搜索;若搜索第一个元素的概率为1/2;搜索第二个元素的概率为1/3;搜索第三个元素的概率为1/6;则搜索到表中任一元素的平均搜索长度为 A ..
A．5/3  B．2  C．7/3  D．4/3
1/23+1/32+1/61=9/6+4/6+1/6=7/3
1/21+1/32+1/63=3/6+4/6+3/6=5/3
24、  向一棵AVL树高度平衡的二叉搜索树插入元素时;可能引起对最小不平衡子树的双向旋转的调整过程;此时需要修改相关字符串是什么数据结构 C 个结点指针域的值..
A．2    B．3    C．4    D．5
25、  向一棵AVL树高度平衡的二叉搜索树插入元素时;可能引起对最小不平衡子树的调整过程;此调整分为 C种旋转类型..
A．2    B．3    C．4    D．5
26、  向一棵AVL树高度平衡的二叉搜索树插入元素时;可能引起对最小不平衡子树的左单或右单旋转的调整过程;此时需要修改相关 C个结点指针域的值..
A．2    B．3    C．4    D．5
三、判断题：
1．×对二叉搜索树进行前序遍历得到的结点序列是一个有序序列..
2．√折半搜索所对应的判定树;既是一棵二叉搜索树;又是一棵理想平衡二叉树它的特点是除最底层结点外其他各层结点数都是满的;最底层的若干结点可能散布在该层各处..
3．√装载因子是散列表的一个重要参数;它反映了散列表的装满程度..
4．√对于两棵具有相同记录集合而具有不同结构的二叉搜索树;按中序遍历得到的结点序列是相同的..

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。