北京邮电大学2019年硕士研究生招生考试试题

考试科目：计算机学科基础综合

请考生注意：①所有答案（包括选择题和填空题）一律写在答题纸上，否则不计成绩。

②不允许使用计算器

一、单项选择题（每小题2分，共80分）

1.下面算法的时间复杂度是

int A（int n）

{if（n<=1）return  1；

retun  n+A（n/2）；}

A.O（n）           B.O（n²）          C.Olog₂n）         D.O（n log₂n）

2.将两个各有n个元素的递增有序的顺序表归并成一个有序表，最少的比较次数是

A.n-l                           B.n                            C.2n-1                 D.2n

3.设n个元素1，2.…，n（n>l00），按从小到大顺序进栈，出栈序列为p₁，p₂.……p_n，若p₁=10，则p₂的值不可能出现的元素个数为

A.n-9                   B.n-10                 C.9                      D.8

4.在循环队列Q[0…m-1]中，front指向队首元素，rear 指向队尾元素的下一个空单元，则此时该队列中空单元的个数为

A.（（m+front-rear）%m                      B.（m-front+rear）%m

 C.（m-front-rear）%m                               D.（m+front+rear）%m

5.具有529个结点的完全二叉树，其叶子结点的个数是

A.256                  B.261                  C.263                  D.265

6.若二维数组A[0..7][0..4]的首地址为10000，以行优先顺序存储在计算机中，每个元素占5个存储单元，则元素A[4][3]的存储地址为

A.10090                     B.10115              C.10140              D.10160

7.有n个顶点的图采用邻接表存储，有m个边结点，m为奇数，若该图任意两个顶点对之间均有路径可达，则m的值最少是

A.n（n-1/2          B.n（n-l）          C.n               D.n-l

8.一棵深度为m的平衡二叉树，其每个结点的平衡因子均为0，则该树的结点数是

A.2^m                    B.2^m-1                 C.2^m-1                   D.无法确定的

9.排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列算法中，每趟均有至少一个元素到达最终位置且稳定的排序方法是

A.简单选择排序              B.快速排序        C.直接插入排序       D.冒泡排序

10.对2019个初始归并段进行4路最佳归并，需补充的虚段数为

A.0                      B.1               C.2                      D.3

11.以下术语中，与存储结构无关的是

A.哈希表            B.双向链表        C.强连通图        D.循环队列

12.以下属于冯·诺依曼结构计算机工作方式基本特点的是

A.单指令流多数据流                    B.程序和数据存放在各自的存储器中

C.CPU由控制器和运算器组成   D.存储器按内容选择地址

13.C语言int、short数据类型分别占用4字节和2字节，其程序在一台32位处理机上运行。程序中定义了三个变量a、b和y，其中a是int 型，y和b为short型。当a=65537，b=-11时，执行语句y=a+b后，y的值是

A.65526                     B.31062              C.-10                   D.-32756

14.若IEEE754单精度浮点数十六进制值为C349C000，则它的十进制值为

A.201.75                    B.-201.75                   C.73.75        D.-73.75

15.下列半导体存储器中，断电后所存储的信息不丢失的是

A.SRAM、DRAM                        B.FLASH、SRAM

C.ROM、SRAM                           D.FLASH、ROM

16.某32位计算机的主存容量为1GB，由若干颗64M*8位的DRAM芯片构成，则该DRAM芯片的地址引脚和数据引脚分别是

A.32、32                   B.30、32                   C.26、8              D.13、8

17.若指令的操作数寻址采用相对寻址方式，则操作数位于（ ）

 A．内存单元中                    B.通用寄存器中

 C．指令中                       D.程序计数器中

18.某小端（Little Endian）模式处理器的减法指令“sub ax,imm”的功能为(ax)-imm→ax,imm表示立即数，该指令对应的十六进制机器码为2DXXXX，其中XXXX对应imm的机器码，如果imm=-3，（ax）=7,则该指令对应的机器码和执行后OF标志的值分别为（ ）

A.2DFFFD、0                               B.2DFFFD、1

C．2DFDFF、0                        D、2DFDFF、1

19. 下列选项中，不符合RISC指令系统特征的是（ ）

A．指令数量少，指令长度通常是固定的

B．允许使用内存引用的只有load指令和store指令

C．通用寄存器数量多

D．可以对内存操作数进行算数和逻辑运算

20. 为了使总线上所有主设备争用总线使用权时优先级相同，可以采用计数器定时查询的集中式总线仲裁器，并且要求（ ）

A.每次计数器从0开始计数               B.每个设备的计数器从0开始计数

C.每次计数器从最大值开始计数       D.每次计数器从暂停点开始计数

21. 队友CISC计算机，为了便于实现多级中断，最有效的办法是保存现场信息到（ ）

A.存储器中B.堆栈中C.通用寄存器中D.专用寄存器中

22.下列关于DMA的叙述中，错误的是

A.是一种主要由硬件实现/O交换的工作方式      

B.只有在指令周期结束时才能响应DMA请求

C.DMA传送过程中不需要处理器参与操作 

D.每一次DMA传送必须申请占用总线

23.假设系统有3个进程，每个进程都需要同类资源5个，为使该系统一定不发生死锁，该类资源需配置的最少数目是（ ）

A.12    B.13             C.14             D.15     

24.最适合分时系统的操作系统CPU调度算法是（ ）

A.FCFS       B.FIFO        C.时间片轮转           D.短作业优先

25.进程从就绪状态转为运行状态的条件是（ ）

A.进程长时间处于等待状态

B.进程长时间处于就绪状态

C.等待某一个事件

D.进程被调度程序选中

26.若信号量S的初值为5，当前值为3，则表示等待该信号量的进程有

A.0个          B.1个          C.2个          D.3个

27.在操作系统的虚拟内存管理中，虚拟存储器的最大容量是（ ）

A.缓存容量                                    B.内存容量       

C.由计算机的地址结构决定        D.外存容量

28.在虚拟内存管理中，采用FIFO页面置换算法，当分配的物理帧的数目增加时，缺页中断次数（ ）

A.减少                                            B.可能增加也可能减少 

C.不变                                            D.增加

29.在操作系统的页式存储管理中，页表内容如下图所示。

若页的大小为4KB，则地址映射机构将逻辑地址2转换成的物理地址是（）。

A.8194         B.4098         C.2050         D.1026

30.操作系统中，可以给不同文件取相同文件名，为了解决命名冲突，一般在文件系统中采用

A.链接结构                      B.索引表

C.环行目录结构              D.树型目录结构

31.在虚拟内存管理采用的页面置换算法中，LRU置换算法是（ ）

A.置换进入内存时间最长的页面

B.置换以后不再需要的，或者在最长时间以后才会用到的页面