2017年武汉纺织大学数学与计算机学院848数据结构考研题库
● 摘要
一、填空题
1． 求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
2． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
3． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
4． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
5． 在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。
6． 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。
【答案】
【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。
7． 实现字符串拷贝的函数strcpy 为：
【答案】
.
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的
8． 关键码序列（Q ，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X ），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_____。
【答案】（Q ，A ，C ，S ，Q ，D ，F ，×，R ，H ，M ，Y ）; （F ，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X ）
【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
9． 在哈希函数
中，P 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
10．无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
二、算法设计题
11．给定
矩阵
并设
设计一算法判定x 的值是否在A 中，
要求时间复杂度为
【答案】算法如下：
12．设单链表的表头指针为h , 结点结构由data 和next 两个域构成，其中data 域为字符型。写出算法dc （h , n ）, 判断该链表的前n 个字符是否中心对称。例如xyx , xyyx 都是中心对称。
【答案】算法如下：
13．已知字符串
中存放一段英文，写出算法
其多余的字符送
将其按给定的长度n 格式化
成两端对齐的字符串
【答案】算法如下：
14．设线性表存于时间复杂度。
【答案】算法如下：
的前num 各分量中，且递增有序。请设计一个算法，将x 插入到线
性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的