2018年中国计量学院考研专业课试题806数据结构与操作系统.docx

1、一、单项选择题（每小题2分，共60分）1. 下面程序段的时间复杂度为（    ）。float fun(int n, float x)  float result = 1.0f;int num = n * n / 4;for(int i=0; i < num; +i)if( i % 2 = 0 )result *= x; return  result;AO( (n2/2)! )      B0(n2/4)     C0(n2/2)     DO(n2)2. 下列排序算法中，平均时间

2、复杂度最小的是（    ）。A基数排序    B直接插入排序    C快速排序   D希尔排序3. 关于线性表的描述错误的是（    ）。A. 采用顺序存储时，其存储地址必须是连续的B. 采用链式存储时，其存储地址可能是连续的C. 采用链式存储时，其存储地址必须是不连续的D. 采用链式存储时，其存储地址可能是不连续的4. 往队列中输入序列1,2,3,4,5，在若干入队与出队操作后，下列描述错误的是（   ）。A输出序列第一个元素肯定是1B队列中的数据有可能只有1,3C输出序列最后一个元素肯定是5

3、D队列中的数据有可能只有4,55. 往栈中输入序列1,2,3,4,5，在若干入栈与出栈操作后，下列描述错误的是（   ）。A最后出栈的元素肯定是1B栈有可能为空C栈中的数据有可能只有1,5D栈中的数据有可能只有26. 已知一棵完全二叉树的第4层有4个叶子节点（树根为第1层），则这棵完全二叉树的节点个数至少是（    ）。A11B24C23D287. 在电子地图中，为了给用户寻找最快的路线和最短的路线，使用哪种数据结构比较合适（    ）。A平衡二叉查找树 B哈希表  C图        D线性表

4、8. 关于邻接矩阵的描述正确的是（    ）。A有向图的邻接矩阵一定是非对称矩阵B. 无向图的邻接矩阵一定是对称矩阵C若图G的邻接矩阵是对称的，则G一定是无向图D有向图的邻接矩阵一定是下三角矩阵9. 下列排序算法中，时间复杂度最小的是（    ）。A基数排序    B. 直接插入排序    C冒泡排序    D归并排序10. 哪种数据结构适合折半(二分）查找算法（   ）。A散列表     B二叉查找树   C顺序表且有序   D链表且有序11.

5、 图1所示这棵二叉树的后序遍历结果是（     ）。AABCEFB. BEFCA C. BACEFD.  BAECF图1.二叉树12. 设有一个空的顺序队列(非循环队列），入队、出队操作顺序为：入队、入队、出队、入队、入队，则顺序队列的容量至少为 (     )。A2        B3       C4          D513. 若数据序列96，12，5，78，64，23，49，第一趟排序结果是：12，5，78，64，2

6、3，49，96，则该排序算法是（  ）。A冒泡排序   B直接插入排序  C归并排序    D快速排序14. 对数据 9，3，7，2，5进行排序时，第一趟的排序结果为：2，3，5，7，9，则采用的排序算法是（     ）。A 直接插入排序   B冒泡排序    C归并排序    D快速排序15. 把数据序列1，2，3，4，5，6，7通过插入操作构造二叉查找树，下面4种插入顺序构造了4棵二叉查找树，在这些树上查找数字8，比较次数最多的是（    ）。A4,2

7、,1,3,6,7,5B1,2,3,4,5,6,7C3,4,1,2,6,7,5 D4,2,1,3,6,5,716. 以下哪种特性不是操作系统的基本特性？( )    A并发性B.并行性C. 异步性D. 共享性17. 某基于动态分区存储管理的计算机，假设其主存容量为45MB(初始为空闲)，采用最佳适配（Best Fit）算法，分配和释放内存的顺序为：分配15MB,分配20MB,释放15MB,分配8MB,分配6MB,此时主存中最大空闲区的大小是(    )。    A. 9MB        B. 1

8、0MB        C. 7MB        D. 15MB18. 假设磁头当前位于100道，现有一个磁道访问请求序列为45，12，68，110，180，170，35，95。采用先来先服务调度（FCFS）算法得到的磁道访问序列是（  ）。A. 110, 170, 180, 95, 68, 45, 35, 12   B. 45, 12, 68, 110, 180, 170, 35, 95C. 110, 170, 180, 12, 35, 45, 68，95   D. 12, 35,

9、45, 68, 95，110, 170, 18019. 假设磁头当前位于100道，现有一个磁道访问请求序列为45，12，68，110，180，170，35，95。采用最短寻道时间优先调度（SSTF）算法得到的磁道访问序列是（  ）。A. 95，110, 170, 180, 68, 45, 35, 12   B. 45, 12, 68, 110, 180, 170，35, 95C. 110, 170, 180, 95, 12, 35, 45, 68   D. 12, 35, 45, 68, 95，110, 170, 18020. 假设磁头当前位于100道，正在向磁道

10、序号增加的方向移动。现有一个磁道访问请求序列为45，12，68，110，180，170，35，95。采用扫描调度（SCAN）算法得到的磁道访问序列是（  ）。A. 95，110, 170, 180, 68, 45, 35, 12   B. 45, 12, 68, 110, 180, 170, 35, 95C. 110, 170, 180, 95, 68，45，35, 12   D. 110, 170, 180, 12，35，45，68, 9521. 假设某一机器的内存有4G,硬盘为200G,请问使用虚拟内存技术后，其虚拟内容的容量为（  ）A. 4G &

11、nbsp; B. 8G  C. 200G   D. 204G22. 在基本分页存储管理中，若采用最佳页面置换算法OPT，则当进程分配到的物理块数目增加时，缺页中断的次数（   ）A. 可能减少，也可能不变   B.一定减少  C. 不变D.一定增加23. 设置当前工作目录的主要目的是（   ）。    A. 节省外存空间             B. 节省内存空间    C. 加快文件的检索速度      

12、 D. 加快文件本身的读/写速度24. 考虑以下表1结构：                           表1                        页号  块号03122431假设页的大小为512字节（ 即页内地址长度为9位），请把以下以十六进制表示的逻辑地址0x965，通过页表转换为物理地址（也用十六进制表示）是 （ &

13、nbsp;）。A. 0xA65     B. 地址转换错误   C. 0x965      D. 0x76525. 空闲链表法可用于(     )A.文件的空闲盘块组织      B.磁盘的设备调度C.CPU调度算法            D.请求分页虚拟管理中的页面置换26. 基本分页内存管理系统中，访问一条指令需要几次访问内存（  ）？    A. 3     B. 0 &

14、nbsp;  C. 1      D. 227. 对于某个活动进程而言，其运行的场所必须在(   )中。A. 内存B. 硬盘C. SWAPING交换区D. 输入井或输出井28. 下列算法中用于磁盘调度的是( )A. 最近最少使用LRU算法 B. FIFO算法C. 时间片轮转法RRD. 循环扫描算法(CSCAN)29. 在I/O设备管理中，通道是一种（  ）。 A.I/O端口    B.设备控制器    C. I/O专用处理机    D.软件工具30. 进程从阻塞状态进入就绪状

15、态的原因可能是( )A. 时间片用完   B. 正等待某一事件发生C.被选中占有处理机 D. 等待的事件已发生（或完成）二、综合应用题（共90分）。31.(25分)把数据序列73,23,44,99,21,78依次插入到二叉查找树中，（1） （5分）请画出最终的二叉查找树（2） （5分）请写出：上一步完成后，二叉查找树的后序遍历结果（3） （15分）请在下列编程语言中选择任意一种（C、C+、Java），写出中序遍历二叉查找树的函数，函数的输入参数为树根结点，结点类型需要自己定义。32.(25分)把数据序列73,23,44,99,21,78放入表长为7的散列（哈希）表中，散列函数h(x)

16、=x % 7,用双散列（二次散列Double Hashing）探测法解决冲突，探测函数为f(i)= i * ( 7 x % 7 )，在依次插入数据时，用上述探测法解决冲突，会碰到始终无法解决冲突的情况，即无法为新数据找到合适的存放位置，这时需要进行重散列(Rehashing)，请完成以下问题。（1） （5分）请画出重散列前的散列表（2） （5分）重散列时，请写出合理的新散列表的长度、散列函数（但探测函数不变）（3） （5分）请画出重散列后的散列表（4） （5分）请写出：在上一步散列表上查找成功情况下的平均比较次数。（5） （5分）如果同样的数据序列放在链表中，请写出查找成功情况下的平均比较次数

17、。33.(10分)在银行家算法中，若出现下述资源分配情况(5个进程，3类资源)：Process Allocation（已分配），MAX（最大需求），Available（系统剩余资源）A   B   C   A   B    C         A  B  CP10   2 3       2   2   10  1  3  2  P20   2   22 &

18、nbsp; 5   4P33   2   2 3   10  7P41   0   0       1   4   5P50   2   3           0   4   4（1） (7分) 该状态是否安全？若是，请给出安全序列,要求写出详细推导过程。若不是，也请详细说明原因。（2） （3分）若P2提出请求Request(1，1，1)后，系统能否将资源分配给它？为什么？（能与不能都

19、要求详细写出各自的理由）34.(20分)考虑下述页面走向：1，2，6，4，1，2，7，1，2，6，4，7当分配的内存物理块数量分别为3和4时，试问：（1） （6分）FIFO（先进先出页面置换算法）的缺页次数分别是多少？（2） （6分）OPT(最优页面置换算法) 的缺页次数分别是多少？（3） （6分）LRU(最近最少使用页面置换算法)的缺页次数分别是多少？上述各小题要求写出详细的页面缺页和置换过程。（4） （2分）请问你能从中发现什么现象？35.(10分)假定在一个处理机上执行的操作如下：作业               估计

20、服务时间    各作业到达时间A                      3           0B                      4           1C            

21、          1           2D                      5           3E                      2           4请给出简单图示说明，分别用FCFS（先来先处理）和RR (时间片轮转,假设时间片q1)两种CPU调度算法，实现这些作业的调度情况（注：不需要算出具体的周转时间和平均周转时间，只需要用简单的图示，标出每个作业调度先后顺序和每个作业完成时间即可）。【完】数据结构与操作系统试卷  第 9 页  共6页