安徽大学2014数据结构期末考试试卷(A卷)

四、 算法阅读题（本大题共3小题，每小题5分，共15分）

30．设线性表的n个结点定义为（a0,a1,…,an-1），在顺序表上实现的插入和删除算法如下，请在空白处填入适当内容。(顺序表的最大可容纳项数为MaxSize)

Template int SeqList::Insert(Type &x, int i) { If (i<0 || i>last+1 || last== (1) ) return 0; Else {

Last++;

For(int j=last;j>i;j--) data[j]= (2) ; (3) ; Return 1; } }

Template int seqList::Remove(Type &x){ int i=Find(x); if(i>=0) { last--;

for (int j= (4) ;j<=last;j++) data[j]= (5) ; return 1; }

return 0; } 答案:

(1) MaxSize-1 (2) data[j-1] (3) Data[i]=x

(4) i (5) data[j+1]

31．阅读下面的算法，请回答下列问题：

（1） 试说明算法的功能。

（2） 当执行该程序时，输入12345678-1，输出什么结果？

#define StackSize 200 typedef int DataType; typedef struct{

DataType data[StackSize];

5

int top; }SeqStack;

void Push(SeqStack *s,DataType x) {

if(s->top!=StackSize-1) s->data[++s->top]=x; }

DataType Pop(SeqStack *s) {

if(s->top!=-1)

return s->data[s->top--]; }

void main( ) {

DataType i; SeqStack s; s.top=-1;

scanf(“%d”,&i); while(i!=-1)

{

push(&s,i); scanf(“%d”,&i); }

while(s->top!=-1)

{

i=Pop(&s); printf(“m”,i); } }

答案:

(1)程序的功能是把输入的一串整数(用-1做结束标记) ，按照与输入相反的次序输出。用栈实现这一功能。

（2）输出结果 8 7 6 5 4 3 2 1。

6

五、 算法设计题（本题共10分）

33．设一棵二叉树以二叉链表表示，试以成员函数形式编写有关二叉树的递归算法。

（1）统计二叉树中度为1的结点个数；（5分） （2）统计二叉树中度为2的结点个数。（5分）

（提示：递归算法如32题所示）

解答：（1）统计二叉树中度为1的结点个数。 Template

Int BinaryTree ::Degree1(BinTreeNode *t)const{

If(t==NULL) return 0;

If(t->leftchild!=NULL &&t->rightchild==NULL || t->leftchild==NULL &&t->rightchild!=NULL) Return 1+Degree1(t->leftchild)+Degree1(t->rightchild); Return Degree1(t->leftchild)+Degree1(t->rightchild);

}

(2) 统计二叉树中度为2的结点个数。 Template

Int BinaryTree ::Degree2(BinTreeNode *t)const{

If(t==NULL) return 0;

If(t->leftchild!=NULL &&t->rightchild!=NULL )

Return 1+Degree2(t->leftchild)+Degree2(t->rightchild); Return Degree2(t->leftchild)+Degree2(t->rightchild);

}

7