重庆理工大学2019年攻读硕士学位研究生入学考试试题计算机学科基础综合.doc

重庆理工大学硕士研究生招生考试试题专用纸 重庆理工大学2019年攻读硕士学位研究生入学考试试题 学院名称：计算机科学与工程 学科、专业名称：计算机科学与技术 考试科目(代码)：计算机学科基础综合(816)A (试题共 6 页) 注意：1.所有试题的答案均写在专用的答题纸上，写在试题纸上一律无效。 2.试题附在考卷内交回。 一、选择题(50分，25小题，每小题2分) 1.数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的( )和运算的学科。 A.结构 B.关系 C.数值 D.算法 2.线性表是一个可在( )位置对数据元素进行插入、删除操作的序列容器。 A.仅表头 B.仅表尾 C.任意 D.都是 3.将长度为n的单链表连接在长度为m的仅带头指针的单链表后面，其算法的时间复杂度为( )。 A.O(1) B.O(n) C.O(m) D.O(m + n) 4.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是( )。 A.front== rear B.front!= rear C.front==rear+ 1 D.front==(rear+1)% maxSize 5.下面关于串的叙述中，不正确的是( )。 A.串是字符的有限序列 B.空串是空格构成的串 C.模式匹配是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 6.对特殊矩阵采用压缩存储的目的主要是为了( )。 A.表达变得简单 B.对矩阵元素的存取变得简单 C.去掉矩阵中的多于元素 D.减少不必要的存储空间 7.对一棵满二叉树，有A个叶结点、B个结点、深度为C，则( )。 A.B=C+1 B.C+A=2B C.A=C-1 D.B=-1 8.任意一棵二叉树，其叶结点在先根遍历、中根遍历和后根遍历序列中的相对次序( )。 A.保持不变 B.先根遍历和中根遍历有变化，后根遍历无变化 C.先根遍历和后根遍历有编号，中根遍历无变化 D.中根遍历和后根遍历有变化，先根遍历无变化 9.一个有n个顶点的无向图最多有( )条边。 A.n B.n(n-1) C.n(n-1)/2 D.2n 10.对某个无向图的邻接矩阵来说，下列叙述正确的是( )。 A.第i行上的非零元素个数和第i列上的非零元素个数一定相等 B.矩阵中的非零元素个数等于图中的边数 C.第i行与第i列上的非零元素的总数等于顶点vi的度数 D.矩阵中非零行的行数等于图中的顶点数 11.对于含有n个顶点的带权连通图，它的最小生成树是指图中的任意一个由( )子图。 A.n-1条权值最小的边构成的 B.n-1条权值之和最小的边构成的 C.n-1条权值之和最小的边构成的连通 D.n个顶点构成的边的权值最小的边构成的极小连通 12.在用邻接表表示图时，拓扑排序算法的时间复杂度为( )。 A.O(n) B.O(n+e) C.O(n2) D.O(n3) 13.内部排序算法的稳定性是指( )。 A.经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变 B.经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变 C.排序算法的性能与被排序元素个数关系不大 D.排序算法的性能与被排序元素个数关系密切 14.下列排序算法中，( )排序算法可能会出现下面的情况，初始数据有序时，花费的时间反而更多。 A.快速 B.堆 C.希尔 D.冒泡 15.在下列的排序中，序列( )是堆。 A.1，2，8，4，3，9，10，5 B.1，5，10，6，7，8，9，2 C.9，8，7，6，4，8，2，1 D.9，8，7，6，5，4，3，7 16.操作系统提供给应用程序的接口是( )。 A.P、V操作 B.中断 C.库函数 D.系统调用 17.现代操作系统基本都采用缓冲技术，目的是为了( )。 A.提高编程效率 B.提高CPU的处理速度 C.实现设备无关性 D.提高设备和CPU之间的并行程度 18.下列哪个程序可以在用户态执行？( ) A.时钟中断处理程序 B.游戏程序 C.缺页处理程序 D.进程调度程序 19.外存上存放的数据( )。 A.先要调入虚拟存储器中才能有CPU访问 B.CPU可直接访问 C.必须在访问前先装入主存 D.可以直接调入高速缓冲存储器中 20.下面哪个不属于I/O控制方式？( ) A. 通道技术 B. DMA方式 C.覆盖方式 D.中断方式 21.进程在系统中是否存在的唯一标志是( )。 A.数据集合 B.目标程序 C.源程序 D.进程控制块 22.存储管理技术中通常采用对换技术，目的是( )。 A.提高内存利用率 B.实现主存共享 C.物理上扩充 D.节省存储空间 23.在文件系统中，文件的属性可以集中存放在( )中以便查找。 A.索引 B.作业控制块 C.目录 D.字典 24.下列哪种方式不能提高磁盘设备的I/O速度？( ) A.重排I/O请求次序 B.优化文件的物理分布 C.预读和滞后写 D.在一个磁盘上设置多个分区 25.操作系统需要解决的问题不包括( )。 A.提供程序保护和安全机制 B.提供高级语言的编译器 C.提供应用程序接口 D.管理目录，提供文件访问方式 二、综合题(100分，12小题) 26.(5分)假设一棵二叉树包含的结点数据值为1，4，9，3，20，请画出两棵高度最大的二叉树。 27.(5分)一棵二叉树，其先根遍历序列为ABDCEGHF，中根遍历序列为DBAGEHCF，请写出其后根遍历序列。 28.(5分)已知一无向图G=(V，E)，其中V={a，b，c，d，e}，E={ (a，b)，(a，d)，(d，c)，(b，e)}，现用深度优先遍历方法从顶点a开始遍历图，写出所得到的遍历序列。 29.(8分)假定某系统中有Z1、Z2、Z3三个资源，现有A，B，C三个进程并发工作。如果各个进程运行需要的资源情况为：进程A需要资源Z3和Z1，进程B需要资源Z1和Z2，进程C需要资源Z2和Z3。回答： (1)若对资源分配不加限制，会发生什么情况，举例说明为什么。(3分) (2)为保证各个进程正常推进，可能采取哪些资源分配策略，阐述原因？(5分) 30.(8分)进程运行过程中，可能引起进程状态变化的情况很多，简述什么是进程调度，可能引起进程调度的情况有哪些？ 31.(8分)在请求分页管理系统中，假定有5个作业，在某时刻作业要求访问的页面顺序是4、1、2、3、1、2、4、1、3、2、1、3，若分配的物理块只有3块，回答下列问题： (1)解释什么情况下会发生缺页中断？(2分) (2)分别采用FIFO、LRU和clock页面分配算法，写出内存块中页面的变化情况，并求各种方式下缺页中断的次数和缺页率。(6分) 32.(7分)假设某通信的电文仅由4个字符组成，每个字符在电文中出现的频度分别为{32，7，24，2}。 (1)请为这4个字符设计哈夫曼编码。(4分) (2)该哈夫曼编码的平均码长是多少？与用2位二进制数(即00，01，10，11)对这4个字符进行等长编码相比，哈夫曼编码使该电文的总长平均压缩了多少？(3分) 33.(8分)请对如图所示的无向图： 写出它的邻接矩阵(4分)，并按照克鲁斯卡尔算法求其最小生成树(4分)。 34.(10分)设哈希函数为H(key)=key mod 13，试用关键字序列{39，25，15，54，26，24，14，21，37，38}构造哈希表。使用链地址法处理冲突，画出该哈希表的存储结构图(7分)；在等概率的情况下，计算查找成功时的平均查找长度(3分)。 35.(10分)有一个带头结点的单链表L，设计一个算法，使其元素递增有序。 36.(12分)有一组进程P1，P2，P3，P4，P5需要运行，它们需要的CPU时间和优先级如下表。假定这五个进程在0时刻按P5，P4，P3，P2，P1的顺序到达，在执行过程中不会发生等待，忽略进程调度所花费的时间，从0时刻开始进程调度，请回答下面的问题： 进程 要求的处理时间 优先级 P5 1 3 P4 4 4 P3 1 5 P2 3 1 P1 2 3 (1)画出采用先来先服务、短作业优先、时间片轮转的调度算法时，进程执行顺序的甘特图。(4分) (2)计算每个进程的周转时间和平均周转时间。(4分) (3)计算每个进程的等待时间和平均等待时间。(4分) 37.(14分)某快递仓库的工作人员分为两类：快递姐和快递哥，快递姐的任务是接收从外地送到本仓库的快件，快递哥的任务是将本仓库中的快件送到客户手里。该仓库一共能存放2000个快件包裹，当仓库未装满时，快递姐可以接收快件放入仓库，否则等待；当仓库不空时，快递哥可以从仓库中取走快件装车，否则等待。要求每次每个快递哥从仓库连续取出30件产品后，其他快递哥才可以从仓库中取快件，请用信号量和P，V操作实现快递姐和快递哥的操作互斥和同步，要求写出完整的过程；并指出所用信号量的含义和初值。 第 6 页 共 6 页