848 数据结构及操作系统

上海理工大学硕士研究生入学

《数据结构及操作系统》考试大纲

第一部分：数据结构

一、参考书目

数据结构（第二版），严蔚敏主编，2006，清华大学出版社。

二、考试内容要求

1、了解数据结构及其分类、数据结构与算法的密切关系。

2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。

3、掌握设计算法的步骤和算法分析方法。

4、掌握数据结构在排序和查找等常用算法中的应用。

5、初步掌握文件组织方法和索引技术。

三、考试内容

1、数据结构基本概念及简单的算法分析

1)什么是数据结构

2) 抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；

面向对象的概念；用于描述数据结构的语言

3) 数据结构的抽象层次

4) 算法定义

5) 性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；

空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂.

2、数组

1)作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数

组；数组的顺序存储方式

2)顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和

删除；使用顺序表的事例

3) 字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配

3、链表

1) 单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带

表头结点的单链表；用模板定义的单链表类；单链表的游标类；静态链表

2) 循环链表：循环链表的类定义；用循环链表解约瑟夫问题；多项式及其

相加：多项式的类定义；多项式的加法

3) 双向链表

4、栈和队列

1) 栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示

2) 队列：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表

示；3) 队列的应用举例

4) 优先级队列：优先级队列的定义；优先级队列的存储表示

5、递归

1) 递归的概念

2) 迷宫问题

3) 递归过程与递归工作栈

4) 利用栈实现的迷宫问题非递归解法

5) 广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；

广6) 义表的访问算法；广义表的递归算法

6、树与森林

1) 树和森林的概念：树的定义；树的术语；树的抽象数据类型

2) 二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型

3) 二叉树的表示：数组表示；链表存储表示

4) 二叉树遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的事例；

二叉树遍历的游标类；不用栈的二叉树中序遍历算法

5) 线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化

6) 堆：堆的定义；堆的建立；堆的插入与删除

7) 树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历

二叉树的计数

8) 霍夫曼树：路径长度；霍夫曼树；霍夫曼编码

7、集合与搜索

1) 集合及其表示：集合基本概念；以集合为基础的抽象数据类型；用位向

量实现集合抽象据类型；用有序链表实现集合的抽象数据类型

2) 等价类：等价关系与等价类；确定等价类的链表方法；并查集

3) 简单的搜索结构：搜索的概念；静态搜索结构；顺序搜索；基于有序顺

序表的对分搜索

4) 二叉搜索树：定义；二叉搜索树上的搜索；二叉搜索树的插入；二叉搜

索树的删除；与二叉搜索树相关的中序游标类

5) AVI树：AVI树的定义；平衡化旋转；AVI树的插入和删除；AVI树的高度

8、图

1) 图的基本概念：图的基本概念；图的抽象数据类型

2) 图的存储表示：邻接矩阵；邻接表；邻接多重表

3) 图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；重连通分量

4) 最小生成树：克鲁斯卡尔算法；普里姆算法

5) 活动网络：用顶点表示活动的网络；用边表示活动的网络

9、排序

1) 插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序

2) 交换排序：起泡排序；快速排序

3) 选择排序：直接选择排序；锦标赛排序；堆排序

4) 归并排序：归并；迭代的归并排序算法；递归的表归并排序

5) 基数排序：多关键码排序；链式基数排序

6) 外排序：外排序的基本过程；k路平衡归并；初始归并段的生成；最佳归并树

10、索引与散列结构

1) 静态索引结构：线性索引；倒排表；m路静态查找树

2) 动态索引结构：动态的m路查找树；b_树；b_树的插入；b_树的删除；b+树

3) 散列：词典的抽象数据类型；散列表与散列方法；散列函数；处理溢出

的闭散列方法；处理溢出的开散列方法；散列表分析

第二部分：操作系统

一、参考书目

汤小丹等，《计算机操作系统》（第三版），西安电子科技大学出版社，2007年

二、考试内容范围

要求考生重点掌握操作系统设计方法与实现技术，能够运用所学的操作系统原理、方法与技术分析问题和解决问题。

1、操作系统引论

操作系统的目标与作用；操作系统的发展与分类；操作系统的基本特性与主要功能。

2、进程管理

进程的基本概念；进程控制；进程同步（进程同步的基本概念、实现临界区互斥的基本方法、信号量、经典同步问题）；进程通信（共享存储系统、消息传递系统、管道通信）；线程概念；线程的实现。

3、处理机调度

调度的基本概念；调度的基本准则；典型调度算法（先来先服务调度算法、短作

业（短进程、短线程）优先调度算法、时间片轮转调度算法、优先级调度算法、高响应比优先调度算法、多级反馈队列调度算法）。

4、死锁

死锁的基本概念；死锁预防；死锁避免（系统安全状态、银行家算法）；死锁检测与解除。

5、存储器管理

程序装入与链接；连续分配管理方式；非连续分配管理方式（基本分页存储管理方式、基本分段存储管理方式；段页式存储管理方式）；虚拟存储器的基本概念；请求分页存储管理方式；请求分段存储管理方式；页面置换算法（最佳置换算法（OPT）、最近最久未少使用置换算法（LRU）、时钟置换算法（CLOCK））。

6、设备管理

I/O系统；I/O 控制方式；缓冲管理；I/O软件；设备分配；磁盘存储器的管理（磁盘性能、磁盘调度、磁盘高速缓存）。

7、文件管理

文件与文件系统的基本概念；文件的逻辑结构（顺序文件；索引文件；索引顺序文件）；外存分配方式（连续分配、链接分配、索引分配）；文件控制块和索引节点；目录结构；文件存储空间的管理方法；文件共享；文件保护。

三、试卷结构

基本知识测试占50%，综合应用测试占50%。

命题着重考察考生对基本概念、基本知识和基本理论的掌握情况，以及对基本方法的运用能力。

(完整版)操作系统基础知识点详细概括

第一章： 1. 什么是操作系统？OS的基本特性是？主要功能是什么 OS是控制和管理计算机硬件和软件资源，合理组织计算机工作原理以及方程用户的功能的集合。特性是：具有并发，共享，虚拟，异步的功能，其中最基本的是并发和共享。主要功能：处理机管理，存储器管理，设备管理，文件管理，提供用户接口。 2. 操作系统的目标是什么？作用是什么？ 目标是：有效性、方便性、可扩充性、开放性 作用是：提供用户和计算机硬件之间的接口，提供对计算机系统资源的管理，提供扩充机器 3. 什么是单道批处理系统？什么是多道批处理系统？ 系统对作业的处理是成批的进行的，且在内存中始终保持一道作业称此系统为单道批处理系统。 用户所提交的作业都先存放在外存上并排成一个队列，然后，由作业调度程序按一定的算法从后备队列中选择若干个调入作业内存，使他们共享CPU和系统中的各种资源。 4 ?多道批处理系统的优缺点各是什么？ 优点：资源利用率高，系统吞吐量大。缺点：平均周转时间长，无交互能力。 引入多道程序技术的前提条件之一是系统具有终端功能，只有有中断功能才能并发。 5. 什么是分时系统？特征是什么？ 分时系统是指，在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互的方式使用计算机，共享主机中的资源。 特征：多路性、独立性、及时性、交互性 *有交互性的一般是分时操作系用，成批处理无交互性是批处理操作系统，用于实时控制或实时信息服务的是实时操作系统，对于分布式操作系统与网络操作系统，如计算机之间无主次之分就是分布式操作系统，因为网络一般有客户-服务器之分。 6. 什么是实时操作系统？ 实时系统：系统能及时响应外部事件的请求，在规定的时间内处理完。按照截止时间可以分为1硬实时任务（必须在截止时间内完成）2软实时任务（不太严格要求截止时间） 7用户与操作系统的接口有哪三种？ 分为两大类：分别是用户接口、程序接口。 用户接口又分为：联机用户接口、脱机用户接口、图形用户接口。 8. 理解并发和并行？并行（同一时刻）并发（同一时间间隔） 9. 操作系统的结构设计 1 ?无结构操作系统，又称为整体系统结构，结构混乱难以一节，调试困难，难以维护 2?模块化os结构，将os按功能划分为一定独立性和大小的模块。是os容易设计，维护, 增强os的可适应性，加速开发工程 3?分层式os结构，分层次实现，每层都仅使用它的底层所提供的功能 4. 微内核os结构，所有非基本部分从内核中移走，将它们当做系统程序或用户程序来实现，剩下的部分是实现os核心功能的小内核，便于扩张操作系统，拥有很好的可移植性。 第二章： 1 ?什么叫程序？程序顺序执行时的特点是什么？ 程序：为实现特殊目标或解决问题而用计算机语言编写的命令序列的集合特点：顺序性、封闭性、可再现性 2. 什么是前趋图？（要求会画前趋图）P35图2-2 前趋图是一个有向无循环图，记为DAG ,用于描述进程之间执行的前后关系。 3?程序并发执行时的特征是什么？ 特征：间断性、失去封闭性、不可再现性

《数据结构与操作系统》试题.doc

谢谢阅读一、单项选择题：1～40小题，每小题2分，共80分。在每小题给出的四 个选项中，请选出一项最符合题目要求的。 1.在下面的程序段中，时间复杂度为（）。 int fun( int n) { if( n = = 1 ) return 1; return n * fun( n - 1 ); } A．O( 2n ) B．0(nlogn) C．0(n2) D．O(n) 2.下列排序算法中，平均时间复杂度最小的是（）。 A．归并排序B．起泡排序 C．简单选择排序 D．直接插入排序 3.关于线性表的描述正确的是（）。 A. 采用顺序存储时，随机存取的时间复杂度是O(1) B. 采用链式存储时，随机存取的时间复杂度是O(1) C. 采用顺序存储时，其存储地址一定是不连续的 D. 采用链式存储时，其存储地址一定是不连续的 4.往队列中输入序列{1,2,3,4}，然后出队1个数字，则出队的数字是（）。 A．4 B．3 C．1 D．不确定 5.往栈中输入序列{1,2,3,4}，然后出栈1个数字，则出栈的数字是（）。 A．4 B．3 C．1 D．不确定 6.假设二叉排序（查找）树上有n个节点，树的高度为h，则查找的平均 时间复杂度是（）。 A．O( n ) B．0(nlogn) C．0(logn) D．O(h) 7.有10个节点的无向图，至少需要多少条边才能成为一个连通图（）。 A．5 B．45 C．9 D．10 8.关于邻接矩阵，下列说法中错误的是（）。 A．有向图的邻接矩阵不一定是对称矩阵 B. 无向图的邻接矩阵不一定是对称矩阵 C．若图G的邻接矩阵是对称的，则G不一定是无向图 D．若图G的邻接矩阵是对称的，则G不一定是有向图 9.折半查找算法中查找的时间复杂度是（）。 A．O( n ) B．0(nlogn) C．0(logn) D．O(n2) 谢谢阅读

数据库设计词汇对照表

数据库设计词汇对照表 1. Access method（访问方法）：此步骤包括从文件中存储和检索记录。 2. Alias（别名）：某属性的另一个名字。在SQL中，可以用别名替换表名。 3. Alternate keys（备用键，ER/关系模型）：在实体/表中没有被选为主健的候选键。 4. Anomalies（异常）参见更新异常（update anomalies） 5. Application design（应用程序设计）：数据库应用程序生命周期的一个阶段，包括设计用户界面以及使用和处理数据库的应用程序。 6. Attribute（属性）（关系模型）：属性是关系中命名的列。 7. Attribute（属性）（ER模型）：实体或关系中的一个性质。 8. Attribute inheritance（属性继承）：子类成员可以拥有其特有的属性，并且继承那些与超类有关的属性的过程。 9. Base table（基本表）：一个命名的表，其记录物理的存储在数据库中。 10. Binary relationship（二元关系）：一个ER术语，用于描述两个实体间的关系。例如，panch Has Staff。 11. Bottom-up approach（自底向上方法）：用于数据库设计，一种设计方法学，他从标识每个设计组建开始，然后将这些组件聚合成一个大的单元。在数据库设计中，可以从表示属性开始底层设计，然后将这些属性组合在一起构成代表实体和关系的表。 12. Business rules（业务规则）：由用户或数据库的管理者指定的附加规则。 13. Candidate key（候选键，ER关系模型）：仅包含唯一标识实体所必须得最小数量的属性/列的超键。 14. Cardinality（基数）：描述每个参与实体的可能的关系数目。 15. Centralized approach（集中化方法,用于数据库设计）：将每个用户试图的需求合并成新数据库应用程序的一个需求集合 16. Chasm trap（深坑陷阱）：假设实体间存在一根，但某些实体间不存在通路。 17. Client（客户端）：向一个或多个服务器请求服务的软件应用程序。 18. Clustering field（群集字段）：记录总的任何用于群集（集合）航记录的非键字段，这些行在这个字段上有相同的值。 19. Clustering index（群集索引）：在文件的群集字段上定义的索引。一个文件最多有一个主索引或一个群集索引。 20. Column（列）：参加属性（attribute）。 21. Complex relationship（复杂关系）：度数大于2的关系。 22. Composite attribute（复合属性）：由多个简单组件组成的属性。 23. Composite key（复合键）：包含多个列的主健。

金碟K3数据库对应表

表名表中文名 t_VoucherGroup 凭证字表 t_VoucherEntry 凭证分录表 t_Voucher 凭证表 t_User 系统用户信息表 t_Userprofile 用户配置文件信息表用户设置错时，删除用户的配置文件 t_UnitGroup 单位类别表 t_SystemProfile 系统参数表 t_Supplier 供应商表 t_SubMesType 辅助资料类别表 t_SubMessage 辅助资料表 t_Stock 仓库表 t_Settle 结算方式表 t_MeasureUnit 计量单位表 t_LogFunction 上机日志标准信息表 t_Log 上机日志信息表 t_ItemRight 基础资料权限表 t_ItemPropDesc 核算项目附表信息描述表 t_ItemClass 基础资料类别表 t_ICItem 物料表 t_Exp 备注资料表 t_Emp 职员表 t_Department 部门表 t_Currency 币别表 t_Account 科目表 t_AccessControl 权限控制表 t_GroupAccess 用户组权限表 t_GroupAccessType 用户组权限类表 t_ObjectAccess 对象权限表 t_ObjectAccessType 对象权限类型表 t_ObjectType 对象类型表 t_Accessory 附件管理表 t_AutoNumber 自动增加表 t_CodeRule 编码规则主表 t_CodeRuleDetail 编码规则明细表 t_CodeRuleValue 编码规则当前值表表 t_CodeTypeFP 编码规则分配表表 t_DataTypeInfo 数据类型定义表 t_dls_moduel 数据灌入模块表 t_dls_TableList 数据灌入中间表 t_dls_TableStruct 数据灌入字段描述表 t_Identity 自动步长编码表 t_Mutex 功能互斥表

数据结构和操作系统试题

数据结构和操作系统试题 姓名________ 学号_________ 得分__________ 数据结构部分 一、判断题。（正确的在括号里打√，错误的打×） ①数据元素是数据的最小单位。（） ②完全二叉树中，若一个结点没有左孩子，则必是树叶。（） ③关键路径是AOE网络中从源点到汇点的最长路径。（） ④顺序存储法适用于存储结构为顺序或链式存储的线性表。（） ⑤对任何一棵二叉树，如果叶子结点数为n0，度为2的结点数为n2，则n2 = n0 - 1。（） ⑥快速排序是一种属于选择排序类的方法，时间效率较高。（） ⑦数组的常见操作有存取、修改、删除、插入。（） ⑧若非空二叉树中每个结点有两个子结点，且左子树的根小于根结点，右子树的根不小于根结点，则是二叉排序树。（） ⑨将一棵树转换为二叉树后，根结点没有左子树。（） ⑩在一般情况下，处理冲突方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。（） 二、选择和填空 1.在一个长度为n的顺序表（即顺序存储的线性表）中，向第i个元素（1<=i<=n+1）之前插入 一个新元素时，需向后移动______个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 2.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为__________。 3.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用 ________存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C. 双向循环链表 D.仅有尾指针的单循环链表 4.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过________。 A．n/2 B．n C．(n+1)/2 D．n+1 5. 对有18个元素的有序表A[1]～A[18]作二分查找，则查找A[3]的比较序列的下标为______。 A．1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 6. 下面程序段的时间复杂度是______________。 for (i=0; i

用友数据库表及数据字典

用友数据库表及数据字典 数据库模块"表名""表中文名"公 共 表 相关功能 Ufdａtａ财务 分析 CW_CoｄePｌaｎ科目计划初始科目预算 Ufdata 财务 分析 CW_ＣodｅＰlｕs科目追加计划科目预算 Ｕｆdatａ财务 分析 CW＿DｅｐtＰlan部门计划初始精细部门预算、粗放部门预算 Ｕｆdaｔa 财务 分析 CW_DeptPlus部门追加计划精细部门预算、粗放部门预算 Ufdata 财务 分析 CW_PrｏfPｌａn利润计划初始利润预算 Ufdａta 财务 分析 CＷ_PrｏfPlus利润追加计划利润预算 Ufdatａ财务 分析 CＷ_ProjＰlan项目计划初始精细项目预算、粗放项目预算 Ufdａta 财务 分析 CW＿ＰrojPlus项目追加计划精细项目预算、粗放项目预算 Ｕfｄata 财务 分析 ＣW＿WiｄeDeptＣode 粗放部门计划 控制科目 粗放部门预算科目控制方向选择 Ufｄata 财务 分析 CW_WidePrｏjCoｄｅ 粗放项目计划 控制科目 粗放项目预算科目控制方向选择 Ｕfdatａ采购 管理 ＡrrivalVouch(无用表） Ufｄata 采购 管理 ＡrriｖalVouchs（无用表） Ufdatａ采购 管理 PO_Poｄetails采购订单子表采购订单(子) Ufdata 采购 管理 PO_Pomａin采购订单主表采购订单(主) Uｆｄata 采购 管理 PＵ＿LｅftSｕｍ（无用表） Ufdata 采购 管理 ＰurBillVoｕch采购发票主表采购发票（主) Ufdata 采购 管理 PuｒBilｌVoｕchｓ采购发票子表采购发票（子） Uｆｄata 采购 管理 ＰurSeｔｔleVｏｕｃ h 采购结算单主 表 采购结算(主)

831-数据结构与操作系统

《数据结构与操作系统》考试大纲 一、考查目标 数据结构和操作系统是计算机类专业的核心课程。《数据结构和操作系统》科目考察的内容包括《数据结构》和《操作系统》的基本内容，要求考生掌握相关的概念、方法和技术，并具备较强的程序设计能力，能够灵活应用相关的方法和技术解决实际问题。 二、考试形式与试卷结构 （一）试卷成绩及考试时间 本试卷满分为150分，考试时间为180分钟。 （二）答题方式 答题方式为闭卷、笔试。 （三）试卷内容结构 各部分内容所占分值为： 数据结构75分 操作系统75分 （四）试卷题型结构 1．数据结构 选择题：15小题，每小题2分，共30分 简答题：3小题，每小题10分，共30分 算法题：1小题，每小题15分，共15分 2.操作系统 三、考查范围 数据结构 一、考查目标 1、掌握数据结构的基本概念、方法和技术。 2、掌握程序设计的基本方法和技巧。 3、能够应用相关知识解决一些有实际背景的问题。 二、考查内容 1. 绪论 数据结构的概念；基本概念与术语；算法的概念，算法的特性，以及算法设计的要求，算法效率的度量。 2. 线性表 线性表相关的基本概念和结构特点；线性表的顺序存储方式以及两种不同的实现方法：表空间的静态分配和动态分配；线性表的链式存储方式的实现；链表与顺序表的相似及不同之处，优缺点比较，各自适用的场合；线性表的各种实现方式能够实现指定的操作。 3.栈和队 栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队列等；栈与队列插入删除操作的特点；栈和递归的关系；栈和队列各种实现方式。 4. 串 串的基本概念，朴素的模式匹配算法。 5.数组 数组的定义；数组的存储，行序和列序；特殊矩阵的定义；特殊矩阵的压缩存储。 6.树和二叉树

金蝶K3数据库表对应关系

金蝶K3数据库表对应关系 Xzczxc119 0 0 t_VoucherGroup 凭证字表凭证的收付转等分类字 0 1 t_VoucherEntry 凭证分录表凭证分录 0 2 t_Voucher 凭证表凭证 0 3 t_User 系统用户信息表系统用户信息表 0 4 t_UnitGroup 单位类别表计量单位类别 0 5 t_SystemProfile 系统参数表公司名称等系统控制参数 0 6 t_Supplier 供应商表供应商资料 0 7 t_SubMesType 辅助资料类别表系统公用的说明信息类别 0 8 t_SubMessage 辅助资料表系统公用的说明信息 0 9 t_Stock 仓库表仓库资料 0 10 t_Settle 结算方式表结算方式如现金、电汇等 0 11 t_MeasureUnit 计量单位表计量单位 0 12 t_LogFunction 上机日志标准信息表上机日志标准信息表 0 13 t_Log 上机日志信息表上机日志信息表 0 14 t_ItemRight 基础资料权限表基础资料权限表 0 15 t_ItemPropDesc 核算项目附表信息描述表描述核算项目附表的字段信息 0 16 t_ItemClass 基础资料类别表基础资料类别 0 17 t_ICItem 物料表所有材料、产品、半成品等 0 18 t_Exp 备注资料表常用的摘要信息 0 19 t_Emp 职员表职员 0 20 t_Department 部门表部门 0 21 t_Currency 币别表币别 0 22 t_Ac_count科目表会计科目 0 23 t_AccessControl 权限控制表权限控制 0 24 t_GroupAccess 用户组权限表用户组权限 0 25 t_GroupAccessType 用户组权限类表用户组权限类 0 26 t_ObjectAccess 对象权限表对象权限

操作系统结构

1.2操作系统结构设计 操作系统是一种大型、复杂的并发系统，为了研制操作系统，首先必须研究它的结构，力求设计出结构良好的程序。操作系统的结构设计有两层含义：一是研究操作系统的整体结构，由程序的构成成分组成操作系统程序的构造过程和方法；二是研究操作系统程序的局部结构，包括数据结构和控制结构。采用不同的构件和构造方法可组成不同结构的操作系统。本节将在讨论操作系统构件之后，全面介绍各种操作系统的构造方法。 操作系统的组件 通常把组成操作系统程序的基本单位称作操作系统的构件。剖析现代操作系统，构成操作系统的基本单位除内核之外，主要还有进程、线程、类程和管程。 1．内核 现代操作系统中xx采用了进程的概念，为了解决系统的并发性、共享性和随机性，并使进程能协调地工作，单靠计算机硬件提供的功能是十分不够的。例如，进程调度工作目前就不能用硬件来实现；而进程自己调度自己也是困难的。所以，系统必须有一个软件部分能对硬件处理器及有关资源进行首次改造，以便给进程的执行提供良好运行环境，这个部分就是操作系统的内核。 由于操作系统设计的目标和环境不同，内核的大小和功能有很大差别。有些设计希望把内核做得尽量小仅具有极少的必需功能，称为微内核（microkernel），其他功能都在核外实现，通过微内核提供

的消息传递机制完成其余功能模块间的联系；有些设计则希望内核具有较多的功能，虽然其内部也可划分成层次或模块，但运行时是一个大二进制映像，模块间的联系可通过函数或过程调用实现，称为单内核（monolithic kernel）。操作系统的一个基本问题就是内核的功能设计。微内核结构是现代操作系统的特征之一，这种方法把内核和核外服务程序的开发分离，可为特定应用程序或运行环境要求定制服务程序，具有较好的可伸缩性，简化了实现，提供了灵活性，很适合分布式系统的构造。 一般而言，内核必须提供以下3个方面的功能。 （1）xx处理。xx处理是内核中最基本的功能，也是操作系统赖以活动的基础，为了缩短屏蔽xx的时间，增加系统内的并发性，通常它仅仅进行有限的、简短的处理，其余任务交给在内核之外的特殊用户态进程完成。当xx事件产生时，先由内核截获并转向xx处理例行程序进行原则处理，它分析xx事件的类型和性质，进行必要的状态修改，然后交给内核之外的进程去处理。例如，产生外围设备结束xx事件时，内核首先分析是否正常结束，如果是正常结束，那么，就应释放等待该外围传输的进程；否则启动相应设备管理进程进行出错或异常处理。又如当操作员请求从控制台输入命令时，内核将把这一任务转交给命令管理进程去处理，以接收和执行命令。 （2）短程调度。主要职能是分配处理器。当系统中发生了一个事件之后，可能一个进程要让出处理器，而另一个进程又要获得处理器。短程调度按照一定的策略管理处理器的转让，以及完成保护和恢

数据结构,操作系统重要概念整理

数据结构： 一、重点知识点 1.了解算法的时间复杂度的概念，会求一个算法的时间复杂度； 2.了解线性表的概念，掌握线性表的顺序表示与链式表示； 3.掌握链表的增、删、查、改等基本操作； 4.理解栈和队列的基本概念； 5.掌握循环队列的判空等基本操作； 6.掌握栈在括号匹配和递归中的应用； 7.了解数组的概念； 8.理解矩阵的压缩存储； 9.了解树和二叉树的基本概念； 10.掌握二叉树的遍历、线索二叉树等相关算法； 11.掌握二叉排序树、平衡二叉树以及Huffman树； 12.了解图的基本概念； 13.理解图的的邻接矩阵法存储与邻接表法存储的类型定义； 14.掌握图的遍历算法； 15.掌握图的最小生成树算法、最短路径以及拓扑排序应用及算法； 16.了解查找的基本概念； 17.理解顺序查找方法与折半查找方法； 18.理解B树的概念与基本操作； 19.掌握散列表的概念、构造以及处理冲突的方法； 20.了解排序的基本概念； 21.掌握几种排序算法； 22.理解几种排序算法性能优劣的比较；

二、重要概念 一、概述 1.数据：信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。 2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 3.数据项：构成数据元素的不可分割的最小单位。 4.数据对象：性质相同的数据元素的集合，是数据的一个子集。 5.数据类型：一个值的集合和定义在此集合上一组操作的总称。、 6.时间复杂度：算法中所有语句在算法中重复执行的次数。 二、线性表 1.线性表：具有相同数据类型的n个数据元素的有限序列。 2.顺序表：用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。 3.单链表：通过一组任意的存储单元来存储线性表中的数据元素。 三、栈和队列 1.栈：只允许在一端进行插入或删除操作的线性表。 2.顺序栈：利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针指示当前栈顶的位置。 3.共享栈：利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。 4.队列：只允许在表的一端进行插入，而在表的另一端进行删除，这种操作受限的线性表。 5.循环队列：将顺序队列假想为一个环状的空间，即把存储队列元素的表从逻辑上看成一个环。 6.数组:是由n(n>1)个相同类型的数据元素构成的有限序列。 7.压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配存储空

操作系统结构

操作系统结构设计 操作系统是一种大型、复杂的并发系统，为了研制操作系统，首先必须研究它的结构，力求设计出结构良好的程序。操作系统的结构设计 有两层含义：一是研究操作系统的整体结构，由程序的构成成分组成操作系统程序的构造过程和方法；二是研究操作系统程序的局部结构，包括数据结构和控制结构。采用不同的构件和构造方法可组成不同结构的操作系统。本节将在讨论操作系统构件之后，全面介绍各种操作系统的构造方法。 1.2.1 操作系统的组件 通常把组成操作系统程序的基本单位称作操作系统的构件。剖析现代操作系统，构成操作系统的基本单位除内核之外，主要还有进程、线程、类程和管程。 1．内核现代操作系统中大都采用了进程的概念，为了解决系统的并发性、共享性和随机性，并使进程能协调地工作，单靠计算机硬件提供的功能是十分不够的。例如，进程调度工作目前就不能用硬件来实现；而进程自己调度自己也是困难的。所以，系统必须有一个软件部分能对硬件处理器及有关资源进行首次改造，以便给进程的执行提供良好运行环境，这个部分就是操作系统的内核。 由于操作系统设计的目标和环境不同，内核的大小和功能有很大差别。有些设计希望把内核做得尽量小仅具有极少的必需功能，称为微内 核（microkernel ），其他功能都在核外实现，通过微内核提供的消息传递机制完成其余功能模块间的联系；有些设计则希望内核具有较多的功能，虽然其内部也可划分成层次或模块，但运行时是一个大二进制映像，模块间的联系可通过函数或过程调用实现，称为单内核 （monolithickernel ）。操作系统的一个基本问题就是内核的功能设计。微内核结构是现代操作系统的特征之一，这种方法把内核和核外服务程序的开发分离，可为特定应用程序或运行环境要求定制服务程序，具有较好的可伸缩性，简化了实现，提供了灵活性，很适合分布式系统的构造。 一般而言，内核必须提供以下 3 个方面的功能。 （1）中断处理。中断处理是内核中最基本的功能，也是操作系统赖以活动的基础，为了缩短屏蔽中断的时间，增加系统内的并发性，通常它仅仅进行有限的、简短的处理，其余任务交给在内核之外的特殊用户态进程完成。当中断事件产生时，先由内核截获并转向中断处理例行程序进行原则处理，它分析中断事件的类型和性质，进行必要的状态修改，然后交给内核之外的进程去处理。例如，产生外围设备结束中断事件时，内核首先分析是否正常结束，如果是正常结束，那么，就应释放等待该外围传输的进程；否则启动相应设备管理进程进行出错或异常处理。又如当操作员请求从控制台输入命令时，内核将把这一任务转交给命令管理进程去处理，以接收和执行命令。 （2）短程调度。主要职能是分配处理器。当系统中发生了一个事件之后，可能一个进程要让出处理器，而另一个进程又要获得处理器。短程调度按照一定的策略管理处理器的转让，以及完成保护和恢复现场的工作。由于它是协调进程竞争处理器资源的程序，所以它不是进程而是内核中的一个程序。 （3）原语管理。原语是内核中实现某一功能的不可中断过程。为了协调进程完成通信、并发执行和共享资源，各种原语是必不可少的。通信原语为进程相互传递消息，同步原语能协调并发进程之间的种种制约关系。此外，还有其他原语，如启动外围设备工作的启动原语，若启动不成功则请求启动者应等待，显然，这个启动过程应该是完整的，否则在成为等待状态时，可能外围设备已经空闲。由于设备的操作与硬件密切相关，故通常设备驱动程序等功能都放在内核中完成。 内核是操作系统对裸机的首次改造，内核和裸机组成了一台虚拟机，进程就在这台虚拟机上运行，它比裸机的功能更强大，具有以下特性： （1）虚拟机没有中断，因而，进程的设计者不再需要有硬件中断的概念，用户进程执行中无须处理中断； （2）虚拟机为每个进程提供了一台虚拟处理器，每个进程就好像在各自的私有处理器上顺序地推进，实现了多个进程的并发执行； （3）虚拟机为进程提供了功能较强的指令系统，即它们能够使用机器非特权指令、系统调用和原语所组成的新的指令系统。 为了保证系统的有效性和灵活性，设计内核应遵循少而精的原则。如果内核功能过强，则一方面在修改系统时可能牵动内核；另一方面它占用的内存容量和执行时间都会增大，且屏蔽中断的时间过长也会影响系统效率。因而，设计内核时应注意：中断处理要简单；调度算法要有效；原语应灵活有力、数量适当。这样就可以做到下次修改系统时，尽量少改动内核，执行时中断屏蔽时间缩短。 2．进程管理 程序本身并不能做什么，只有在CPL执行它的指令时才能有所作为；因此，可以把进程看做是正在运行的程序。但是当我们进一步研究时，对进程的定义将更为普遍。例如：一个分时用户程序（如编译器）是一个进程，个人用户在PC上运行的字处理程序是一个进程，一个系统任务（如输出到打印机）也是一个进程，并可以提供允许进程创建与其并发执行的子进程的系统调用。 进程需要特定的资源（包括CPU寸间、内存、文件和I/O设备）来完成工作。这些资源或者在进程创建时分配给它，或者在其运行时分配。除了在进程创建时所获得的各种物理资源和逻辑资源以外，各种各样的初始化数据（或输入）也可能一同传送给进程。例如，考虑一个能够在终端的显示屏上显示一

数据结构与操作系统 - 中国民航大学

数据结构与操作系统 科目代码：830 科目名称：数据结构与操作系统 I.考查目标 计算机科学与技术专业课程考试包括数据结构和操作系统两科专业基础课程。要求考生系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 II.考试形式和试卷结构 1、试卷满分及考试时间:本试卷满分为150分，考试时间为180分钟 2、答题方式:答题方式为闭卷、笔试 3、试卷内容结构:数据结构80分,操作系统70分 III.考试大纲 第一部分 数据结构 考查目标： 1、熟悉线性表、栈、队列、串、、树和二叉树以及图等基本类型的数据结构及其特点，学会根据实际问题要求选用及设计数据结构； 2、理解数据的逻辑结构、存储结构以及各种基本操作的实现； 3、掌握基本的算法分析和设计方法； 4、掌握数据结构在排序和查找等常用算法中的应用，学会一般问题的算法设计。 考查内容： （一）线性表 （1）线性表的定义和基本操作 （2）线性表的实现 顺序存储 链式存储 线性表的应用 （二）栈和队列 （1）栈和队列的基本概念。 （2）栈和队列两种存储结构表示（顺序存储和链式存储）中基本操作的实现算法。 （3）栈和队列的应用。 （三）字符串 （1）字符串的基本概念。 （2）字符串在顺序存储表示中基本操作的实现算法。 （3）字符串匹配的KMP算法，字符串特征向量的计算方法。 （四）树和二叉树 （1）二叉树的定义及其主要性质。 （2）二叉树的顺序存储结构和链式存储结构。 （3）二叉树的遍历。 （4）二叉树线索化的实质和线索化的过程。 （5）树和森林与二叉树的转换。 （6）树和森林的遍历。 （7）二叉树的应用：二叉搜索树、堆、Huffman树和Huffman编码。 （五）图 （1）图的基本概念。 （2）图的存储（相邻矩阵表示和邻接表表示）及基本操作。 （3）图的两种遍历策略：深度优先搜索和广度优先搜索。

金蝶K3数据库各表说明

金蝶K3数据库各表说明 表ID 表名表中文名表说明 0 0 t_VoucherGroup 凭证字表凭证的收付转等分类字 0 1 t_VoucherEntry 凭证分录表凭证分录 0 2 t_Voucher 凭证表凭证 0 3 t_User 系统用户信息表系统用户信息表 0 4 t_UnitGroup 单位类别表计量单位类别 0 5 t_SystemProfile 系统参数表公司名称等系统控制参数 0 6 t_Supplier 供应商表供应商资料 0 7 t_SubMesType 辅助资料类别表系统公用的说明信息类别 0 8 t_SubMessage 辅助资料表系统公用的说明信息 0 9 t_Stock 仓库表仓库资料 0 10 t_Settle 结算方式表结算方式如现金、电汇等 0 11 t_MeasureUnit 计量单位表计量单位 0 12 t_LogFunction 上机日志标准信息表上机日志标准信息表 0 13 t_Log 上机日志信息表上机日志信息表 0 14 t_ItemRight 基础资料权限表基础资料权限表 0 15 t_ItemPropDesc 核算项目附表信息描述表描述核算项目附表的字段信息0 16 t_ItemClass 基础资料类别表基础资料类别 0 17 t_ICItem 物料表所有材料、产品、半成品等 0 18 t_Exp 备注资料表常用的摘要信息 0 19 t_Emp 职员表职员 0 20 t_Department 部门表部门 0 21 t_Currency 币别表币别 0 22 t_Ac_count科目表会计科目 0 23 t_AccessControl 权限控制表权限控制 0 24 t_GroupAccess 用户组权限表用户组权限 0 25 t_GroupAccessType 用户组权限类表用户组权限类 0 26 t_ObjectAccess 对象权限表对象权限 0 27 t_ObjectAccessType 对象权限类型表对象权限类型 0 28 t_ObjectType 对象类型表对象类型 0 29 t_Accessory 附件管理表附件管理 0 30 t_AutoNumber 自动增加表自动增加 0 31 t_CodeRule 编码规则主表编码规则主表 0 32 t_CodeRuleDetail 编码规则明细表编码规则明细表 0 33 t_CodeRuleV alue 编码规则当前值表表编码规则当前值表 0 34 t_CodeTypeFP 编码规则分配表表编码规则分配表表 0 35 t_DataTypeInfo 数据类型定义表采用ADO定义数据类型 0 36 t_dls_moduel 数据灌入模块表包含数据灌入模块划分信息 0 37 t_dls_TableList 数据灌入中间表包含数据灌入用到的中间表信息 0 38 t_dls_TableStruct 数据灌入字段描述表数据灌入中间表的字段描述信息0 39 t_Identity 自动步长编码表为表实现自动编码

苏州大学数据结构与操作系统

2、《数据结构与操作系统》科目考查的内容范围 一、数据结构 （一）概述 1、数据、数据对象、数据结构、数据类型 2、算法及算法描述 3、算法的时间复杂度和空间复杂度 （二）线性表 1、线性表的概念和基本操作 2、线性表类的定义和实现 3、线性表的应用及算法 （三）栈 1、栈的概念和基本操作 2、栈类的定义和实现 3、栈的应用及算法 （四）队列 1、队列的概念和基本操作 2、队列类的定义和实现 3、队列的应用及算法 （五）递归 1、理解递归的概念以及与栈的关系 2、理解递归的工作原理 3、递归算法的设计 （六）字符串 1、串的概念、术语和基本操作 2、串类的定义和实现 3、朴素模式匹配算法 （七）数组 1、数组的定义和运算 2、数组的按行、按列存储 3、特殊矩阵的压缩存储 （八）二叉树 1、二叉树的概念和相关术语 2、二叉树的先序、中序、后序三种遍历方法 3、线索二叉树 4、哈夫曼树的概念和建立方法

（九）树 1、有关树、森林的概念和术语 2、森林、树与二叉树的转换方法 3、森林、树的遍历方法 （十）图 1、图的定义和相关术语 2、计算机表示 3、图的遍历及算法 4、拓扑排序概念及算法 5、最短路径求解算法 6、最小生成树求解算法 （十一）查找 1、有关查找的基本概念 2、顺序查找算法实现及性能分析 3、二分查找算法实现及性能分析 4、二叉查找树的基本概念 5、二叉查找树下的查找、插入、删除算法 6、二叉查找树建立算法 7、AVL树定义 8、哈希查找的概念、哈希函数的选择及冲突解决方法 9、哈希查找算法实现及性能分析 10、不同查找算法的性能比较 （十二）排序 1、掌握有关排序的基本概念 2、插入排序算法实现及性能分析 3、选择排序算法实现及性能分析 4、希尔排序算法基本原理 5、归并排序算法实现及性能分析 6、快速排序算法实现及性能分析 7、堆和堆排序算法实现及性能分析 8、基数排序算法的基本原理 9、各种排序算法在时间、空间、程序效率等方面的比较 二、操作系统 （一）操作系统及其相关概念 1、操作系统的概念、发展、类型； 2、操作系统的功能、结构。 （二）进程管理

用友数据库对照表

a_Control 30_记录互斥 fa_Departments 07_部门 fa_Depreciations 11_折旧方法 fa_DeprList 34_折旧日志 fa_DeprTransactions 19_折旧 fa_DeprVoucherMain 23_折旧分配凭证主表fa_DeprVouchers 24_折旧分配凭证 fa_DeprVouchers_pre 24_折旧分配凭证_准备fa_Dictionary 12_常用参照字典 fa_EvaluateMain 21_评估单主表 fa_EvaluateVouchers 22_评估单 fa_Items 12_项目 fa_ItemsManual 32_自定义项目 fa_ItemsOfModel 14_对应各样式的项目 fa_ItemsOfQuery 35_查询项目 fa_Log 33_日志 fa_Models 13_样式 fa_Msg 29_信息 fa_Objects 03_对象表 fa_Operators 02_操作员 fa_Origins 09_增减方式 fa_QueryFilters 05_查询条件 fa_Querys 04_查询 fa_ReportTemp

fa_Status 10_使用状况 fa_Total 31_汇总表 Accessaries 成套件表AccInformation ！账套参数表 Ap_AlarmSet 单位报警分类设置表Ap_BillAge 账龄区间表 Ap_Cancel 核销情况表 Ap_CancelNo 生成自动序号 Ap_CloseBill 收付款结算表 Ap_CtrlCode 控制科目设置表 Ap_Detail 应收/付明细账 AP_DispSet 查询显示列设置表 Ap_InputCode 入账科目表 Ap_InvCode 存货科目设置表 Ap_Lock 操作互斥表 Ap_MyTableSet 查询条件存储表 Ap_Note 票据登记簿 Ap_Note_Sub 票据登记簿结算表 Ap_SStyleCode 结算方式科目表 Ap_Sum 应收/付总账表 Ap_Vouch 应付/收单主表 Ap_Vouchs 应付/收单主表的关联表Ap_VouchType 单据类型表 Ar_BadAge 坏账计提账龄期间表

操作系统结构 (1)

操作系统是一种大型、复杂的并发系统，为了研制操作系统，首先必须研究它的结构，力求设计出结构良好的程序。操作系统的结构设计有两层含义：一是研究操作系统的整体结构，由程序的构成成分组成操作系统程序的构造过程和方法；二是研究操作系统程序的局部结构，包括数据结构和控制结构。采用不同的构件和构造方法可组成不同结构的操作系统。本节将在讨论操作系统构件之后，全面介绍各种操作系统的构造方法。 1.2.1 操作系统的组件 通常把组成操作系统程序的基本单位称作操作系统的构件。剖析现代操作系统，构成操作系统的基本单位除内核之外，主要还有进程、线程、类程和管程。 1．内核 现代操作系统中大都采用了进程的概念，为了解决系统的并发性、共享性和随机性，并使进程能协调地工作，单靠计算机硬件提供的功能是十分不够的。例如，进程调度工作目前就不能用硬件来实现；而进程自己调度自己也是困难的。所以，系统必须有一个软件部分能对硬件处理器及有关资源进行首次改造，以便给进程的执行提供良好运行环境，这个部分就是操作系统的内核。 由于操作系统设计的目标和环境不同，内核的大小和功能有很大差别。有些设计希望把内核做得尽量小仅具有极少的必需功能，称为微内核（microkernel），其他功能都在核外实现，通过微内核提供的消息传递机制完成其余功能模块间的联系；有些设计则希望内核具有较多的功能，虽然其内部也可划分成层次或模块，但运行时是一个大二进制映像，模块间的联系可通过函数或过程调用实现，称为单内核（monolithic kernel）。操作系统的一个基本问题就是内核的功能设计。微内核结构是现代操作系统的特征之一，这种方法把内核和核外服务程序的开发分离，可为特定应用程序或运行环境要求定制服务程序，具有较好的可伸缩性，简化了实现，提供了灵活性，很适合分布式系统的构造。 一般而言，内核必须提供以下3个方面的功能。 （1）中断处理。中断处理是内核中最基本的功能，也是操作系统赖以活动的基础，为了缩短屏蔽中断的时间，增加系统内的并发性，通常它仅仅进行有限的、简短的处理，其余任务交给在内核之外的特殊用户态进程完成。当中断事件产生时，先由内核截获并转向中断处理例行程序进行原则处理，它分析中断事件的类型和性质，进行必要的状态修改，然后交给内核之外的进程去处理。例如，产生外围设备结束中断事件时，内核首先分析是否正常结束，如果是正常结束，那么，就应释放等待该外围传输的进程；否则启动相应设备管理进程进行出错或异常处理。又如当操作员请求从控制台输入命令时，内核将把这一任务转交给命令管理进程去处理，以接收和执行命令。 （2）短程调度。主要职能是分配处理器。当系统中发生了一个事件之后，可能一个进程要让出处理器，而另一个进程又要获得处理器。短程调度按照一定的策略管理处理器的转让，以及完成保护和恢复现场的工作。由于它是协调进程竞争处理器资源的程序，所以它不是进程而是内核中的一个程序。 （3）原语管理。原语是内核中实现某一功能的不可中断过程。为了协调进程完成通信、并发执行和共享资源，各种原语是必不可少的。通信原语为进程相互传递消息，同步原语能协调并发进程之间的种种制约关系。此外，还有其他原语，如启动外围设备工作的启动原语，若启动不成功则请求启动者应等待，显然，这个启动过程应该是完整的，否则在成为等待状态时，可能外围设备已经空闲。由于设备的操作与硬件密切相关，故通常设备驱动程序等功能都放在内核中完成。 内核是操作系统对裸机的首次改造，内核和裸机组成了一台虚拟机，进程就在这台虚拟机上运行，它比裸机的功能更强大，具有以下特性： （1）虚拟机没有中断，因而，进程的设计者不再需要有硬件中断的概念，用户进程执行中无须处理中断； （2）虚拟机为每个进程提供了一台虚拟处理器，每个进程就好像在各自的私有处理器上顺序地推进，实现了多个进程的并发执行； （3）虚拟机为进程提供了功能较强的指令系统，即它们能够使用机器非特权指令、系统调用和原语所组成的新的指令系统。 为了保证系统的有效性和灵活性，设计内核应遵循少而精的原则。如果内核功能过强，则一方面在修改系统时可能牵动内核；另一方面它占用的内存容量和执行时间都会增大，且屏蔽中断的时间过长也会影响系统效率。因而，设计内核时应注意：

2014年山东科技大学数据结构与操作系统真题.pdf

数据结构部分 一、单项选择题（每小题2分，共20分） 1.下面关于线性表的叙述中，错误的是哪一个？（）A． 线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单 元。D．线性表采用链接存储，便于插入和删除操作。 2.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。 A.单链表 B.单循环链表 C.带尾指针的单循环链表 D.带头结点的双循环链表 3.设栈的输入序列是1，2，3，4，则（）不可能是其出栈序列。 A.1，2，4，3 B.2，1，3，4 C.1，4，3，2 D.4，3，1，2 4.循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则 当前队列中的元素数是()。 A.(rear-front+m)%m B.rear-front+1 C.rear-front-1 D.rear-front 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是 （）。 A．9B．11C．15D．不确定 6.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结 果为（）。 A．CBEFDA B．FEDCBA C．CBEDFA D．不定 7.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）。 A.11 B.35 C.19 D.53 8.快速排序在最坏情况下的时间复杂度为（）。 A.O(log2n) B.O(nlog2n) C.O(n) D.O(n2) 9.下面关于二分查找的叙述正确的是()。