山东大学数据结构2004考研试题研究生入学考试试题考研真题
● 摘要
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,
求树的叶子结点数。