2017年伊犁师范学院数据结构(同等学力加试)复试仿真模拟三套题
● 摘要
一、应用题
1． 设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？
【答案】（1）首次适配法
从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。首次适配法适合事先不知道请求分配和释放信息的情况，分配时需查询，释放时插在表头。
（2）最佳适配法
链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。最佳适配法适用于请求分配内存大小范围较宽的系统，释放时容易产生存储量很小难以利用的内存碎片，同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。
（3）最差适配法
链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。最差适配法适合请求分配内存大小范围较窄的系统，分配时不查询，回收时查询，以便插入适当位置。
2． 某文件系统空间的最大容量为4TB
以磁盘块为基本分配单位，磁盘块大小为1KB 。
文件控制块（FCB ）包含一个512B 的索引表区。请回答下列问题。
（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节? 可支持的单个文件最大长度是多少字节？
（2）假设索引表区采用如下结构：第0〜7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占6B ，块数占2B ; 剩余504字节采用直接索引结构，一个索引项占6B ，则可支持的单个文件最大长度是多少字节? 为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理 值并说明理由。
【答案】
（1）文件系统存储空间共有块数可存放
（2）
为表示
个块号，索引表项占
512B
个索引项，每个索引项对应一个磁盘块，故最大文件长度：
块号占6字节，块数占2字节的情形下，最大文件长度
：
理由：
合理的起始块号和块数所占字节数分别为
块数占4B 或以上，就可表示4TB 大小的文件长度，达到文件系统的空间上限。
3． S 是字符数组
，中存放的是该字符串的有效长度，
假设中字符串的内容为
说明下列程序的功能及执行结果。
【答案】本程序的功能是求字符串的nextval 函数，程序执行结果是0110132。
4． 将算术表达式（（a+b）+c*（d+e）+f）*（g+h）转化为二叉树。
【答案】该算术表达式转化的二叉树如图所示。
图
5． 在某程序中，有两个栈共享一个一维数组空间的栈底。
（1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。 （2）对栈1、栈2, 试分别写出栈满、栈空的条件。 【答案】（1）入栈主要语句
出栈主要语句
分别是两个栈
（2）
6． 对一个有t 个非零元素的矩阵，用的数组来表示，其中第0行的三个元素分
别为m ，n ，t ，从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作-确定任意一个元素
在B 中的位置并修改其值，应如何设计算法可以使时间得到改善？
【答案】题中矩阵非零元素用三元组表存储，查找某非零元素时，按常规要从第一个元素开始查找，属于顺序查找，
时间复杂度为
若使查找时间得到改善，可以建立索引，将各行行
号及各行第一个非零元素在数组B 中的位置（下标）放入一向量C 中。若查找非零元素，可先在数组C 中用折半查找到该非零元素的行号，并取出该行第一个非零元素在B 中的位置，再到B 中顺序（或折半）查找该元素，这时时间复杂度为
7．
设与记录
对应的关键字分别是
成立，试证明经过一趟起泡后，一定有记录与值。由题假设知中包括
在
之前且
则
即说明
和
如果存在
进行交换。
之前全部记录
（其
的关键字一定和
使得
且
【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极
是反序；设对于
）中关键字最大为
，故经过起泡排序前i-2次比较后，
为又因故和Rf 为反序，由此可知和必定交换，证毕。
8． 在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？
【答案】不一定相邻。哈希地址为同义词，都争夺哈希地址i 。
的关键字，和为解决冲突形成的探测序列f 的
二、算法设计题
9． 给定
矩阵
并设
设计一算法判定x 的值是否在A 中，
要求时间复杂度为
【答案】算法如下：