《数据结构》样卷.docVIP

韩山师范学院2011年专升本插班生考试样卷 计算机科学与技术 专业 数据结构 题号 一 二 三 四 五 六 七 八 总分 评卷人 得分 一、单项选择题（每题2分，共40分）n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要向后依次移 个元素。 A. n- i B. n- i +1 C. n- i -1 D. i 2、若进栈序列为1、2、3、4；进栈过程中可以出栈，则 是不可能的出栈序列。 A.3、4、2、1 B.2、4、3、1 C.1、4、2、3 D.3、2、1、4 3、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂性为 。 A.O(1) B.O(n) C.O(n2) D.O(log2n) 4、从一个具有n个结点的单链表中查找其值等于X结点时，在查找成功的情况下，需平均比较 个结点。 A.n B.n/2 C.（n-1）/2 D.（n+1）/2 5、一个中缀算术表达式为[5 +（7 - X）] * Y，则对应的后缀算术表达式为 。 A.5 7 - + X – Y * B.5 7 X + - Y * C.5 7 X - + Y * D.5 7 X Y - + * 6、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2 个，那么度为0的结点数为 个。 A.4 B.5 C.6 D.7 7、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储。 A.数据的处理方法B.数据元素之间的关系 C.数据元素的类型D.数据的存储方法 A.8 B.15 C.16 D.32 9、在一棵完全二叉树中，若编号为i的结点有右子女，则该结点的编号为 。 A.2i-1 B.2i+1 C.2i-1 D.i/2 10、由权值分别为16,12,19,16,28的叶子结点生成一棵哈夫曼树，它的带权路径长度为 。 A.91 B.126 C.148 D.210 11、以知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为 。 A.4 B.5 C.6 D.7 12、在一个图中，所有顶点的度数之和等于所有边数的 倍。 A.1/2 B.1 C.2 D.4 13、A.5 B.2 C.4 D.1 14、设散列(Hash)函数为H(K)=K MOD 7,一组关键码为（23,14,9,6,30,12，18），散列表T的地址空间为0..6。用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为 。 A. 0 1 2 3 4 5 6 14 6 23 9 18 30 12 B. 0 1 2 3 4 5 6 14 18 23 9 30 12 6 C. 0 1 2 3 4 5 6 14 12 9 23 30 18 6 D. 0 1 2 3 4 5 6 14 23 30 14 18 12 9 15、如果一棵二叉树中任何一个结点的值都小于它的左子树上所有结点的值而大于它的右树上所有结点的值，要得到这棵二叉树中各结点值的递减序列，应按 次序排列结点？ A. 先序 B. 中序 C. 后序 D. 按层 16、在一个具有N个顶点的无向完全图中，包含有 条边。 A.n（n-1）/2 B.n（n-1） C.n（n+1）/2 D.n2 17、在一个3阶的B 树上，每个结点所含的子树数目最多为 ，最少为 。 A. 1，3 B. 2，1 C. 3，2 D. 4，4 18、采用二分查找的方法查找长度为n的有序表时，查找每个元素时平均比较次数 对应的判定树的高度（假定高度大于等于2）。 A.小于 B. 大于 C. 等于 D. 大于等于 19、一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有