2012.1数据结构试卷(A).docVIP

华南农业大学期末考试试卷（A卷） 2011-2012学年第 1 学期　 考试科目： 数据结构 考试类型：（闭卷）考试　　　 考试时间：　120 　分钟 学号 姓名 年级专业 题号 一 二 四 总分 得分 评阅人 考生须知： 答案必须写在答卷上，写在试卷上不得分； 考试结束时，只回收答题卡，不回收试卷； 必须在答题卡上正确填写班级、学号、姓名等内容，否则没有考试成绩。 得分 一、选择题（本大题共 10 小题，每小题2分，共20分） 1、以下数据结构中，哪一个是线性结构？（ ） A．广义表 B．二叉树 C．稀疏矩阵 D．串 2、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=i=n+1)。 A．O(0) B．O(1) C．O(n) D．O(n2) 3、输入序列为ABC，为BA时，经过的栈操作为（ ）。A．push, pop, push, pop, push, pop B．push, push, poppush, pop, pop C．push, push, pop, pop, push, pop D．push, pop, push, push, pop, pop 4、模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（ ）。 A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2、设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ ）。 A．(n2/2)+(n/2)-1 B．(n2/2)+(n/2) C．n2 D．2n-1 、假设以行序为主序存储二维数组A=array[0..99，0..99]，设每个数据元素占2个存储单元，基地址为10，则[5，5]=（ ）。 A．808 B．818 C．1010 D．1020 、某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则前序序列是：（ ）。 A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对 、根据使用频率为5个字符设计的哈夫曼编码不可能是（ ）。 A．0，100，101，110，111 B．0000，0001，001，01，1 C．000，001，010，011，11 D．00，01，10，110，111 、采用分块查找时，若线性表中共有1225个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（ ）个结点最佳。A．15 B．25 C．35 D．313 1、以下序列不是堆的是（ ）。 A．(100,85,98,77,80,60,82,40,20,10,66) B．(100,98,85,82,80,77,66,60,40,20,10) C．(10,20,40,60,66,77,80,82,85,98,100) D．(100,85,40,77,80,60,66,98,82,10,20)得分 二、应用题（本大题共 5 小题，每题6分，共30分）假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI中序序列为BCDAFEHIG。请画出该二叉树举例说明顺序队的假溢出现象，简要叙述循环队列的数据结构，并说明判定循环队列的队空条件和队满条件。已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态（）和终态（）。（生成的哈夫曼树权值左孩子小右孩子大，权值相等时编号小的先取） 字符 weight Parent lch rch 字符 weight Parent lch rch 1 1 2 2 3 3 … … 关键字序列为{19,14,2