数据结构与操作系统试卷 第 1 页 共 6 页一、单项选择题（每小题 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( (n 2/2)! ) B0(n 2/4) C0(n 2/2) DO(n 2)2. 下列排序算法中，平均时间复杂度最小的是（ ） 。A基数排序 B直接插入排序 C快速排序 D希尔排序3. 关于线性表的描述错误的是（ ） 。A. 采用顺序存储时，其存储地址必须是连续的B. 采用链式存储时，其存储地址可能是连续的C. 采用链式存储时，其存储地址必须是不连续的D. 采用链式存储时，其存储地址可能是不连续的4. 往队列中输入序列1,2,3,4,5，在若干入队与出队操作后，下列描述错误的是（ ） 。A输出序列第一个元素肯定是 1 B队列中的数据有可能只有1,3数据结构与操作系统试卷 第 2 页 共 6 页C输出序列最后一个元素肯定是 5 D队列中的数据有可能只有4,55. 往栈中输入序列1,2,3,4,5，在若干入栈与出栈操作后，下列描述错误的是（ ） 。A最后出栈的元素肯定是 1B栈有可能为空C栈中的数据有可能只有 1,5D栈中的数据有可能只有 26. 已知一棵完全二叉树的第 4层有 4个叶子节点（树根为第 1层） ，则这棵完全二叉树的节点个数至少是（ ） 。A11 B24 C23 D287. 在电子地图中，为了给用户寻找最快的路线和最短的路线，使用哪种数据结构比较合适（ ） 。A平衡二叉查找树 B哈希表 C图 D线性表8. 关于邻接矩阵的描述正确的是（ ） 。A有向图的邻接矩阵一定是非对称矩阵B. 无向图的邻接矩阵一定是对称矩阵C若图 G的邻接矩阵是对称的，则 G一定是无向图D有向图的邻接矩阵一定是下三角矩阵9. 下列排序算法中，时间复杂度最小的是（ ） 。A基数排序 B. 直接插入排序 C冒泡排序 D归并排序数据结构与操作系统试卷 第 3 页 共 6 页10. 哪种数据结构适合折半(二分）查找算法（ ） 。A散列表 B二叉查找树 C顺序表且有序 D链表且有序11. 图 1所示这棵二叉树的后序遍历结果是（ ） 。AABCEF B. BEFCA C. BACEF D. BAECF图 1.二叉树12. 设有一个空的顺序队列(非循环队列） ，入队、出队操作顺序为：入队、入队、出队、入队、入队，则顺序队列的容量至少为 ( )。A2 B3 C4 D513. 若数据序列 96，12，5，78，64，23，49，第一趟排序结果是：12，5，78，64，23，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，比较次数据结构与操作系统试卷 第 4 页 共 6 页数最多的是（ ） 。A4,2,1,3,6,7,5 B1,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. 10MB 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, 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, 180数据结构与操作系统试卷 第 5 页 共 6 页20. 假设磁头当前位于 100道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为 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 B. 8G C. 200G D. 204G22. 在基本分页存储管理中，若采用最佳页面置换算法 OPT，则当进程分配到的物理块数目增加时，缺页中断的次数（ ）A. 可能减少，也可能不变 B.一定减少 C. 不变 D.一定增加23. 设置当前工作目录的主要目的是（ ） 。A. 节省外存空间 B. 节省内存空间C. 加快文件的检索速度 D. 加快文件本身的读/写速度24. 考虑以下表 1结构：表 1页号 块号0 31 2数据结构与操作系统试卷 第 6 页 共 6 页2 43 1假设页的大小为512字节（ 即页内地址长度为9位） ，请把以下以十六进制表示的逻辑地址0x965，通过页表转换为物理地址（也用十六进制表示）是 （ ） 。A. 0xA65 B. 地址转换错误 C. 0x965 D. 0x76525. 空闲链表法可用于( )A.文件的空闲盘块组织 B.磁盘的设备调度C.CPU调度算法 D.请求分页虚拟管理中的页面置换26. 基本分页内存管理系统中，访问一条指令需要几次访问内存（ ）？A. 3 B. 0 C. 1 D. 227. 对于某个活动进程而言，其运行的场所必须在( )中。A. 内存 B. 硬盘C. SWAPING交换区 D. 输入井或输出井28. 下列算法中用于磁盘调度的是( )A. 最近最少使用 LRU算法 B. FIFO算法C. 时间片轮转法 RR D. 循环扫描算法(CSCAN)29. 在 I/O设备管理中，通道是一种（ ） 。A.I/O端口 B.设备控制器 C. I/O 专用处理机 D.软件工具30. 进程从阻塞状态进入就绪状态的原因可能是( )数据结构与操作系统试卷 第 7 页 共 6 页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)=x % 7,用双散列（二次散列 Double Hashing）探测法解决冲突，探测函数为 f(i)= i * ( 7 x % 7 )，在依次插入数据时，用上述探测法解决冲突，会碰到始终无法解决冲突的情况，即无法为新数据找到合适的存放位置，这时需要进行重散列(Rehashing)，请完成以下问题。（1） （5 分）请画出重散列前的散列表（2） （5 分）重散列时，请写出合理的新散列表的长度、散列函数（但探测函数不变）（3） （5 分）请画出重散列后的散列表（4） （5 分）请写出：在上一步散列表上查找成功情况下的平均比较次数。数据结构与操作系统试卷 第 8 页 共 6 页（5） （5 分）如果同样的数据序列放在链表中，请写出查找成功情况下的平均比较次数。33.(10分)在银行家算法中，若出现下述资源分配情况(5 个进程，3 类资源)：Process Allocation（已分配） ，MAX（最大需求） ，Available（系统剩余资源）A B C A B C A B CP1 0 2 3 2 2 10 1 3 2 P2 0 2 2 2 5 4P3 3 2 2 3 10 7P4 1 0 0 1 4 5P5 0 2 3 0 4 4（1） (7分) 该状态是否安全？若是，请给出安全序列,要求写出详细推导过程。若不是，也请详细说明原因。（2） （3 分）若 P2提出请求 Request(1，1，1)后，系统能否将资源分配给它？为什么？（能与不能都要求详细写出各自的理由）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(最近最少使用页面置换算法)的缺页次数分别是多少？数据结构与操作系统试卷 第 9 页 共 6 页上述各小题要求写出详细的页面缺页和置换过程。（4） （2 分）请问你能从中发现什么现象？35.(10分)假定在一个处理机上执行的操作如下：作业 估计服务时间 各作业到达时间A 3 0B 4 1C 1 2D 5 3E 2 4请给出简单图示说明，分别用 FCFS（先来先处理）和 RR (时间片轮转,假设时间片 q1)两种 CPU调度算法，实现这些作业的调度情况（注：不需要算出具体的周转时间和平均周转时间，只需要用简单的图示，标出每个作业调度先后顺序和每个作业完成时间即可） 。【完】