2018年北京市培养单位光电研究院866计算机原理之数据结构考研强化五套模拟题
● 摘要
目录
2018年北京市培养单位光电研究院866计算机原理之数据结构考研强化五套模拟题（一） ... 2 2018年北京市培养单位光电研究院866计算机原理之数据结构考研强化五套模拟题（二） . 14 2018年北京市培养单位光电研究院866计算机原理之数据结构考研强化五套模拟题（三） . 24 2018年北京市培养单位光电研究院866计算机原理之数据结构考研强化五套模拟题（四） . 37 2018年北京市培养单位光电研究院866计算机原理之数据结构考研强化五套模拟题（五） . 48
一、填空题
1． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。
【答案】n －1
【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。
2． 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH ，中序序列是FEBGCHD ，则它的后序序列是_____。设上述二叉树是由某棵树转换而成，则该树的前序序列是_____
【答案】FEGHDCB ；BEF
【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF 。
3． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】
4． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
(1)若是边，则的值等于_____，若不是边，则A(i, j) 的值是一个比任何
置边的权_____，矩阵的对角线元素全为0。 (2)构造最小生成树过程中，若顶点已包括进生成树，就把相邻矩阵的对角线元素
成_____，若
【答案】(1)已包括进生成树，就把矩阵元素置成_____。 (3)算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。 边上的权值；都大的数；(2)1; 负值；(3)为负；边
5． 设二维数组A 的行和列的下标范围分别为[0:8]和[0:10]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为b+50处的元素为_____。
【答案】A[2][3]
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是(ll*i＋j ＋l ﹣l)*2＋b 。当其值为b ＋50时，则i ＝2，j ＝3。
6．
给定一组数据
WPL 的值为_____。
【答案】5；96 以它构造一棵哈夫曼树，则树高为_____，带权路径长度
【解析】每次找两个最小的权值构建哈夫曼树:
7． 从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ; ；2；k
8． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。
【答案】（ ）；(（ ）) ；2；2
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
9． 设有一个空枝，栈顶指针为1000H(十六进制) ，现有输入序列为1，2，3，4，5，经过PUSH ，PUSH ，POP ，PUSH ，POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序找，每个元素占4个字节。
【答案】23；100CH
10．设数组
址为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为2000＋((i﹣l)*80＋j ﹣
1) 2。若以列序为主存储顺序，则它的存储地址为2000＋((j﹣l)*50＋i ﹣l)*2。
的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为_____；若以列序为主序顺序存储，则元素a[45，68]的存储地
二、判断题
11．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
【答案】√
【解析】堆排序:基本思想先将原始序列构造成一个堆(初始堆) ，使其n 个元素的最大(小) 值处于序列的第 —个位置；然后交换序列第一个元素与最后一个元素的位置。
12．在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。（ ）
【答案】×
【解析】伙伴系统的伙伴不一定是位置相邻的内存块。
起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:
只要符合公式的内存块都是伙伴。
13． 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ）
【答案】 ×
【解析】队列是一种先入先出型结构，而找才是先进后出的线性结构。
14．—个排序算法是否稳定，是指该算法在各种情况下的时间效率是否相差不大。（ ）
【答案】×
【解析】排序的稳定性指:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序， 这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri 在rj 之前，而在排序后的序列中，ri 仍在ij 之前，则 称这种排序算法是稳定的；否则称为不稳定的。
15．外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（ ）
【答案】×
【解析】外部排序方法:按可用内存大小，将外存上含n 个记录的文件分成若干长度为2的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串(run)。对这些归并段进行逐趟归并，使归并段(有序的子文件) 逐渐由小至大，直至得到整个有序文件为止。一般情况下，外部排序所需总的时间=内部排序(产生初始归并段) 所需的时间m*tIS+外存信息读写的时间内部归并所需的时间。
16．广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ）
【答案】 ×
【解析】广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。