查找。一、 选择题。
1. 对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )
a．（n+1）/2 b. n/2 c. n d. [1+n）*n ]/2
2. 下面关于二分查找的叙述正确的是 (
a. 表必须有序，表可以顺序方式存储，也可以链表方式存储
c. 表必须有序，而且只能从小到大排列。
b. 表必须有序且表中数据必须是整型，实型或字符型
d. 表必须有序，且表只能以顺序方式存储。
3. 既希望较快的查找又便于线性表动态变化的查找方法是 (
a．顺序查找 b. 折半查找 c. 索引顺序查找 d. 哈希法查找。
4. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为a,并已知a的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( )型调整以使其平衡。
a. llb. lrc. rld. rr
5．下列关于m阶b-树的说法错误的是。
a．根结点至多有m棵子树
b．所有叶子都在同一层次上。
c. 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树
d. 根结点中的数据是有序的。
6. 下面关于m阶b-树说法正确的是( )
①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字；
③所有叶子在同一层上当插入一个数据项引起b树结点**后，树长高一层。
abcd. ③
7. 下面关于b和b+树的叙述中，不正确的是( )
a. b树和b+树都是平衡的多叉树。 b. b树和b+树都可用于文件的索引结构。
c. b树和b+树都能有效地支持顺序检索。 d. b树和b+树都能有效地支持随机检索。
8. m阶b-树是一棵。
a. m叉排序树 b. m叉平衡排序树 c. m-1叉平衡排序树 d. m+1叉平衡排序树。
9. 下面关于哈希(hash，杂凑)查找的说法正确的是。
a．哈希函数构造的越复杂越好，因为这样随机性好，冲突小
b．除留余数法是所有哈希函数中最好的
c．不存在特别好与坏的哈希函数，要视情况而定。
d．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可。
10. 若采用链地址法解决冲突，散列函数为h（key）=key mod 17，则需 (（1）) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2
1） a．17b. 13c. 16d. 任意。
2） a．0至17 b. 1至17 c. 0至16 d. 1至16
11. 设哈希表长为14，哈希函数是h(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
a．8 b．3 c．5 d．9
12. 将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。
a. 一定会b. 一定不会 c. 仍可能会。
二、综合。1. 设有一组关键字，采用哈希函数：
h（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法hi=(h(key)+di) mod 10解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
2. 依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵平衡二叉排序树，写出调整过程，对该二叉排序树作中序遍历，试写出遍历序列；
(3) 假定每个元素的查找概率相等，试计算该平衡二叉树的平均查找长度。
三、算法。1.折半查找算法的实现。
练习题答案
15日经典诵读练习题。1 空山新雨后，天气晚来秋。泥融飞燕子，清泉石上流。这首诗的题目是 山居秋暝 作者是唐代的王维。2 合抱之木，生于毫末 九层之台，起于累土 千里之行，始于足下。这句话选自 老子 3 生当作人杰，死亦为鬼雄。至今思项羽，不肯过江东。4 羊跪乳，鸦反哺，人之情，孝父母。父母教，须敬...
练习题答案
第三章参 2 按语音特征用国际音标注出相应的音素 1 双唇浊鼻音 m 2 舌尖前清擦音 s 3 舌面后送气清塞音 k 4 后低不圆唇元音 5 前半高不圆唇元音 e 6 后半低圆唇元音。3 描写下列音素的语音特征 1 舌面前清擦音 2 t 舌尖后送气清塞擦音 3 l 舌尖前浊边音。4 后半高不圆唇元音...
练习题答案
单选aadab，ccbbb，bb 多选bde，ab，ace，acd，bc，bd，abcd，abcd，abc，abc 判断fftff，ftfft 案例。1交货品质违约，卖方负责赔偿。2仲裁理由成立。卖方不能既用说明又用样品两种方法来约定商品品质，否则均要遵守。此外，样品应妥善保存。3 查阅教材469页...