12.有如下图所示单链表，经过reverse 算法处理后，单链表发生了什么变化 ？ 画出处理后的单链表图示。 void Link ::reverse() struct Snode //结点结构 { Snode *p, *q ; { char data; p= Head ->next; Snode *next ; Head ->next=NULL; } ; while( p !=NULL) { q=p->next ; class Link //链表类 p->next= Head ->next; { private: Head >next=p; Snode *Head; p=q; public: } Link (){Head =NULL}; } // reverse void creat(); Head void reverse (); d a e ^ c b void output(); //…….; 13.下列函数是二叉排序树的什么算法？如果K值为5，针对下图所示二叉树，运行下列算法，输出是什么？比较几次得到结果？
Void Bstree::Search( KeyType K) { int flag = 0;
BstNode *q=root, *p = NULL; while((q!=NULL)&&(flag==0)) { if(q->key==K) flag = 1;
else if ( K
if(flag == 0) cout<<\查找失败，无此结点！\\n\ else cout<<\查找成功，找到：\
}
7
4 8
2 9 5 14.void AA (LNode * HL,const ElemType & item)
9 2 {
LNode * newptr=new Lnode ; newptr->data=item; LNode *p=HL;
while ( p->next!=HL ) p=p->next;
newptr->next=HL; p->next=newptr; }
对于结点类型为LNode的单链表，以上算法的功能为：
15.void BB(List &L)
第11页共22页
{
int i=0;
while (i int j=i+1; while (j if(L.list[j] = =L.list) { for (int k=j+1;k else j++; } i++; } } 以上算法的功能为： 16.void CC(BTreeNode * & BST ) { ElemType a[6 ]={45，23，78，35，77，25}； BST=NULL； for( int i=0,i<6;i++) Insert(BST , a[i]); } 调用该算法后，生成的二叉搜索数的中序序列为： 17.void DD ( ) { ElemType A[ ]={1,3,5,7,9,2,4,6,8,10},B[10]; TwoMerge(A, B,0,4,9); for ( int i=0; i<10; i++) cout< 调用该算法后，输出结果为： 五、算法设计题： 1.编写复制一棵二叉树的非递归算法。 2.假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。 3.试用递归法编写输出从n个数中挑选 k个进行排列所得序列的算法。 4.编写一个算法，交换单链表中p所指向的结点和其后续结点的两个结点，Head指向该链表的表头，P指向链表中的某一结点。 Head d a c e ^ b第12页共22页 5.试写一递归算法，从大到小输出二叉排序树中所有的关键字值小于key的元素值。 6.已知带头结点的单链表是一个递增有序表，试写一算法，删除表中值大于min且小于max的结点（若表中有这样的结点），同时释放被删除结点的空间，这里min和max是两个给定的参数。 Head 26 7 50 ^ 15 9 7.已知深度为h的二叉树以一维数组BT(1:2h-1)作为其存储结构。请写一算法，求该二叉树中叶结点的个数。 8.编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找item带回整个结点的值并返回true，否则返回false。 bool Find（BtreeNode*BST，ElemType&item） 9.设A=(a1,...,am)和B=(b1,...,bn)均为顺序表，A'和B'分别为A和B中除去最大共同前缀后的子表。若A'=B'=空表，则A=B；若A'=空表，而B'≠空表，或者两者均不为空表，且A'的首元小于B'的首元，则A 10.已知单链表a和b的元素按值递增有序排列, 编写算法归并a和b得到新的单链表c，c的元素按值递减有序。 11.编写递归算法，对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 12.编写算法判别T是否为二叉排序树。 第13页共22页 参考答案 一、填空题： 1.4，10 2.n 3.1，2 4.线性结构，树型结构，图型结构 5.n(n-1)/2 n(n-1) 6.增加1 7.O(log2n) O(nlog2n) 8.归并 9. n-1 10.左右子树空 11.1225 12.n(n-1)/2 13.head(A) 14.节省空间 15.L->next=L->prior 或 L->next=L 16. 1044 17. 入栈（插入） ， 出栈（删除） 18. 前驱结点 ， 后继结点 19.中序序列 20.顺序存储结构 ， 有序的 21.O(n) O(1) 22. 行号 列号 h 23. 3 x 2.4 5 ／6 －*＋ 24.(3 -1)/2 33 25. n ， O (n) 26.零个字符的串 ， 零 27.邻接矩阵 ， 邻接表 28.s, p 29.q->next, q 30.两个串的长度相等且对应位置的字符相同 31.200+（6*20+12）= 326 32.1000+((18-10)*6 +(9-5))*4 = 1208 33. (1). (b) (2). (d) 34求矩阵第i列非零元素之和 35.将矩阵第i行全部置为零 36.2. 2; 4; （23，38，15） 37.堆排序、快速排序、归并排序、归并排序、快速排序、堆排序 二、单项选择题： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 B B B C B B D A C D B B A D A 16 17 18 19 20 21 22 23 24 252526 27 28 29 ① ② A C C D D B D A C B A B B D A 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 A B B A D B B D A A B B A D B 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 A B C B B D A D C D B C B C C 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 C C D C C C C B A C B A B C D 75 B 三、计算与算法应用题： A 1.普里姆算法从顶点1出发得到最小生成树为： (1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20 B 2.在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。 3.画出下列树对应的二叉树，并写出其先根遍历序列： D C E F G 先根遍历序列： A B D E G F C 第14页共22页 4.将关键字序列为{54，29，37，86，71，91，8，31，44，26}进行归并排序，写出各趟详细过程。 54 29 37 86 71 91 8 31 44 26 29 54 37 86 71 91 8 31 26 44 29 37 54 86 8 31 71 91 26 44 8 29 31 37 54 71 86 91 26 44 8 26 29 31 37 44 54 71 86 91 5.全部可能的拓扑排序序列为：1523634、152634、156234、561234、516234、512634、512364 6. 100 42 48 F 29 B 19 23 29 D H E 15 8 11 14 C 8 7 G A 7. 3 5 平均长度为4. 8.深度优先搜索序列：a，b，f，h，c，d，g，e 第15页共22页