《数据结构与算法》模拟卷（2）答案
一. 单项选择题（每项选择1.5分，共60分）
1、① A ② B
3、① C ② A 5、① A ② C 7、① C 9、① B ② A 11、① D 13、① C 15、① A 17、① D 19、① B 21、① B 23、① B 25、① C ② D 27、① C ② B 29、① D 31、① B 33、① A
2、① D 4、① B 6、① B 8、① B 10、① D 12、① D 14、① D 16、① B 18、① C 20、① A 22、① B 24、① C 26、① C 28、① D 30、① C 32、① A 34、① B
二. 填空题（将正确的答案填在相应的空位中,每空1-2分，共20分）
1、① n(n+1)/2 (给2分)； n(n-1)/2 或 n或 O(n) (给1分)
2、① n-i (给2分)； n-i+1 或 n-i-1 (给1分)
3、① 循环队列 (给2分)；仅写出 循环 或仅写出 队列 (给1分) 4、① 零个字符的串 ② 0 (各给1分) 5、① 42 (给2分)； 41 (给1分)
(i-1)h
6、① 3 ② (3-1)/2 (各给1分)
7、① 2 ② 1 ③ 2 ④ 强连通 ⑤ 1 ⑥ 6 (各给1分) 8、① 比较 ② 移动 (各给1分，只要包含这两个关键字的含义就给分)
2
2
三. 分析题（每题5分，共20分）
1、Ltag正确给1分；Rtag正确给1分；Lchild和Rchild正确给3分,个别有误扣1分；（Lchild
和Rchild错误，但二叉链树的形态正确给1分，线索二叉链树的形态正确给2分）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 Info A B C D E F G H I J K L M N Ltag 0 0 1 0 1 1 1 0 0 1 0 1 1 1 Lchild 2 4 1 7 2 3 0 10 13 4 12 8 6 9 Rtag 0 0 0 0 1 0 1 0 0 1 1 1 1 1 Rchild 3 5 6 8 1 9 4 11 14 8 2 11 9 0 2、算法(1)的功能是___从顺序存储结构的线性表a中删除第i个元素起的k个元素___; 算法(2)的功能是___________同上_____________;(功能的意思正确各给1分)
这两个算法在算法思想上的主要区别是 算法(1)每删除一个数据都要作(a.length-i)次数据移动，效率低，复杂度约为k*(a.length-i) ; 而算法(2) 总共只要作(a.length-i)次数据移动，效率高，复杂度约为 (a.length-i) 。(能够分出效率高低就给3分，否则酌情给分) 3、（酌情给0-5分；写出步骤给5分；未求出最短路径长度仅写出邻接矩阵给1分；未写路径不扣分；步骤不完整酌情扣1-3分) A B C D E F G A出发 B C D E F G A 15 2 12 步骤1 15 2 12 ∞ ∞ ∞ 选C B 6 步骤2 15 2 12 10 6 ∞ 选F C 8 4 步骤3 15 2 12 10 6 16 选E D 5 3 步骤4 15 2 12 10 6 16 选D E 9 步骤5 15 2 12 10 6 15 选B F 10 步骤6 15 2 12 10 6 15 G 4 路径 AB AC AD ACE ACF ADG 结束 4、（酌情给0-5分，大体上每句1分) Status exchangelr(BiTree &T) // 算法用函数名 exchangelr 表示 {BiTree p; // 临时工作指针
if(!T) return OK; // 待完成的若干语句； else{ p = T->lchild;
T->lchild = T->rchild; T->rchild = p;
exchangelr(T->lchild); exchangelr(T->rchild); } }