一、 单项选择题：1－20小题，每小题2分，共40分。在每小题给出的四个选项中，请选出一项最符合题目要求的选项。
1. d 2. a
3. d 4. d
5. c6. b
7. b8. a
9. d 10. d
11. c12. b
13. b14. a
15. a16. d
17. d18. b
19. a20. c
二、 简答题。21－23小题。共35分。
21. （8分）答：哈夫曼树（略）构造成功5分，编码正确3分。
22. （18分）
3）关键路径为0—>1245，长度为3+4+2+4=13.
23. （9分）答： （1）
构造的散列表如下：（7分）
评分说明】所画的散列表长度正确（长度为10，下标从0到9），给1分。填写关键字正确，每个给1分。考生可以不写出计算过程。若解答部分正确，酌情给分。
2）查找成功的平均查找长度：（2分）
因为查找长度为1的关键字有4个，查找长度为2的关键字有1个，查找长度为3的关键字有2个，所以查找成功的平均查找长度：
asl成功=（1次×2+2次×1+3次×2+4*1）/7=2（2分）
各位置对应的探查次数如下表所示：
评分说明】若分别采用公式（为装填因子）：
和。计算查找成功，且计算正确，可共给2分。若解答部分正确，酌情给分。
三、 算法设计题。24－25小题。共25分。每题要求：
24. （12分）给定有m个整数的递增有序数组a[m]和有n个整数的递减有序数组b[n]，试写出算法，将数组a和b归并为递增有序数组c[m+n] （要求算法的时间复杂度为o(m+n)）。
答：（1）描述算法的基本设计思想（3分）
把b[n]逆置，然后两个递增有序数组归并成c数组。
2）描述算法的详细实现步骤（4分）略。
3）根据设计思想和实现步骤，采用c语言描述算法，关键处请给出注释（5分）略。
题目分析]数组a和b的元素分别有序，欲将两数组合并到c数组，使c仍有序，应将a和b拷贝到c，只要注意a和b数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到c中即可。
void union(int a,b,c,m,n)
//整型数组a和b各有m和n个元素，前者递增有序，后者递减有序，本算法将a和b归并为递增有序的数组c。
算法结束。25. （13分）设含有n个元素的线性表a=(a1, a2, a3,…,an-1, an)，用带头结点的单链表表示。
试编写一个算法，对a进行调整，使得所有偶数项排在奇数项之前，即：当n为偶数时，a=(a2,a4,…,an,a1,a3,…,an-1)；当n为奇数时，a=(a2,a4,…,an-1,a1,a3,…,an)，并分析算法的时间复杂度。
答：1）描述算法的基本设计思想（3分）
设置遍历指针p和计数器j，以及指向偶数项表尾的指针。将偶数项从原表中删除，插在偶数项表尾。
2）描述算法的详细实现步骤（4分）略。
3）根据设计思想和实现步骤，采用c语言描述算法，关键处请给出注释（5分） 略。
4）算法时间复杂度：o(n).（1分）
数据结构试题 A卷2019 答案
2012 2013学年第一学期期末考试。数据结构 试题a答案。一 选择 每空2分，共30分 bcdbd bccbb cabbc 二 1.答 1 应选择链式存储结构。它可动态申请内存空间，不受表长度 即表中元素个数 的影响，插入 删除时间复杂度为o 1 2 应选择顺序存储结构。顺序表可随机存取，时间复...
2019数据结构A卷
数据结构 试卷a 1.算法的时间复杂度取决于 问题的规模 待处理数据的初态和 的长短。2 从逻辑上可以把数据结构分为 两大类。动态结构 静态结构 顺序结构 链式结构 线性结构 非线性结构 初等结构 构造型结构。3.对于栈操作数据的原则是。先进先出 后进先出后进后出不分顺序。4.一个栈的输入序列为12...
北大15春《数据结构》作业答案答案
作业id 82376 以下哪个算法的时间复杂度表示是最慢的？b 第一章 a.a.o 1 b.b.o log2n c.c.o n d.d.o n 2 2.在一个线性表中，假设第一个元素a1的存储地址是20，每个元素占用四个存储单元，则第8个数据元素a8的地址是 c 第二章 a.a.42 b.b.28 ...