2013数据结构复习题程序与算法题.doc

第  PAGE 5 页 共  NUMPAGES 5 页 一、程序理解题 写出下列程序段的输出结果，简述算法的功能 void main() { SeqStack intS; 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 coutd; } } 2．写出下列程序段的输出结果 void main() { CirQueue charQ; 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 (); couty; (1) y= c h a } coutxendl; (2) x= r } 3、在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，栈顶元素、栈底元素、栈中元素分别是什么？（push(k)表示整数k入栈，pop表示栈顶元素出栈。）， void main( ) { SeqStackint 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(); coutx; (2)x= 385 } coutendl; } 4、在操作序列EnQueue(1)、 EnQueue(3)、 DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，队头元素和队尾元素分别是什么？（EnQueue(k)表示整数k入队，DeQueue表示队头元素出队）。 写出下列程序段的输出结果 void main( ) { SeqStackchar b; char x,y; x=c; y=k; b.Push(y); b.Push(x); b.Push(a); b.Push(y); b.Pop(); b.Push(t); b.Push(x); b.Pop(); b.Push(s); while (!b.Empty()) { char n=b.Pop(); coutn; (1) n= s t a c k } coutendl; (2) x= c } 二、算法 1、设计算法求二叉树的叶子结点个数。 struct BiNode //二叉树的结点结构 { int data; BiNode *lchild, *rchild; }; int count(BiNode * root) /* root为二叉树的根结点*/ { int c1,c2,c; if(root==NULL) c=0; else if(root-lchild==NULL root-rchild==NULL) c=1; else { c1=count(root-lchild); c2=count(root-rchild); c=c1+c2;