2018年江西中医药大学经济与管理学院804法理学之数据结构考研基础五套测试题
● 摘要
目录
2018年江西中医药大学经济与管理学院804法理学之数据结构考研基础五套测试题（一） ... 2 2018年江西中医药大学经济与管理学院804法理学之数据结构考研基础五套测试题（二） . 11 2018年江西中医药大学经济与管理学院804法理学之数据结构考研基础五套测试题（三） . 19 2018年江西中医药大学经济与管理学院804法理学之数据结构考研基础五套测试题（四） . 28 2018年江西中医药大学经济与管理学院804法理学之数据结构考研基础五套测试题（五） . 38
第 1 页，共 46 页
一、填空题
1． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。
【答案】15
2n
【解析】当时，100n2>2n，而，时，100n ＜2
2． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
3． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
a 中存放待排序的关键字
第 2 页，共 46 页
【答案】
【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
4． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【答案】if(top!＝n)data[++top]＝x ；
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
5． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____ (表示为n 的函数) 。
【答案】1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋…＋n) ＝n(n＋1)(n＋2)/6，即O(n)
【解析】当i ＝l 时，赋值语句就被执行了一次。当i ＝2时，赋值语句被执行了1＋2次。当i ＝3时，赋值语句被执行了1＋2＋3次。...... 可以推出赋值语句总共被执行了1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋... ＋n) ＝n(n＋1)(n＋2)/6次。
6． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为。
7． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k ＝_____。(注:矩阵元素下标从1开始)
【答案】93
【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。
8． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。
【答案】
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N－1) 个非零元素。
在B
第 3 页，共 46 页
9． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
10．以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
h 为附加头结点指针
(_____)
_____；
【答案】(1)p!＝NULL //链表未到尾就一直进行 (2)q //将当前结点作为头结点后的第一元素结点插入
二、判断题
11．为了很方便的插入和删除数据，可以使用双向链表存放数据。（ ）
【答案】 √
【解析】链式存储结构便于数据的插入和删除，但只能顺序访问表中的元素。
12．如果完全二叉树从根结点开始按层次遍历的输序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。（ ）
【答案】×
【解析】不是，2，3作为1的左右孩子，由于左节点2比1大，所以不具有二叉排序树的性质。
13．有n 个数顺序(依次) 入栈，出栈序列有Cn 种，
【答案】 √
14．2，n ，a 2，a n
若…，…，桟的输入序列是1，输出序列是a 1，（ ）
【答案】 ×
【解析】出找序列不一定满足a 1＞a i+1... ＞a n ，比如1进栈，然后出找，a 1＝1。
15．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）
【答案】 √
【解析】二叉排序树是的父结点和左右子树的值的大小是确定的。
第 4 页，共 46 页
（ ）
则有:。
。
相关内容
相关标签