中国计量大学2019考研真题806数据结构与操作系统.pdf
数据结构与操作系统试卷 第 1 页 共 9 页 中国计量大学 2019 年硕士研究生招生考试试题 考试科目代码: 806 考试科目名称:数据结构与操作系统 所有答案必须写在报考点提供的答题纸上, 做在试卷或草稿纸上无效。 一、 单项选择题:130 小题,每小题 2 分,共 60 分。 1. 以下 T(n)表示各算法中最耗时操作的执行次数,n 表示数据量,请按照时间复杂度从小到大排列, 正确 的是() 。 T1(n) = 100n + 200log2n T2(n) = 3n2T3(n) = 10000000 T4(n) = 300log2n A. T10.5 时,需要扩大数组容量,一般为大于原容量 2 倍的最接近的质数,并用散列函数 h(x)=x % 表长 ,重新把数据散列到新数组中。请采用该方法 对原散列表进行扩容和重散列,并计算新的装载因子和查找成功情况下的平均查找长度 ASL。 (4) (5 分)如果原数据序列依次插入 到初始时刻为空树的方法,构造一棵平衡二叉查找(排序)树,请画出该树的构造过程,并计算在最终的这棵树 上,查找成功情况下的平均比较次数。 (5) (5 分)如果用线性表来存储该数 据序列,请计算在查找成功情况下的平均比较次数。 33. (10分)假定在一个处理机上执行的操作如下: 作业 估计服务时间 各作业到达时间 A 2 0 B 33 C 1 4 D 56 E 4 5 请给出简单图示说明,分别用 FCFS(先来先处理)和 R R (时间片轮转,假设时间片 q1) 两种 CPU 调度算法,实现这些作业的调度情况(注:不需要算出具体的周转时间和平均周转时间, 只需要用简图标出每个作业调度先后顺序和每个作业完成时间即可) 。 34.(20分)考虑下述页面走向:6,7,5,2,6,7,3,6,7,5,2,3 当分配的 内存物理块数量分别为 3 和 4 时 : ( 1) ( 6 分) FIFO(先进先出页面置换算法)的缺页次数分别是多少? ( 2) ( 6 分) OPT(最优页面置换算法 ) 的缺页次数分别是多少? ( 3) ( 6 分) LRU(最近最久未使用页面置换算法 )的缺页次数分别是多少? 上述各小题 要求写出详细的页面缺页和置换过程。 ( 4) ( 2 分)请问你能从这三种算法中发现什么现象? 数据结构与操作系统试卷 第 9 页 共 9 页 35. (10 分)在银行家算法中,若出现下述资源分配情况(5 个进程,资源 A/B/C 共 3类),假设系统有A类资源5个, B类资源7个,C类资源12个,某一时刻有以下分资源分配 Process Max(最大需求) Allocation(已分配) A B C A B C P1 41 3 21 2 P2 0 6 2 0 2 2 P3 1 22 00 1 P4 1 0 3 1 0 0 P5 357 1 2 5 (1) (7 分)该状态是否安全?若是,请给出安全序列, 要求写出详细推导过程 。若不是,也请详细说明原因。 (2) (3分)若P2提出请求Request(0,1,0)后,系统能否将资源分配 给它?为什么?( 能与不能都要求详细写出各自的理由 ) 【完】