山东大学1998数据结构考研试题研究生入学考试试题考研真题
● 摘要
山东大学1998
一，填空。 1．（3分）执行顺序查找时，储存方式可以是 ，二分法查找时，要求线性分块查找时要求线性表，二三列表的查找，要求线性表的存储。
2．（3分）在对称表的存储结构中，每个节点之包含一个指针字段和一个信息字段，这个指针字段存放的节点，又可以很快的求出它的和 。
3．（3分）广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于 。为了区分原子和表，一般用 表示表，表示原子。一个表的长度是指 ，而表的深度是指 。
二，填空并回答问题。
1．（2分）什么是同义词：
2．（2分）什么是堆积：
3．（2分）为避免堆积的发生，可用两遍处理的方法建立散列表，
第一遍
第二遍
三，（9分）选择填空。
1．（4分）二维数组A 的元素都是6个字符组成的串，行下标I 的范围从0到8，列下标J 的范围从1到
10。从供选择的答案中选出应填入下列关于数组储存叙述中（ ）内的正确答案。
（1）存放A 至少需要（ ）个字节。
（2）A 的第8列和第5行共占（ ）个字节。
（3）A 按行存放，元素A[ ]的起始地址与A 按列存放时的元素( ) 的起始地址一致。 供选择的答案：
（1）a 90 b 180 c 240 d 270 e 540
（2）a 108 b 114 c 54 d 60 e 150
（3）A[8,5] A[3,10] A[5,8] A[0,9]
2．（5分）排序的方法有很多种，（ ）法从未排序的序列中依次调出元素与已排序序列中的元素相比较，将其放在已排序序列的正确位置上；（ ）法从未排序序列中挑选元素，并将其依次放入已排序序列的一端；交换排序发式对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换。（ ） 和（ ）是基于这类方法的两种排序方法，而（ ）是比（ ）效率更高的方法。
供选择的答案：
A. 快速排序 B. 选择排序 C. 归并排序 D. 冒泡排序 E. 直接插入排序
四．（5分）判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。
（1）100，85，98，77，80，60，82，40，20，10，66
（2）100，98，85，82，80，77，66，60，40，20，10
（3）100，85，40，77，80，60，66，98，82，10，20
（4）10，20，40，77，80，60，66，98，82，10，20
五．（16分）表插入排序的基本思想是在节点中设一指针字段，插入R1时，R1到Rn 已经用指针安排序码不减次序链结起来，这是采用顺序比较的方法找到Ri 应插入的位置，作链表插入。如此反复，直到把 Rn 插入为止。
（1）（6分）请完成下列表插入的算法：
1．R[0].LINK ( ) ;