习题八 参考答案
一、选择题
1.对线性
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
进行二分查找时,要求线性表必须( 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的有序表,现用二分查找
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
查找某一记录,则查找不成功,最多需要比较( 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 + ",失败!");
}
}
}
运行结果: