南 京 邮 电 学 院
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]的存储位置为___________。 | 
