中国人民公安大学2005年数据结构试题 | |||||||||
---|---|---|---|---|---|---|---|---|---|
http://www.sina.com.cn 2005/11/30 20:26 爱考网 | |||||||||
中国人民公安大学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)给出哈夫曼树的逻辑结构。
[上一页] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] |