浙 江 大 学
二○一○年攻读硕士学位研究生入学考试试题
考试科目 计算机专业基础(A 卷) 编号 878
注意:答案必须写在答题纸上,写在试卷或草稿纸上均无效。
第一部分:数据结构(共 60 分)
一、单项选择题(每题 2 分,共 24 分)
1、 h 为不带头结点的单向链表。在 h 的头上插入一个新节点 t 的语句是:
A. t->next=h; h=t; B. h=t; t->next==h;
C. t->next==h->next; h=t; D. h=t; t->next==h->next;
2、 设一个栈的输入队列是 1、2、3、4、5。若第一个输出的元素是 4,则最后一个输出的
元素是:
A. 1 B. 5 C. 1 或 5 D. 以上都不是
3、 某二叉树的前序遍历序列和中序遍历序列正好相反,则该二叉树一定是:
A. 任一节点无左孩子 B. 任一节点无右孩子
C. 只有一个根节点 D. 不存在
4、 在一个用数组表示的完全二叉树中,根节点下标为 1,那么下标为 17 和 19 节点的最近
公共祖先的下标是:
A. 1 B. 2 C. 4 D. 8
5、 如果森林 F 采用“儿子-兄弟”表示法对应的二叉树是 16 个节点的完全二叉树,问:森
林 F 中树的数目和最大树的节点个数分别是多少?
A. 2 和 8 B. 2 和 9 C. 4 和 8 D. 4 和 9
6、 下面关于 m 阶 B 树说法不正确的是:
A. 最低一层节点数一定大于其它各层节点数的总和;
B. 非叶结点均有不小于 m/2 个儿子;
C. 最大值一定在叶节点上;
D. 当插入一个数据项引起 B 树节点分裂后,树并不一定会长高一层。
7、 若 AVL 树的节点数是 21,则该树的高度至多是多少?(只有一个根节点的树高度为 0)
A. 4 B. 5 C. 6 D. 7
8、 设一段文本中包含对象{a,b,c,d,e},其出现次数相应为{3,2,5,1,1},则经过哈夫曼编码后,
该文本所占总位数为:
A. 40 B. 36 C. 25 D. 12
9、 已知有向图 G={V,E},其中 V = {v1,v2,v3,v4,v5,v6},E = {<v1,v2>,<v1,v3>,<v2,v5>,
<v2,v6>,<v3,v4>,<v3,v5>,<v4,v5>,<v5,v6>}。下面哪个序列是 G 的拓扑序列:
A. v1,v2,v4,v3,v5,v6 B. v1,v3,v4,v5,v2,v6
C. v1,v3,v4,v2,v5,v6 D. v1,v2,v4,v5,v3,v6
10、在求解有向图的关键路径问题时,如果该有向图用邻接矩阵表示且第 i 列值全为∞,则:
A. 如果关键路径存在,第 i 个顶点一定是起点;