重庆理工大学硕士研究生试题专用纸
重庆理工大学2013年攻读硕士学位研究生入学考试试题
学院名称：计算机科学与工程学院 学科、专业名称：计算机科学与技术 考试科目（代码）： 809计算机学科基础综合 （B卷） （试题共 5 页）
注意：1.所有试题的答案均写在专用的答题纸上，写在试题纸上一律无效。 2.试题附在考卷内交回。
本试卷共49题，满分150分。1-40题为选择题，每题2分，共80分，41-49题为综合题，共70分。
一、选择题
1.顺序表的第1个元素存储地址是300，每个元素占用2个存储单元，则该顺序表的第3个元素地址是（ ）
A．302 B.304 C.306 D.308 2.具有 m个顶点的有向完全图的边的数目为（ ）
A.m(m+1)/2 B.m(m-1)/2 C.m(m-1) D.m(m+1) 3.数据的存储结构可分为顺序存储结构和（ ）
A. 链式存储结构 B.哈希存储结构 C. 索引存储结构 D.表存储结构
4.深度为3（根结点的层次号为1）的满二叉树的叶子结点个数为（ ）
A.2 B.4 C.6 D.8
5.满二叉树，按层次序列编号（根结点编号为1），则编号为6的结点的双亲编号为（ ）
A.1 B.2 C.3 D.4
6.判定栈(栈最多能容纳n个元素)为空的条件是（ ）
A.T->top!=0 B. T->top!=n C. T->top==0 D. T->to==n 7. 队列的特点是（）
A.后进先出 B.先进先出 C.同进同出 D.同出同进 8.算法具有五个特性，下列描述中不是算法特性的是（ ）
第 1 页
重庆理工大学硕士研究生试题专用纸
A.输入 B.输出 C.有穷性 D.无限性
9.数据元素之间有四种基本逻辑结构，下列描述中不是逻辑结构的是（ ）
A. 树形结构 B. 线形结构 C.哈希结构 D.图形结构 10.单链表的指针域的个数为（ ）
A.0 B.1 C.2 D.3 11. 第一代计算机是以（ ）为主要器件的。
A．电子管 B.晶体管 C. 二极管 D. 触发器 12. 静态RAM基本电路单元是靠（ ）来寄存信息的。 A．电阻 B.电感 C. 触发器 D. 晶体管 13. Cache是为解决（ ）与内存之间速度不匹配而采用的一项技术。 A．外设 B.CPU C.寄存器 D. 总线
14. DMA用于高速数据块的传送，直接在（ ）和外设之间进行数据传送。 A．内存 B.硬盘 C. CPU D. Cache 15. 浮点数表示的范围和精度取决于（ ）。
A． 阶码的位数和尾数的位数 B. 阶码的编码方式和尾数的位数 C. 阶码的编码方式和尾数编码方式 D. 阶码的位数和尾数编码方式 16. 某存储器芯片规格为8K×16位，则它的地址线和数据线分别有（ ）根、（ ）根。
A．13、8 B. 13、16 C. 8、16 D. 18、16 17. 在主机中能对指令进行译码的器件是（ ）。
A．MDR B.ALU C.控制器 D. MAR
18. 操作数的地址就是操作数本身，这种寻址方式称为（ ）寻址。 A．立即 B.直接 C.间接 D. 基址 19.以硬连线方式构成的控制器也称（ ）控制器。 A．组合逻辑型 B.微程序 C.存储逻辑型 D. 运算器 20.计算机中存放微指令的控制存储器属于（ ）。 A．外存 B. Cache C.U盘 D. CPU 21.断电后信息会丢失的是（ ）。
A．Flash Memory B.硬盘 C.RAM D. 光盘 22.主机、与外设串行工作的方式是（ ）。
A．程序查询 B.程序中断 C. 通道方式 D. DMA 23. 与外存相比，内存的特点是（ ）。
第 2 页
重庆理工大学硕士研究生试题专用纸
A．容量大、速度快、成本低 B. 容量大、速度慢、成本高 C. 容量小、速度快、成本高 D. 容量小、速度慢、成本高 24. CPU响应中断的时间是（ ）。
A．任一机器周期结束时 B. 外设提出中断时 C. 取指周期结束时 D. 一条指令执行结束时 25.微程序控制系统中，机器指令与微指令之间的关系是（ ）。 A．每条机器指令由一段微指令编成的微程序来解释 B. 每条机器指令由一条微指令来完成
C.一段机器指令组成的程序由一条微指令来执行 D. 一条微指令由若干条机器指令组成
26. 下列资源一般不由操作系统管理的是（ ） A．内存 B.打印机 C.CPU D. 应用程序的变量 27.下列哪一个不是操作系统提供的接口（ ）
A．游戏 B.系统调用 C.图形用户界面 D.操作系统命令 28. 多道程序设计系统中，让多个计算问题同时装入计算机系统的主存储器（ ）。
A．并发执行 B.顺序执行 C.并行执行 D.同时执行 29. 某进程由于需要从硬盘上读入数据而处于等待状态，当系统完成了所需的读盘操作后，此时该进程的状态将（ ）
A．从就绪变为运行 B. 从运行变为就绪 C. 从运行变为阻塞 D. 从等待变为就绪 30. 进程是由（ ）组成的。
A．程序+数据+进程控制块 B. 程序+数据+标识符 C. 数据+进程控制块 D. 标识符+数据+进程控制块
31. 在进程调度算法中，最有利于提高系统吞吐量的作业调度算法是（ ）。
A．FCFS调度算法 B. 短作业优先调度算法 C. 时间片轮调度算法 D. 多级反馈队列调度算法 32. 分区分配内存管理方式的主要保护措施是（ ）。
A．界限寄存器 B. 程序代码保护 C. 设置访问权限 D. 密码保护
33. 下列算法中属于磁盘寻道调度算法的是（ ）。
第 3 页
重庆理工大学硕士研究生试题专用纸
A．短作业优先法 B. 时间片轮转法 C. 最短寻道时间优先法 D. 最近最少使用法
34.通过硬件和软件的功能扩充，把原来独占的设备改造成能为若干用户共享的设备，这种设备叫（ ）。
A．存储设备 B. 系统设备 C. 虚拟设备 D. 用户设备
35. 从用户角度看，文件系统的主要目的是（ ）。
A．实现对文件的按名存取 B. 实现虚拟存储器 C. 提高外围设备的输入/输出速度 D. 用于存储系统文档 36.下列传输介质中，抗电磁干扰性最好的是（ ）
A.双绞线 B.光纤 C.同轴电缆 D.电话线 37.IPv6地址的长度是（ ）
A.16bit B.32bit C.48bit D.128bit 38.Internet的网络体系结构是（ ）
A.OSI/RM B.ARP/RARP C.HTTP/SMTP D.TCP/IP
39.数据通信线路的工作模式分为单工通信、半双工通信和（ ）
A.多播通信 B.组播通信 C.全双工通信 D.P2P通信 40.下列描述中，不属于多路复用技术的是（ ）
A.双分复用技术 B.频分复用技术 C.时分复用技术 D.波分复用技术
二、综合题
41.计算程序段的时间复杂度（5分） t=0;
for(i=1;i<=N;i++) for(j=1;j<=N;j++) {t++;}
42.简答什么是数据？什么是数据结构（10分）
43.假设二叉树采用如下的存储结构，其中lchild和rchild为分别指向左右孩子的指针。
第 4 页
重庆理工大学硕士研究生试题专用纸
typedef struct node {
int data;
struct node *lchild,*rchild; }TwoTree;
请编写一个算法，实现用递归方法求二叉树的叶子结点个数。 （10分） int Leafcount(TwoTree *bt)
44.已知x=0.10010,y=-0.11011。
（1）写出x、y的变形补码（双符号位）；（2分） （2）用变形补码求[x+y]补,并指出其值是否溢出；（4分） （3）用变形补码求[x-y]补,并指出其值是否溢出；（4分）
45.什么是指令周期？一个完整的指令周期应该包括哪几个子周期？（5分）
46.（1）什么是临界资源和临界区?（2分）
（2）桌上有一个盘子，可以容纳一个水果，每次只能存或取一个水果，爸爸向盘中放水果，女儿从盘中取水果吃，请用P、V操作来描述爸爸和女儿之间的同步和互斥关系。（5分）
47.（1）在请求分页系统中，页面置换的含义是什么？（2分）
（2）设系统为某进程分配了3个物理块，该进程共有8个页面，考虑如下的页面引用顺序：7,0,1,2,0,3,0,4，问：
A．按FIFO页面置换算法，访问第3号页面时，应淘汰第几号页面，共发生几次页面置换？（3分）
B．按LRU页面置换算法，访问第3号页面时，应淘汰第几号页面，共发生几次页面置换？（3分）
48.简答什么是网络协议？网络协议的三要素是什么？（7分）
49.简答OSI/RM七层参考模型有哪七层？最高层的主要功能是什么？（8分）
第 5 页
