2012《数据结构》期中试卷A.doc

《2012《数据结构》期中试卷A.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、专业：计算机科学与技术课程名称：数据结构学分：4试卷编号（A）课程编号：1349160考试方式：闭卷考试时间：90分钟拟卷人(签字)：拟卷日期：2012-11-1审核人(签字)：得分统计表：题号一二三四五六七八九十总分得分得分一、简答题：（5小题，共50分）1.（本题10分）什么是顺序表？什么是栈？什么是队列？【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入在

2、表的一端进行，数据的删除在表的另一端进行，因此队列具有先进先出，后进后出的特点。2.（本题10分）将下列中缀表达式转换为等价的后缀表达式。(1)5+6*7【答】：(1)5+6*7后缀表达式：567*+(2)(5-6)/7【答】：(2)(5-6)/7后缀表达式：56-7/(3)5*(7-6)+8/9【答】：(3)5*(7-6)+8/9后缀表达式：576-*89/+(4)7*(5-6*8)-9【答】：(4)7*(5-6*8)-9后缀表达式：7568*-*9-3.（本题10分）队列以循环队列（d[0~m-1]）方式存储,并设立尾指针rear和队长length（当前队列中的元素个数），试给出

3、队列队空和队满条件。【答】：队列队空：rear=front=0队满条件：(rear+1)%n=front4.（本题10分）已知一棵二叉树如图1所示，试求该二叉树前序、中序和后序遍历的结果。图1二叉树形状【答】：前序遍历为CBADEGFH，中序遍历为ABCEFGHD，后序遍历为ABFHGEDC。5.（本题10分）若一棵二叉树的左、右子树均有3个结点，其左子树的前序序列与中序序列相同，右子树的中序序列与后序序列相同，试画出该二叉树。【答】：该二叉树如下图所示：得分二、算法设计题（4小题，共50分）1.（本题10分）设计一个算法，对一个有序的单链表，删除所有值大于x而不大于y的结点。【答】

4、：voiddeletedata(linklisthead,datatypex,datatypey){/*删除带头结点单链表中所有结点值大于x而不大于y的结点*/linklistpre=head,p,q;p=head->next;/*初始化*/while(p&&p->data<=x)/*找第1处大于x的结点位置*/{pre=p;p=p->next;}while(p&&p->data<=y)/*找第1处小于y的位置*/{p=p->next;q=pre->next;/*删除大于x而小于y的结点*/pre->next=p;pre=q->next;while(pre!=p)/*释放被删除结点所

5、占用的空间*/{free(q);q=pre;pre=pre->next;}}2.（本题10分）写出求Ackerman函数Ack(m，n)值的递归函数，Ackerman函数在m≥0和n≥0时的定义为：Ack(0，n)=n+1;Ack(m，0)=Ack(m−1，1);Ack(m，n)=Ack(m−1，Ack(m，n−1))n>0且m>0【答】：intAck(intm,intn)//递归函数{if(m==0)returnn+1;elseif(n==0){returnAck(m-1,1);}else{returnAck(m-1,Ack(m,n-1));}}3.（本题15分）已知多项式pn(x

6、)=a0+a1x+a2x2+…+anxn的系数按顺序存储在数组a中，试编写一个递归函数，求n阶多项式的值。【答】：doublepnx1(doublea[],intn,doublex)//递归函数{if(n==0)returna[0];elsereturnpnx1(a,n-1,x)+a[n]*pow(x,n);}4.（本题15分）设二叉树以二叉链表为存储结构，采用递归方式编写函数，求一棵给定二叉树中叶子结点的个数。【答】：intleaf1(bintreet)/*递归方法求二叉树叶子结点的个数*/{if(t==NULL)return0;elseif(!t->lchild&&!t->rch

7、ild)return1;elsereturnleaf1(t->lchild)+leaf1(t->rchild);}