2017年哈尔滨工业大学数据结构之数据结构(C语言版)复试实战预测五套卷
● 摘要
一、应用题
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． 某文件系统空间的最大容量为4TB
以磁盘块为基本分配单位，磁盘块大小为1KB 。
文件控制块（FCB ）包含一个512B 的索引表区。请回答下列问题。
（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节? 可支持的单个文件最大长度是多少字节？
（2）假设索引表区采用如下结构：第0〜7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占6B ，块数占2B ; 剩余504字节采用直接索引结构，一个索引项占6B ，则可支持的单个文件最大长度是多少字节? 为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理 值并说明理由。
【答案】
（1）文件系统存储空间共有块数可存放
为表示
个块号，索引表项占
512B
个索引项，每个索引项对应一个磁盘块，故最大文件长度：
（2）
块号占6字节，块数占2字节的情形下，最大文件长度
：
理由：
合理的起始块号和块数所占字节数分别为
块数占4B 或以上，就可表示4TB 大小的文件长度，达到文件系统的空间上限。
3． （1）对于有向无环图，叙述求拓扑有序序列的步骤；
（2）对于图1，写出它的四个不同的拓扑有序序列。
图1
【答案】（1）对有向图，求拓扑序列步骤为：
1）在有向图中选一个没有前驱（即入度为0）的顶点并输出。 2）在图中删除该顶点及所有以它为尾的弧。
3）重复1）和2）, 直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。
（2）拓扑有序序列如图2:
图2 拓扑有序序列
4． KMP 算法（字符串匹配算法）较Brute （朴素的字符串匹配）算法有哪些改进？
【答案】朴素的模式匹配度达到
时，KMP 算法的优点更为突出。
时间复杂度是KMP 算法有一定改进，时间复杂
主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配
5． 一个ISAM 文件除了主索引外，还包括哪两级索引？
【答案】ISAM 文件有三级索引：磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引一主索引。故还包括的两级索引是盘组和磁道。
6． 设将n （n ＞l ）个整数存放到一维数组R 中。试设计一个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P （0＜P ＜n ）个位置，即将R 中的数据由
变换为
（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或
或JA V A 语言描述算法，关键之处给出注释。
原地逆置，
得到
（3）说明你所设计算法的时间复杂度和空间复杂度。 【答案】（1）算法的基本设计思想：先将n
个数据由然后再将数组R 中的前
，
（2）用C 语言算法描述如下：
（3）说明算法的复杂性：上述算法中3个Reverse 函数的的时间复杂度分别
为
为O
故算法的时间复杂度为
，算法的空间复杂度为0（1）。
（n 为正整数）。现要求
7． 用单链表保存m 个整数，节点的结构为（data , link ）, 且点而删除其余绝对值相等的节点。
例如若给定的单链表head 如下
个数和后P 个数分别原地逆置，
最终得到结果
要求：
设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节