2017年新疆大学数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。
【答案】此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。
第一趟：12，23，35，16，25，36， 19，21，16， 47
第二趟：12，16，23，35，16，25，36， 19，21，47
第三趟：12，16，23，16，25，35， 19，21，36， 47
第四趟：12， 16， 16，23， 19， 25， 35， 21， 36，47
第五趟：12，16，16，19，23，25，21，35， 36， 47
第六趟：12，16，16，19，21， 23，25，35， 36， 47
第七趟：12，16，16，19，21，23，25，35， 36， 47
2． 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，则它的中序前驱结点没有右孩子。
【答案】根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点：叶结点或仅有右子树的结点；而其中序前驱是其左子树上按中序遍历的最后个结点：叶结点或仅有左子树的结点。命题得证。
3． 试比较顺序文件、索引非顺序文件、索引顺序文件、哈希文件的存储代价，检索、插入、删除记录时的优点和缺点。
【答案】（1）顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺序文件不能像顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”，只能通过复制整个文件实现上述操作。
（2）索引非顺序文件适合随机存取，不适合顺序存取，因主关键字未排序，若顺序存取会引起磁头频繁移动。索引顺序文件是最常用的文件组织，因主文件有序，既可顺序存取也可随机存取。索引非顺序文件是稠密索引，可以“预查找”，索引顺序文件是稀疏索引，不能“预查找”，但由于索引占空间较少，管理要求低，提高了索引的查找速度。
（3）散列文件也称直接存取文件，根据关键字的哈希函数值和处理冲突的方法，将记录散列到外存上。这种文件组织只适用于像磁盘那样的直接存取设备，其优点是文件随机存放，记录不必排序，插入、删除方便，存取速度快，无需索引区，节省存储空间。缺点是散列文件不能顺序存取，且只限于简单查询。经多次插入、删除后，文件结构不合理，需重组文件，这很费时。
4． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求两头匹配的真子串？且为最大真子串？
【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有为了不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。
5． 在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？
【答案】不一定相邻。哈希地址为的关键字，和为解决冲突形成的探测序列f 的同义词，都争夺哈希地址i 。
6． 将关键字序列（7, 8, 30，11，18, 9，14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组。散列函数是：
列法，要求装填（载）因子为0.7。
（1）请画出所构造的散列表。
（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。
【答案】（1）要求装填因子为0.7, 数组的长度应该为7/0.7=10, 数组下标为0〜9。各关键字的散列函数值如下表：
采用线性探测法再散列法处理冲突，所构造的散列表为：
（2）查找成功时，在等概率情况下，查找表中每个元素的概率是相等的，因此是根据表中元素个数来计算平均查找长度，各关键字的比较次数如下表所示： 处理冲突采用线性探测再散
故查找成功的平均查找长度为（1+1+1+1+3+3+2）/7=12/7。
在不成功的情况下，由于任意关键字key , H （key ）的值只能是0〜6之间，H （key ）为0需要比较3次，H （key ）为1需要比较2次，H （key ）为2需要比较1次，H （key ）为3需要比较2次，H （key ）为4需要比较1次，H （key ）为5需要比较5次，H （key ）为6需要比较4次，共7种情况，如下表所示：
所以，在等概率下，查找失败的平均查找长度为：（3+2+1+2+1+5+4）/7=18/7。
7． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？
【答案】（1）动态存储分配伙伴系统的基本思想
在伙伴系统中，无论占用块或空闲块，其大小均为（k 为大于等于0的正整数）。若内存容
量为
则空闲块大小只能是由同一大块分裂而得的两个小块互称“伙伴空
（若）
，
如内存大小为
间”
或的块分裂成两个大小为的块。只有两个“伙伴空间”才能合并成一个大（若
（2）和边界标识法的不同
边界标识法在每块的首尾均有“占用”/“空闲”标志，空闲块合并方便。伙伴系统算法简单、速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。
8． 对下面的关键字集若查找表的装填因子为0.8，采用线性探测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。
【答案】（1）由于装填因子为0.8，关键字有8个，所以表长为
哈希函数，哈希函数为
（2）哈希表如表所示：
表 哈希表
（3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，
当其哈希地址为时的查找次数。本例中
（4）算法如下：
空间。起始地址为P ，
大小为的内存块，其伙伴的起始地址为：）。 用除留余数法设计 故查找失败和查找成功时的平均查找长度分别为：
相关内容
相关标签