当前位置：问答库＞考研试题

目录

2018年大连大学教育部先进设计与智能计算重点实验室836数据结构考研核心题库（一） ... 2 2018年大连大学教育部先进设计与智能计算重点实验室836数据结构考研核心题库（二） . 12 2018年大连大学教育部先进设计与智能计算重点实验室836数据结构考研核心题库（三） . 22 2018年大连大学教育部先进设计与智能计算重点实验室836数据结构考研核心题库（四） . 32 2018年大连大学教育部先进设计与智能计算重点实验室836数据结构考研核心题库（五） . 43

一、填空题

1． 属于不稳定排序的有_____。

【答案】希尔排序、简单选择排序、快速排序、堆排序等

2． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。 【答案】

【解析】无向完全图中任意一个顶点都和其他n －1个顶点都有一条边，即为n(n－1) 。又因

. 。 为每条边重复出现两次，所有无向完全图的边数为

3． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，

2而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。

4． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。

【答案】O(m＋n)

5． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录的_____。

【答案】比较；移动

6． 完善算法:求KMP 算法.next 数组。

k :＝_____；next[1]:＝0；

k :＝_____；

END ；

【答案】0；next[k]

7． 关键码序列(Q，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X) ，要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_____。

【答案】(Q，A ，C ，S ，Q ，D ，F ，X ，R ，H ，M ，Y) ; (F，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X)

【解析】希尔排序的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

快速排序(quick sort) 的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

8． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度____；深度优先遍历图的时间复杂度_____，两者不同之处在于_____，反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈

【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

9． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____；而又根据指针的连接方式，链表又可分成_____和_____。

【答案】单链表；双链表；(动态) 链表；静态链表

【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。

10． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ，则a 85的地址为_____。

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则

＝i(i﹣l)/2＋j 。若i ＜j 。则

的地址为l ＋2＋... ＋i ﹣l ＋j 的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。

二、算法设计题

11．设键盘输入n 个英语单词，输入格式为

词个数，试编一程序，建立一个单向链表，实现:

(1)如果单词重复出现，则只在链表上保留一个。

(2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k＜＝n) 个单词。

【答案】定义结点数据类型如下:

其中n 表示随后输入英语单

//频度域，记单词出现的次数

//maxsize是单词中可能含有的最多字母个数

(1)算法如下:

（ ）

//建立有n(n＞0) 个单词的单向链表，若单词重复出现，则只在链表中保留一个

//申请头结点

//链表初始化

//建立n 个结点的链表

//a是与链表中结点数据域同等长度的字符数组

//p是工作指针，pre 是前驱指针

//单词重复出现，频度增

1

//指针后移

//该单词没出现过，应插入

//将新结点插入到链表最后

//结束for 循环

//结束creat 算法

(2)算法如下:

（ ）

//建立有n 个单词的单向链表，重复单词只在链表中保留一个，最后输出频度最高的k 个单词

//申请头结点

//链表初始化

//建立n 个结点的链表

//a是与链表中结点数据域同等长度的字符数组

//P是工作指针，pre 是前驱指针

//单词重复出现，频度增

1

//先将P 结点从链表上摘下，再按频度域值插入到合适位置