第8章 查找 习题参考答案

习题八 参考 一、选择题 1．对线性表进行二分查找时，要求线性表必须(  B  ) A.以顺序方式存储    B.以顺序方式存储，且结点按关键字值有序排列 C.以链接方式存储    D.以链接方式存储，且结点按关键字值有序排列 2. 用二分查找法查找具有n个结点的顺序表时，查找每个结点的平均比较次数是( D  ) A.O(n2)      B.O(nlog2n)      C.O(n)        D.O(log2n) 3. 对长度为4的顺序表进行查找，若查找第一个的概率为1/24, 查找第二个记录的概率为1/6, 查找第三个记录的概率为2/3, 查找第四个记录的概率为1/8,则查找任意一个记录的平均查找长度为(  A  ) A.23/8        B.20/8          C.17/8        D.14/8 4. 若有一个长度为64的有序表，现用二分查找查找某一记录，则查找不成功，最多需要比较(  B    )次。 A.9          B.7              C.5          D.3 5. 当采用分块查找时，数据的组织方式为(  C  ) A.数据必须有序 B.数据不必有序 C.数据分成若干块，每块内数据不必有序，但块间必须有序 D.数据分成若干块，每块内数据必须有序，但块间不必有序 6. 一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该平衡二叉树共有(  C  )个结点。 A.2k-1-1        B.2k-1+1           C.2k-1        D.2k+1 7. 具有5层结点的平衡二叉树至少有(  B    )个结点。 A.10          B.12            C.15          D.17 8. 若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为(  D    ) A.顺序存储结构  B.链式存储结构  C.索引存储结构  D.散列存储结构 9. 以下有关m阶B-树的叙述中，错误的是(  B  )。 A.根结点至多有m棵子树        B.每个结点至少有 棵子树 C.所有叶子结点都在同一层上    D.每个结点至多有m-1个关键字 10．哈希表的地址区间为0～17，哈希函数为h(key)=K%17。采用线性探测法处理冲突，并将关键字序列{26，25，72，38，8，18,59}依次存储到哈希表中，则在哈希表中查找元素59需要搜索的次数为(  C  )。 A.2            B.3            C.4          D.5 二、填空题 1．动态查找表和静态查找表的主要区别在于  动态查找表有插入和删除操作 。 2．假定待查找记录个数为n,则在等概率的情况下，顺序查找在查找成功情况下的平均查找长度为  (n+1)/2  ；在查找失败情况下的平均查找长度为  n+1  。 3. 对线性表进行二分查找时，要求线性表必须以顺序方式存储，且数据有序  。 4. 分块查找分为两个阶段，分别是确定待查元素所在的块  和  在块内查找待查的元素。 5．哈希法存储中，冲突指的是不同关键字值对应到相同的存储地址。 6. 一棵二叉排序树用中序遍历输出的信息是 递增  序列。 7．深度为4的平衡二叉树中至少有  7  个结点，至多有 15    个结点。 8．引入B-树的根本原因是减少查找一个元素需要访问的外存的次数。 9．哈希法存储的基本思想是根据  关键字      来决定存储地址。 10．设计一个好的哈希函数，其函数值应该以 同等  概率取其值域的每个值。 三、算法设计题 1．基于SeqList类，设计带监视哨的顺序查找算法，要求把监视哨设置在n号单元。 参考答案： public int seqSearchWithGuard(Comparable key) { int i = length() - 1; getRecord()[i].setKey(key);    //哨兵设置在第n号单元 i = 0; while ((getRecord()[i].getKey()).compareTo(key) != 0) { i++; } if (i < length() - 1) { return i; } else { return -1; } } 2．基于SeqList类，设计一个递归算法，实现二分查找。 参考答案： public int binarySearchRecursively(int low, int high, Comparable key) { int mid, result; if (low <= high) { mid = (low + high) / 2;  //中间位置，当前比较元素位置 result = getRecord()[mid].getKey().compareTo(key); if (result > 0) { return binarySearchRecursively(low, mid - 1, key);                                //查找成功 } else if (result < 0) { return binarySearchRecursively(mid + 1, high, key); } else { return mid; } } return -1;  //查找不成功 } 3．基于BSTree类，设计一个算法，判断所给的二叉树是否为二叉排序树。 参考答案： public class Exercise8_3_3 extends BSTree { boolean flag = true; Comparable lastkey = new KeyType(0); //判断二叉树T是否二叉排序树,是则返回true,否则返回false boolean Is_BSTree(BiTreeNode T) { if (T.getLchild() != null && flag) { Is_BSTree(T.getLchild()); } if (lastkey.compareTo(((RecordNode) T.getData()).getKey()) > 0) { flag = false;  //与其中序前驱相比较 } ((KeyType) lastkey).setKey(((KeyType) (((RecordNode) T.getData()).getKey())).getKey()); if (T.getRchild() != null && flag) { Is_BSTree(T.getRchild()); } return flag; } } 4．基于BSTree类，设计一个算法，输出给定二叉排序树中值最大的结点。 参考答案： BiTreeNode maxNode(BiTreeNode T) { if (T == null) { System.out.println("这是一颗空树."); return null; } else { BiTreeNode q = T; while (q.getRchild() != null) { q = q.getRchild(); } return q; } } 5．基于BSTree类，设计一个算法，求出指定结点在给定的二叉排序树中所在的层数。 参考答案： public class Exercise8_3_5 extends BSTree { static int level = 0;          //层数 static boolean found = false;  public static int levelOfNode(BiTreeNode p, Comparable key) { if (p != null && !found) { level++; if (key.compareTo(((RecordNode) p.getData()).getKey()) == 0) { found = true; ; } else { levelOfNode(p.getLchild(), key);    //在左子树中查找 levelOfNode(p.getRchild(), key);    //在右子树中查找 if (!found) { level--; } } } return level; } } 6．基于BSTree类，设计一个算法，在二叉排序树中以非递归方式查找值为key的结点。 参考答案： public Object searchBSTNonRecur(BiTreeNode p, Comparable key) { while (p != null) { if (key.compareTo(((RecordNode) p.getData()).getKey()) == 0) //查找成功 { return p.getData(); } else if (key.compareTo(((RecordNode) p.getData()).getKey()) < 0) { p = p.getLchild();    //在左子树中查找 } else { p = p.getRchild();    //在右子树中查找 } } return null; } 四、上机实践题 1．已知关键字序列{8,30，43,52,59,80,83,100}，设计程序，要求采用带监视哨的顺序查找算法完成以下功能： ⑴ 查找关键字为83的数据元素，若找到，则输出该数据元素在表中的位置，否则给出查找失败的提示信息。 ⑵ 查找关键字为36的数据元素，若找到，则输出该数据元素在表中的位置，否则给出查找失败的提示信息。 参考答案： package ch08Exercise; import ch07.*; import java.util.Scanner; public class Exercise8_4_1 { static SeqList ST = null; public static void createSearchList() throws Exception { int maxSize = 20;  //查找表预分配空间的大小 ST = new SeqList(maxSize);    //创建查找表对象 int curlen;      //表的实际长度 int[] d={8,30,43,52,59,80,83,100};  curlen = d.length; KeyType[] k = new KeyType[curlen]; System.out.println("关键码序列："); for (int i = 0; i < curlen; i++) {  //输入关键字序列 k[i] = new KeyType(d[i]); System.out.print(d[i]+" "); } System.out.println(""); for (int i = 0; i < curlen; i++) {  //记录顺序表 RecordNode r = new RecordNode(k[i]); ST.insert(ST.length(), r); } } public static void main(String[] args) throws Exception { createSearchList();  //创建查找表 System.out.println("请输入2个待查找的关键字:");  //提示输入待查找的关键字 Scanner sc = new Scanner(System.in); //输入待查找关键字 KeyType key1 = new KeyType(sc.nextInt()); KeyType key2 = new KeyType(sc.nextInt()); System.out.println("seqSearchWithGuard(" + key1.getKey() + ")=" + ST.seqSearchWithGuard(key1)); System.out.println("seqSearchWithGuard(" + key2.getKey() + ")=" + ST.seqSearchWithGuard(key2)); } } 运行结果： 2．设计一个简单的学生信息管理系统。每个学生的信息包括学号、姓名、性别、班级和电话等。采用二叉排序树的结构实现以下功能： ⑴ 创建学生的； ⑵ 按照学号或姓名查找学生信息。 参考答案： package ch08Exercise; import ch07.*; import ch08.BSTree; import ch08.StudentType; public class Exercise8_4_2 { public static void main(String args[]) { BSTree bstree = new BSTree();  // String[][] item={{"小张","男","计科081","131********"}, {"小李","女","计科082","132********"}, {"小王","男","计科081","133********"},}; int[] k = {1002, 1001, 1003};  //关键字数组 KeyType[] key = new KeyType[k.length];          //关键字数组 StudentType[] elem = new StudentType[k.length]; //记录数据数组 System.out.println("原序列： "); for (int i = 0; i < k.length; i++) { key[i] = new KeyType(k[i]);            //创建关键字对象 elem[i] = new StudentType(item[i]);    //创建记录数据对象 if (bstree.insertBST(key[i], elem[i])) { //若插入对象成功 System.out.print("[" + key[i] + "," + elem[i] + "]"); } } System.out.println("\n中序遍历二叉排序树：  "); bstree.inOrderTraverse(bstree.getRoot()); System.out.println(); KeyType keyvalue = new KeyType(); keyvalue.setKey(1002); RecordNode found = (RecordNode) bstree.searchBST(keyvalue); if (found != null) { System.out.println("按学号查找：" + keyvalue + ",成功！ 对应学生为:" + found.getElement()); } else { System.out.println("按学号查找：" + keyvalue + ",失败!"); } keyvalue.setKey(1005); found = (RecordNode) bstree.searchBST(keyvalue); if (found != null) { System.out.println("按学号查找：" + keyvalue + ",成功！ 对应学生为:" + found.getElement()); } else { System.out.println("按学号查找：" + keyvalue + ",失败!"); } } } 运行结果：