2018年合肥工业大学计算机与信息学院850计算机科学与技术学科专业基础综合之数据结构考研核心题库
● 摘要
一、填空题
1． 深度为H 的完全二叉树至少有_____个结点:至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】
2． 完善算法:求KMP 算法.next 数组。
k :＝_____；next[1]:＝0；
k :＝_____；
END ；
【答案】0；next[k]
3． 有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)
【答案】3个
【解析】以3，4先出栈的序列有34521、34215、34251共3个。
4． 表达式23＋((12*3﹣2)/4＋34，5/7) ＋108/9的后缀表达式是_____。 【答案】
5． 二进制地址为011011110000, 大小为【答案】011011110100；011011100000
【解析】011011110000是块的起始地址，大小分别为算公式如下:
当大小为4时，起始地址为011011110000+0100。当大小为16时，起始地址为:011011110000-010000。
(表达式中的点(.)是数分隔符，如和块的伙伴地址分别为:_____ 和是三个数) 其伙伴块的起始地址计
6． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增
量序列) 依次是4， 2， 1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; (10，7，-9，0，47，23，1，8，98，36)
7． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，
2而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。
8． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构(网状结构)
9． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
10．如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】
序查找效率一样为
。 【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺二、判断题
11．深度为k 的二叉树中结点总数小于等于2k ﹣l 。（ ）
【答案】 √
【解析】深度为K 的二叉树，当结点数最多时为满二叉树，此时结点数为2k ﹣l 。
12．树形结构中元素之间存在一对多的关系。（ ）
【答案】√
【解析】树形结构是非线性结构，存在一对多的关系。
13．程序一定是算法。（ ）
【答案】 ×
【解析】一个程序不一定满足有穷性。而算法是对问题的解，用程序设计语言来实现来描述，
这时算法就是一个程序。
14．基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。（ ）
【答案】×
【解析】如果用字符串为关键字，可以将其中的字符串的每一位用Ascn 码进行比较。
15．即使有向无环图的拓扑序列唯一，也不能唯一确定该图。（ ）
【答案】×
【解析】如果有向无环图的拓扑序列唯一，则能够确定每个结点的唯一前驱和后继，因此能够确定该图。
16．在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。（ ）
【答案】×
【解析】伙伴系统的伙伴不一定是位置相邻的内存块。
起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:
只要符合公式的内存块都是伙伴。
17．静态链表就是一直不发生变化的链表。（ ）
【答案】 ×
【解析】用数组描述的链表，即称为静态链表。仍具有链式存储结构的主要优点。不是指不发生变化的的链表。
18．若一个有向图无环，则它一定有唯一的拓扑序列。（ ）
【答案】×
【解析】有向图无环说明它一定有拓扑序列，但这个拓扑序列不唯一。如果在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，在做拓扑排序时，则排序的结果是唯一的，即它有唯一的拓扑序列。
19．对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ ）
【答案】 √
【解析】可以有长度无穷大的广义表，只是在计算机中不能实现。
20．KMP 算法的特点是在模式匹配时指示主串的指针不会变小。（ ）
【答案】 √
【解析】KMP 算法是一种字符串匹配的算法，KMP 算法的关键是利用匹配失败后的信息，