aaa
一、选择题（每小题1分，共10分）1.B 2. B 3.C 4.B 5.C 6.C 7. B 8.A 9.D 10.A
二、填空题（每小题1分，共10分）
11. 静态 12. 2 * I + J 13. 顺序 14. 对尾 对头
15. 3 16. 栈 17. （（d,e,f）） 18. 根
19. 2 20. 50
三、判断题（每小题1分，共10分）
21.√22.√23.×24.√25.√26.√27.√28.×29.×30. ×
四、运算题（每小题8分，共40分）
31.按行存储时与按列存储时，计算A[ i ][ j ]地址的公式分别为
LOC( i, j ) = LOC(0,0)+(i *n + j) * d
及 LOC ′( i, j ) = LOC(0,0)+( j *n + i) * d
两者相减，得
LOC( i, j ) – LOC ′( i, j ) = LOC(0,0)+( i *n + j) * d – LOC(0,0) – ( j *n + i) * d
=( i – j) * n * d + (j – i)*d 或
=(i – j)*(n – 1) *d
32.汉诺塔的递归处理过程如下表示：
move 1 to 3 (2分)
move 1 to 2 (2分)
move 3 to 2 (2分)
move 1 to 3 (2分)
33.后序序列：c, e, d, b, i, j, h, g, f, a
34.插入结果和调整类型为
调整类型：
插入数据：
40
28
16
56
50
32
30
63
无
无
右单旋
无
先右后左
双旋转
先左后右双旋转
无
左单旋
//每一个元素调整类型正确给1分。
35. 已知要存储的表项数为 n = 150，搜索成功的平均搜索长度为ASLSUCC≤2，则有ASLSUCC = 1/2（1+1/1-a）≤2， 解得a ≤2/3。 又有a = n/m = 150/m ≤ 2/3, 则 m ≥225。
五、算法分析题（每小题8分，共24分）
36. (1) 算法执行后得到的顺序表为{38，47，94，64，73，83，51，0}，表的长度减为8。（4分）
（2）该算法的功能是在顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。（2分）
（3）此算法的渐进时间复杂度为O（n）（2分）
37. 1 1 // 3分
1 2 1 // 3分
1 3 3 1 // 2分
38.（1） return c1 + 1 // 3分
(2) NodeLevel (BT → rightChild , X) // 3分
（3） return c2 + 1 // 2 分
六、6分，请根据编程情况酌情给分。
39. 算法如下：
int BTreeHeight (BinTreeNode * BT ) {
if (BT = = NULL ) return – 1; // 对于空树，返回–1并结束递归，1分
else {
int h1 = BTreeHeight(BT → leftChild ); //计算左子树的高度，2分
int h2 = BTreeHeight(BT → rightChild ); //计算右子树的高度，2分
if (h1>h2) return h1 + 1 ;
else retrun h2 + 1; //返回树的高度，1分
}
} 你是火星人么 好像数据结构 可能是他们班考试试卷的答案吧
页:
[1]