北京 1998年上半年自考数据结构试题内容简介
北京 1998年上半年自考数据结构试题
一、 单项选择题（在每小题的四个备选答案中选出一个正确的答案，并将其号码填在题干后的号码内，每小题2分，共10分）
1.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（ ）
A. 1，3，2，4B. 2，3，4，1 C. 4，3，1，2 D. 3，4，2，1
2.下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？（ ）
A. 直接插入排序 B. 起泡排序 C. 快速排序 D. 直接选择排序
3.对n个记录的文件进行二路归并排序，总的时间代价为
A. O（nlog2n） B. O（n2） C. O（log2n） D. O（n）
4.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（）
A. 9 B. 11 C. 12D. 不确定
5.下面关于B树和B+树的叙述中，不正确的是
A. B树和B+树都是平衡的多分树 B. B树和B+树都是可用于文件的索引结构
C. B树和B+树都能有效地支持顺序检索 D. B树和B+树都能有效地支持随机检索
二、 填空题（每空2分，共20分）
1.从逻辑结构看，线性表是典型的 ，树是典型的 。
2.设有二维数组A[0..9,0..19]，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为，按列优顺序存储，元素A[6,6]的存储地址为 。
3.若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当i为 且小于n时，结点I的右兄弟是结点，否则结点i没有右兄弟。
4.求具有最小带权外部路径长度的扩充二叉树的算法称为 算法。堆排序中建堆的方法称作 。
5.6阶B树中，每个结点至多包含 个关键码，除根和叶结点外，每个结点至少包含个关键码。
三、 简答题（每小题6分，共18分）
1.请简述散列函数在散列法存储中的作用，并举出一个散列函数的例子。
2.请简述散列法存储中处理碰撞（冲突）的两类基本方法。
3.请简述负载因子的定义，为什么说负载因子是散列法存储的一个重要参数？
四、 求解下列问题（每小题6分，共30分）
..............................