数据结构全部练习题及上机题参考答案

数据结构简明教程练习题及参考答案练习题11单项选择题（1）线性结构中数据元素之间是（）关系。A一对多B多对多C多对一D一对一答D（2）数据结构中与所使用的计算机无关的是数据的（）结构。A存储B物理C逻辑D物理和存储答C（3）算法分析的目的是（）。A找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性答C（4）算法分析的两个主要方面是（）。A空间复杂性和时间复杂性B正确性和简明性C可读性和文档性D数据复杂性和程序复杂性答A（5）计算机算法指的是（）。A计算方法B排序方法C求解问题的有限运算序列D调度方法答C（6）计算机算法必须具备输入、输出和（）等5个特性。A可行性、可移植性和可扩充性B可行性、确定性和有穷性C确定性、有穷性和稳定性D易读性、稳定性和安全性答B2填空题（1）数据结构包括数据的、数据的和数据的这三个方面的内容。答逻辑结构存储结构运算（2）数据结构按逻辑结构可分为两大类，它们分别是和。答线性结构非线性结构（3）数据结构被形式地定义为（D,R），其中D是的有限集合，R是D上的有限集合。答数据元素关系（4）在线性结构中，第一个结点前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点后继结点，其余每个结点有且只有1个后继结点。答没有没有（5）在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后继结点数可以是。答前驱1后继任意多个（6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（）。答任意多个（7）数据的存储结构主要有四种，它们分别是、和存储结构。答顺序链式索引哈希（8）一个算法的效率可分为效率和效率。答时间空间3简答题（1）数据结构和数据类型两个概念之间有区别吗答简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。（2）简述线性结构、树形结构和图形结构的不同点。答线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。（3）设有采用二元组表示的数据逻辑结构SD,R，其中DA,B,I，RA,B,A,C,C,D,C,F,F,H,D,E,F,G,H,I，问相对于关系R，哪些结点是开始结点，哪些结点是终端结点答该逻辑结构为树形结构，其中A结点没有前驱结点，称为根结点，B、E、G、I结点没有后继结点，是终端结点，也称为叶子结点。（4）以下各函数是算法中语句的执行频度，N为问题规模，给出对应的时间复杂度T1NNLOG2N1000LOG2NT2N1000LOG2N3LOGT3NN21000LOG2NT4N2NLOG2N1000LOG2N答T1NONLOG2N，T2NO，T3NON2，T4NONLOG2N。（5）分析下面程序段中循环语句的执行次数。INTJ0,S0,N100DOJJ1SS10JWHILEJIJS答语句S的执行次数。231122NNININIIJ（7）设N为问题规模，求以下算法的时间复杂度。VOIDFUN1INTNINTX0,IFORI1IVOIDMAXSINTA,INTN,INTMAX1MAX2A0FORI1IMAX1MAX2MAX1MAX1AIELSEIFAIMAX2MAX2AIVOIDMAININTA1,4,10,6,8,3,5,7,9,2INTN10INTMAX1,MAX2MAXSA,N,MAX1,MAX2PRINTF“最大元素值D,次大元素值DN“,MAX1,MAX2练习题21单项选择题（1）数据在计算机存储器内表示时，物理地址与逻辑地址相对顺序相同并且是连续的，称之为（）。A存储结构B逻辑结构C顺序存储结构D链式存储结构答C（2）在N个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）。A访问第I个结点（1IN）和求第I（2IN）个结点的前驱结点B在第I（1IN）个结点后插入一个新结点C删除第I个结点（1IN）D将N个结点从小到大排序答A（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。A8B635C63D7答B（4）链式存储结构所占存储空间（）。A分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B只有一部分，存放结点值C只有一部分，存储表示结点间关系的指针D分两部分，一部分存放结点值，另一部分存放结点所占单元数答A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A必须是连续的B部分地址必须是连续的C一定是不连续的D连续或不连续都可以答D（6）一个线性表在（）情况下适用于采用链式存储结构。A需经常修改其中的结点值B需不断对其进行删除插入C其中含有大量的结点D其中结点结构复杂答B（7）单链表的存储密度（）A大于1B等于1C小于1D不能确定答C2填空题（1）在顺序表中插入或删除一个元素时，需要平均移动（）元素，具体移动的元素个数与（）有关。答表中一半表长和该元素在表中的位置（2）向一个长度为N的顺序表的第I个元素（1IN1）之前插入一个元素时，需向后移动（）个元素。答NI1（3）向一个长度为N的顺序表中删除第I个元素（1IN）时，需向前移动（）个元素。答NI（4）在顺序表中访问任意一个元素的时间复杂度均为（），因此顺序表也称为（）的数据结构。答O1随机存取（5）顺序表中逻辑上相邻的元素的物理位置（）相邻。单链表中逻辑上相邻的元素的物理位置（）相邻。答一定不一定（6）在带头结点的单链表中，除头结点外，任一结点的存储位置由（）指示。答其前驱结点的链域的值（7）在含有N个数据结点的单链表中要删除已知结点P，需找到它的（），其时间复杂度为（）。答前驱结点的地址ON（8）含有N（N1）个结点的循环双向链表中，为空的指针域数为（）。答03简答题（1）试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好答顺序存储结构中，相邻数据元素的存放地址也相邻，并要求内存中可用存储单元的地址必须是连续的。其优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储结构中，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。其优点是插入或删除元素时很方便，使用灵活；缺点是存储密度小，存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。（2）对于表长为N的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为多少删除一个元素所需要移动的平均个数为多少答插入一个元素所需要移动的元素的平均个数为N1/2，删除一个元素所需要移动的平均个数为N/2。（3）在链表中设置头结点的作用是什么答在链表中设置头结点后，不管链表是否为空表，头结点指针均不空，并使得对链表的操作（如插入和删除）在各种情况下统一，从而简化了算法的实现过程。（4）对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个答对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的NEXT域、后继结点的PRIOR域和新插入结点的NEXT、PRIOR域。所以共修改4个指针。对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的NEXT域，新插入结点的NEXT域。所以共修改两个指针。（5）某含有N（N1）结点的线性表中，最常用的操作是在尾结点之后插入一个结点和删除第一个结点，则采用以下哪种存储方式最节省运算时间。单链表；仅有头指针不带头结点的循环单链表；双链表；仅有尾指针的循环单链表。答在单链表中，删除第一个结点的时间复杂度为O1。插入结点需找到前驱结点，所以在尾结点之后插入一个结点，需找到尾结点，对应的时间复杂度为ON。在仅有头指针不带头结点的循环单链表中，删除第一个结点的时间复杂度ON，因为删除第一个结点后还要将其改为循环单链表；在尾结点之后插入一个结点的时间复杂度也为ON。在双链表中，删除第一个结点的时间复杂度为O1；在尾结点之后插入一个结点，也需找到尾结点，对应的时间复杂度为ON。在仅有尾指针的循环单链表中，通过该尾指针可以直接找到第一个结点，所以删除第一个结点的时间复杂度为O1；在尾结点之后插入一个结点也就是在尾指针所指结点之后插入一个结点，时间复杂度也为O1。因此最节省运算时间。4算法设计题（1）设计一个高效算法，将顺序表的所有元素逆置，要求算法空间复杂度为O1。解遍历顺序表L的前半部分元素，对于元素LDATAI（0ILLENGTH/2），将其与后半部分对应元素LDATALLENGTHI1进行交换。对应的算法如下VOIDREVERSESQLISTELEMTYPEXFORI0IJ/表示LDATAI和LDATA0J中所有元素都不相同JLDATAJLDATAILLENGTHJ1/顺序表长度置新值本算法的时间复杂度为ON2，空间复杂度为O1。（3）设计一个算法从有序顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。解在有序顺序表L中，所有重复的元素应是相邻存放的，用K保存不重复出现的元素个数，先将不重复的有序区看成是LDATA00，置ELDATA0，用I从1开始遍历L的所有元素当LDATAIE时，将它放在LDATAK中，K增1，置ELDATAI，最后将L的LENGTH置为K。对应的算法如下VOIDDELSAME1SQLIST/K保存不重复的元素个数ELEMTYPEEELDATA0FORI1INEXT/P指向Q的前驱结点WHILEQNULLQQNEXTIFQNULL/找到值为X的结点PNEXTQNEXTFREEQRETURN1ELSERETURN0/未找到值为X的结点（5）设计一个算法判定单链表L是否是递增的。解判定链表L从第2个结点开始的每个结点的值是否比其前驱的值大。若有一个不成立，则整个链表便不是递增的；否则是递增的。对应的算法如下INTINCREASESLINKLSLINKPRELNEXT,P/PRE指向第一个数据结点PPRENEXT/P指向PRE结点的后继结点WHILEPNULLIFPDATAPREDATA/若正序则继续判断下一个结点PREP/PRE、P同步后移PPNEXTELSERETURN0RETURN1（6）有一个整数元素建立的单链表A，设计一个算法，将其拆分成两个单链表A和B，使得A单链表中含有所有的偶数结点，B单链表中所有的奇数结点，且保持原来的相对次序。解采用重新单链表的方法，由于要保持相对次序，所以采用尾插法建立新表A、B。用P遍历原单链表A的所有数据结点，若为偶数结点，将其链到A中，若为奇数结点，将其链到B中。对应的算法如下VOIDSPLITSLINKRAABSLINKMALLOCSIZEOFSLINK/建立头结点RBB/R总是指向B链表的尾结点WHILEPNULLIFPDATA20/偶数结点RANEXTP/将P结点链到A中RAPPPNEXTELSE/奇数结点RBNEXTP/将P结点链到B中RBPPPNEXTRANEXTRBNEXTNULL本算法的时间复杂度为ON，空间复杂度为O1。（7）有一个有序单链表（从小到大排列），表头指针为L，设计一个算法向该单链表中插入一个元素为X的结点，使插入后该链表仍然有序。解先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。对应的算法如下VOIDINORDERLISTSLINKSSLINKMALLOCSIZEOFSLINK/建立一个待插入的结点SDATAXSNEXTNULLIFLNULL|XDATA/若单链表为空或X小于第1个结点DATE域SNEXTL/把S结点插入到头结点之后LSELSEQL/寻找插入位置,P指向待比较的结点,Q指向P的前驱结点PQNEXTWHILEPNULLPPNEXTSNEXTP/将S结点插入到Q和P之间QNEXTS（8）有一个单链表L，其中可能出现值域重复的结点，设计一个算法删除值域重复的结点。并分析算法的时间复杂度。解用P遍历单链表，用R遍历P结点之后的结点，Q始终指向R结点的直接前驱结点，若RDATAPDATA，则删除R结点，否则Q、R同步后移一个结点。对应的算法如下VOIDDELS1SLINKWHILEPNULLQPRQNEXTWHILERNULLIFRDATAPDATA/R指向被删结点TRNEXTQNEXTTFREERRTELSEQRRRNEXTPPNEXT本算法的时间复杂度为ON2。（9）有一个递增有序单链表（允许出现值域重复的结点），设计一个算法删除值域重复的结点。并分析算法的时间复杂度。解由于是有序表，所以相同值域的结点都是相邻的。用P遍历递增单链表，若P结点的值域等于其后结点的值域，则删除后者。对应的算法如下VOIDDELSSLINKWHILEPNEXTNULLIFPDATAPNEXTDATA/找到重复值的结点QPNEXT/Q指向这个重复值的结点PNEXTQNEXT/删除Q结点FREEQELSEPPNEXT本算法的时间复杂度为ON。（10）有一个双链表L，设计一个算法查找第一个元素值为X的结点，将其与后继结点进行交换。解先找到第一个元素值为X的结点P，Q指向其后继结点，本题是将P结点移到Q结点之后，实现过程是删除P结点，再将其插入到Q结点之后。对应的算法如下INTSWAPDLINKL,ELEMTYPEXDLINKPLNEXT,QWHILEPNULLIFPNULL/未找到值为X的结点RETURN0ELSE/找到值为X的结点PQPNEXT/Q指向P的后继结点IFQNULL/P结点不是尾结点PPRIORNEXTQ/先删除P结点QPRIORPPRIORPNEXTQNEXT/将P结点插入到Q结点之后IFQNEXTNULLQNEXTPRIORPQNEXTPPPRIORQRETURN1ELSE/P结点是尾结点RETURN0/无法与后继结点交换，返回0（11）对于有N（N1）个数据结点的循环单链表L，设计一个算法将所有结点逆置。解采用头插法重建循环单链表L的思路，先建立一个空的循环单链表，用P遍历所有数据结点，每次将P结点插入到前端。对应的算法如下VOIDREVERSESLINKLNEXTL/建立一个空循环单链表WHILEPLQPNEXTPNEXTLNEXT/将P结点插入到前端LNEXTPPQ上机实验题2有两个整数集合采用有序单链表存储，设计尽可能高效的算法求两个集合的并集、交集和差集。并用相关数据进行测试。INCLUDEINCLUDE“SLINKH“VOIDUNIONSLINKL1,SLINKL2,SLINKL3SLINKMALLOCSIZEOFSLINKTCL3PL1NEXTQL2NEXTWHILEPNULLSDATAPDATATCNEXTSTCSPPNEXTELSEIFPDATAQDATASSLINKMALLOCSIZEOFSLINKSDATAQDATATCNEXTSTCSQQNEXTELSESSLINKMALLOCSIZEOFSLINKSDATAPDATATCNEXTSTCSPPNEXTQQNEXTWHILEPNULLSSLINKMALLOCSIZEOFSLINKSDATAPDATATCNEXTSTCSPPNEXTWHILEQNULLSSLINKMALLOCSIZEOFSLINKSDATAQDATATCNEXTSTCSQQNEXTTCNEXTNULLVOIDINTERSECTIONSLINKL1,SLINKL2,SLINKL3SLINKMALLOCSIZEOFSLINKTCL3PL1NEXTQL2NEXTWHILEPNULLELSEIFPDATAQDATAQQNEXTELSE/PDATAQDATASSLINKMALLOCSIZEOFSLINKSDATAPDATATCNEXTSTCSPPNEXTQQNEXTTCNEXTNULLVOIDSUBSSLINKL1,SLINKL2,SLINKL3SLINKMALLOCSIZEOFSLINKTCL3PL1NEXTQL2NEXTWHILEPNULLSDATAPDATATCNEXTSTCSPPNEXTELSEIFPDATAQDATAQQNEXTELSE/PDATAQDATAPPNEXTQQNEXTWHILEPNULLSSLINKMALLOCSIZEOFSLINKSDATAPDATATCNEXTSTCSPPNEXTTCNEXTNULLVOIDMAINSLINKA,B,C,D,EELEMTYPEA1,3,6,8,10,20CREATELISTRA,A,6/尾插法建表PRINTF“集合A“DISPLISTAELEMTYPEB2,5,6,10,16,20,30CREATELISTRB,B,7/尾插法建表PRINTF“集合B“DISPLISTBPRINTF“求A、B并集CN“UNIONA,B,C/求A、B并集CPRINTF“集合C“DISPLISTCPRINTF“求A、B交集CN“INTERSECTIONA,B,D/求A、B并集DPRINTF“集合D“DISPLISTDPRINTF“求A、B差集EN“SUBSA,B,E/求A、B差集EPRINTF“集合E“DISPLISTEDESTROYLISTADESTROYLISTBDESTROYLISTCDESTROYLISTDDESTROYLISTE练习题31单项选择题（1）栈中元素的进出原则是（）。A先进先出B后进先出C栈空则进D栈满则出答B（2）设一个栈的进栈序列是A、B、C、D（即元素AD依次通过该栈），则借助该栈所得到的输出序列不可能是（）。AA,B,C,DBD,C,B,ACA,C,D,BDD,A,B,C答D（3）一个栈的进栈序列是A、B、C、D、E，则栈的不可能的输出序列是（）。AEDCBABDECBACDCEABDABCDE答C（4）已知一个栈的进栈序列是1，2，3，N，其输出序列的第一个元素是I（1IN）则第J（1JN）个出栈元素是（）。AIBNICJI1D不确定答D（5）设顺序栈ST的栈顶指针TOP的初始时为1，栈空间大小为MAXSIZE，则判定ST栈为栈空的条件为（）。ASTTOP1BSTTOP1CSTTOPMAXSIZEDSTTOPMAXSIZE答A（6）设顺序栈ST的栈顶指针TOP的初始时为1，栈空间大小为MAXSIZE，则判定ST栈为栈满的条件是。ASTTOP1BSTTOP1CSTTOPMAXSIZE1DSTTOPMAXSIZE1答D（7）队列中元素的进出原则是（）。A先进先出B后进先出C栈空则进D栈满则出答A（8）元素A、B、C、D顺序连续进入队列QU后，队头元素是（），队尾元素是（）。AABBCCDD答AD。（9）一个队列的入列序列为1234，则队列可能的输出序列是（）。A4321B1234C1432D3241答B（10）循环队列QU（队头指针FRONT指向队首元素的前一位置，队尾指针REAR指向队尾元素的位置）的队满条件是（）。AQUREAR1MAXSIZEQUFRONT1MAXSIZEBQUREAR1MAXSIZEQUFRONT1CQUREAR1MAXSIZEQUFRONTAQUREARQUFRONT答C（11）循环队列QU（队头指针FRONT指向队首元素的前一位置，队尾指针REAR指向队尾元素的位置）的队空条件是（）。AQUREAR1MAXSIZEQUFRONT1MAXSIZEBQUREAR1MAXSIZEQUFRONT1CQUREAR1MAXSIZEQUFRONTDQUREARQUFRONT答D（12）设循环队列中数组的下标是0N1，其头尾指针分别为F和R（队头指针F指向队首元素的前一位置，队尾指针R指向队尾元素的位置），则其元素个数为（）。ARFBRF1CRFN1DRFNN答D（13）设有4个数据元素A、B、C和D，对其分别进行栈操作或队操作。在进栈或进队操作时，按A、B、C、D次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是（），第二次出栈得到的元素是（）；类似地，考虑对这4个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是（），第二次出队得到的元素是（）。经操作后，最后在栈中或队中的元素还有（）个。AABBCCDDA1B2C3D0答BDABB（14）设栈S和队列Q的初始状态为空，元素E1E6依次通过栈S，一个元素出后即进队列Q，若6个元素出队的序列是E2、E4、E3、E6、E5、E1，则栈S的容量至少应该是（）。A5B4C3D2答C2填空题（1）栈是一种特殊的线性表，允许插入和删除运算的一端称为（）。不允许插入和删除运算的一端称为（）。答栈顶栈底（2）一个栈的输入序列是12345，的输出序列为12345，其进栈出栈的操作为（）。答1进栈，1出栈，2进栈，2出栈，3进栈，3出栈，4进栈，4出栈，5进栈，5出栈。（3）有5个元素，其进栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（即C第一个且D第二个出栈）的次序有（）。答CDBAE、CDEBA、CDBEA。（4）顺序栈用DATA0N1存储数据，栈顶指针为TOP，其初始值为0，则元素X进栈的操作是（）。答DATATOPXTOP（5）顺序栈用DATA0N1存储数据，栈顶指针为TOP，其初始值为0，则出栈元素X的操作是（）。答TOPXDATATOP（6）（）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。答队列（7）设有数组A0M作为循环队列的存储空间，FRONT为队头指针（它指向队首元素的前一位置），REAR为队尾指针（它指向队尾元素的位置），则元素X执行入队的操作是（）。答REARREAR1M1AREARX（8）设有数组A0M作为循环队列的存储空间，FRONT为队头指针（它指向队首元素的前一位置），REAR为队尾指针（它指向队尾元素的位置），则元素出队并保存到X中的操作是（）。答FRONTFRONT1M1XAREAR3简答题（1）简要说明线性表、栈与队的异同点。答相同点都属地线性结构，都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。用途不同，栈用于子程调用和保护现场等，队列用于多道作业处理、指令寄存及其他运算等等。（2）顺序队的“假溢出”是怎样产生的如何知道循环队列是空还是满答一般的一维数组队列的尾指针已经到了数组的上界，不能再有进队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决循环队列是空还是满的办法如下设置一个布尔变量以区别队满还是队空；浪费一个元素的空间，用于区别队满还是队空。使用一个计数器记录队列中元素个数（即队列长度）。通常采用法，让队头指针FRONT指向队首元素的前一位置，队尾指针REAR指向队尾元素的位置，这样判断循环队列队空标志是FRONTREAR，队满标志是REAR1MAXSIZEFRONT。4算法设计题（1）假设采用顺序栈存储结构，设计一个算法，利用栈的基本运算返回指定栈中栈底元素，要求仍保持栈中元素不变。这里只能使用栈ST的基本运算来完成，不能直接用STDATA0来得到栈底元素。解假定采用顺序栈结构。先退栈ST中所有元素，利用一个临时栈TMPST存放从ST栈中退栈的元素，最后的一个元素即为所求，然后将临时栈TMPST中的元素逐一出栈并进栈到ST中，这样恢复ST栈中原来的元素。对应算法如下INTGETBOTTOMSQSTACKST,ELEMTYPESQSTACKTMPST/定义临时栈INITSTACKTMPST/初始化临时栈IFSTACKEMPTYST/空栈返回0RETURN0WHILESTACKEMPTYST/临时栈TMPST中包含ST栈中逆转元素POPST,XPUSHTMPST,XWHILESTACKEMPTYTMPST/恢复ST栈中原来的内容POPTMPST,EPUSHST,ERETURN1/返回1表示成功（2）设计一个算法，采用一个顺序栈逆向输出单链表L中所有元素。解本题并不需要改变单链表L的结构。设置一个顺序栈ST，先遍历单链表并将所有元素进栈，然后栈不空循环并输出栈中所有元素。对应算法如下VOIDREVERSEDISPSLINKLELEMTYPEXSTRUCTNODEELEMTYPEDATAMAXSIZEINTTOPST/定义一个顺序栈STTOP1SLINKPLNEXTWHILEPNULL/遍历单链表，将所有元素进栈STTOPSTDATASTTOPPDATAPPNEXTWHILESTTOP1/栈不空循环，输出栈中所有元素XSTDATASTTOPSTTOPPRINTF“D“,XPRINTF“N“（3）设计一个循环队列，用FRONT和REAR分别作为队头和队尾指针，另外用一个标志TAG标识队列可能空（0）或可能满（1），这样加上FRONTREAR可以作为队空或队满的条件。要求设计队列的相关基本运算算法。解设计的队列的类型如下TYPEDEFSTRUCTELEMTYPEDATAMAXSIZEINTFRONT,REAR/队头和队尾指针INTTAG/为0表示队空,为1时表示不空QUEUETYPE初始时TAG0，进行成功的插入操作后TAG1，进行成功的删除操作后TAG0；因为只有在插入操作后队列才有可能满，只有在删除操作后队列才有可能空，因此，这样的队列的基本要素如下初始时TAG0，FRONTREAR队空条件QUFRONTQUREARQUTAG0/为0表示队空可能为空/判队空算法INTQUEUEEMPTY1QUEUETYPEQURETURNQUFRONTQUREAR/判队满算法INTQUEUEFULL1QUEUETYPEQURETURNQUTAG1/进队算法INTENQUEUE1QUEUETYPEQUREARQUREAR1MAXSIZEQUDATAQUREARXQUTAG1/至少有一个元素,可能满RETURN1/出队算法INTDEQUEUE1QUEUETYPEQUFRONTQUFRONT1MAXSIZEXQUDATAQUFRONTQUTAG0/出队一个元素,可能空RETURN1（4）假设用一个循环单链表表示队列，并且只设一个指针REAR指向队尾结点，但不设头指针，设计出相应的队初始化、进队、出队和判队空的算法。解假设链队是不带头结点的循环单链表，其示意图如图31所示。队空条件REARNULL；进队操作在REAR结点之后插入结点并让REAR指向该结点；出队操作删除REAR结点之后的一个结点。对应的算法如下A1A2ANREAR队尾队首图31不带头结点的循环单链表表示队列TYPEDEFSTRUCTNODEELEMTYPEDATASTRUCTNODENEXTQNODE/链队结点类型/初始化队列VOIDINITQUEUEQNODE/进队算法VOIDENQUEUEQNODESQNODEMALLOCSIZEOFQNODE/创建新结点SDATAXIFREARNULL/原链队为空SNEXTS/构成循环链表REARSELSESNEXTREARNEXT/将S结点插入到REAR结点之后REARNEXTSREARS/让REAR指向这个新插入的结点/出队算法INTDEQUEUEQNODEIFREARNULL/队空RETURN0ELSEIFREARNEXTREAR/原队中只有一个结点XREARDATAFREEREARREARNULLELSE/原队中有两个或以上的结点QREARNEXTXQDATAREARNEXTQNEXTFREEQRETURN1/判队空算法INTQUEUEEMPTYQNODEREARRETURNREARNULL上机实验题3假设以I和O字符分别表示进栈和出栈操作，栈的初态和终栈均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。如IOIIOIOO序列是合法的，而IOOIOIIO序列是不合法的。设计一个算法判定所给的操作序列是否合法。若合法返回1；否则返回0。（假设被判定的操作序列已存入一维数组中）。并用相关数据进行测试。解采用一个链栈来判断操作序列是否合法，其中STR为存放操作序列的字符数组，N为该数组的元素个数（这里的ELEMTYPE类型设定为CHAR）。对应的算法如下INCLUDEINCLUDETYPEDEFSTRUCTNODECHARDATASTRUCTNODENEXTLSTACK/链栈结点类型VOIDINITSTACKLSTACKVOIDDESTROYSTACKLSTACKIFPRENULLRETURN/考虑空栈的情况PPRENEXTWHILEPNULLFREEPRE/释放PRE结点PREPPPNEXT/PRE、P同步后移FREEPRE/释放尾结点VOIDPUSHLSTACKPLSTACKMALLOCSIZEOFLSTACKPDATAX/创建结点P用于存放XPNEXTLS/插入P结点作为栈顶结点LSPINTPOPLSTACKIFLSNULL/栈空,下溢出返回0RETURN0ELSE/栈不空时出栈元素X并返回1PLS/P指向栈顶结点XPDATA/取栈顶元素XLSPNEXT/删除结点PFREEP/释放P结点RETURN1INTSTACKEMPTYLSTACKLS/判断栈空运算算法IFLSNULLRETURN1ELSERETURN0INTJUDGECHARSTR,INTN/判断STR序列的合法性INTI,TAGCHARXLSTACKLSINITSTACKLS/链栈LS初始化FORI0INEXTNULL。（3）对于一个含有N个字符的链串S，查找第I个元素的算法的时间复杂度为（）。答ON3简答题（1）设S为一个长度为N的串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数是多少答由串S的特性可知，1个字符的子串有N个，2个字符的子串有N1个，3个字符的子串有N2个，N2个字符的子串有3个，N1个字符的子串有2个。所以，非平凡子串的个数NN1N22。（2）若S1和S2为串，给出使S1/S2S2/S1成立的所有可能的条件（其中，“/”表示两个串连接运算符）。答所有可能的条件为（1）S1和S2为空串（2）S1或S2其中之一为空串（3）S1和S2为相同的串（4）若两串长度不等，则长串由整数个短串组成。4算法设计题（1）设计一个算法REPCHARS,X,Y，将顺序串S中所有字符X替换成字符Y。要求空间复杂度为O1。解因要求算法空间复杂度为O1，所以只能对串S直接替换。从头开始遍历串S，一旦找到字符X便将其替换成Y。对应算法如下VOIDREPSTRSQSTRINGFORI0IDATAPDATA时，P和Q同步后移一个结点；否则返回0。当所有元素是递增排列时返回1。对应算法如下INTINCREASELINKSTRINGSLINKSTRINGPSNEXT,QIFPNULLWHILEPNEXTNULLQPNEXT/Q指向P的后续结点IFQDATAPDATAPQELSE/逆序时返回0RETURN0RETURN1（3）假设以链式结构存储一个串S，设计一个算法求串S中最长等值子串。解假设串用带头结点的单链表存储串S。用MAX存放最大平台长度，扫描串S，计算一个平台的长度N，若N大于MAX，则置MAX为N。对应的算法如下INTMAXLENGTHLINKSTRINGSINTN,MAX0LINKSTRINGPSNEXT,QWHILEPNULLN1QPPPNEXTWHILEPNULLPPNEXTIFNMAXMAXNRETURNMAX上机实验题4两个非空串S和T采用顺序存储结构存储，设计一个算法求这两个串最大公共子串，并用相关数据进行测试。解采用INDEX算法思路设计由顺序串S、T产生最大公共子串STR。对应的程序如下INCLUDEINCLUDE“SQSTRINGH“/包含顺序串的基本运算函数SQSTRINGMAXCOMSTRSQSTRINGS,SQSTRINGTSQSTRINGSTRINTMIDX0,MLEN0,TLEN,I0,J,K/用MIDX,MLEN保存最大公共子串WHILEIMLEN/将较大长度者赋给MIDX与MLENMIDXIMLENTLENJTLEN/继续扫描T中第JTLEN字符之后的字符ELSEJI/继续扫描S中第I字符之后的字符FORI0IDEFINEM3DEFINEN4VOIDMINMAXINTAMNINTI,J,HAVE0INTMINM,MAXNFORI0IMAXJMAXJAIJFORI0I0IFAIJXIFAIJXJ/修改列号ELSEI/修改行号ELSE/AIJXFLAG1BREAKRETURNFLAG上机实验题5采用一维动态数组模拟二维数组的操作，即将一个二维数组的元素存放在一个一维数组中，一维数组的空间根据二维数组的大小动态分配。设计一个算法实现两个二维数组的相加运算。并用相关数据进行测试。解对应的程序如下INCLUDEINCLUDETYPEDEFINTELEMTYPETYPEDEFSTRUCTELEMTYPEP/存放二维数组元素INTM,N/存放二维数组的行数和列数MAT2VOIDINITMATMAT2MNYMPELEMTYPEMALLOCXYSIZEOFELEMTYPEINTSETIJMAT2IFI0ELSEQQ/2RETURNAP（2）已知一棵二叉树采用顺序方式存储在数组A1N中。设计一个先序遍历的递归算法。解先序遍历树中结点的递归算法如下VOIDPREORDER1ELEMTYPEA,INTI,INTNIFIDATA只有一个结点时FBTMAXFBTLCHILD,FBTRCHILD,BTDATA其他情况对应的算法如下ELEMTYPEMAXNODEBTNODEBTELEMTYPEMAX,MAX1,MAX2IFBTLCHILDNULLELSEMAX1MAXNODEBTLCHILD/求左子树的最大结点值MAX2MAXNODEBTRCHILD/求右子树的最大结点值MAXBTDATAIFMAX1MAXMAXMAX1IFMAX2MAXMAXMAX2/求最大值RETURNMAX/返回最大值（4）假设含有N个结点的二叉树采用二叉链存储结构。设计一个算法输出中序遍历序列中的第K（1IN）个结点值。解对应的算法如下INTI0/I为全局变量VOIDTRAVBTNODEBT,INTKIFBTNULLTRAVBTLCHILD,K/遍历左子树IIFIKPRINTF“C“,BTDATARETURNTRAVBTRCHILD,K/遍历右子树（5）假设二叉树采用二叉链存储结构，设计一个算法LEVEL求二叉树中结点值为X的结点的层数。解对应的递归算法如下INTLEVELBTNODEBT,ELEMTYPEX,INTH/调用H对应的实参置初值1INTLIFBTNULLRETURN0ELSEIFBTDATAXRETURNHELSELLEVELBTLCHILD,X,H1/在左子树中查找IFL0RETURNLELSE/在左子树中未找到,再在右子树中查找RETURNLEVELBTRCHILD,X,H1上机实验题6假设一棵二叉树采用二叉链存储结构，其中所有结点值均不相同。设计一个算法求从根结点到值为X的结点的路径。并用相关数据进行测试。解采用递归和层次遍历两种求解方法，对应的程序如下INCLUDEINCLUDE“BTREEH“VOIDPATH1BTNODEBT,ELEMTYPEX,ELEMTYPEPATH,INTPATHLENINTIIFBTNULLIFBTDATAX/找到值为X的结点PRINTF“从根结点到C结点的路径“,BTDATAFORI0IDATARETURNELSEPATHPATHLENBTDATA/将当前结点放入路径中PATHLEN/PATH中元素个数增1PATH1BTLCHILD,X,PATH,PATHLEN/递归遍历左子树PATH1BTRCHILD,X,PATH,PATHLEN/递归遍历右子树VOIDPATH2BTNODEBT,ELEMTYPEXBTNODEPELEMTYPEPATHMAXSIZEINTI,DSTRUCTBTNODES/存放结点指针INTPARENT/存放其双亲结点在QU中的下标QUMAXSIZE/QU存放队中元素INTFRONT1,REAR1/队头队尾指针REARQUREARSBT/根结点进队QUREARPARENT1/根结点没有双亲,其PARENT置为1WHILEFRONTREAR/队不空循环FRONTPQUFRONTS/出队一个结点P,它在QU中的下标为FRONTIFPDATAX/找到值为X的结点PRINTF“从根结点到C结点的路径“,PDATAD0PATHDPDATAIQUFRONTPARENTWHILEI1DPATHDQUISDATAIQUIPARENTPRINTF“C“,PATHDFORID1I0IPRINTF“C“,PATHIPRINTF“N“IFPLCHILDNULL/P有左孩子,将左孩子进队REARQUREARSPLCHILDQUREARPARENTFRONT/左孩子的双亲为QUFRONT结点IFPRCHILDNULL/P有右孩子,将右孩子进队REARQUREARSPRCHILDQUREARPARENTFRONT/右孩子的双亲为QUFRONT结点VOIDMAINBTNODEBTELEMTYPEPATHMAXSIZE,XICREATEBTREEBT,“ABD,EG,H,C,FI“/建立图614的二叉链PRINTF“BT括号表示法“DISPBTREEBTPRINTF“N“PRINTF“解法1N“PATH1BT,X,PATH,0PRINTF“解法2N“PATH2BT,X练习题71单项选择题（1）在一个图中，所有顶点的度数之和等于图的边数的（）倍。A1/2B1C2D4答C（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A1/2B1C2D4答B（3）有8个顶点的无向图最多有（）条边。A14B28C56D112答B（4）有8个顶点的无向连通图最少有（）条边。A5B6C7D8答C（5）有8个顶点的有向完全图有（）条边。A14B28C56D112答C（6）N个顶点的强连通图中至少有（）条边。ANBN1C2NDNN1答A（7）若一个图的邻接矩阵是对称矩阵，则该图一定是（）。A有向图B无向图C连通图D无向图或有向图答D（8）设无向图GV,E和GV,E，如果G是G的生成树，则下面的说法中错误的是（）。AG为G的子图BG为G的连通分量CG为G的极小连通子图且VVDG是G的一个无环子图答B（9）用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。A栈B队列C树D图答B（10）用邻接表表示图进行深度优先遍历时，通常是采用（）来实现算法的。A栈B队列C树D图答A（11）图的广度优先遍历算法中用到辅助队列，每个顶点最多进队（）次。A1B2C3D不确定答A（12）一个无向图中包含K个连通分量，若按深度优先搜索方法访问所有结点，则必须调用（）次深度优先遍历算法。AKB1CK1DK1答A（13）已知一个图的邻接表如图71所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）。V00V11V22V331202010233图71一个邻接表A0132B0231C0321D0123答D（14）已知一个图的邻接表如图71所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）。A0132B0231C0321D0123答D（15）深度优先遍历类似于二叉树的（）。A先序遍历B中序遍历C后序遍历D层次遍历答A（16）广度优先遍历类似于二叉树的（）。A先序遍历B中序遍历C后序遍历D层次遍历答D（17）最小生成树指的是（）。A由连通网所得到的边数最少的生成树B由连通网所得到的顶点数相对较少的生成树C连通网中所有生成树中权值之和为最小的生成树D连通网的极小连通子图答C（18）任何一个无向连通图的最小生成树（）。A只有一棵B一棵或多棵C一定有多棵D可能不存在答B（19）用PRIM和KRUSKAL两种算法构造图的最小生成树，所得到的最小生成树（）。A是相同的B是不同的C可能相同，也可能不同D以上都不对答C（20）对于有N个顶点E条边的有向图，求最短路径的DIJKSTRA算法的时间复杂度为（）。AONBONECON2DONE答C（21）对于有N个顶点E条边的有向图，求最短路径的FLOYD算法的时间复杂度为（）。AONBONECON2DON3答D（22）若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图。A是个有根有向图B是个强连通图C含有多个入度为0的顶点D含有顶点数目大于1的强连通分量答D（23）关键路径是事件结点网络中（）。A从源点到汇点的最长路径B从源点到汇点的最短路径C最长的回路D最短的回路答A2填空题（1）N个顶点的连通图至少（）条边。答N1（2）在图的邻接矩阵和邻接表表示中，（）表示一定是唯一的，而（）表示可能不唯一。答邻接矩阵邻接表（3）具有10个顶点的无向图中，边数最多为（）。答45（4）在有N个顶点的有向图中，每个顶点的度最大可达（）。答2N1。（5）N个顶点E条边的图，若采用邻接矩阵存储，则空间复杂度为（）。答ON2（6）N个顶点E条边的有向图，若采用邻接表存储，则空间复杂度为（）。答ONE（7）N个顶点E条边的有向图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为（）；若采用邻接表存储时，该算法的时间复杂度为（）。答ON2ONE（8）N个顶点E条边的有向图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为（）；若采用邻接表存储时，该算法的时间复杂度为（）。答ON2ONE（9）一个连通图的生成树是该图的一个（）。答极小连通子图（10）用普里姆（PRIM）算法求具有N个顶点E条边的图的最小生成树的时间复杂度为（）；用克鲁斯卡尔（KRUSKAL）算法的