信息学院本科生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页
相关推荐：
loading