淮阴工学院数据结构期末试卷A.doc

淮 阴 工 学 院 课 程 考 试 试 卷班级 姓名 学号 -装-订-线-专业： 通信工程 课程名称：数据结构学分：3.5试卷编号（A）课程编号： 1311050 考试方式： 闭卷 考试时间： 100 分钟拟卷人(签字)： 拟卷日期：2006,12,25审核人(签字)： 得分统计表：题 号一二三四五六七八九十总 分得 分得分阅卷人一、填空题：（每空1分，共10分）1. 数据的存储结构种类包括。2. 分析以下部分代码的时间复杂度用大O表示法为 。 int i=1; s=0; while(inext=s；s-next=p-next； Bsnext=pnext；pnext=s；Csnext=pnext；pnext=snext； Ds-next=p+1；p-next=s； 19对于图1的有向图，以下 是正确的拓扑排序序列。A1，2，3，4，5，6 B6，5，4，3，2，1C3，2，4，5，6，1D3，5，2，4，6，120若有10个结点的有向图是强连通图，则最少有 条边。A8 B9 C10 D11得分阅卷人三、判断题（正确的打，错误的打）（10小题，共10分）（ ）1. 数据结构中，数据的存储结构是与所使用的计算机无关的。（ 对 ）2. 顺序存储方式也能用于存储非线性结构。（ ）3. 栈是一种插入、删除操作限于在表的一端进行的线性表，是一种先进先出的结构。（ 对 ）4. 对一棵非空二叉树，它的根结点是第1层，则它的第i层上最多能有2 i-1个结点。（ ）5. 图的邻接表存储结构适用于稠密图的情况。（ ）6. 图的深度优先遍历序列是唯一的。（ ）7. 拓扑排序就是按照关键字的递增次序进行的排序方法。（ 对 ）8. 散列查找的平均查找长度ASL与元素个数n无关。（ ）9. 冒泡排序的时间复杂度为O(nlogn)。（ 对 ）10. 完全二叉树按自上而下，从左到右给结点编号（从1开始，共n个），则编号最大的分枝结点的编号是n/2。得分阅卷人四、简答题（6小题，共50分）1待排关键字序列为21, 58, 1,29, 17, 43, 99, 33, 12，请分别给出用快速排序和简单选择排序的过程。 （本题8分）2用三元组表表示下列稀疏矩阵： （本题6分）3设哈希（Hash）表的地址范围为010，哈希函数为：H（K）K % 11。K为关键字，用线性探测法再散列法解决冲突，输入关键字序列： （27，45，53，28，42，91，60，58，37）造出Hash表，试回答下列问题： （本题10分）1466165235554632图2（1） 画出哈希表的示意图；（2） 若查找关键字60，需依次与哪些关键字进行比较？（3） 计算查找成功时的平均查找长度ASL。 4对图2的带权无向图，画出采用Prim算法（从顶点1开始）构造最小生成树的过程。 （本题10分）5假设用于通信的电文仅由8个字母组成，字母a,b,c,d,e,f,G,h在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试构建相应的哈夫曼树（按左子树根结点的权小于等于右子树根结点的权的次序构造），为这8个字母设计哈夫曼编码，并计算平均码长。（本题8分）6给定二叉树T的两种遍历序列，分别是：前序遍历序列： A，D，B， E，C，H，F，G，I 中序遍历序列： A，B，C， E，H，D，G，I，F试画出二叉树B，并写出二叉树的后序遍历序列。（本题8分）得分阅卷人四、数据结构与算法设计题（10分）1 二叉树采用二叉链表结构存储，有创建二叉树、前序遍历二叉树、中序遍历