数据结构试卷98年上半年北京市自学考试试题及答案

数据结构试卷(98年上半年北京市)《自学考试试题及答案》姓名:_____________ 年级:____________ 学号:______________题型选择题填空题解答题判断题计算题附加题总分

数据结构试卷(98年上半年北京市)《自学考试试题及答案》 姓名:_____________年级:____________学号:______________ 计算题 附加题 总分 题型 选择题 填空题 解答题 判断题 得分 评卷人 得分 一、单项选择题（在每小题的四个备选答案中选出一个正确的答案，并将其号码填在题干后的号码内， 每小题2分，共10分） 1.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（）A.1， 3，2，4B.2，3，4，1C.4，3，1，2D.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.9B. 11C.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分） 1.设待排序文件的关键码为（512,275,908,677,503,765,612,897,154,170）以第一元素为分界元素进 行快速排序（按关键码值递增顺序），请给出一趟扫描后的结果。 2.请画出下面的树所对应的二叉树。 3.从一棵空的二叉排序树开始，将以下关键码值依次插入：25,13,15,31,7,20,37，请画出插入全部完成 试卷第1页共2页