28．已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，画出这棵二叉树。 【分析】： 由后序遍历序列能够得到的二叉树的根结点A（后序序列中最后一个结点）；在中序序列中，A的左边是A 的左子树上的结点，A的右边是A 的右子树上的结点；再到后序序列中找左子树和右子树的根结点，依次类推，直到画出该二叉树。 【答案】：
C
A B F G D E H
29．对以链表作存储结构的二叉树设计求二叉树的深度的算法。
typedef struct node {int data； struct node *lchild，*rchild；} NODE； 【分析】： ： 本算法为递归算法。空树的深度为0，如果树不空，分三步进行：第一步，判断根结点是否为叶子结点，若是，则深度为1；第二步，调用该算法求根结点的左子树的深度hl，第三步，调用该算法求根结点的右子树的深度hr；二叉树的深度为max(hl，hr)+1。
【答案】：
int depth(NODE *root){
if (root==NULL) return 0；
else if((root->lchild==NULL)&&(root->rchild==NULL))
return (1)； /* 如根结点是叶子结点，则深度为1 */
else {
hl=depth(root->lchild)； /* 左子树的深度 */
hr=depth(root->rchild)； /* 右子树的深度 */
if(hl>hr) return(hl+1)；
else return(hr+1)； /*深度为max(hl，hr)+1 */ }
}
30．对序列12，7，17，11，16，2，13，9，21，4构成一棵二叉排序树。 【答案】：
2 7 12 17 21 11 16 4
9 13 16
31．从供选择的答案中找出应添入下列叙述中的（ ）内的正确答案。 （1）要进行线性查找，则线性表（ ）； （2）要进行二分查找，则线性表（ ）； （3）要进行散列查找，则线性表（ ）； （A）：必须以顺序方式存储； （B）：必须以链式方式存储； （C）：必须以散列方式存储；
（D）：既可以以顺序方式存储，也可以以链式方式存储； （E）：必须以顺序方式存储且数据元素已按值递增或递减的次序排好。 （F）：必须以链式方式存储且数据元素已按值递增或递减的次序排好。 【答案】：（1）选择D；（2）选择E；（3）选择A；
32．用二分查找的查找速度必然比线性查找的速度快。这说法对吗？为什么？ 【答案】：
正确。因为用二分查找法来查找时，在每一次比较之后，如查找不成功，是将待查范围缩小一半。而采用线性查找时，每次比较之后是将待查范围缩小一个元素。二分查找的平均查找长度为：log2n；而线性查找的平均查找长度为：（n+1）/2。
33．说明散列查找和其它查找方法的区别。
【答案】： 散列查找是希望平均查找长度与记录的个数无关，既不经过任何比较，“一次”存取就能得到所要查找的元素的查找方法。它要求在元素的存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字和结构中一个唯一的存储位置相对应。而其它的查找方法的平均查找长度都与记录的个数有关，但不必在元素的存储位置和它的关键字之间建立一个确定的对应关系。
34．r是一个顺序表结构的有序表，编写一个查找算法，要求在查找失败时做插入操作并保持表r的有序性。 【分析】：：用二分查找方法，如查找成功，则返回待查元素在表中的位置，如果查找不成功，既low>high时，此时high+1的位置为待查元素所应插入的位置，这样可以保持表r的有序性。 【答案】：
#define M 500
typedef struct {int key； char info；} NODE；
NODE r[M]；
int binsrch_insert(int n，int k){ /* k为要查找的数据，n为实际的表长 */ int low，high，mid，k； NODE temp； low=1； high=n； while(low<=high){
mid=(low+high)/2；
if(k==r[mid].key) return(mid)； /* 查找成功 ，返回*/
else if(k 17 if(n==M) { printf(“ Table is full!\\n”)； return 0； } /* 表满不能插入 */ else { for(k=n；k>=high+1；k--) r[k+1]=r[k]； /*从r[high+1]到r[n]的所有元素右移一个位置*/ r[high+1].key=k； r[high+1].info=??；/* 数据插入 */ } } 35．设记录的关键字集合为K=（32，13，49，55，22，39，17），用模除散列函数得到散列 地址，解决冲突的办法为线性探测法，按上述条件将集合中的各值依次添如下表中。 0 1 2 3 4 5 6 7 【答案】： 32 49 39 17 13 22 55 36．选取散列函数H（key）=（3*key）% 11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0~ 10，表长为11的散列表，（22，41，53，08，46，30，01， 31，66）。 22 01 41 30 66 53 46 31 08 0 1 2 3 4 5 6 7 8 9 10 37．关键字序列T={13，6，3，31，9，27，5，11}，分别写出选择排序和直接插入排序的 中间过程序列。 【答案】： （1）选择排序： i k 初始序列： 13 6 3 31 9 27 5 k 27 5 11 /*T[1]与T[3]交换 */ 11] /*T[2]与T[7]交换 */ i 完成第一趟： 3 [6 13 31 9 i k 完成第二趟： 3 5 [13 31 9 27 6 11] /*T[3]与T[7]交换 */ i k 完成第三趟： 3 5 6 [31 9 27 13 11] /*T[4]与T[5]交换 */ i k 完成第四趟： 3 完成第五趟： 3 完成第六趟： 3 完成第七趟： 3 （2）直接插入排序： 初始序列： 13 6 3 31 9 27 5 11 第一趟： [13] 6 3 31 9 27 5 11 第二趟： [6 13] 3 31 9 27 5 11 5 6 9 [31 27 13 11] /*T[5]与T[8]交换 */ i k 5 6 9 11 [27 13 31] /*T[6]与T[7]交换 */ i=k 5 6 9 11 13 [ 27 31] /*不用交换 */ i=k 5 6 9 11 13 27 [ 31] 18 第三趟： 第四趟： 第五趟： 第六趟： 第七趟： 第八趟： [3 [3 [3 [3 [3 [3 6 6 6 6 5 5 13] 31 9 13 9 9 6 6 27 5 11 31] 9 27 5 11 13 31] 27 5 11 13 27 31] 5 11 9 13 27 31] 11 9 11 13 27 31] 38．对于整数序列100，99，?，3，2，1，如果将它完全倒过来，分别用冒泡排序和快速 排序法，它们的比较次数和交换次数各是多少？ 【答案】： 对冒泡排序方法来说，这个序列是最坏的情况，n=100个数据，共进行99趟排序操作，第一趟要比较99次，第二趟要比较98次，??，第99趟要比较1次，每一次比较都 执行了一次交换，所以共进行了99+98+97+??+1=100*99/2=4950次比较和交换。 对快速排序方法来说，这个序列也是最坏的情况，与冒泡排序一样，共进行99趟排序。第一趟要比较99次，进行一次交换，第二趟要比较98次，不需要交换，第三趟要比较97次，进行一次交换，第四趟要比较96次，不需要交换，??，所以总的比较次数为4950次，交换的次数为50次。 39．对关键码值为{35，11，52， 69， 6， 17， 76，64，82}的序列执行以下排序算法， 画出执行过程中每个中间状态和结束时的状态： （1）直接插入排序；（2）二分插入排序；（3）直接选择排序；（4）冒泡排序；（5）快速排 序。 【答案】： （1）直接插入排序： 初始序列： 35 11 52 69 6 第一趟： [35] 11 52 69 6 第二趟： [11 35] 52 69 6 第三趟： [11 35 52] 69 6 第四趟： [11 35 52 69] 6 17 76 64 82 17 76 64 82 17 76 64 82 17 76 64 82 17 76 64 82 第五趟： [6 11 35 52 69] 17 76 64 82 第六趟： [6 11 17 35 52 69] 76 64 82 第七趟： [6 11 17 35 52 69 76] 64 82 第八趟： [6 11 17 35 52 64 69 76] 82 第九趟： [6 11 17 35 52 64 69 76 82] （2）二分插入排序：与直接插入排序类似，只是在找插入位置时用二分查找方法。 （3）直接选择排序： 初始序列： [ 第一趟： 第二趟： 第三趟： 第四趟： 第五趟： 第六趟： 35 11 52 69 6 17 76 64 82 ] 6 [ 11 52 69 35 17 76 64 82 ] 6 6 6 6 6 11 [ 52 69 35 17 76 64 82 ] 11 17 [ 69 35 52 76 64 82 ] 11 17 35 [69 52 76 64 82 ] 11 17 35 52 [ 69 76 64 82 ] 11 17 35 52 64 [ 76 69 82 ] 19 第七趟： 第八趟： （4）冒泡排序： 初始序列： 6 6 11 17 35 52 64 69 [ 76 82 ] 82 ] 11 17 35 52 64 69 76 [ 35 11 52 69 6 17 76 64 82 第一趟： 11 35 52 6 17 69 64 76 82 /* 4次交换 */ 第二趟： 11 35 6 17 52 64 69 76 82 /* 3次交换 */ 第三趟： 第四趟： 第五趟： 11 6 17 35 52 64 69 76 82 /* 2次交换 */ 6 11 17 35 52 64 69 76 82 /* 1次交换 */ 6 11 17 35 52 64 69 76 82 /* 没有任何交换，完 成*/ （5）快速排序： 初始序列： 35 11 52 69 6 i 第一次交换： 17 11 52 69 6 i 第二次交换： 17 11 35 69 6 i j 第三次交换： 17 11 6 第四次交换： 17 11 6 i j i j 17 76 64 82 /* 初始化i=1，j=9 */ j 35 76 64 82 /* j=6时与35交换 */ j 52 76 64 82 /* i=3 时与35交换*/ 69 35 52 76 64 82 /* j=5 时与35交换*/ 35 69 52 76 64 82 /* i=4 时与35交换*/ i=j 完成一趟排序：[17 11 6] 35 [69 52 76 64 82 ] /* i=j=4 */ i j i j 下一趟初始： [17 11 6] [69 52 76 64 82 ] i j i j 第一次交换： [6 11 17] [64 52 76 69 82 ] i= j i j 第二次交换： [64 52 69 76 82 ] i=j 完成第二趟排序： [6 11] 17 [64 52] 69 [76 82] 下一趟初始： 第一次交换： 完成第三趟排序： 6 [11] 排序完成： [52] 64 76 [82] 69 76 82 i j i j i j i= j [6 11] [64 52] i= j [76 82] i j [52 64] 6 11 17 35 52 64 20 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库自考 2365计算机软件基础（二）课后 习题(4)在线全文阅读。
相关推荐：