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页
