06年的考研硝烟已经基本停下来了,回想这考研生活,其中有甜也有苦,有酸也有辣,总之是一言难尽吧!在考研中让人感动的东西很多,在读研究生的无私奉献应该是一件!有了他们的帮助,考研者一路上才有了许多安慰,才有了许多感激之情!

在此,我再次呼吁06年的考研者能够奉献出他们手中的历年真题,呼吁帮帮07的学弟,学妹们!相信好人会得到他们的祝福的!同时也希望07的能够贡献你们手上有的资料,要知道帮助别人就是帮助自己,毕竟个人收集的资料有限,大家集合起来就全了.

大家可以把试卷发到我的邮箱（luo95@sohu.com）,我帮你们上传。也可以邮寄给我，或者开学后给我，由我来输入！当然,跟帖就最好了,我将稍后整理出来,放进真题资料库!

郑君里《信号与系统》(第二版) 答案

跟我学模拟电子电路和跟我学数字电子技术

信号与系统课件1

《离散数学》部分
1、如果两个图中各结点的度数分别如（1）、（2）所示，问它们是否可能构成无向树？如果能，请画出3棵非同构的无向树。（10分）
（1）1，1，1，1，2，3，3，4
（2）1，1，1，1，2，2，3，3

2、给定群<G,*>,R 是G的元素之间的等价关系，并且任意给定a，x，y属于G，有（a*x）R(a*y)=>xRy,证明：若H＝{x|x属于G，xRe},则<H,*>是<G,*>的子群。其中e是<G,*>的幺元。（10分）

3、符号化下面的命题并给出推理证明：
没有不守信用的人是可信赖的；有些可以信赖的人是受过教育的。因此，有些受过教育的人是守信用的。（15分）

4、设有一个由a 生成的循环群<G,*>，若a 的阶是无限的，则<G,*>与整数加法群<I,+>同构。（10分）

5、对下列每组集合A和B，构造一个从A 到B的双射，以说明A 和B具有相同的势。
（1）A＝R（实数集），B＝（0，无穷大）（5分）
（2）A＝[0，1]，B＝[1/4,1/2]   (5分)

6、设R是集合A 上的一个具有传递和自反性质的关系，T是A上的关系，<a,b>属于T <=> <a,b>属于R  ^ <b,a>属于R， 证明T是A上的等价关系。（10分）

7、用图论的方法证明下列问题：
（1）若有n 个人，每个人恰好有3个朋友，则n必为偶数。 （5分）
（2）在任何六个人中，或者有三个人互相认识，或者有三个人互相不认识。（5分）

《数据机构》部分
一、填空（10分）
1、对长度为n 的线性表采用顺序查找，在等概率的条件下，查找成功的平均检索长度为_____。在长度为n 的顺序表中删除第i（1<= i <= n ）个数据元素需要移动_____个数据元素。在长度为n 的顺序表中的第i（1<= i <= n ）个数据元素之前插入一个新元素，需要移动______个数据元素。
2、高度为i（i>= 1）的完全二叉树最多有______个结点，最少有_____个结点；若按自上而下，从左到右的次序给结点编号（从1开始），则编号最小的叶子结点的编号为______。
3、设有n 阶3对角阵（aij）n×n    将其三条对角线上的元素存于数组B[3][n]中，使得元素B[v]＝aij， 从（i，j）到（u，v）的下标变换公式为___________。
4、线性表的______存储结构是随机存储结构。
5、设字符a,b,c,d,e,f的使用频度分别为3，4，9，12，15，20。则b，d的哈夫曼编码分别为______,_________。

二、回答下列问题（20分）
1、对长度为n 的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。（1）你＝7时，在最好情况下需要进行多少次比较？请说明理由。（2）对n＝7，给出一个最后情况的初始排列的具体例子。
2、已知在一棵含有n个结点的树中，只有度为k 的分支结点和度为0 的叶子结点，求该树含有的叶子结点数。
3、假设一棵二叉树的层次遍历序列为a b c d e f g h i j， 中序遍历序列为d b g e h j a c i f ,请画出该二叉树。
4、主串S＝"abbacbabbcabbcabbcabcaabbc",子串＝“abbcabcaa”,若用简单模式匹配算法，查找成功需要比较多少次？若用KMP 算法，查找成功需要比较多少次？并计算出相应的NEXT[]数组和NEXTVAL[]数组的值。

三、用C 语言，进行算法设计（45分）
1、2－路归并排序的另一种策略是，先对待排序序列扫描一遍，找出并划分为若干个最大有序子序列，将这些子序列作为初始归并段，设计算法在链表结构上实现这一策略。

2、在平衡二叉排序树的每个结点中增设一个lsize 域，其值为它的左子树中的结点数加1。试写一时间复杂度为O(log n)的算法，确定树中第K小的结点的位置。

3、一个四则运算表达式以有向无环图的临接表方式存储，每个操作数原子都有单个字母表示，设计算法输出其逆波兰表达式。