2017年常州大学数据结构(同等学力加试)复试仿真模拟三套题
● 摘要
一、应用题
1． S 是字符数组
，中存放的是该字符串的有效长度，
假设中字符串的内容为
说明下列程序的功能及执行结果。
【答案】本程序的功能是求字符串的nextval 函数，程序执行结果是0110132。
2． 将算术表达式（（a+b）+c*（d+e）+f）*（g+h）转化为二叉树。
【答案】该算术表达式转化的二叉树如图所示。
图
3． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。
（1）试问这种二叉树的结点总数是多少？
（2）试证明 。其中：表示第i 个叶结点所在的层号（设根结点所在层号为1）。
【答案】（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-l 。
（2）证明：当i=l时，
成立。
第 2 页，共 21 页 , 公式成立。设当i=n-1时公式成立，证明当i=n时公式仍
设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1, 对于公式的变化，是减少了一个原来的叶结点，増加了两个新叶结点，反映到公
，所以结果不变，这就证明当i=n时公式仍成立。证毕。 式中. 因为
4． 画出同时满足下列两个条件的两棵不同的二叉树。
（1）按前序遍历二叉树的顺序为ABCDE 。
（2）高度为5其对应的树（森林）的高度最大为4。
【答案】（1）满足条件的二叉树如图1所示：
图1
（2）满足条件的二叉树如图2所示：
图2
5． 在堆排序、快速排序和合并排序中：
（1）若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？
（2）若只从排序结果的稳定性考虑，则应选取哪种排序方法？
（3）若只从平均情况下排序最快考虑，则应选取哪种排序方法？
（4）若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？
【答案】（1）应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法。 （2）应选取归并排序方法
（3）应选取快速排序方法
（4）应选取堆排序方法
第 3 页，共 21 页
6． 在某程序中，有两个栈共享一个一维数组空间
的栈底。 分别是两个栈
（1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。
（2）对栈1、栈2, 试分别写出栈满、栈空的条件。
【答案】（1）入栈主要语句
出栈主要语句
（2）
7． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问：
（1）当n=7时，在最好情况下需进行多少次比较? 请说明理由。
（2）当n=7时，给出一个最好情况的初始排序的实例。
（3）当n=7时，在最坏情况下需进行多少次比较? 请说明理由。
（4）当n=7时，给出一个最坏情况的初始排序的实例。
【答案】（1）在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度那么第一趟划分得到两个长度均为
以此类推，
总共进行
需2次，共10次即可。
（2）在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。
（3）在最坏情况下，若每次用来划分的记录的关键字具有最大（或最小）值，那么只能得到左（或右）子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递増次序排列时，快速排序的效率与起泡排序相同，其时间复杂度为
n=7时，最坏情况下的比较次数为21次。
（4）在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递増排序。
8． 写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。
第 4 页，共 21 页 的子文件，第二趟划分得到4个长度均为的子文件，趟划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一趟需比较6次，第二趟分别对两个子文件（长度均为3，k=2）进行排序，各所以当