《数据结构》课程复习资料.doc.pdf

《《数据结构》课程复习资料.doc.pdf》由会员分享，可在线阅读，更多相关《《数据结构》课程复习资料.doc.pdf（36页珍藏版）》请在三一文库上搜索。

1、数据结构课程复习资料 一、填空题： 1.设需要对5个不同的记录关键字进行排序，则至少需要比较土次，至多需要比较10次。 2.设二叉排序树的高度为h,则在该树中查找关键字key最多需要比较丄次。 3.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有丄个，比较两次查找成功有结点 数有生个。 4.数据结构从逻辑上划分为三种基本类型线性结构、树型结构和图型结构。 5.在一个具有n个顶点的无向完全图中，包含有n(n-l)/2条边, 在一个具有n个顶点的有向完全图中，包含有 n(n-l)条边。 6.向一棵B.树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度增加1。 7?在

2、堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为0(log2n),整个堆排序过程的时间复杂度为 0(nlog2n)。 8.在快速排序、堆排序、归并排序中，归并排序是稳定的。 9.在有n个叶子结点的哈夫曼树屮，总结点数是旷1 10.棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定左右子 树空。 11.已知数组A 1 0 1 0 为对称矩阵，英中每个元素占5个单元。现将英下三角部分按行优先次序存储在 起始地址为1000的连续的内存单元中，则元素A 5, 6对应的地址是1225 o 12.在有n个结点的无向图中，其边数最多为n(n-l)/2。 13.取出广

3、义表A二(x, (a, b, c, d)中原子x的函数是head (A) o 14.对矩阵采用压缩存储是为了节省空间。 15.带头结点的双循环链表L为空表的条件是L-next二L-prior 或L-next二L。 16.设线性表中元素的类型是实型，其首地址为1024,则线性表屮第6个元素的存储位置是1044。 17.对于顺序存储的栈， 因为栈的空间是有限的， 在进行入栈 ( 插入) 运算时 , 可能发生栈的上溢， 在进 行出栈 (删 除)运算时 , 可能发生栈的下溢。 18?在双向链表中，每个结点有两个指针域，一个指向前驱结点, 另一个指向后继结点。 19.由一棵二叉树的前序序列和中序序列可唯

4、一确定这棵二叉树。 20.折半查找的存储结构仅限于顺序存储结构, 且是有序的。 21.对于一个顺序存储的线性表，在表头插入元素的时间复杂度为迪，在表尾插入元素的时间复朵度为0(1)。 22.在稀疏距阵所对应的三元组线形表中，每个三元组元素按行号为主序, 列号为辅序的次序排列。 23.中缀表达示3+X* (2. 4/5-6)所对应的后缀表达示为3 x 2.4 5/6 *+。 24.在一棵高度为h的3叉树中，最多含有(3 h-l)/2结点。 25?分析下面算法( 程序段 ) ，给出最大语句频度迫，该算法的时I可复杂度是0(n3)。 for (i=0;inext!=p) q二q-next; s= n

5、ew Node; s-data=e; qnext= s ; / 填空 snext= p ; / 填空 29.在一个单链表屮删除p所指结点的后继结点时，应执行以下操作： q= p-next; p-next=qnext; / 填空 delete q ; / 填空 30.两个串相等的充分必要条件是两个串的长度相等H对应位置的字符相同。 31 . 二维数组A10 20采用列序为主方式存储，每个元素占一个存储单元并且A0 0的存储地址是200, 则A6 12的地址是200 + (6 * 20 + 12)二326。 32.二维数组A10 20 5 10采用行序为主方式存储，每个元素占4个存储单元，并且A1

6、0 5的存储 地址 是1000,则A18 9的地址是1000 + (18-10) * 6 + (9 - 5) * 4 二1208。 33.求下列广义表操作的结果： (1)GetTa订GetHead(3, b), (c, d); (b) (2)GetTai 1 GetHeadGetTai 1 (a, b), (c, d) (d) 34.已知一个有向图的邻接矩阵表示，计算第i个结点的入丽另法是求矩阵第i列1F?零元素之和。 35.已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是将矩阵第i行全部置为零。 36.在利用快速排序方法对一组记录(54, 38, 96, 23, 15, 72,

7、 60, 45, 83)进行快速排序时 , 递归调 用而使用的栈 所能达到的最大深度为2,共需递归调用的次数为其中第二次递归调用是对(23, 38, 15)组记录进行快速排序。 37.在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取堆排序方法, 其次选取快速 排序方 法, 最后选取归并排序方法；若只从排序结果的稳定性考虑，则应选収归并排序方法; 若只从 平均情况下排 序最快考虑，则应选取快速排序方法; 若只从最坏情况下排序最快并II要节省内存考虑 , 则应选取堆排序方 法。 3 p-next二q; B. p-next二q; q-next=p; C.p-next=q-next;

8、p=q; D. q-next=p-next; p-next=q; 23.() 不是队列的基本运算。A A.在队列第i个元素Z后插入一个元素B.从队头删除一个元素 C.判断一个队列是否为空D.读取队头元素的值 24.若已知一个栈的入栈序列是1, 2, 3,，n,其输出序列为pl, p2, p3,，pn,若pl=n,则pi 为C A. i B. n=i C. n-i+1 D.不确定 25.栈的特点是 (B ),队列的特点是(A )o A.先进先ill B.先进后出 26.设有两个串p和q,求q在p中首次出现的位置的运算称作B A.连接B.模式兀配C.求子串D.求串长 27 . 二维数组A中，每个元

9、素Aij的长度为3个字节，行下标i从0到7,列下标j从0到9,从首地 址SA开始 连续存放在存储器内，该数组按列存放时，元素 A47的起始地址为B A. SA+141 B. SA+180 C. SA+222 D. SA+225 28.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历 的结点访问顺序是D A. bdgcefha B. gdbecfha C. bdgaechf D.gdbehfea 29.在一非空二叉树的中序遍历序列中，根结点的右边A A.只有右子树上的所有结点B.只有右子树上的部分结点 C.只有左子树上的部分结点D.只有左子

10、树上的所有结点 30.具有6 个顶点的无向图至少应有() 条边才能确保是一个连通图。A A. 5 B. 6 C. 7 D.8 31.二分查 找和二叉排序树的时间性能 B A.相同B.不相同 32.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为B A.O (n2) B.O(nlog2n) C.O(n) D.0(log2n) 33.在待排 序的元素序列基本有序的前提下，效率最高的排序方法是A A.插入排序B.选择排序C.快速排序D.归并排序 34.下述几 种排序方法中，要求内存量最大的是 D A.插入排序B.选择排序C.快速排序D.归并排序 35.设有两个串p和q,求q在p中首次

11、出现的位置的运算称作B A.连接B.模式匹配C.求子串D.求串长 36.二维数组A中，每个元索Aij的氏度为3个字节，行下标i从0到7,列下标j从0到9,从首地 址SA开始连续存放在存储器内，该数组按列存放时，元素A 47的起始地址为B A. SA+141 B.SA+180 C. SA+222 D. SA+225 37.某二叉树的前序遍历结点访问顺序是abdgcofh, I 1 序遍历的结点访问顺序是dgbaechf,则其后序遍历 的结点访问顺序是D A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 3 HL-next=p B. p-next=HL

12、; HL二p C. p-next=HL; p=HL D.HL=p; p-next=HL 46.对线性 表，在下列哪种情况下应当采用链表表示？B A.经常需要随机地存取元素B.经常需要进行插入和删除操作 C.表屮元素需要占据一片连续的存储空间D.表中元素的个数不变 47.个栈 的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是C A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 4 III厂next二p B. p-next=IIL; III尸p C. p-next=HL; p=HL D. I1L二p; p-next=HL 94.对线性 表，在下列哪种情况下应当采用

13、链表表示？ B A.经常需要随机地存取元素B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变 95.个栈的输入序列为1 2 3,贝IJ下列序列屮不可能是栈的输出序列的是C A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 96?每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是B A.冒泡排序B.简单选择排序C.希尔排序D.直接插入排序 97.采用开 放定址法处理散列表的冲突时，其平均查找长度 B A.低于链接法处理冲突B.高于链接法处理冲突 C.与链接法处理冲突相同D.高于二分查找 98.若需要利用形参直接访问实参时

14、，应将形参变量说明为() 参数。D A.值B.函数C.指针D.引用 99.在稀疏 矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的 A A.行号B.列号C.元素值D.非零元素个数 100.快速排 序在最坏情况下的时间复杂度为 D A. 0 (log2n) B. 0(nlog2n) C. 0(n) D. 0(n 2) 101.从二叉搜索树中查找一个元素时，其时间复杂度大致为C A. O(n) B. 0(1) C. 0(log 2n) D. 0(n 2 ) 102.设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的 时间复杂度为 D A. 0(l

15、og 2n) B. 0(1) C. 0(n 2) D. 0(n) 103.设一棵m叉树中度数为0的结点数为NO,度数为1的结点数为N1,度数为m的结点数为Nm, 则N0二B A. NI+N2+ . +Nm B. 1+2+22+3汕+ + (m-l)Nm C. 2+22+37+ . + (m-l)Nm D. 2N+3W+ + (m+l)Nm 104.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较 () 次。B A. 25 B. 10 C. 7 D. 1 105.设连通图G 中的边集E= (a, b), (a, e), (a, c), (b, e), (e, d), (d, f),

16、 (f, c),贝! 从顶点a 出发可以得到一种深度优先遍历的顶点序列为 B A. abedfc B. acfebd C. aebdfc D. aedfcb 106.拓扑排 序运算只能用于C A.带权有向图B.连通无向图C.有向无坏图D.无向图 107.在一个具有n个结点的有序单链表屮插入一个新结点并仍然保持有序的时间复杂度是B A. 0(1) B. 0(n) C. 0(n 2) D. O(nlogn) 三、计算与算法应用题： 1.已知一个图的顶点集V和边集E分别为： V二1,2, 3, 4, 5, 6, 7; E二(1,2)3, (1,3)5, (1,4)8, (2, 5)10, (2, 3

17、)6, (3,4)15, (3,5)12, (3, 6)9, (4,6)4, (4, 7)20, (5, 6)18, (6, 7)25; 按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。 2. 棵二叉树的先序、屮序和后序序列分别如下，其屮有一部分未显示出来。试求出空格处的内容，并画出该 二叉树。 先序序列：_B_F_TCEH_G 中序序列： D_KFIA_EJC_ 后序序列：_K_FBHJ_G_A 4.将关键字序列为54, 29, 37, 86, 71, 91, 8, 31, 44, 26进行归并排序，写出各趟详细过程。 3.画出下列树对应的二叉树, 并写出其先

18、根遍历序列 : 5.试列出如下图中全部可能的拓扑排序序列。 6.设某通信系统使用A, B , C, D, E, F, G, H八个字符，他们出现的概率w二5, 29, 7, 8, 14, 23, 3, 11,试构 造对应的哈夫曼树 ( 请按左子树根结点的权小于右子树树根结点的权的次序构造) 。 7.给定表(119, 14, 22, 1, 66, 21, 83, 27, 56, 13, 10)，请按表中元素的顺序构造一棵平衡二叉树, 并求其在等 概率情况下查找成功的平均长度。 8.已知一个有向图的顶点集V和边集G分别为： V=a, b, c, d, e, f, g, h) E=, , , , ,

19、 , , , , ; 假定该图采用邻接矩阵表示，则分别写出从顶点a出发进行深度优先搜索遍历和广度优先搜索遍历得 到的顶点序列。 9.设散列表的长度为13,散列函数为H (h) =k%13,给定的关键码序列为19, 14, 23, 01, 68, 20, 84, 27。试画出用线性探查法解决冲突时所构成的散列表。 0 1 2 3 4 5 6 7 8 9 10 11 12 10.对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。 (1)假设关键字集合为1, 2, 3,4, 5, 6, 7，试举出能达到上述结果的初始关键字序列; (2)对所举序列进行快速排序，写出排序过程。 11.

20、如图所示二叉树，回答下列问题。 (1J薦申序遐厉馬钊 12.画出在一个初始为空的AVL树中依次插入3, 1, 4, 6, 9, LNode *p=HL; while (p!二NULL) if (p-data= =x) n+; p二p-next; return n; 对于结点类型为LNode的单链表，以上算法的功能为: 2. int AA(LNode *HL , ElemType x) 19.己知关键字序列为 :03, 87, 12, 61, 9 LNode *p=HL; while (p!二NULL) if (p-data= =x) n+; p二p-next; return n; 对于结点类型

21、为LNode的单链表，以上算法的功能为： 3.假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 #include #include const int stackmaxsize = 30; typedef int elemtype; struct stack elemtype stack stackmaxsize; int top; ; #include “stack, h“ void main 【 stack a; initstack (a); int x; cin x; while (x! = -1) push (a, x ); cin x; while (!stack

22、ompty (a) cout void BinTree : unknown (Bi nTreeNode*t) BinTreeNode *p =t, *temp; if (p!二NULL) t emp = pf leftchild; p-leftchild = p-rightchild; p-rightchiId = temp; unknown (p leftch订d); undnown(prightchild); -1，请写出输出结果。 ) 算法处理后，单链表发生了什么变化？画出处理后的单链表 图示。 void Link :output() p二Head- next; while( p !=N

23、ULL) cout? ” n data=?p -data ; p=p_next; /output 7.读下述算法，说明本算法完成什么功能。 void Btree :inordern( bnode *p, int if ( p-1ch二二NULL inordern ( p-rch, n); / inordern 8. void AD(Lnode* Insert (HL, 50); Delete (IIL, 26); Delete(HL,55); 该算法的功能是： _ 0 5.阅读下列算法，说明该算法的作用。 void Sqstack:push(ElemType x ) if ( topMAX-l

24、 ) cout? v n 满！”； else top+; elemtop=x; / push I /类定义I ! const int MAX=20; ! I ! typedef char ElemType ; i ! i ! class Sqstack i i private: i i ElemType elem MAX; j | int top ; j public: j Sqstack () top=0 ; | j ElemType pop() ; | | void push(ElemType x): ! I / .; I struct Snode / 结点结I ! i ! 构! ! i

25、! char data; i ! i Snode *next ; i I ; I class Link /链 表 类| j private: | | Snode *Head; | public: | ! Link () Head NULL; ! void creat(); ! ! void output(): i ! / . ；I 6?有如下图所示单链表，经过output ( 假定调用该算法时以 IIL为表头指针的单链表中的内容为(15, 26, 48, 55),则调用返回后该单链表 中的内容为：_ o 9. void Al (adjuieitirix GA, int i, int n) co

26、utnext=NULL; while( p !=NULL) q二p-next ; p-next= Hoad - next; Head next二p; p=q; ()Head 二NULL; i creat (); reverse () ; output () ；i / reverse Void Bstree:Search( KeyType K) int flag = 0; BstNode *q=root, *p = NULL; while (q!=NULL) else if ( Kkey) p = q; q = q-lch; else p = q; q = q-rch; if (flag = 0

27、) cout? ， n 查找失败，无此结点！rT; else coutdata=item; LNode *p=HL; wh i1e ( p-next!=HL ) p=p-next; newptr-next=HL; p-next二newptr; 对于结点类型为LNode的单链表，以上算法的功能为： 14. void BB(List while (i int SeqList:Insert(Type else Last+; for(int j=last; ji;j) dataj= dataj-l; datai=x; retui n 1; 对于结点类型为SeqList的顺序表，以上算法的功能为： 四、

28、算法设计题： 1.编写攵制一棵二叉树的非递归算法。 状显示二叉树。 3.试用递归法编写输出从n个数中挑选k个进行排列所得序列的算法。 4.编写一个算法，交换单链表中p所指向的结点和其后续结点的两个结点，Head指向该链表的表头，P指向 链 表中的某一结点。 5.试写一递归算法，从大到小输出二叉排序树中所有的关键字值小于key的元素值。 2.假设二叉树中每个结点所含数据元素均为单字母, 以二叉链表为存储结构，试编写算法按如下图所示的树 C e a d b 6.己知带头结点的单链表是一个递增有序表，试写一算法，删除表中值大于min且小于max的结点 ( 若表中 有 这样的结点 ) ，同时释放被删除

29、结点的空间，这里min和max是两个给定的参数。 度为 h的二叉树以一维 数组BT(l:2h-l)作为其存储结构。请写一算法，求该二叉树小叶结点的个数。 8.编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找item带冋整个结 点的值并返回true,否则返回falseo bool Find (BtreeNode*BST, ElemType 4; (23, 38, 15) 37 . 堆排序、 快速排序、归并排序、归并排序、 快速排序、堆排序 38. f(n) 39.0(n) 40. 10 41.栈顶 42.3 43.逻辑结构 44. n/2 45.先进先出46.

30、 79 47.中序48. n-1 49. 快速排序 50. head-next=NULL 51. 10, 13, 27, 76, 65,97, 38 52.入度为零53.非线性结构54.p-next=p-nextnext 55. (resT-front+n)%n 56. (n-m+1) Xm 57. (b), j, (d) 58. 166 59. 队列 二、单项选择题 : 1.B 2. B 3. B 4.C 5. B 6.B 7. D 8. A 9. C 10. D 11.B 12. B 13. A 14. D 15. A 16. A 17. C l / 释放toBtPtr if (fromB

31、tPtr-Empty() /空二叉树 toBtPtr = NULL; / 空二叉树 p 1 Qp / 非空二叉树 LinkQueue * fromQ, toQ; / 队列 BinTreeNode *fromPtr, *toPtr, *fromRoot, *toRoot; fromRoot = fromBtPtr-GetRoot () ; / 取出fromBtPtr 的根 toRoot = new BinTreeNode (fromRoot-data); / 复制根结点fromQ. InQueue(fromRoot) ; toQ. TnQueue (toRoot) ; / 入队 while (!

32、fromQ. Empty() / fromQ 非空 fromQ. OutQueue (fromPtr) ; / 出队 toQ. OutQueue (toPtr) ; / 出队 if (fromPtr-leftChild ! 二NULL) / 左子树非空 toPtr-leftChiId Bi nTreeNode(fromPtrleftChi1d-data); / 复制fromPtr左孩牛 fromQ.TnQueue(fromPtr-leftChiId); toQ. TnQueue(toPtr-leftChiId); / 入队 if (fromPtr-rightChi1d != NULL) / 右

33、子树非空 toPtr-rightChild = new BinTreeNode(fromPtr-rightChild-data); / 复制 fromPtr左孩子 fromQ.TnQueue(fromPtr-rightChi1d); toQ. InQueue(toPtr-rightChiId); / 入队 toBtPtr = new BinaryTree (toRoot) ; / 生成toBtPtr 2.从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个 结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的 中序

34、遍历次序显示各结点。 具体算法实现如下： / 文件路径名 :examlalg. h ss ElemType void DisplayHelp(BinTreeNode *r, int level) new / 操作结果：按树状形式显示以i?为根的二叉树，level为层次数，可设根结点的层次数为1 if(r ! 二NULL) / 空树不显式，只显式非空树 DisplayHelp (r-right.Child, level + 1); / 显示右子树 cout ? endl; / 显示新行 for(int i = 0; i data; / 显示结点 DisplayHelp(r-leftChiId,

35、level + 1) ; / 显示左子树 template class ElemType void Display(const BinaryTreo / 树状显示以bt. GetRoot ()为根的二叉树 cout ? endl; / 换行 3.对于排列的解空间可构造一个虚拟的解空间树，比如n=5, k二3时的解空间树如下图所示，可采用对此树进 行先序遍历方式进行遍历，并用递归法进行递归输出从n个数屮挑选k个进行排列所得序列。 具体算法实现如下： / 文件路径名 :exam7alg. h template void Arrage(ElemType a,int k,int n, int outl

36、en二0) / 操作结果：冋溯法输出排列序列，a0k-l为k个数的排列序列outlen为当前所求排列 / 序列的长度，其中outlen二k时的排列序列为所求；n为list数组长度 if (k = n) return; / 此时无排列 int i; / 临时变量 if (outlen = k + 1) / 得到一个排列 for (i = 0; i next; if(q!二NULL) if(p=Head) IIead=Head-next; s=Head-next; Hoad-noxt=p; p-next二s; Else / r=Head; while (r-next!二p) r=r-ncxt; r

37、-next二q; p-next二q-next; q-next=p; 5. 可按先遍历右子树，遍历根结点，再遍历左子树进行中序遍历，这样可实现由大到小遍历一棵二叉排序树。 具体算法实现如下： / 文件路径名 :exam4alg. h include ，zbinary sort tree. hz， / 二叉排序树类 template void InOrderHelp(BinTreeNodeEleniTYpe *r, const KeyType / 遍历左子树 if (rdata data rightChild, key); template void In Order (co nst Bin ar

38、)SortTree while(p!=NULL q 二p; whi1e ( q!=NULL r-next二q-next; r=p-next; while(r!=q) delete p; p=r;r=r-next; delete q; / del pro 7.二叉树采取顺序结构存储，是按完全二叉树格式存储的。对非完全二叉树要补上“虚结点”。由于不是完 全二叉树，在顺序结构存储中对叶子结点的判定是根据其左右子女为0。叶子和双亲结点下标间的关系满足 完全二叉树的性质。 int Leaves (int h) / 求深度为h以顺序结构存储的二叉树的叶子结点数 int BT; int len=2 h-l,

39、 count=0; /BT 是二叉树结点值一维数组, 容量为2 11 for (i=l; ilen) count卄；第i个结点没子女，肯定是叶子 else if(BT2*i=0 else BST=BST aright ； return false; 9.int Compare-List(SqList a, SqList b) /a, b为顺序表，若时，返回T；a二b时，返回0； ab时，返回1 i 二0; while (inext; q二b-next; c-next=NULL; while (p p-next二c-next; c-next二p; p=pn; else qn=q- next; q

40、-next二c-next; c-next二q; q二qn; while (p) pn二p-next; p-next=cnext; c-next=p; p=pn; while (q) qn二q-next; q-next二c-next; c-next二q; q二qn; free(b); /MergcList 11.Status Del-subtree (Bi tree bt) 删除 bt所指二叉树，并释放相应的空间 if (bt) De1-subtree(bt-1 chi Id); Del-subtree (bt-rchiId); free (bt); return OK; /Del-subtre

41、e Status Search-del(Bitree bt, TelemType x) / 在 bt所指的二叉树中，查找所有元素值为X的结点，并删除以它为根的子树if (bt) if (bt-data=x) Del-subtree(bt); else Search-De1(bt-1 ch i1d, x); Search-Del(bt-rchild, x); return OK; /Search-Del 12.TelemType Maxv(Bitree T) / 返回二叉排序树T中所有结点的最大值 for (p=T; p-rchild; p=p-rchild); return p-data; /

42、Maxv TelemType Minv(Bitree T) / 返回二叉排序树 T中所有结点的最小值 for (p=T; p-lchild; p二p-lchi1d); return p-data; /Minv Status IsBST(Bitree T) / 判别 T是否为二叉排序树 if (!T) return OK; else if (!T-lch订d)|(T-lch订d) /IsBST 13.void Got_PreScq(Bitree T)/求先序序列为k的结点的值 if(T) C+; 每访问一个子树的根都会使前序序号计数器加1 if (c=k) printf ( z/ Value i

43、s %dn ，z, T-data); exit (1); else Get_PreSeq(T-lch订d); / 在左子树中查找 Get_PreSeq(T-rch订d); 在右子树中查找 /if /Get_PreSeq 14.int pathMAXSIZE, visitedMAXSIZE; int Find All Path(ALGraph G, int u, int v, int k)/求有向图G中顶点u到v之间的所有简单 路径,k表示当前路径长度 pathk=u; / 加入当前路径中 visitedu=l; if(u=v) / 找到了一条简单路径 printf (Found one pat

44、h! n ，z); for (i=0;pathi; i+) printf pathi) ; / 打印输出 Else for(p二G. verticesu. firstarc;p;p=p-nextare) l=p-adjvex; if (!visitedl) Find Al 1 Path(G, 1, v, k+1) ; / 继续寻找 visitedu=O; pathk=0; / 回溯 /Find_All_Path 15.先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的 值，重复上述过程直到最后一个结点。具体算法： Status Delete_Equal

45、(Linklist q=p-next; /p, q 指向相邻两元素 while(p-next) if(p-data!=q-data) p=p-next;q=p-next; 当相邻两元素不相等时,p, q都向后推一步 Else while (q-data=p-data) s=q； q=q-next; free (s); p-next=q;p=q;q=p-next; 当相邻元素相等时删除多余元素 /else /wh订e /Delete_Equal void LayerOrder(Bitree T)/层序遍历二叉树16. TnitQueue(Q) ; / 建立工作队列 EnQueue (Q, T);

46、 wh i1e (!QuoueEmpty(Q) DeQueue (Q, p); visit (p); if(p-lchild) EnQueue(Q, p-lchild); if(p-rchiId) EnQueue(Q, p-rchi1d); /LayerOrder 17. int PairBracket( char *SR) / 检查表达式ST中括号是否配对 int i; SeqStack S; / 定义一个栈 InitStack ( for (i=0; istrlen(SR) ; i十+) if ( Si= C ) Push( / 遇( 时进栈if ( Si“)， )遇) if (JStackEmpty(S)/栈不为空时 , 将栈顶元素出栈Pop ( else return 0;/不匹配，返回0 if EmptyStack(/ 匹配 , 返回1 else return 0;/不匹配 , 返回0 i class Link / 链表类 private: j Snode *IIead; j public: |Link I void ! void I ! void 12.下列函数是二叉排序树的什么算法？如果K值为5,针对下图所示二叉L疋刑ET疋 FPT 比较几次得到结 果？