2017年南京理工大学计算机科学与工程学院877计算机专业基础C之数据结构考研冲刺密押题
● 摘要
一、填空题
1． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
已
．
求REPLACE （S ，V , m ）=_____。
【答案】
3．
给定一组数据
的值为_____。 【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树：
以它构造一棵哈夫曼树，则树高为_____，
带权路径长度
2知
4． 在单链表中设置头结点的作用是_____。
【答案】方便运算
5． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】
6． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
【答案】
【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
7．
【答案】5
8． —个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
9． 设二维数组A 的行和列的下标范围分别为
【答案】
当其值为
和
每个元素占2个单元，按行优先顺处的元素为_____。
=_____
序存储，第一个元素的存储起始位置为b ，则存储位置为
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是时，则i=2，j=3。
10．在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。
11．属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
12．从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m
阶个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；
树每个结点至多有_____个儿子，除
根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____
二、选择题
13．对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。
A.
B.
C.
D. 【答案】C 。
【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间
为
其中n 为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为
即可得出正确答案。
共享三类资
源题表资源分配情况表
这些资源总数分别
为
其
中e 为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为
14．假设5个进
程
时刻的资源分配情况如题表所示，此时存在的一个安全序列是（ ）。