2010学院A卷答案

信息学院本科生2009－2010学年第二学期 数据结构期末考试试卷(A卷)答案

得 分 一、单项选择题（每小题2分，共20分）

1．若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许

连续三次进行退栈工作，则不可能得到的出栈序列是____ D ____。

B．cbdaef

C．abcdef

D．afedcb

A．dcebfa

2．某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。设入队顺序是abcde，则不可能得到的出队顺序是___ C _____。 A．bacde

B．dbace

C．dbcae

D．ecbad

3．在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是____ C ____。 A．13，48 C．24，53

B．24，48 D．24，90

4．在一棵度为4的树T中，若有20个度为4的结点，10

个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是____ B ____。 A．41

B．82

C．113

D．122

5．使用哈夫曼算法对n（n大于等于2）个权值均不相同的字符构造哈夫曼树，关于该树的叙述中，错误的是____A____。 A．该树一定是一棵完全二叉树 B．树中一定没有度为1的结点

C．树中两个权值最小的结点可能是兄弟结点

D．树中任一非叶结点的权值一定不小于下一层任一结点的权值

6．若无向图G = (V, E)中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是___ C _____。 A．6

B．15

C．16

D．21

7．下列排序算法中，____C___算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。 A．堆排序

B．起泡排序

C．快速排序

D．希尔排序

第1页，共6页

8．已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多是____ B ____。 A．4

B．5

C．6

D．7

9．采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是___ D _____。

A．递归次数与初始数据的排列次序无关

B．每次划分后，先处理较长的分区可以减少递归次数 C．每次划分后，先处理较短的分区可以减少递归次数 D．递归次数与每次划分后得到的分区处理顺序无关

10．对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下 第一趟：2，12，16，5，10，88 第二趟：2，12，5，10，16，88 第三趟：2，5，10，12，16，88 则采用的排序方法可能是___A_____。 A：起泡排序

B：希尔排序

C：归并排序

D：基数排序

得 分

二、（本题10分）设一棵二叉排序树的先序遍历序列为25，16，23，48，35，40，36，79，72，82，请画出该二叉排序树，并简要描述思路。

25162335487940367282

（本题12分）有以下关键字：28，72，97，63，4，53，84，32，61，得 分 三、

52，使用堆排序方法将所给关键字排成升序序列，给出排序过程。要求画出初始堆，每输出一个元素，画出剩余元素组成的新堆。

第2页，共6页

32636147252539784283263619772524845328

61328472635297453286361327284975245328615232728497284536353523272849728614635232287284975361463725284972853324616342828452728497536132325361635263728497第3页，共6页

得 分 四、（本题10分）设关键字序列为：1，13，22，41，53，64，85，130，151，使用二分查找法分别查找关键字60和24，给出查找过程，查找过程

中，查找序列分别是什么，并求各自的查找长度。

查找60的比较序列：53，85，64，查找成功，查找长度=3 查找24的比较序列：53，13，22，41，查找不成功，查找长度=4 或是

查找60的比较序列：53，130，85，64，查找成功，查找长度=4 查找24的比较序列：53，22，41，查找不成功，查找长度=3

五、（本题6分）交叉矩阵”是如下图所示的大小为2n×2n（n为正整数）

得 分 的矩阵，其中非零元素的分布如图中“×”符号所示。设计一种映射模式，

使用大小为4n的一维数组保存交叉矩阵，给出矩阵元素下标到数组位置

的映射函数。

用一维数组a保存矩阵非0元素，左上?右下的主对角线保存在数组起始位置，随后保存左下?右上的对角线，则可得映射函数

a[i?1],??M(i,j)??a[4n?i],?0,?i?ji?j?2n?1

else对角线保存顺序不同，可能会有不同的映射函数，只要映射正确即可。

第4页，共6页

六、（本题12分）给定字符集及对应的出现频度值如下表所示：

A B C D E F G H 得 分 字符 频度 67 52 31 7 15 29 20 46

请构造对应该字符集的哈夫曼树，给出各字符的哈夫曼编码。

26715511260B52F29C31G20D722E15A674288H46 字符 编码

A

B C D E F G H 10 00 011 11010 11011 010 1100 111 得 分 七、（本题15分）对下面加权有向图，回答下列问题。

1）给出每个顶点的入度和出度。 2）画出邻接链表。

3）求所有点对间的最短路径。

出度：3，2，2，0，3 入度：0，3，3，3，1 邻接链表： 0 (1, 5) (2, 3) (4, 2) 1 (2, 2) (3, 6) 2 (1, 1) (3, 2) 3

4 (1, 6) (2, 10) (3, 4) 最短路径

0 0 0 1 5 2 3 第5页，共6页

3 5 4 2 1 2 3 4 NA NA NA NA 0 1 NA 6 2 0 NA 8 4 2 0 4 NA NA NA 0 除以下3条路径外，其他最短路径皆为直达或不存在 0?2?3 4?1?2 1?2?3

八、（本题15分）已知一棵二叉树用二叉链表存储，root指向根结点，树

得 分 中每个结点中均保存一个非负整数。定义叶路径长度为从根到叶结点的路

径上各结点中保存的值之和。试编写程序，输出该树中路径长度最大的一

条路径。要求：

（1）描述算法的基本设计思想及实现步骤； （2）给出算法中使用的数据结构；

（3）根据设计思想和实现步骤，采用C++描述算法，关键之处请给出简要注释。 答案略。

第6页，共6页

1 2 3 4 NA NA NA NA 0 1 NA 6 2 0 NA 8 4 2 0 4 NA NA NA 0 除以下3条路径外，其他最短路径皆为直达或不存在 0?2?3 4?1?2 1?2?3

八、（本题15分）已知一棵二叉树用二叉链表存储，root指向根结点，树

得 分 中每个结点中均保存一个非负整数。定义叶路径长度为从根到叶结点的路

径上各结点中保存的值之和。试编写程序，输出该树中路径长度最大的一

条路径。要求：

（1）描述算法的基本设计思想及实现步骤； （2）给出算法中使用的数据结构；

（3）根据设计思想和实现步骤，采用C++描述算法，关键之处请给出简要注释。 答案略。

第6页，共6页

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