当前位置:问答库>考研试题

2018年北京理工大学软件学院885软件工程专业基础综合之数据结构考研仿真模拟五套题

  摘要

一、填空题

1. 对单链表中元素按插入方法排序的C 语言描述算法如下,其中L 为链表头结点指针。请填充算法中标出的空白处,完成其功能。

:_____:

{_____)

(_____、

:_____;_____;p =u ;

【答案】(1)L﹣>next =NULL //置空链表,然后将原链表结点逐个插入到有序表中

(2)p!=NULL //当链表尚未到尾,p 为工作指针

(3)q!=NULL //查P 结点在链表中的插入位置,这时q 是工作指针

(4)p﹣>next =r ﹣>next //将P 结点链入链表中

(5)r﹣>next =p //r是q 的前驱,u 是下个待插入结点的指针

2. 在基于关键字比较且时间为

【答案】归并;堆

3. 文件可按其记录的类型不同而分成两类,即 _____和_____文件。

【答案】操作系统文件;数据库

4. 在一个具有n 个单元的顺序栈中,假定以地址高端(即下标为n 的单元) 作为栈底,以top 作为栈顶指针,则当向栈中压入一个元素时,top 的变化是top =_____。

【答案】top ﹣1

【解析】由于栈底在地址高端,栈中压入一个元素时,栈顶向地址底端移动一个单位,所以top ﹣1。

_ 的排序中,若要求排序是稳定的,则可选用_____排序;若要求就地排序(及辅助空间为O(1)),则可选用_____排序。

5. 二进制地址为011011110000, 大小为【答案】011011110100;011011100000 和块的伙伴地址分别为:_____

和其伙伴块的起始地址计【解析】011011110000是块的起始地址,大小分别为算公式如下:

当大小为4时,起始地址为011011110000+0100。当大小为16时,起始地址为:011011110000-010000。

二、单项选择题

6. 某二叉树结点的中序序列为BDAECF ,后序序列为DBEFCA ,则该二叉树对应的森林包括( )棵树。

A.1

B.2

C.3

D.4

【答案】C

【解析】由两序列可知,A 为根节点,ECF 为右子树,C 为右子树的根,F 为C 的右孩子。再由二叉树和森林的对应关系可知该二叉树对应的森林包括3棵树。根据中序序列和后序序列画出二叉树,根据二叉树得出对应的森林包含的树的棵数。

7. 已知三叉树T 中6个叶结点的权分别是2, 3, 4, 5, 6, 7, T 的带权(外部) 路径长度最小是 ( )

A.27

B.46

C.54

D.56

【答案】B

【解析】利用三叉树的6个叶子结点的权构建最小带权生成树, 最小的带权路径长度为

8. 可以用( )定义一个完整的数据结构。

A. 数据元素

B. 数据对象

C. 数据关系

D 抽象数据类型

【答案】D

【解析】抽象数据类型可以定义一个完整的数据结构。包括数据元素,数据元素之间的关系,以及可以进行的操作。

9. 若某文件系统索引结点(inode)中有直接地址项和间接地址项, 则下列选项中, 与单个文件长度无关的因素是( )

A. 索引结点的总数

B. 间接地址索引的级数

C. 地址项的个数

D. 文件块大小

【答案】A

【解析】根据文件长度与索引结构的关系可知, 只有选项A 是与单个文件长度无关的。

10.若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是( ).

A.. 起泡排序

B. 插入排序

C. 选择排序

D. 二路归并排序

【答案】B

【解析】经过两趟排序后,A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置;B 项插入排序的结果是前三个数有序即可;C 项选择排序结果是两个最小的元素在最前面按顺序排好;D 项二路归并排序的结果是长度为4的子序列有序,即前4个数排好序,接下来的4个数排好序. 显然题目中的元素序列只能是插入排序第二趟排序后的结果,因此,B 项正确.

11.下列四个序列中,哪一个是堆( )?

A.75,65,30,15,25,45,20,10

B.75,65,45,10,30,25,20,15

C.75,45,65,30,15,25,20,10

D.75,45,65,10,25,30,20,15

【答案】C

【解析】堆的定义:

n 个关键字序列

①②且且 称为堆,当且仅当该序列满足如下性质(简称为堆性质) : 小根堆:满足第①种情况的堆;

大根堆:满足第②种情况的堆。

根据堆定义即可得出答案。