一些资料奉送给06年想考山大计算机的 (外加答疑)

zhangbingzhi

这些资料并不完整，更没有答案，一切仅供参考。本人也是从外校考到山大的，深知资料的重要性，无奈当今天下卖题者多，真心助人的少。特贴出一些我搜集的资料，你看了如果觉得好请顶一下，如果觉得不好也不要怪我，我的资料就这些了。如果大家有什么疑问，可以写在后面，我尽我所能解答。很多资料都来自网上，是很多有心人共同努力的结果。

先贴05年的试题，可能是对大家最有帮助的内容:
我先说一道:
  第二题:
  2、已知下面函数:
  int undown (* A,n)
      {  if n<=1 return 0;
      if A[0]<A[1] return 1;
      return undown (A+1,n-1);
     }
    （1） 请说出上面函数的功能，及时间复杂度。
  （2） 已知a＝{11,56,3,2,5,8,49,7,1},求结果。

AVL树的定义
高度为h的AVL树最少有多少结点，最多有多少结点
n个结点的高度？

一组数据,给出快速排序的排序结果,如果有序,快速排序的轴选择对时间复杂性的影响

11题 A,B为单链表队列,设计算法使A=A交B,给出算法

13题  给出递归算法求图中所有顶点间最小路径的算法

B＋树的插入，删除，如何计算磁盘读写的次数
一个二叉树的中序和后序序列，写出创建树的算法
写出递规求最短路径的方法，并证明为什么是最短的（同上面那个）
上三角和下三角矩阵计算元素的位置
散列表概念，冲突和什么相关？
单链表队列，只有一个tail指针，写出入队和出队算法
对二叉树中序遍历，写出begin()和 next()两个函数
单链表的元素为整数，按照奇数，偶数分成两个链表
给出一个数列，用快速排序法写出排序过程，并证明对已经有序的序列退化为O(n2)

[ 本帖最后由 控制面板 于 2006-10-31 00:27 编辑 ]

zhangbingzhi

题目虽然多，但新题形很少，很多题目出现在各种习题集和辅导资料中。B+树的磁盘读写问题必须要看机械出版社的那本老外写的书。最上面那道题如果不会做，说明你程序的阅读能力不强，要加强训练。

zhangbingzhi

03年也是kybird整理的。
2003数据结构试题回忆版
简答：
1。链表、顺序表的定义、性质、优缺点，及适用对象。
2。找关键路径
3。顺序把1，2，。。。，2^n-1输入空平衡二叉树中，证明所的是一棵满/完全二叉数
4。顺序排列的一组数中，用快速排序，证明分界点取在中点时速度最快（好象这样） (证明：快速排序算法若每次都选较短的先排，则额外空间复杂度可为logn。)
5。 根据前序、中序，确定一二叉树，并前序、中序、后序线索化。
6。
7。
8。
9。
10。
11。
12。
13.
14.
15.
算法：
1。判断一棵树是否二叉查找树 （同2002年数据结构一个算法题目）
2。判断回文
3。建立三阶堆
4。找二叉树上2个接点的共同祖先
5。矩阵中找鞍点
6。一字符串，判断其是否对称
7。求树的深度

[ 本帖最后由 控制面板 于 2006-11-9 10:08 编辑 ]

zhangbingzhi

03年和04年的题比较像，应该是同一个题库，05年开始换了新教材，题库也有较大的变化，当时考完之后，就听一个考生说" 怎么以前考的一道也没考？“

所以说05年的题对06有较大的参考意义，03，04的就稍微差一些。（个人分析）

zhangbingzhi

下面这个也是摘自以前的贴子

山东大学2004计算机研究生入学考试专业课辅导班《数据结构》笔记
> 04年形势：
> 1、1-5章占50分，6+7章50分，其余50分，第8、11章不考，除3.3、5.7、12.5、12.6外其余带*号的均不做要求；
> 2、题型为简答和大题的形式，链表+树+链表分值>50%，算法设计题目占40分左右，算法思想题目占10分左右，算法主要集中在链表、树、内部排序，详细见内容；
> 3、今年题量和去年一样大，时间大家要安排好，比较《习题集》上，1、2、3级别的题目占多数，4级题目很少，5级没有。
> 4、今年采取题库的形式，一共15套题目，随机抽取，每套允许有不多于30%的重复，希望大家认真对待历年的试题。
>
> 第一章 绪论
> 1、   基本概念 ：（不会直接考基本概念）
> 数据---数据结构：a、逻辑：集合、线性表、树、图
>         b、物理：顺序、链式
> 抽象数据类型（不用写很全的描述）
> 2、   算法分析：（思想表达，语言细节不重要，注意要加上适当的注释）
> a、时间复杂性 （计算语句的执行频度）
> b、空间复杂性 （排序的辅助空间）
>
> 第二章  线性表
> 1、   线性表的定义、顺序、链式结构的特点（优点、缺点）。
> 2、   顺序表存储地址表示：loc(ai)=loc(a1)+(i-1)l. 及简单操作。
> 3、   链表（单、双、循环）的相关算法 （插入、删除、逆置、前负后正、结点倒换等）最好画出示意图，标指针与边界情况（表头与其它的特殊情况）
> a、一般单链表
> b、循环单链表（最后空指针指向头）
> c、双向链表（仅要求基本操作）
> 4、多项式相加：看课本43页算法
>
> 第三章 栈和队列
> 1、   栈的结构特点：顺序存储的结构表示，空满条件，链式存储基本操作。
> 2、   栈的应用（书中的例子不考，不用看）双端队列不要求。
> 3、   利用栈实现递归的工作原理及栈的变化，具体的转化不做要求
> 4、   队列的结构特点
> a、 链式
> b、 顺序---循环队列（假溢出情况而导致循环队列）
>
>
> 第四章 串
> 1、   串的基本算法（书中），基本函数库复合算法，由基本的操作，实现一个复杂的操作（P72），
> 存储相关不要求。
>
> 第五章 数组、广义表
> 1、   数组的定义及存储表示：一维、二维、按行、列存储先，特殊矩阵（?值相同或零元素在距阵的分布有一定规律）的表示。
> 2、   稀疏矩阵：定义、用途、结构表示、三元组和转置表示，十字链表的结构表示，算法不要求。
> 3、   广义表：定义及存储结构表示。画出结构，常见的递归算法，对5.7.3不做要求、对建立广义表不做要求。
>
> 第六章 树和二叉数
> 写算法时可描述一下算法思想和写算法所需要的结构。
> 1、   树的定义及相关概念。
> 2、   二叉树的定义、性质
> 性质：参数，不同度接点数，父子关系。
> 存储：顺序：按完全编号；链式：二、三叉。
> 3、   ▲二叉数的遍历序列及算法。
> 递归、非递归，前中后层次遍历（非递归），非递归时栈的变化。
> 4、线索二叉树的作用、特点、画法、遍历算法（重点是中序）（线索化及中插入、删除、建立不考）
> 5、一般树、森林与二叉树的转化及遍历。
> 6、哈夫曼树：思想与构造方法，算法不做要求。
> 7、二叉树的一般算法（遍历基础上的变形）
> 算法：链表、串、树、广义表，但链表，排序时会要求复杂性，树要求递归非递归。
> 常见算法有求：结点数，结点所在层次，点的双亲点。遍历算法基础上的算法，利用树递归的性质，特点，如换左右子树及求深度等，主要看习题集！！！
>
> 第七章   图
> 概念、比较、应用、算法的思想、实现、应用、时空复杂度分析
> 1、   图的定义：有向图，无向图，度，路径，回路，顶点的度和边的关系，生成树的定义，DFS，BFS，AOV，AOE，拓扑排序
> 2、   图的存储结构：邻接惧阵（对角线上有时为0，有时为无穷，但是意思一致）、邻接表。
> 3、   算法以及相关应用：
> A．   图的DFS，BFS思想、实现、示例，两种不同存储结构的时间空间复杂度分析，对某一特定图是BFS还是DFS最优，与树的哪些遍历类似。
> B．   最小生成树：定义，二种算法的思想、实例，复杂度分析，实现掌握其核心，证明这种算法能得到最小生成树且不会有回路，是否唯一？（生成树不唯一，只有代价唯一）；最大生成树，适用于什么样的存储结构，两算法分别适用于图的什么情况？
> C．   DAG，AOV拓扑排序的定义、思想、实现、实例、复杂度分析，正确性的证明，借助堆，栈，队列结构实现以及其栈深度，算法为什么就是DAG（证明）
> D．   AOE的定义，关键路径的定义，思想，算法的关键路径实现步骤（递归公式），实例。复杂度分析（n与e的关系），永远处于关键路径上的活动叫做桥，缩短他一定能缩短关键路径，桥具有什么样的特点？
> E．   最短路径：1、单原点的思想，关键步骤的实现、证明，如何证明最短？如何修改下一最短呢？，实例的实现，时间复杂度的分析。2、所有顶点间的：思想，实例，算法关键步骤实现，谁和谁做比较？复杂度分析，为什么一定是最短路径？
>
> 第九章 查找
> 1、   关键字，HASH，二叉排序树，AVL树，B树，B+树
> 2、顺序表查找
> A、折半查找查找，思想，实现，实例，存储结构，时空分析，对数据有何要求，成功不成功的分析
> B、分块查找思想，复杂度的分析
> C、二叉排序树基本算法的实现都要掌握（查找、插删，判断，比较，判层次），查找成功不成功的时间复杂度分析，内外结点间的关系
> D、AVL树：定义，调整算法，实例，复杂度（结果）
> E、B 树B+树的定义、区别、插入、删除的过程
> F、HASH表定义，构造，查找的分析（不成功），冲突适应情况，解决冲突的办法（线性探测，链地址），查找分析及装填因子，冲突与何有关？
>
> 第十章   内部排序
> 1、概念：排序、稳定、不稳定、内部外部排序，基本分类、比较移动是两个关键步骤，也是算法分析的出发点，顺序存储、连接，静态表（较少）
> 2、   插入排序：思想、实现、实例、数据结构
> 3、   希而排序：算法的思想、实例、复杂度分析结论结果
> 4、   快速排序：思想、实现、实例、时间复杂度、效率分析
> 5、   选择排序：算法，思想、实现、实例都掌握
> 6、   归并排序：思想、算法实现、实例
> 7、   基数排序：思想、实例
>
> 第十一章    文件
> 1、ISAM文件：数据组织，B+树实例，了解
> 2、多关键字文件，多丛表与倒排表的组织
>
> 总结：
> 1、证明 反证法、递归、递推、数学归纳法
> 2、解决同一个问题时方法的比较，如排序对存储，对时间复杂度的要求
> 3、对算法的推广：如一些树，多叉树对应的顺序，链试存储结构及相应算法的变换，数据排列局部有序时采用哪种查找比较好， 如何查找？
&Oslash;4、辅助数据结构的选用，栈、队列有什么不同？是否可以互相替代？

[ 本帖最后由 控制面板 于 2006-11-9 10:08 编辑 ]

zhangbingzhi

虽然过去两年多了，教材也换了，但04年的这份笔记对外校的考生仍然有极高的参考价值。从这份笔记再结合最近3年的试题，可以看出山大出题的几个特点：
1 考的多是些基本知识，几乎没有新题。只要对各种题型烂熟于心，考出高分不难。
2 证明题每年都会考，有些证明题就是课本上的。
3 题量非常大，答题的时候留给你思考的时间很少，所以要提高答题速度。
4 改卷很松，所以不会的题也不要放弃，尽量答。

zhangbingzhi

看到这儿你对山大出题的特点应该有所明白了吧？再不明白我也没辙了。对付专业课这些资料应该够了，辅导班是不会有的，大家不要指望了。

fatxp

楼主贴出好东西！

泉韵心生考验板块，买题的广告那个多阿，
那些卖题的不会是骗人的吧。


加精！！！！！！阿！！！！！

[ 本帖最后由 fatxp 于 2005-9-3 17:18 编辑 ]

fatxp

请问楼主

我看那本机械工业的，还需要看清华的那本么？

zhangbingzhi

原帖由 fatxp 于 2005-9-3 17:10 发表
请问楼主

我看那本机械工业的，还需要看清华的那本么？

机械那本比清华的难度大多了，吃透机械的足够了（个人意见）