中国人民公安大学2005年数据结构试题

文章作者 100test 发表时间 2007:02:25 10:32:23
来源 100Test.Com百考试题网

中国人民公安大学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)给出哈夫曼树的逻辑结构。