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

27.设有一个已排序的整数数组a[1..n]，和一个整数x，研究下面用类C所表示的折半查找的五个程序段，指出哪些是正确的。 第一个： i=1; j=n;

do{ k=(i+j)div 2;

if x>a[k] i=k+1; else j=k-1; }while !((a[k]=x) || (i>j)); 第二个: i=1; j=n;

while (i<=j) { k=(i+j) / 2;

switch{

case x>a[k]: i=k+1; case x= =a[k]: return; case x

第三个： i=1; j=n;

do{ k=(i+j) / 2;

if x>a[k] i=k; else j=k

}while !((a[k]= =x) || (i>=j)); 第四个： i＝1; j=n;

do{ k=(i+j) / 2;

if xa[k] i=k+1; }while !(i>=j); 第五个： i=1; j=n;

do{ k=(i+j) / 2; if x=j); 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

21

并不等于x，即求出的k是错误的。

第一、二、四个程序段是正确的折半查找算法的表示。

28.设a、b、c、d都是串名，a＝'THIS IS A BOOK'，b＝'ESE ARE'，C＝'S'。 求d＝CONCAT(SUB(a,1,2)，b，SUB(a,10,5),c)＝？ 28. 解答: d＝'THESE ARE BOOKS'

**29.数组b[1..10,-2..6,2..8]以行优先的顺序存储，设第一个元素的首址是100，每个元素的长度为3。试求元素b[5,0,7]的存储首址。

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×n(n≥3)的稀疏矩阵A中，只有下标满足1

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 的地址可用下式求出 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.用三元组表示下面稀疏矩阵的转置矩阵。 ┏0 1 0 0 0┓ ┃2 0 0 0 3┃ M＝┃0 0 4 0 0┃ ┗0 0 0 5 0┛

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

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

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

(3)按交换后的行号从小到大重排三元组中各元素的次序。

由以上三条可得转置矩阵的三元组为

22

i j data ━━┳━━━┳━━ 1 ┃ 2 ┃ 2 2 ┃ 1 ┃ 1 3 ┃ 3 ┃ 4 4 ┃ 4 ┃ 5 5 ┃ 2 ┃ 3 ━━┻━━━┻━━ **32.给出下列每个广义表的相关运算。 (1) A＝(a，b，c，d) head(A) tail(A) (2) C＝((a，b)，(c，d)) head(C) head(tail(C))

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、62、18、34、12、40、73)，试画出按元素排列顺序输入而生成的一棵二叉排序树。

33. 解答:得到的二叉排序树如下图所示。 46

25 78

18 34 62

12 40 73 34.已知一棵树的边的集合表示为：(L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G), (D,H),(D,I),(D,J),(A,B),(A,C),(A,D))画出这棵树，并回答下列问题： (1)树根是哪个结点？哪些是叶子结点？哪些是非终端结点？ (2)树的度是多少？各个结点的度是多少？

(3)树的深度是多少？各个结点的层数是多少？以结点Ｇ为根的子树的深度是多少？ (4)对于结点Ｇ，它的双亲是哪个结点？它的祖先是哪些结点？它的孩子是哪些结点？ 它的子孙是哪些结点？它的兄弟和堂兄弟分别是哪些结点？ 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.设高度为h的二叉树上只有度为0和度为2的结点，问该二叉树的结点数可能达到的最大值和最小值。

35. 解答:最大值(高度为h的满二叉树) 20 ＋21 ＋22 ＋?＋2h-1 ＝2h －1

23

最小值：第一层只有一个结点，其余的h-1层各有2个结点，所以最小值为2h-1个。 36.设二叉树BT的存储结构如下：

１ ２ ３ ４ ５ ６ ７ ８ ９ 10 ┏━┳━┳━┳━┳━┳━┳━┳━┳━┳ …… 此处隐藏：2016字，全部文档内容请下载后查看。喜欢就下载吧 ……