2014-2015学年二学期数据结构期末考试试卷（A卷）

石家庄学院

2014-2015学年二学期数据结构期末考试试卷(A卷)

班级:___________学号:___________姓名:___________得分:___________

题号 得分 阅卷 一 二 三 四 五 六 七 八 九 十 成绩 复核 题目部分，(卷面共有23题,100分,各大题标有题量和总分) 一、应用题(4小题,共29分)

1．若一棵二叉树，左右子树均有三个结点，其左子树的前序序列与中序序列相同，右子树的中序序列与后序序列相同，试构造该树。

2．设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？ 3．请回答下列关于堆的一些问题

①堆的存储表示是顺序的，还是链接的?

②设有一个最小堆，即堆中任意结点的关键码均大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方?

③对一个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)?

4．若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？

二、判断正误(4小题,共4分)

1．有n个数顺序(依次)进栈，出栈序列有种。

2．算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。( )

3．线性表的逻辑顺序与物理顺序总是一致的（ ）。 4． 数据元素是数据的最小单位( )。 三、单项选择题(6小题,共12分) 1．循环链表H的尾结点P的特点是

A、P^.NEXT:=H B、P^.NEXT:= H^.NEXT C、P:=H D、P:=H^.NEXT

2．一般情况下，将递归算法转换成等价的非递增归算法应该设置 A、堆栈 B、队列 C、堆栈或队列 D、数组 3．在一棵高度为k的满二叉树中，结点总数为

A、2k-1 B、2k C、2k-1 D、?log2k?+1

4．对有18个元素的有序表作二分(折半)查找，则查找A[3]的比较序列的下标为 A、1、2、3 B、 9、5、2、3 C、 9、5、3 D、 9、4、2、3 5．下面说法错误的是

(1)算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A、 (1) B、 (1),(2) C、 (1),(4) D、 (3)

6．设有广义表D(a,b,D),其长度为（ ），深度为

A、∞ B、3 C、2 D、5 四、算法设计题(3小题,共35分)

1．编写算法判别给定二叉树是否为完全二叉树。 2．设后序线索树中结点构造为(Ltag,Lchild,Data,Rchild,Rtag)。其中:Ltag,Rtag 值为0时,Lchild、Rchild 分别为儿子指针；否则分别为直接前驱,直接后继的线索。请写出在后序线索树上找给定结点p^ 的直接前驱q 的算法。（13分） 3．关于堆排序方法，完成如下工作： (1) 简述该方法的基本思想。 (2) 写出堆排序算法。

(3) 分析该算法的时间复杂度。 五、填空题(5小题,共12分)

1．含4个度为2的结点和5个叶子结点的二叉树，可有______个度为1的结点。 2．设为哈夫曼树的叶子结点数目．则哈夫曼树共有_______个结点。 3．树在计算机内的表示方式有 ， ， 。 4．通常元素进栈的操作是_________。

5． 一棵高度为5的满二叉树中的结点数为 个，一棵高度为3满四叉树中的结点数为 个。

六、简答题(1小题,共8分)

1．试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

石家庄学院

2014-2015学年二学期数据结构期末考试试卷(A卷)

答案部分，(卷面共有23题,100.0分,各大题标有题量和总分) 一、应用题(4小题,共8分)

1．据题意，左子树的前序序列与中序序列相同，有

即以左子树为根的树无左孩子。此外，右子树的中序序列与后序序列相同，即有

即以右子树为根的树无右孩子。由此构造该树如下图所示：

2．方法有二。一是对该算术表达式（二叉树）进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值；二是递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符（+、-、*、/ 等）进行最后求值。 3．①堆的存储表示是顺序的。

②其具有最大值的元素可能在叶子结点上，即③最多作4n次数据比较。

4．将学号、姓名、平均成绩看成一个记录（元素，含三个数据项），将100个这样的记录存于数组中。因一般无增删操作，故宜采用顺序存储。 typedef struct {int num;//学号

char name[8];//姓名 float score;/平均成绩 }node；

node student[100]; 二、判断正误(4小题,共8分) 1．√ 2．× 3．× 4．×

三、单项选择题(6小题,共8分) 1． A 2．A 3． C 4．D 5．C 6． B A

四、算法设计题(3小题,共8分)

1．int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0

{

InitQueue(Q); flag=0;

EnQueue(Q,T); //建立工作队列 while(!QueueEmpty(Q)) {

DeQueue(Q,p); if(!p) flag=1;

else if(flag) return 0; else {

EnQueue(Q,p->lchild);

EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列 }

}//while return 1;

}//IsFull_Bitree

分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针。 2．[题目分析]后序遍历是“左-右-根”，因此，若结点有右子女，则右子女是其后序前驱，否则，左子女（或左线索）指向其后序前驱。

BiThrTree PostSucc (BiThrTree T,p)//在后序线索二叉树T中，查找指定结点p的直接前驱q {if(p->Rtag==0) q=p->Rchild;//若p有右子女，则右子女为其前驱

else q=p->Lchild; //若p无右子女，左子女或左线索就是p的后序前驱 return (q);

}//结束PostSucc

3．(1) 堆排序是对树型选择排序的改进，克服了树型选择排序的缺点，其定义在前面已多次谈到，请参见上面“四、应用题”的43题和45题（4）。“筛选”是堆排序的基础算法。由于堆可以看作具有n个结点的完全二叉树，建堆过程是从待排序序列第一个非终端结点?n/2?开始，直到根结点，进行“筛选”的过程。堆建成后，即可选得一个关键字最大或最小的记录。然后堆顶元素与序列中最后一个元素交换，再将序列中前n-1记录重新调整为堆，可选得一个关键字次大或次小的记录。依次类推，则可得到元素的有序序列。 (2) void Sift(RecType R[]，int i，int m) { //假设R[i+1..m]中各元素满足堆的定义，本算法调整R[i]使序列R[i..m]中各元素满足堆的性质

R[0]=R[i];

for(j=2*i; j<=m; j*=2)

{ if(j

R[i]=R[0]; }//Sift

void HeapSort(RecType R[]，int n)

{ //对记录序列R[1..n]进行堆排序。 for(i=n/2;i>0;i--) Sift(R,i,n);

for(i=n;i>1;i--){ R[1]<-->R[i]; Sift(R,1,i-1);}//for }//HeapSort

(3)堆排序的时间主要由建堆和筛选两部分时间开销构成。对深度为h的堆，“筛选”所需进行的关键字比较的次数至多为2(h－1)；对n个关键字，建成深度为h(=?log2n?+1)的堆，所需进行的关键字比较的次数至多C (n)，它满足下式：

调整“堆顶”n-1次，总共进行的关键字比较的次数不超过：2(?log2(n-1)?+ ?log2(n-2)?+ ?+log22)<2n(?log2n?)因此，堆排序的时间复杂度为O（nlog2n）。

五、填空题(5小题,共8分) 1．0至多个。 2．-1 3．双亲链表表示法 孩子链表表示法 孩子兄弟表示法 4．先移动栈顶指针，后存入元素。 5．63 85

六、简答题(1小题,共8分)

1．例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢?是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题，我们从高级语言的层次讨论这个问题。最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。 试卷指标统计数据 总题量 23 总分值 100 1 2 8 1 3 4 4 2 3 2 线性表及其顺序存储 顺序表 栈和队列 查找 章节编码 题量 分值 章节说明 01 02 05 07 08 10 13 45 树和二叉树、森林 24 排序 18 绪论 6 数据结构试题 难度编码 1 2 3 题量 8 9 6 4 4 6 3 5 1 分值 39 36 25 29 4 12 35 12 8 难度说明 易 中 难 应用题 判断正误 单项选择题 算法设计题 填空题 简答题 题型编码 01 02 03 04 06 07 题量 分值 题型说明

本文来源：https://www.bwwdw.com/article/pngh.html