南理工计算机系数据结构2005数据结构B

课程名称：数据结构学分： 3 大纲编号 062204 试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟 组卷日期：2007年6月4日组卷教师（签字）张宏审定人（签字）王树梅 学生班级：计算机学院05级 一、选择题（2*20=40分） 1.对于链队，在进行删除操作时， A) 仅修改头指针 B) 仅修改尾指针 C)头、尾指针都修改 D) 头、尾指针都可能修改 2.二维数组A中，每个元素的长度为3个字节，行下标从0到9，列下标从0到11，则连续存放该数组至少需要字节 A)100 B）240C)360 D)340 3. 一棵有124个叶子的完全二叉树，最多有个结点 A)247 B)248 C)249 D)250 4.利用3,6,8,12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权利路径长度为 A) 55B)29 C)58D)39 5．一个堆是一棵二叉树 A）普通 B)排序 C）满 D）完全 6．在一个有向图的邻接表中，每个顶点链表中结点的个数等于该定点的 A) 入度 B) 出度 C)度 D)度数减1 7．下面程序段的时间复杂度是。 for(i=1;i18．就排序算法所用的辅助空间多少而言，下面正确的是 A) 堆排序>快速排序>希尔（Shell）排序 B) 堆排序<希尔（Shell）排序<快速排序 C) 堆排序>希尔（Shell）排序>快速排序 D) 堆排序>快速排序>希尔（Shell）排序 19．哈希表R范围是R[0]到R[13], 哈希函数H(key)=key%11。已有4个数据15，38，61，84在表中，位置分别在R[4],R[5],R[6],R[7],如果用二次探测再散列，数据49的位置是 A)R[8] B)R[2]C)R[5] D)R[9] 20．树的遍历策略可分为先序遍历和后序遍历（也有称为中序遍历的）；二叉树的基本遍历有三种，即先序、中序和后序。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论：“树的序遍历序列与其对应的二叉树的序遍历序列相同”是正确的 A)后（中） 先 B)后（中） 中 C)先 中D) 先 后 二、填空题（26分,每空2分） 1． 下面是对无向图的一种操作，其中adj是无向图的邻接表，n是图的顶点数，顶点标号为1到n，visited是一个全程变量的一维数组，初值为全0，下面的类C/C++算法，tr1对图做什么操作 （1） 。 void tr(adj,v0)// v0是图的顶点号，值范围为1到n之间的整数 { visit(v0); //visit是一个函数，完成对给定图顶点的访问 visited[v0-1]=1; for(p=adj[v0-1].firstarc;p!=NULL;p=p->nextarc) if(!vi[p->adjvex-1]) tr(adj,p->adjvex); } void tr1(adj,n) { for(i=0;i3．（9分）有一个AOE网如图-3： 1 100 3 6 60 120 2 1 2 80 40 4 1 2 4 1 图-2 3 2 5 图-3 （1） 求出所有事件的最早发生时间与最迟发生时间（3分） （2） 列出所有关键活动（3分） （3） 画出该AOE网的逆邻接表（3分） 四、算法设计（用类-C/类-C++描述）（14分） 1．(7分)完成一个在根为tree的二叉排序树中插入数据x的算法insert (tree,x)。(二叉排序树结点的三个域为：左、右孩子lchild与rchild，数据域dada) 2．(7分)有n个结点的有向图（图的顶点号为1至n）用邻接表表示， 试完成从图中删去弧的算法DelArc(adj,u,v)。(注：（1）为简便，假定弧是存在的（2）adj为邻接表表头数组，数组下标从0计（3）结点的数据域名称可自己命名)

第3页共 3 页