1、一、 单项选择题：140小题，每小题2分，共80分。在每小题给出的四个选项中，请选出一项最符合题目要求的。1. 函数fun的时间复杂度为（ ）。float fun(float x, int n) float result = 1.0f;for( i=0; i n*n/2; +i) result *= x; return resultAO( (n2/2)! ) B0(2log2n) C0(n2/2) DO(n2)2. 下列排序算法中，需要额外辅助存储空间最多的是（ ）。A归并排序 B快速排序 C堆排序 D直接插入排序3. 以下数据结构中，不属于线性表的是（ ）。A. 队列 B. 栈 C. 图D.
2、 循环链表4. 下面关于栈的描述中，错误的是（ ）。A先进后出B两头都可以插入和删除C可以用数组来实现D可以用链表来实现5. 关于环形（循环）队列，错误的是（ ）。A先进先出 B用数组来实现C可以提高空间的利用率D用循环链表来实现6. 层数为8的二叉树其结点个数最多有（ ）。A1023 B511 C255 D1277. 有100个结点的无向图要确保是一个连通图至少应有（ ）。A101条边 B99条边 C50条边 D6条边8. 关于图的描述，错误的是（ ）。 A有向图的邻接矩阵一定是对称矩阵 B. 完全图中的边一定比连通图中的边多 C深度优先搜索的结果可能不唯一 D广度优先搜索的结果可能不唯一9
3、. 下列排序算法中，哪个是不稳定的（不稳定指的是：关键字相同的两个数据，排序后它们的先后位置会变化）（ ）。A希尔排序 B简单选择排序 C插入排序 D冒泡排序10. 二叉查找树中有1023个结点，查找其中一个数据时，描述正确的是（ ）。A至少要比较10次B最多比较10次C不可能超过10次D如果是平衡二叉查找树，可能要比较1023次11. 图1所示这棵树的中序遍历结果是（ ）。AABCDEFB. DBACEF C. DBAECFD. BACCEF 图1.树12. 往栈中输入序列1,2,，n后再逐个输出，则输出序列的最后一个元素是( )。A不确定 Bn-1 Cn D113. 假设N个数据已经放在不
4、同的数据结构，然后进行查找，下列描述错误的是：（ ）。A如果采用合适的散列表，其查找速度最快B用二叉查找树来查找比用折半查找要快C链表上的查找要比二叉查找树 快D平衡二叉查找树上的查找要比普通二叉查找树 快14. 若数据序列5, 96, 12, 64, 78, 23, 49是采用下列方法之一得到的第一趟排序后的结果，则该排序算法是（ ）。A冒泡排序 B直接插入排序 C快速排序 D归并排序15. 对数据 8，1，4，9，6，3，5，2，7，0进行排序时，第一趟的排序结果如下：0,1,4,2,5,3,6,9,7,8；则采用的排序算法是（ ）。A快速排序 B直接插入排序 C冒泡排序 D归并排序16.
5、 把数据1，2，3，4，5，6，7通过插入操作构造一棵二叉查找树，下列描述错误的是（ ）。A按照3,4,1,2,6,7,5的插入顺序构造的二叉查找树，树高为3 B按照4,2,1,3,6,5,7的插入顺序构造的二叉查找树的查找效率最高C按照3,4,1,2,6,7,5的插入顺序构造的二叉查找树是平衡二叉树D按照4,2,1,3,6,5,7的插入顺序构造的二叉查找树是平衡二叉树17. 已知一个数据序列中有1024个数据，且其已经有序排列，若采用最快的查找算法和必要的存储结构，在该序列中要查找一个数据元素，则平均比较次数最少要多少次（ ）。A512B. 256C. 10D. 118. 一棵满二叉树共有1
6、1层（树根为第一层），则叶子节点个数为（ ）。A. 0B. 2048C. 1024D. 51219. 若要检查文件中的括号是否匹配，采用的数据结构应该是（ ）。A 图B. 二叉树C. 栈D. 栈20. 快递员每天要送很多包裹给客户，为了提高效率，缩短总路程长度，请问该选用什么样的数据结构来设计路线（ ）。A线性表B. 图C.队列D. 二叉树21操作系统是一种( ) A实用软件 B.系统软件 C. 应用软件 D. 工具软件 22. 设置当前工作目录的主要目的是（ ）。 A. 节省外存空间 B. 节省内存空间 C. 加快文件的检索速度 D. 加快文件的读/写速度23. 进程从阻塞状态进入就绪状态的
7、原因可能是( )A. 被选中占有处理机 B. 等待某一事件发生C. 等待的事件已发生 D. 时间片用完24. 在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数无变化的情况是( )A.无上邻空闲区，也无下邻空闲区 B.有上邻空闲区，也有下邻空闲区C.有下邻空闲区但无上邻空闲区;或有上邻空闲区但无下邻空闲区D. 以上三种都可以25. 假设某一机器的内存有2G,硬盘为300G,请问使用虚拟内存技术后，其虚拟内容的容量为（ ） A. 2G B. 4G C. 300G D.302G26. 在基本分段存储管理中，逻辑地址转换为物联地址时，若段
8、号超过段表长度，则会引起( )。A. 输入输出中断 B. 缺段中断 C. 越界中断 D. 缺页中断27. 某个进程运行在( )中。A. 内存 B. 硬盘C. SWAPING交换区 D. 硬盘中的某个子目录28. 成组链接法可用于( )A.磁盘空闲空间的管理 B.磁盘的驱动调度C.文件目录的查找 D.页式虚拟存贮管理中的页面调度29. 下列算法中用于磁盘调度的是( )A. SSTF优先级高者优先算法 B. FIFO先进先出算法C. 时间片轮转法RRD. 最短寻道时间优先30. 通道是一种（ ）。A. I/O端口 B. 数据通道C. I/O专用处理机 D. 软件工具31.假设磁头当前位于100道，
9、正在向磁道序号增加的方向移动。现有一个磁 道访问请求序列为28，55，12，68，110，180，170，195，采用先来先服务调度（FCFS）算法得到的磁道访问序列是（ ）。 A. 110,170,180,195,68,55,28,12 B. 28,55,12,68,110,180,170,195 C. 110,170,180,195,12,28,55,68 D. 12,28,55,68,110,170,180,19532. 在通过索引分配技术时，若某一文件的索引块如下图所示：11421-1-1请问，该索引文件大小总共占有磁盘空间（ ）块？ A. 4 B. 7 C. 5 D. 633. 在基
10、本分页存储管理中，若采用最佳页面置换算法OPT，则当进程分配到的物理块数增加时，缺页中断的次数会（ ）A. 一定减少 B.一定不会增加 C. 无影响 D.可能增加也可能减少34. 采用（ ）不会产生内部碎片。A. 分页式存储管理 B. 分段式存储管理C. 固定分区式存储管理 D. 虚拟分页存储管理35. 某基于动态分区存储管理的计算机，其主存容量为55MB(初始为空闲)，采用最佳适配（Best Fit）算法，分配和释放的顺序为：分配15MB,分配30MB,释放15MB,分配8MB,分配6MB,此时主存中最大空闲分区的大小是( )。 A. 10MB B. 9MB C. 7MB D. 15MB36
11、. 某计算机系统中有K台打印机，由4个进程竞争使用，每个进程最多需要3台打印机。该系统不可能发生死锁的K的最小值是（ ）。 A. 6 B. 10 C. 8 D. 937. 采用SPOOLing技术的目的是（ ）。A. 提高独占设备的利用率 B. 提高主机效率C. 减轻用户编程负担 D. 提高程序的运行速度38考虑以下页表结构： 页号 块号 02152139 假设页的大小为512字节, 即页内地址长度为 9 位，请把以下以十六进制表示的逻辑地址0x967，通过页表转换为物理地址（也用十六进制表示）是 （ ）。A. 0x3417 B. 地址转换错误 C. 0x367 D. 0x567 39. 以下
12、不是设备分配算法的是（ ）A. 先来先服务 B. 短作业优先C. 优先级高的优先 D. 以上几种都不是40. 对两个并发进程，其互斥信号量为mutex；初值为1，若mutex0，则表明（ ）。A没有进程进入临界区B有一个进程进入临界区但没有进程处于阻塞状态C一个进程进入临界区而另一个进程正处于等待进入临界区状态D有两个进程进入临界区二、 综合应用题：4145小题，共70分。41.带有头节点的单链表，其节点结构为datanext带有头结点的单链表如下图所示请设计一个算法对两个有序单链表L1，L2进行求交的操作，得到新的链表L3，L3仍然保持有序的状态，要求：（1） 请描述算法的基本设计思想（5分
13、）（2） 用伪代码描述算法的详细实现步骤（5分）（3） 根据设计思想和实现步骤，采用某一程序设计语言写一个函数来实现该算法，请先给出结点类型的定义。（5分）（4） 请采用某一程序设计语言写一个函数，其功能是：遍历单链表，输出所有结点中的data值。（5分）（5） 请采用某一程序设计语言写一个函数，其功能是：创建空链表。（5分）42. 现有数据序列4371，1323,6173，4199,4344,9679,1989和散列函数h(x)=x mode 10。（1）请画出用分离链接法表示的散列表（5分）（2）请画出用平方探测法f(i)=i*i表示的散列表（5分）（3）请计算前两题中散列表的装载因子和查
14、找成功的平均查找长度ASL（5分）43. 在银行家算法中，若出现下述资源分配情况(5个进程，4类资源)：process Max (最大需求) Allocation（已分配） Available（系统资源）A B C D A B C DA B C DP12 7 5 0 1 0 0 0 1 6 2 2P20 6 6 10 0 0 1 4 P33 6 10 9 1 3 5 4P40 9 8 4 0 3 3 2P50 0 4 3 0 0 3 1试问：（1）(6分) 该状态是否安全？若是，请给出其中一个安全序列，若不是，也请说明原因。要求：是否安全状态均要求写出具体推导过程。（2）（4分）若P3提出请求
15、Request(1，2，1,1)，系统能否将资源分配给它？为什么？要求详细说明你的理由。 44.(10分) 考虑下述页面走向： 6，7，2，1，6，7，5，6，7，2，1，5当内存物理块数量分别为3和4时，试问FIFO（先进先出）、LRU(最近最少使用)算法这两种内存置换算法的缺页次数和置换次数分别是多少？最后，比较这两种算法后，你有何发现？上述过程要求分别写出详细的置换过程。45.（10分）用类C语言来完成程序，尝试用学过的信号量操作解决以下问题： 有一个家庭，有父、子、女三人，爸爸负责不停地把水果放到盘中，假设一次只能允许放一个水果，水果品种分为苹果和香蕉两种，限制条件是儿子只能从盘中取苹果吃，女儿只能从盘中取香蕉吃，请你用信号量WAIT和SIGNAL操作实现这三个人的进程并发操作，假设开始时盘中为空。 【完】数据结构与操作系统试卷 第7页 共7页
