求：2005年下半年北京市高等教育自学考试数据结构试卷？

数据结构试卷(98年上半年北京市)

一、 单项选择题（在每小题的四个备选答案中选出一个正确的答案，并将其号码填在题干后的号码内，每小题2分，共10分）

1.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（ ） A. 1，3，2，4 B. 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. 12 D. 不确定

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分）