福建师范大学《数据结构与算法》期末练习题(有答案)

福建师范大学数学与计算机学院计算机科学与技术《数据结构与算法》期末练习一选择题1．以下与数据的存储结构无关的术语是（D）。A．循环队列B.链表C.哈希表D.栈2.算法的时间复杂度取决于（A）A．问题的规模B.待处理数据的初态C.A和BD.计算机cpu3.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（B）。A.23415B.54132C4.有关静态链表的叙述：(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（B）A．（1），（2）B．（1）C．（1），（2）,(3)D.（2）5．对于有n个结点的二叉树,其高度为（D）A．nlog2nB．log2nC．ëlog2nû|+1D．不确定6．从下列有关树的叙述中,选出正确的叙述（C）A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B．当K≥1时高度为K的二叉树至多有2k-1个结点。C．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。D．在二叉树中插入结点,该二叉树便不再是二叉树。7．设无向图的顶点个数为n，则该图最多有（B）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n8．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（A）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V79．下列排序算法中，其中（D）是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.希尔排序，归并排序D.归并排序，冒泡排序10．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447(4）152125478411.则采用的排序是(A)。A.选择B.冒泡C.快速D.插入12．以下数据结构中，哪一个是线性结构（D）？A．广义表B.二叉树C.稀疏矩阵D.串13．下面关于线性表的叙述中，错误的是哪一个？（B）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。14.设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D）。A.51234B.45132C.43125D.3215415.设n为正整数.下列程序段中前置以@的语句的频度为（）。i=1;k=0;do{@k+=10*i;i++;}While(i<=n-1);A.n–1B.nC.n+1D.n-216.一棵具有n个结点的完全二叉树的树高度（深度）是（A）A．ëlognû+1B．logn+1C．ëlognûD．logn-117．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B）。A.不确定B.n-i+1C.iD.n-i18．n个结点的完全有向图含有边的数目（D）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）19．稳定的排序方法是（B）A．直接插入排序和快速排序B．折半插入排序和起泡排序C．希尔排序和四路归并排序D．树形选择排序和shell排序20．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为(A)（按递增序）。A．下面的B，C，D都不对。B．9，7，8，4，-1，7，15，20C．20，15，8，9，7，-1，4，7D.9，4，7，8，7，-1，15，2021．以下那一个术语与数据的存储结构无关？（A）A．栈B.哈希表C.线索树D.双向链表22．下面关于串的的叙述中，哪一个是不正确的？（B）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储23.某堆栈的输入序列为a,b，c，d,下面的四个序列中，不可能是它的输出序列的是（D）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b24.关于二叉树的叙述：①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。正确的是（D）A．①②③B．②③④C．②④D．①④25．高度为K的二叉树最大的结点数为（C）。A．2kB．2k-1C．2k-1 D．2k-126．从下列有关树的叙述中,选出正确的叙述（C）A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B．当K≥1时高度为K的二叉树至多有2k-1个结点。C．用树的前序遍历和中序遍历可以导出树的后序遍历。D．哈夫曼树是带权路径最长的树,路径上权值较大的结点离根较近。27.关键路径是事件结点网络中（A）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路28．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是(A)。A．逆拓扑有序B．拓扑有序C．无序的29．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C）。A．(38,40,46,56,79,84)B.(40,38,46,79,56,84)C．(40,38,46,56,79,84)D.(40,38,46,84,56,79)30.一个向量的第一个元素的地址是begin，每个元素的长度是k，则第i个元素的地址是(D)A.begin+(k-1)iB.begin+(k-2)iC.begin+kiD.begin+(i-1)k31.有一个有序表为{1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找63，要经过(C)次与63比较。A.12B.6C.4D.32.一个序列的初始状态为（46，77，82，53，31，70），今对其进行冒泡排序，当进行两趟冒泡后，序列中的元素排列为(D)。A.（31，46，70，53，77，82）B.（46，77，53，31，70，82）C.（46，31,82，53，77，70）D.(46，53，31，70，77，82)33.将一个长度为n的向量的第i个元素删除时，需要前移(B)个元素。A.iB.n-iC.n+1D.n-i+134.不带表头的单链表，头指针为head，判断其是否为空的条件是(A)A.head==0B.head->next==nullC.head==headD.head->next==head35.在一个单链表中，已知*q是（*q表示指针q所指的结点，以下同）*p的前驱结点，在*q之后插入结点*s，正确的操作步骤序列是(A)。A)q->next=s;s->next=pB)s->next=p->next;q->next=s;C)p->nexr=s;s->next=p;D)p->next=s;s->next=q;36.非空循环链表head的尾结点*p满足下列(C)条件A)head->next==p;B)head==p;C)p->next==head;D)p->next==037.一个栈的输入序列是a,b,c,d,e，则可能的出栈序列是(D)。A.ecdabB)cebdaC)daecbD)abcde38.设栈s的类型为sqstack，判定栈空的条件是(C)。A.s==NULLB)s->top==0C)s.top==0D)s.top==NULL39.深度为5的二叉树至多有个(B)结点。A.12B.31C.14D.1540.已知二叉树的后、中根序列分别是bedfca和badecf，则该二叉树的前根遍历序列是(C)。A)defbcaB)fedbcaC)abcdefD)fedcba41.一个有n个顶点的有向图最多有(B)弧。A)n(n+1)B)n(n-1)C)n(n+1)/2D)n(n-1)/242.具有n个顶点的无向图至少要有(B)条边才有可能是一个连通图。A)n(n+1)B)n-1C)n+1D)n(n-1)43.已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是(B)。A)1234B)1423C)1324D)14324^4^2^3^3^4^2^4^123444.一个向量的第一个元素的地址是100，每个元素的长度是2，则第五个元素的地址是(C)A)102B)110C)108D)12045.一个循环顺序队列,队头、尾指针的值分别为front,rear，则队列中元素个数为(A)。（maxlen为循环顺序表的长度）A.(rear-front+maxlen)%maxlenB.(rear-front)%maxlenC.rear-front+1D.front-rear+146.一个有n个顶点的图最少有(D)条边。A)n(n+1)B)n(n-1)C)n(n+1)/2D)047.具有5个顶点的无向图至少要有(A)条边才能确保是一个连通图。A)4B)5C)6D)748.设栈s的类型为sqstack，最多可容纳maxlen个元素，则判定栈满的条件是(B)。A.s==maxlen-1B)s.top==maxlen-1C)s->top==maxlen-1D)s.top=49.一个顺序队列q的类型为sqqueue,队头、尾指针分别为front,rear，最多可容纳maxlen个元素，则队空的条件是(C)。A)front==rearB)rear==0C)q.front==q.rearD)rear==maxlen-150.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(B)A.O(1)B.O(n)C.O(nlogn)D.O(n*n)51.链栈与顺序栈相比，比较明显的优点是(D)A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况52.二叉树中第5层上的结点个数最多为(C)A.8B.15C.16D.3253.下列编码中属前缀码的是(A)A.{1,01,000,001}B.{1,01,011,010}C.{0,10,110,11}D.{0,1,00,11}54.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（B）A．深度优先搜索算法 B．广度优先搜索算法C．求最小生成树的prim算法 D．拓扑排序算法55.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为(B)A.O(1)B.O(logn)C.O(n)D.O(nlogn)56.对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为(C)A.(n-1)/2B.n/2C.(n+1)/2D.n57.对于哈希函数H(key)=key%13,被称为同义词的关键字是(D)A.35和41B.23和39C.15和44D.25和5158.关于线性表的说法,下面选项正确的是（B）A线性表的特点是每个元素都有一个前驱和一个后继B线性表是具有n(n>=0)个元素的一个有限序列C线性表就是顺序存储的表D线性表只能用顺序存储结构实现59.表长为n的顺序存储的线性表，当在任何一个位置上插入或者删除一个元素的概率相等时，删除一个元素需要移动元素的平均个数为（A）A(n-1)/2Bn/2CnDn-160.设双向循环链表中节点的结构为(data,LLink,RLink)，且不带头节点。若想在指针p所指节点之后插入指针s所指节点，则应执行下列哪一个操作？（D）Ap->RLink=s;s->LLink=p;p->RLink->LLink=s;s->RLink=p->RLink;Bp->RLink=s;p->RLink->LLink=s;s->LLink=p;s->RLink=p->RLink;Cs->LLink=p;s->RLink=p->RLink;p->RLink=s;p->RLink->LLink=s;Ds->LLink=p;s->RLink=p->RLink;p->RLink->LLink=s;p->RLink=s;61.栈和队列都是（A）A限制存取位置的线性结构B链式存储的非线性结构C顺序存储的线性结构D限制存取位置的非线性结构62.单循环链表表示的队列长度为n，若只设头指针，则入队的时间复杂度为（A）AO(n)BO(1)CO(n*n)DO(n*logn)63.一棵含有n个节点的k叉树，可能达到的最小深度为多少？（C）An-kBn-k+1C|logkn|+1D|logkn|其中|k|表示下取整64.下列序列中(B)不是堆。A.12365368486075B.12485368366075C.12483660756853D.1236605348687565.在下列内排序方法中，(C)的平均时间复杂性是O(nlogn)。A.直接插入排序B.简单选择排序C.快速排序D.希尔排序66.设顺序栈s非空，则语句段(C)可实现栈s的出栈操作，其中s.top为栈顶指针，s.elem为栈空间，出栈的元素存放在x中。A.s.top:=s.top+1;B.x:=s.elem[s.top];x:=s.elem[s.top];s.top:=s.top+1;C.s.top:=s.top-1;D.x:=s.elem[s.top];x:=s.elem[s.top];s.top:=s.top-1;67.已知L是带头结点的单链表，p指向表中某结点，则要删除p结点的后继结点应执行操作(A)；要在p结点后插入s结点应执行操作(D)。A.pnext:=pnextnext;B.pnextnext:=.next;C.pnext:=s;snext:=pnext;D.snext:=pnext;pnext:=s;68.下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（D）。A．二叉排序树B．哈夫曼树C．AVL树D．堆69.下面给出的四种排序法中(D)排序法是不稳定性排序法。A.插入B.冒泡C.二路归并D.快速排序70.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（C）。A.快速排序B.堆排序C.归并排序D.直接插入排序二填空题1、在单链表L中，指针p所指结点有后继结点的条件是：p->next!=null2、表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是：(请在表达式中用点(.)将数隔开)23.12.3*2-4/34.5*7/++108.9/+3、有一个100*90的稀疏矩阵，非0元素有9个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是604、深度为9的完全二叉树至少具有的个结点2565、已知二叉树后序为DGEBFCA，中序为DBGEACF，则前序一定是ABDEGCF6、先根遍历树林正好等同于按___遍历对应的二叉树.先序7、构造n个结点的强连通图，至少有_______条弧。n8、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为6,9,11,129、在单链表指针为p的结点之后插入指针为s的结点的操作是：s->next=p->next;p->next=s;10、有N个顶点的有向图，至少需要量_______条弧才能保证是连通的。N-111、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值12，需做的关键码比较次数为413、下面是一个无向图的邻接矩阵，试将有关数据填入本题的空白处（顶点号由1开始）0101110100010101010110010该图的顶点数为该图的边数为顶点3的度为。56214、后根遍历树林正好等同于按__(6)_遍历对应的二叉树。中序15、n个结点的完全有向图含有边的数目__(7)n*（n－l）16、当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的________。时间复杂度17、假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为___________。SXSSXXSSXSSXXX18、在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是________。（注：没有包含度为1的结点）219、如图所示的有向无环图可以排出________种不同的拓扑序列。1220、利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(________)。75,66,48,29,31,3721、对长度为20的有序表进行二分查找的判定树的高度为________。522、n个顶点的连通无向图，其边的条数至少为________________________。n-123、排序(sorting)有哪几种方法_______________，_____________，____________，_____________，____________。直接插入排序，冒泡排序，快速排序，希尔排序，归并排序，基数排序，堆排序等24、下面程序段的时间复杂度为______________。（用O估计）FORi:=1TOnDOFORj:=iTOnDOs=s+j;O（n*n）25、非线性结构包括______________和_________________。树，图26、在线性表的___________存储结构上进行插入或删除操作要移动元素。顺序存储结构27、用一维数组r[0..m-1]表示顺序存储的循环队列，设队头和队尾指针分别是front和rear，且队头指针所指的单元闲置，则队满的条件是______________________________，队空的条件是_____________________________。Front=rear,rear+1=front28、下面表达式树所对应的表达式的前缀表达式是_____________________________，后缀表达式是____________________________。+*a-bc/de,abc-*de/+29、在AOE-网中，设e(i)和l(i)分别表示活动的最早开始时间和最晚开始时间，则当且仅当_________________时，为关键活动。e(i)==l(i)30．对有向图进行拓扑排序，若拓扑排序不成功，则说明该图_________________。下面有向图的一个拓扑有序序列是______________________________。存在回路，12345679831、二叉排序树的特点是其序列是有序的。中序遍历三简答题1、名词解释：（1）抽象数据类型；（2）算法的时间复杂性； （3）散列法(hashing)；（4）索引文件。（1）抽象数据类型：（课本P7）是指一个数学模型以及定义在该模型上的一组操作。（2）算法的时间复杂性；（课本P15）一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间量度记作T(n)=O(f(n))，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。（3）散列法(hashing)：（课本P253）散列法（Hashing）或哈希法是一种将字符组成的字符串转换为固定长度（一般是更短长度）的数值或索引值的方法。根据设定的哈希函数和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为哈希表，这一映像过程称为哈希造表或散列。（4）索引文件：

（课本P311）

除了文件本身（称作数据区）之外，另建立一张指示逻辑记录和物理记录之间一一对应关系的表---索引表。这类包括文件数据区和索引表两大部分的文件称作索引文件。

索引表中的每一项称作索引项，一般索引项都是由主关键字和该关键字所在记录的物理

地址组成的。显然，索引表必须按主关键字有序，而主文件本身则可以按主关键字有序或无

序，前者称为索引顺序文件（IndexedSequentialFile），后者称为索引非顺序文件（IndexedNonSequentialFile）。2、堆与二元查找树的区别?（课本P280）堆的定义如下：n个元素的序列{Kl，K2，…，Kn}当且仅当满足如下关系时，称之为堆：(1)ki≤K2i且ki≤K2i+1或(2)Ki≥K2i且ki≥K2i+1(1≤i≤)若将和此序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于(或不小于)其左右孩子结点的值。由此，若序列{Kl，K2，…，Kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。（课本P227）二叉排序树又称二元查找树（BinarySearchTree），或者是一棵空树，或者是具有下列性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）它的左、右子树也分别为二叉排序树。3、快速分类法的基本思想是什么?（课本P273）快速排序是对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。4、如下所示的是一个带权无向图，带框的数字表示相应边的权，不带框的数字表示顶点号。用prime算法求最小生成树时，如果已确定的边为(5,4),则，下一条边应在哪几条边中选取？选取哪一条？11234565723415438下一条边应在（5，1），（5，6），（4，6），（4，3）中选取，根据MST性质应该选取（4，6）。5、二叉树的后根遍历的序列中，任何一个非叶子结点均处在其孩子结点后面。该论断是否正确？正确6、有一棵哈夫曼树共有5个叶子结点其权值分别为0.1,0.25,0.08,0.21,0.9,试画出该哈夫曼树。假设该叶子分别表示a,b,c,d,e，分别给出五个叶子对应的哈夫曼编码。0000，0001，001，01，17、对于一个队列，若入队的顺序为a,b,c,则所有可能的出队序列是什么？a,b,c8、已知一个图如下，试画出其逆邻接链表。22134注意：课本P164，逆邻接表是为了便于确定顶点的入度。9、若一个栈的输入序列是1,2,3……，n,其输出序列为p1,p2,……pn,若p1=n，则pi为多少？Pi=n-i+110、非空的二叉树的中根遍历序列中，根的右子树的所有结点都在根结点的后边，这说法对吗？正确11、已知二叉树的中根遍历序列为abc，试画出该二叉树的所有可能的形态。5种12、已知一个图如图所示，如从顶点a出发进行按深度优先遍历，可否得到序列acebdf?为什么？若按广度优先遍历，能否得到序列abedfc?为什么？ddabcef不行，不行根据深度优先和广度优先遍历的规则13、栈的存储方式有哪两种？顺序存储结构和链式存储结构14、对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p，能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断，若可以，写出程序段；否则说明理由。其中：datenext单链表和单循环链表的结点结构为priordatenext双向链表的结点结构为1.单链表不行，因为单链表没有办法得到其前驱；

2.单循环链表可以，假设链表的元素大于等于2：

structNode

{

Node*next;

intdata;

};

循环链表Node*list;

Node*pnode=p;

while(pnode->next!=p)

{

pnode=pnode->next;

}

//找到其前驱了

inttmp=pnode->data;

pnode->data=p->data;

p->data->tmp;

3.双向链表可以，假设链表的元素大于等于2，且p不为链表头。

structNode

{

Node*next;

Node*pre;

intdata;

}

双向链表list;

Node*pnode=p;

if(p->pre!=NULL)

{

inttmp=p->data;

p->data=p->pre->data;

p->pre->data=tmp;

}15、假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。（1）根据哈夫曼编码的规则画树。（课本P146）（2）（具体计算方法见课本P146）该哈夫曼树的带权路径长度：25316、对于线性表的两种存储结构（顺序存储和链式存储结构），如果线性表基本稳定，并且很少进行插入和删除操作，但是要求以最快速度存取线性表中的元素，则应选择哪种存储结构？试说明理由。（期中试题）顺序存储17、内存中一片连续空间（不妨假设地址从1到m）提供给两个栈s1和s2使用，怎样分配这部分存储空间，使得对任一栈，仅当这部分空间全满时才发生上溢。如何判断栈满，栈空，并对两个栈的容量进行分析。（期中试题）18、设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。（1）试画出该二叉树；（2）画出该二叉树后序线索化图。（3）试画出该二叉树对应的森林。（期中试题）19、一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。从上到下，从左到右依次为：5，1，9，4，6，2，7，3，820、试证明：若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i<j<k,使Pj<Pk<Pi。如果i<j，则对于pi<pj情况，说明pi在pj入栈前先出栈。而对于pi>pj的情况，则说明要将pj压到pi之上，也就是在pj出栈之后pi才能出栈。这就说明，对于i<j<k，不可能出现pj<pk<pi的输出序列。换句话说，对于输入序列1，2，3，不可能出现3，1，2的输出序列。【详细参考】因为借助栈由输入序列1,2,3,…,n,可得到输出序列p1,p2,p3,…,pn,如果存在下标i,j,k,满足i<j<k,那么在输出序列中,可能出现如下5种情况:i进栈,i出栈,j进栈,j出栈,k进栈,k出栈.此时具有最小值的排在最前面pi位置,具有中间值的排在其后pj位置,具有最大值的排在pk位置,有pi<pj<pk,不可能出现pj<pk<pi的情形;i进栈,i出栈,j进栈,k进栈,k出栈,j出栈.此时具有最小值的排在最前面pi位置,具有最大值的排在pj位置,具有中间值的排在最后pk位置,有pi<pk<pj,不可能出现pj<pk<pi的情形;i进栈,j进栈,j出栈,i出栈,k进栈,k出栈.此时具有中间值的排在最前面pi位置,具有最小值的排在其后pj位置,有pj<pi<pk,不可能出现pj<pk<pi的情形;i进栈,j进栈,j出栈,k进栈,k出栈,i出栈.此时具有中间值的排在最前面pi位置,具有最大值的排在其后pj位置,具有最小值的排在pk位置,有pk<pi<pj,也不可能出现pj<pk<pi的情形;i进栈,j进栈,k进栈,k出栈,j出栈,i出栈.此时具有最大值的排在最前面pi位置,具有中间值的排在其后pj位置,具有最小值的排在pk位置,有pk<pj<pi,也不可能出现pj<pk<pi的情形.四算法阅读1、voidAE(Stack&S){ InitStack(S); Push(S,3); Push(S,4); intx=Pop(S)+2*Pop(S); Push(S,x); inti,a[5]={1,5,8,12,15}; for(i=0;i<5;i++)Push(S,2*a[i]); while(!StackEmpty(S))print(Pop(S));}该算法被调用后得到的输出结果为：（期中试题）2、voidABC(BTNode*BT,int&c1,int&c2){if(BT!=NULL){ABC(BT->left,c1,c2);c1++;if(BT->left==NULL&&BT->right==NULL)c2++;ABC(BT->right,c1,c2);}//if}该函数执行的功能是什么？（期中试题）3、在下面的每个程序段中，假定线性表La的类型为List，e的类型为ElemType,元素类型ElemType为int，并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。（1）InitList(La);Inta[]={100,26,57,34,79};For(i=0;i<5;i++)ListInsert(La,1,a[i]);（2）ListDelete(La,1,e);ListInsert(La,ListLength(La)+1,e);（3）ClearList(La);For(i=0;i<5;i++)ListInsert(La,i+1,a[i]);（期中试题）4、intPrime(intn){inti=1;intx=(int)sqrt(n);while(++i<=x)if(n%i==0)break;if(i>x)return1;elsereturn0;}(1)指出该算法的功能；(2)该算法的时间复杂度是多少？（期中试题）5.写出下述算法A的功能：其中BiTree定义如下:TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;StatusA(BiTreeT){QueueQ;InitQueue(Q);ENQueue(Q,T);While(notQueueEmpty(Q)){DeQueue(Q,e);If(e==NULL)break;Else{Print(e.data);ENQueue(Q,e.LChild);ENQueue(Q.e.RChild);}}}（期中试题）6.阅读下列函数algo,并回答问题：(1)假设队列q中的元素为(2,4,5,7,8),其中“2”(2)简述算法algo的功能。voidalgo(Queue*Q){StackS;InitStack(&S);while(!QueueEmpty(Q))Push(&S,DeQueue(Q));while(!StackEmpty(&S))ＥnQueue(Q,Pop(&S));}（1）q=(8,7,5,4,2)（2）算法利用栈S辅助实现队列Q的逆置。五算法填空1、下面是在带表头结点的循环链表表示的队列上，进行出队操作，并将出队元素的值保留在x中的函数，其中rear是指向队尾结点的指针。请在横线空白处填上适当的语句。typedefstructnode{intdata;structnode*next;}lklist;voiddel(lklistrear,int&x);{lklistp,q;q=rear->next;if(_q==rear_________)printf(“itisempty!\n”);else{p=q->next;x=p->data;__q->next=p->next____________;if(_rear==p__________)rear=q;free(p);};};2、堆分配存储方式下，串连接函数。（期中试题）typedefstruct{char*ch；intlen；}HString；HString*s，t;StatusStrCat(s，t)/*将串t连接在串s的后面*/{inti;char*temp;if(temp==NULL)return(0);for(i=0;;i++)temp［i］=s->ch［i］;for(;i<s->len+t.len;i++)temp［i］=t.ch［i-s->len］;s->len+=t.len;frs->ch=temp;return(1);}3、向单链表的末尾添加一个元素的算法。（期中试题）LNode是一个包含（data，Next）的结构体VoidInsertRear(LNode*&HL,constElemType&item){LNode*newptr;newptr=newLNode;If(______________________){cerr<<"Memoryallocationfailare!"<<endl;exit(1);}________________________=item;newptr->next=NULL;if(HL==NULL)HL=__________________________;else{LNode*P=HL;While(P->next!=NULL)____________________;p->next=newptr;}}4、L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。LinkListf30(LinkListL,intc){LinkListLc,p,pre;pre=L;p=(1);Lc=(LinkList)malloc(sizeof(ListNode));Lc->next=Lc;while(p!=L)if(p->data>c){pre->next=p->next;(2);Lc->next=p;p=pre->next;}else{pre=p;(3);}returnLc;}(1)L->next;(2)p->next=Lc->next;(3)p=p->next;vertexfirstedge5、已知图的邻接链表的顶点表结点结构为adjvexnext边表结点EdgeNode的结构为下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整的算法。intFindDegree(ALGraph*G,inti)//ALGraph为图的邻接表类型{intdegree,j;EdgeNode*p;degree=(1);for(j=0;j<G->n;j++){p=G->adjlist［j］.firstedge;while((2)){if((3)){degree++;break;}p=p->next;}}returndegree;}(1)0(2)p!=NULL;(3)p->adjvex==i;六简单应用题1、已知一个非空二元树，其按中根和后根遍历的结果分别为：中根：CGBAHEDJFI后根：GBCHEJIFDA试将这样二元树构造出来;若已知先根和后根的遍历结果，能否构造这棵二元树，为什么?若二叉树中各结点的值均不相同，则由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树；但由先序序列和后序序列却不一定能唯一地确定一棵二叉树。由二叉树的前序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。（因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边表示左子树，若左边无元素，则说明左子树为空；右边是右子树，若为空，则右子树为空。）例如，任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。2、对于下图，画出按Kruskal（克鲁斯卡尔）算法和Prim（普里姆）算法构造最小生成树的过程。（根据算法思想画）3、画出由下面的二叉树转换成的森林。（根据二叉树转换成的森林的方法画）4、用Floyed（弗洛伊徳）算法求下图每一对顶点之间的最短路径及其长度，将计算过程的中间和最后结果填入下表：AA(0)A(1)A(2)A(3)12312312312312227223635353531051058585PATHPATH(0)PATH(1)PATH(2)PATH(3)1231231231231acacacacbac2babcbabacbabacbabac3cacbcacbcbacbcbacb5、哈夫曼树在构造时，首先进行初始化存储空间，结果如左下图，当构造完成后，请填写最后状态表，如右下图。（期中考试题）weightParentLchildRchildweightParentLchildRchild123456789101112131415500029000700080001400023000300011000--000--000--000--000--000--000--0001234567891011121314156、考虑右图：(1)从顶点A出发，求它的深度优先生成树(4分)(2)从顶点E出发，求它的广度优先生成树(4分)(3）根据普利姆(Prim)算法，求它的最小生成树(请画出过程)(设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列)(6分)答案如下：七编写算法题1、设计函数，求一个单链表中值为x的结点个数。并将结果放在头结点的data域中。voidcount1(lklisthead,intx){lklistp;intcount=0;p=head->next;while(p!=NULL){if(p->data==x)count++;p=p->next;}head->data=count;}2、设计递归函数，求一棵二叉树的深度。intdepth(bitreptrroot){ if(root==NULL) return0; else { intdep1=depth(root->lchild); intdep2=depth(root->rchild); if(dep1>dep2)returndep1+1; elsereturndep2+1; }}3、设计建立有向图正邻接矩阵的函数（数据输入格式自定）。Typedefstruct{intdata[maxsize][maxsize];intdem,e;}sqgraph;sqgraphcrt(sqgraphg)（可参考实验程序）4、设计函数，将不带表头结点的单链表清除。voidclearList(ListL){Listp;p=L->next;while(p!=NULL){q=p->next;free(p);p=q;}free(L);}5、设计递归函数，求一棵非空的二叉树的深度。intdepth(bitreptrroot){ if(root==NULL) return0; else { intdep1=depth(root->lchild); intdep2=depth(root->rchild); if(dep1>dep2)returndep1+1; elsereturndep2+1; }}6、设线性表A=(a1,a2,a3,…,an)以带头结点的单链表作为存储结构。编写一个函数，删去A中序号为奇数的结点。voidclearOdd(ListA){intcount=1;Listr=A;Listp=A->next;while(p!=NULL){q=p->next;if(count%2==1){r->next=q;free(p);}else{r=p;}p=q;count++;}}7、试编写一个算法，能由大到小遍历一棵二元树。8、假设二元树用左右链表示，试编写一算法，判别给定二元树是否为完全二元树?TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;StatusA(BiTreeT){QueueQ;InitQueue(Q);ENQueue(Q,T);While(notQueueEmpty(Q)){DeQueue(Q,e);If(e==NULL)returnfalse;//不是完全二叉树；Else{ENQueue(Q,e.LChild);ENQueue(Q.e.RChild);}}returntrue;//是完全二叉树；}9、利用直接插入排序的方法对一组记录按关键字从小到大的顺序排序。（算法见课本P265）实现程序：

voidinsert_sort(ElemTypea[],intn)

//待排序元素用一个数组a表示，数组有n个元素

{inti,j;

ElemTypet;

for(i=1;i<n;i++)//i表示插入次数，共进行n-1次插入

{t=a[i];//把待排序元素赋给t

j=i-1;

while((j>=0)&&(t<a[j]))

{a[j+1]=a[j];j--;}//顺序比较和移动

a[j+1]=t;}

}10、给出一棵表示表达式的二叉树，其中运算符和运算对象都用一个字符表示，求该表达式的值。设二叉树用二叉链表表示，表达式中仅包含二元运算，函数operate(a,b,op)可求任何一种二元运算的值，其中参数op表示运算符，a和b分别表示左右两个运算对象。算法中允许直接引用函数operate(函数operate不必定义)，如果需要还允许引用栈和队列的基本操作。（课本P129脚注部分介绍了以二叉树表示表达式的递归定义）intcomputevalue(BiTreeT){if(T!=NULL){if(T->lchild==NULL&&T->rchild==NULL)returnT->data;intvalue1=computevalue(T->lchild);intvalue2=computevalue(T->rchild);returnoperate(value1,value2,T->data);}｝11、编写算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表（可以申明零时变量、指针）。该链表带头节点、头节点和数据节点的结构定义如下typedefstructLNode{ElemTypedata;StructLNode*next;}List,LNode;函数定义：voidinvert(List&L)（期中考试题）12、编写算法计算给定二叉树中叶结点的个数。其中树节点定义如下typedefstructBiTNode{DataTypedata;StructBiTNode*LChild,*RChild;}BiTNode,*BiTree;函数定义：CountLeaf(BiTreeT,int&LeafNum)（期中考试题）13、写出二叉树前根遍历的递归算法已知二叉树结点定义为：structnode{elemtpdata;structnode*lc,*rc;);Typedefstructnode*bitreptr(指向根),*tpointer(指向一般结点);voidpreorder(bitreptrP)//P