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

专业：计算机科学与技术 课程名称：数据结构 学分：4 试卷编号（A） 课程编号： 1349160 考试方式： 闭卷 考试时间： 90 分钟 拟卷人(签字)： 拟卷日期：2012-11-1 审核人(签字)： 得分统计表： 题 号 一 二 三 四 五 六 七 八 九 十 总 分 得 分 得分 一、简答题：（5小题，共50分） 1.（本题10分）什么是顺序表？什么是栈？什么是队列？ 【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行 （即栈顶），因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具有先进先出，后进后出的特点。 2.（本题10分）将下列中缀表达式转换为等价的后缀表达式。 (1) 5+6*7 【答】： (1) 5+6*7 后缀表达式：5 6 7*+ (2) (5-6)/7 【答】：(2) (5-6)/7 后缀表达式：5 6-7/ (3) 5*(7-6)+8/9 【答】：(3) 5*(7-6)+8/9 后缀表达式：5 7 6-*8 9/+ (4) 7*(5-6*8)-9 【答】： (4) 7*(5-6*8)-9 后缀表达式：7 5 6 8*-*9- 3.（本题10分）队列以循环队列（d[0~m-1]）方式存储, 并设立尾指针rear和队长length（当前队列中的元素个数），试给出队列队空和队满条件。 【答】： 队列队空：rear = front=0 队满条件：(rear + 1)%n = front 4.（本题10分）已知一棵二叉树如图1所示，试求该二叉树前序、中序和后序遍历的结果。 图1 二叉树形状 【答】： 前序遍历为 CBADEGFH，中序遍历为 ABCEFGHD，后序遍历为ABFHGEDC。 5.（本题10分）若一棵二叉树的左、右子树均有 3 个结点，其左子树的前序序列与中序序列相同， 右子树的中序序列与后序序列相同，试画出该二叉树。 【答】：该二叉树如下图所示： 得分 二、算法设计题（4小题，共50分） 1.（本题10分）设计一个算法，对一个有序的单链表，删除所有值大于 x 而不大于 y 的结点。 【答】： void deletedata(linklist head,datatype x,datatype y) { /*删除带头结点单链表中所有结点值大于 x 而不大于 y 的结点*/ linklist pre=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) /*释放被删除结点所占用的空间*/ {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)) n0 且 m0 【答】： int Ack (int m,int n) //递归函数 { if (m == 0) return n + 1; else if (n == 0) { return Ack (m - 1,1); } else { return Ack (m - 1,Ack (m,n - 1)); } } 3.（本题15分）已知多项式 pn(x) = a0 + a1x + a2x2 + … + anxn的系数按顺序存储在数组 a 中，试编写一个递归函数，求 n 阶多项式的值。 【答】： double pnx1(double a[],int n,double x)//递归函数 { if (n==0) return a[0]; else return pnx1(a,n-1,x)+a[n]