中国人民公安大学2005年硕士研究生入学考试

　　试题(数据结构)

　　请将所有答案标明题号，写在答题本上，试题纸上请勿答题。严禁在答题纸密 封线以外留下姓名、考号等任何标记，否则该卷无效。

　　一、 名词解释(每小题5分，共30分)

　　1. 描述线性表中三个概念的区别：头指针、头结点、首元结点(第1个元素结点 )。

　　2. 数据结构

　　3. 二叉排序树

　　4. 关键路径

　　5. 稀疏矩阵

　　6. 连通图

　　二、 单项/多项选择题(每空3分，共30分)

　　1. 具有N个结点的二叉树的二叉链表结构中，指针域为NULL的数目应为( )；

　　A) N B) 2N

　　C) N+1； D) 2N+1

　　2. 假定有T1、T2、T3、T4、T5五个元素进栈，进栈次序为T1T2T3T4T5，不可能 的出栈序列有( )；

　　A)T1T2T3T4T5 B)T5T4T3T2T1

　　C)T1T2T5T3T4 D)T3T2T4T5 T1

　　E)T3T5T2T4 T1 F)T2T4 T3T5 T1

　　3. 表达式(15-3)*6/3*(20+6)的逆波兰式，正确的是( )；

　　A)15 3 6 3 20 6-*/*+ B)15 3-6 *3/20 6+*

　　C)15 3 - 6 3 20 6+*/* D)15 3-6 3*20 6+*/

　　4. 下列各函数是按照增长率由大至小的顺序排列的是( )；

　　A) B)

　　C) D)

　　5. 已知L是带表头结点的单链表，其P结点既不是首结点(第一结点)，也不是尾 结点：

　　1) 删除P结点的直接后继结点的语句序列是( )；

　　2) 删除P结点的语句序列是( )；

　　3) 删除首结点的语句序列是( )；

　　4) 删除尾结点的语句序列是( )；

　　A) P=P→next ;

　　B) P→next=P ;

　　C) P→next=P→next→next ;

　　D) P=P→next→next ;

　　E) while P !=NULL { P=P→next ;}

　　F) while P→next !=NULL { P=P→next ;}

　　G) while P→next !=Q {P=P→next ;}

　　H) while P→next→next !=Q { P=P→next ;}

　　I) Q=NULL ;

　　J) Q=P ;

　　K) Q=P→next ;

　　L) P=L ;

　　M) L=L→next ;

　　N) free(Q);

　　6. N个结点的集合，利用二叉排序树查找方法的平均查找长度(ASL)的计算公式 为( )；

　　A)N+1 B)log2N

　　C)(N+1)/2 D)1+4 log2N

　　7. 对下列关键字序列按照起泡排序算法进行排序，则两趟排序后的结果可能为 ( )。

　　(Kay, Eva, Amy, Roy, Dot, Jon, Kim, Boy)

　　A)(Amy, Eva, Dot, Jon, Kay, Boy, Kim, Roy)

　　B)(Amy, Boy, Dot, Eva, Jon, Kay, Kim, Roy)

　　C)(Eva, Amy, Kay, Dot, Jon, Kim, Boy, Roy)

　　D)(Eva, Amy, Dot, Roy, Jon, Boy, Kim, Kay)

　　三、 填空题(每题2分，共20分)

　　1. 在顺序存储结构的线性表中，插入或删除一个元素需要平均移动 【1】 元 素，具体移动元素个数与 【2】 有关。

　　2. 假设二维数组A[6][8]，每个元素用相邻的4个字节存储，存储器按字节编址 ，已知A的开始存储位置为100，则数组的存储容量为 【3】 字节；按列优先顺序存储 的元素A[2][5]的第一个字节的地址为 【4】 。

　　3. 一棵深度为5，18个结点的完全二叉树，编号为10的结点的右儿子的编号 【 5】 ，其双亲结点的编号为 【6】 。

　　4. 在一棵有14个结点的完全二叉树中，所含叶子结点的数目为 【7】 个。

　　5. 对稀疏矩阵的压缩存储，一般包括三元组表和 【8】 两种基本方法。如图 (A)所示的稀疏矩阵，试给出它所对应的三元组线性表 【9】 ；

　　6. 如图(B)所示的有向图，该图有 【10】 个强连通分量。

　　四、 简答题(每题8分，共40分)

　　1. 对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元 素的初始序列。现假设n=7，试问在最好的情况下需进行多少次比较？请说明理由。

　　2. 试证明：具有n个结点的二叉树的最小深度为 。

　　3. 在串操作中，执行以下函数会产生怎样的输出结果？

　　void demonstrate(){

　　StrAssign(s, ‘THIS IS A BOOK’);

　　Replace(s, SubString(s, 3, 7), ‘ESE ARE’);

　　StrAssign(t, Concat(s, ‘S’));

　　StrAssign(u, ‘XYXYXYXYXYXY’);

　　StrAssign(v, SubString(u, 6, 3));

　　StrAssign(w, ‘W’);

　　printf(‘t=’, t, ‘v=’, v, ’u=’, Replace(u, v, w));

　　} //demonstrate

　　4. 判别下面的一个序列是否为堆。如果不是，则把它调整为堆，画出生成堆的 调整过程(要求记录交换次数最少，且堆顶元素为最小值)。

　　(12，70，48，86，24，56，30，92，65，38)

　　5. 试列出如图(C)中全部可能的拓扑有序序列。

　　图 (C)

　　五、 综合设计题(每题15分，共30分)

　　1. 试利用Dijkstra算法求图(D)中从顶点a到其他各顶点间的最短路径，写出执 行算法过程中各步的状态。

　　图 (D)

　　2. 假设用于通信的电文只使用A，B，C，D，E，F这六个字母组成，字母在电文 中出现的频率依次为4，2，6，8，3，2。按照要求完成如下任务：

　　1)试为这6个字母设计哈夫曼编码和等长二进制编码方案，给出两种编码的对照 表。

　　2)求出这两种编码的带权路径长度WPL，比较两种方案的优缺点。

　　3)给出哈夫曼树的逻辑结构。