中国人民公安大学2005年硕士研究生入学考试试题（数据结构）
请将所有答案标明题号，写在答题本上，试题纸上请勿答题。严禁在答题纸密封线以外留下姓名、考号等任何标记，否则该卷无效。

名词解释（每小题5分，共30分）
描述线性表中三个概念的区别:头指针、头结点、首元结点（第1个元素结点）。
数据结构
二叉排序树
关键路径
稀疏矩阵
连通图
单项/多项选择题（每空3分，共30分）
具有N个结点的二叉树的二叉链表结构中，指针域为NULL的数目应为（ ）；
A) N B) 2N
C) N+1； D) 2N+1
假定有T1、T2、T3、T4、T5五个元素进栈，进栈次序为T1T2T3T4T5，不可能的出栈序列有（ ）；
A）T1T2T3T4T5 B）T5T4T3T2T1
C）T1T2T5T3T4 D）T3T2T4T5 T1
E）T3T5T2T4 T1 F）T2T4 T3T5 T1
表达式(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+*/
下列各函数是按照增长率由大至小的顺序排列的是（ ）；
A） B）
C） D）
已知L是带表头结点的单链表，其P结点既不是首结点（第一结点），也不是尾结点:
删除P结点的直接后继结点的语句序列是（ ）；
删除P结点的语句序列是（ ）；
删除首结点的语句序列是（ ）；
删除尾结点的语句序列是（ ）；
P=P→next ;
P→next=P ;
P→next=P→next→next ;
P=P→next→next ;
while P !=NULL { P=P→next ;}
while P→next !=NULL { P=P→next ;}
while P→next !=Q {P=P→next ;}
while P→next→next !=Q { P=P→next ;}
Q=NULL ;
Q=P ;
Q=P→next ;
P=L ;
L=L→next ;
free(Q);
N个结点的集合，利用二叉排序树查找方法的平均查找长度(ASL)的计算公式为（ ）；
A）N+1 B）log2N
C）(N+1)/2 D）1+4 log2N
对下列关键字序列按照起泡排序算法进行排序，则两趟排序后的结果可能为（ ）。
（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】 元素，具体移动元素个数与 【2】 有关。
假设二维数组A[6][8]，每个元素用相邻的4个字节存储，存储器按字节编址，已知A的开始存储位置为100，则数组的存储容量为 【3】 字节；按列优先顺序存储的元素A[2][5]的第一个字节的地址为 【4】 。
一棵深度为5，18个结点的完全二叉树，编号为10的结点的右儿子的编号 【5】 ，其双亲结点的编号为 【6】 。
在一棵有14个结点的完全二叉树中，所含叶子结点的数目为 【7】 个。
对稀疏矩阵的压缩存储，一般包括三元组表和 【8】 两种基本方法。如图（A）所示的稀疏矩阵，试给出它所对应的三元组线性表 【9】 ；
如图（B）所示的有向图，该图有 【10】 个强连通分量。

简答题（每题8分，共40分）
对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始序列。现假设n=7，试问在最好的情况下需进行多少次比较？请说明理由。
试证明:具有n个结点的二叉树的最小深度为 。
在串操作中，执行以下函数会产生怎样的输出结果？
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
判别下面的一个序列是否为堆。如果不是，则把它调整为堆，画出生成堆的调整过程（要求记录交换次数最少，且堆顶元素为最小值）。
（12，70，48，86，24，56，30，92，65，38）
试列出如图（C）中全部可能的拓扑有序序列。

图 (C)
综合设计题（每题15分，共30分）
1. 试利用Dijkstra算法求图（D）中从顶点a到其他各顶点间的最短路径，2. 写出执行算法过程中各步的状态。

图 (D)
3. 假设用于通信的电文只使用A，4. B，5. C，6. D，7. E，8. F这六个字母组成，9. 字母在电文中出现的频率依次为4，10. 2，11. 6，12. 8，13. 3，14. 2。按照要求完成如下任务:
1）试为这6个字母设计哈夫曼编码和等长二进制编码方案，给出两种编码的对照表。
2）求出这两种编码的带权路径长度WPL，比较两种方案的优缺点。
3）给出哈夫曼树的逻辑结构。