数据结构与算法A卷答案
一、选择题（本题共20小题，每题2分，共40分）1A11A2B12C3D13D4D14D5B15C6B16C7A17A8B18D9C19D10C20D
二、分析运算题（本题共6小题，每题6分，共36分）
1如果输入序列为654321试问能否通过栈结构得到以下两个序列346521和234156请说明为什么不能或如何才能得到输出序列234156可以得到（2分）输出序列346521不能得到（2分），其理由是，输出序列中间两元素是65，前面2个元素（34）得到后，栈中元素剩65，且5在栈顶，不可能栈底元素6在栈顶元素5之前出栈2分。2请写出图中二叉树的前序先序和中序遍历序列。①前序先序：ABDCEF（3分）②中序：DBAECF（3分）3算术表达式如下：abcd①用二叉树表示算术表达式②写出后序（后缀）表达式
abcd
（3分）②后序（后缀）表达式：abcd（3分）
f4请写出无向图中顶点af的度a3（1分）b2（1分）c1（1分）d2（1分）e4（1分）f2（1分）5给定元素序列：（50，25，80，20，76，93），画出按照该序列构造的二叉排序树必须画出二叉排序树的建树过程。
502580
20
76
93
每个结点1分6下面的邻接表表示一个给定的无向图①请根据邻接表画出无向图②给出从顶点v1开始根据邻接表对图用深度优先搜索法进行遍历时的顶点序列；③给出从顶点v1开始根据邻接表对图用广度优先搜索法进行遍历时的顶点序列。
V1
V2
V3
V4
V5
V6
（2分）②深度序列：V1V2V5V3V4V6（2分）③广度序列：V1V2V3V4V5V6（2分）
f三、程序填空题（本题共5空，每空2分，共10分）
①p
ext（2分）②malloc（2分）③data（2分）④s
extp
ext（2分）⑤p
exts（2分）
四、算法设计题（本题共1小题，每题14分，共14分）
1如果通讯字符a，b，c，d出现频度分别为7，5，2，4①某同学设计了如下程序，请根据程序画出对应的二叉树，计算所画出的二叉树的带权路径长度（必须写出计算过程，否则不给分）；②请画出赫夫曼（哈弗曼）树必须画出赫夫曼树的建树过程；③计算它的带权路径长度（必须写出计算过程，否则不给分）④根据赫夫曼树，用ifelse语句修改①中的程序，写出最佳判定算法。①
18
16
2
c
12
4
d
7a
5b
（2分）（2分）
WPL7353422146②
f18
11
7a
6
5b
2c
4d
（3分）（3分）
③WPL2343527135④ifi
put’a’pri
tf