山东大学计算机考研真题集
2004年 山东大学硕士研究生入学考试数据结构试题
一、简答题：
1、10分 （1）数据结构和数据类型的区别，一个好的数据结构类型有哪几个标准？
（2）顺序和链式存取的特点是什么，什么时候顺序存取有优势？
2、12分 g（m，n）= 0 (m=0,n>=0)
= g(m-1,2n)+n (m>=0,n>=0)
写出递归算法并画出 g(5,2)的栈的变化。
3、8分 求下列算法里@区域的 时间执行频度和整个算法最时间复杂度。
X=0,y=0;
For (i-1;i++;i<=n) {
If odd(i)
@{ for(j=i;j++;j<=n) x++;
For(j=i;j++;j<=i) y++; }
}
4、10分 a(x)=7+3x+9x^8+5x^17 b(x)=8x+22x^7-9x^8
(1) 画出a(x)和b(x)的单链表的存储表示，做一下结构说明。
(2) 执行插入删除运算得出a(x)+b(x)的存储表示，利用a(x)和b(x)原有的空间。
5、6分 有中序线索2叉树序列cbedahgijf,后续序列：cedbhjigfa,画出前序、中序和后序的线索二叉树。
6、6分 树的度为m，度为1的结点数为N1, 度为2的结点数为N2, 度为m的结点数为Nm,
求树的叶子结点数。
7、8分 无向图G=（V，E），G的各顶点的度>=2，证明这个无向图中一定含有回路。
8、10分 求关键路径。
9、8分 平衡2叉树中的插入元素调整平衡的过程。
10、8分，什么是哈希表？冲突可能与哪些因素有关？为什么？
11、8分 有5000个无序列的元素，如果要快速选择最大的10个元素，那么在快速、堆、归并、基数、希尔排序中哪个最好，为什么？
12、10分 n个不同的英语单词排序，长度均为m,n>>50,m<5,那种排序方式最佳？为什么？
二、算法设计题目：
1、8分 写折半查找（2分法）的递归算法
2、8分 三叉堆（同去年的题目）
3、10分 设计选举人得票数，按得票数输出，一张选票只能选一个被选举人，一共有n个被选举人，m张选票。
4、8分 P是中序线索2叉树的非根接点，写出不用栈删除P的子树的算法。
5、12分 写出2叉中序非递归的算法。
山大计算机考研笔记\山东大学2004操作系统笔记.doc山大计算机考研笔记\山东大学04数据结构辅导笔记.doc
山大计算机考研笔记山东大学计算机考研真题（99---04）\山东大学04数据结构试题.doc山东大学计算机考研真题（99---04）\shandongdaxue20011.doc山东大学计算机考研真题（99---04）\shandongdaxue2001.doc山东大学计算机考研真题（99---04）\shandongdaxue1998.doc山东大学计算机考研真题（99---04）\shandongdaxue1993.doc山东大学计算机考研真题（99---04）\shandongdaxue1992.doc
山东大学计算机考研真题（99---04）\sdui01ds.zip山东大学计算机考研真题（99---04）\sdui00ds.zip山东大学计算机考研真题（99---04）\sdu03osbiji.zip山东大学计算机考研真题（99---04）\sdu03dsbiji.zip
山东大学计算机考研真题（99---04）\sdu03ds.rar山东大学计算机考研真题（99---04）\sdu02dsbiji.zip山东大学计算机考研真题（99---04）\sdu02ds.zip山东大学计算机考研真题（99---04）\sdu01ds.zip山东大学计算机考研真题（99---04）\sdu00ds.zip山东大学计算机考研真题（99---04）
