计算机专业（基础综合）模拟试卷101

计算机专业（基础综合）模拟试卷101

一、单选题（本题共40题，每题1.0分，共40分。）

1、在n个结点的线性表的数组表示中，以下算法的时间复杂度是0（1）的操作是

（）oI.访问第i个结点（1V=iV=n）和求第i个结点的的直接前驱（2V=iV=n）

n.在最后一个结点后插入一个新的结点in.删除第一个结点w.在第i个结点

后插入一个结点（1<=i<=n）

A仅

、I

B仅

、口、①

c仅

、I、n

D仅

、I、n、m

标准答案：c

知识点解析：I：由于线性表是用数组表示，即顺序存储，可以直接通过结点编号

访问，所以I的时间复杂度一定是o（i）“n：由于是在最后一个结点处插入一个

结点，所以不需要移动元素，故时间复杂度为o（i）。n：删除第一个结点之后，

需要将后续所有结点往前移动，所以时间复杂度为08）。IV：由于i是不固定

的，所以后续结点i+l,i+2,n-l,都需要向后移动，所以时间复杂度为

O（n）o

2、中缀表达式a*（b+c）-d的后缀表达式是（）。

A^abcd*+-

B、abc+*d-

C、abc*+d-

D、-+*abcd

标准答案：B

知识点解析：本题转化过程如图4-5所示。图4・5转化过程示意图由图4-5可以

写出以下转化过程：第一步：b+c-bce+（假设x="bc+”）第二步：a*x—>ax*（假设

y="ax*"）第三步：y-d—>yd-将xy还原后得到：abc+*d-o

3、设线性表有n个元素，以下操作中，()在顺序表上实现比链表上实现效率更

高。

A、输出第i(lSign)个元素值

B、交换第I个元素与第2个元素的值

C、顺序输出这n个元素的值

D、输出与给定值x相等的元素在线性表中的序号

标准答案：A

知识点解析：顺序表支将随机存储，链表不支持，因此顺序表输出第i个元素的值

的时间复杂度为0(1),链表则为0(n),因此A正确。交换第1个与第2个元素的

值，对于顺序表和链表，时间复杂度均为0(1),因此B不对。输出n个元素的

值，两者时间复杂度均为O(n),因此C不对。输出与给定值x相等的元素在线性

表中的序号，对于顺序表和链表，count需要搜索整个表，因此时间复杂度为

0(n),因此D不对。

4、设k是中序线索二叉树中一个有左子女的结点，且k不是根结点，则k在中序

序列下的直接前驱结点是()。

A、k的左线索(指示中序前驱)所指示的结点

B、从k父结点的左子女开始沿右子女链走到底的结点

C、从k的左子女开始沿右子女链走到底的结点

D、从k的左子女开始沿左子女链走到底的结点

标准答案：C

知识点解析：如果k没有左子女，则k的左指针即为指向k的中序前驱的线索；当

k有左子女时，k的中序直接前驱结点是k的左子树中中序的最后一个结点，即从

k的左子女开始沿右链走到右指针不再是右子女的结点为止，该结点即为k的中序

前驱结点。说明：上述二叉树的线索化算法其实考试中涉及的不多，本节在考试中

涉及最多的是，在选择题中给你一棵二叉树，让你指出其中一个结点的线索按照某

种线索化方法所应该指向的结点。例如：请画出图4-7中按照中序线索化方法线

索化后E结点的右线索的接连情况。图4・7二叉树解决这类题的方法为，先

写出题目所要求的遍历方式下的结点访问序列，根据此序列找出题目要求中结点的

前驱和后继，然后连接线索。图4-7中二叉树的中序遍历序列为D,B,E,A,

Co结点E的前驱为B,后继为A,因此其右线索应该指向A,结果如图4-8所

5、假定一组元素序列为{38,42,55,15,23,44,34,74,45,26},按次序插

入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为2的结点个数

为()。

A、1

B、3

C、4

D、5

标准答案：C

知识点解析：根据题目所给的元素疔列，可以得到以下的平衡二叉树，如图4-9所

示。图右9平衡二叉树可以看出度为2的结点有4个。

6、由23、12、45、36构成的二叉排序树有()个,其中AVL树有()个。

A、13：4

B、13；5

C、14：5

D、14；4

标准答案：C

知识点解析：该题的结点不多，可以采用枚举法。但枚举法比较容易造成遗漏，所

以在枚举时要按照一定的规律，而且在枚举完之后看是否有重合的树并将其去掉，

为避免重复可以采用根结点来枚举，枚举得二叉排序树共有14个，其中5个为

AVL树。

序，可以得到不同的拓扑序列的个数是（）。

图4・1第7题图

A、4

B、3

C、2

D、1

标准答案：B

知识点解析：寻找拓扑排序的步骤：（1）在有向图中选一个没有前驱的顶点并且输

出。（2）从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均

已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中

所给图有3个不同的拓扑排序序列，分别为：l）a,b,c,e,do2）a,b,e,

c,do3）a,e,b,c,do

8、无向图G有16条边，有3个度为4的顶点，4个度为3的顶点，其余顶点的度

均小于3,则G至少有（）个顶点。

A、10

B、11

C、12

D、13

标准答案：B

知识点解析：度的定义指的是进入一个顶点的边数和从该顶点出去的边数之和。我

们可以根据这个关系来求解此题。由于题目已经告诉度为4的顶点有3个，度为3

的顶点有4个，其余的顶点的度均小于3,而已知有16条边，则总的度数应为

16x2=32o所以要求最小的顶点个数，我们应当尽量增加每个顶点的度数，这里将

剩下的结点的度数全部看成2,设结点数为x,则3x4+4x3+（x-3-4）x2N32,解得x

至少为11。

9、以下有关m阶B一树的说法中正确的有（）。I.每个结点至少有两棵非空子

树n.树中每个结点至多有m-1个关键字W.所有叶子在同一层上W.当插入一

个数据项引起B-树结点分裂后，树长高一层

A、仅I、H

B、仅口、迎

C、仅M、IV

D、仅I、口、IV

标准答案：B

知识点解析：I中：m阶B—树根结点至少有两棵子树，并且这两颗子树可以是

空树，其余结点至少有［m/2］个分支，即［m/2］个子树，所以I错误。D中：每

个结点中关键字的个数比分支数少1,m阶B-树的一个结点中至多有m个分支，

因此至多有m-1个关键字，所以H正确。HI中：B一树是平衡的多路查找树，叶

子结点均在同一层上，所以m正确。w中：发生结点分裂的时候不一定会使树长

高。比如向图4-10中的B—树插入一个关键字10变成图4-11中的B-树，使得第

二层右端的一个结点分裂成两个，但是树并没有长高，所以W错误。

I247I8-H13

图4-10B-树

图4.“插入一个关键字后的B-树综上所述，口、n［正确。

10、对以下关键字序列用快速排序进行排序，速度最慢的是（）。

A、{19,23,3,15,7,21,28）

B、{23,21,28,15,19,3,7}

C、{19,7,15,28,23,21,3）

D、{3,7,15,19,21,23,28）

标准答案：D

知识点解析：这种题目其实就是考查考生的记忆能力，因为在考研紧张的氛围下，

很少有考生在做这种选择题的时候能够分析其算法来选择答案。这里就是变相地考

查快速排序算法的最坏情况.快速排序法的最坏情况为待排序列是有序或接近有序

的时候，由于D中元素已经有序，所以选择D。

II、某个文件经内部排序得到80个初始归并段。如果操作系统要求一个程序同时

可用的输入/输出文件的总数不超过15个，则按多路归并至少需要（）趟可以完成

排序。

A、2

B、3

C、4

D、5

标准答案：A

知识点解析：不妨设采用m路归并，则至少需要m个输入缓冲区和1个输出缓冲

区。因为一个缓冲区对应一个文件，所以m+l=15,解得m=14,所以可做14路归

并。假设需要s趟可以完成排序，贝ijsqlogi480］=2。

12^考虑以下C语言代码：shortsi=-8196;unsignedshortusi=si;执行上述程序段

后，usi的值为（）。

A、8196

B、34572

C、57339

D、57340

标准答案：D

知识点解析：首先,求得・8196的补码表示为1101111111111100,赋值给usi

后，由于usi为无符号数，所以将二进制1101111111111100转换为十进制为

57340o

13、设浮点数的阶码用移码表示，尾数用补码表示，阶码的底数为2,阶码用3位

表示（包含一位符号位），尾数用5位表示（包含1位符号位），则它能表示的最小负

数为（）。

A、-8

B、-7.5

C、-128

D、-256

标准答案：A

知识点解析：要求最小负数，按照浮点数的格式来看，我们要尽量使尾数最小，达

到补码所能表示的最小的负数，另外还要使阶码最大，达到移码所能表示的最大整

数，而由补码的性质可知，无论对于尾数多少位来说，尾数的最小值永远是-1,阶

码最大为3。故最小的负数为-8。

14、硬盘平均寻道时间为12ms,传输速率为10MB/s,磁盘控制器延时为2ms,

则一个转速为7200r/min的硬盘写1KB数据的时间为（）。

A、13.11ms

R、14.13ms

C、15.15ms

D、18.27ms

标准答案：D

知识点解析：首先，需要判断1KB数据是否需要存储到多个磁道上。72001-/

也毁,MB/s

min=l20r/s；因为传输速率为10MB/s,故每转容量为：,20r/s葭,所

以1KB的数据只要在一个磁道上就能存储下了，无须换道。其次，写数据时间=磁

盘启动时间+磁盘寻道时间+旋转等待时间+数据传输时间。旋转等待时间为：旋转

半圈的时间，及（60/7200）x1/2=4.17ms；数据传输时间等于1KB/10MB/

s=0.1ms,所以写1KB数据的时间为：2ms+12ms+4.17ms+0.lms=18.27ms0

储

性存

易失

不是

RAM

静态

I.

()。

确的有

中，正

的说法

存储器

于各种

下面关

15、

写

可改

M是

PRO

I.E

一次D

写录

只能

ROM

D.P

储器

性存

易矢

M是

态RA

而动

器，

储器

写存

是可

储器

M存

EPRO

W.E

的一种

存储器

是随机

并且也

的，

A仅

、

仅I、n

B、

仅口、IV

c、

、田

仅I、u

D、

、w

口、m

：B

答案

标准

遗

都会

信息

电后

器，断

性存储

是易失

M都

态RA

和动

AM

静态R

I：

解析：

知识点

烧

将其

电流

利用

需要

丝，视

式的熔

有行列

的内部

ROM

H：P

误。

I错

所以

失，

,用

全为1

内容

储的

，存

出厂时

M在

。PRO

录一次

仅能写

料，但

需的资

写入所

断，

为

据全