南京邮电大学2004年数据结构考研试卷

南 京 邮 电 学 院
攻读硕士学位研究生入学考试
数 据 结 构 试 题
说明：1.本试卷有五类题型：单选、填空、简答、解答、和算法设计题。
2,试卷共4页。所有答题均写在答题纸上（包括单选题和填空题），请务必准确标明所答题的题号。
3.算法设计题使用Pascal或C/C++语言描述，但每位考生只能选用其中一种语言描述。在同一试卷中不允许混用Pascal和C/C++两种语言描述算法，你所使用的描述语言是___________（请考生填写）。
4,算法（程序）中需调用其它函数或过程，必须另行编写，不允许直接调用教材上已实现的过程或函数。

一、单选题（每题3分，共15分）

1、从堆中删除一个元素的时间复杂度为__________。
A.O(1) B.O(log2n) C.O(n) D.O(nlog2n)

2、下面关于二叉树的结论正确的是__________。
A.二叉树中，度为0的节点个数等于2的结点个数加1
B.二叉树中结点个数必大于0
C.完全二叉树中，任何一个结点的度或者为0，或者为2
D.二叉树的度是2。

3、对人以一棵树，设它有n个结点，这n个结点的度数之和为__________。
A.n B.n-2 C.n-1 D.n+1

4、设X是树T的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是__________。
A.在树T中，X是其双亲的第一个孩子
B.在树T中，X一定无右边兄弟
C.在树T中，X一定是叶子结点
D.在树T中，X一定是左边兄弟

5、连通的无向图G有n个顶点，则图G的最小生成树的边数为__________。
A.n B.n-1 C.n*(n-1)/2 D.n/2

二、填空题：（每题5分，共40分）

1、设a=6，b=4，c=2，d=3，e=2，则后缀表达式abc-/de*+的值为____________。

2、设有元素序列的入栈次序为：（a1，a2，…an），其出栈的次序为：（ap1，ap2，…apn），现已知p1=n，则p1=___________。

3、设对一棵二叉树进行三种次序的遍历（结点的值为字母，大小按字母顺序），已知其中序和后序遍历的结果分别d b e a f c g 和 d e b f g c a ，则先序遍历次序是___________。

4、在有序表（22，29，33，39，42，47，50，65，68）中以对半查找方法查找元素39，40，则元素间的比较次数分别为___________和___________。

5、简单选择算法的最好和最坏情况时间复杂度分别为___________和___________。

6、设有一个二维数组A[m][n]（二维下标为[0..m-1，0..n-1]）。假定每个元素占一个空间，元素A[0][0]和A[2][2]的存储位置分别为644和676（十进制数），则元素A[3][3]的存储位置为___________。