2017年三峡大学计算机与信息学院938数据结构[专业学位]考研导师圈点必考题汇编
● 摘要
目录
2017年三峡大学计算机与信息学院938数据结构[专业学位]考研导师圈点必考题汇编（一） . 2 2017年三峡大学计算机与信息学院938数据结构[专业学位]考研导师圈点必考题汇编（二） 11 2017年三峡大学计算机与信息学院938数据结构[专业学位]考研导师圈点必考题汇编（三） 19 2017年三峡大学计算机与信息学院938数据结构[专业学位]考研导师圈点必考题汇编（四） 29 2017年三峡大学计算机与信息学院938数据结构[专业学位]考研导师圈点必考题汇编（五） 39
一、填空题
1． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
2． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
3． 完善算法：求KMP 算法.next 数组。
END ；
【答案】
和
每个元素占2个单元，按行优先顺处的元素为_____。
当其值为
4． 设二维数组A 的行和列的下标范围分别为
【答案】
序存储，第一个元素的存储起始位置为b ，则存储位置为
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是
时，则i=2，j=3。 5． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为
6． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
【答案】（1）（2）（3）（4）（5）
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
7． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
8． —个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
9． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
10．对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
二、选择题
11．设栈S 和队列Q 的初始状态为空，元素后即进队列Q ，若6个元素出队的序列是
A.6 B.4 C.3 D.2
【答案】C
A. 连续结构
依次通过栈S ，一个元素出栈 则栈S 的容量至少应该是（ ）。
12．下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）。
B. 索引结构
C. 链式结构且磁盘块定长 D. 链式结构且磁盘块变长 【答案】B
【解析】连续结构的优点是结构简单，缺点是不易于文件扩展，不易随机访问。链式结构的优点是文件易于扩展，缺点是不易随机访问。索引结构的优点是具有链式结构的优点并克服了它的缺点，可随机存取，易于文件扩展。
13．某二叉树结点的中序序列为BDAECF ，后序序列为DBEFCA ，则该二叉树对应的森林包括（ ）棵树。
A.1 B.2 C.3 D.4
【答案】C
【解析】由两序列可知，A 为根节点，ECF 为右子树，C 为右子树的根，F 为C 的右孩子。再由二叉树和森林的对应关系可知该二叉树对应的森林包括3棵树。根据中序序列和后序序列画出二叉树，根据二叉树得出对应的森林包含的树的棵数。
14．某计算机存储器按字节编址，主存地址空间大小为64MB ，现用4Mx8位的RAM 芯片组成32MB 的主 存储器，则存储器地址寄存器MAR 的位数至少是（ ）。
A.22 位 B.23 位 C.25 位 D.26 位 【答案】D
【解析】虽然实际的主存储器（RAM 区）只有32MB , 但不排除还有ROM 区，考虑到存储器扩展的需要， MAR 应保证能访问到整个主存地址空间。因为主存的地址空间大小为64MB , 所以MAR 的位数至少需要26位。
15．连续存储设计时，存储单元的地址（ ）。
A. 一定连续 B. 一定不连续 C. 不一定连续
D. 部分连续，部分不连续 【答案】A
【解析】连续存储是指数据的物理存储相连，即存储单元的地址是连续的。
相关内容
相关标签