2017年东北林业大学数据结构与高级语言程序设计之数据结构复试仿真模拟三套题
● 摘要
目录
2017年东北林业大学数据结构与高级语言程序设计之数据结构复试仿真模拟三套题（一） . .... 2
2017年东北林业大学数据结构与高级语言程序设计之数据结构复试仿真模拟三套题（二） . .... 8
2017年东北林业大学数据结构与高级语言程序设计之数据结构复试仿真模拟三套题（三） . .. 17
一、应用题
1． 在堆排序、快速排序和合并排序中：
（1）若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？
（2）若只从排序结果的稳定性考虑，则应选取哪种排序方法？
（3）若只从平均情况下排序最快考虑，则应选取哪种排序方法？
（4）若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？
【答案】（1）应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法。 （2）应选取归并排序方法
（3）应选取快速排序方法
（4）应选取堆排序方法
2． 已知世界六大城市为：北京（Pe ）、纽约（N ）、巴黎（Pa ）、伦敦（L ）、东京（T ）、墨西哥
，下表给定了这六 大城市之间的交通里程：
（M ）
（1）画出这六大城市的交通网络图；
（2）画出该图的邻接表表示法；
（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。
【答案】（1）这六大城市的交通网络图如图1所示：
图1
（2）该图的邻接表表示法如图2所示：
图2
（3）最小生成树有6个顶点与条边：V （G ）={Pe，N ，Pa ，L , T，M}
E （G ）=（ {（L , Pa, 3）, （Pe , T, 21）, （M , N, 32）, （L , N, 55）, （L , Pe, 81）}
3． 文件存储结构的基本形式有哪些? 一个文件采用何种存储结构应考虑哪些因素？
【答案】文件的基本组织方式有顺序组织、索引组织、散列组织和链组织，常用的结构有顺序结构、索引结构、散列结构。
（1）顺序结构，相应文件为顺序文件，其记录按存入文件的先后次序顺序存放。顺序文传本质上就是顺序表。若逻辑上相邻的两个记录在存储位置上相邻，则为连续文件；若记录之间以指针相链接，则称为串联文件。顺序文件只能顺序存取，要更新某个记录，必须复制整个文件。顺序文件连续存取的速度快，主要适用于顺序存取，批量修改的情况。
（2）带索引的结构，相应文件为索引文件。索引文件包括索引表和数据表，索引表中的索引项包括数据表中数据的关键字和相应地址，索引表有序，其物理顺序体现了文件的逻辑次序，实现了文件的线性结构。索引文件只能是磁盘文件，既能顺序存取，又能随机存取。
（3）散列结构，也称计算寻址结构，相应文件称为散列文件，其记录是根据关键字值经哈希函数计算确定其地址，存取速度快，不需索引，节省存储空间。不能顺序存取，只能随机存取。
文件采用何种存储结构应综合考虑各种因素，如：存储介质类型、记录的类型、大小和关键字的数目以及对文件作何种操作。
4． 证明：置换选择排序法产生的初始归并段的长度至少为m （m 是所用缓冲区的长度）。
【答案】证明：由置换选择排序思想，第一个归并段中第一个元素是缓冲区中最小的元素，
，缓以后每选一个元素都不应小于前一个选出的元素，故当产生第一个归并段时（即初始归并段）
冲区中m 个元素中除最小元素之外，其他m-1个元素均大于第一个选出的元素，即当以后读入元素均小于输出元素时，初始归并段中也至少能有原有的m 个元素。证毕。
5． 设依以下次序给出关键字：34，16，19，21，5，49，24，62，3，17，45，8，构造3阶树。要求从空树开始，每插入一个关键字，画出一棵树。
【答案】如图所示：
图
6． KMP 算法（字符串匹配算法）较Brute （朴素的字符串匹配）算法有哪些改进？
【答案】朴素的模式匹配度达到时间复杂度是KMP 算法有一定改进，时间复杂
主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP 算法的优点更为突出。
7． 如果只要找出一个具有n 个元素的集合的第
种最适合? 给出实现的思想。
【答案】在具有n 个元素的集合中找第个最小元素，你所学过的排序方法中哪个最小元素，应使用快速排序方法。其基本思想如下：设n 个元素的集合用一维数组表示，其第一个元素的下标为1，最后一个元素下标为n 。以第一个元素为“枢轴”，经过快速排序的一次划分，找到“枢轴”的位置i ，若i=k，则该位置的元素即为所求；若
素。
则在1至i-1间继续进行快速排序的划分；若则在i+1至n 间继续进个最小元行快速排序的划分。这种划分一直进行到i=k为止，第i 位置上的元素就是第