数据结构查找练习题及答案
一 选择题
1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为(C )。
A． (n-1)/2 B. n/2 C. (n+1)/2 D. n
2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )
A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2
3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（D）,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（C）。 在此假定N为线性表中结点数，且每次查找都是成功的。
A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N2
4. 下面关于二分查找的叙述正确的是 ( D )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序且表中数据必须是整型，实型或字符型
C. 表必须有序，而且只能从小到大排列
D. 表必须有序，且表只能以顺序方式存储
5. 用二分（对半）查找表的元素的速度比用顺序法( D )
A． 必然快 B. 必然慢 C. 相等 D. 不能确定
6. 具有12个关键字的有序表，二分查找的平均查找长度（ A ）
A. 3.1 B. 4 C. 2.5 D. 5
7. 二分法查找的时间复杂性为（ D ）。
A. O（n2） B. O（n） C. O（nlogn） D. O（logn）
8．当采用分快查找时，数据的组织方式为 ( B )
A．数据分成若干块，每块内数据有序
B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
9. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ D ）个记录。
A．1 B．2 C．3 D.4
10. 下面关于哈希(Hash，杂凑)查找的说法正确的是( C )
A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B．除留余数法是所有哈希函数中最好的
C．不存在特别好与坏的哈希函数，要视情况而定
D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
11. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (A) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (C)
（1） A．17 B. 13 C. 16 D. 任意
（2） A．0至17 B. 1至17 C. 0至16 D. 1至16
二、判断题
1．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（ √ ）
2．在散列(哈希)检索中，“比较”操作一般也是不可避免的。（ √ ）
3．哈希函数越复杂越好，因为这样随机性好，冲突概率小. （ × ）
4．哈希函数的选取平方取中法最好。 （ × ）
5．Hash表的平均查找长度与处理冲突的方法无关。 （ × ）
6．负载因子 (装填因子)是哈希表的一个重要参数，它反映哈希表的装满程度。（ √ ）
7. 哈希法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。（ √ ）
8. 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。 （ × ）
9．查找相同结点的效率二分查找总比顺序查找高。 （ × ）
10．用数组和单链表表示的有序表均可使用二分查找方法来提高查找速度。 （ × ）
11. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ √ ）
12. 顺序查找法适用于存储结构为顺序或链接存储的线性表。 （ √ ）
13. 二分查找法的查找速度一定比顺序查找法快 。（ × ）
14. 就平均查找长度而言，分块查找最小，二分查找次之，顺序查找最大。（ × ）
15．对无序表用二分法查找比顺序查找快。（× ）
三、填空
1. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为n次；当使用监视哨时，若查找失败，则比较关键字的次数为n+1。
2. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为4.
3．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为6,9,11,12。
4. 在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是5
5. 高度为4的3阶b-树中，最多有26（第4层是叶子结点，每个结点两个关键字）个关键字。
6. 在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是1,3,6,8,11,13,16,19
7. 给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为5 ，带权路径长度WPL的值为96。
8. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需2次查找成功，47时4成功，查100时，需3次才能确定不成功。
9．哈希表是通过将查找码按选定的哈希函数和解决冲突的方法，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是选择好的哈希函数和处理冲突的方法。一个好的哈希函数其转换地址应尽可能均匀，而且函数运算应尽可能简单。
四、应用题
1．名词解释：
哈希表：
同义词：
答：概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答略。
2. 回答问题并填空
（1）哈希表存储的基本思想是什么？
答：散列表存储的基本思想是用关键字的值决定数据元素的存储地址
（2）哈希表存储中解决冲突的基本方法有哪些？其基本思想是什么？
答：散列表存储中解决碰撞的基本方法：
① 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种：
a．di =1，2，…，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。
b．di =12，-12，22，-22，… ，k2（k≤m/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。
c．di =伪随机数序列，称为随机探测再散列。
② 再散列法 Hi=RHi（key） i=1，2，…，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。
③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。
④ 建立公共溢出区 设H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出区 O[0..m-1]。
3. 如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出三种解决冲突的方法。
答：评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法见上面2题。
4．HASH方法的平均查找路长决定于什么？ 是否与结点个数N有关？ 处理冲突的方法主要有哪些？
答：哈希方法的平均查找路长主要取决于负载因子（表中实有元素数与表长之比），它反映了哈希表的装满程度，该值一般取0.65~0.9。解决冲突方法见上面2题。
5．在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？
答：不一定相邻。哈希地址为i（0≤i≤m-1）的关键字，和为解决冲突形成的探测序列i的同义词，都争夺哈希地址i。
五、算法设计题
1．在用除余法作为散列函数、线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不致于断裂。
答：[题目分析]首先计算关键字的散列地址，若该地址为空，则空操作；若该地址有关键字，但与给定值不等，则用解决冲突的方法去查找给定值；若该地址有关键字且与给定值相等，则实行删除。题目要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不断裂。由于用线性探测解决冲突，设被删除元素的散列地址为i，则其余m-1（m为表长）个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到i才能结束。为了提高算法效率，减少数据移动，应将最后一个同义词前移填充被删除关键字。
void HsDelete（rectype HS[]，K）
//在以除余法为散列函数、线性探测解决冲突的散列表HS中，删除关键字K
{i=K % P； // 以造表所用的除余法计算关键字K的散列地址
if（HS[i]==null）{printf（“散列表中无被删关键字”）；exit（0）；}
// 此处null代表散列表初始化时的空值
switch
{case HS[i]==K：del(HS，i，i，K)；break；
case HS[i]!=K：di=1；j=(i+ di)%m； // m为 表长
while（HS[j]!=null && HS[j]!=K && j!=i）// 查找关键字K
{di=di+1；
j=(i+di)%m； }// m为 表长
if（HS[j]==K）del(HS，i，j，K)；
else {printf（“散列表中无被删关键字”）；exit（0）;}
}// switch
}算法结束
void del（rectype HS[]，in i，int j，rectype K）
//在散列表HS中，删除关键字K，K的散列地址是i，因解决冲突而将其物理地置于表中j。算法查找关键字K的同义词，将其最后一个同义词移到位置j，并将其同义词的位置置空。
{di=1；last=j；x=(j+di)% m；// 探测地址序列，last记K的最后一个同义词的位置
while（x!=i） //可能要探测一圈
{if（HS[x]==null）break； // 探测到空位置，结束探测
else if（HS[x]%P==i）last=x；// 关键字K的同义词
di=di+1；x=(j+di) % m； // 取下一地址探测
}
HS[j]=HS[last]; HS[last]=null; //将哈希地址last的关键字移到哈希地址j
}
[算法讨论] 由于用线性探测解决冲突，可能发生“二次聚集”（两个第一哈希地址不同的记录争夺同一后继哈希地址）。象上面这样处理后，对于哈希地址为i的记录没有问题了，但由于将地址j置空，有可能截断了其它记录的探测通路。最明显的是哈希地址为j的记录就查不到了。解决的办法是继续调整，直到当前哈希表中的每个记录的查找都是正确的为止。这里不再深入讨论。
2．设排序二叉树中结点的结构为下述三个域构成:
data: 给出结点数据的值；left: 给出本结点的左儿子结点的地址；right: 给出本结点的右儿子结点的地址
设data 域为正整数，该二叉树树根结点地址为T。 现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除掉。
答：[题目分析]利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于x，则顺左子树向下查找，直到某结点的值小于等于x，则该结点及其左子树均应删除。下面设计一查找算法，确定被删除子树的根结点，再设计一删除算法，删除以被删结点为根的子树。
typedef struct node
{int data； struct node *left，*right;
}BiTNode，*BSTree；
void DelTree(BSTree r）
//非递归删除以r为根的二叉排序树
{BSTree S[]；// 栈，容量足够大，栈中元素是二叉排序树结点的指针
top=0；
while （r!=null || top>0）
{while（r!=null） // 沿左分枝向下
{S[++top]=r；r=r->left ；}
if（top>0） // 退栈，沿栈顶结点的右子树向下删除，释放被删除结点空间
{p=S[top--]；r=p->right；free（p）；}
}
}// DelTree
void DeleteAllx(BSTree Ｔ，int x）
//在二叉排序树Ｔ中，删除所有小于等于x的结点
{BSTree p=T，q；
while（T && T->data≤x） //根结点的值小于等于x
{p=T；T=T->right；p->right=null；
DelTree（p）；} //删除二叉树p,删除持续到“根”结点值大于x或T为空树为止
if (T)
{q=T；p=T->left；
while（p && p->data>x） //沿根结点左分枝向下，查小于等于x的结点
{while（p && p->data>x） { q=p；p=p->left；} // q记p的双亲
if（p） //p结点的值小于等于x
{q->left=p->right；p->right=null；DelTree（p）； }
p=q->left；// 再查原p的右子树中小于等于x的结点
}}
}// DeleteAllx
