2017年北京市培养单位信息工程研究所863计算机学科综合(专业)之数据结构考研冲刺密押题
● 摘要
一、填空题
1． 索引顺序文件既可以顺序存取，也可以_____存取。
【答案】随机
2． 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。
【答案】23; 100CH 3
．
求REPLACE （S ，V , m ）=_____。
【答案】
4． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
第 2 页，共 56 页
已
知
【答案】
【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
5． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
6． 串是一种特殊的线性表，其特殊性表现在_____; 串的两种最基本的存储方式是_____、_____; 两个串相等的充分必要条件是_____。
【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等
7． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）
【答案】3个
【解析】以3, 4先出栈的序列有34521、34215、34251共3个。
8． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若
则
则的地址为
若
的地址为将代入得33。
9． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
10．设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素为_____。
【答案】9174；8788
第 3 页，共 56 页
，）则 的地址为_____。
的存储地址为_____；若以列序为主序顺序存储，则元素的存储地址
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，
则它的存储地址为
若以列序为主存储顺序，则它的存储地址为
二、判断题
11．设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为
【答案】
【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操 作的时间复杂度是
12．快速排序和归并排序在最坏情况下的比较次数都是
【答案】×
【解析】快速排序最坏的情况下比较次数是
13．内排序要求数据一定要以顺序方式存储。（ ）
【答案】×
【解析】由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序；另一类是外部排序。因此，内部排序没有要求数据一定是以顺序方式存储。
14．栈和队列都是限制存取点的线性结构。（ ）
【答案】
15．数据结构的抽象操作的定义与具体实现有关。（ ）
【答案】
【解析】数据结构的抽象操作定义取决于客观存在的一组逻辑特性，与其在计算机内具体表示和实现无关。
16．在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易増加闲置空间的碎片。
（ ） 【答案】√
【解析】最佳适配法：将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户；最先适配法：从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户；从适配法选择上可以看出最佳适配法会增加闲置空间。
17． 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）
【答案】×
第 4 页，共 56 页
（ ）。
（ ）