发布时间 : 星期四 文章数据结构复习题及参考答案更新完毕开始阅读07758f7bc850ad02df804100
}
while (!stackempty (a)) cout < } 该算法的输出结果为： __________________________________________________________. 4.读下述算法，说明本算法完成什么功能。 template unknown (BinTreeNode temp = p→leftchild; p→leftchild = p→rightchild; p→rightchild = temp; unknown(p→leftchild); undnown(p→rightchild); } } // 类定义 该算法的功能是：________________________________ const int MAX=20; 5.阅读下列算法，说明该算法的作用。 typedef char ElemType ; void Sqstack::push(ElemType x ) class Sqstack { if ( top==MAX-1 ) { private: cout<<”\\n 满！”； ElemType elem [MAX]; else { top++; int top ; elem[top]=x; public: } Sqstack(){top=0}; } // push ElemType pop(); void push(ElemType x); //…….; } ; struct Snode //结点结构 { char data; 6.有如下图所示单链表，经过output（）算法处理后， Snode *next ; 单链表发生了什么变化 ？画出处理后的单链表图示。 } ; void Link :output() class Link //链表类 { p=Head->next; { private: while( p !=NULL) Snode *Head; { cout<<”\\n data=”< 第9页共22页 b c d e ^ void output(); //…….; 7.阅读下列算法，说明该算法的作用。 int LinkList::sum【 】 { int x;NodeType *p;p=Head->next; while(p!=NULL) { x++; p=p->next; } return x; } // pop 8.读下述算法，说明本算法完成什么功能。 void Btree ::inordern( bnode *p, int &n ) { if ( p!=NULL) { inordern( p->lch, n); if ( p->lch==NULL && p->rch==NULL) n++; inordern( p->rch, n); } } // inordern 9.void AD(Lnode* & HL) { Insert(HL,30); Insert(HL,50); Delete(HL,26); Delete(HL,55); } 假定调用该算法时以HL为表头指针的单链表中的内容为（15，26，48，55），则调用返回后该单链表中的内容为：______________________________。 10. void AI(adjmatrrix GA,int i,int n) { cout< // 类定义 for(int j=0;j const int MAX=20; if(Ga[I][j]! =0&& GA[i][j]! =MaxValue&& ! visited[j]) typedef char ElemType ; AI(GA,j,n); class Sqstack } { private: 该算法的功能为： ElemType elem [MAX]; ___________________________________。 int top ; public: 11.阅读下列算法，说明该算法的作用。 Sqstack(){top=0}; ElemTtype Sqstack::pop【 】 ElemType pop(); { ElemType x; void push(ElemType x); if ( top==0 ) x=-999; //…….; else { x = elem[top]; } ; top--; } return x; } // pop 第10页共22页 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页