山东科技大学数据结构与操作系统2007考研试题研究生入学考试试题考研真题
● 摘要
数据结构部分
注意事项：
1、算法应说明基本思路，应对主要数据类型、变量给出说明，所写算法应结构清晰、简明易懂，应加上必要的注释。
2、算法可用（类）PASCAL语言、（类）C语言等你所熟悉的高级语言编写，但要注明语种。
一、解答下列问题[每小题4分，共16分]：
1、[4分]为什么要分析算法的时间复杂度？
2、[4分]简述代码区、全局数据区、栈区、堆区在程序运行时的作用。
3、[4分]求模式串s ＝’aaaabc’的next 及nextval 函数。
4、[4分]证明根据森林的先序序列与中序序列可以唯一确定一个森林。
二、综合应用题[每小题8分，共24分]：
1、[8分]推导满k 叉树上的叶子结点数n0和非叶子结点数n1之间的关系（即用k 和n1表示n0）。
2、[8分]设有正文AADBAACACCDACAC AAD ，字符集为A 、B 、C 、D ，设计一套二进制编码，使得上述正文的编码最短。
3、[8分]画出对长度为10的有序表进行二分查