1、重庆理工大学硕士研究生试题专用纸重庆理工大学2016年攻读硕士学位研究生入学考试试题 学院名称：计算机科学与工程学院 学科、专业名称：计算机科学与技术 考试科目（代码）：计算机学科专业基础综合（812）A卷 （试题共 4 页）注意：1所有试题的答案均写在专用的答题纸上，写在试题纸上一律无效。2试题附在考卷内交回。一单选题(每题2分，共50分)1数据元素之间有4种逻辑结构，下列不属于数据元素的逻辑结构是（ ）A线性结构 B树形结构 C图形结构 D队列2数据结构的二元组结构B=（D，R），其中D是数据元素的集合，R是（ ）A关系的集合 B线性的集合 C树形的集合 D图形的集合3算法有5个特性，下列
2、不属于算法特性的是（ ）A输入 B输出 C可行性 D方法4单链表中每个结点的指针域的个数为（ ）A1 B2 C3 D45完全二叉树，按层次序列对每个结点编号（根结点编号为1），则编号为3的结点的双亲编号为（ ）A1 B2 C3 D46下列不属于线性结构的是（ ）A线性表 B栈 C队列 D图7顺序表的第1个元素存储地址是2000，每个元素占用2个存储单元，则该顺序表的第3个元素地址是（ ）A2002 B2004 C2006 D20088n个顶点连通图的生成树中边的数目是（ ）An Bn+1 Cn-1 D2n9深度为1（根的层次号为1）的满二叉树结点个数为（ ）A1 B3 C7 D810在一个无向
3、图中，边的数目为4，则所有顶点的度数之和为（ ）A4 B8 C16 D3211有一个有序表为1，2，3，当折半查找到2时，需要的比较次数为（ ） A1 B2 C3 D412一个栈的入栈顺序是BCD，则该栈的不可能的输出序列是（ ）ABCD BDCB CCBD DDBC13完全二叉树共有15个结点，按层次序列对每个结点编号（根结点编号为1），则编号为3的结点的右孩子编号为（ ）A6 B7 C8 D914设先序遍历某二叉树的序列为AB，中序遍历该二叉树的序列为BA，则后序遍历该二叉树的序列为（ ）AAB BBA CAC DCA15下列是图的存储结构的是（ ）A数组 B邻接表 C线性表 D栈16在普
4、通用户看来，操作系统是（ ）A用户与计算机之间的接口 B控制和管理计算机的接口C合理地组织计算机工作流程的软件 D计算机资源的管理者17并发和下面哪个是操作系统的基本特征，两者之间互为存在条件？（ ）A虚拟 B异步 C共享 D可扩展性18通道是一种（ ）AI/O中断口 B共享文件 CI/O专用处理机 D数据通道 19作业从进入后备队列到被调度程序选中的时间称为（ ）A周转时间 B响应时间 C触发时间 D等待时间20临界区是指（ ）A公共数据区 B临时工作区 C系统管理区 D与共享变量有关的程序段21进程调度的关键问题是（ ）A时间片大小 B进程调度算法 CCPU速度 D内存空间的大小22下列哪
5、种存储方式不能实现虚拟存储（ ）A分区 B页式 C段式 D段页式23操作系统处理缺页中断时，选择一种好的调度算法对内存和外存中的信息进行高效调度，必须尽可能避免（ ）A碎片 BCPU空闲 C多重中断 D抖动24对随机存取的文件，在磁盘上必须组织成（ ）A有序文件 B索引文件 C连续文件 D链接文件25在多级文件结构中，要访问一个文件时，必须指出文件的（ ）A父目录 B当前目录 C路径名 D根目录二简答题(每题5分，共50分)26数据结构的定义是什么?（5分）27设给定权集W=1，3，5，9，试构造关于W的一棵赫夫曼树，并求其带权路径长度WPL。（5分）28设有一序列25,18,6,44，请按该
6、序列构成一棵二叉排序树，并求其查找成功时的平均查找长度ASL。（5分）29写出下图所示二叉树的先序，中序和后序遍历序列。（5分）CAD30 已知待散列的线性表为（7，12，13，17，10），散列用的一维地址空间为05，假定选用的散列函数是H（K）= K mod 6，若发生冲突采用线性探查法处理，计算出每一个元素的散列地址并在下图中填写出散列表。（5分）01234531什么是进程，进程和程序有哪些不同？（5分）32说明进程的三种基本状态以及各状态之间的转换。（5分）33什么是死锁，产生死锁有哪几个条件？（5分）34什么是虚拟存储器，虚拟存储器有什么特点，如何实现虚拟存储地址的转换？（5分）35
7、中断和DMA有什么异同？（5分）三综合题(共50分)36编写函数，实现对二叉树的后序遍历(postorder)的递归算法。（10分）二叉树结点的结构体为 struct BiTreeNode int data;struct BiTreeNode * leftChild;struct BiTreeNode * rightChild; typedef struct BiTreeNode Node; void postorder (Node * t) /*t为指向二叉树的根结点的指针*/37编写两个函数，分别实现对数组a(元素个数为n)中元素进行冒泡排序和简单选择排序的算法。（15分） void ma
8、opaosort(int a, int n)void xuanzhesort(int a, int n)38在微信操作的程序中，假设有一个邮箱，有4个程序A、B、C、D对该邮箱进行操作，A写入的数据X只能被C使用，B写入的数据Y只能被B使用，A、B写入数据后C、D才能使用，C、D使用一次数据后不能再重复使用，只有等到A、B再次写入后才能使用。规定邮箱中一次只能存放一个数据。请用信号量的方式实现这几个进程之间的同步和互斥关系。(10分)39（本题共15分）在一个多道作业批处理系统中，作业调度采用短作业优先的调度算法，设有下列作业序列：作业名到达时间预估运行时间优先级18:0030828:2040538:2020748:30106其中给出的作业优先级即为进程的优先级，其数值越小，优先级越高。要求：（1）如果进程调度采用抢占式优先调度算法。列出所有作业进入内存的时间及结束时间。并计算周转时间和平均周转时间。（5分）（2）如果进程采用非抢占式调度，结果又如何？（5分）（3）分析哪种调度方式更好？（5分）第1页
