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