哈夫曼树的定义_哈夫曼树的定义

南理工04级至07级数据结构课程期末考试试卷及答案 　　南京理工大学课程考试试卷（学生考试用） 　　课程名称：数据结构学分：3大纲编号062204 　　试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟 　　组卷口期：2006年5月18日组卷教师（签字）补宏审定人（签字）［树林 　　学生班级：计算机学院04级学生学号：学生姓名： 　　一、选择题(1.5*20=30分) 　　1.若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树，则带权路径长度是一 　　A)55B)68C)59D)28 　　2lol1^1G—(VE),.比中.V—(abcdef) 　　E={(a,b),(a,e),(a,ct(b：e),(c,’f)：(‘f,’d)’,(e,’d)},对该图进行广度优先遍历，得到的顶 　　点序列正确的是— 　　A)a,b,e,c,d,fB)a,c,f,e,b,dC)a,e,b,c,f,dD)a,e,d,f,c,b 　　3.对关键字码集合1<={53,30,37,12,45,24,96},从空二叉树出发建立与集合K对应的二 　　叉排序树，若希望得到树的高度最小，应选择下列哪个输入序列。 　　A)45,24,53,12,37,96,30B)12,24,30,37,45,53,96 　　037,24,12,30,53,45,96D)30,24,12,37,45,96,53 　　4.已知一组数{20,8,6,2,30,1}的排序过程为： 　　(1)20,8,6,2,30,1 　　(2)1,8,6,2,30,20 　　(3)1,2,6,8,30,20 　　(4)1,2,6,8,20,30 　　问它是下面那一种排序： 　　A)快速排序B)直接插入排序C)起泡排序D)选择排序 　　5.计算机算法必须具备输入、输出和等五个特征。 　　A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性 　　O确定性、有穷性和稳定性D)易读性、稳定性和安全性 　　6.设哈希表长为14,哈希函数是H(key)=key%ll,表中已有数据的关键字为15,38,61,84共四个, 　　现要将关键字为26的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是一 　　A)8B)3C)2D)9 　　7.在一个单链表中，若要删除p所指结点的后继结点，则执行一。 　　A)p=p->next;p->next=p->next->next 　　B)free(p->next)(C语言格式)或deletep->next(C++语言格式) 　　C)p=p->next->next; 　　D)p->next=p->next->next 　　8.数组A的每个素需要4个字节存放，数组有8行10歹ij,若数组以行为主顺序存放在内存 　　SA开始的存储区中，则A中8行5列的素的位置是一 　　A)SA+74B)SA+292OSA+296D)SA+300 　　9-10.在一棵7阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原 　　有(1)个关键字:若在某结点中删去一个关键字而导致结点合并，则该结点中原有的关 　　键字的个数是(2)。 　　(1)A)6B)5C)4D)3 　　(2)A)4B)3C)2D)1 　　11.已知四个素a,b,c,d依次进栈，进栈过程中可出栈，下面那一种出栈顺序是不正确的— 　　A)a,d,c,bB)b,c,d,aC)c,a,d,bD)c,d,b,a 　　12.队列操作的原则是o 　　A)先进先出B)后进先出0只能进行插入D)只能进行删除 　　13.在有n个结点的二叉链表中，值为空链域的个数为 　　A)n-1B)2n-1C)n+1D)2n+1 　　14.具有1080个结点的完全二叉树的深度为 　　A)12B)10OilD)13 　　15.若已知一个栈的入栈序列是素1,2,3….n,其输出序列为PbP2,P3,…P”,若出是n, 　　则8是() 　　A)iB)n-iC)n-i+1D)不确定 　　16.对于个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 　　A)nB)(n-1)’C)n-1D)n 　　第2页共3页 　　17.对线性表进行二分查找时，要求线性表必须 　　A)以顺序方式存储B)以链接方式存储 　　C)以顺序方式存储，且数据有序D)以链接方式存储，且数据有序 　　18.若用起泡排序对序列｛14,26,29,41,52,5｝从小到大排序,需要次比较 　　A)15B)28C)3D)21 　　19.有一个有序表为｛1,3,9,12,32,41,45,62,70,77,82,95,100｝,当二分查找值62 　　的数据时要次比较成功。 　　A)1B)2C)4D)3 　　20.设双向循环链表中结点的结构为(data,pre,next),若在指针p所指结点之后插入结点s, 　　则应执行下列操作 　　A)p->next=s;s->pre=p;p->next->pre=s;s->next=p->next; 　　B)p->next=s;p->next->pre=s;s->pre=p;s->next=p->next; 　　C)s->pre=p;s->next=p->next;p->next=s;p->next->pre=s; 　　D)s->pre=p;s->next=p->next;p->next->pre=s;p->next=s; 　　二、填空题(19分，其余每空1分) 　　1.已知h是无表头结点的单链表，且p结点既不是首结点，亦不是尾结点，试从F列提供答 　　案中选择合适的语句序列(给出序号)： 　　a.在p结点后插入s结点的语句序列是(1) 　　b.在p结点前插入s结点的语句序列是(2) 　　C.在表首插入S结点的语句序列是⑶ 　　d.在表尾插入S结点的语句序列是⑷ 　　(1)p->next=s; 　　(2)p->next=p->next->next; 　　(3)p->next=s->next; 　　(4)h=s; 　　(5)p=h; 　　(6)s->next=NULL; 　　(7)q=p; 　　(8)while(p->next!=NULL)p=p->next; 　　(9)while(p->next!=q)p=p->next; 　　(10)p=q; 　　(11)p=h;s->next=h; 　　(12)h=p; 　　(13)s->next=p->next; 　　2.图的遍历分为⑸和⑹。 　　3.假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA,则先序序列为： 　　_______________Q)_________________。 　　4.深度为k的完全二叉树至少有3个结点；至多有(9)结点。 　　5.在一棵二叉树中，度为1的结点有40个，总的结点数为99,则二叉树中叶子结点数共有一 　　(10)Q 　　6.在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂时，则左边结点有 　　(11)个关键字:右边结点的关键字数是(12)。 　　7.求图的最小生成树有两种算法，(13)算法适合于求稀疏图的最小生成树。 　　8.一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对 　　结点编号，则编号最小的叶子的序号是(14)；编号是i的结点所在的层次号是(15)(根 　　所在的层次号规定为1层)。 　　三、简答题(35分) 　　1.已知有向图的带权矩阵为： 　　00 　　0000 　　COco00000000 　　 　　00000050020 　　0000 　　1）（3分）画出该有向图。 　　2）（3分）按Dijkstra算法，给出从顶点1（顶点标号从1计）到其余顶点的最短路 　　径长度以及经过的中间点。 　　3）（3分）画出该图邻接表存储结构示意图。 　　4）（3分）画出对应无向图的最小生成树，给出生成树边权之和。（如果去掉方向后,一对顶 　　点之间有两条以上的边,只保留权值最小的边） 　　2.已知关键字的集合{56,8,15,80,10,22,28,50,60,40,90} 　　（1）（3分）试按给出的序列构造一棵平衡二叉树。 　　（2）（3分）试构造3阶电树。 　　（3）（3分）写出依次删除关键字60,40后的B_树。 　　（4）（3分）按以上数据，用链地址法处理冲突（Hash函数H（key）-key%13）,画出示意图（不 　　要写算法） 　　3.（3分）已知三棵树的森林如下，试把它转化为二叉树 　　AGN 　　//I/ 　　BCHIK0P 　　/I//I 　　DEFLMRST 　　4.（4分）按大顶堆将序列{56,8,15,80,10,22,28,50,60,40,90}调整为堆,写出最后的 　　数据序列 　　5.（4分）给出拓扑排序算法描述（不用写C/C++算法） 　　四、算法设计（用类-C/类-C++描述）（16分） 　　1.（8分）完成一个二叉树左右子树交换的递归算法。 　　2.（8分）设在一个带头结点的双向链表中，所有结点的数据素按值递增顺序排列，写一算法， 　　删除表中所有大于min,小于max的素（若存在）。双链表的定义如下： 　　typedefstructDLnode{ 　　intdata; 　　DLnode*pre,*next; 　　}DLnode; 　　第4页共3页 　　南京理工大学课程考试试卷(学生考试用) 　　课程名称：数据结构学分：3大纲编号062204 　　试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟 　　组卷日期：2006年5月18日组卷教师(签字)秘宏审定人(签字)上树林 　　学生班级：计算机学院04级学生学号：学生姓名： 　　一、单项选择题(1.5*20=30分) 　　1、对于序列(12,13,11,18,60,15,7,18,25,100),用筛选法建堆，必须从值为 　　的数据开始建初始堆。 　　A)100B)12C)60D)15 　　2、若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是一 　　A)9B)11C)12D)不确定 　　3、对某二叉树进行前序遍历的结果为ABDEFC,中序遍历的结果为DBFEAC,则后序遍历的结果为 　　A)DBFEACB)DFEBCAC)BDFECAD)BDEFAC 　　4、5阶B树中，每个结点最多有个关键字。 　　A)2B)3C)4D)5 　　5、设有一个二维数组a[m][n],假设a[0][0]存放位置在644,a[2][2]存放位置在676, 　　每个素占一个空间，则a[4][5]在位置(数组素以行为主存储) 　　A)692B)626C)709D)724 　　6、一棵完全二叉树按顺序方式存储在一维数组chars[]=｛’A’,’B’,’C’,’D’,’E’, 　　’F’,’G’,’H’,’I’JJ’)中，则结点E在二叉树的第层。(注：根所在的层 　　为1层) 　　A)1B)2C)3D)4 　　7、下面说法不正确的是 　　A)循环链表从任何•个结点出发，都能访问到所有结点 　　B)一般树和二叉树的结点的孩子数都可以为0 　　C)在拓扑排序序列中，若Vi在匕之前，则必定存在从％到V」的路径 　　D)图(网)的最小代价生成树不是唯一的 　　8、下面说法不正确的说法有个 　　1)队列逻辑上是一个表头和表尾都能插入又能删除的线性表 　　2)有n个顶点的无向图G的最小生成树T就是由G中具有最小权值n-1条边所构造出来的G 　　的子图。 　　3)在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆 　　排序及直接排序法都快。 　　4)哈希表查找无需进行关键字的比较。 　　A)1B)2C)3D)4 　　9、一个堆通常采用存储结构来存储 　　A)顺序B)链接C)索引D)哈希(散列) 　　10、长度为n的线性表中，都有一个直接前驱素。 　　A)任意素B)除第n/2个素C)除第一个素D)除最后一个素 　　11、在由head所指的非空线性链表中删除由p指的链结点的下一个链结点的过程是依次执行 　　q=p->next;;deleteq; 　　A.)p->next=qB)q->next=pC)q->next=p->nextD)p->next=q->next 　　12、稀疏矩阵采用三组方法进行压缩存储的原因是 　　A)0素分布有规律B)非0素分布有规律C)0素多D)非0素多 　　13、已知一个有向图的弧集合为｛<a,b>,<a,c>,va,d>,vb,d>,<b,e>,<d,e>｝，则由该图产生的一种可能 　　的拓扑序列为 　　A)a,b,c,d,eB)a,c,d,e,bC)a,c,b,e,dD)a,c,d,b,e 　　14、对于一个数据序列，按照给定的次序建立一个二叉排序树，该二叉排序树的形状取决于_ 　　A）该序列的存储结构B）序列中的数据素的取值范围 　　C）数据素的输入次序D）使用的计算机的软、硬件条件 　　15、一组数据为（25,48,16,35,79,8423,40,36,72）,现在用某种排序算法进行一趟后的结果如下：1648 　　03672,则采用的是排序 　　A）选择B）快速C）Shell（希尔）D）直接插入 　　16、链表不具有的特点是. 　　A）可随机访问任一素B）插入删除不需要移动素 　　C）不必事先估计存储空间D）所需空间与线性表长度成正比 　　17、在有n个叶子的哈夫曼树中，其结点总数为o 　　A）不确定B）2nC）2n+lD）2n-l 　　18、任何一个无向带权连通图的最小生成树o 　　A）只有一棵B）有一棵或多棵C）一定有多棵D）可能不存在 　　19、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号， 　　根结点的编号为1,则编号为49的结点的左孩子编号为。 　　A）98B）99C）50D）48 　　20、下面说法正确的是 　　1）二叉树的前序遍历序列中，任意一个结点均处于其子孙结点的前面 　　2）一棵树的先序遍历序列同它对应的转换后的二叉树的中序遍历序列相同 　　3）二叉线索树中每个结点都有指向前驱和后继的指针 　　A）1B）2C）1）和3）D）1）和2） 　　二、填空题（1*16=16分） 　　1、已知一有个链表表示的栈，栈顶指针为top,退栈后，对top的操作是（1）（用C/C++语 　　句描述，每个结点的两个域为值域data和指针域next） 　　2、若由3,6,8,12,10构成一棵哈夫曼树，则该树的高度是（2）,带权路径长度为（3）； 　　3、求从指定源点到其余各顶点的最短路径长度的算法中，弧上权须为正的原因是（4）； 　　4.图的（5）遍历是一种递归的算法,图的（6）遍历算法需要使用队列。 　　5.写出两个排序算法的名字,其平均排序时间为0（nlog2n）: 　　_________________（7）_________________。 　　6.有2049个结点的二叉树至少高（8）个结点;最大高度可达（9）。 　　7.在一棵二叉树中，度为1的结点有31个，总的结点数为50,则二叉树中叶子结点数共有一 　　（10）Q 　　8.在一棵11阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂时，则左边结点有 　　（11）个关键字:右边结点的关键字数是（12）o 　　9.快速排序在（13）情况下效率最坏;此时，时间复杂度达到（14） 　　10.一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左向右）用自然数依此对 　　结点编号，则编号最小的叶子的序号是（1序；编号是i的结点所在的层次号是（16）（根 　　所在的层次号规定为1层）。 　　三、简答题（40分） 　　2.已知有向图G有6个顶点（顶点号从1计），弧集E如下：（其中弧后面冒号后数表示弧上的 　　权） 　　E={<1,2>:12,<1,4>:15,<1,5>:8,<2,3>:13,<4,1>:6,<4,3>:25,<4,6>:5,<5,4>:5, 　　<5,6>:20,<6,3>:2,<6,5>:7} 　　完成问题1）至4） 　　1）（3分）画出该有向图。 　　2）（3分）按Dijkstra算法,给出从顶点1（顶点标号从1计）到其余顶点的最短路 　　径长度以及经过的中间点。 　　3）（3分）画出该图邻接表存储结构示意图。 　　4）（3分）上图去除弧上方向（去方向后，若两个顶点有两条边，去权值大的边），画出对应 　　无向图的最小生成树，给出生成树边权之和。 　　第6页共3页 　　2.已知关键字的集合｛56,8,15,80,10,22,28,50,60,40,90｝ 　　（1）（4分）试按给出的序列构造一棵平衡二叉树。 　　（2）（4分）试构造3阶上树。 　　（3）（4分）写出依次删除关键字56,90后的B_树。 　　⑷（4分）按以上数据,用链地址法处理冲突（Hash函数H（key）-key%13）,画出示意图（不 　　要写算法） 　　3.（4分）已知三棵树的森林如下，试把它转化为二叉树 　　AGN 　　//1/ 　　BCHIK0P 　　/1//1 　　DEFLMRST 　　4.（4分）按大顶堆将序列｛56,8,15,80,10,22,28,50,60,40,90｝调整为堆,写出最后的 　　数据序列 　　5.（4分）给出求最小生成树的Kruskal算法描述（不用写C/C++算法） 　　四、算法设计（用类-C/类-C++描述）（14分） 　　1.（7分）完成一个求二叉树叶子的递归算法treeleaf（p）。（p为二叉树根） 　　2.（7分）有n个顶点的有向图用邻接表adj表示，写算法finddegree求出所有顶点的出度,结果 　　放在数组outdegree[i]中（OWiWn）。（outdegree[i]表示顶点i+1的出度，图的顶点号从1计） 　　南京理工大学课程考试试卷（学生考试用） 　　课程名称：数据结构学分：3大纲编号062204 　　试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟 　　组卷日期：2007年6月4日组卷教师（签字）祢宏审定人（签字）工相检 　　学生班级：计算机学院05级 　　二、选择题（2*20=40分） 　　1.—不是算法的基本特征 　　A）可行性B）长度有限C）在有限时间内完成D）确定性 　　2.某算法的时间复杂度为0（r），表明该算法的— 　　A）问题规模是n,B）执行时间等于n,C）执行时间与祐成正比D）问题规模与r?成正比 　　3.设n个素进栈序列是P1,P2,P3,…,Pn,其输出序列是1,2,3,…,n,若p3=3,则Pl的值为_ 　　A）可能是2B）一定是2C）不可能是1D）一定是1 　　4.链表不具备的特点是_____ 　　A）可随机访问任一结点B）插入、删除不需要移动素 　　0不必事先估计存储空间D）所需空间与其长度成正比 　　5.最不合适用作链队的链表是= 　　A）只带队首指针的非循环单链表B）只带队首指针的循环双链表 　　C）只带队尾指针的循环双链表D）只带队尾指针的循环单链表 　　6.设二维数组A[6][10],每个数组素占用4个字节，若按行优先顺序存放时，数组素A[3][5] 　　的存储地址为1000,则A[0][0]的存储地址是一 　　A）872B）860C）868D）864 　　7.以下不是堆的序列是。 　　A）100,85,98,77,80,60,82,40,20,10,66 　　B）100,98,85,82,80,77,66,60,40,20,10 　　O10,20,40,60,66,77,80,82,85,98,100 　　D）100,85,40,77,80,60,66,98,82,10,20 　　8.一棵完全二叉树上有1001个结点，其中叶子结点的个数是 　　A）250B）D）501 　　9.无向图的邻接矩阵是一个矩阵。 　　A）对称B）零C）上三角D）对角 　　10.对于含有n个结点的带权连通图，它的最小生成树是指图中任意一个。 　　A）有n-1条权值最小的边构成的子图 　　B）有n-1条权值之和最小的边构成的子图 　　0有n-1条权值最小的边构成的连通子图 　　D）有一n个顶点构成的边的权值之和最小的连通子图 　　11.有n个结点的线索二叉树上含有的线索数为一 　　A）2nB）n-1C）n+1D）n 　　12.若•个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图。 　　A）是个有根有向图B）含有多个入度为0的顶点 　　O是个强连通图D）含有顶点数目大于1的强连通分量 　　13.关键路径是指A0E网络中 　　A）从源点到汇点的最长路径B）从源点到汇点的最短路径 　　C）最长的回路D）最短的回路 　　14.对有18个素的有序表R[0]至R[17],则二分查找R[2]的比较序列的下标为. 　　A）0、1、2B）8、4、1、2C）8、4、2D）8、3、1、2 　　15.有k个相同的数据，若用线性探测法把这k个数据存入哈希表，至少要进行次探查 　　A）k-1B）kC）k+1D）k（k+l）/2 　　第8页共3页 　　16.在一棵二叉排序树上查找值为35的数据，以下比较的数据序列正确的为 　　A）28、36、18、46、35B）18、36、28、46、35 　　C）46、28、18、36、35D）46、36、18、28、35 　　17.快速排序在情况下最不利于发挥其长处 　　A）要排序的数据量太大B）要排序的数据中含有多个相同的值 　　。要排序的数据已基本有序D）要排序的数据个数是奇数 　　18.稀疏矩阵采用压缩存储的目的主要是为了• 　　A）表达变得简单B）对矩阵素的存取变得简单 　　0去掉矩阵中的多余素D）减少不必要的存储空间的开销 　　19.哈希函数构造的原则是：它的函数值应概率的取其值域的每一个值。 　　A）最大B）最小C）同等D）平均 　　20.树的遍历策略可分为先序遍历和后序遍历（也有称为中序遍历的）；二叉树的基本遍历有三 　　种，即先序、中序和后序。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。 　　结论：“树的—序遍历序列与其对应的二叉树的—序遍历序列相同”是正确的 　　A）先先B）后（中）后C）先中D）先后 　　二、填空题（20分，其余每空2分） 　　1.下面是对无向图的一种操作，其中g是无向图的邻接矩阵，n是图的顶点数，顶点标号为 　　1到n,vi是一个全程变量的一维数组，初值为全0,下面的类C/C++算法tt对图做什么 　　操作（1）。 　　voidtr（g[][n],v0）//v0是图的顶点号，值范围为1到n之间的整数 　　（ 　　visit（vO）;〃visit是一个函数，完成对给定图顶点的访问 　　vi[v0-l]=l; 　　for（i=0;i<n;i++） 　　if（!vi[i]&&g[vO-l][i]）tr（g,i）; 　　voidtt（g[][n],n） 　　（ 　　for（i=0;i<n;i++）vi[i]=0; 　　for（i=0;i<n;i++） 　　if（!vi[i]）tr（g,i+1）; 　　} 　　2.求最短路径的Dijkstra算法若用邻接矩阵表示图，在有100个顶点时如果时间是t,则在400 　　个顶点时，时间去约是（2）。 　　3.已知一棵完全二叉树共有892个结点，则该二叉树的高度是（3）,叶子数是（4）,度 　　为1的结点数是（5）,最后一个非叶结点的序号是（6）。（注：二叉树结点按自然数 　　顺序从1开始从上到下，同一层从左到右编号） 　　4.原始数据为（34、90,30,50,23,11,10,100,46）按快速排序算法一趟划分后，数据 　　的排列是（7）。 　　5.求最小生成树有（8）和（9）两个算法。 　　6.在一棵5阶上树中，高度是5（叶子层不算），则这棵B树至少有（10）个结点 　　三、简答题（26分） 　　1.（6分）按13、24、37、90、53的次序， 　　a）画出建立平衡二叉树的过程并注明平衡类型（3分） 　　b）画出建立3阶也树（又称2-3树）的过程（3分） 　　2.（13分）有一个AOE网如下: 　　（1）画出该AOE网的邻接表示意图（3分） 　　（2）求出所有事件的最早发生时间与最迟发生时间（4分） 　　（3）列出所有关键活动（3分） 　　（4）把上图看成无向图（忽略弧的方向），求出•棵最小生成树，生成树边权之和为多 　　少？（生成树不需要画出，3分） 　　3.（4分）有数据13、24、37、90、53,试建立一棵Huffman树并计算WPL。（4分） 　　4.（3分）简述分块查找的数据组织方式，查找过程。（3分） 　　四、算法设计（用类-C/类-C++描述）（14分） 　　1.（7分）完成一个二叉树拷贝的递归算法treecopy（d,s）。 　　其中s是源二叉树，d是目的二叉树。 　　2.（7分）设在n个数据存在一维数组r中，试写一个算法将数据按原始顺序构造一个带有头结点 　　的双向循环链表。 　　函数名为：Convert（r,la,n）,其中r为存有n个数据的一维数组，la为链表头指针。双 　　向链表的三个域为：数据域data,前向指针prior,后向指针next,数组下标从0计。 　　第10页共3页 　　南京理工大学课程考试试卷(学生考试用) 　　课程名称：数据结构学分：3大纲编号062204 　　试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟 　　组卷日期：2007年6月4日组卷教师(签字)祢宏审定人(签字)3■相检 　　学生班级：计算机学院05级 　　三、选择题(2*20=40分) 　　1.对于链队，在进行删除操作时，— 　　A)仅修改头指针B)仅修改尾指针C)头、尾指针都修改D)头、尾指针都可能修改 　　2.二维数组A中，每个素的长度为3个字节，行下标从0到9,列下标从0到11,则连续存 　　放该数组至少需要一字节 　　A)100B)D)340 　　3.一棵有124个叶子的完全二叉树，最多有个结点 　　A)247B)248C)249D)250 　　4.利用3,6,8,12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权利路径长度为一 　　B)55B)29C)58D)39 　　5.一个堆是一棵二叉树 　　A)普通B)排序C)满D)完全 　　6.在一个有向图的邻接表中，每个顶点链表中结点的个数等于该定点的— 　　A)入度B)出度。度D)度数减1 　　7.下面程序段的时间复杂度是。 　　for(i=l;i<m;i++) 　　for(j=0;j<n;j++)a[i][j]=i*j; 　　A)0(m’)B)O(n’)C)0(m*n)D)0(m+n) 　　8.•棵深度为h的完全二叉树上所含结点的个数不小于— 　　A)2″B)2h-1C)2h-1D)2″‘1 　　9.在一个带头结点的循环双向链表中，若要在p所指向的结点之前插入一个新结点，则需要 　　相继修改一个指针域 　　A)2B)3C)4D)6 　　10.下面叙述中不正确的是。 　　E)任何关键活动不按期完成就会影响整个工程完成时间 　　F)任何一个关键活动提前完成，将使整个工程提前完成 　　a)所有关键活动提前完成，将使整个工程提前完成 　　b)所有关键活动按期完成，整个工程也按期完成 　　11.用二分查找表中查找一个数据的速度比用顺序查找— 　　A)必然块B)必然慢C)相等D)不能确定 　　12.对图进行广度优先遍历时，通常采用来实现算法 　　A)栈B)队C)树D)图 　　13.具有2000个结点的二叉树的最小深(高)是 　　A)9B)10OilD)12 　　14.对有序表(3,6,8,10,12,15,16,18,21,25,30)中，用二分查找数据11,需要比较一次 　　A)2B)304D)5 　　15.在一个二叉树的中序遍历中，根结点的右边只有结点 　　A)右子树上的所有B)右子树上的部分C)左子树上的所有D)左子树.上的部分 　　16.在一棵平衡二叉树中,每个结点的平衡因子数的取值范围是 　　人)-1到113)-2至1]2C)1到2口)0到1 　　17.将两个各有n个素的有序表归并为一个有序表，至少比较次数是一。 　　B)nB)2n-lC)2nD)n-1 　　18.就排序算法所用的辅助空间多少而言，下面正确的是— 　　A）堆排序》快速排序》希尔（Shell）排序B）堆排序〈希尔（Shell）排序〈快速排序 　　0堆排序〉希尔（Shell）排序〉快速排序D）堆排序〉快速排序》希尔（Shell）排序 　　19.哈希表R范围是RW到R[13],哈希函数H（key）=key%ll。已有4个数据15,38,61,84 　　在表中,位置分别在R[位,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分） 　　2.下面是对无向图的一种操作，其中adj是无向图的邻接表，n是图的顶点数，顶点标号为 　　1到n,visited是一个全程变量的一维数组，初值为全0,下面的类C/C++算法，tri对 　　图做什么操作（1）。 　　voidtr（adj,v0）//v0是图的顶点号，值范围为1到n之间的整数 　　（ 　　visit（v0）;〃visit是一个函数，完成对给定图顶点的访问 　　visited[vO-l]=l; 　　for（p=adj[vO-1].firstarc;p!=NULL;p=p->nextarc） 　　if（!vi[p->adjvex-l]）tr（adj,p->adjvex）; 　　voidtri(adj,n) 　　( 　　for(i=0;i<n;i++)visited[i]=0; 　　for(i=0;i<n;i++) 　　if(!visited[i])tr(adj,i+1); 　　) 　　2.假定对数据序列（7,3,5,9,1,12,8,15）进行快速排序，则进行第一次划分后,在7的左边数 　　据依次是（2）,7的右边数据依次是（3）。 　　-010 　　3.从邻接矩阵A=101可以看出，该图有（4）个顶点。如果是有向图，该图有（5） 　　010 　　条弧，若是无向图，该图有（6）条边。m 　　4.有向图如图-1所示： 　　写出一个拓扑序列（7）,添加孤（8）后,则仅可能/ 　　有唯一的拓扑序列。 　　5.由一棵二叉树的先序序列和（9）可唯一的确定这棵二叉树。（3、（2） 　　6.已知完全二叉树的第8层有8个结点（根为第1层），则叶子数V/ 　　为（10）。/ 　　7.Diikstra算法可以求从指定源点到其它各顶点的（11）路径,/ 　　路径长度按（12）序产生，若采用邻接矩阵存储有向图，对于有厂X 　　n个顶点的图而言，算法的时间复杂度是（13）。, 　　三、简答题（20分） 　　a）简单叙述哈希查找的思想，链地址法是如何解决冲突的？（2+3分）图T 　　b）引入平衡二叉树的目的是什么？在图-2中的平衡二叉树中加入70后 　　需要做什么类型的平衡，画出平衡后的二叉树。（2+2+2分） 　　第12页共3页 　　（1）求出所有事件的最早发生时间与最迟发生时间（3分） 　　（2）列出所有关键活动（3分） 　　（3）画出该AOE网的逆邻接表（3分） 　　四、算法设计（用类-C/类-C++描述）（14分） 　　L（7分）完成一-个在根为tree的二叉排序树中插入数据x的算法insert（tree,x）。 　　（二叉排序树结点的三个域为：左、右孩子Ichild与rchild,数据域dada） 　　2.（7分）有n个结点的有向图（图的顶点号为1至n）用邻接表表示，试完成从图中删去弧 　　＜u,v〉的算法DelArc（adj,u,v）。（注：（1）为简便，假定弧＜u,v＞是存在的（2）adj为邻接表 　　表头数组，数组下标从0计（3）结点的数据域名称可自己命名） 　　南京理工大学课程考试试卷(学生考试用) 　　课程名称：数据结构学分：3大纲编号062204 　　试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟 　　组卷日期：2008年4月28日组卷教师(签字)秘宏审定人(签字)上树梅 　　学生班级：计算机学院06级 　　四、选择题(2*20=40分) 　　1、以下不属于算法特性的是— 　　A)可行性B)有输入C)确定性D)健壮性 　　2、下面关于算法的说法正确的是— 　　A)算法最终必须由计算机程序实现 　　B)算法的有穷性是对于任意的一组输入值必须在有穷步骤后结束 　　0算法的可行性是指指令不能有二义性 　　D)以上几个都是错误的 　　3、线性表采用链表存储时，其地址 　　A)必须是连续的B)一定是不连续的C)部分地址必须是连续的D)连续与否均可以 　　4、一个栈的进栈序列是a,b,c,d,e,则栈的不可能输出序列是 　　C)edcbaB)decbaC)dceabD)abcde 　　5、对于链队，在进行删除操作时，o 　　A)仅修改头指针B)仅修改尾指针 　　C)头、尾指针都要修改D)头、尾指针可能都要修改 　　6、设二维数组A[m][n],每个数组素占用k个字节，第一个数组素的存储地址是 　　Loc(a[0][0]),求按行优先顺序存放的数组素a[i][j](OWiWnrl,OWjWn-1)的存储地址为 　　A)Loc(a[0][O])+((i-l)*n-l)*kB)Loc(a[0][O])+(i*n+j)*k 　　C)Loc(a[0][O])+(j*m+i)*kD)Loc(a[0][O])+((j-l)*m+i-l)*k 　　7、如果二叉树T2是由树T1转换而来的二叉树，那么T1中结点的先序就是T2中结点的。 　　A)先序B)中序C)后序D)无对应关系 　　8、一个具有1025个结点的二叉树的高h为 　　A)11B)10C)H到1025D)12到1024 　　9、一棵二叉树的后序遍历序列为EFHIGJK,中序遍历序列为HFIEJKG,则该二叉树根结 　　点的右孩子为。 　　A)EB)FC)GD)H 　　10、n个结点的线索二叉树上含有的线索数为。 　　G)2nB)n-1C)n+1D)n 　　IE堆是一 　　A)完全二叉树B)线性表C)二叉排序树D)平衡二叉树 　　12、假定在一棵二叉树中，度为2的结点数为15,度为1的结点数为30,则叶子结点数为o 　　A)15B)16C)17D)18 　　13、由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 　　A)23B)37C)46D)44 　　14、下面的叙述中，不正确的是 　　A)关键活动不按期完成就会影响整个工程完成时间 　　B)任何一个关键活动提前完成，将使整个工程提前完成 　　0所有关键活动提前完成，则整个工程提前完成 　　D)某些关键活动若提前完成，将可能使整个工程提前完成 　　15、设哈希表长为14,哈希函数为h(key)=key%ll。表中现有数据15、38、61和84,其余位置 　　为空，如果用二次探测再散列处理冲突，则49的位置是 　　A)8B)3C)5D)9 　　第14页共3页 　　16、在一棵二叉排序树上查找值为35的数据，以下比较的数据序列正确的为 　　A）28、36、18、46、35B）18、36、28、46、35 　　C）46、28、18、36、35D）46、36、18、28、35 　　17、下面排序算法中，—算法可能会出现下面情况：初始数据有序时，花费的时间反而最多 　　A）堆排序B）冒泡排序C）快速排序D）希尔（Shell）排序 　　18、任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序。 　　0不发生改变B）发生改变0不能确定D）以上都不对 　　19、如果从无向图的任一顶点出发进行一次图遍历即可访问所有顶点，则该图一定是。 　　A）完全图B）连通图C）有回路D）一棵树 　　20、对有18个素的有序表r[0..17],进行二分查找，则查找r[3]的比较序列下标为 　　A）0、1、2B）8、4、1、208、4、2D）8、3、1、2 　　五、填空题（24分，每空3分） 　　a）下面程序段的时间复杂度为（1）o 　　s=0; 　　for（i=l;i<n;i++） 　　for（j=l;j<i;j++） 　　s+=i*j； 　　2、已知完全二叉树T的第5层只有7个结点，则该树共有（2）个叶子结点 　　3、始数据为（35、97,30,50,23,11,101,100,46）按快速排序算法一趟划分后，数据的 　　排列是（3）。 　　4、n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（4）非零素。 　　5、评价哈希函数好坏的标准是（5）。 　　6、对于关键字序列：12、13、11、18、60、15、7、20、25、100,用筛选法建堆，必须从值为（6） 　　的关键字开始。 　　7、Dijkstra最短路径算法按9J衣次产生路径，在边（弧）上权有（8）值时不能正确工作。 　　三、简答题（25分） 　　23k 　　1、（4分）有0（1）,0（log2n）,0（n）,0（nlog2n）,0（n）,0（n）,•••,0（n）,0（2″）,试用W把它们从左向 　　右连接起来。 　　2、（9分）已知3阶B.树如图所示。 　　（1）画出将关键字88插入之后的B-树； 　　（2）画出将关键字47和66依次插入之后的B-树。 　　题29图 　　3、（4分）简述哈希查找中链地址法解决冲突的方法。 　　4、（8分）有一个AOE网如下: 　　（4）求出所有事件的最早发生时间与最迟发生时间（4分）