一.单项选择题（本题共10分，每小题2分）
1.给定n个整数，进行堆排序的时间复杂度为（ ?）
a.o(n2)?????????????b.o(log2n)?????????????c.o(nlog2n）????????????d.o(n1.5)
?
2.有7个元素g，f，e，d，c，b，a依次进栈（注：相邻两个元素进栈操作之间可能存

在若干出栈操作），则下列选项中不可能出现的出栈序列是（ ?）。
a.e，c，d，b，a，f，g ??????????????b.f，d，b，c，e，g，a ??????????????
c.g，d，e，b，c，a，f ??????????????d.d，b，f，a，c，e，g
?
3.kmp算法分析了模式中隐含的用于模式匹配的信息，这种信息就是模式中的“部分匹配”信息。当有了next数组之后，从而明显提高了匹配效率。kmp算法的时间复杂度为（ ?）。
a.o(m+n) ????????????????????????b.o(m×n) ???????????????
c.o(log2m+log2n) ?????????????????d.o(log2m×log2n)
?
4.给定一个二叉树（根结点为第一层），则第五层最多有（ ?）个结点。
a.16 ???????????????????b.15 ???????????????????c.32 ??????????????d.31
?
5.给定一棵二叉树，该二叉树的前序遍历得到的序列是abcdef，中序序列得到的序列是cbaedf，后序遍历得到的序列为（ ?）。
a.cbefda ???????????b.fedcba ??????????c.cbedfa ???????????d.不确定
?
二.简答题（本题共20分，每小题5分）
1.关于栈和队列两种数据结构，请指出哪一种数据结构符合“先进先出”原则，哪一种数据结构符合“先进后出”原则？
2.请简述邻接矩阵方法存储无向无权图的基本原理。
3.给定一个长度为100的字符串s，该字符串s对应的集合是{a，b，c，d，e，f，g}，即字符串中没有出现7个以外的字符，同时在字符串s的这100个字符中，a出现23次，b出现2次，c出现30次，d出现3次，e出现10次，f出现7次，g出现25次，请写出a，b，c，d，e，f，g的哈夫曼编码。（说明：构造哈夫曼树时，值较小的结点放左分支，值较大放右分支，左分支为0，右分支为1）
4.使用动态规划方法求解问题需要具备哪些性质？
?
三.综合题（本题共10分）
元素个数为n的int型数组a，用二路归并算法实现排序，简述算法实现思路，说明算法的时间复杂度。
?
四.算法设计题（本题共10分）
请写一算法，将两个按值逆序链接的非空线性链表合并为一个按值逆序链接的线性链表。