（数据结构A卷参考答案）

13-14-1《数据结构》A卷参考答案

一、判断题（10 × 1 = 10分） ? ? ? ? ? ? ? ? ? ? 二、填空题（10 × 1 = 10分）

1、逻辑 2、4 3、59 4、B[61] 5、n + 1 6、2h – 1 7、n – 1 8、2e 9、m – 1 10、3

三、单项选择题（15 × 2 = 30分） A D B B A C B D D C C C D A D

四、综合应用题（5 × 6 = 30分）

1、二叉树（3分）、后序DHEBIFCA（3分） A BC DEF HI

1002、Huffman 树（3分）、Huffman 编码共（3分） 46字符 编码 字符 编码 54a 0101 e 011 21252628b 10 f 000 1011c 01000 g 01001 1213d 11 h 001 57 233、深度优先：ABCED；广度优先：ABCDE （每个遍历序列3分） 4、(0, 4, 1, 3, 2, 5, 6, 7, 9, 8)

（6分）

5、Prim 算法步骤

(6分)

a1c

第一步

a11cac33a1c 3a1cee449f 3222e ebbdbd 第二步 第三步 第四步 第五步

五、算法设计题（2 × 10 =20分）

1、 （本题共10分）

void Reverse(SqList &L)

{ // 原地逆置顺序表L 中的元素 int i, j; ElemType temp; // 交换用中间变量 （2分） for (i = 0, j = L.length – 1; i < j; ++ i, -- j) { // i 当前最左元素下标，j 当前最右元素下标 （3分） temp = L.elem[i]; （5分） L.elem[i] = L.elem[j]; L.elem[j] = temp; } }

2、 （本题共10分）

int Count(BiTree T) { // 使用先序遍历 int count = 0; （1分） if (T) （2分） { if (! T->lchild && T->rchild || T->lchild && ! T->rchild)（3分） ++ count; count += Count(T->lchild) + Count(T->rchild); （3分） } return count; （1分）}