数据结构复习题及参考答案

}

while (!stackempty (a)) cout <

}

该算法的输出结果为：

__________________________________________________________. 4.读下述算法，说明本算法完成什么功能。

template void BinTree ：：

unknown (BinTreeNode*t) { BinTreeNode< Type> *p =t, *temp; if (p!=NULL) {

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=”<data ; public: p=p->next; Link (){Head =NULL}; } void creat(); Head a } //output

第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 ( Kkey) { p = q; q = q->lch; } else { p = q; q = q->rch; } }

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页