文档介绍：京邮电学院
2003年攻读硕士学位研究生入学
数据结构试题*
说明：：填空题，解答题和算法设计题.
所有答题均写在答题纸上（包括填空题），请务必准确标明答题
的题号。 -
算法设计题使用Pascal或C/C素时，再去判定待查元素与表中元素是否相等，从而确定搜索成功与失败。
（1）请写出实现上述算法的Pascal语言或C/C++语言描述的韭送四函数
（或过程）。要求先使用类型说明准确描述你所使用的有序表的顺序结构。
（2）设以数组A存储一个长度为10的有序表,试画出以你的算法对A 进行对半查找的二叉判定树。该二叉判定树上每个圆形结点代表一次元素间的比较。方形结点代表算法终止（成功或失败）・
南京邮电学院
2004年攻读项士学位研究生入学 .*■ - 数据结构试题 *■
说明：：单选、填空,简犯解答和舞法设计题.
(包括堆选题和珑空题｝,请务必准确标明所答题的题号.
算法设计题；知 Pasod或C/CfT描述，但每位考里只能选
用其中一种语"5■翳述［在同一试卷中不允许源用PascalC/C++角种语 ■语*是 " (请考生O),
算法(程序)中需调用共他函毂或过程,必须另行嫡骂，不允许直接调用教材上已实现的过电或踵款.
»
一、单选题(每题3分，共15分)
L从堆中删除一个元素的时间复杂度为・
A. 0(1) B. 0(log:n) C* 0(n) D. O(nlog2n)
下面关于二叉树的结论正确的是・
二叉树中，度为0的结点个数等于度为2的结点个数加1
二叉树中堵点个数必大于0
完全二叉树中，任何一个结点的度或者为。，或者为2
二叉树的度是2
对任意一棵树，设它有n个结点，这h个结点的度数之和
为・
A. n B. n - 2 C. n - 1 D. n + 1
设X是树T中的一个非根结点，中，X是其双亲的右孩子，下列结论正确的是•
在树T中，X是其双亲的第一个孩子
在树T中，X-定无右边兄弟
在树T中，X —定是叶子结点
在树T中，X —定有左边兄弟
连通的无向图G有n个顶点，则图G的最小生成树的边数为*
A, n B. n*l C. n* (n-1) /2 D. n/2
二、填空题K每题5分，共40分)
L 设 a=6, b*4, c-2> d-3, e-2,则后缀表达式 abc*/de*+ 的值为 .
设有元素序列的入栈次序为：(aPaIt...aB),其出栈的次序
为：(apl,ap2, ...apn) > 现已知 pAn,则 pi・ : .
设对一棵二叉树进行三种次序的遍历(结点的值为字母，大小按字母顺序).已知其中'序和后序遍历的结果分别为dbeaf c g和d e b f g c a,则先序遍历次序是・
4 在有序表( 22, 29, 33, 39, 42, 47, 50, 65, 68)中以对半查找方法查找元素39, 40 ,则元素间的比较次数分别为— 和.
简单选择算法的最好和最坏情况时间复杂度分别为和.
设有一个二维数组A[m] [n](二维下标为[0…m-1, 0,.n-l]). 假定每个元素占一个空间，元素A[0] [0]和A[2] [2]的存储位置分别为644和676 (十进制数)，则元素A⑶⑶的存储位置为.
L 一个无向图中，存在一条从顶点u到顶点v的边，则该图的邻接矩阵A中代表该边的元素有 . .若该图中有e条边，则图中所有顶点的度之和是・
&、T是一个散列表，H为散列(哈希). 中的任意一个关键字，经散列函数H映象到地址集合中的任意一个地址的概率是相等的，不同的关键码k^kr若H(k)=H (kJ,这种现案称为・
三、简答题《每题8分，共40分)
1 - ，
I
，通过依次插入元素(V,A,X,CM,P ) 构造过程.
图1表示一个地区的通讯网，也表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的nT条线路，函出所有可能神藻％
设有向图如图匕所示.
画出其邻接矩阵
画出其邻接表箜构路2
' (3)该图是否强连通图
请采用弗洛伊德(Floyd)算法求图2所示的有向图的每对项，保存最短路径长度的二维数组的值.
5・快速排序被认为在已知的排序算法中速度较快的算法.
是否在所有情况下快速排序都优于