问题:2005年下半年北京高等教育自学考试数据结构试卷？

1.选择题(从每题四个备选答案中选择一个正确答案，并在题后填入数字，每题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 .(NLOG 2n)b . o .(N2)c . o .(LOG 2n)d . o .(N)。

4.如果一棵二叉树有10个度为2的节点，那么该二叉树的度为0的节点数是()A.9b.11 C.12 D .不确定性。

5.在下面对B树和B+树的描述中，A树和B+树都是平衡多叉树，B树和B+树都是可以用于文件的索引结构的说法是不正确的。C树和B+树都可以有效地支持顺序检索，D树和B+树都可以有效地支持随机检索。

二、填空(每空2分，***20分)

1.从逻辑结构上看，线性表比较典型，树比较典型。

2.二维数组A的存储地址为，元素A的存储地址为。

3.如果一棵有n个节点的完全二叉树的所有节点按层次顺序从1到n编号，那么当I小于n时，节点I的右兄弟是一个节点，否则节点I没有右兄弟。

4.求具有最小加权外部路径长度的扩展二叉树的算法称为算法。在堆排序中构建堆的方法称为。

在5.6阶B树中，每个节点最多包含一个键码，除了根节点和叶节点，每个节点至少包含一个键码。

三。简答题(每道小题6分，***18分)

1.请简述哈希函数在哈希存储中的作用，并举例说明哈希函数。

2.请简述哈希存储中处理碰撞(冲突)的两种基本方法。

3.请简要描述负载系数的定义。为什么加载因子是hash方法存储的重要参数？

四、解决以下问题(每道小题6分，***30分)

1.设待排序文件的键码为(512，275，908，677，503，765，612，897，154，170)，以第一个元素为划分元素进行快速排序。

请画出下列树对应的二叉树。

3.从一个空的二叉排序树开始，依次插入下一个键码值:25，13，15，31，7，20，37。请在所有插入后画出二叉排序树。

4.请用下面的加权图画一个最小生成树。

5.对于下面的稀疏矩阵

1)画出它的三重存储表示。2)画出它的行列存储表示法(交叉链表法)。五、算法问题(6分)有一个线性表是以链接的方式存储的。表中每个节点包含两个指针，其节点用PASCAL描述如下:TYPE pointer =↑node；node = RECORD infdatatypelink1，link2:指针结束；其中link1是指向该节点下一个节点的指针，link2是指向该节点上一个节点的指针，如图所示。P和Q都是指针类型的变量。现在表中Q指向的新节点要插在P指向的节点前面(注意:P不是指链表中的第一个节点)。请用PASCAL语句写出插入的关键步骤。部里要求写完整的算法，只要求用几句话写出关键步骤。) 6.填空分析算法(***16分)下面是用PASCAL语言编写的二进制插入排序算法，用整数排序码对线性表进行升序排序。TYPE node =记录键:整数；infdatatype结束；list=ARRAY[1..节点的max];过程binary sort(VAR R:list；n:整数)；VAR temp:节点；low，m，high，I，j:整数；开始nteger开始nteger开始ntegerBEGIN FOR I:= 2 TO n DO BEGIN temp:= R[I]；低:= 1；高:= I-1；而① DO开始m :=(低+高)DIV 2；如果②那么高:=m-1否则③结束；FOR j:= I-1 down to④DO R[j+1]:= R[j]；⑤结束；结束；1.请在下面的算法空白处写下应该填写的正确内容。(10) 12345

2.假设要排序的记录数为n=7。当排序码初始顺序分别为(15，25，35，45，55，65，75)和(75，65，55，45，35，25，15)时，请说明。(假设算法中中项的整数除法采用小数截断的方法。)(6分)