《考研计算机－习题精炼和重点回顾 查找 》由会员分享，可在线阅读，更多相关《考研计算机－习题精炼和重点回顾 查找 （15页珍藏版）》请在金锄头文库上搜索。
1、在一个有 n 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂度为 A.O( B.O(n) C.O( ) 您的答案是：【未答】 正确答案是：【B】解析：在单链表上进行查找，只能采用顺序查找，因此平均时间复杂度为 O(n)。2具有 n 个数据元素的顺序组织的表，一个递增有序，一个无序，查找一个元素时采用顺序查找。其中对有序表从头开始查找，发现当前检测元素已不小于待查元素时，停止查找，确定查找不成功。已知查找任一元素的概率是相同的，则在两种表中查找成功 您的答案是：【未答】 正确答案是：【B】解析：顺序查找的基本思想是：从表的一端开始，顺序扫描线性表，依次用查找条件中给定的值与查
2、找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。查找不成功时，需进行 n+1 次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表和无序表是一样的。查找成功时，平均查找长度为（n+1）/2，有序表和无序表也是一样的。因此，在无序表和有序表中查找成功时的平均查找时间是相同的。3如果有 5 个关键码a,b,c,d,e放在顺序表中，它们的查找概率分别是，可使成功的平均查找长度达到的最小的存放方式是 A.d,a,b,c,e B.e,d,c,b,a C.a,b
3、,c,d,e D.a,c,e,d,b 您的答案是：【未答】 正确答案是：【C】解析：选项 C 的成功平均查找长度为+=是因为查找概率大的放在了表的前面。4在线性表中采用折半查找法（二分查找法）查找一个数据元素，线性表应 且采用顺序存储结构 且采用链式存储结 您的答案是：【未答】 正确答案是：【C】解析：只有当线性表中数据元素按值大小有序排列，并且采用顺序存储结构时才能使用折半查找方法查找数据元素。即使线性表中数据元素按值大小有序排列，但采用的不是顺序存储结构（如链式存储结构），仍然不能够采用折半查找方法。5将数据元素 2，4，6，8，10，12，14，16，18，20 依次存放于一个一维数组中
4、，然后采用折半查找方法查找数组元素 12，被比较过的数组元素的下标依次为 6，12 2，16 ，6 ，8 您的答案是：【未答】 正确答案是：【C】解析：第一次与数组下标为 5 的元素比较，不匹配；第二次与数组下标为 8 的元素比较，仍然不匹配；第三次与数组下标为 6 的元素比较，匹配，查找成功。因此，经过比较的数组元素的下标依次为 5，8，6。6对表长为 n 的有序表进行折半查找，其判定树的高度为 A. B. C. D. 您的答案是：【未答】 正确答案是：【B】解析：本题主要考查折半查找的性能分析和判定树的概念。折半查找的过程可用二叉树来描述，把当前查找范围的中间位置的数据元素（即 置的数据元
5、素）作为二叉树的根结点，把左半部分（即查找范围和右半部分（即查找范围，的数据元素分别作为左子树和右子树中的结点，由此得到的二叉树成为折半查找的判定树。在有 n 个元素的有序表中，设层数为 h，该树中层数为 1 的结点有 1 个，层数为 2 的结点有 2 个，层数为 有 1+2+2n1+2+2 以判定树高度 是 。7n 个结点的用于折半查找的判定树，表示查找失败的外部结点共有（ ）个 D. 您的答案是：【未答】 正确答案是：【B】解析：本题主要考查折半查找的判定树的概念和外部结点的概念。外部结点实质上表示查找失败的结点，而查找失败意味着待查元素的值位于待查列表中某两个值的中间位置，而在有 n 个
6、元素的待查列表中，这样的位置有 n+1 个，因此查找失败的外部结点个数共有 n+1 个。8具有 n 个关键字的 m 阶 （ ）个叶子结点。 m D. 您的答案是：【未答】 正确答案是：【A】解析：本题主要考查 m 阶 m 阶 n 个关键字查找不成功的情况是待查找的关键字值介于 n 个关键字中某两个关键字值之间，这样的可能性共有 n+1 种，因此叶子结点有 n+1 个。9已知一棵 5 阶 3 个关键字，并且每个结点的关键字都达到最少状态，则它的深度是 您的答案是：【未答】 正确答案是：【C】解析：本题主要考查 m 阶 据 m 阶 根结点之外所有非终端结点至少有 即 3 棵子树，所以除根结点之外的
7、所有非终端结点至少有 2 个关键字，根结点至少有 2 棵子树，至少有 1 个关键字。因为叶子结点不含关键字，设不包括叶子结点那一层，若该树为 1 层，则有 1 个关键字；若该树为 2 层，则有 1+22 个关键字；若该树为 3 层，则有1+22+232=17 个关键字；若该树为 4 层，则有1+22+232+2332=53 个关键字。所以它的最终深度为 5。10向一棵 m 阶 插入关键字时需要分裂该结点，则在插入之前，该结点的关键字数目为 您的答案是：【未答】 正确答案是：【B】解析：本题主要考查 m 阶 据定义，树中的结点最多有 m 棵子树，而树中每个结点含有的关键字数目比指向孩子结点的指针
8、数目少 1，所以树中的结点最多有 关键字，若插入后该结点的的关键字数目超过该值则需要进行分裂。11下面关于 +树的叙述中，不正确的是 +树都是平衡的多分树 +树都可用于文件的索引结构 +树都能有效地支持随机检索 +树都能有效地支持顺序检索 您的答案是：【未答】 正确答案是：【D】解析：因为 B+树所有的叶子结点中包含了全部关键字信息，以及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小到大顺序链接，所以支持从根结点的随机检索和直接从叶子结点开始的顺序检索，但是 以只支持从根结点的随机检索，而不支持直接从叶子结点开始的顺序检索。12采用开放地址法解决冲突的散列查找中，发生聚集的原因
9、主要是 您的答案是：【未答】 正确答案是：【D】解析：不同关键字对同一散列地址进行争夺的现象称为聚集或是堆积。这将造成不是同义词的结点也处在同一个探查序列之中，从而增加了探查序列的长度，即增加了查找时间。发生聚集的主要原因是算法选择的问题，如果用二次探测再散列法，则聚集的程度会远小于线性探测再散列法。13在下列查找方法中，平均查找长度与元素的个数无关的方法是 、C 都是 您的答案是：【未答】 正确答案是：【C】解析：顺序查找方法和折半查找方法的平均查找长度都与元素的个数有关，由于散列结构是由事先准备好的散列函数关系与处理冲突的方法来确定数据元素在散列表中的存储位置的。因此，散列查找方法的平均查
10、找长度与元素的个数无关。14散列表的检索性能可以表示为下列哪个变量的函数 您的答案是：【未答】 正确答案是：【C】解析：散列表的平均查找长度不是结点个数 n 的函数，而是装填因子 的函数。因此在设计散列表时可选择 以控制散列表的平均查找长度。15假设有 k 个关键字互为同义词，若用线性探测法把这 k 个关键字存入散列表中，至少要进行多少次探测 D.k（k+1）/2 您的答案是：【未答】 正确答案是：【D】解析：因为 k 个关键字互为同义词，只有在存入第一个关键字的情况下不发生冲突，因而至少需要进行 1+2+k= k（k+1）/2 次探测。16从 19 个元素中查找其中任意一个元素，如果最多进行
11、 4 次元素之间的比较，则采用的查找方法只可能是 您的答案是：【未答】 正确答案是：【C】解析：折半查找和二叉树查找最多需要 5 次比较，而分块查找则更多。17在单链表中，每个结点含有 5 个正整型的数据元素（若最后一个结点的数据元素不满 5 个，以值 0 填充），试编写一算法查找值为 n（n0）的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素则返回空指针。 您的答案是：未答； 参考答案是：这是一个在单链表中查找结点，在结点内查找给定值的过程，先定义存储结构。m； /每个结点内含有 m 个正整数，本例中 m 为 5j； /正整数在结点内的序号s；/结点的指针解答】用 C
12、语言算法描述如下：n) R;p=，p 指向链表第一元素结点；p & !i=0;iAi= =n) ；/查找成功p=p-if（p= =R.j=i; R.s=p; ； 解析：无18对下面的关键字集30,15,21,40,25,26,36,37若查找表的装填因子为 用线性探测再散列方法解决冲突：（1）设计散列函数； （2）画出散列表；（3）计算查找成功和查找失败的平均查找长度。 您的答案是：未答； 参考答案是：由于装填因子为 键字有 8 个，所以表长为 8/0。（1）用除留余数法，散列函数为 H（OD p= .（2）散列表：解析：无19已知一组关键字为（1，9，25 ，11，12，35 ，17，29），用链地址法解决冲突，散列函数为 H(K) = K 3，回答下列问题：（1）画出散列表；（2）计算出等概率情况下查找成功的平均查找长度；（3）计算出等概率情况下查找失败的平均查找长度。 您的答案是：未答； 参考答案是：（1）散列表：解析：顺序查找法而言，对于 n 个数据元素的表，给定值 表中第 i 个元素关键码相等，即定位第 i 个记录时，需进行 次关键码比较，即 Ci=。则查找成功时，顺序查找的平均查找长度为：设每个数据元素的查找概率相等，即 ，则等概率情况下有查找不成功时，关键码的比较次数总是 n+1 次。算法中的基本工作就是关键码
