中国海洋大学命题专用纸（首页）04－05学年第1学期试题名称：数据结构专业年级：物理、海洋技术02级学号姓名授课教师名李华分数一、填空题（每空2分，共20分）1、在顺序表中插入或删除一个元素，需要平均移动个元素，具体移动的元素个数与有关。2、n个顶点的连通图至少有条边。3、设无向图的顶点个数为n，则该图最多有条边。4、对某二叉树进行前序遍历的结果为abdefc,中序遍历的结果为dbfeac,则后序遍历的结果为。5、栈结构中数据元素之间呈关系。6、深度为k的二叉树至多有个结点。7、快速排序算法的时间复杂度为。8、树中某一结点的度是该结点的。9、一棵二叉树中度为1的结点个数为8，度为2的结点个数为10，该二叉树共有个结点。二、简答题（每题10分，共50分）1、已知森林对应的二叉树如下图所示，画出原来的森林，并写出该森林按前序和中序遍历的结果。24a152531cb1g234fed第1题图第2题图2、已给如上无向图，画出其邻接表，并按普里姆算法画出由顶点1开始的最小生成树。（要求体现出每条边被加入的顺序）3、对关键字『may,mar,apr,jul,aug,sep,oct,nov,feb,jan,dec,jun』依次输入，构造二叉排序树。4、已给关键字序列『50，89，27，30，70，100，28，15，60』，写出一趟快速排序结果。5、已知某系统在通信联络中只可能出现10种字符，其出现概率分别为0。03，0，19，0。10，0。09，0．04，0．20，0．14，0．13，0．02，0。06，试设计哈夫曼编码。（要求先画出哈夫曼树）三、算法设计题（每题15分，共30分）1、写出顺序查询算法。（要求监视哨设在高下标一端）2、写出在二叉树中查找按后序遍历第一个结点的算法。（要求用非递归）授课教师命题教师或命题负责人签字院系负责人签字年月日