北京大学-计算机科学与技术(2018秋)作业及复习

计算机科学与技术（本科）

2018秋

2018年11月27日

操作系统原理复习题

1. 通道是一种专门用于控制（D）的处理机（书6.1.4课件23）

A. 主存

B. 外存

C. 进程

D. I/O设备

2. 引入进程概念的关键在于（B ）（书2.1课件9）

A. 独享资源

B. 共享资源

C. 顺序执行

D. 便于调试

3. 多道程序环境下，操作系统分配资源以（C ）为基本单位。（书2.1 课件10）

A. 程序

B. 指令

C. 进程

D. 作业

4. 在UNIX操作系统中，把输入输出设备看成（D ）。（书

5.1课件27）

A. 普通文件

B. 目录文件

C. 索引文件

D. 特别文件

5. 若P、V操作的信号量S初值为3，当前值为-2，则表示有（C ）等待进程。（书3.2.3课件13）

A. 0个

B. 1个

C. 2个

D. 3个

6. 进程和程序的一个本质区别（D ）（书2.1课件10）

A. 前者分时使用CPU，后者独占CPU

B. 前者存储在内存，后者存储在外存

C. 前者在一个文件，后者在多个文件中

D. 前者是动态的，后者是静态的

7. 操作系统中，P V操作是一种（D ）（书3.2.3课件12）

A. 机器指令

B. 系统调用

C. 作业控制命令

D. 低级进程通信原语

8. 进程启动的I/O设备传输完成并请求中断后，该进程的状态变化为（B）（书2.2 课件10）

A. 运行态变为阻塞态

B. 阻塞态变为就绪态

C. 就绪态变为运行态

D. 运行态变为就绪态

9. 下列哪种处理机调度算法会使得进程出现“饿死”现象（A ）（书2.4课件11）

A. 最短作业进程优先调度法

B. 响应比高者优先调度法

C. 优先级调度法

D. 轮转法

10. 请求页式管理中，如果淘汰页面选择不当，就会出现刚被淘汰的页面马上又要调入，调入不久再被淘汰，淘汰不久再次装入，如此反复，这种现象叫做（C ）。（书4.7课件21）

A. 死锁

B. Belady异常

C. 抖动

D. 饿死

11. 常用的文件存取方法有两种：顺序存取和（D）存取。（书5.3课件27）

A. 流式

B. 串联

C. 索引

D. 随机

12. 把逻辑地址变为内存的物理地址的过程称为（D ）（书4.1课件19）

A. 编译

B. 连接

C. 运行

D. 重定位

13. 计算机操作系统是一个（D ）（书1.1 课件2）

A. 应用软件

B. 硬件的扩展

C. 用户软件

D. 系统软件

14. 通过资源的静态分配（即进程开始运行之前，必须获得所需的全部资源，若不满足，则进程等待）来预防死锁，是破坏了死锁产生的哪个必要条件（B）（书3.5.2课件16）

A. 互斥使用

B. 保持和等待

C. 非剥夺性

D. 循环等待

15. 银行家算法是一种（B）算法。（书3.5.2课件16）

A. 死锁解除

B. 死锁避免

C. 死锁预防

D. 死锁检测

16. 下列算法中（C）不是请求页式管理的页面置换算法。（书4.7课件21）

A. FIFO

B. LRU

C. 鸵鸟算法

D. 时钟页面置换算法

17. 任何两个并发进程之间（D）（书3.1课件12）

A. 一定存在互斥关系

B. 一定存在同步关系

C. 一定彼此独立无关

D. 可能存在同步或互斥关系

18. 在I/O数据传输的控制方式中，（C）方式的CPU利用效率最低（书6.1.4课件23）

A. DMA

B. 中断

C. 程序查询

D. 通道

19. 利用Spooling技术实现虚拟设备的目的是（A）（书6.2.2课件25）

A. 把独享的设备变成可以共享

B. 便于独享设备的分配

C. 便于独享设备的管理

D. 便于独享设备与CPU并行工作

20. 实现由虚地址映射到物理地址的工作是由（B ）硬件完成的。（书4.1课件19）

A. DMA

B. MMU

C. TLB

D. FCB

二、《多选题》(共5题，每题4分，共20分)

21. __A___和___B___是解决大进程与小主存矛盾的两种存储器管理技术，在一定程度上对主存进行了逻辑扩充。

A. 覆盖

B. 交换

C. 中止

D. 共存

22. 对于批处理系统，处理机调度通常分为___A___、___B____和__C___三级。（书2.4 课件9）

A. 作业调度

B. 进程调度

C. 交换调度

D. 优先调度

23. 进程的并发执行，使得它们之间存在两种制约关系：_A_和_D___ 。

A. 互斥

B. 并行

C. 并发

D. 同步

24. 对文件存储空间的管理方法有三种：__B___、__C__、___D___。

A. 链存储

B. 空白文件目录

C. 位映像表

D. 空闲块链

25. 文件的物理结构分为__A__、_C___和__D__三种。（书5.4课件27）

A. 连续

B. 串联

C. 链接

D. 索引

三、《简答题1》(共2题，每题10分，共20分)

26. 试列出5种处理机调度算法（书2.4 课件11）

1）先来先服务调度法2）最短作业进程优先调度法3）响应比高者优先调度法4）优先级调度法5）轮转法

27. 什么是死锁?死锁的四个必要条件是什么? （书3.5课件16）

一组进程是死锁的，是指这一组中的每个进程都正在等待这一组中的其他进程所占有的资源时可能引起的一种错误现象。必要条件：互斥使用、保持和等待、非剥夺性和循环等待。

四、《简答题2》(共1题，每题20分，共20分)

28. 进程与程序是两个完全不同的概念，但又有密切的联系，试写出两者的区别。（书2.1 课件10）

两者的区别主要是：

1）动态性和静态性进程是一个动态概念，程序是一个静态概念。程序可以作为一种软件资源长期保存；进程是把程序作为它的运行实体，没有程序，也就没有进程，它是临时的，有生命期的。

2）进程是系统进行资源分配和调度的一个独立单位，具有独立性，程序则不是。

3）一个进程可以与其他的进程并发执行，具有并发性，程序则不然

4）进程具有结构性：进程控制块——程序+数据+PCB构成

5）进程具有创建其他进程的功能，而程序没有

6）操作系统中的每一个程序都是在一个进程现场中运行的

软件工程复习题

1.软件工程的定义（第一章）是应用计算机科学理论和技术以及工程管理原则和方法、按预算和进度实现满足用户要求的软件产品的工程，或以此为研究对象的学科。

2.模型的定义（第一章）简单的说，模型是任一抽象，其中包括所有的基本能力、特性或一些方面，而没有任何冗余的细节。进一步说，模型是在特定意图下所确定的角度和抽象层次上对物理系统的描述，通常包含对该系统边界的描述，给出系统内个模型元素以及它们之间的语义关系。

3.简述对问题域和运行平台之间“距离”概念的理解（第一章）软件开发过程中问题域中的概念和逻辑处理与运行平台中的概念和逻辑处理的差别。

4. 软件工程包括的主要内容（本课程的主要内容）（第一章）

1）做哪些映射，即要完成哪些开发任务

2）如何根据软件的项目特点、环境因素等，选择并组织这些开发任务

3）如何实现不同抽象层之间的映射

4）如何进行测试，如何支撑整个软件开发

5）如何管理一个软件项目

5. 软件生存周期的定义（第二章）

6. 软件生存周期的三类过程是什么，它们的含义是什么（第二章）

基本过程：与软件生产直接相关的活动集。支持过程：是有关各方按他们的支持目标所从事的一系列相关活动集，以便提高系统或软件产品的质量。

7. 软件生存周期的基本过程包括那些子过程（第二章）

包括获取过程、供应过程、开发过程、运行过程和维护过程。

8. 简述瀑布模型的主要步骤，以及瀑布模型的问题（第二章）

瀑布模型包括，系统需求、软件需求、需求分析、设计、编码、测试、运行。

瀑布模型的主要问题有：1)要求客户能够完整、正确和清晰地表达他们的需求；并要求开发人员一开始就要理解这一应用；2)由于需求的不稳定性，使设计、编码和测试阶段都可能发生延期；并当接近项目结束时，出线大量的集成和测试工作；3)在开始的阶段中，很难评估真正的进度状态；并且知道项目结束前，都不能演示系统的能力；4)在一个项目的早起阶段，过分强调了基线和里程碑处的文档；并可能需要话费更多的时间，用于建立一些用处不大的文档。

9. 软件需求的定义（第三章）一个需求是一个“要予结构”的陈述，描述了待开发产品（或项）功能上的能力、性能参数或者其他性质。

10. 软件需求的5个基本性质及含义（第三章）

1）必要的，即该需求是用户所要求的；

2）无歧义的，即该需求只能用一种方式解释

3）可测的，即该需求是可进行测试的

4）可跟踪的，即该需求可以从一个开发阶段跟踪到另一个开发阶段

5）可测量的，即该需求是课测量的

11. 软件需求的5种类型（第三章）

功能需求、性能需求、外部接口需求、设计约束、设计属性

12. 软件需求的5种发现技术（第三章）自悟、交谈、观察、小组会、提炼

13. 数据和数据流的定义（第四章）

数据是客观事物的一种表示，是信息的载体；数据流是数据的流动。

14. 加工的定义（第四章）

加工是对数据进行变换的单元，即接受输入的数据，对其进行处理，并产生输出。

15. 数据存储的定义（第四章）数据存储是数据的静态结构

16. 据源和数据潭的定义（第四章）数据源是数据流的起点，数据潭是数据流的归宿地。数据源和数据潭是系统之外的实体，可以是人、物或其他软件系统。

17. 结构化分析的建模过程（第四章）

1）建立系统环境图，确定系统语境

2）自顶向下，逐步求精，建立系统的层次数据流图

3）定义数据字典4）描述加工

18. 结构化设计中总体设计的任务（第五章）总体设计是把系统的功能需求分配给一个特定的软件体系结构。

19. 结构化设计中详细设计的任务（第五章）详细设计的目标是将总体设计阶段所产生的系统高层结构，映射为以这些术语所表达的低层结构，也是系统的最终结构。

20. UML是什么（第六章）UML是一种可视化语言，可用于规约系统的制品、构造系统的制品、建立系统制品的文档。这意味着UML可作为软件需求规约、设计和实现的工具。21. UML名词解释：类与对象、接口、协作、用况、主动类、构件、制品、节点（第六章）

1）类是一组具有相同属性、操作、关系和语义的对象的描述；对象是累的一个实例；

2）接口是操作的一个集合，其中每个操作描述了类、构件或子系统的一个任务；

3）协作是一个交互，涉及交互三要素：交互各方、交互方式和交互内容；

4）用况是一组动作序列的描述，系统执行这些动作应产生对特定参与者有价值的、可观察的结果；

5）主动类是一种至少具有一个进程或线程的类；

6）构建是系统设计中的一种模块化部件，通过外部结构隐藏了它的内部实现；

7）制品是系统中包含物理信息的、可替代的物理部件；

8）节点是运行时存在的物理元素,通常表示一种具有记忆能力和处理能力的计算机资源22. UML名词解释：关联、泛化、细化、依赖（第六章）

1）关联是类目之间的一种结构关系，是对一组具有相同结构、相同链的描述；

2）泛化是一般性类目(超类或父类)和它的较为特殊性类目(成为子类)之间的一种关系；

3）细化是类目之间的语义关系，其中一个类目规约了保证另一个类目执行的契约；

4）依赖是一种使用关系，用于描述一个类目使用另一个类目的信息和服务。

23. RUP的定义（第七章）

24. 软件测试的目的（第八章）预防错误、发现错误。

1，软件测试是为了发现错误而执行程序的过程；

2，测试是为了证明程序有错，而不是证明程序无错误。

3，一个好的测试用例是在于它能发现至今未发现的错误；

4，一个成功的测试是发现了至今未发现的错误的测试。

25. 软件测试的定义（第八章）

按照特定桂城发现软件错误的过程；使用人工或自动手段，运行或测定某个系统的过程，其目的是检验它是否满足规定的需求，或是清楚了解预期结果与实际结果之间的差异。26. 白盒测试技术的定义和主要方法（第八章）

白盒测试又称为结构测试技术，白盒测试的依据的是程序的逻辑结构；路径测试技术是白盒测试的一种重要方法。

27. 黑盒测试技术的定义和主要方法（第八章）

黑盒测试技术又称为功能测试技术，黑盒测试技术依据的是软件行为的描述；等价类划分是黑盒测试的一种重要方法。

28. 软件测试的主要步骤（第八章）

单元测试、集成测试、有效性测试、系统测试。

29. 列举一种软件规模的估算方法和一种软件成本估算模型（第九章）

30. CASE的意义和定义（第十章）

CASE是计算机辅助软件工程；CASE=软件工程+自动化工具。

二、问答题(共1题，每题40分，共40分)

31. 根据自己的工作经验，简述软件工程方法在实际工作中的应用，不少于200字。

自答：根据书本的定义，软件工程是应用计算机科学理论和技术以及工程管理原则和方法，按照预算和进度实现满足用户要求的软件产品的工程。在实际的开发中，一般而言大公司有自己成熟的整套流程，如需求分析，概要设计，详细设计，编码、测试、交互，整个过程有明确的分工和处理流程。对于小公司，在成本、项目周期以及项目的快速迭代和试错往往通过分析客户需求，而后简单的画出UML以及流程图就进入编码阶段了，编码阶段往往会对功能模块进行简单的测试。这样一个软件从立项到最后交互都较快。当然这仅仅是针对小项目而言，对于中大型项目必须要按照软件工程方法进行设计，因为这牵涉到整个项目的成功与否。比如在需求分析阶段如果分析有偏差，那么最终的交付可能并不是客户所需要的产品了。又比如，在详细设计阶段不够到位，流程没有处理好，那么必须在测试花费较大的精力和时间，从而导致项目交付延期。软件工程对于软件开发来说是非常重要的，必须借鉴和学习的，更是软件开发的必然产物。

网络工程应用复习题

1.[第二章]1000Base-T的物理拓扑为星型、逻辑拓扑为总线

2.[第四章]IPv4地址长度为32比特

4.[第四章]IPv6地址长度为128比特

5.[第二章]集线器是工作在物理层的网络设备（请填写七层模型的具体层次名称）

6.[第二章]网卡是工作在数据链路层的网络设备（请填写七层模型的具体层次名称）

7.[第四章]路由器是工作在网络层的网络设备（请填写七层模型的具体层次名称）

8.[第八章]网络设计三层模型自顶向下的最上层是核心层中间层是汇聚层最底层是接入层

二、选择题(共5题，每题2分，共10分)

11. [第二章]与虚拟局域网相关的国际标准是__A__。

A. IEEE 802.1Q

B. IEEE 802.3u

C. IEEE 802.5

D. IEEE 802.11a

12. [第二章]IEEE关于以太网的协议为__B__。

A. IEEE 802.1

B. IEEE 802.3

C. IEEE 802.5

D. IEEE 802.11

13. [第二章]IEEE 802.11a通信使用__D__频段。

A. 902 MHz

B. 1800 MHz

C. 2.4 GHz

D. 5 GHz

14. [第二章]综合布线系统中，水平布线子系统一般采用__B__进行铺设。

A. 细同轴电缆

B. 无屏蔽双绞线

C. 多模光纤

D. 微波天线

15. [第三章]不属于局域网传输技术的是__A__。

A. 帧中继

B. 以太网

C. 令牌环网

D. WLAN

三、计算题(共15题，每题3分，共45分)

请计算下列所属的网络地址,并给出该子网的广播地址、最小可用IP地址和最大可用IP地址

24. [第四章]请按照路由汇聚的方式对下列子网进行合并

四、简答题(共3题，每题5分，共15分)

31. [第二章]IEEE 802.11有关54Mbps以下传输速度标准有哪几种？请分别作出简要说明。IEEE 802.11，在2.4GHz的ISM波段传输1 Mbps和2 Mbps IEEE 802.11b，在2.4 GHz 频带上传输5.5 Mbps和11 Mbps IEEE 802.11a，在5 GHz频带上最高传输54Mbps IEEE 802.11g，在2.4 GHz频带上最高传输54Mbps IEEE 802.11b向下兼容IEEE 802.11的DSSS系统IEEE 802.11a不能向下兼容IEEE 802.11和IEEE 802.11b IEEE 802.11g向下兼容现在的IEEE 802.11b

32. [第二章]简单描述无屏蔽双绞线的特点及用途，画出EIA/TIA-568B标准的RJ-45接口连接示图，并简要说明线序。

第一线对：蓝色，位于第4和5针

第二线对：橙色，位于第1和2针

第三线对：绿色，位于第3和6针

第四线对：棕色，位于第7和8针

RJ-45连接器示意图白橙橙白绿蓝白蓝绿白棕棕白绿绿白橙白棕棕橙蓝白蓝

33. [第二章]简单说明交换机的两种转发方式

存储转发Store-and-forward 在转发开始前会先接收整个数据帧。在数据帧被转发前，会读取目的地址（与/或来源地址），并使用过滤器。当数据帧被接收时会发生延迟；越大的数据帧延迟越久，因为整个数据帧需要花更多的时间来读取。错误检测率很高，因为等待接收整个数据帧的时间让交换机有时间可以检查错误

直通式Cut-through 交换机在接收整个数据帧前先读取目的地址。然后数据帧会在整个帧抵达前被转发出去。这个方式減少传输延迟，但LAN交换错误检测较差。

五、问答题(共2题，每题10分，共20分)

34. [第八章]简单描述网络层次化设计的优点，说明网络设计的三层模型各层应实现的功能。层次化设计的优点是：扩充性、执行容易、容易排解问题、可预测性、更好的支持协议、可管理性层次式网络设计包括以下这三层核心层在网站间提供最佳传输汇聚层提供以策略为主的连接接入层供工作群组和用户访问网络核心层的功能便是提供远程网站间的快速路径这一层网络层不应执行任何数据报处理，例如利用访问控制列表和执行过滤，因这些会降低数据报的交换速度核心层通常都是以WAN 的模式来执行的。WAN 需要冗余路径，因此网络可以承受个别的电路中断并继续运作路由协议的负载分发和快速收敛亦是很重要的设计功能。如何在核心层中有效利用带宽一直都是考虑的因素之一网络的汇聚层是访问层与核心层间的分界点，可以帮助定义并区分核心汇聚层的目的是提供边界定义，负责处理数据报。汇聚层可以包含多种功能：地址或区域聚集对核心层的部门或工作群组访问广播/多点广播领域定义VLAN路径选择不需转换任何介质安全接入层是区域用户被允许进入网络的接入点。这一层也可以利用访问控制列表，进一步将一组特殊用户的需求最佳化。在园区网络环境中，接入层的功能包括：共享带宽交换带宽MAC 层过滤微区段。

35. [第八章]请说明单播、广播和组播的概念和特点；以视频流转播服务器为例，画图说明不同传播方式；分析不同传播方式对网络带宽的需求。

单播在单点传送中，每个包的副本都可发送到请求使用多媒体的目标上。例如，如果有4个工作站请求一应用程序，那么包的4个副本将分别发送到各个工作站上。单点传送无须

特殊的网络协议，因此开发起来要相对容易一些。由于发送端给每个要接收应用的工作站都发送一个包，所以单点传送中的信息流量是点到点的

广播在广播传送中，每个帧的副本都将发送往网络的每个结点，无论工作站是否请求了该应用程序。例如，如果网络上有100个工作站，那么发送端计算机发出的包将被集线器、交换机、网桥和路由器复制到100个位置上。如果网络包括着网桥、交换机或路由器，控制广播信息流量的一种方法就是创建过滤装置来限制广播包的传输。因为在广播传送中，发送端计算机会将广播的包传送到所有的点，因此广播传送是多点信息流量的典型例子

组播组播传送是多点信息流量的另一个例子，发送端将使用一个包来传送到所有客户端。组播传送给请求多媒体应用的工作站创建组结合MAC和IP编址，它将指向一个或多个组的包发送出去组由MAC和IP编址来标识，只有请求了应用的组内的工作站才有组播传送的可能如果应用程序是根据单点传送设计的，那么服务器传送带宽为1.5Mbps与客户端数量的乘积，例如对5个客户端而言，就是7.5Mbps。在通过10Mbps链路连接的服务器上，仅6个或7个客户端便可以完全占据网络带宽。使用广播传送，带宽的利用至少与单点传送相等，或者更大组播传送时，不管有多少客户端，带宽利用都可降低到1.5Mbps。

数据结构复习题

1.（第一章）数据的逻辑结构被形式地定义为B=(K,R),其中K是___C___的有限集合。

A. 存储

B. 数据操作

C. 数据元素

D. 操作

E. 逻辑结构

F. 映象

G. 算法

H. 关系

2.（第一章）数据的逻辑结构被形式地定义为B=(K,R),其中R是K上的__H____的有限集合。

A. 存储

B. 数据操作

C. 数据元素

D. 操作

E. 逻辑结构

F. 映象

G. 算法

H. 关系

3.（第一章）以下关于算法的说法不正确的是______B________。

A. 一个算法应包含有限个步骤

B. 算法越简单越好

C. 算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之

D. 算法中的每个步骤都能在有限时间内完成

4. （第一章）设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是_______B_______。

A. 线性结构

B. 树型结构

C. 物理结构

D. 图型结构

5. （第一章）下面程序段的时间复杂度为___C___

int sum=0;

for(i=0; i

for(j=i;j

s++;

A. O(m+n)

B. O(n*n)

C. O(m*n)

D. O(m*logn)

6.（第二章）下列有关线性表的叙述中，正确的是____A____。

A. 一个线性表是n 个数据元素的有限序列

B. 线性表中任何一个元素有且仅有一个直接前驱

C. 线性表中任何一个元素有且仅有一个直接后继

D. 以上说法都不正确

7.（第二章）在含有n个结点的顺序存储的线性表中，在任一位置插入一个结点所需移动结点的平均次数为___C___

A. n

B. (n-1)/2

C. n/2

D. (n+1)/2

8.（第四章）若栈采用链式存储结构,则下面的说法中正确的是___A_____

A. 不需要判断栈满但需要判断栈是否为空

B. 需要判断栈是否栈空与栈满

C. 需要判断栈满但不需要判断栈空

D. 栈满栈空都不需要判断

9.（第四章）在一个链栈中，已知s为栈顶指针（直接指向栈顶元素结点，无头结点），t 为栈底指针，直接指向栈底元素，则插入r结点的操作为_____C_______。

A. t->next=r;t=r;

B. r->next=s;s=r;

C. s->next=r;s=r;

D. r->next=t;

10.（第二章）链表不具备的特点是______C______。

A. 不必事先估计存储空间

B. 插入删除不需要移动元素

C. 可顺序访问任一结点

D. 所需空间与其长度无关

11.（第二章）带附加头结点的双循环链表L为空表的条件是_____C_______。

A. L==NULL

B. L->next==NULL

C. L->prior==L

D. L->prior==NULL

12.（第三章）设广义表L=（a,（b,c,d））,则L的长度与深度分别为___D_____。

A. 1和3

B. 1和2

C. 2和3

D. 2和2

13.（第四章）一个栈的输入序列为1,2,3,4,5,6下面哪一个序列不可能是这个栈的输出序列。

A. 1, 2, 3, 4, 5, 6

B. 3, 2, 6, 4, 5, 1

C. 2, 4, 6, 5, 3, 1

D. 6, 5, 4, 3, 2, 1

14.（第四章）循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____A________。

A. (rear-front+m)%m

B. rear-front+1

C. rear-front-1

D. rear-front

15.（第四章）栈和队列的共同特点是______A______。

A. 只允许在端点处插入和删除元素

B. 都是先进后出

C. 都是先进先出

D. 没有共同点

16.（第四章）中缀表达式(A+B)*D+E/(F+A*D)+C的后缀形式是___D___

A. AB+D*E/FA+*DC+

B. ABD*+EFAD*+/C+

C. ABDEFADC+*+/+*+

D. AB+D*EFAD*+/+C+

17.（第五章）如下图所示的4棵二叉树，____C_____不是完全二叉树。

A. B. C. D.

18.（第五章）设某棵二叉树中有2000个结点，则该二叉树的最小高度为______C______。

A. 9

B. 10

C. 11

D. 12

19.（第五章）深度为6(根的层次为1)的二叉树至多有______B____结点

A. 64

B. 63

C. 31

D. 32

20.（第五章）二叉树的第k层的结点数最多为_______D_____。

A. 2k-1

B. 2k+1

C. 2k-1

D. 2k-1

21.（第五章）如果一棵二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是____B______。

A. 空或只有一个结点

B. 高度等于其结点数

C. 任一结点无右孩子

D.任一结点无左孩子

22.（第五章）树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论_____A_____是正确的。

A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同

B. 树的后根遍历序列与其对应的二叉树的先序遍历序列相同

C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同

D. 以上都不对

23.（第六章）根据使用频率为5个字符设计的哈夫曼编码不可能是_____C______。

A. 100，111，110，101，0

B. 111，110，10，01，00

C. 000，001，010，011，01

D. 001，000，01，11，10

24.（第六章）下列数据结构中,不属于二叉树的是____D_____

A. 堆

B. 哈夫曼树

C. 线索二叉树

D. B树

25. （第七章）采用邻接表存储的图的广度优先遍历算法类似于二叉树的___D___。

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 层次遍历

26. （第七章）对用邻接表表示的图进行深度优先遍历时，通常是借助___B____来实现算法。

A. 队列

B. 栈

C. 树

D. 图

27. （第七章）在一个图中，所有顶点的度数之和等于图的边数的___C______倍。

A. 1/2

B. 1

C. 2

D. 4

28. （第九章）对线性表进行二分查找，要求线性表必须______B______。

A. 以顺序方式存储

B. 以顺序方式存储，且结点按关键字有序排序

C. 以链接方式存储

D. 结点按关键字有序排序，存储方式无所谓

29. （第十章）排序方法中，每次从未排序序列中查找值最小的元素放到已排序序列（初始时为空）的末尾，该排序方法称为______A______。

A. 选择排序

B. 冒泡排序

C. 希尔排序

D. 插入排序

30. （第十章）下列四种排序中，______D______是空间复杂度最大的。

A. 选择排序

B. 冒泡排序

C. 希尔排序

D. 插入排序

二、填空题(共30题，每题1分，共30分)

31.（第一章）数据结构分为逻辑结构和物理结构两种结构。

32.（第一章）线性结构中元素之间存在一对一关系,而图形结构中元素之间存在多对多关系。

33.（第一章）线性结构中元素之间存在一对一关系,而树形结构中元素之间存在一对多关系。

34.（第一章）一个算法的最基本的原操作执行次数为(3n2+2nlog2n+4n-7)/(7n),则该算法的时间复杂度为O(n)。

35.（第二章）链式存储结构用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过指针间接地反映。

36.（第二章）向一个长度为n的顺序表中的第i个元素(1≤i≤n)之后插入一个元素时，需向后移动n-i个元素。

37.（第二章）当线性表的元素总数不固定，且很少随机存取表中元素，但插入和删除操作较多时，应采用链式存储结构。

38.（第二章）在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。