2017年重庆工商大学数据结构(C语言)复试仿真模拟三套题
● 摘要
一、应用题
1． 在各种排序方法中，哪些是稳定的? 哪些是不稳定的? 并为每一种不稳定的排序方法举出一个不稳定的实例。
【答案】各种排序算法稳定性的归纳如图所示：
图
2． 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。
【答案】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O （n ）; 而在链式存储方式下，插入和删除时间复杂度都是0（1）。
3． 某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描
，本轮没有被访问过的页框将被系统回收，并放入到空闲页框链一轮驻留集（扫描时间忽略不计）
尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程
（1）访问
（2）访问
（3）访问
【答案】
（1）页框号为21。因为起始驻留集为空，而0页对应的页框为空闲链表中的第三个空闲页
第 2 页，共 22 页 P 依次访问的<虚拟页号，访问时刻>是
：请回答下列问题。 时，对应的页框号是什么？ 时，对应的页框号是什么? 说明理由。 . 时，对应的页框号是什么? 说明理由。 （4）该策略是否适合于时间局部性好的程序? 说明理由。
框，其对应的页框号为21。
（2）页框号为32。理由：因11>10故发生第三轮扫描，页号为1、3的页框32、15在第二轮已处于空闲页框链表中，此刻1页又被重新访问，因此应被重新放回到驻留集中。其页框号为32。
（3）页框号为41。理由：因为第2页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41，页框号为41。
（4）适合。理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。
4． 为什么在倒排文件组织中，实际记录中的关键字域可删除以节约空间? 而在多重表结构中这样做为什么要牺牲性能？
【答案】因倒排文件组织中，倒排表有关键字值及同一关键字值的记录的所有物理记录号，可方便地查询具有同一关键字值的所有记录；而多重表文件中次关键字索引结构不同，删除关键字域后查询性能受到影响。
5． 索引顺序存取方法（ISAM ）中，主文件已按关键字排序，为何还需要主关键字索引？
【答案】ISAM 是专为磁盘存取设计的文件组织方式。即使主文件关键字有序，但因磁盘是以盘组、柱面和磁道（盘面）三级地址存取的设备，因此通常对磁盘上的数据文件建立盘组、柱面和磁道（盘面）三级索引。在ISAM 文件上检索记录时，先从主索引（柱面索引的索引）找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到查到为止；反之，若找遍该磁道而未找到所查记录，则文件中无此记录。
6． 已知世界六大城市为：北京（Pe ）、纽约（N ）、巴黎（Pa ）、伦敦（L ）、东京（T ）、墨西哥
，下表给定了这六 大城市之间的交通里程：
（M ）
（1）画出这六大城市的交通网络图；
（2）画出该图的邻接表表示法；
（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。
【答案】（1）这六大城市的交通网络图如图1所示：
第 3 页，共 22 页
图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）}
7． 在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？
【答案】不一定相邻。哈希地址为的关键字，和为解决冲突形成的探测序列f 的同义词，都争夺哈希地址i 。
8． 设五个字符的编码分别为1，2，3，4，5，并设标识符依以下次序出现
：
要求用哈希（Hash ）方法将它们存入具有10个位置的表
中。
（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；
（2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。
【答案】（1）构造的哈希函数为：哈希函数（2）关键字在表中的位置如表所示：
表 关键字在表中的位置
（关键字各字符编码之和）
二、算法设计题
第 4 页，共 22 页