算法与数据结构复习题

1、算法与数据结构复习题一、单选题1要求具有同一逻辑结构的数据元素具有相同的特性，其含义为（B）。A. 数据元素具有同一的特点B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致C. 每个数据元素都一样D. 仅需要数据元素包含的数据项的个数相同2. 下列程序段for（i=1;i<=n;i+）Al,j=O;的时间复杂度是（D）。A. 0B.0（0）C.0（1+n）D.O（n）3. 在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入结点*s，则执行操作（0。A. s->next=p->next;p->next=s;B.s->next

2、=p;p->next=sC.q->next=s;s->next=p;D.p->next=s;s->next=q;4. 在一个单链表中，若删除*p结点的后继结点，则执行操作（A）。A. q=p->next;p->next=q_>next;free（q）;B.p=p->next;p->next=p->next->next;free（p）;C.p->next=q->next;free（p->next）;D.p=p->next->next;free（p->next）;5. 设指针p指向双链表的某

3、一结点，则双链表结构的对称性可以用下面的操作来反映（C）。A. p->prior->next=p->next->next;B.p->prior->prior=p->next->prior;C.p->prior->next=p->next->prior;D.p_>next->next=p->prior->prior;6. 表达式a*（b+c）-d的后缀表达式是（B）。A. abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd7. 设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的

4、输出序列不可能是（D）。A.A,B,C,DB.D,C,B,AC.A,C,D,BD.D,A,B,C&设一个栈的输入序列为12345,则借助一个栈所得到的输出序列不可能是（B）。A.23415B.54132C.23145D.154329. 设有一个顺序栈，6个元素1、2、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1,则栈的容量至少应该是（B）。A.2B.3C.5D.610. 设有一个顺序栈的入栈序列是a、b、c,则3个元素都出栈的可能不同排列个数为（B）。A.4B.5C.6D.711.若已知一个栈的入栈序列是1,2,3，n,其输出序列为pl,p2,p3,pn,若p

5、l是n,则pi是(C)oA.iB.n-lC.n-i+1D.不确定12.已知广义表LS=(a,b,c),(d,e,f)，运算head和tail函数取出兀素e的运算是(C)oA.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)13.二维数组A的每个兀素是由6个字符组成的串，其行下标i=0,l，8,列下标为j=1,2.，10o设每个字符占一个字节，若按行先存储，元素A8,5的起始地址与A按列存储时起始地址相同的元素是（B）。A.A8,5B.A3,10C.A5,8D.A0,914. 数组A1.5

6、,1.6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中,则元素A5,5的地址为（A）A.1140B.1145C.1120D.112515. 对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用遍历方式是（C）。A.先序B.中序C.后序D.从根开始的层次遍历16. 某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是（B）。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子17.下列说法正确的是(D)。(1) 二又树按某种方式线索化后，任一节

7、点均有指向前趋和后继的线索(2) 二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前(3) 二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值A.(2)(3)B.(1)(2)C.(1)(3)D.前面的可选答案都不对18. 下面的说法中正确的是(B)。(1) 任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。(2) 按二叉树定义，具有三个节点的二叉树共有6种。A.(1),(2)B.(1)C.(2)D.(1),(2)都错19. 树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是(B)。A. 树的后根遍历与其对应的二叉树的后根遍历相同B. 树的后根遍历与其对应的二叉树的

8、中根遍历相同C. 树的先根遍历与其对应的二叉树的中根遍历相同D. 以上都不对20. 下图的邻接表中，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列是(D)。A.V1V2V3V4V5B.V1V2V3V5V4C.V1V4V3V5V2D.V1V3V4V5V221 .以下说法不正确的是(D)。A. 无向图中的极大连通子图称为连通分量B. 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C. 图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D. 有向图的遍历不可采用广度优先搜索22 .在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A,并已知A的左、右孩

9、子的平衡因子分别为-1和0,则应进行的平衡旋转是(B)。A.LL型B.LR型C.RL型D.RR型23. 设哈希表长为14,哈希函数H(key)=key%11,表中已有数据的关键字为15,38,61,84,四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是(A)。A.8B.3C.5D.924. 对散列文件，以下说法错误的是(D)。A. 散列文件插入、删除方便，不需要索引区且节省存储空间B. 散列文件只能按关键字随机存取且存取速度快C. 经过多次插入、删除后，可能出现溢出桶满的情况D. 散列文件顺序存取方便26. 对有18个元素的有序表作二分查找，则查找A3的比较序列

10、的下标为(D)。A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,327. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1，则应调整以使其平衡，所作的平衡旋转是(C)。A.LL型B.LR型C.RL型D.RR型28. 在n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为(B)。2A.O(n)B.O(log2n)C.O(nlog2n)D.O(n)29下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是（ATA.插入B.选择C.快速D.堆30. 下面关于B树和B+树的叙述中，不正确的

11、结论是（A）。A. B-树和B+树都能有效地支持顺序查找B. B-树和B+树都能有效地支持随机查找C. B-树和B+树都是平衡的多叉树D. B树和B+树都可用于文件索引结构31. 关键路径是事件结点网络中（B）。A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长的回路D.最短的回路32. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（A）oA.nB.2n-1C.2nD.n-133. 下列排序算法中，时间复杂度不受数据初始状态影响，恒为0（nlog2n）的是（A）。A.堆排序B.冒泡排序C.直接选择排序D.快速排序34. 下列排序算法中，某一趟结束后未必能选出一个元素

12、放在其最终位置上的是（D）A.堆排序B.冒泡排序C.快速排序D.直接插入排序35. 数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用最节省时间的排序算法是（A）oA.堆排序B.希尔排序C.快速排序D.直接选择排序36. 数据结构被形式地定义为（D,R）,其中D是（）oA.算法B.操作的集合C.数据元素的集合D.数据关系的集合37. 顺序表是线性表的（A）oA.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构38.在一个单链表中，已知*p结点不是最后结点，若在*p之后插入结点*s，则执行操作（B）A.s->next=p;p->next=s;B.s-

13、>next=p->next;p->next=sC.s->next=p->next;p=s;D.p->next=s;s->next=p;39. 循环队列A0.m-1存放其元素值，用front和rear分别表示队头及队尾，则循环队列满的条件是（A）。A.（Q.rear+1）%m=Q.frontB.Q.rear=Q.front+1C.Q.rear+l=Q.frontD.Q.real=Q.front40. 如果以链栈为存储结构，则出栈操作时（B）oA.必须判栈满B.必须判别栈空C.判别栈中元素类型D.不必作任何判别41.对矩阵压缩存储是为了（B）°A

14、.方便运算B.节省空间C.方便存储D.提高运算速度42. 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1, 则编号为49的结点的左孩子编号为（B）oA.98B.99C.50D.4843. 二义树在线索化后，仍不能有效求解的问题是（D）。A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前趋D.后序线索二又树中求后序后继44. 对于关键字序列（12,13,11,18,60,15,7,18,25,100），用筛选法建堆，则开始结点的键值必须为（C）oA.100B.12C.60D.1545. 无向图G=（VE）

15、，其中V=a,b,C,d,e,f,E=<a,b>,<a,e>,<a,c>,<b,e>,<c,f>,<f,d>,<e,d>，对该图进行深度优先排序，得到的顶点序列正确的是（D）oA.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b46. 设图G用邻接表存储，则拓扑排序的时间复杂度为（B）oA.D（n）B.O（n+e）C.O（nxn）D.0（nxe）47. 关于散列法查找说法正确的是（B）oA. 采用链地址解决冲突时，查找一个元素的时间是相同的B. 采用链地址解决

16、冲突时，若规定插入总是在链首，则插入任一个元素的时间是相同的C. 采用链地址解决冲突容易引起聚集现象D. 再散列不易产生聚集48在平衡二叉树中插入一个结点后引起了不平衡，设最低（最接近于叶子）的不平衡点是A,并已知A的左、右孩子的平衡因子分别为-1和0,则应进行的平衡旋转是（B）。A.LL型B.LR型C.RL型D.RR型49. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（D）。A.G中有弧<Vi,Vj>B.G中有一条从Vi到Vj的路径C.G中没有弧<Vi,Vj>D.G中有一条从Vj到Vi的路径50. 排序算法中，算法可能会出现下面情况：初

17、始数据有序时，花费的时间反而最多的是（C）。A.堆排序B.冒泡排序C.快速排序D.SHELL排序二、填空（问答）题1. 数据结构被形式地定义为（D,R）,其中D和R的含义是什么。（D是数据元素的集合，R是数据关系的集合）。数据的逻辑结构包括哪四种类型。（线性结构、树形结构、图形结构、集合类型）。从存储结构的概念上讲，顺序表是线性表的（顺序存储结构）,链表是（链式存储结构）。2. 算法的五个重要特性有哪些。（有穷性、确定性、可行性、输入、输出）。抽象数据类型是指一个（数学模型）以及定义在该模型上的（一组操作）。3. 在含有n个结点的顺序存储的线性表中，在任意一个结点前插入一个结点所需要移动结点的

18、平均次数为（n/2）。在含有n个结点的顺序存储的线性表中，任意删除一个结点所需要移动结点的平均次数为（n-1/2）。对一个线性表分别进行遍历和逆置运算，其最好的时间复杂度量级均为（0（n）。4. 线性结构中的一个结点代表一个（数据元素）。若线性表中最常用的操作是取第i个元素和查找该元素的前驱，则采用的存储方式最能节省时间的是（顺序表）。若最常用的操作是插入和删除第i个元素，则采用的存储方式最能节省时间的是（单链表）。5. 在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除操作过程不同，需要修改（头指针）。在单链表中设置头结点的作用是（便于操作），无论链表是否为空。使（头指针）均

19、不为空。对于双向链表，在两个结点之间插入一个新结点需修改的指针共有（4个），单链表为（2个）。6. 如果以链栈为存储结构，则出栈操作时（必须判别栈空），与顺序栈相比，链栈有一个明显的优势是（不易出现栈满）。7. 循环队列采用数组data1.n来存储元素的值，并用front和rear分别作为其头尾指针。为区分队列的满和空，约定：队中能够存放的元素个数最大为n-l，也即至少有一个元素空间不用，则在任意时刻，至少可以知道一个空的元素的下标是（front）;入队时，可用语句（rear=rear+1%n）求出新元素在数组data中的下标。&已知栈的输入序列为1,2,3.，n,输出序列为a1,a2

20、,，an,a2=n的输出序列共有（n-1）种输出序列。9. 稀疏矩阵一般的压缩存储方法有两种，它们是用（哈希表、三元组和十字链表）。对矩阵压缩存储是为了（节省空间）。10. 将下三角矩阵Al.8,1.8的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A7,5的地址为（1100）。11. 已知数组A1.10,1.10为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A5,6对应的地址为（1095）。12.两个串相等的充要条件是，两个串的（长度）相等，且其所对应各个位置的（字符）也相等。13.取出广义

21、表A=（x,（a,b,c,d）中原子C的函数是（head（tail（tail（head（tail（head（A）。14.在有n个结点的二又链表中，值为非空的链域的个数为（n-1）。在有n个叶子结点的哈夫曼树中，总结点数是（2n-1）。在树形结构中，根结点数只有（1个），其余每个结点有且仅有一个元素（前驱）结点。15.一棵二叉树L的高度为h，所有结点的度或为0,或为2,则这棵二叉树最少的结点数为（2h-1）。已知二叉树有50个叶子结点，则该二叉树的总结点数至少是（99）。将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1,则编号为49的结点的左孩

22、子编号为（98）。有64个结点的完全二叉树的深度为（7）。16拓扑排序只能用于（有向无环图）。连通图是指图中任意两个顶点之间（都连通的无向图）。一个有n个顶点的无向连通图，它所包含的连通分量个数最多为（1）个。任何一个无向连通图的最小生成树（有一棵或多棵）。若含有n个顶点的图形成一个环，则它有（n）棵生成树。17. 求图的最小生成树有两种算法，（prim（普里姆）算法适合于求稠密图的最小生成树，（kruskal（克鲁斯卡尔）算法适合于求稀疏图的最小生成树。设图G用邻接表存储，则拓扑排序的时间复杂度为（0（n+e）。18. 在一棵三叉树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点

23、数为2个，则度为0的结点数为（6）。19.中序表达式A*（B+C）/（D-E+F）的后序表达式是（ABC+*DE-F+/）。20.有向图G用邻接矩阵A存储，则顶点i的入度等于A中（第i列1的元素之和）。具有10个顶点的无向图，边的总数最多为（45）个，具有n个顶点的强连通有向图G边的总数至少有（n）条。21 .从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（插入排序）。对于关键字序列（12,13,11,18,60,15,7,18,25,100），用筛选法建堆，则开始结点的键值必须为（60）。22 .在有序表Al.20中，采用二分

24、查找算法查找元素值等于A12的元素，所比较过的元素的下标依次为（10,15,12）,查找元素值等于5的元素，所比较过的元素个数为（5）个。分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间的是（插入排序）算法，最费时问的是（快速排序）算法。直接选择排序算法所执行的元素交换次数最多为（n-1）次，最好情况下所作的交换元素的次数为（0）次。在堆排序，希尔排序，快速排序，归并排序算法中，占用辅助空间最多的是（归并排序）。二分查找法要求查找表中各元素的关键字的值得排列必须是（递增或递减或有序）。23. 若一个待散列存储的线性表长度为n,用于散列的散列表长度

25、为m,则m应（小于等于）n,装填因子公式为（n/m）。散列表的平均查找长度（与处理冲突方法有关而与表的长度有关）。24. 在平衡二叉树上删除一个结点后可以通过旋转使其平衡，最坏情况下需旋转（O（log2n）次。25. 贪心算法的基本思想是，逐步构造最优解，每步都按照一定的标准，称为（贪心）准则，做出决策。0/1背包问题的三种贪心准则中，相对较优的是（价值密度）贪心准则。分治法与（递归）技术紧密结合。与分治法不同的是，动态规划是（自底向上或自下而上）、逐级求解子问题。分枝定界的搜索策略与（广度优先）类似，而回溯方法则采用（深度优先）搜索策略。26. 对于单链表、单循环链表和双向链表，若仅仅知道一

26、个指向链表中某结点的指针p，能否将p所指的结点的数据元素与它的直接前趋（假设存在）交换？若不可以，说明理由；若可以，写出主要算法。（1）单链表不能，单循环链表和双向链表可以。（2）单循环链表q=p;while（q>next!=p）q=q>next;temp=p>data;p>data=q>data;q>data=temp;（3）双向链表：q=p>prior;temp=q>data;q>data=p>data;p>data=temp;27. 设有三对角矩阵a1.n,1.n把非零元素按列存储在向量b1.3*n-2中，使得bk=ai,

27、j。求：用i,j表示k的下标变换公式（k=2*（j-1）+i）用k表示i,j的下标变换公式（j=（kDIV3）+1i=k-2*（j-1）28. 内存中一片连续空间（不妨设地址从1到m）,提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任意一个栈，仅当这部分全满时才发生上溢。（为了尽量利用空间，减少溢出的可能，可采用栈顶相向，栈底分设两端的存储方式，这样，对任何一个栈，仅当整个空间全满时才会发生上溢。）29. 有一n个结点的树，其中所有分支结点的度均为k，求该树中叶子结点的个数。设no为叶子结点数，nk为度为k的结点数，n为结点总数（依题意：n=n°+n（1）n=knk+1（

28、2）综合（1）和得：no=n-（n-1）/k30. 设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序列，其中n>>k,最好采用什么排序方法？为什么？如有这样一个序列：59,11,26,34,17,91,25，得到的部分序列是11,17,25，对于该例使用所选择的方法实现时，共执行多少次比较？（1）采用堆排序最合适，因为当部分序列较小时，堆排序的时间复杂度近似为O（n）。（2）初始建堆：比较8次输出11,第一次调整：比较4次输出17第二次调整：比较2次输出25,总共比较14次。31. 设二叉排序树中关键字由1至1000的整数组成，现要查找关键字为363的结点，下述关

29、键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。（1）51,250,501,390,320,340,382,363;（2）24,877,125,342,501,623,421,363;（1）是；不是。因为查询序列是：查421时，其623左、右两个区间都不存在，查找失败。）32. 在执行某个排序算法过程中，出现了排序关键字朝着最终排序序列相反方向的移动，从而认为该算法是不稳定的，这种说法对么？为什么？（不正确。算法的稳定性是考察最终排行的位置交换，与中间过程无关。如：对于整数序列（18,36,25）。按基数排序的LSD方法，第一趟排序后（25，36，18），第二趟排序后得到（18,25

30、，36），18虽向相反方向移动，但不影响最终位置。）33. 将算术表达式（a+b）+c*（d+e）+f）*（g+h）转化为二叉树（二叉链表结构）（略）34. 在线性结构中，开始结点没有（前驱）结点，最后一个元素没有（后继）结点。35. 线性表的逻辑结构是（线性结构），其所含结点的个数称为线性表的（长度）。36队列的特性是（先入先出或后入后出），栈的特性是（后入先出或先入后出）。37.数组Al.10,1.10的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续的内存单元中，则元素A5,6的地址为（1270）。38 .若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树

31、的总结点数是（69）。39 .树t的存储结构为二叉链表bt，树t中的一个叶子结点在bt中满足条件（bt->lchild<>nulI&&bt->rchild<>nuII;40.求图的最小生成树有两种算法，（prim（普里姆）算法适合于求稠密图的最小生成树。41.在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的（长度）有关，而且与每一块中的元素（长度）有关。42. 分枝定界的搜索策略与（广度优先）类似，而回溯方法则采用（深度优先）搜索策略。43. 0/1背包问题的三种贪婪准则中，相对较优的是（价值密度）贪婪准则。三、应用题

32、1. 有一个二叉树按层次顺序存放在一维数组中，如下图所示：试求：（1）该树的后序遍历序列。（C,E,B,D,A）（2）画出该树的后序线索树。（略）1234567891011ACBED2. 按顺序输入下列顶点对：（1,2）、（1,6）、（2,6）、（1,4）、（6,4）、（1,3）、（3,4）、（6,5）、（4,5）、（1,5）、（3,5）,（1）画出相应的邻接表。（2）写出在邻接表上，从顶点3开始（表下标从0开始）的DFS序列和DFS生成树。（1）邻接表VIf3IT1|f0|A(2)DFS序列2-0-1-5-3-43. 设一哈希表长为13，采用线性探测法解决冲突，哈希函数H(key)=key%

33、13,(1) 画出在空表中依次插入关键字25，20，36，15，41，52，29，72，67后的哈希表。(2) 求在等概率情况下，查找成功和查找不成功的平均查找长度。(1)100101102103104105106107108109110111112521541296720723625(2)平均查找长度查找成功的平均查找长度=(5*1+3*2+1*4)/9=1.6查找不成功的平均查找长度=(2+1+5+4+3+2+1+3+2+1+2+1+3)/13=30/134. 对下面的关键字集(30，15，21,40，25，26，36，37)，若查找表的装填因子为0.8，采用线性探测再散列解决冲突：(1)

34、设计哈希函数；(2)画出哈希表；(1)表长：m=n/a=8/0.8=10哈希函数：H(key)=key%7(2)哈希表01234567892115303625402637建立一棵平衡二叉排序树的过程，并写出调整5.写出对关键字序列503,087,512,061,908,124,897,275,653,426平衡时的旋转类型。RL>”.087897061124、512908、503、087512061124908-、897"6.7.8.唇087897061124512908275、653426已知一棵二叉树的先序序列和中序序列分别为：(略)假设通信电文使用的字符集为a,b,c,d

35、,e,f,g和010。(1) 画出此哈夫曼树(略)(2) 若这些字符在电文中出现的频度分别为路径长度WPL=2.53已知有一个10个顶点的连通图，顶点编号为(3,9)，(3，10)，(5,7)，(6,7)，(7，成树。(略)对下面的关键字集35,15,21,99,25,26,36,37,01,18写出快速排序的每趟结果和最终结果。(略)3y-*ay2A/-的操作步骤。(可用X代表扫描改字符串过RR50308/275061124426653897/512908、abdgicefhj及bgidaecfjh，画出该的二叉树的后序线索二叉树。字符的哈夫曼编码依次为：0110，10，110，111，00

36、，01113、35、13、15、20、5、9，求哈夫曼树的带权路径长度。(带权至8)，(8，9)，试求：画出该连通图及以顶点为根的深度优先生10，其边的关系集合表示为(1,2)(1,3)，(1，8)，(2,4)，9.10有字符串次序为3*-y-a/yA2，利用栈，给出将次序改为程中顺序取一个字符进栈的操作，用为BCA的操作步骤为XXSXSS。(略)11.设有一个由正整数组成的无序单链表，阅读下面的算法，指出该算法的功能，并在“”后面加上必要的注释。voidF1(Linklist&L)S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变p=Lfnext;pre=p;/pre

37、为最小结点指针while(p)if(pfdata<prefdata;pre=p;p=pfnext;/(1)/whileprintf(prefdata);/(2)if(prefnext&&prefdata%2!=0)/(3)temp=prefdata;prefdata=prefnextfdata;prefnextfdata=temp;/if/F1算法功能：找出最小值结点，且打印该数值。若该数值是奇数且有后继，则与后继结点的数值交换。(1)查找最小值结点；(2) 输出最小值结点；(3) 若该数值是奇数且有后继，则与后继结点的数值交换。12. 已知二叉树的存储结构为二叉链表，L

38、inkList和BiTree为已定义的指针类型，ListNode为已定义的结点类型,阅读下面算法并回答：LinkListL=Null;p;voidF2(BiTreeT)if(T)F2(Tflchild);if(!Tflchild)&&(!Tfchild)p=(ListNode*)malloc(sizeof(ListNode);pfdata=Tfdata;pfnext=L;L=p;/ifF2(Tfrchild);/if/F2(1) 说明该算法的功能；(2) 对于一棵有8个结点的完全二叉数(假设结点顺序为A、BC、DE、F、GH,画出执行上述算法后建立的结构。(1)按中序遍历二叉树

39、，逆序建立以叶子结点为链表结点、以L为头指针的无头结点的单链表。(2)(略)四、算法分析与设计题1设有一个由正整数组成的无序单链表，阅读下面的算法，指出该算法的功能，并在“/”后面加上必要的注释。voidF1(Linklist&L)p=Lfnext;pre=p;/pre为最小结点指针while(p)if(pfdata<prefdata;pre=p;p=pfnext;/(1)查找最小值结点/whileprintf(prefdata);/(2)输出最小值结点if(prefnext&&prefdata%2=0)/(3)删除其后继结点p=prefnext,prefnext

40、=pfnext;free(p);/if/F1算法功能：找出最小值结点，打印该数值。若该值是偶数且有后继，则将其后继结点删除。2. 设有n个大小不等的数据组(n个数据组中数据的总数为m),顺序存放在空间区D内，每个数据占一个存储单元。数据组的首地址由数组S给出，阅读下面的算法，指出该算法的功能，并在“/”后面加上必要的注释。voidF1(sqlist&L,inti,ElemTypex)if(i>=1&&i<=L.length)/(1)插入到D区for(j=0,p=L.elem0;j<=m;j+)p+;/(2)求D区空闲空间首地址if(i=L.length

41、)*p=x;(3)插入到第n个数组elsefor(q=L.elemi;p>=q;-p)*(p+1)=*p;*p=x;/插入xfor(q=&L.elemi,p=&L.elemLength-1;p>=q;q+)(*q)+;/elsem+;/if/F1算法功能：将数据x插入到D区，插入后D和S关系不变。3设有一个正整数序列组成的非递减有序单链表，阅读下面的算法，指出该算法的功能，并在“/后面加上必要的注释。voidF1(LinklistL;int,x)p=Ltnext;q=p;/p为工作指针pre=L;Ltnext=NULL;./q指最小元素while(P&&am

42、p;Ptdata<x)(1)比x小的数递减r=pTnext;ptnext=Ltnext;Ltnext=p;p=r;/(2)置逆/whileqtnext=p;pre=q;/(3)重新链接/F1算法功能：在单链表中将比正整数x小的数按递减次序排列。4. 假设一个仅包含二元运算符的算术表达式以二叉链表形式存储在二叉树T中，阅读下面的算法，指出该算法的功能，并在“”后面加上必要的注释。intF1(BiTrecT)if(!T)return0;if(!Ttlchild&&!Ttrchild)/(1)判断是否为叶子结点return(Ttdata);Lv=F1(Ttlchild);Rv=

43、F1(Ttrchild);switch(Ttdata)/(2)运算case'+':V=Lv+Rv;break;case'-':V=Lv-Rv;break;case'*':V=Lv*Rv;break;case'/':V=lv/Rv;break;/switchreturnV;/(3)返回结果/F1算法功能：后序遍历二叉树，求算术表达式的值。5. 在有向图G中，如果r到G的每个结点都有路径可达，则称结点r为G的根结点，下面算法的功能是判断有向图G是否有根，若有，则打印出所有根结点的值。请填空补全算法，并在“/”后面给以注释。voidF2

44、(ALGraphG)/利用深度优先搜索，判断有向图G是否有根结点。intvisitedmaxsige,count;/count为记录结构的顶点数。for(v=0;v<G.vexnum;v+)for(v=0;v<G.vexnum;v+)(1)_;初始化顶点数组count=O;DFS(G,v);if(count=(2)_)判断是否为根printf(G.verv.data);/F2voidDFS(ALGraphG,intv)/从第v个顶点出发递归地深度优先遍历图Gvisitedv=1;count+;for(p=G.verticesv.firstarc;p;p=pnextarc)w=pta

45、djvex;if(!visitedw)(3)_;/深度优先搜索/DFS(1)visitedv=0;(2)G.vexnum(3)DFS(G,w);6下面算法的功能是实现单链表中的简单选择排序，其中L为链表的头结点指针，请填空补全算法，并在“/”后面给以注释。voidF2(LinkList&L)/用单链表实现简单选择排序p=L>next;/初始化，p为工作指针while(p)min=p;(1)_;/q为插入指针，min为当前最小指针while(2)/一趟选择排序if(q>data<min>data)min=p;q=q>next;/while(q)if(3)/_

46、交换temp=p>data;p>data=min>data;min>data=temp;/ifp=p>next;/while(p)/F2(1)q=p>next;(2)q或q!=null(3)min7设计算法DeleteX的功能是：删除单链表L中值为x的结点的直接前趋结点。(设L是带头结点的单链表的头指针，并为已知的LinkList类型voidDeleteX(LinkList&L)/删除单链表中的直接前驱结点p=L>next;/初始化，p为工作指针while(p&&p>next>data!=x)/q为前驱结点指针q=p

47、;p=p>next;/whileif(p)/删除q>next=p>next;free(p);/if/DeleteX8 Internet的域名系统是一个典型的层次结构，可用树形结构表示。每一个域名服务器提供的区域信息恰好是以该结点为根的子树中的全部的IP地址。设计算法以孩子-兄弟链表作为树的存储结构，实现搜索所有www域名的IP地址。voidOutpath(CSTreeT,Stack&S)/搜索IP地址while(T)Push(S,T>data)if(!T>firstchild&&T>data=”www)visitstack(S);/输

48、出一条路径elseOutpath(T>firstchild，&S)/递归遍历左子树Pop(S,e);T=T>nextsibiling;/遍历右子树/while/Outpath9 设计算法实现以逆邻接表为存储结构的有向图的拓扑排序(要求给出逆邻接表的存储结构定义)。(1) 存储结构定义顶点结构表结点结构(2) 算法设计vexdatafirstinadjvexinfofirstarcinttoposort(ALGraphG,inttpv)/以逆邻接表为存储结构的有向图的拓扑排序top=0;for(i=0;i<G.vexnum;i+)for(p=G.adjlisti.fir

49、stedge;p;pfindoutdegree(G,outdegree);/对各顶点求出度tnext)outdegreeptadjvex+;InitStack(&S);/for(i=0;i<G.Vexnum;i+)if(outdegreei=0)Push(&S,i);/初始化栈出度为零的顶点入栈while(!Stack(S)Pop(&S,i);printf(G.adjlisti.vextex);tpvtop+=i;for(p=G.adjlisti.firstedge;p;ptnext)j=ptadjvex;outdegreej-;if(!outdegreej)Pu

50、sh(&S,j);/出度为零的顶点入栈/for/whileif(top<G.vexnum)return0;/无环else/输出顶点拓扑排序序列for(i=0;j=top-1;i<G.vexnum/2;i+,j-)/temp=tpvi;tpvi=tpvj;tpvj=temp;置逆输出/forreturn1;/else/toposort10.已知深度为h的二叉树采用顺序存储结构存放在数组B1.2h-1中，设计一个递归算法,链表结构。voidCreateTree(intB2h,intj,BiTreet)/创建t树的二叉链表结构，j为数组下标，初值为1t=(BiTree)malloc(sizeof(BiTNode);t>data=Bj;/创建根结点if(2*j>2h)t>Lchild=null;/无左子树else/递归创建左子树t>Lchild=CreateTree(B,2*j,t>Lchild);if(2*j+1>2h)t>Rchild=null;/无右子树else/递归创建右子树t>Rchild=CreateTree(B,2*j+1,t>Rchild);/CreateTree11假设哈希函数为