DOC《北京化工大学》

北京化工大学 2XXX年攻读硕士学位研究生入学考试 数据结构 试题 注意事项 答案必须写在答题纸上,写在试卷上均不给分.

答题时可不抄题,但必须写清题号. 答题必须用蓝、黑墨水笔或圆珠笔,用红色笔或铅笔均不给分.

一、单项选择题:1~40小题,每小题2分,共80分.下列每题给出的选项中,只有一个选项是最符合题目要求的.请在答题卡上将所选项的字母涂黑. 1. 设n是描述问题规模的非负整数,下面程序片段的时间复杂度是 x = 2;

while (x <

n/2) x = 2*x;

A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2) 2. 设栈S和队列Q的初始状态均为空,元素abcdefg依次进入栈S.若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是bdcfeag,则栈S的容量至少是 A.

1 B.

2 C.

3 D.

4 3. 若元素a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替进行.但不允许连续三次进行退栈工作,则不可能得到的出栈序列是 A:dcebfa B:cbdaef C:dbcaef D:afedcb 4. 某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作,则不可能得到的顺序是 A:bacde B:dbace C:dbcae D:ecbad 5. 元素a, b, c, d, e依次进入初始为空的栈中,若元素进栈后可停留、可出栈,直到所有元素都出栈,则在所有可能的出栈序列中,以元素d开头的序列个数是 A.

3 B.

4 C.

5 D.

6 6. 已知循环队列存储在一维数组A[0..n-1]中,且队列非空时front和rear分别指向队头元素和队尾元素.若初始时队列为空,且要求第一个进入队列的元素存储在A[0]处,则初始时front和rear的值分别是 A. 0,

0 B. 0, n-1 C. n-1,

0 D. n-1, n-1 7. 给定二叉树图所示.设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树.若遍历后的结点序列为3,1,7,5,6,2,4,则其遍历方式是 A.LRN B.NRL C.RLN D.RNL 8. 下列二叉排序树中,满足平衡二叉树定义的是 9. 已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则完全二叉树的结点个数最多是 A.39 B.52 C.111 D.119 10. 将森林转换为对应的二叉树,若在二叉树中,结点u是结点v的父结点的父结点,则在原来的森林中,u和v可能具有的关系是 I.父子关系 II.兄弟关系 III. u的父结点与v的父结点是兄弟关系 A.只有II B.I和II C.I和III D.I、II和III 11. 下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是 12. 在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树,在新平衡二叉树中,关键字37所在结点的左、右子结点中保存的关键字分别是 A:13,48 B:24,48 C:24,53 D:24,90 13. 在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶节点个数是 A:41 B:82 C:113 D:122 14. 对n(n大于等于2)个权值均不相同的字符构成哈夫曼树,关于该树的叙述中,错误的是 A:该树一定是一棵完全二叉树 B:树中一定没有度为1的结点 C:树中两个权值最小的结点一定是兄弟结点 D:树中任一非叶结点的权值一定不小于下一级任一结点的权值 15. 若一棵完全二叉树有768个结点,则该二叉树中叶结点的个数是 A.

257 B.

258 C.

384 D.

385 16. 若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1,则该二叉树的中序遍历序列不会是 A. 1, 2, 3,

4 B. 2, 3, 4,

1 C. 3, 2, 4,

1 D. 4, 3, 2,

1 17. 已知一棵有2011个结点的树,其叶结点个数为116,该树对应的二叉树中无右孩子的结点个数是 A.