漳州师范学院2013年硕士研究生入学考试试题数据结构部分.PDF

漳州师范学院 2013 年硕士研究生入学考试试题 考试科目：计算机专业基础 注意事项： 1 150 3 、本卷满分为 分，考试时间为 小时； 2 、本卷属试题卷，另有答题纸，答案一律写在答题纸上，写在该试卷或草稿纸上均无 效； 3、必须用蓝黑钢笔或签字笔答题，其他均无效。 ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ 数据结构部分 1、 填空题 （每题2 分，共 20 分） 1. 具有 200 个结点的完全二叉树，其高度为_____ （注：空的二叉树高度 为-1，非空的二叉树高度为其左、右子树的高度的较大者加 1）。 2．某二叉树的后序遍历序列为 DBECA, 中序遍历序列为BDAEC,则先序遍历 序列为_______. 3. 与树相对应的二叉树必为其右子树为_______ 的二叉树。 有向图用邻接矩阵 存储， 的第列的所有元素之和等于顶点 的 。 4. A A i i _______ 5. G 是一个非连通无向图，共有 22 条边，则该图至少有_______个顶点。 6. 在作出栈运算时应先判别栈是否_______; 7. 已知数组A[0..29, 0..29] 的每个元素占4 个存储单元，将其按行优先次序 存储在起始地址为 2000 的连续的内存单元中，则元素A[6 ，8]的地址为_______ 。 8. 已知一个无向图的邻接矩阵表示，计算第j 个顶点的度的方法是______ 。 9. 设串 S1=’ABCDEF’，S2=’TXYZ’，函数con(x，y)返回x 串和y 串的连接串 subs(s，i，j)返回串 s 的第i 个字符起长度为j 的子串，len(s)返回串 s 的长度， 则 con(subs(S1，2，len(S2))，subs(S1，len(S2)，2))的结果串是_______. 10. 单链表中删除 q 结点的直接后继结点的语句是： p=q-next; _______________; free(p); 2、 应用题 （每题15 分，共 45 分） 1. 已知某系统在通讯中只可能出现七种字符A,B,C,D,E,F,G，其出现的概率分 别为 0.20, 0.06, 0.13, 0.12, 0.30, 0.10, 0.09，试为这些字符设计Huffman 编码. 2. 试采用 Prim 算法，画出下图所示的最小生成树的生成过程 (从顶点 A 开始)。 第 1 页 共 4 页 3 ．已知某图的邻接表如下： 0 F 1 2 7 1 G 6 4 5 2 0 3 3 H 0 5 4 I 5 J 1 6 6 K 1 6 7 L 1 2 7 M 3 1 4 5 0 1) 画出该邻接表所对应的图； 2) 分别写出其深度优先搜索序列和广度优先搜索序列。 3、 算法设计题 （15分） 设有一个由整数组成的带头结点的无