山东大学2001数据结构考研试题研究生入学考试试题考研真题
● 摘要
山东大学2001
一 判断题
1． 顺序查找法适用于存储结构为顺序或链接存储的线行表。
2． 一个广义表可以为其他广义表所共享。
3． 快速排序是选择排序的算法。
4． 完全二叉树的某结点若无左子树，则它必是叶子结点。
5． 最小代价生成树是唯一的。
6． 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。
7． 存放在磁盘，磁带上的文件，即可意识顺序文件，也可以是索引文件。
8． 折半查找法的查找速度一定比顺序查找法快 。
二 选择题
1．将两个各有n 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A. n B. 2n-1 C. 2n D. n-1
2. 在文件" 局部有序" 或文件长度较小的情况下，最佳内部排序的方法是（ ）。
A. 直接插入排序 B. 气泡排序
C. 简单选择排序 D. 快速排序
3. 高度为 K 的二叉树最的结点数为（ ）。
A. 2
4.一个栈的输入序列是12345，则占的不可能的输出序列是（ ）
A.54321 B. 45321 C.43512 D.12345
5.ISAM文件和V ASM 文件属于（ ）
A 索引非顺序文件 B. 索引顺序文件 C. 顺序文件 D. 散列文件
6. 任何一棵二叉树的叶子结点在先序，中序和后序遍历序列中的相对次序（ ）
A. 不发生变化 B. 发生变化 C. 不能确定 D. 以上都不对
7.已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。
A. acbed B. decab C. deabc D.cedba
三．填空题
1．将下图二叉树按中序线索化，结点的右指针指向（ ），Y 的左指针指向（ ）
E
2．一棵树T 中，包括一个度为1的结点，两个度为2的结点，三个