浙江工商大学数据结构期末复习题2(8)

status preorder(bt) { top＝0; p＝bt do{

(1) while( p!=nil ){

printf (p->data); if (p->right!=nil){ top＝top＋1;

s[top]＝p->right; }

//若右子树非空，则把链接指针保存起来， 待访问过左子树后再访问它 p＝p->left; //使p指向左子树 }

(2) if (top>0) { // 出栈，使p指向右子树 p＝s[top] top＝top－1; }

}while !((top＝0) && (p＝nil)); } 27.答：

第三个程序段不正确。例如，令n＝2,a[1]＝5,a[2]＝6,x＝6,则开始时，i＝1,j＝2, k＝(1＋2) div 2，又因a[k]

第五个程序段不正确。例如，令n＝2,a[1]＝5,a[2]＝6,x＝6,则开始时，i＝1,j＝2, k＝1,又因x

第一、二、四个程序段是正确的折半查找算法的表示。 28. d＝'THESE ARE BOOKS'

29. 由三维数组中的数据元素存储位置的计算公式（以行为主存储）为 LOC(i,j,k)＝LOC(c1 ,c2 ,c3 )＋[(i－c1 )(d2 －c2 ＋1)(d3 －c3 ＋1)] ＋(j－c2 )(d3 －c3 ＋1)＋(k－c3 )]×l

＝100＋(4×9×7＋2×7＋5)×3＝913

30. 根据题意可知这个矩阵的第一行和第n行的元素均为零。对满足2≤i≤n－1的各 行，除ai,n-i ，ai,n-i+1 ，ai,n-i+2 三个元素外，其它元素均为零。其矩阵的形状为

┏ ０ ０ ０ ０ ? ? ０ ０ ０ ０ ┓ ┃ ０ ０ ０ ０ ? ? ０ a2,n-2 a2,n-1 a2,n ┃ ┃ ０ ０ ０ ０ a3,n-3 a3,n-2 a3,n-1 ０ ┃ Ａ＝ ┃ ┃ ┃an-1,1 an-1,2 an-1,3 ０ ? ? ０ ０ ０ ０ ┃

┗ ０ ０ ０ ０ ? ? ０ ０ ０ ０ ┛ 如果按行优先顺序存放这些非零元素，可得如下序列：

a2,n-2 a2,n-1 a2,n a3,n-3 a3,n-2 a3,n-1 ? an-1,1 an-1,2 an-1,3 把它 们顺序存放在以FIRST为首址的一个连续的存储空间中，前i-1行共中非零元素3*(i-2)个， 在非零的aij 前，本行还有非零元素的个数为j－(n－i)个，若第一个非零元素a2,n-2 的存储地址为LOC(a2,n-2 ),则非零元素aij 的地址可用下式求出

36

LOC(aij )＝LOC(a2,n-2 )＋3×(i-2)＋(i＋j－n) 其中 2≤i≤n－1,n≤i＋j≤n＋2

即 LOC(aij )＝FIRST＋3×(i－2)＋(i＋j－n)

31.矩阵的转置运算是一种简单的运算，其方法是：

(1)把矩阵的行列值相互交换，所以一个m×n的矩阵M，它的转置矩阵N是一种n×m的矩阵；

(2)将每个三元组中的i和j相互交换；

(3)按交换后的行号从小到大重排三元组中各元素的次序。 由以上三条可得转置矩阵的三元组为 i j data ━━┳━━━┳━━ 1 ┃ 2 ┃ 2 2 ┃ 1 ┃ 1 3 ┃ 3 ┃ 4 4 ┃ 4 ┃ 5 5 ┃ 2 ┃ 3 ━━┻━━━┻━━

32.(1)head(A)＝a (2)tail(A)＝(b,c,d) tail(A)＝(b,c,d) head(tail(C))＝(c,d) 33.得到的二叉排序树如下图所示。 46

25 78

18 34 62

12 40 73

34.解：

(1)树的根是A，而E、F、C、H、I、J、K、M、N是叶子结点，其它为非终端结点。 (2)树的度为4。deg(A)＝3,deg(B)＝2,deg(D)＝4,deg(G)＝3,deg(L)＝1，其它各叶子结点的度均为0。

(3)树的深度为5（设根结点的深度为1）。level(A)＝1,level(B)＝2,level(C)＝2, ?,level(G)＝3,?,level(K)＝4,?，level(N)＝5。

(4)D是G的双亲；A、D是G的祖先；K、L、M是G的孩子；K、L、M和N是G的子孙；H、I、 J是G的兄弟；E、F是G的堂兄弟。 35.最大值

20 ＋21 ＋22 ＋?＋2h-1 ＝2h －1

最小值：第一层只有一个结点，其余的h-1层各有2个结点，所以最小值为2h-1个。

36.(1)见下图。

A

37

B

C D

E F G

H I

J (2)前序遍历：ABCEDFHGIJ 中序遍历：ECBHFDJIGA 后序遍历：ECHFJIGDBA

(3)后序线索化树见下图：

A NIL

B

C D

NIL E F G

H I

J 37.由前序遍历结果可知该二叉树的根结点为Ａ。由此及中序遍历结果可知，该二叉树在中序遍历下的左、右子树为

CBED和HGIJF

依此可推出前序遍历的左、右子树的结点序列为 BCDE和FGHIJ

B和F又分别为左、右子树的根结点，进而又可推出以B为根结点的左、右子树，以及 以F为根结点的左、右子树。依此类推，可推出二叉树见下图。 A

B F

C D G

E H I

J

38. (1) 图G的邻接矩阵

┏０ １ １ ０ ０ ０ ０┓

38

┃１ ０ ０ １ ０ ０ ０┃ ┃１ ０ ０ １ ０ ０ ０┃ A＝┃０ １ １ ０ １ １ ０┃ ┃０ ０ ０ １ ０ ０ １┃ ┃０ ０ ０ １ ０ ０ １┃ ┗０ ０ ０ ０ １ １ ０┛ (2)邻接表如见：

┌─┬─┐ ┌─┬─┐ ┌─┬─┐ １│Ａ│ ┼→─┤Ｂ│ ┼→─┤Ｃ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ２│Ｂ│ ┼→─┤Ａ│ ┼→─┤Ｄ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ３│Ｃ│ ┼→─┤Ａ│ ┼→─┤Ｄ│＾│

├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐ ┌─┬─┐ ４│Ｄ│ …… 此处隐藏：1272字，全部文档内容请下载后查看。喜欢就下载吧 ……