浙江大学数据结构试卷1213613301844
浙江大学远程教育学院
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
答案
A卷
课程名称 数据结构与算法 年级专业(层次) 计算机
一. 单项选择题(每项选择1.5分,共60分)
1、? A ? B 2、? D
3、? C ? A 4、? B
5、? A ? C 6、? B
7、? C 8、? B
9、? B ? A 10、? D
11、? D 12、? D
13、? C 14、? D
15、? A 16、? B
D 18、? C 17、?
19、? B 20、? A
B 22、? B 21、?
23、? B 24、? C
25、? C ? D 26、? C
27、? C ? B 28、? D
29、? D 30、? C
31、? B 32、? A
33、? A 34、? B
二. 填空题(将正确的答案填在相应的空位中,每空1-2分,共20分) 2 21、? 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分,只要包含这两个关键字的含义就给分)
三. 分析题(每题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 B C D E F G A出发
A 15 2 12 15 2 12 步骤1 ? ? ? 选C B 6 15 2 12 10 6 步骤2 ? 选F C 8 4 15 2 12 10 6 16 步骤3 选E D 5 3 15 2 12 10 6 16 步骤4 选D E 9 15 2 12 10 6 15 步骤5 选B F 10 15 2 12 10 6 15 步骤6
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);
}
}