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

《南京理工大学课程考试试卷学生考试用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、南京理工大学课程考试试卷（学生考试用）课程名称：数据结构学分：3大纲编号062204试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟组卷日期：2007年6月4日组卷教师（签字）张宏审定人（签字）王树梅学生班级：计算机学院05级一、选择题（2*20=40分）1.对于链队，在进行删除操作时，A)仅修改头指针B)仅修改尾指针C)头、尾指针都修改D)头、尾指针都可能修改2.二维数组A中，每个元素的长度为3个字节，行下标从0到9，列下标从0到11，则连续存放该数组至少需要字节A)100B）240C)360D)3403.一棵有124个叶子

2、的完全二叉树，最多有个结点A)247B)248C)249D)2504.利用3,6,8,12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权利路径长度为A)55B)29C)58D)395．一个堆是一棵二叉树A）普通B)排序C）满D）完全6．在一个有向图的邻接表中，每个顶点链表中结点的个数等于该定点的A)入度B)出度C)度D)度数减17．下面程序段的时间复杂度是。for(i=1;i

3、上所含结点的个数不小于A)2hB)2h-1C)2h-1D)2h+19．在一个带头结点的循环双向链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改个指针域A)2B)3C)4D)610．下面叙述中不正确的是。A)任何关键活动不按期完成就会影响整个工程完成时间B)任何一个关键活动提前完成，将使整个工程提前完成C）所有关键活动提前完成，将使整个工程提前完成D）所有关键活动按期完成，整个工程也按期完成11．用二分查找表中查找一个数据的速度比用顺序查找A)必然块B)必然慢C)相等D)不能确定12．对图进行广度优先遍历时，通常采用来实现算法

4、A)栈B)队C)树D）图13．具有2000个结点的二叉树的最小深（高）是A)9B)10C)11D)1214．对有序表(3,6,8,10,12,15,16,18,21,25,30)中，用二分查找数据11,需要比较次A)2B)3C)4D)515．在一个二叉树的中序遍历中，根结点的右边只有结点A)右子树上的所有B)右子树上的部分C)左子树上的所有D)左子树上的部分16．在一棵平衡二叉树中,每个结点的平衡因子数的取值范围是A）-1到1B）-2到2C）1到2D）0到117．将两个各有n个元素的有序表归并为一个有序表，至少比较次数是。第3页共3页A)

5、nB)2n-1C)2nD)n-118．就排序算法所用的辅助空间多少而言，下面正确的是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．树的遍历策略可分为先序

6、遍历和后序遍历（也有称为中序遍历的）；二叉树的基本遍历有三种，即先序、中序和后序。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论：“树的序遍历序列与其对应的二叉树的序遍历序列相同”是正确的A)后（中）先B)后（中）中C)先中D)先后二、填空题（26分,每空2分）1．下面是对无向图的一种操作，其中adj是无向图的邻接表，n是图的顶点数，顶点标号为1到n，visited是一个全程变量的一维数组，初值为全0，下面的类C/C++算法，tr1对图做什么操作（1）。voidtr(adj,v0)//v0是图的顶点号，值范围为1到n之间的整

7、数{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);}voidtr1(adj,n){for(i=0;i

8、的左边数据依次是(2)，7的右边数据依次是(3)。3．从邻接矩阵A=可以看出，该图有（4）个顶点。如果是有向图，该图有（5）条弧，若是无向图，该图有（6）条边。13424．有向图如图-1所示：