《数据结构2008年A卷解析》由会员分享，可在线阅读，更多相关《数据结构2008年A卷解析（10页珍藏版）》请在金锄头文库上搜索。
1、信息学院本科生20072008学年第二学期数据结构期末考试试卷(A卷)专业：_年级：_学号：_姓名：_成绩：_得 分 一、 选择题（本题共25分）1. （1分）简单队列对数据处理的方式是_。A. 先来先服务B. 后来先服务C. 先来后服务D. 以上均不对2. （2分）下面哪些问题的求解应用了栈？_。A函数调用时保存函数的参数、局部变量等。B检查括号匹配。C图的宽度优先搜索。D基于深度优先搜索的图的拓扑排序过程。3. （2分）通过相邻元素比较交换进行排序的算法，如插入排序、起泡排序等，其平均时间复杂性最好只能达到_。AQ(n)BQ(nlogn)CQ(n2)DQ(n3)4. （2分）基数排序要求每
2、阶段的排序算法是_。A稳定的B不稳定的CA、B皆可D以上均不对5. （2分）f(n)=O(n)，g(n)=O(n)，下面哪些等式成立？_Af(n)+g(n) = O(n)Bf(n)-g(n) = O(n)Cf(n)/g(n) = O(1)Df(n) = O(g(n)6. （2分）采用Hash技术，下面哪些操作性能不佳？_A搜索给定关键字。B按关键字升序排列输出所有元素。C删除给定关键字的元素。D输出关键字升序排列位于第k位的元素。7. （4分）7个关键字的4阶B-树有几种可能的结构？_A8B9C10D118. （2分）二叉搜索树中一个节点两棵子树均非空，删除它可转换为删除_或_。A该节点的左子
3、树的最左节点B该节点的左子树的最右节点C该节点的右子树的最左节点D该节点的右子树的最右节点9. （2分）设有一个双端队列deque，允许在队列的两端进行插入和删除操作。可以形象地把双端队列看作是两个对底的栈。设双端队列的输入顺序是1,2,3,4,5,6，以下结果中_不可能是双端队列的输出结果。A. 1 2 3 4 5 6B. 2 4 3 6 5 1C. 1 5 2 4 3 6D. 4 2 1 3 5 6E. 1 2 6 4 5 3F. 5 2 6 3 4 110. （3分）下述编码_具有前缀特性：A. A=0, B=1, C=01, D=10, E=11, F=100B. A=0, B=10,
4、 C=1111, D=11101, E=111101, F=110C. A=1110, B=101, C=01, D=10, E=11, F=100D. A=0, B=1, C=01, D=011, E=11, F=11011. （3分）以下序列_是堆？A.100，86，48，73，35，39，42，57，66，21B.12，70，33，65，24，56，48，92，86，33C.103，97，56，38，66，23，42，12，30，52，6，26D.5，56，20，23，40，38，29，61，35，76，28，100得 分 二、 画出下面程序段运行过程中，栈myStack的变化情况，假定
5、初始时为空（本题共5分）myStack.push(4);myStack.push(3);Integer num = myStack.pop();myStack.push(7);myStack.push(2);myStack.push(5);myStack.push(9);Integer num = myStack.pop();myStack.push(num);myStack.push(9);得 分 三、 对下面的整数列表，利用基数排序算法整理为递增序列，写出每趟分配收集的过程，及最终排序结果（本题共6分）44，97，76，29，13，7，50，9，20，61得 分 四、 一个反对称矩阵A是一
6、个nn的矩阵，且对所有满足，即（）。为反对称矩阵设计高效的存储方案，使用一个一维数组a保存它。（本题共6分）得 分 五、 对下面这棵树，回答下列问题。（本题共14分）1) （2分）指出根节点和叶节点。根节点：_叶节点：_2) （2分）指出节点D的父节点、孩子节点和兄弟节点。父节点：_孩子节点：_兄弟节点：_3) （4分）将它转换为二叉树。4) （6分）给出转换后的二叉树的先序、中序和后序遍历的结果。先序遍历：_中序遍历：_后序遍历：_得 分 六、 一个文件中出现的字符及它们出现的频率如下表所示，为它们构造Huffman编码，需要画出Huffman树。（本题共8分）字符aeist空格回车频率10
7、151234131得 分 30124356251015386310710201678910814121833七、 对下面AOE，回答下列问题。（本题共16分）1) （8分）求出每个事件和每个活动的最早开始时间和最迟开始时间；2) （2分）完成该工程至少需要多少时间？_3) （4分）求出该工程的所有关键活动；_4) （2分）求出该工程的关键路径。_得 分 八、 漏失栈（drop-out stack）的动作与栈很类似，只是当已经保存最大个数元素（n）时，如果第n+1个元素入栈，则栈底的元素丢失。使用循环数组实现漏失栈，试完成入栈、出栈操作。（本题共8分）第9页，共10页得 分 九、 有一种起泡排序算法的变形称为gap（间隔）排序，每次扫描表时它不是比较表中相邻的元素，而是比较位置相隔某个值（i）的元素，其中i是小于n的一个整数。例如，第一个元素应与第(i+1)个元素进行比较，第二个元素应与第(i+2)个元素进行比较，第n个元素应与第(n-i)个元素进行比较，等等。当所有能比较的元素都比较过时，完成一次迭代。下一次迭代中，i减去一个大于1的一个值，继续这个过程，直到i小于1时为止。（本题共12分）第10页，共10页
