课后作业部分第七章图
2. 设计算法，计算图中出度为零的顶点个数。
3. 已知一个有向图的邻接表，编写算法建立其逆邻接表
19
课后作业部分第九章查找
第九章查找
一. 填空题
1. 顺序查找技术适合于存储结构为顺序和链式存储的线性表，而折半查找技术适用于存储结构为顺序存储的线性表，并且表中的元素必须是按关键码有序。
2. 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素28，6，12，20比较大小。
3. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列（哈希）查找。
4. 为了能有效地应用哈希查找技术，必须解决的两个问题是构造散列函数和解决冲突。 5. 有一个表长为m的散列表，初始状态为空，现将n（n 二. 选择题 1. 静态查找与动态查找的根本区别在于（ B ）。 A 它们的逻辑结构不一样 B 施加在其上的操作不同 C 所包含的数据元素的类型不一样 D 存储实现不一样 2. 用n个键值构造一棵二叉排序树，其最低高度为（ D ）。 A n/2 B n C log2n D log2n+1 3. 散列技术中的冲突指的是（ D ）。 A 两个元素具有相同的序号 B 两个元素的键值不同，而其他属性相同 C 数据元素过多 D 不同键值的元素对应于相同的存储地址 4. 链表适用于A查找 A顺序 B二分法 C顺序，也能二分法 D随机 三. 简答题 1. 分别画出在线性表（a，b，c，d，e，f，g）中进行折半查找关键码e和g的过程。 见下页 2. 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 20 课后作业部分第九章查找 第1题答案 3. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。 K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 构造出Hash表，试回答下列问题： (1)画出哈希表的示意图； (2)若分别查找关键字63和60，分别需要依次与哪些关键字进行比较？ (3)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 解：（1）画表如下： 0 1 2 3 4 5 6 32 17 63 49 7 8 9 10 11 12 13 14 15 16 17 30 31 46 47 24 40 10 （2）查找63,首先要与H(63)=63=15号单元内容比较，即63 vs 31 ,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！ （3）查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。 （4）对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55 四. 算法设计 1. 编写算法求给定结点在二叉排序树中所在的层数 21 课后作业部分第九章查找 2. 一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。 解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树” （刘注：即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要遵循（左小右大）原则）。 若要采用递归算法，建议您采用如下的函数首部： bool BisortTree(BiTree T, BiTree&PRE)，其中PRE为指向当前访问结点的前驱的指针。 （或者直接存储前驱的数值，随时与当前根结点比较） 一个漂亮的算法设计如下： int last=0, flag=1; // last是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。 int Is_BSTree(Bitree T) //判断二叉树T是否二叉排序树，是则返回1，否则返回0 { if(T->lchild&&flag) Is_BSTree(T->lchild); if(T->data if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; }//Is_BSTree 22 课后作业部分第九章查找 第十章排序 一. 填空题 1. 排序的方法有很多种，插入排序法从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。选择排序法从未排序序列中挑选元素，并将其依次放入已排序序列的一端。交换排序是对序列中元素进行一系列比较，当被比较的两元素为逆序时，进行交换；冒泡排序和快速排序是基于这类方法的两种排序方法，而快速排序是比冒泡排序效率更高的方法；堆排序法是基于选择排序的一种方法，是完全二叉树结构的一个重要应用。 2. 一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较3次。 3. 对n个待排序记录序列进行快速排序，所需要的最好时间是O(nlog2n)，最坏时间是 O(n2) 二. 选择题 1. 下列序列中，（A）是执行第一趟快速排序的结果。 A [da，ax，eb，de，bb] ff [ha，gc] B [cd，eb，ax，da] ff [ha，gc，bb] C [gc，ax，eb，cd，bb] ff [da，ha] D [ax，bb，cd，da] ff [eb，gc，ha] 2. 堆的形状是一棵（C）。 A二叉排序树 B满二叉树 C完全二叉树 D 判定树 3. 希望用最快的速度从5000个元素挑选出前10个最大的，采用（B）方法最好。 A快速排序 B堆排序 C希尔排序 D 归并排序 4. 设要将序列（Q，H，C，Y，P，A，M，S，R，D，F，X）中的关键码按升序排列，则（D）是起泡排序一趟扫描的结果，（B）是增量为4的希尔排序一趟扫描的结果，（E）二路归并排序一趟扫描的结果，（A）是以第一个元素为轴值的快速排序一趟扫描的结果，（C）是堆排序初始建堆的结果。 A（F，H，C，D，P，A，M，Q，R，S，Y，X） B（P，A，C，S，Q，D，F，X，R，H，M，Y） C（A，D，C，R，F，Q，M，S，Y，P，H，X） D（H，C，Q，P，A，M，S，R，D，F，X，Y） E（H，Q，C，Y，A，P，M，S，D，R，F，X） 5. 下述几种排序方法中，要求内存最小的是（AD） A插入排序B快速排序C堆排序D选择排序 三. 简答题 1. 已知数据序列为(12，5，9，20，6，31，24)，对该数据序列进行排序，写出插入排 23