1、重庆理工大学硕士研究生试题专用纸重庆理工大学2015年攻读硕士学位研究生入学考试试题学院名称：计算机科学与工程学院 学科、专业名称：计算机科学与技术考试科目（代码）：计算机学科专业基础综合（813）A卷（试题共 5 页）注意：1.所有试题的答案均写在专用的答题纸上，写在试题纸上一律无效。2.试题附在考卷内交回。一单选题(每题2分，共50分)1一个栈的入栈顺序是a,b,c,d,e，则该栈的输出序列不可能是（ ）Aabcde Baecbd Ccbade Dedcba2二叉树的二叉链表的指针域的个数为（ ）A0 B1 C2 D33队列的删除操作在（ ）A队头 B队尾 C栈顶 D栈底4设一组初始记录关
2、键字序列(4，2，3，7)，进行一趟简单选择排序的结果为（ ）A4，2，3，7 B4，2，7，3 C2，7，4，3 D2，4，3，75设先序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BCAD，则后序遍历该二叉树的序列为（ ）AABCD BBCAD CCBDA DCDBA6深度为5的二叉树（根结点层次为1）至多结点个数为（ ）A15 B31 C32 D637有7个顶点的无向连通图最少边数为（ ）A5 B6 C7 D88三元组表用于表示（ ）A线性表 B双向链表 C稀疏矩阵 D栈9设无向图G中有n个顶点，则该无向图的最小生成树上边的数目为（ ）An-1 Bn C2n-1 D2n10有序
3、表为3，5，7，9，30，当折半查找到3时，需要的比较次数为（ ）A1 B2 C3 D411设有一个10阶的下三角矩阵A（包括对角线），按照以行为序进行顺序存储到连续的55个存储单元中，每个元素占1个字节的存储空间，如果A00存储地址为100，则A43的存储地址为（ ）A111 B112 C113 D11412与&ai等价的是（ ）A*（a+i） Ba+i C*a+i D&（a+i）13完全二叉树共有20个结点，按层次序列对每个结点编号（根结点编号为0），则编号为7的结点的右孩子编号为（ ）A13 B14 C15 D1614在一个无向图中，边的数目为8，则所有顶点的度数之和为（ ）A16 B8
4、 C24 D3215下列不属于算法的五个重要特性的是（ ）A有穷性 B确定性 C输入 D描述性16. 操作系统的主要功能是（ ）。A提高系统的运行速度 B. 增强计算机系统的功能C. 合理组织系统的工作流程 D. 提高系统资源的利用率17.关于程序的并发，下列叙述正确的是（ ）。A 并发是指若干事件在同一时刻发生 B. 并发是指若干事件在不同时刻发生C. 并发是指若干事件在同一时间间隔内发生 D. 并发是指若干事件在不同时间间隔内发生18.进程生存期中的状态不包括下列哪一种（ ）。A 就绪 B. 执行C. 阻塞 D. 等待 19. 分时系统的响应时间（及时性）主要是根据下面哪一个来确定的？（
5、）A 时间片 B. 用户数目C. 用户所能接受的等待时间 D. 控制对象所能接受的时延20. 下面关于临界区的论述中，哪条是正确的？（ ）A. 临界区是指进程中用于访问临界资源的那段代码 B 临界区是指进程中用于实现进程互斥的那段代码 C. 临界区是指进程中用于实现进程同步的那段代码D. 临界区是指进程中用于实现进程共享的那段代码21.下列算法中，哪一个是只能采用非抢占调度方式？（ ）A高优先级优先法 B. 时间片轮转法C. FCFS调度算法 D. 短作业优先算法22. 磁盘属于块设备，磁盘的I/O控制方式主要利用（ ）A程序I/O方式 B. DMA方式C. 程序中断方式 D.SPOOLing
6、方式 23. 文件系统主要通过下面哪一种方式来实现文件的按名存取？（ ）A存储空间管理 B. 文件的安全性管理C. 文件的读写管理 D. 目录管理24. 操作系统向用户提供多种接口，其中通过下面哪一种接口，用户可从终端键入dir（或ls）来显示当前目录的内容？（ ）A脱机用户接口 B. 联机命令接口 C. 图形用户接口 D. 系统调用接口25.一个计算机系统的虚拟存储器的最大容量是由下面那一项确定的？（ ）A内存和硬盘容量之和 B. 内存容量C硬盘容量 D. 计算机的字长二简答题(每题6分，共60分)26图的定义是什么？图中元素之间的关系是1对1，1对多，还是多对多？（6分）ACEBDFG27
7、写出下图所示二叉树的先序，中序和后序遍历序列。（6分） 28设给定权集W=1，2，3，8，20，试构造关于W的一棵赫夫曼树，并求其加权路径长度WPL。（6分）29什么是栈? 栈的特点是什么? 什么是队列? 队列的特点是什么?（6分）30已知待散列的线性表为（7，15，23，54，26，20），散列用的一维地址空间为0.7，假定选用的散列函数是H（K）= K mod 8，若发生冲突采用线性探测法处理，计算出每一个元素的散列地址并在下图中填写出散列表，并求出平均查找长度ASL。（6分）0123456731.什么是进程？与程序有何不同？（6分）32.在设备管理中引入缓冲的主要原因是什么？一般有哪几种
8、常见的缓冲类型？（6分）33.说明操作系统与硬件、其它系统软件以及用户之间的关系。（6分）34.什么是目录，目前广泛采用的目录结构是哪种？有什么优点？（6分）35.引起进程调度的因素有哪些？（6分）三综合题(每题10分，共40分)36假设二叉树采用如下定义的存储结构： typedef struct node int data; struct node *lchild,*rchild; PBinTree;其中，结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针。请编写一个算法，实现用递归方法求二叉树的叶子结点个数。（10分）void Leafcount(PBinTree *
9、bt) 37编写一个函数，实现对数组a中元素进行快速排序的算法，其中low为下界，high为上届。（10分）void quickSort(int a, int low, int high)38.有三个进程A，B，C，分别调用过程get、copy和put对缓冲区S和T进行操作，其中get负责将数据输入缓冲区S，copy负责从缓冲区S中提取数据并复制到缓冲区T，put负责从缓冲区T取出数据打印，如图所示，描述get、copy和put的操作过程。（10分）39. 解释固定分区算法中的首次适应算法（First fit）、最佳适应算法（Best fit）、最差适应算法（Worst fit）的基本思想，假如某个系统有5个固定分区，其长度分别为100KB、500KB、200KB、300KB、600KB，仅有4个进程，对内存需求分别为212KB、417KB、112KB、426KB。当分别采用首次适应算法（First fit）、最佳适应算法（Best fit）、最差适应算法（Worst fit）响应4个进程的内存申请时，请分别给出系统的内存分配动态，哪种算法最有效？（10分）第4页
