资源描述
中国石油大学（北京）远程教育学院 期 末 复习题一、选择题（本大题共15小题，每小题2分，共30分）1. 以下与数据的存储结构无关的术语是（ ）A、循环队列 B、链表C、哈希表 D、栈2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）A、110 B、108C、100 D、1203. 假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（ ）A、head= =NULL B、headnext= =NULL C、headnext= =head D、head!=NULL4. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（ ） A、2，4，3，1，5，6B、3，2，4，1，6，5C、4，3，2，1，5，6D、2，3，5，1，6，45. 下列关键字序列中，构成小根堆的是（ ）A、12，21，49，33，81，56，69，41 B、81，69，56，49，41，33，21，12 C、81，49，69，41，21，56，12，33 D、12，21，49，33，81，41，56，696. 下列数据结构中，不属于二叉树的是（ ）A、B树 B、AVL树 C、二叉排序树 D、哈夫曼树7. 用顺序存储的方法来存储一棵二叉树，存放在一维数组A1.N中，若结点Ai有右孩子，则其右孩子是（ ）。A、A2i B、A2i-1 C、A2i+1 D、Ai/28. 设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子数为（ ）A、 5 B、 6 C、7 D、 89. 有数据53，30，37，12，45，24，96，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下面哪个序列输入（ ）A、45，24，53，12，37，96，30B、37，24，12，30，53，45，96C、12，24，30，37，45，53，96D、30，24，12，37，45，96，5310. 对下面有向图给出了四种可能的拓扑序列，其中错误的是（ ）A、1，5，2，6，3，4B、1，5，6，2，3，4C、5，1，6，3，4，2 D、5，1，2，6，4，311. m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于( ) A、 m/2+1 B、m/2-1 C、m/2 D、m12. 散列文件也称为( ) A、顺序文件 B 、索引文件C、直接存取文件 D、间接存取文件13. 数据结构是（ ）A、一种数据类型B、数据的存储结构C、一组性质相同的数据元素的集合D、相互之间存在一种或多种特定关系的数据元素的集合14. 从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ ）A、线性结构B、树形结构C、线性结构和树型结构 D、线性结构和图状结构15. 设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用pllink和prlink表示，则同样表示p指针所指向结点的表达式是（ ）A、pllink B、prlinkC、pllinkllink D、pllinkrlink16. 若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈( i =1,2)栈顶，栈1的底在v1，栈2的底在Vm，则栈满的条件是（ ）A、 |top2-top1|=0 B、 top1+1=top2 C、 top1+top2=m D、 top1=top217. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（ ）A、10 B、11C、12D、不确定的18. 树的先根序列等同于与该树对应的二叉树的（ ）A、先序序列B、中序序列C、后序序列 D、层序序列19. 下面关于哈希(Hash，杂凑)查找的说法正确的是( )A、哈希函数构造的越复杂越好，因为这样随机性好，冲突小B、除留余数法是所有哈希函数中最好的 C、不存在特别好与坏的哈希函数，要视情况而定D、若需在哈希表中删去一个元素，解决冲突都只要简单的将该元素删去即可20. 下列序列中，（ ）是执行第一趟快速排序后所得的序列。 A、 68，11，18，69 23，93，73 B、 68，11，69，23 18，93，73 C、 93，73 68，11，69，23，18 D、 68，11，69，23，18 93，7321. 下列关键字序列中，构成小根堆的是( )A、 (84，46，62，41，28，58，15，37) B、 (84，62，58，46，41，37，28，15)C、 (15，28，46，37，84，41，58，62) D、 (15，28，46，37，84，58，62，41)22. ISAM文件和VASM文件属于( ) A、索引非顺序文件 B、顺序文件C、索引顺序文件 D、散列文件23. 下面程序段的时间复杂度为（ ）for (i=0; im; i+)for (j=0; jnext=s-next；s-next=p； B、s-next=p；q-next=s-next；C、p-next=s-next；s-next=q； D、s-next=q；p-next=s-next；25. 为便于判别有向图中是否存在回路，可借助于（ ）A、广度优先搜索算法 B、最小生成树算法 C、最短路径算法 D、拓扑排序算法26. 若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ ）A、SXSSXXXX B、SXXSXSSXC、SXSXXSSX D、SSSXXSXX27. 设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是( )A、2 B、3 C、5 D、628. 假设以数组Am存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位 置为（ ）。A、(rear-length+m+1)%m B、(rear-length+m)%m C、(rear-length+m-1)%m D、(rear-length)%m29. 在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（ ）。A、s-next=rear;rear=s; B、front=front-next;C、s-next=front;front=s; D、rear-next=s;rear=s;30. 对于哈希函数H(key)=key%13,被称为同义词的关键字是（ ）A、35和41 B、 23和39 C、15和44 D、25和5131. 采用二叉链表存储的n个结点的二叉树，共有空指针（ ）个。A、n+1 B、n C、n-1 D、2n-132. 连通网的最小生成树是其所有生成树中（ ）A、顶点集最小的生成树 B、边集最小的生成树C、顶点权值之和最小的生成树 D、边的权值之和最小的生成树33. 对记录序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为（ ）A、123，145，298，314，486，508 B、508，314，123，145，486，298C、486，314，123，145，508，298 D、298，123，508，486，145，31434. 任何一个无向连通图的最小生成树( )。A、一定有多棵 B、可能不存在 C、一棵或多棵 D、只有一棵35. 无向图的邻接矩阵是一个( )A、对角矩阵 B、上三角矩阵 C、对称矩阵 D、零矩阵36. 设无向图G-=(V,E)和G=(V,E),如G为G的生成树，则下列说法中不正确的是( )。A、G为G的无环子图 B、G为G 连通分量C、G为G极小连通子图且V=V D、G为G的子图37. 以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ ）A、 v1，v2，v3，v4，v5，v6，v7 B、 v1，v2，v5，v4，v3，v7，v6C、 v1，v2，v3，v4，v7，v5，v6 D、 v1，v2，v5，v6，v7，v3，v438. 下面几个符号串编码集合中，不是前缀编码的是（ ）A、0,10,110,1111 B、0,1,00,11C、00,010,0110,1000 D、b,c,aa,ac,aba,abb,abc39. 希尔排序的增量序列必须是（ ）。A、 递增的 B、递减的 C、随机的 D、非递减的40. 采用起泡排序法对n个关键字进行升序排序，若要使排序过程中比较关键字的次数最多，则初始时的序列应满足条件（ ）A、关键字完全无序 B、关键字基本有序C、关键字从小到大排列 D、关键字从大到小排列41. 在下列内部排序中( )是不稳定的。A、希尔排序 B、起泡排序 C、直接插入排序 D、归并排序42. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。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)43. 在查找过程中，冲突指的是（ ）。A、两个元素具有相同序号 B、两个元素的键值不同C、不同键值对应相同的存储地址 D、两个元素的键值相同44. 对有14个元素的有序表A1.14作二分查找，查找元素A4时的被比较元素依次为（ ）。A、A1，A2，A3，A4 B、A1，A14，A7，A4 C、A7，A5，A3，A4 D、A7，A3，A5，A445. 以v1为起始结点对下图进行广度度优先遍历，正确的遍历序列是（ ）A、 v1，v2，v3，v4，v5，v6，v7B、v1，v2，v5，v6，v7，v3，v4C、 v1，v2，v5，v6，v7，v3，v4D、 v1，v4，v5，v7，v6，v2，v3二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分)1. 数据的物理结构包括 的存储和 的存储。2. 若一个算法中的语句频度之和为T(n)=1921n+4nlogn,则算法的时间复杂度为 。 3. 下面程序段的时间复杂度是 。 i=1； while (i=n) i=i*3；4. 循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是 。5. 在单链表中设置头结点的作用是 _。6. 线性表L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_ 。7. 已知一无向图G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是 遍历方法。8. 如果排序过程不改变 之间的相对次序，则称该排序方法是稳定的。9. 从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需 一个位置。 10. 当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的 。11. 若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数即为顶点vi的 。12. 一棵含999个结点的完全二叉树的深度为 。13. 假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为 。14. .如图所示的有向无环图可以排出 种不同的拓扑序列。15. 从空树起，依次插入关键字1l，27，35，48，52，66和73构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为 。16. 带头结点的双循环链表L中只有一个元素结点的条件是 。 17. 求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中 的数目正相关。18. 已知一棵完全二叉树中共有768结点，则该树中共有 个叶子结点。19. 实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需要 存放被访问的结点以实现遍历。20. Prim（普里姆）算法适用于求 的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求 的网的最小生成树。21. 对长度为20的有序表进行二分查找的判定树的高度为 。22. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为 ，有_ 个叶子结点。23. 高度为h的完全二叉树中最少有 个结点，最多有 个结点。24. 设连通图G中有n个顶点e条边，则对应的最小生成树上有 条边。25. 构造n个结点的强连通图，至少有 条弧。26. 表达式求值是 应用的一个典型例子。27. 设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是 。28. 快速排序算法在最差的情况下其时间复杂度是 。29. 对序列55，46，13，05，94，17，42进行基数排序，第一趟排序后的结果是 。三、应用题（本大题共5小题，每小题6分，共30分）1. 已知二叉树的先序遍历序列ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。2. 如图请给出邻接表、邻接矩阵及逆邻接表。V1V3V2V43. 由字符集s，t，a，e，I及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。4. 请画出下图所示的树所对应的二叉树，并写出对应二叉树的先序遍历和中序遍历。123456785. 设散列表为HT13, 散列函数为 H (key) = key %13。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。6. 已知带权图G如图所示，画出图G的一棵最小生成树。7. 假设用于通信的电文由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，请为这8个字母设计哈夫曼编码。8. 试用权集合12,4,5,6,1,2构造哈夫曼树，并计算哈夫曼树的带权路径长度。9. 画出与如图所示森林对应的二叉树。10. 已知一个散列表如下图所示：3520334859 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函数为h(key)=key%13, 处理冲突的方法为双重散列法，探查序列为： hi=(h(key)+*h1(key)%m =0,1,，m-1其中： h1(key)=key%11+1回答下列问题：（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？（2）该散列表在等概率查找时查找成功的平均查找长度为多少？11. 请画出与下列二叉树对应的森林。12. 对于给定结点的关键字集合K=5，7，3，1，9，6，4，8，2，10，（1）试构造一棵二叉排序树；（2）求等概率情况下的平均查找长度ASL。13. 给出下图对应的邻接矩阵，并给出A，B，C三个顶点的出度与入度 14. 已知图5.32如下所示，求从顶点a到其余各顶点的最短路径。（给出求解过程）543223356abdfce15. 阅读下列算法，并回答问题：（1）假设串由合法的英文字母和空格组成，并以0作结束符。设串s=”Iamastudent”(表示空格符)，写出f30（s）的返回值；（2）简述算法f30的功能。int f30 (char*s)int i, n, inword;n=inword=0;for (i=0;si!=0;i+)if (si!=& inword=0)inword=1;n+; else if (si=& inword=1) inword=0;return n;16. 阅读下列函数,并回答问题：（1）假设队列q中的元素为(a,b,c,d,e),其中“a”为队头元素。写出执行函数调用Conv(&q)后的队列q；（2）简述算法Conv的功能。void Conv (Queue *Q) Stack S; InitStack(&S); while (!QueueEmpty(Q) Push(&S, DeQueue(Q); while (! StackEmpty(&S) nQueue(Q,Pop(&S);17. 阅读下列函数,并回答问题：已知整形数组L1.8中的元素依次为（19，18，15，17，16，13，12，10），阅读下列函数，并写出执行函数调用sort(L, 8)时，对L进行的头两趟（pass分别为0和1）处理结果。 void sort (int R,int n) int pass = 0, k, exchange, x; do k=pass%2+1; exchange = 0; while (kRk+1) x = Rk; Rk = Rk+1; Rk+1 = x; exchange =1; K+=2; pass +;while (exchange = = 1| pass =1);keynext18. 已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m，散列函数为Hash(key)=key%m。链表的结点结构为： 。请在空缺处填入适当内容，使其成为一个完整算法。void f33 (LinkList L, LinkList H, int m)/由带头结点的单链表L生成散列表H，散列表生成之后原链表不再存在 int i,j; LinkList p,q; for (i=0;inext; while(p) q=p-next; j=p-key%m; (2) ; Hj=p; (3) ; free(L); 19. 下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。 void union (LinkList La, LinkList Lb)/本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中LinkList pre = La, q;LinkList pa = La - next;LinkList pb = Lb - next;free (Lb);while (pa & pb)if (pa - data data) pre = pa; pa = pa - next;else if (pa - data pb -data) (1) ;pre = pb;pb = pb - next; (2) ;elseq = pb; pb = pb - next; free (q);if (pb) (3) ;20. 阅读算法f30，并回答问题：下列算法为有向图拓扑排序,请在空缺处填入合适的内容，使其成为一个完整的算法。void f30 (hdnodes graph ,int n) int i,j,k,top; node_pointer ptr ; top=-1; for (i=0; in; i+) if (!graphi.count)graphi.count=top; top=i; for (i=0; ilink) k=ptr-vertex; graphk.count-; if( (3) ) graphk.count=top; top=k; 21. 阅读算法f31，并回答问题：下列算法功能为在数组a的前n(n=1)个元素中找出第k(1=k=n)小的值。这里假设数组a中各元素的值都不相同。请在空缺处填入合适的内容，使其成为一个完整的算法。#define MAXN 100int aMAXN,n,k;int f31(int a, int n, int k)int low, high, i, j, m, t; k-,;low=0 ;high=n-1; do i=low; j=high ; t=alow; do while (ij & taj) j-; if (ij) ai+=aj; while (i=ai) i+ if (ij) aj-=ai; while (ij);ai=t;if (1) ; if (iai+1,将二者交换;以后重复上述二趟过程,直至整个数组有序。请在空缺处填入合适的内容，使其成为一个完整的算法。void f33 (int an)int flag,i,t;do flag=0;for(i=1;iai+1) flag=1; t=ai+1; ai+1=ai; _ (1)_; for _ (2)_ if (aiai+1) flag=1;t=ai+1; ai+1=ai; ai=t; while ( (3) _ ); 四、算法设计题（本大题共2小题，每小题10分，共20分）1. 已知单链表的结点类型为Lnode，包含next和data成员。编写算法，实现带头结点单链表的逆置算法。2. 编写一个函数，要求借助一个栈把一个数组中的数据元素逆置。其中，栈类型为SeqStack，可以直接使用InitStack(SeqStack*)、Push(SeqStack*,ElemType)、Pop(SeqStack*,ElemType*)函数。3. 二叉树采用链接存储结构，结点类型为Btree，包括left、right和data三个成员，试设计一个算法计算一棵给定二叉树的度为2的结点的个数。4. 假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示：typedef char DataType;typedef struct node DataType data; struct node *lchild, *rchild; /左右孩子指针 struct node *parent; /指向双亲的指针 BinTNode;typedef BinTNode *BinTree;若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。(1)就后继的不同情况，简要叙述实现求后继操作的方法；(2)编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。5. 已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。6. 已知有n个顶点的有向图邻接表，编写一个函数求出该图中指定顶点的出度。已知边类型edgenode，包含next和adjvex（序号）成员。类型adjlist表示顶点数组类型，每个数组元素包含link和vex成员。7. 编写算法实现对给定的二叉树是否为二叉排序树的判别。设二叉树以二叉链表存储表示。（要求写出二叉链表的类型定义）中国石油大学（北京）远程教育学院 期 末 复习题一、选择题（本大题共15小题，每小题2分，共30分）123456789101112131415CBCDAACDBCBCDCD161718192021222324252627282930BAACDDCCADDBBDD313233343536373839404142434445ADBCCBDBBDACCDA二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分)30. 数据元素 、 数据之间关系 31. nlogn 32. 33. （ rear-front+m ）% m 34. 主要是使插入和删除等操作统一_35. （n-1）/2 36. 深度优先 37. 相同值关键字 38. 前移 39. 时间复杂度 40. 出度 41. 10 42. sxssxxssxssxxx 43. . 12 44. 4 45. L-next-next=L 46. 边 47. 384 48. 队列 49. 边稠密 、 边稀疏 50. 5 51. 8 、 64 52. 2h-1 、 2h-1 53. n-1 54. n 55. 栈 56. 3 57. O(n2) 58. （42,13,94,55,05,46,17） 三、应用题（本大题共5小题，每小题6分，共30分）23.答案：二叉树形态 24. 参考答案：（1）邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1) vertex firstedge next （2）逆邻接表：（3）25. 答案：原来的电文为：eatst26. 答案：12345678先序遍历为：12345687 中序遍历为：3486752127. 答案：使用散列函数 H(key) = key mod 13，有H(12) = 12, H(23) = 10,H(45) = 6,H(57) = 5,H(20) = 7,H(03) = 3,H(78) = 0,H(31) = 5,H(15) = 2,H(36) = 10.利用线性探查法造表： 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 (1) (1) (1) (1) (1) (1) (4) (1) (2) (1)搜索成功的平均搜索长度为ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 28. 答案：29. 答案：哈夫曼编码为：a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000注意：答案不唯一30. 答案：WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=6931. 答案：32. 答案：（）对关键字35、20、33和48进行查找的比较次数为、；（）平均查找长度33. 答案： 34. 答案：（1）构造二叉排序树 ： 74312596108（2）ASL=(1*1+2*2+3*4+4*3)/10=2.935. 答案: 邻接矩阵为： A B C D E F其中顶点A的入度为2，出度为1；其中顶点B的入度为2，出度为2；其中顶点C的入度为1，出度为3；36. 答案:终点最短路径求解过程b6 (a,b)5 (a,c,b)c3 (a,c)d6 (a,c,d)6 (a,c,d)e7 (a,c,e)7 (a,c,e)7 (a,c,e)f9 (a,c,d,f)9 (a,c,d,f)vjcbdefSa,ca,c,ba,c,da,c,ea,c,d,f37. 答案：(1) 4(2)算法功能：统计单词的个数。38. 答案：（1） e，d，c，b，a（2） 将队列里的值反转39. 答案：（1）第一趟（pass = 0）19 15 18 16 17 12 13 10（2）第二趟（pass = 1）19 15 16 18 12 17 10 1340. 答案：（1）NULL （2）p-next=Hj p=q41. 答案：（1）pre-next=pb （2）pre-next=pa （3）pre-next=pb42. 答案：(1）top=-1 （2）top=graphj.count （3）graphk.count=043. 答案：（1）(i=k) return; （2）i+1 （3）i-144. 答案： (1)ai=t (2)(i=2;inext) return ERROR; p=head-next; q=p-next; p-next =NULL; while(q) p=q; q=q-next; p-next=head-next; head-next=p; 9. 参考答案：void Inverse(ElemType arr,int n)SeqStack *s;int i;InitStack(&s);for(i=0;in;i+) /数组元素依次入栈Push(s,arri);for(i=0;ileft); num2=twochild1(b-right);if ( b-left!=NULL&b-right!=NULL) return (num1+num2+1); else return (num1+num2); 11. 参考答案：（1）分两种情况讨论当*px的右子树不为空时，则从*px的右孩子开始，沿其左孩子往下查找，直到找到一个没有左孩子的节点为止，则该结点为*px在中序序列中的后继；当*px的右孩子为空时，则沿*px的双亲指针链向上查找，直至找到其左子树中包含*px的最年轻祖先，则该祖先结点为*px在中序序列中的后继。（2）BinTree f34(BinTree px)BinTree q=px-rchild;if(q!=NULL)/沿左孩子往下查找px=q;while(px-lchild!=NULL)px=px-lchild;else/沿双亲指针链向上查找while(px!=NULL & px-rchild=q)q=px;px=px-parent;return px;/返回所找到的中序序列后继结点的指针 /或者无后继结点时返回空指针12. 参考答案： void AllSPdfs(AdjList g,vertype u,vertype v) /求有向图g中顶点u到顶点v的所有简单路径，初始调用形式：AllSPdfs(g,u,v)int top=0,s; s+top=u; visitedu=1; while (top0 | p) p=gstop.firstarc; /第一个邻接点。 while (p!=null & visitedp-adjvex=1) p=p-next; /下一个访问邻接点表。 if (p=null) top-; /退栈。 else i=p-adjvex; /取邻接点（编号）。 if (i=v) /找到从u到v的一条简单路径，输出。 for (k=1;knext; return degree;14. 参考答案：/二叉树的二叉链表表示typedef struct BINTREENODE ElemType data;struct BINTREENODE *lchild, rchild; BinNode,*BinTree /答对给2分int BsBtr(BinTree t, BinTree pre, int flag) /判别给定的二叉树是否为二叉排序树pre =NULL; flag=TRUE; if (t & flag) BSBtr(t-lchild, pre, flag); if (pre = = NULL) flag=TRUE；pre=t; else if(pre-key key) /比较t 与中序直接前驱pre的大小 flag=TRUE; pre=t; /pre与t有序 else flag=FALSE; /pre与t无序 /if BSBtr(t-rchild,pre,flag); /BSBtr 25
展开阅读全文