1 / 6 华南农业大学期末考试试卷（A 卷）2011-2012学年第 1 学期考试科目：数据结构考试类型：（闭卷）考试考试时间：120 分钟学号姓名年级专业题号一二三四总分得分评阅人考生须知：1.答案必须写在“答卷”上，写在试卷上不得分；2.考试结束时，只回收答题卡，不回收试卷；3.必须在答题卡上正确填写班级、学号、姓名等内容，否则没有考试成绩。一、选择题（ 本大题共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 ，输出序列为BCA 时，经过的栈操作为（）。A ．push, pop, push, pop, push, pop B．push, push, pop, push, 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 5、设 S 为一个长度为n 的字符串， 其中的字符各不相同，则S 中的互异的非平凡子串（非空且不同于S 本身的串）的个数为（）。A．(n2/2)+(n/2)-1 B．(n2/2)+(n/2) C．n2D．2n-1 6、假设以行序为主序存储二维数组A=array[0..99 ，0..99]，设每个数据元素占2 个存储单元，基地址为10，则 A[5 ，5]= （）。A． 808 B．818 C．1010 D．1020 7、某二叉树中序序列为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．上面的都不对得分8、根据使用频率为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 9、采用分块查找时，若线性表中共有1225 个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（）个结点最佳。A ．15 B．25 C．35 D．313 10、以下序列不是堆的是（）。A ． (100,85,98,77,...
VIP
