2018年武汉轻工大学数学与计算机学院810数据结构考研核心题库-一、填空题1 无用单元是指_，例_【答案】用户不再使用而系统没有回收的结构和变量； 2 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_和_；若只设尾指针，则出队和入队的时间复杂度分别是_和_。【答案】O(1)；O(n)；O(1)；O(1)【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。 3 阅读下列程序，指出其功能，并写出空格处应填上的语句。 【答案】 【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。4 阅读下列程序说明和程序，填充程序中的_。【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。 本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:(1)把根结点放入堆栈。(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。(3)重复(2)直到堆栈为空时为止。 【答案】 【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。 5 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_的排序方法。【答案】稳定 6 外排序的基本操作过程是_和_。【答案】生成有序归并段(顺串) ；归并 7 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。【答案】顺序【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。 8 数组的存储结构采用_存储方式。【答案】顺序存储结构【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。9 设有N 个结点的完全二叉树顺序存放在向量 中，其下标值最大的分支结点为_。【答案】 【解析】最大的分支结点是最后一个叶子结点的父结点。 10索引顺序文件既可以顺序存取，也可以 _存取。【答案】随机 11对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。 :_: _) (_、:_；_；p u ； 【答案】(1)Lnext NULL /置空链表，然后将原链表结点逐个插入到有序表中 (2)p!NULL /当链表尚未到尾，p 为工作指针(3)q!NULL /查P 结点在链表中的插入位置，这时q 是工作指针 (4)pnext r next /将P 结点链入链表中(5)rnext p /r是q 的前驱，u 是下个待插入结点的指针 12有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_。(3在4之前出栈)【答案】3个【解析】以3，4先出栈的序列有34521、34215、34251共3个。 二、单项选择题13希尔排序的组内排序采用的是（ ）。A. 直接插入排序 B. 折半插入排序 C. 快速排序 D. 归并排序 【答案】A【解析】希尔排序基本思想是:先将整个待排元素序列按某个增量分割成若干个子序列, 在子序列内进行直接插入排序, 然后依次缩减增量再进行排序, 待整个序列中的元素基本有序(增量足够小) 时, 再对全体元素进行一次直接插入排序。 -一、填空题-考研试题-