数据结构复习题——程序与算法题

1、一、程序理解题1. 写出下列程序段的输出结果，简述算法的功能void main()SeqStack <int>S; int d;CirQueue <int> Q;Q.EnQueue(1);Q.EnQueue(2);Q.EnQueue(3);Q.EnQueue(4);Q.EnQueue(5);while(!Q.Empty() d=Q.DeQueue(); S.Push(d); (1) 栈中元素： 12345 while(!S.Empty() d=S.Pop(); Q.EnQueue(d); (2) 队列中元素： 54321 cout<<d;2写出下列程序段的输

2、出结果void main()CirQueue <char>Q; char x='e', y='c'Q.EnQueue ('h'); Q.EnQueue ('r'); Q.EnQueue (y); x=Q.DeQueue (); Q.EnQueue (x); x=Q.DeQueue (); Q.EnQueue ('a'); while(!Q.Empty() y=Q.DeQueue ();cout<<y; (1) y= c h a cout<<x<<endl; (2) x

3、= r 3、在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，栈顶元素、栈底元素、栈中元素分别是什么？（push(k)表示整数k入栈，pop表示栈顶元素出栈。），void main( ) SeqStack<int> b; b.Push(5); b.Push(2);b.Pop(); b.Push(8); b.Push(7);b.Pop(); b.Push(3); (1) 栈底元素 5 ，栈顶元素 3 。while (!b.Empty() int x=b.Pop();cout<<x; (2)x= 385 cout&

4、lt;<endl; 4、在操作序列EnQueue(1)、 EnQueue(3)、 DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，队头元素和队尾元素分别是什么？（EnQueue(k)表示整数k入队，DeQueue表示队头元素出队）。5、 写出下列程序段的输出结果void main( ) SeqStack<char> b; char x,y;x='c'y='k'b.Push(y); b.Push(x); b.Push('a'); b.Push(y);b.Pop(); b.Pus

5、h('t'); b.Push(x);b.Pop(); b.Push('s');while (!b.Empty() char n=b.Pop(); cout<<n; (1) n= s t a c k cout<<endl; (2) x= c 二、算法1、设计算法求二叉树的叶子结点个数。struct BiNode /二叉树的结点结构 int data; BiNode *lchild, *rchild;int count(BiNode * root) /* root为二叉树的根结点*/ int c1,c2,c; if(root=NULL) c=

6、0; else if(root->lchild=NULL && root->rchild=NULL) c=1; else c1=count(root->lchild); c2=count(root->rchild); c=c1+c2; return c; 2、设计算法求二叉树的深度。struct BiNode /二叉树的结点结构 int data; BiNode *lchild, *rchild; int Depth(BiNode<T> *root) int hl,hr; if (root= =NULL) return 0; else hl=

7、 Depth(root->lchild); hr= Depth(root ->rchild); if(hl>hr) return hl+1; elsereturn hr+1; 3、设一个算法，求二叉树中结点个数。struct binode int data; binode *lchild,*rchild; void num(BiNode<T> * root) if(root=NULL) return; n+; /在main函数前定义n num(root->lchild); num(root->rchild); 4、设计一个非递归的折半查找算法函数 P192void BubbleSso