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页