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 个关键字序列
①②且且 称为堆,当且仅当该序列满足如下性质(简称为堆性质) : 小根堆:满足第①种情况的堆;
大根堆:满足第②种情况的堆。
根据堆定义即可得出答案。
相关内容
相关标签