数据结构(C语言版) 第9章 查找

则表明查找不成功，返回“空指针”;
12.10.2020
18
在 Trie 树中的插入
查找,得到插入位置
插入一个叶子结点
12.10.2020
2
例如:
表示关键字集合
{HAD, HAS, HAVE, HE, HER, HERE, HIGH, HIS }
H
A
E
I
DSV$R
GS
$ $E
$ EH$
$
12.10.2020
$$ 3
1. 键树的结构特点：
1. 关键字中的各个符号分布在从根结点到叶的 路径上；
2. 叶结点内的符号为“结束”的标志符；
p=p->first; i++; 若 ( p && p->symbol != K.ch[i] ) 则继续在键树的同一层上进行查找 p=p->next;
若 ( p == NULL) 则表明查找不成功，返回“空指针”; 若 ( p && p->symbol==K.ch[i] && i==K.num-1) 则12.查10.20找20 成功，返回指向相应记录的指针 p->info1p0 tr
T
分支结点
H
A
叶子结点 D
E
$ … $
HAD
HE
R
$
G H
I S
含关键字 的记录HERFra bibliotekE $
$ HIGH
$ HIS
12.10.2020
HERE
6
结点结构:
分支结点
first symbol next
叶子结点 infoptr symbol next

数据结构（C语言版）9-12章练习答案清华大学出版社9-12章数据结构作业答案第九章查找选择题1、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/2 2. 下面关于二分查找的叙述正确的是 ( D )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储3. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A)个链表。

这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C) （1） A．17 B. 13 C. 16 D. 任意（2） A．0至17 B. 1至17 C. 0至16 D. 1至16判断题1．Hash表的平均查找长度与处理冲突的方法无关。

(错) 2. 若散列表的负载因子α<1，则可避免碰撞的产生。

（错）3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。

（错）填空题1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为 4 .算法应用题1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。

要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

进行比较。 如果找到一个记录,有：
k=elem [i].key, (0≤i≤n)，则停止比较。
如果 i>0,则查找成功；否则,查找失败。
输入：查找表ST，查找条件（关键字）k
输出：成功时：记录序号，失败时：0
int sequsearch(SSTable ST,keytype k)
{
int i=ST.length； //从第n个记录开始查找
折半查找算法2
int binsrch(SSTable ST,keytype k) {int low,mid,hig；
low=1； hig=ST.length；
while (low<=high)
{ mid=(low+high)/2；
if (k<ST.elem [mid].key) hig=mid-1；//查左子表
break；
//查找成功,退出循环
else low=mid+1； //查右子表
｝
if (ST.elem[mid].key==k)
{ printf("success\n”)； return mid；
} else
{ printf("fail\n”)； return 0；
} }
//查找成功 //查找失败
n=15,满二叉树
2 5 8 10 12
n=12,非满二叉树
➢结点内的数据表示数据元素的序号（如例中表示有15个元素组成 的有序表的判定树）
➢根结点表示首先要和关键字k进行比较的数据元素的序号（如8）， 比较相等时，查找成功，否则，当k小于根结点对应元素的关键字 时，下步就和左子结点（如序号4）对应元素的关键字比较，否则， 下步就和右子结点（如序号12）对应元素的关键字比较。

第九章查找一、选择题1。

若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A． (n—1)/2 B. n/2 C。

（n+1）/2 D。

n2. 下面关于二分查找的叙述正确的是（ )A。

表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B。

表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储3. 用二分(对半）查找表的元素的速度比用顺序法（ )A．必然快 B. 必然慢 C. 相等 D. 不能确定4. 具有12个关键字的有序表，折半查找的平均查找长度( ）A. 3。

1 B。

4 C. 2。

5 D. 55．当采用分块查找时,数据的组织方式为 ( ）A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序,但块间必须有序，每块内最大(或最小）的数据组成索引块C。

数据分成若干块，每块内数据有序，每块内最大(或最小）的数据组成索引块D. 数据分成若干块,每块（除最后一块外)中数据个数需相同6。

二叉查找树的查找效率与二叉树的( （1）)有关, 在（（2）)时其查找效率最低（1）: A。

高度 B。

结点的多少 C. 树型 D. 结点的位置(2）: A。

结点太多 B. 完全二叉树 C。

呈单枝树 D. 结点太复杂。

7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败，它们的平均查找长度是((1）） ,对于查找成功，他们的平均查找长度是（（2））供选择的答案：A。

相同的 B。

不同的9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）A．(100,80， 90， 60， 120，110，130） B。

（100，120，110,130，80， 60, 90) C。

（100，60, 80， 90, 120，110，130） D。