2017年中国刑事警察学院计算机软件综合之数据结构(C语言版)复试仿真模拟三套题
● 摘要
目录
2017年中国刑事警察学院计算机软件综合之数据结构(C语言版) 复试仿真模拟三套题（一） .. 2
2017年中国刑事警察学院计算机软件综合之数据结构(C语言版) 复试仿真模拟三套题（二） .. 8 2017年中国刑事警察学院计算机软件综合之数据结构(C语言版) 复试仿真模拟三套题（三） 16
第 1 页，共 24 页
一、应用题
1． 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。
【答案】快速排序的思想如下：首先将待排序记录序列中的所有记录作为当前待排序区域，
，凡其关键字不大干枢轴的记录均移动至该记录之前，以第一个记录的关键字作为枢轴（或支点）
凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序
割成两部分：和和
且
将分然后再递归地将进行快速排序。快速排序在记录有序时蜕变为起泡排序，可用“三者取中”法改善其性能，避免最坏情况的出现。本题解答如下：
初始序列：[28]，07，39，10，65，14，61，17，50，21
21移动：21，07，39，10，65，14，61，17，50，[]
39移动：21，07，[]，10，65，14，61，17，50，39
17移动：21，07，17，10，65，14，61，[]，50，39
65移动：21，07，17，10，[]，14，61，65，50，39
14移动：21，07，17，10，14，[28]，61，65，50，39
2． 系统中有多个生产者进程和消费者进程，，共享用一个可以存1000个产品的缓冲区（初始为空）当缓冲区为未满时，生产者进程可以放入一件其生产的产品，否则等待；当缓冲区为未空时，消费者进程可以取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品，请用信号量
求写出完整的过程；并指出所用信号量的含义和初值
【答案】设置5个信号量
empty :表示缓冲区是否为空，初值为1000
full ： 表示缓冲区是否为满，初值为0
mutex 1：生产者之间的互斥信号，初值为1
mutex2：消费者之间的互斥信号，初值为1
available :当前消费者能否访问缓冲区，初值为1
定义变量in , out 分别为生产者和消费者进程所要使用的指针，指向下一个可用的缓冲区单元，MaXNum= 1000 为缓冲区的大小，count 标志当前消费者已经取的产品的数量，初值为0
生产者进程：
第 2 页，共 24 页 操作实现进程间的互斥和同步，要
生产一个产品；
产品送入buffer （in ）;
消费者进程
取出产品buffer （out ）;
3． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求
真子串？且为最大真子串？
【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有为了不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。
4． 如果输入序列为123456, 试问能否通过栈结构得到以下两个序列：435612和135426; 请说明为什么不能或如何才能得到。
【答案】输入序列为123456, 不能得出435612, 其理由是，输出序列最后两元素是12, 前面4个元素（4356）得到后，栈中元素剩12, 且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1; 然后2和3入找，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。
两头匹配的
第 3 页，共 24 页
5． 对一个有t 个非零元素的矩阵，用的数组来表示，其中第0行的三个元素分别为m ，n ，t ，从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作-确定任意一个元素
在B 中的位置并修改其值，应如何设计算法可以使时间得到改善？
【答案】题中矩阵非零元素用三元组表存储，查找某非零元素时，按常规要从第一个元素开始查找，属于顺序查找，
时间复杂度为若使查找时间得到改善，可以建立索引，将各行行号及各行第一个非零元素在数组B 中的位置（下标）放入一向量C 中。若查找非零元素，可先在数组C 中用折半查找到该非零元素的行号，并取出该行第一个非零元素在B 中的位置，再到B 中
顺序（或折半）查找该元素，这时时间复杂度为
6． 设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？
【答案】（1）首次适配法
从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。首次适配法适合事先不知道请求分配和释放信息的情况，分配时需查询，释放时插在表头。
（2）最佳适配法
链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。最佳适配法适用于请求分配内存大小范围较宽的系统，释放时容易产生存储量很小难以利用的内存碎片，同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。
（3）最差适配法
链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。最差适配法适合请求分配内存大小范围较窄的系统，分配时不查询，回收时查询，以便插入适当位置。
7． （1）判定起泡排序的结束条件是什么？
（2）请简单叙述希尔排序的基本思想。
（3）将下列序列调整成堆（堆顶为最小值）。
（4）在16个关键字中选出最小的关键字至少要进行多少次比较? 再选出次小的关键字至少要进行多少次比较? 请简要说明选择的方法和过程。
【答案】（1）至多进行n-1趟起泡排序，或一趟起泡排序中未发生交换（即已有序）时，结束排序。
（2）希尔排序是对直接插入排序算法的改进，它从“记录个数少”和“基本有序”出发，将
，从而减少参与直接插入排序的数据量，当经过几次分待排序的记录划分成几组（缩小增量分组）
组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。
（3）13，24，33，65，70，56，48，92，80，112
（4）采用树形锦标赛排序选出最小关键字至少要15次比较。再选出次小关键字比较4次（两
第 4 页，共 24 页