DOC《一、单项选择题（每小题2分,共60分）》

一、单项选择题(每小题2分,共60分) 下面程序段的时间复杂度为( ).

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;

} A.O( (n2/2)B.0(n2/4) C.0(n2/2) D.O(n2) 下列排序算法中,平均时间复杂度最小的是( ). A.基数排序 B.直接插入排序 C.快速排序 D.希尔排序 关于线性表的描述错误的是( ). A. 采用顺序存储时,其存储地址必须是连续的 B. 采用链式存储时,其存储地址可能是连续的 C. 采用链式存储时,其存储地址必须是不连续的 D. 采用链式存储时,其存储地址可能是不连续的 往队列中输入序列{1,2,3,4,5},在若干入队与出队操作后,下列描述错误的是( ). A.输出序列第一个元素肯定是1 B.队列中的数据有可能只有1,3 C.输出序列最后一个元素肯定是5 D.队列中的数据有可能只有4,5 往栈中输入序列{1,2,3,4,5},在若干入栈与出栈操作后,下列描述错误的是( ). A.最后出栈的元素肯定是1 B.栈有可能为空 C.栈中的数据有可能只有1,5 D.栈中的数据有可能只有2 已知一棵完全二叉树的第4层有4个叶子节点(树根为第1层),则这棵完全二叉树的节点个数至少是( ). A.11 B.24 C.23 D.28 在电子地图中,为了给用户寻找最快的路线和最短的路线,使用哪种数据结构比较合适( ). A.平衡二叉查找树 B.哈希表 C.图D.线性表 关于邻接矩阵的描述正确的是( ). A.有向图的邻接矩阵一定是非对称矩阵 B. 无向图的邻接矩阵一定是对称矩阵 C.若图G的邻接矩阵是对称的,则G一定是无向图 D.有向图的邻接矩阵一定是下三角矩阵 下列排序算法中,时间复杂度最小的是( ). A.基数排序 B. 直接插入排序 C.冒泡排序 D.归并排序 哪种数据结构适合折半(二分)查找算法( ). A.散列表 B.二叉查找树 C.顺序表且有序 D.链表且有序 图1所示这棵二叉树的后序遍历结果是( ). A.ABCEF B. BEFCA C. BACEF D. BAECF 图1.二叉树 设有一个空的顺序队列(非循环队列),入队、出队操作顺序为:入队、入队、出队、入队、入队,则顺序队列的容量至少为 ( ). A.2 B.3 C.4 D.5 若数据序列96,12,5,78,64,23,49,第一趟排序结果是:12,5,78,64,23,49,96,则该排序算法是( ). A.冒泡排序 B.直接插入排序 C.归并排序 D.快速排序 对数据 9,3,7,2,5进行排序时,第一趟的排序结果为:2,3,5,7,9,则采用的排序算法是( ). 直接插入排序 B.冒泡排序 C.归并排序 D.快速排序 把数据序列1,2,3,4,5,6,7通过插入操作构造二叉查找树,下面4种插入顺序构造了4棵二叉查找树,在这些树上查找数字8,比较次数最多的是( ). A.4,2,1,3,6,7,5 B.1,2,3,4,5,6,7 C.3,4,1,2,6,7,5 D.4,2,1,3,6,5,7 以下哪种特性不是操作系统的基本特性?( ) A.并发性 B.并行性 C. 异步性 D. 共享性 某基于动态分区存储管理的计算机,假设其主存容量为45MB(初始为空闲),采用最佳适配(Best Fit)算法,分配和释放内存的顺序为:分配15MB,分配20MB,释放15MB,分配8MB,分配6MB,此时主存中最大空闲区的大小是( ). A. 9MB B. 10MB C. 7MB D. 15MB 假设磁头当前位于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,

95 C. 110, 170, 180, 12, 35, 45, 68,95 D. 12, 35, 45, 68, 95,110, 170,