数据结构习题集

HEILONGJIANGUNIVERSITYOFSCIENCEANDTECHNOLOGY数据结构习题集、授课教师学生姓名所在班级计算机与信息工程学院第1章绪论11基本内容数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和实现方法；算法的定义、设计的基本要求以及从时间和空间角度分析算法的方法。12学习要点（1）熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。熟悉逻辑结构的四种基本类型和存储结构两种基本机内表示方法。（2）理解算法五个要素的确切含义1）动态有穷性（能执行结束）；2）确定性（对于相同的输入执行相同的路径）；3）有输入；4）有输出；5）可行性（用以描述算法的操作都是可实现的）。（3）掌握计算语句频度和估算算法时间复杂度的方法。13习题1、数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。_是数据的基本单位；_是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为_。2、数据结构主要研究的三个内容为、以及定义在该结构上的。3、数据结构从逻辑结构上可分为线性结构与非线性结构，其中树、图属于。4、数据结构被形式地定义为（D，R），其中D是的有限集，R是D上的有限集。5、数据结构在计算机内存中的表示是指（）A）数据的存储结构B）数据结构C）数据的逻辑结构D）数据元素之间的关系6、线性结构的特点是第一个结点_前驱结点，其余结点有且仅有_个前驱结点；最后一个结点_后继结点，其余每个结点有且仅有_个后继结点。7、树型结构的特点是根结点没有_结点，其余每个结点有且仅有_个前驱结点；叶子结点_后继结点，其余结点可以有_个后继结点。8、图型结构的特点是每个结点可以有_个前驱结点和后继结点。9、常见的时间复杂度有常数阶O1、对数阶OLOG2N、线性阶ON、平方阶ON2、线性对数阶ONLOG2N、立方阶ON3、指数阶O2N等等，这些数量阶之间的大小关系为_。10、算法的五个重要特性是_,_,_,_,_。11、给出以下给定的两个程序段中划波浪线的语句的执行频度（次数）。（1）SUM0FORI0I0个元素的线性结构表示成A1，A2,AN，A1称为_元素，AN称为_元素，I称为AI在线性表中的_。对任意一对相邻结点AI、AI11NEXTFREEQ（3）若L为带头结点的单链表，则A在表首插入S结点的语句序列是B单链表为空的判定条件为（4）若L为不带头结点的单链表，则A在表首插入S结点的语句序列是B单链表为空的判定条件为14、已知L是带表头结点的双向链表L为头指针，结点的后继指针分量为NEXT，前驱指针为PRE,其P结点（P为链表中某结点的指针）既不是首元结点，也不是尾元结点。A）在P结点后插入S结点S为某结点的指针的语句序列是SNEXTPNEXT；SPRESPNEXTSB）在P结点前插入S结点S为某结点的指针的语句序列是SPREPPRESNEXTSPPRESC）删除P结点的直接后继结点的语句序列是QPNEXTPNEXTPFREEQD删除P结点的直接前驱结点的语句序列是QPPREPFREEQE删除P结点语句序列PNEXTPNEXTPREFREEPF在表首插入S结点的语句序列是SNEXTLNEXTLLNEXTS15、在一个循环双向链表L中，结点的两个指针域分别为PRIOR和NEXT（PRIOR为指向前驱的指针，NEXT为指向后继的指针）。指针P所指的结点是双向循环链表L的尾结点的条件是。16、设带头结点的单链表类型定义如下TYPEDEFSTRUCTLNODEELEMTYPEDATA/ELEMTYPE为数据元素类型STRUCTLNODENEXT/后继结点的指针LNODE,LINKLIST（1）函数INVERSELISTL的作用是将一带头结点的单链表实现就地逆置的算法（即利用原来链表的空间，将单链表中的结点按原来相反的顺序存储）。填写空缺使算法完整。VOIDINVERSELISTLINKEDLISTLNEXTNULLWHILEPQPNEXTPQ（2）MERGELISTLA,LB函数的作用是将两个递增有序的带头结点的单链表LA,LB，利用原来的结点空间，合并成一个递增有序的链表LA。填写空缺位置，使此该算法完整。VOIDMERGELISTLINKLISTLNODEPBLBNEXTLNODESLAWHILEIFPADATADATASNEXTPASPAPAPANEXTELSESNEXTPBSPBIFPASNEXTPAELSESNEXTFREELB（3）函数LISTLENGTHL用来求一带头结点的单链表L的长度。请写出此函数的算法代码。17、顺序表的类型定义如下。DEFINELISTINITSIZE100/顺序表存储空间的初始分配量DEFINELISTSPACEINCR20/存储空间的增量，当存储空间不够时用于空间的动态扩充TYPEDEFSTRUCTLELEMTYPEBASEINTLENGTH/顺序表的长度INTLISTSIZE/栈当前的存储空间大小SQLIST/SQLIST为顺序表类型下面给出的是顺序表的插入操作算法，回答下面两个问题。STATUSLISTINSERTSQLISTINTJIFILLENGTH1RETURNERROR/插入位置出错IF/若存储空间已满，则追加存储空间NEWBASELELEMTYPEREALLOCLBASE,LLISTSIZELISTSPACEINCRSIZEOFLELEMTYPEIFNEWBASERETURNOVERFLOW/存储空间扩充失败LBASENEWBASELLISTSIZELISTSPACEINCR/存储空间扩充成功FORJJJ/从最后一个元素到第I个元素依次后移LBASEI1E/在顺序表的第I个位置（下标I1处）插入ELLENGTH/顺序表长度增1RETURNOK（1）填写上述算法的空白处。（2）插入操作算法在平均情况下的时间复杂度是，插入操作算法在各个位置插入元素时平均需要进行的元素后移次数是次。18、顺序表的类型定义如下。DEFINELISTINITSIZE100/顺序表存储空间的初始分配量DEFINELISTSPACEINCR20/存储空间的增量，当存储空间不够时用于空间的动态扩充TYPEDEFSTRUCTLELEMTYPEBASE/LELEMTYPE为顺序表的元素类型，BASE为表示存储空间的动态数组INTLENGTH/顺序表的长度INTLISTSIZE/栈当前的存储空间大小SQLIST/SQLIST为顺序表类型下面给出的是顺序表的删除操作算法，回答下面两个问题。STATUSLISTDELETESQLISTIFILLENGTHRETURNERROR/第I个元素不存在ELBASEI1/若第I个元素存在，由E返回其值FORJJ0INDEXPRINTF“D“,LBASEINDEXFORINTJJNEXTL1L/L1利用L的头结点RL1/尾指针RL2LINKLISTMALLOCSIZEOFLNODE/初始化单链表L2WHILEPNULLQPNEXTRNEXTP/利用尾插法将P结点插入到L1PQNEXT/利用头插法将Q结点插入到L2L2NEXTQ/置L1的链表尾下面再来看第二个例子，这个例子是书中的例24。21、图（A）和图（B）给出了两个用尾指针表示的带头结点的循环单链表R1和R2。请设计一个算法，将这两个循环单链表合并成图（C）所示的一个带头结点的循环单链表R2。R1ANA2A1（A）循环单链表R1R2BMB2B1（B）循环单链表R2（C）合并后的循环单链表ANA2A1R2BMB2B1实现上述功能的算法如下，填写空白语句。VOIDUNIONCIRLISTLINKLISTFREEQ22、查找单链表的倒数第K个结点已知一个带有表头结点的单链表，结点结构为DATALINK假设该链表只给出了头指针LIST，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第K个位置上的结点K为正整数。若查找成功，算法输出该结点的DATA值，并返回1；否则，只返回0。算法设计思路首先统计带头结点的单链表中的结点个数，不包括头结点，假设有NUM个结点，下面只需查找单链表中的第NUMK1个结点即可，该结点就是单链表中的倒数第K个结点。根据上述思想，实现上述功能的算法如下，填写空白语句。TYPEDEFSTRUCTLNODEINTDATA/设结点的数据类型为整型STRUCTLNODELINKLINKLISTINTSEARCHLINKLISTLIST,INTKINTNUM0,J1LINKLISTPWHILEPPPLINKPLISTLINKWHILEPJIFPPRINTF“D“,PDATARETURN1ELSERETURN0上述问题在求解时还有另一种思路，设置两个指针P和Q，初始时都指向首元结点，然后利用Q指针向后查找单链表的第K个结点，找到后Q指向第K个结点，接下来同时向后移动指针P和Q，当Q指向最后一个结点时，P所指向的结点就是我们要找的倒数第K个结点。根据上述思想，实现上述功能的算法如下，填写空白语句。TYPEDEFSTRUCTLNODEINTDATA/设结点的数据类型为整型STRUCTLNODELINKLINKLISTINTSEARCHLINKLISTLIST,INTKINTJ1LINKLISTP,QLISTLINKWHILEQJIFQ/找到第K个结点且Q指向它WHILE/同时向后移动P和Q,当Q指向最后一个结点时结束循环PPLINKQQLINKPRINTF“D“,PDATA/P指向倒数第K个结点RETURN1ELSERETURN023设单链表的类型描述为TYPEDEFSTRUCTLNODEINTDATASTRUCTLNODENEXTLINKLIST编写函数INTMAXCOUNTLINKLISTL,INTX，用以求出以L为头指针的带头结点单链表上值大于X的结点个数并作为函数值返回。第3章栈和队列31基本内容本章介绍了两种重要的操作受限的线性表栈与队列。栈的插入与删除操作均限制在栈顶端进行，故栈具有后进先出（LIFO）特性。队列的插入操作限制在队尾端进行，而删除操作则限制在队头端进行，所以队列具有先进先出（FIFO）特性。栈和队列的特性使得它们在程序设计中的应用非常广泛。针对栈和队列的操作特性，本章还给出了这两种特殊线性表的顺序存储结构和链式存储结构以及定义在每种存储结构上的基本操作的实现算法。本章还进一步给出栈和队列在程序设计中的应用实例。应在充分理解栈与队列的定义与特性的基础上，掌握它们各自的存储实现方式（包括存储结构与基本操作实现算法），并能够应用栈与队列来解决程序设计中的相关问题。本章还介绍了递归与递归算法及基于系统工作栈的递归算法运行机制，应理解递归的两个最基本的法则，学会利用递归分析问题和解决问题的方法。32学习要点（1）掌握栈和队列的结构特点，了解在什么问题中应该使用哪种结构和如何使用。（2）熟悉栈（队列）和线性表的关系；顺序栈（顺序队列）和顺序表的关系；链栈（链队列）和链表的关系。（3）重点掌握在顺序栈和链栈上实现的栈的基本运算，特别注意栈满和栈空的条件及它们的描述。（4）重点掌握在循环队列和链队列上实现的基本运算，特别注意队满和队空的描述方法。（5）熟悉栈和队列的下溢和上溢的概念；顺序队列中产生假上溢的原因；循环队列消除假上溢的方法。33习题1、栈与队列是二种特殊的线性表，栈亦称为；队列亦称为。2、现有一个空栈，现有4个元素其入栈顺序为A、B、C、D，则不可能得到了出栈顺序为。A）A,B,C,DBD,C,B,ACC,A,B,DDA,C,B,D3、现有一个空栈，已知其入栈序列为1,2,3,N，其输出序列为P1,P2,P3,PN。若P1N，则PI（1IN）为A）IBNICNI1D不确定4、栈与队列的共同点是。A）都是先进后出B）都是先进先出C）只允许在端点处插入和删除元素D没有共同点5、设有一顺序栈S，元素S1,S2,S3,S4,S5,S6依次进栈，如果6个元素出栈的顺序是S2,S3,S4,S6,S5,S1,则栈的容量至少应该是（）A）2B）3C）5D）66、若元素A,B,C,D,E,F依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（）ADCEBFABCBDAEFCBCAEFDDAFEDCB7、元素A,B,C,D,E依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素D开头的序列个数是A3B4C5D68、为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据该缓冲区的逻辑结构应该是A栈B队列C树D图9、一个队列的入列序是1，2，3，4，则队列的输出系列是（）A）4，3，2，1B）1，2，3，4，C）1，4，3，2D）3，2，4，110、设栈S和队列Q的初始状态均为空，元素A,B,C,D,E,F,G依次通过栈S，一个元素出栈后立即进入队列Q，若7个元素出队的顺序为B,D,C,F,E,A,G则栈S的容量至少应该为（）。A1B2C3D411、已知循环队列存储在一维数组A0N1中，且队列非空时FRONT和REAR分别指向队头和队尾元素若初始时队列为空，且要求第1个进入队列的元素存储在A0处，则初始时FRONT和REAR的值分别是A0,0B0,N1CN1,0D,N1,N112、向一个栈顶指针为TOP（TOP指向栈顶元素）的链中插入一个S所指结点时，其操作步骤为（）A）TOPNEXTSB）SNEXTTOPNEXTTOPNEXTSC）SNEXTTOPTOPSD）SNEXTTOPTOPTOPNEXT13、在一个栈顶指针为TOP（TOP指向栈顶元素）的链栈中，进行出栈操作，并将被出栈元素的值保存到X中，其操作步骤为（）A）PTOPXTOPDATATOPTOPNEXTFREEPB）PTOPTOPTOPNEXTXTOPDATAFREEPC）XTOPTOPTOPNEXTFREETOPD）XTOPDATAFREETOP14、对于顺序存储的栈，其类型描述如下TYPEDEFSTRUCTSELEMTYPEBASE100/用静态数组BASE存储栈的元素INTTOP/TOP标识栈顶位置，其值为下标值SQSTACKSQSTACKS（1）若栈S为实指栈，即栈顶指针TOP指示的位置为当前栈顶元素的位置，则栈S为空的判定条件为；将元素E入栈S的操作语句为；将S的栈顶元素出栈并将其值赋给元素E的操作语句为。（2）若栈S为虚指栈，若TOP指示的位置为当前栈顶元素的下一位置（即入栈位置），则栈空的判定条件为；将元素E入栈的操作语句为；将栈顶元素出栈并将其值赋给元素E的操作语句为。15、阅读下列算法，写出其完整的功能。DEFINEMAX100TYPEDEFSTRUCTLNODEDATATYPEDATA/DATATYPE为数据元素类型STRUCTLNODENEXT/后继结点的指针LINKEDLISTVOIDRVLISTLINKEDLISTHEADDATATYPESMAXINTTOP0LINKEDLISTPPHEADNEXTWHILEPSTOPPDATAPPNEXTPHEADNEXTWHILETOPPDATASTOPPPNEXT函数RVLIST的功能为16、以下算法是以顺序存储结构实现一个双向栈（即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点，如下图所示）。以下给出了此双向栈类型的定义及初始化、入栈与出栈的操作算法。填写空白位置，使此算法完整。012IMAXJ1MAX2MAX1A0A1A2AIBJB1B0DEFINEMAX200TYPEDEFSTRUCTELEMTYPEELEMMAX/ELEMTYPE为栈内数据元素的类型INTTOP0,TOP1/定义两个栈顶位置指针，分别存储两个栈的当前栈顶元素的下标DSTACKVOIDINISTACKDSTACKSTOP1STATUSPUSHDSTACKRETURNERRORELSEIFI0SELEMSTOP0EELSERETRUNOKSTATUSPOPDSTACKELSEESELEMSTOP0RETURN1ELSEIFRETURN0ELSEERETURN117、以下是有关循环队列的类型定义及其有关操作，填写相应的空白位置。DEFINEMAX100TYPEDEFSTRUCTELEMTYPEBASEMAX/ELEMTYPE为元素的数据类型INTFRONT/头指针，若队列不空，指向队列头元素INTREAR/尾指针，若队列不空，指向队列尾元素的下一个位置SQQUEUE/说明少用一个元素空间，以区别队列判空和判满条件STATUSINITQUEUESQQUEUERETURNOKSTATUSENQUEUESQQUEUE/若队列满，返回出错QBASEQREAREQREARQREAR1MAXRETRUNOKSTATUSDEQUEUESQQUEUE/若队列空，则返回出错EQBASEQFRONTQFRONT18、若用如下图所示一带头结点的单链表来表示队列。以下给出了此队列的类型描述、初始化操作、入队操作和出队操作，在空白处填写上正确答案。（1）一般的队列形式（2）空队列形式STRUCTQNODE/结点类型描述ELEMTYPEDATA/ELEMTYPE为元素的数据类型STRUCTQNODENEXTTYPEDEFSTRUCT/链队类型描述STRUCTQNODEFRONTSTRUCTQNODEREARLINKQUEUESTATUSINITQUEUELINKQUEUEIFQFRONTRETURNFALSERETURNOKSTATUSENQUEUELINKQUEUEIFPRETURNFALSEPDATAEPNEXTNULLRETURNOKSTATUSDEQUEUELINKQUEUE/空队时PQFRONTNEXTQFRONTNEXTPNEXTIFPQREAREPDATAFREEPRETURNOK19、用下图所示一带头结点的循环单链表表示队列，并且只设一个指针Q指向队尾结点（注意不设头指针）。以下给出了此队列的类型描述及初始化、入队和出队操作算法，在空白处填写上正确答案。（1）一般的队列形式（2）空队列形式A1A2ANQQTYPEDEFSTRUCTLNODEELEMTYPEDATA/ELEMTYPE为元素的数据类型STRUCTLNODENEXTCLINKQUEUESTATUSINITQUEUECLINKQUEUEIFQRETURNFALSEQNEXTRETURNOKSTATUSENQUEUECLINKQUEUEIFQRETURNFALSEQDATAEQNEXTQNEXTQNEXTQRETURNOKSTATUSDEQUEUECLINKQUEUE/空队时PQNEXTNEXTQNEXTNEXTPNEXTIFPQEPDATAFREEPRETURNOK第6章树61基本内容本章介绍了树和二叉树的递归定义，详细分析了二叉树的五个基本性质，并讨论了二叉树的五种不同形态和两种特殊的二叉树满二叉树和完全二叉树。本章分析了二叉树的顺序存储结构的实现及其缺点常常浪费存储空间，为了克服这个缺点，引入了链式存储结构，常见的形式有二叉链表和三叉链表，其结点结构除了数据域外，另设指针域指向结点的左右孩子或者双亲。二叉树常见的遍历算法有三种先序、中序和后序遍历，遍历是各种操作和运算的基础，本章深入分析了三种遍历的搜索路径，给出了先序遍历的递归和中序遍历的非递归实现，并且引出了先序和后序遍历算法的实现思路，最后举例说明了二叉树若干运算。本章讨论了在求某个结点的前驱和后继时，可以利用N1个空链域，解决其时间和空间开销的问题，由此引出线索二叉树的概念和思路，给出了中序线索化的实现算法。本章介绍了树常见的几种存储结构，可以利用二叉链表作为媒介导出树和森林与二叉树之间的一一对应和转换关系。为了使学生了解树的应用，本章还给出了一个简单的书目管理系统的设计实例。作为二叉树的具体应用，本章介绍了哈夫曼树的概念，讨论了编码时出现的问题，利用哈夫曼树可以实现最优前缀编码，给出了哈夫曼树的构造算法以及哈夫曼树的编码方法。62学习要点（1）熟练掌握二叉树的结构特性，了解相应的证明方法。（2）熟悉二叉树的各种存储结构的特点及适用范围。（3）遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。不仅要熟练掌握各种遍历策略的递归和非递归算法，了解遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。（4）理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行的遍历，而线索二叉树上的线索又为相应的遍历提供了方便。（5）熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握1至2种建立二叉树和树的存储结构的方法。（6）学会编写实现树的各种操作的算法。（7）了解最优二叉树树的特性，掌握建立最优树和哈夫曼编码的方法。63习题1、在一棵含有N个结点的二叉树中，其分支数（边数）为；若此二叉树只有度为2的分支结点，和度为0的叶子结点，则该树中叶子结点的数目为；若此二叉树的深度（根所在数为1，深度为树的最大层数）为D，且此树为满二叉树，则此树的结点数N为。2、对于一棵有N个结点的完全二叉树，其深度为（根所在数为1，深度为树的最大层数）；若对其结点按层进行编号（根结点为1，每层从左到右），则对于一编号为I1DRRETURNDL1ELSERETURN（2）递归函数PREORDERT、INORDERT、POSTORDERT的作用对以T为根指针的二叉树进行先根（序）遍历、中根（序）遍历、后根（序）遍历。VOIDPREORDERBITREET/先序遍历以T为根指针的二叉树IFTVISITTDATA/其中VISIT为结点数据的访问函数VOIDINORDERBITREET/中序遍历以T为根指针的二叉树IFTVISITTDATA/其中VISIT为结点数据的访问函数VOIDPOSTORDERBITREET/后序遍历以T为根指针的二叉树IFTVISITTDATA/其中VISIT为结点数据的访问函数（3）设计一个算法计算一棵给定二叉树的所有结点数。INTNODESBITREET33、给定权值集合15，3，14，2，6，9，16，17，请构造相应的哈夫曼树并计算它的带权路经长度。34、设用于通讯的电文仅由6个字母（A、B、C、D、E、F）组成，字母在电文中出现的频率分别为024,002,012,008,036，018。试为这6个字母设计出哈夫曼编码。（要求画出相应的哈夫曼树，根据哈夫曼树给出哈夫曼编码）第7章图71基本内容图是最复杂的非线性结构，是一种在各个领域中广泛应用的数学模型，它的表达能力最强。本章首先给出了图的定义和基本概念、术语，应在理解的基础上掌握。然后介绍了图的两种最为常用的存储结构,即邻接矩阵存储结构和邻接表存储结构，并分别基于这两种存储结构实现了图的常用操作。熟练地掌握结构体类型将有助于理解图的存储结构的类型定义，并有助于掌握相关算法。图的遍历算法是图的最基本而且非常重要的算法，是求解图的连通性问题的重要基础，图的许多问题都可借助于遍历算法来实现。要熟练掌握深度优先遍历和广度优先遍历算法的基本思想及其实现算法。图的应用非常广泛，包括求无向网的最小生成树、求有向图的拓扑序列和关键路径、求有向网的最短路径。其中每个问题都涉及到了一些经典算法，如求最小生成树的PRIM算法和KRUSKAL算法，拓扑排序算法和关键路径算法以及求最短路径的DIJKSTRA算法和FLOYD算法，要熟练掌握这些算法的求解方法和算法设计思想，并能够利用这些算法解决一些实际问题。72学习要点（1）熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。（2）熟练掌握图的两种搜索路径的遍历遍历的逻辑定义、深度优先搜索的两种形式（递归和非递归）和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略。（3）应用图的遍历算法求解各种简单路径问题。（4）理解并掌握各种图的应用算法的设计思想和算法描述。73习题1、选择题（1）在一个图中，所有顶点的度数之和等于图的边数的倍。A）1/2B）1C）2D）4（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和倍。A）1/2B）1C）2D）4（3）有8个结点的无向图最多有条边。A）14B）28C）56D）112（4）有8个结点的无向连通图最少有条边。A）5B）6C）7D）8（5）有8个结点的有向完全图有条边。A）14B）28C）56D）112（6）用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。A）栈B）队列C）二叉树D）树（7）已知图的邻接矩阵如下，根据算法思想，则从顶点0出发，按深度优先遍历的结点序列是011011A）0243156B）0135642C）0423165D）0134256（8）已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A）0243165B）0135642C）0123465D）0123456（9）已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是A）0132B）0231C）0321D）0123（10）已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是A）0321B）0123C）0132D）0312（11）图的简单路径是指（）不重复的路径。A）权值B）顶点C）边D）边与顶点均（12）若采用邻接矩阵法存储一个无向图，则该邻接矩阵是一个。A）上三角矩阵B）稀疏矩阵C）对角矩阵D）对称矩阵（13）设G1V1,E1和G2V2,E2为两个图，如果V1V2，E1E2，则称（）。A）G1是G2的子图B）G2是G1的子图V0V1V2V331203010012322V0V1V2V313220312012300C）G1是G2的连通分量D）G2是G1的连通分量（14）一个连通图的生成树是包含图中所有顶点的一个（）子图。A）极小B）连通C）极小连通D）无环（15）对于具有E条边的无向图，它的邻接表中有（）个边结点。A）E1B）EC）2E1D）2E（16）与邻接矩阵相比，邻接表更适合于存储（）图。A）无向B）连通C）稀疏D）稠密图（17）在有向图G的拓扑序列中，若顶点VI在顶点VJ之前，则下列情形不可能出现的是（）。A）G中有弧VI，VJB）G中有一条从VI到VJ的路径C）G中没有弧VI，VJD）G中有一条从VJ到VI的路径（18）有向图G用邻接矩阵A存储，则顶点I的出度等于。A）第I行非0元素个数B）第I列非0元素个数C）第I行和第I列所有非0的元素个数D）矩阵A中所有非0元数个数（19）下列关于无向连通图特性的叙述中，正确的是（）所有顶点的度之和为偶数边数大于顶点个数减1至少有一个顶点的度为1A只有B只有C和D和2、填空题（1）遍历图有、等方法。（2）在一个具有N个顶点的无向图中，最多可包含条边，在一个具有N个顶点的有向图中，最多可包含条弧。（3）用DIJKSTRA算法求某一顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。（4）拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。（5）对于一AOE网，若用EI表示活动AI的最早开始时间，LI表示活动AI的最迟开始时间，则活动AI为关键活动的条件为。3、给出图71所示的无向图的邻接矩阵（邻接数组）及邻接表。4、给出图72所示的有向图的邻接矩阵（邻接数组）及邻接表。5、对于图72所示的有向无环图给出其所有拓扑排序序列。V1V2V4V3V5V6655563624图731V11图72V2V3V4V5V6V0V2V1V3图71V46、给出图73所示连通网的邻接矩阵。7、对如图73所示连通网（边上的数值为此边的权值）（1）从结点V1出发，利用普里姆算法构造其最小生成树。（2）利用克鲁斯卡尔算法构造其最小生成树。（只需画出最终的最小生成树，在每条边的两侧分别注明边的权值和选边的顺序，并将选边顺序用括号括起来以区别权值）8、图74给出了一个AOE网，求它的关键路径。9、图75给出了一个有向网，以顶点V1为源点，求V1到其余各个顶点的最短路径长度，并构造出最短路径。图74AOE网V4V3V6V5V2V1V7A13A26A32A44A104A52A61A73图75有向网V4V3V6V5V2V1V725621841249522A93A8110、用C语言定义邻接表表示法的数据类型ALGRAPH。然后写一函数求有向图中各顶点的入度，设该函数头为FINDINDEGREEALGRAPH/顶点数组，VEXTYPE为顶点类型INTARCSMAXVEXNUMMAXVEXNUM/邻接矩阵，有弧或边则值为1，否则为0INTVEXNUM,ARCNUM/顶点数或边数INTKIND/图的种类标识MGRAPH函数FIRSTADJVEXG,V的作用为在图G中，求顶点V（V为顶点在顶点数组中的下标，下同）的第一个邻接顶点；若存在函数返回所求得的邻接顶点（即其在顶点数组中的下标），否则返回1。函数NEXTADJVEXG,V,W的作用为在图G中，已知顶点W是顶点V当前的一个邻接顶点，函数用来求相对于顶点W顶点V的下一个邻接顶点；若存在函数返回所求得的邻接顶点（即其在顶点数组中的下标），否则返回1。给出了这两个函数的完整定义。INTFIRSTADJVEXMGRAPHHIGHNWHILEMIDLOWHIGH/2IFMAMIDRETURNELSEIFMDATAMRETURNELSEIFMDATAPPLCHILDELSERETURNNULL12、对于给定的关键字序列（15，19，8，43，10），选取哈希函数为H（KEY）KEY7，分别利用以下给出的解决冲突的方法，在06的地址空间上构造出哈希表（画出所构造的哈希表即可），并求出在等概率查找的情况下查找成功时的平均查找长度。（1）开放定址法的线性探测再散列；（2）开放定址法的二次探测再散列；13、设哈希表长度为11，哈希函数H（KEY）VALUEKEY11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列，要求在010的地址空间中构造哈希表，并求出等概率情况下查找成功平均查找长度。第9章排序91基本内容本章中主要阐述了内部排序常见的四类排序，即插入排序、交换排序、选择排序和归并排序。分别介绍了各类排序中的主要排序方法的基本思想、算法的实现过程及排序算法性能评价等。最后，本章还给出了各种排序方法的比较及选择原则。本章给出了直接插入排序、折半插入排序和希尔排序三种插入排序方法。直接插入排序和折半插入排序的时间复杂度为ON2，直接插入排序当记录数较小或已基本有序时效率较高；相对直插入排序来说，折半插入排序其仅仅是提高了查找查入位置进的效率。希尔排序试图将待排序序列变成“基本有序”，然后再用直接插入排序来完成最后的排序工作。希尔排序中最好增量序列的确定涉及一些数学上尚未解决的难题。交换排序包括冒泡排序和快速排序，它是藉助交换进行排序的方法。冒泡排序是基于相邻两记录关键字间的比较与交换，其时间复杂度为ON2，是一种稳定的排序方法。快速排序是基于不相邻记录间关键字的比较与交换，是一个递归过程，每执行一次这个过程就把当前区间上的所有元素按基准元素划分为前后两个子区间，其中一个子区间的关键字均比另一子区间的关键字小，当一个子区间的元素个数等于或大于2时继续向下递归，以达到整个序列有序。选择排序主要包括简单选择排序和堆排序，其基本思想是每一趟在NI1I1,2,N1个记录中选取关键字最小（或最大）的记录作为有序序列中第I个记录。简单选择排序首先在未排序的序列中找到最小关键字的记录与第1个记录交换，其时间复杂度为ON2。堆排序是利用堆来选取待排序的记录中关键字的极值，其过程包括建立初始堆和利用堆排序两个阶段。归并排序是不断地利用将两个（或多个）有序表合并成一个有序表的归并过程。归并排序的运行时间并不依赖于待排序记录的原始顺序，这样，它就避免了快速排序的最差情况。92学习要点（1）深刻理解排序的定义和各种排序方法的基本思想、排序过程、实现的算法、算法的效率分析及排序的特点，并能加以灵活应用。（2）理解各种方法的排序过程依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。（3）掌握各种排序方法的