04级期末考试试题解答-final.doc

《数据结构》试题 （闭卷） （电信系本科2004级 2005年12月） 题号 一 二 三 总分 题分 40 32 28 100 得分 一、回答下列问题 (每题5分，共40分) 1．算法A的时间复杂度为O(1)，算法B的时间复杂度是O(log2n)，算法A的运算时间一定比算法B少吗？为什么？ 答:不一定.因为① 最好情况下也许O(log2n)会更快;②当n 比较小时,也许O(log2n)会更快. O(1)并非只有1次,只是有限次的意思. 2．二叉排序树的中序遍历序列是有序序列，对吗？反之，如果一棵二叉树的中序遍历序列是有序序列，是否就是二叉排序树，为什么？ 答:前一句正确,后一句未必.例如以下图形就是例外. 10 / \ 10 \ 10 3．前序遍历的平均空间和最坏空间复杂度是多少？从时间效率上看，前序遍历和后序遍历哪一种更费时间，为什么？ 答: 前序遍历的平均空间复杂度是O(log2n), 最坏空间复杂度是O(n); 从时间效率上看，前序遍历比后序遍历更费时间，原因是前序便历入栈次数多一些。 4．由1001个结点构成的二叉树，何种型态叶子结点最多，何种叶子最少？分别给出叶子结点个数和度为1结点的个数。 答: 完全二叉树形态时叶子结点最多，单枝树时叶子最少。 5．采用一个辅助空间的堆排序算法对关键字序列{46，37，65，96，75，11，25，48}排序，如果排序结果为逆序，请给出初始堆。 答：排序结果若是逆序，则说明初始堆必为小根堆。 46 65 96 75 11 25 48 6．设有一个动态分配顺序栈S，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为多少？ 答：1+1-1（+1-1）（+1-1）（+1+1）-1-1-1————至少为3 7．如果借用一个布尔变量tag作为标志，能否以tag为0或1来区分尾指针和头指针值相同时循环队列的状态是“空”还是“满”？如果能，请写出队空和队满的判断条件。 答：能。 rear++; tag=1; if(rear==front) tag=1 then(队满)； front++; tag=0; if(rear==front) tag=0 then(队空)； 8．快速排序在什么情况下最快？什么样情况下最慢？在最慢的情况下请提出一种提高效率的解决办法。 答：快速排序在完全无序（大小交错）的情况下最快，在完全有序的情况下最慢。在最慢的情况下的解决办法，可以选择有序序列正中的元素作为中枢。 二、综合题（4小题，共32分） 1．已知下图的深度优先和广度优先有哪些信誉好的足球投注网站的输出前2个结点是①、②，请写出深度优先和广度优先的输出序列。（6分） 答： 2．哈夫曼树是带权路径长度之和最小的树，但现在要求带权路径长度之和最大的树，你认为应该怎样求？请写出设计思路。假设字符a,b,c,d,e,f的使用频度分别是0.07, 0.09, 0.16, 0.18, 0.23, 0.27，请画出对应的WPL最大的树并计算WPL的值。 （10分） 答： 3．设一个哈希表包含hashSize=13个表项，其下标从0到12，采用线性探测法解决冲突Hi=(H(key)+di)% hashSize, di=1,2,3,4,…, hashSize-1。请按以下要求，将下列关键码散列到表中。 10，100，32，45，58，126，3，29，200，0（1）哈希函数采用除留余数法，用%hashSize（取余运算）将各关键码映像到表中。请指出每一个产生冲突的关键码可能产生多少次冲突。（2）?若哈希函数 H(key)=(3*key－11)%hashSize映像到表中，画出哈希表。? （8分） 答： 4．下面是某人设计的判断是否完全二叉树的算法，p是根结点，指出下面算法的错误（不需写出正确的算法）（8分） Boolean Iscomplete(BiTree p) { if p == NIL return(TRUE)； if (p-lchild != NIL p-rchild ==NIL) return(TRUE); if (p-lchild == NIL p-rchild !=NIL) return(FALSE) else return (Iscomplete(p-lchild) Iscomplete (p-rchild)