南京理工大学课程考试试卷学生考试用

1、南京理工大学课程考试试卷（学生考试用）课程名称：数据结构学分：3大纲编号062204试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟组卷日期：2007年6月4日组卷教师（签字）张宏审定人（签字）王树梅学生班级：计算机学院05级、选择题（2*20=40分）不是算法的基本特征A）可行性B）长度有限C）在有限时间内完成D）确定性某算法的时间复杂度为0（n2）,表明该算法的A）问题规模是n2B）执行时间等于n2C）执行时间与n2成正比D）问题规模与n2成正比C）不可能是1D）定是1设n个元素进栈序列是P/P2,P3，,p，其输出序列是1,2,3,n,若p3=3，则的值为A）可能是2B）一定

2、是2链表不具备的特点是B）插入、删除不需要移动元素D）所需空间与其长度成正比A）可随机访问任一结点C）不必事先估计存储空间最不合适用作链队的链表。A）只带队首指针的非循环单链表B）只带队首指针的循环双链表C）只带队尾指针的循环双链表D）只带队尾指针的循环单链表设二维数组A610,每个数组元素占用4个字节，若按行优先顺序存放时，数组元素A35的存储地址为1000，则A00的存储地址是A）872B）860C）868D）864以下不是堆的序列是。A）100，85，98，77，80，60，82，40，20，10，66B）100，98，85，82，80，77，66，60，40，20，10C）10，20，

3、40，60，66，77，80，82，85，98，100D）100，85，40，77，80，60，66，98，82，10，20&一棵完全二叉树上有1001个结点，其中叶子结点的个数A）250B）500C）505D）501无向图的邻接矩阵是一个矩阵。A）对称B）零C）上三角D）对角对于含有n个结点的带权连通图，它的最小生成树是指图中任意一个。A）有n-1条权值最小的边构成的子图B）有n-1条权值之和最小的边构成的子图C）有n-1条权值最小的边构成的连通子图D）有n个顶点构成的边的权值之和最小的连通子图有n个结点的线索二叉树上含有的线索数为A）2nB）nTC）n+1D）n若一个有向图中的顶点不能排成

4、一个拓扑序列，则可断定该有向。A）是个有根有向图B）含有多个入度为0的顶点C）是个强连通图D）含有顶点数目大于1的强连通分量关键路径是指AOE网络中A）从源点到汇点的最长路径B）从源点到汇点的最短路径C）最长的回路D）最短的回路对有18个元素的有序表R0至R17，则二分查找R2的比较序列的下标为A）0、1、2B）8、4、1、2C）8、4、2D）8、3、1、2有k个相同的数据，若用线性探测法把这k个数据存入哈希表，至少要进行次探查A）k-1B）kC）k+1D）k（k+1）/2在一棵二叉排序树上查找值为35的数据，以下比较的数据序列正确的为A）28、36、18、46、35B）18、36、28、46

5、、35C）46、28、18、36、35D）46、36、18、28、35快速排序在情况下最不利于发挥其长处A）要排序的数据量太大B）要排序的数据中含有多个相同的值C）要排序的数据已基本有序D）要排序的数据个数是奇数稀疏矩阵采用压缩存储的目的主要是为了。A）表达变得简单B）对矩阵元素的存取变得简单C）去掉矩阵中的多余元素D）减少不必要的存储空间的开销哈希函数构造的原则是：它的函数值应概率的取其值域的每一个值。A）最大B）最小C）同等D）平均树的遍历策略可分为先序遍历和后序遍历（也有称为中序遍历的）；二叉树的基本遍历有二种，即先序、中序和后序。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。

6、结论：“树的序遍历序列与其对应的二叉树的遍历序列相同”是正确的A）先先B）后（中）后C）先中D）先后二、填空题（20分，其余每空2分）n,下面是对无向图的一种操作，其中g是无向图的邻接矩阵，n是图的顶点数，顶点标号为1到n，vi是一个全程变量的一维数组，初值为全0,下面的类C/C+算法tt对图做什么操作（1）。voidtr（gn,v0）/v0是图的顶点号，值范围为1到n之间的整数visit（v0）;/visit是一个函数，完成对给定图顶点的访问viv0T=l;for（i=0;in;i+）if（!vii&gv0-1i）tr（g,i）;voidtt(gn,n)for(i=0;in;i+)vii=0

7、;for(i=0;in;i+)if(!vii)tr(g,i+l);求最短路径的Dijkstra算法若用邻接矩阵表示图，在有100个顶点时如果时间是t,则在400个顶点时，时间大约是（2）。已知一棵完全二叉树共有892个结点，则该二叉树的高度是（3），叶子数是（4），度为1的结点数是（5），最后一个非叶结点的序号是_（）。（注：二叉树结点按自然数顺序从1开始从上到下，同一层从左到右编号）原始数据为（34、90，30，50，23，11，10，100,46）按快速排序算法一趟划分后，数据的排列是（7）。求最小生成树有（8）和（9）两个算法。在一棵5阶B_树中，高度是5（叶子层不算），则这棵B树至少有

8、（10）个结点、简答题（26分）1.（6分）按13、24、37、90、53的次序，a）画出建立平衡二叉树的过程并注明平衡类型（3分）b）画出建立3阶B_树（又称2-3树）的过程（3分）2.3.4.5.6.号是(6)o（13分）有一个AOE网如下:a=710a=2a=8a=710a=614a=13a=48a11=4a=3a=3a=10a=1041213a=41a=55a=29（1）画出该AOE网的邻接表示意图（3分）（2）求出所有事件的最早发生时间与最迟发生时间（4分）（3）列出所有关键活动（3分）（4）把上图看成无向图（忽略弧的方向），求出一棵最小生成树，生成树边权之和为多少？（生成树不需要画出，3分）（4分）有数据13、24、37、90、53,试建立一棵Huffman树并计算WPL。（4分）（3分）简述分块查找的数据组织方式，查找过程。（3分）四、算法设计（用类-C/类-C+描述）（14分）（7分）完成一个二叉树拷贝的递归算法treecopy（d,s）。其中s是源二叉树，d是目的二叉树。（7分）设在n