2017年北京市培养单位空间应用工程与技术中心863计算机学科综合(专业)之数据结构考研强化模拟题
● 摘要
一、填空题
1． 对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。
【答案】n （n-1）/2
【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。
2． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。 【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
3． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____（表示为n 的函数）。
【答案】1＋（1＋2）＋（1＋2＋3）＋"•＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6，即
【解析】当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次。
4． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。 【答案】
5． 在循环队列中，队列长度为n ，存储位置从0到，
【答案】 编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是（ ）。
6． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
7．
求REPLACE （S ，V , m ）=_____。 已
知
【答案】
8． 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。 【答案】
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，
所以
9． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
10．对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
二、判断题
11．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ ） 【答案】
【解析】对于链式存储，数据元素之间的存储地址不一定是相邻的，即结点的存储空间可以是不连续的。而结点内部的存储空间需要是连续的，因为它是一个完整的数据。
12．数据结构的抽象操作的定义与具体实现有关。（ ） 【答案】
【解析】数据结构的抽象操作定义取决于客观存在的一组逻辑特性，与其在计算机内具体表示和实现无关。
13．在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。（ ）
【答案】×
【解析】伙伴系统的伙伴不一定是位置相邻的内存块。
起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
只要符合公式的内存块都是伙伴。
14．数据元素是数据的最小单位。（ ） 【答案】
【解析】数据项是数据的不可分割的最小单位，而数据元素是数据的基本单位。
15．设栈采用顺序存储结构。若已有个元素入栈，则将第i 个元素入栈时，入栈算法的时间复杂性为（ ） 【答案】
【解析】由于该栈采用顺序存储结构，时间复杂度应该为0（1）。
16．二叉树中序线索化后，不存在空指针域。（ ）
【答案】×
【解析】非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。
17．归并排序辅助存储为
【答案】×
【解析】归并排序的辅助存储是
18．稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）
【答案】√
【解析】稀疏矩阵在压缩存储后，必回失去随机存储的功能。因为在这个矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。
19．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ） 【答案】
【解析】数据的逻辑结构是指数据元素之间的逻辑关系。
20．在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（ ） 【答案】
【解析】必须从头指针开始，查找到尾指针所指结点的前驱结点的指针。
（ ）
三、算法设计题
21．已知二叉树T ，试写出复制该二叉树的算法（t →T ）。
【答案】算法如下：
相关内容
相关标签