重庆理工大学硕士研究生试题专用纸第 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 个特性，下列不属于算法特性的是（ ）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 C 2006 D20088n 个顶点连通图的生成树中边的数目是（ ）An Bn+1 Cn-1 D2n9深度为 1（根的层次号为 1）的满二叉树结点个数为（ ）A1 B3 C7 D810在一个无向图中，边的数目为 4，则所有顶点的度数之和为（ ）重庆理工大学硕士研究生试题专用纸第 2 页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在普通用户看来，操作系统是（ ）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下列哪种存储方式不能实现虚拟存储（ ）A分区 B页式 C段式 D段页式23操作系统处理缺页中断时，选择一种好的调度算法对内存和外存中的信息进行高效调度，必须尽可能避免（ ）A碎片 BCPU 空闲 C多重中断 D抖动重庆理工大学硕士研究生试题专用纸第 3 页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，请按该序列构成一棵二叉排序树，并求其查找成功时的平均查找长度 ASL。 （5 分）29写出下图所示二叉树的先序，中序和后序遍历序列。 （5 分）30 已知待散列的线性表为（7，12，13，17，10） ，散列用的一维地址空间为0 5 ，假定选用的散列函数是 H（K）= K mod 6，若发生冲突采用线性探查法处理，计算出每一个元素的散列地址并在下图中填写出散列表。（5 分）0 1 2 3 4 531什么是进程，进程和程序有哪些不同？（5 分）32说明进程的三种基本状态以及各状态之间的转换。 （5 分）33什么是死锁，产生死锁有哪几个条件？（5 分）34什么是虚拟存储器，虚拟存储器有什么特点，如何实现虚拟存储地址的转换？（5 分）35中断和 DMA 有什么异同？（5 分）三综合题(共 50 分)36编写函数，实现对二叉树的后序遍历(postorder)的递归算法。 （10 分）二叉树结点的结构体为CA D重庆理工大学硕士研究生试题专用纸第 4 页struct BiTreeNodeint data;struct BiTreeNode * leftChild;struct BiTreeNode * rightChild;typedef struct BiTreeNode Node;void postorder (Node * t) /*t 为指向二叉树的根结点的指针*/37编写两个函数，分别实现对数组 a(元素个数为 n)中元素进行冒泡排序和简单选择排序的算法。 （15 分）void maopaosort(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 分）在一个多道作业批处理系统中，作业调度采用短作业优先的调度算法，设有下列作业序列：作业名 到达时间 预估运行时间 优先级1 8:00 30 82 8:20 40 53 8:20 20 74 8:30 10 6其中给出的作业优先级即为进程的优先级，其数值越小，优先级越高。要求：（1 ）如果进程调度采用抢占式优先调度算法。列出所有作业进入内存的时间及结束时间。并计算周转时间和平均周转时间。 （5 分）（2 ）如果进程采用非抢占式调度，结果又如何？（5 分）（3 ）分析哪种调度方式更好？（5 分）重庆理工大学硕士研究生试题专用纸第 1 页