算法与数据结构习题

PAGEPAGE18第1章数据结构概论一、判断题1算法可以没有输入语句。2数据的逻辑结构按照数据元素前驱的个数划分为线性与非线性两类，线性的数据结构指数据元素只有一个前驱，非线性的则有多个前驱。3数据结构包括数据间的逻辑结构、数据的存储方式和数据的运算三个方面。二、选择题1算法的时间复杂度取决于。(A)．问题的规模(B)．待处理数据的初态(C)．编码的语言(D)．占用内存的大小2算法与程序的主要区别在于程序可以不满足算法的B。(A)．确定性(B)．有穷性(C)．可行性(D)．健壮性3.算法分析的两个方面是。(A)．空间复杂性和时间复杂性(B)．正确性和简明性(C)．可读性和文档性(D)．数据复杂性和程序复杂性三、填空题1若算法中语句频度之和为，则算法的时间复杂度为。2数据的存储结构分为、、和四种。3在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着、和的关系。4算法的计算工作量大小和实现算法所需的存储单元多少，分别称为计算的和。四、应用题1计算带下划线语句的执行次数，n为已知的正整数。(1)x=91,y=n;while(y>0){if(x>100){x=x-10;y--;}elsex++;}(2)j=0，k=0;while(k<n){j++;k+=10*j;}2一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别。其中：n是问题的规模，为简单起见，可设n是2的整数幂。第2章线性表一、判断题1线性关系的逻辑结构与存储结构总是一致的。2每种数据结构都包括插入、删除和查找这三种基本运算。3线性表中的每个结点最多只有一个前驱和一个后继。4线性的数据结构既可以顺序存储，也可以链接存储；非线性的数据结构则只能链接存储。5顺序存储方式只能用于存储线性结构。6多维数组是向量的推广。7设串s的长度为n，则s的子串个数最多为n(n+1)/2。8单链表从任何一个结点出发，都能访问到所有结点。9线性表的长度是线性表所占用的存储空间的大小。10双循环链表中，任意一结点的后继指针均指向其逻辑后继。11数据结构、数据元素、数据项在计算机中的映象(或表示)分别称为存储结构、结点、数据域。12线性表的顺序存储结构优于链式存储结构。二、选择题1若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为，元素的移动次数为(0≤i≤n)。(A)．O(0)(B)．O(1)(C)．O(n)(D)．O(n2)(E)．n-i+1(F)．n-i(G)．i(H)．i-12在长度为n的顺序存储的线性表中，删除第i个元素(0≤i≤n-1)时，需要从前向后依次前移个元素。(A)．n-i(B)．n-i+1(C)．n-i-1(D)．i3从解决问题的需要出发，为实现必要的功能所建立的数据结构，称为。(A)．物理结构(B)．逻辑结构(C)．数据类型(D)．数据对象4若长度为n的线性表采用顺序存储结构，在其第i(0≤i≤n)个位置插入一个新元素的平均移动元素移动次数为，在其第i(0≤i≤n-1)个位置删除一个元素的平均移动元素移动次数为。(A)．n(B)．(n+1)/2(C)．n/2(D)．(n-1)/25若长度为n的无序线性表采用顺序存储结构，在其中查找某个元素时，所需要的平均比较的次数为。(A)．n(B)．(n-1)/2(C)．n/2(D)．(n+1)/26对于只在首、尾两端进行插入操作的线性表，宜采用的存储结构为。(A)．顺序表(B)．带头指针的单链表(C)．带尾指针的单循环链表(D)．单链表7在一个单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行。(A)．q->link=p->link；p->link=q；(B)．p->link=q->link；q=p；(C)．q->link=p->link；p=q；(D)．p->link=q->link；q->link=p；8在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行。(A)．HL=p;p->next=HL;(B)．p->link=HL;HL=p;(C)．p->link=HL;p=HL;(D)．p->link=HL->link;HL->link=p;9在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行。(A)．p=q->link;p->link=q->link;deletep;(B)．p=q->link;q->link=p;deletep;(C)．p=q->link;q->link=p->link;deletep;(D)．q->link=q->link->link;q->link=q;10设p为有头结点双向循环链表中某结点的指针，lLink为左链指针，rLink为右链指针，则下述表达式中，不恒为真。(A)．p->rLink->lLink==p(B)．p->rLink->lLink==p->lLink->rLink(C)．p->lLink->rLink==p(D)．p->rLink->rLink==p->lLink->lLink11若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用存储方式最节省时间。(A)．单链表(B)．双向链表(C)．带头结点的双循环链表(D)．单循环链表12链表不具有的特点是。(A)．可随机访问任一元素(B)．插入删除不需要移动元素(C)．不必事先估计存储空间(D)．所需空间与线性表长度成正比13线性表采用链式存储时，其地址。(A)．连续的(B)．部分连续的(C)．一定是不连续的(D)．连续与否均可14设有一8×8下三角矩阵A[8][8]，采用按行压缩存储的方式存放在一维数组B[]中，则数组B[]的容量至少需要个元素空间。(A)．32(B)．36(C)．16(D)．64三、填空题1对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。2在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为，若假定p为一个数组a中的下标，则其后继结点的下标为。3在单循环链表中，最后一个结点的指针指向结点。4在双向链表中每个结点包含有两个指针域，一个指向其结点，另一个指向其结点。5在双向循环链表中表头结点的左指针域指向结点，最后一个结点的右指针域指向结点。6在以HL为表头指针的带附加表头结点的单链表和单循环链表中，链表为空的条件分别为和。7在双循环链表L中，指针p所指结点为尾结点的条件为。8在单链表中，如果要使指针p指向它所指结点的后继结点，其语句是。9在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的、和三项。10二维数组A[4][5]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4]的存储地址为。如果其余条件不变，但是数组的存放方式变为列序优先，则元素A[3][4]的存储地址变为。四、算法设计1编写算法将以数组表示方式的顺序表原地逆置。2对于带附加头结点的单链表，给出下列算法的代码。(1)假设单链表中结点的数据域中数据依升序排列，将名为newNode，数据域数据为x的结点插入到该单链表中。(2)从无序的单链表中查找出所有元素的最大值，该值由函数返回；若单链表为空，则显示出错信息并停止运行。(3)统计出单链表中结点的值等于给定值x的结点数。五、阅读算法并描述其功能1函数1代码如下:intfun1(intx){inti=0;while(i<=last&&data[i]!=x) i++;if(i>=0&&i<=last){ last--; for(intj=i;j<=last;j++) data[j]=data[j+1]; return1;}return0;}2函数2代码如下:intfun2(intx){inti=0,flag=0;while(i<=last&&!flag) if(data[i]!=x)i++;elseflag=1;returnflag;}六、简答题线性结构可用顺序表或链表存储。试问：(1)两种存储表示各有哪些主要优缺点?(2)如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变，在此情况下，应选用哪种存储表示?为什么?(3)若表中很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示?为什么?

第3章栈和队列一、判断题1单链表形式的队列，头指针f指向队列的第一个结点，尾指针r指向队列的最后一个结点。2栈和队列逻辑上都是线性表，都是限制存取点的线性结构。3消除递归不一定需要使用栈。4递归工作栈的纪录包括返回地址与本层的所有局部变量值。二、选择题1在一个顺序队列中，队首指针指向队首元素的位置。(A)．前一个(B)．后一个(C)．当前2假定一顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为。(A)．f+1==r (B)．r+1==f(C)．f==0(D)．f==r3输入序列为1，2，3，4，不可能通过栈得到的输出序列有。(A)．4312(B)．3421(C)．1342(D)．3124(E)．1324(F)．23414对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若以循环队列的方式管理队列中的数据，则队列中元素的个数为。(A)．R-F (B)．n+R-F(C)．(R-F+1)modn(D)．(n+R-F)modn5栈的插入与删除操作在进行。(A)．栈顶(B)．栈底(C)．任意位置(D)．指定位置6当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行语句修改top指针。(A)．top++(B)．top--(C)．top=0(D)．top7若让元素1，2，3依次进栈，则出栈次序不可能出现种情况。(A)．3，2，1(B)．2，1，3(C)．3，1，2(D)．1，3，28在一个循环顺序队列中，队首指针指向队首元素的位置。(A)．前一个(B)．后一个(C)．当前(D)．后面9当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为。(A)．N-2(B)．N-1(C)．N(D)．N+110从一个循环顺序队列删除元素时，首先需要。(A)．前移一位队首指针(B)．后移一位队首指针(C)．取出队首指针所指位置上的元素(D)．取出队尾指针所指位置上的元素11假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是。(A)．f+1==r(B)．r+1==f(C)．f==0(D)．f==r12假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是。(A)．front==rear(B)．front!=NULL(C)．rear!=NULL(D)．front==NULL三、填空题1对于单链表形式的队列，其空队列的F指针和R指针都等于。2用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是和；若只设尾指针，则出队和入队的时间复杂度分别是和。3从一个链栈中删除一个结点时，需要把栈顶结点的指针域的值赋给。4当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件为。5假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为。6对于顺序存储的栈，因为栈的空间是有限的，在进行运算时，可能发生栈的上溢，在进行运算时，可能发生栈的下溢。7栈又称为表，队列又称为表。四、写出算法的运行结果设队列Q={11,23,37,47,59}，其中11为队头元素，59为队尾元素。函数Invert(Q)的伪代码如下：voidInvert(Queue&Q){StackS;S.MakeEmpty();while(!Q.IsEmpty())S.Push(Q.DeQueue());while(!S.IsEmpty())Q.EnQueue(S.Pop());}(1)执行函数Invert(Q)之后，队列Q的最终状况是什么；(2)用程序验证你的结论。五、算法设计题1假设以数组Q[0…m-1]存放循环队列中的元素，同时以rear和length分别表示循环队列中的队尾位置和队列中所含元素个数。试给出该循环队列的判空函数(IsEmpty)、判满函数(IsFull)、入队函数(EnQueue)和出队函数(DeQueue)。2若使用循环链表来表示队列，p是链表中的一个指针。试基于此结构给出队列的判空函数、入队函数和出队函数。3已知head为单链表的表头指针，链表中存储的都是整型数据，试写出实现下列运算的递归算法。(1)求链表中的最大整数;(2)求链表的结点个数;(3)求所有结点值之和。

第4章树一、判断题1在只有度为和度为的结点的叉树中，设度为的结点有个，度为的结点有个，则有。2一般树和二叉树的全部结点个数均可以为0。3具有个结点的树，其全体结点的度数之和为。4用树的前序遍历和中序遍历可以导出树的后序遍历。5将一棵树转换成二叉树后，该二叉树没有根结点。6用二叉链表存贮n个结点的二叉树时，结点的2n个指针域中有n+1个为空。7去掉一颗非空树的根，这颗树就变成了一个森林。8在二叉树中，设度为的结点有个，度为2的结点有个，则有。9如果约定遍历的次序是先左子树，后右子树，则二叉树的各遍历序列中，各叶子结点的相对次序决不会发生改变。10按照堆的定义，如果存在左右子女，则堆中任一子树根结点的关键码均大于其左子女的关键码，但小于其右子女的关键码。11Huffman树一定是满二叉树。12Huffman树是带权路径长度最短的树，路径上权值较大的结点离根较近。二、选择题1下列关于二叉树的陈述中，正确的是（）。(A)．二叉树是度为2的有序树(B)．二叉树中结点只一个孩子时无左右之分(C)．二叉树中必有度为2的结点(D)．二叉树最多只有两棵子树，且有左右之分2若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（）。(A)．9(B)．11(C)．12(D)．不确定3一个二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。(A)．CABDEFG(B)．BCDEAFG(C)．DBACEFG(D)．EBACDFG4高度为的满二叉树(仅含根结点的二叉树高度为零)的结点个数（）。(A)．(B)．(C)．(D)．5有64个结点的完全二叉树的深度是（）。(A)．8(B)．7(C)．6(D)．56设二叉树中有个度为0的结点，个度为1的结点，个度为2的结点，则（）。(A)．(B)．(C)．(D)．7已知某二叉树的结点的后序序列是BDECA,中序序列是BADCE,前序序列是（）。(A)．EDCBA(B)．ABCDE(C)．CDABC(D)．CDEBA8树有几个根结点()。(A)．0个或1个(B)．0个可多个(C)．有只有1个(D)．或1个以上9A另有3个兄弟，B是A的双亲，B的度()(A)．3(B)．4(C)．5(D)．110某二叉树的前序序列与后序序列正好相反，则该二叉树是（）。(A)．空或只有一个结点(B)．高度等于其结点数(C)．任一结点无左孩子(D)．任一结点无右孩子11将树转换成二叉树，其对应的二叉树的根结点的右孩子（）。(A)．为空(B)．指向其它孩子(C)．指向其兄弟(D)．指向最后一个结点12将一棵有100个结点的完全二叉树从根这一层开始,每一层上从左到右依次对结点进行编号,根结点的编号为1，则编号为49结点的左孩子编号是（）。(A)．98(B)．99(C)．50(D)．4813将森林转换成二叉树，其对应的二叉树的根结点的右孩子（）。(A)．空(B)．指向其孩子(C)．指向其兄弟(D)．指向第二棵树的根结点14森林的中根次序遍历等同于该森林对应的二叉树的什么遍历序列（）。(A)．前序遍历序列(B)．后序遍历序列(C)．中序遍历序列(D)．都不是15下列关于二叉树的陈述中，正确的是（）。(A)．二叉树是度为2的树(B)．结点只有一个孩子时无左右之分(C)．二叉树中必有度为2的结点(D)．每个结点最多只有两棵子树，而且有左右之分16用二叉链表存贮有n个结点的二叉树时，结点的所有指针域中有（）个为空。(A)．n(B)．n+1(C)．n–1(D)．n/217堆的存储方式是采用（）。(A)．有左右子女指针的二叉链表(B)．带双亲指针与左右子女指针的二叉链表(C)．带双亲指针的三叉链表存储(D)．完全二叉树的顺序存储18由权值为2,3,5,6,8的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。(A)．24(B)．48(C)．55(D)．5319在有n个叶子结点的哈夫曼树中，其结点总数为（）。(A)．不确定(B)．2n(C)．2n+1(D)．2n-1三、应用题1设初始数据为{40,12,64,74,65,63,82,36}，试将其分别调整为最大堆与最小堆。2试分别找出满足以下条件的所有二叉树（1）二叉树的前序序列与中序序列相同；（2）二叉树的中序序列与后序序列相同；（3）二叉树的前序序列与后序序列相同。3判断以下序列是否是堆？如果不是，将它调整为最小堆。（1）{100,86,48,73,35,39,42,57,66,21};（2）{12,24,33,70,33,56,48,92,86,65};（3）{103,97,56,38,66,23,42,12,30,52,06,20};（4）{5,56,20,23,40,38,29,61,35,76,28,99};4假定用于通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成，各字母在电文中出现的频度分别为5，25，3，6，10，11，36，4。试为这8个字母设计不等长的哈夫曼编码，并给出该电文的总码数。5将下图中的树转换成为二叉树。四、算法设计若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：（1）统计二叉树中叶子结点的个数。（2）统计二叉树中的结点个数。（3）计算二叉树的高度。（4）用以下二叉树验证所写算法的正确性（约定：二叉树的创建采用广义表法）

第5章图一、判断题1在一个有向图的邻接矩阵中，其主对角线及主对角线以下的元素均为零，则该图存在着拓扑序列。2在拓扑排序序列中，任意两个相继结点Vi和Vj间都存在一条路径。3用邻接矩阵表示图所用的存储空间大小与图的边数成正比。4图的简单路径绝不可能是回路。5n个结点的无向图最多有n(n-1)条边。6在连通图中，任何一对顶点之间至少存在两条路经。7如果网络上各边的权值是互异的，则它的最小生成树唯一。8图的邻接矩阵表示是惟一的，且无向图的邻接矩阵是一个对称矩阵；而图的邻接表表示是不惟一。二、选择题1在一个无向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。(A)．1/2(B)．1(C)．2(D)．42用邻接矩阵存储图时所需存储空间大小与图的有关。(A)．顶点数(B)．边数(C)．出度(D)．入度3关键路径是顶点网络中。(A)．从源点到汇点的最长路径(B)．从源点到汇点的最短路径(C)．最长的回路(D)．最短的回路4具有n个顶点的无向图最多有条边，n个顶点的有向完全图中含有向边的数目最多为。(A)．n(B)．n(n-1)(C)．n(n+1)(D)．n2(E)．n(n-1)/2(F)．n-15下图是由7个顶点组成的无向图，从顶点1出发进行广度优先遍历，不可能得到的顶点序列是。(A)．1234576 (B)．1754326(C)．1354726(D)．12345676已知一个有向图如下图所示，从顶点A出发进行深度优先遍历，不可能得到的深度优先遍历序列为。(A)．ADEBFC(B)．ADBFEC(C)．ADCEBF(D)．ADCBEF三、填空题1设G为有n个顶点的无向连通图，若采用邻接矩阵存储G，则矩阵大小为；则该矩阵至少有个非零元素。2对于一个具有n个顶点和e条边的连通图，其生成树中顶点数和边数分别为和。3已知邻接矩阵A＝，从中可以看出，该图共有个顶点。如果是有向图，该图共有条边、各顶点的出度分别是、入度分别是；如果是无向图，则共有条边，各顶点的度分别是。4假定一个图具有n个顶点和e条边，当采用邻接矩阵、邻接表表示时，其相应的空间复杂度分别为和。四、应用题1对于下面的带权图，若从顶点0出发，则按照Prim(普里姆)算法，画出最小生成树。2对于如下图所示的有向图，试画出：（1）从顶点①出发进行深度优先搜索所得到的深度优先生成树；（2）从顶点②出发进行广度优先搜索的得到广度优先生成树。3试对下图所示的AOE网络回答下列问题：（1）这个工程最早可以在什么时间结束。（2）求每个活动的最早开始时间TE和最迟开始时间TL。（3）确定哪些活动是关键活动与关键路径。五、算法设计题关于图G的邻接表创建、显示、广度与深度优先遍历函数的共享代码如下，在此基础上，完成以下算法设计。#include<iostream>usingnamespacestd;#defineMAXVEX30//图中最多顶点个数//邻接表中链表结点定义structNode{ intvno;//顶点序号 structNode*next;//指向下一个顶点的指针};intvisited[MAXVEX];//顶点访问标识数组,全局变量intqueue[MAXVEX];//广度优先遍历存储队列,全局变量intstack[MAXVEX];//深度优先遍历存储栈,全局变量//输入有向图的边,建立图的邻接表与邻接矩阵intCreateGraph(Node*LGraph[MAXVEX]){//*LGraph邻接表指针数组 intvn,en,i,j,k; Node*newnode,*p; //输入图的顶点数与边数 while(1) { vn=en=0; cout<<"输入有向图的顶点数[1-30]:"; cin>>vn; if(vn<1||vn>30) {cout<<"输入的顶点数"<<vn<<"超限,重新输入!"<<endl; continue; } //完全有向图的边数最大值为vn*(vn-1) cout<<"输入图的边数[1-"<<vn*(vn-1)<<"]:";cin>>en; if(en>=1&&en<=vn*(vn-1)) break;else {cout<<"输入的边数"<<en<<"超限,重新输入!"<<endl; continue; } } //邻接表初始化 for(i=0;i<vn;i++) { newnode=newNode; newnode->vno=i+1; newnode->next=NULL; LGraph[i]=newnode;//创建邻接链表中每根链的头结点 } //输入有向边,构造邻接表k=0;//边数计数 while(k<en) {i=j=-1; cout<<"输入第"<<k+1<<"条边的出边顶点序号与入边顶点序号"<<endl; cout<<"出边顶点序号:";cin>>i; cout<<"入边顶点序号:";cin>>j; if(i<1||j<1||i>vn||j>vn) {cout<<"输入错误,顶点范围为[1-"<<vn<<"]"<<endl; continue; } k++; //用有向边<i,j>为邻接表赋值 newnode=newNode; newnode->vno=j;//出边顶点j newnode->next=NULL; p=LGraph[i-1];//出边顶点为i,属于第i-1条链 while(p->next!=NULL) p=p->next;//p指向第i-1条链的尾结点 p->next=newnode;//与顶点i相连的顶点j入链尾 } returnvn;//返回图的顶点数}//输出邻接表voidDispLGraph(Node*LGraph[],intn){//*LGraph[]邻接表,n顶点个数 cout<<"有向图的邻接表"<<endl;Node*p; for(inti=0;i<n;i++) { p=LGraph[i];//p指向第i条链表的头结点 cout<<p->vno<<"=>";//输出头结点的顶点序号 while(p->next!=NULL) { p=p->next; cout<<p->vno<<"=>";//输出链表上顶点结点的序号 } cout<<"NULL"<<endl;//输出链表结束符 }}//邻接表表示的图的广度优先遍历voidLBFS(Node*LGraph[],ints,intn){//*LGraph[]邻接表,s出发顶点,n顶点数inti,v,w,front,rear;Node*p;cout<<"广度优先遍历为:";//置全部顶点为未访问标识for(i=0;i<n;i++) visited[i]=0;front=rear=-1;//队列置空queue[++rear]=s;//出发顶点s进队visited[s-1]=1;//置顶点s已被访问标识while(front<rear)//当队列非空时,循环{ v=queue[++front];//队列中队头顶点出队 cout<<v<<"";//输出出队顶点 p=LGraph[v-1];//p指向队头顶点在邻接表中对应的链表 while(p->next!=NULL) {p=p->next; w=p->vno;if(visited[w-1]==0)//顶点w未被访问过 {queue[++rear]=w;//顶点w进队 visited[w-1]=1;//置顶点w已被访问标识 } }}cout<<endl;}//邻接表表示的图的深度优先遍历voidLDFS(Node*LGraph[],ints,intn){//*LGraph[]邻接表,s出发顶点,n顶点数inti,v,w,top;Node*p;cout<<"深度优先遍历为:";//置全部顶点为未访问标识for(i=0;i<n;i++) visited[i]=0;top=-1;//栈置空stack[++top]=s;//出发顶点s进栈visited[s-1]=1;//置顶点s已被访问标识while(top!=-1)//当栈非空时,循环{v=stack[top--];//栈中的栈顶顶点出栈 cout<<v<<"";//输出出栈顶点 p=LGraph[v-1];//p指向出栈顶点在邻接表中对应的链表 while(p->next!=NULL) {p=p->next; w=p->vno;if(visited[w-1]==0)//顶点w未被访问过 {stack[++top]=w;//顶点w进栈 visited[w-1]=1;//置顶点w已被访问标识 } }}cout<<endl;}voidmain(){Node*LGraph[MAXVEX];//邻接表intvexnum;//图中顶点个数vexnum=CreateGraph(LGraph);//创建有向图并返回顶点数DispLGraph(LGraph,vexnum);//输出邻接表LBFS(LGraph,1,vexnum);//从顶点1出发,对有向图作广度优先遍历LDFS(LGraph,1,vexnum);//从顶点1出发,对有向图作深度优选遍历}1、假设图G采用邻接表存储，设计一个算法，判断图G是否连通。若连通则返回1；否则返加0。2、将图顶点的结构体中增加一个顶点入度域，设计一个算法，创建图G的邻接表。3、假设图G采用邻接表存储，设计一个算法，判断图G是否为有向无环图。若是有向无环图则返回1；否则返加0。

第6章排序一、判断题1在待排序文件中，存在多个具有相同关键字的记录，经排序后这些记录的相对顺序仍保持不变，这种排序算法是不稳定的。2快速排序当被排序的数量太大时最不利发挥其长处。3对有n个结点的顺序表进行快速排序，在最坏情况下，其关键字码比较次数为O(n2)。4在n个数据中选取前k个最小元(k<<n，n很大时)，最有效的方法是采用堆排序。5在n个数据中选取前k个的最小元(k<<n，n不是很大时)，最有效的方法是采用直接选择排序。6在n个数据中选取前k个的最小元(k<<n，n不是很大时)，最有效的方法是采用直接插入排序。7一组数据已有序，最快的排序方法是冒泡排序。8一组数据已有序，最快的排序方法是快速排序。9外部排序指的是大文件的排序，即待排序的记录存储在外存上，在排序过程中需进行多次的内、外部之间的交换。10稳定的内部排序方法有基数排序，快速排序和归并排序。11稳定的内部排序方法有改进的选择排序、冒泡排序、插入排序和希尔排序。二、填空题1当从一个最小堆中删除堆顶元素时，需要把元素填补到位置，然后再按形成最小堆的条件，将这些元素逐层调整。2在一个最小堆中，堆顶结点的值是所有结点中的，具有最大值的元素可能在。在一个最大堆中，堆顶结点的值是所有结点中的。3每次直接比较两个元素，若出现逆序时就交换它们的位置，该方法称之为排序。4用冒泡法对n个关键码排序，在最好情况下，只需做次比较和次移动；在最坏的情况下要做次比较和次移动。5设关键码序列为{46,79,56,38,40,80,25,34}，若采用首个元素为支点的快速排序，在整个排序过程中，所取的支点分别为。三、应用题1对于含12个关键码的序列{236,295,704,612,123,734,74,665,742,512,254,469}，按照关键码递增次序进行排序，试给出以下问题的解。（1）采用冒泡排序，写出第1趟排序的结果。（2）采用插入排序，写出第4趟排序的结果。（3）若采用初始步长为4的希尔排序，写出第1趟排序的结果。（4）若采用以第一个元素为支点的快速排序法，写出第1趟排序结果。（5）采用堆排序，假定将关键码序列调成最大堆为第1趟排序，写出第2趟排序结果。（6）采用基数排序，写出第2趟排序结果。2用递归方式，改写选择排序法。第7章查找一、选择题1.对n个元素的顺序表顺序查找，若查找每个元素的概率相同，则平均查找长度为()。(A)．(n+1)/2(B)．n/2(C)．n(D)．n(n+1)/22.对线性表进行折半查找时，要求线性表必须（）(A)．以顺序方式存储(B)．以顺序方式存储，且数据元素有序(C)．以链接方式存储(D)．以链接方式存储，且数据元素有序3．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()。(A)．（100，80，90，60，120，110，130）；(B)．（100，120，110，130，80，60，90）；(C)．（100，60，80，90，120，110，130）；(D)．（100，80，60，90，120，130，110)。4.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造哈希表，哈希函数为H(key)=key%13,哈希地址为1的链中有（）个记录。(A)．1(B)．2(C)．3(D)．45.设哈希表长为11，哈希函数是H(key)=key%11，表中已存入关键字为15，38，61，84这四个关键字。现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()(A)．8(B)．3(C)．5(D)．9二、判