北京邮电大学2019年硕士研究生招生考试试题
考试科目：计算机学科基础综合
请考生注意：①所有答案（包括选择题和填空题）一律写在答题纸上，否则不计成绩。
②不允许使用计算器
一、单项选择题（每小题2分，共80分）
1.下面算法的时间复杂度是
int A（int n）
{if（n<=1）return 1；
retun n+A（n/2）；}
A.O（n） B.O（n2） C.Olog2n） D.O（n log2n）
2.将两个各有n个元素的递增有序的顺序表归并成一个有序表，最少的比较次数是
A.n-l B.n C.2n-1 D.2n
3.设n个元素1，2.…，n（n>l00），按从小到大顺序进栈，出栈序列为p1，p2.……pn，若p1=10，则p2的值不可能出现的元素个数为
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.2m B.2m-1 C.2m-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.在操作系统的页式存储管理中，页表内容如下图所示。
帧号 | |
0 | 2 |
1 | 4 |
2 | 1 |
若页的大小为4KB，则地址映射机构将逻辑地址2转换成的物理地址是（）。
A.8194 B.4098 C.2050 D.1026
30.操作系统中，可以给不同文件取相同文件名，为了解决命名冲突，一般在文件系统中采用
A.链接结构 B.索引表
C.环行目录结构 D.树型目录结构
31.在虚拟内存管理采用的页面置换算法中，LRU置换算法是（ ）
A.置换进入内存时间最长的页面
B.置换以后不再需要的，或者在最长时间以后才会用到的页面
