大学计算机基础试题

第1章 计算机基础知识

二、填空题

1、微型机的主要性能指标有（ ）；存储容量；运算速度；字长。

2、能把计算机处理好的结果转换成为文本、图形、图像或声音等形式并输送出来的设备称

为（ ）设备。

3、将高级语言源程序翻译成机器语言通常有解释和（ ）两种方式。

4、程序设计语言通常分为机器语言、汇编语言、（ ）三大类。

5、汉字库中储存汉字的编码是（ ）码。

6、微型计算机的总线一般由（ ）总线；地址总线和控制总线组成。

7、4个二进制位可表示（ ） 种状态。

8、软件分为系统软件和应用软件两大部分，微机的诊断程序属于（ ）。

9、利用计算机来模仿人的高级思维活动称为（ ）。

10、冯·诺依曼计算机的基本原理是（ ）。

11、计算机中用来保存正在运行的程序和数据，以及运算的中间结果和最后结果的装置是

（ ）。

12、为解决某一特定的问题而设计的指令序列称为（ ）。

13、计算机包括硬件系统与软件系统，我们通常所说的“裸机”是指计算机仅有（ ）

系统。

14、Cache的中文译名是（ ）。

15、计算机内部使用的数是（ ）进制数。

16、科学计算程序、字表处理软件、工资管理程序、人事管理程序、财务管理程序以及计算

机辅助设计与制造、辅助教学等软件都是（ ）。

17、构成计算机物理实体的部件被称为（ ）。

18、能够将高级语言源程序加工为目标程序的系统软件是（ ）。

19、微型计算机的微处理器芯片上集成了控制器和（ ）。

20、目前使用的家庭用计算机采用的逻辑器件属于（ ）。

21、正数的补码与原码相同；负数的补码是在原码基础上( )不变，其余各位全部取反

后加1。

22、（ ）是指计算机一次所能加工处理的二进制数据的实际位数（长度）。

23、计算机中的浮点数由两部分构成，阶码和( )。

24、按照通信方式，总线可分为并行总线和( )总线。

25、缓存Cache的引入解决了高速的CPU与相对较慢的主存之间( )不匹配的矛盾

三、判断题

1、（ ）汇编语言是一种高级语言。

2、（ ）CPU不能直接访问外存储器。

3、（ ）安置在主机箱外部的存储器叫外部存储器, 简称外存。

4、（ ）我们常用的文字处理软件如：WPS、Word，它们属于系统软件。

5、（ ）在计算机中，所有数据都是以十进制形式表示。

6、（ ）计算机发展阶段的划分是以程序设计语言作为标志的。

7、（ ）语言处理程序也是系统软件之一。

8、（ ）操作系统是所有软件的总称。

9、（ ）虚拟存储器( Virtual Memory ) 技术是一种通过硬件和软件的综合来扩大用户

可用存储空间的技术。

1

10、（ ）所有的ROM都不可以向其写数据。

11、（ ）地址总线与数据总线一样，都是双向的总线。

12、（ ）总线就是一组导线。

13、（ ）计算机内部对汉字信息的存储和处理使用汉字机内码（内码）。

14、（ ）国标码就是区位码。

15、（ ）基本ASCII码使用七位二进制数为字符编码，所以在计算机内存储一个字符的

ASCII码使用7个bit。

16、（ ）定点小数的小数点隐含在数值部分左端，即在数的符号位之后、最高数位之前。

17、（ ）定点小数-0.125用8位二进制数可表示为10010000。

18、（ ）浮点数中，尾数占用位数决定的数的精度。

19、（ ）定点数只能用来表示整数或纯小数

20、（ ）补码的加减法运算规则：[X+Y]

补

=[X]

补

+[Y]

补

[X-Y]

补

=[X]

补

-[Y]

补

。

21、（ ）计算机软、硬件之间的关系是：硬件是基础、软件是灵魂。

22、（ ）接口是指连接总线与外部设备的适配电路。

23、（ ）USB接口是串行接口的一种。

24、（ ）硬盘必须通过并行接口与总线相连。

25、（ ）一张蓝光单碟上可存储25Gb到50Gb的信息。

四、计算题

1、已知8位机器数10110100，它是补码时，它的十进制真值是多少？

2、十六进制数30E与八进制数21734的和的十进制表示是多少？

3、存储1000个32×32点阵的汉字字形所需的存储容量是多少KB？

4、已知某硬盘的磁头数为256，柱面数为2048，扇区数为63，每个扇区记录512B数据，

计算机该硬盘的存储容量，单位使用GB。

5、4MB的存储空间可以存储多少个汉字？

6、十进制数-101对应的八位二进制补码是什么？给出计算机过程。

7、某汉字的区位码是(2036)

D

，该汉字的十六进制的国标码和机内码各是什么？写出计算过

程。

8、某硬盘的存储容量为16GB，若柱面数为1024，扇区数为128，每个扇区记录512B数据，

那么该硬盘有多少个磁头？给出计算过程。

9、与(4F2.A)

H

等值的八进制数是多少？给出计算过程。

10、与(345.44)

O

等值的十进制数多少？给出计算过程。

五、综合题

1、什么是总线、总线按照任务可以分为哪几类？

2、程序设计语言按其发展演变过程可分为哪几种？分别列举出两种面向过程的计算机语言

和两种面向对象的计算机语言。

3、试比较内存储器和外存储器。

4、地址总线的位数与CPU可直接寻址的内存空间大小的关系是什么？如地址总线为24位，

其寻址空间是多少MB？

5、计算机内使用二进制表示各类数据，其原因是什么？

6、r进制数的基数是什么？每位的位权是什么？

7、简述计算机的特点。

8、简述操作系统的功能。

2

9、什么是汇编程序、 编译程序？

10、冯·诺依曼（Von Neumann）体制所描述的通常所说的硬件系统的五大部件是什么？

第2章 计算机网络技术基础

二、填空题

1、将一幢办公楼内的计算机连成一个计算机网络，该网络属于（ ）网。

2、Internet采用IP地址和（ ）地址两种方式标识入网的计算机。

3、WWW由三部分组成：浏览器、Web服务器和（ ）。

4、网络中的各计算机之间交换信息，除了需要安装网络操作系统外，还需要遵循（ ）。

5、网卡全称网络接口卡，又称（ ）。

6、802参考模型为局域网规定了一种（ ）位二进制数的MAC地址。

7、网络协议的3个要素是（ ）、语义和同步。

8、电子邮件系统一般采用两种协议：简单邮件传送协议和（ ）协议。

9、收发电子邮件可以采用两种方式：WWW方式和（ ）方式。

10、在当今计算机网络的发展史上，两个主要网络体系结构分别是OSI参考模型和（ ）

模型。

11、接入Internet的常用方式包括调制解调器入网、通过ISDN、（ ）专线入网、以

局域网方式入网、以DDN、X.25、帧中继等专线方式入网和以无线方式入网。

12、任何计算机只要遵循（ ）网络协议，都可以接入Internet。

13、在计算机网络中，使用域名方式访问Internet上的某台计算机时，DNS服务器需要将

域名转换成（ ）才能被Internet识别。

14、计算机网络按照地域可以分为LAN、MAN和（ ）。

15、每个网卡的MAC地址都固化在（ ）中，并且全球唯一。

16、网卡完成OSI（ ）层和数据链路层的功能。

17、OSI模型将计算机网络划分为7个层次，其中在数据链路层和传输层之间的是（ ）

层。

18、通常，通过（ ）服务，用户可以从一个Internet主机向本地计算机“下载”文

件，或从本地计算机向一个Internet主机“上传”文件。

19、局域网中的计算机采用( )方式相互通信。

20、CSMA/CD是局域网中使用的一种( )控制协议。

21、路由器工作在物理层、数据链路层和( )。

22、在WindowsXP的命令提示符下，输入( )命令可以查看本机的MAC地址信息。

23、子网掩码是一个( )位二进制编码。

24、子网掩码与一台主机的IP地址作( )运算可以确定该主机的网络号和子网号。

25、个人用户通过电话线上网必须有( )。

三、判断题

1、（ ）域名可以由用户自己任意命名。

2、（ ）IP地址又称URL地址。

3、（ ）所有Internet上的计算机都能提供WWW服务。

4、（ ）我们既可以从因特网上下载文件，也可以上传文件到因特网。

5、（ ）万维网就是所说的因特网。

6、（ ）星型拓扑结构网络当中央节点发生故障时，整个网络不能工作。

7、（ ）电路交换必定是面向连接的。

8、（ ）网络协议的语法指操作执行顺序的详细说明。

9、（ ）计算机网络的发展过程大致分为三个阶段：局域网、城域网、广域网。

3

10、（ ）数据链路层传送的数据单位是帧。

11、（ ）光纤的光源都使用激光。

12、（ ）资源子网主要负责网络中的数据处理。

13、（ ）数据率也叫比特率，是指每秒传送多少字节的数据。

14、（ ）拓扑不关心事物的细节，只将讨论范围内的事物之间的相互关系通过图表示出

来。

15、（ ）网络体系结构保，每一层最都要依靠下一层提供的服务。

16、（ ）PDU是协议数据单元的英文缩写。

17、（ ）网桥又称为网间协议转换器。

18、（ ）调整解调器既可以完成数字数据向模拟数据的转换，也可以完成模拟数据向数

字数据的转换。

19、（ ）ARPnet使用TCP/IP协议。

20、（ ）IP地址可分为A、B、C三类。

21、（ ）网状拓扑结构在局域网中很少使用。

22、（ ）E-mail服务使用SMTP协议收发电子邮件。

23、（ ）TCP协议工作在数据链路层。

24、（ ）WWW的英文全称是Wide Web World。

25、（ ）IP地址中，网络地址占用高16位，主机地址占用低16位。

四、计算题

1、子网掩码为255.255.254.0，判断IP地址188.188.0.111与188.188.5.222是否在同一

网段？

2、在一条64Kbps的理想信道上，传送一个100kB的文件需要多长时间?

3、如果将一个C类网络222.97.255.0分为4个子网，写四个子网的IP地址范围。

4、某网络的子网掩码为255.255.255.248，每个网段最多可容纳多少台主机。

5、如果将一个C类网络分为8个子网，写该网络子网掩码的点分十进制形式。

6、某网段子网掩码为 255.255.240.0，求每个网段最多可容纳多少台主机？

7、将IP地址00100010表示成点分十进制。

8、将IP地址98.198.12.34化成二进制形式的IP地址。

9、如果数据传输速率为1Gbps，那么2s传输多少字节数据。

10、传输速率为10Gbps的局域网每一秒钟可以发送的比特数为多少？

五、综合题

1、LLC子层的功能是什么？

2、简述CSMA/CD协议的工作要点。

3、根据下图回答该主机的计算机名、网卡地址、IP地址、子网掩码、默认网关和DNS的值。

4

4、在OSI参考模型中，相邻两层的关系是什么？

5、简述TCP“三次握手”的基本过程。

6、简述路由器的功能。

7、TCP/IP协议可分为四个层次，按自下而上的顺序给出各层的名称？

8、TCP协议如何实现流量控制？

9、简述HTTP会话过程

10、决定局域网 特征的主要技术有哪些？局域网最常用的介质访问控制方法有哪几种？

第3章 数据库基础

二、填空题

1. 数据库数据具有永久存储、有组织和（ ）三个基本特点。

2. 数据库管理系统是数据库系统的一个重要组成部分，它的主要功能包括数据定义、

（ ）、数据控制、数据维护。

3. DBMS 的中文含义是（ ）。

4. DBMS的数据操作功能可以实现对数据的查询、插入、删除和（ ）等基本操作。

5. 按用户的观点来对信息世界建立的数据模型称为（ ）。

6. 在概念数据模型中，现实世界中存在的、可以相互区别的事物或活动都称为（ ）。

7. 关系数据模型中，二维表的列称为属性，二维表的行称为（ ）。

8. 关系模型由（ ）、关系操作、关系完整性约束三部分构成。

9. 对关系进行选择、投影或连接运算之后，运算的结果仍然是（ ）。

10. 根据参照完整性规则，外键的值或者等于以此外键为主键的关系中某个元组主键的值，

或者取（ ）。

11. 关系数据库中的数据表是依据（ ）数据模型创建的。

12. 关系模型中用（ ）来描述一个关系。

13. 主键的值可以用来识别和区分（ ），主键的取值是惟一的、不能重复的。

14. 如果对多个关系进行综合查询,需要进行（ ）运算。

15. 针对关系：课程（课程号，课程名，开课学期，学分，开课院系），若要查询某学院开

设的所有课程名单，须进行（ ）运算。

16. 为防止选课关系中出现不存在的学生的选课信息，需要定义学生关系与选课关系的

（ ）约束条件。

5

17. 指定某关系的“性别”字段的取值只能是”男”或”女”，这是数据的（ ）完整性约

束。

18. 当向选课表中插入实际不存在的学生的选课数据时，DBMS会根据参照完整性规则进行

检测并（ ）该操作。

19. 假设有关系：

学生（学号，姓名，性别，所在班级）

选课（学号，课程号，成绩）

课程（课程号，课程名，学分）

若试图向选课关系中插入一个课程号为空的元组时，将会违反（ ）完整性规则。

20. 命令 SELECT （ ） FROM 选课 WHERE 课程号=”c03” 将从选课表（学号，

课程号，成绩）查询选修课程c03的学生该课程的最高成绩。

21. 命令“SELECT （ ） 课程号FROM 选课”将从选课表（学号，课程号，成绩）

查询所有被选修的课程号且不允许重复。

22. 关系 R （ A ， B ， C ）和 S （ A ， D ， E ， F ）， R 和 S 有相同属性 A ，

若将关系代数表达式：π A,B,D,F （ RS ）用 SQL 语言的查询语句表示，则为：

SELECT R.A ,B ,D ,F FROM R ,S WHERE （ ）。

23. 基于关系数据模型构建的数据库称为（ ）。

24. 在关系数据库中，采用（ ）语言对数据表进行操作。

25. Oracle是一款应用很广泛的（ ）软件。

三、判断题

1. （ ）数据库应用程序可以直接访问数据库中的数据，无须通过DBMS。

2. （ ）数据库是数据库系统的核心。

3. （ ）数据库的设计离不开DBA的参与。

4. （ ）数据库中的数据只能被一个应用程序使用。

5. （ ）数据库实现数据共享，主要是为了节省存储空间。

6. （ ）概念模型中，每个实体型至少存在着一个关键字，以此来区别各实体。

7. （ ）实体联系模型是一种关系数据模型。

8. （ ）不同的逻辑数据模型有不同的数据结构形式。

9. （ ）一个关系中，主键的取值不可以重复，但可以为空。

10. （ ）关系模型的数据结构很简单，只包含单一的数据结构——关系。

11. （ ）一个关系的候选键至少有一个，也可能有多个。

12. （ ）数据的完整性约束能够防止非法用户修改和破坏数据。

13. （ ）所谓的主键不能取空值，是指构成主键的所有主属性中至少有一个不取空值即

可。

14. （ ）任何关系数据库系统都必须支持实体完整性约束和用户定义的完整性约束。

15. （ ）一个关系中同一列的取值可以是不同的数据类型。

16. （ ）向关系中添加数据时可以不考虑关系的完整性约束条件。

17. （ ）RDBMS能够按照用户定义的数据完整性规则自动检验用户的数据操作。

18. （ ）要从关系：选课（学号，课程号，成绩）中查询选修了课程号为‘c01’的课

程，且成绩不及格的学生的学号，相应的关系表达式为π学号(σ课程号=’c01’∧成绩<60(选

课)) 。

19. （ ）关系模型中是通过对关系的运算来表达用户的查询要求。

20. （ ）假设有如下的关系：

选课（学号，课程号，成绩）

6

该关系的候选键是（学号，课程号），而（学号，课程号，成绩）同样也是该关系的候选键。

21. （ ）制定用户定义的完整性规则是为了从语义上保证数据的正确性。

22. （ ）在关系模型中，实体型之间的联系也用关系来表示。

23. （ ）SQL命令只能用来对数据表进行查询操作。

24. （ ）关系数据库中连接查询可以实现多个表的综合查询。

25. （ ）关系数据库中的一个数据表通常是依据概念模型中的一个实体型建立起来的。

四、计算题

1. 假设有关系：学生（学号，姓名，性别，班级），要查询090511班所有男同学的信息，

请写出相应的关系运算表达式。

2. 假设有关系：选课（学号，课程号，成绩），要查询学号为09051109的同学选修课程成

绩不及格的课程号和具体成绩，请写出相应的关系运算表达式。

3. 假设有2个关系：学生（学号，姓名，性别，班级）、选课（学号，课程号，成绩），要

查询090511班的李莉同学选修的所有课程的课程号及成绩，请写出相应的关系运算表达式。

4. 假设有关系：学生（学号，姓名，性别，班级），关系表达式：π姓名（σ班级=”090511”

∧性别=”女”（学生）能够查询到什么信息？

5. 假设有3个关系：学生（学号，姓名，性别，班级）、课程（课程号，课程名，学分）、

选课（学号，课程号，成绩），下面的关系表达式能够查询到什么信息？

π姓名（σ课程名=”数据库原理及应用”（学生选课课程））

6. 假设有2个关系：课程（课程号，课程名，学分）、选课（学号，课程号，成绩），关系

表达式：π学号,成绩（σ课程名=”计算机原理”（课程）选课）能够查询到什么信息？

7. 对数据库中的选课表（包含字段：学号、课程号、成绩），要查询选修了课程号为06001

的课程、且成绩在90分以上（包括90分）的所有同学的学号，请写出相应的SELECT命

令。

8. 针对数据库中的2个数据表：学生（包含字段：学号、姓名、性别、班级）、选课（包含

字段：学号、课程号、成绩），要查询所有选修了课程号为06001的课程的同学姓名及成绩，

请写出相应的SELECT命令。

9. 针对数据库中有学生数据表（包含字段：学号、姓名、性别、班级），要统计查询090511

班学生人数，请写出相应的SELECT命令。

10, 对数据库中的选课表（包含字段：学号、课程号、成绩），要查询课程号为06001的课

程成绩的最高分，请写出相应的SELECT命令。

五、简答题

1. DBMS是什么？其功能？它与数据库系统的关系？

2. 某单位有若干个仓库，每个仓库存放多种零件，每种零件根据其组装产品的不同会存放

在不同的仓库中。仓库信息包括仓库号、面积、电话，零件信息包括零件号、名称、规格、

单价、描述，仓库存放零件要记录库存量。请构建相应的概念数据模型。

3. 某单位有若干个工程项目，每个项目由多家供应商供应多种零件，每家供应商为多个项

目提供零件。供应商信息包括供应商号、姓名、地址、电话、帐号，项目信息包括项目号、

预算、开工日期，零件信息包括零件号、名称、规格、单价、描述。供应商提供零件时要记

录供应数量。请构建相应的概念数据模型。

4. 简述概念数据模型与逻辑数据模型之间的区别与联系？

5. 简述关系数据模型的三要素。

6. 举例说明什么是关系的候选键？

7. 在一个关系数据库中，“用户能够向数据表中添加任何数据”，这句话是否正确？为什么？

8. 举例说明什么是数据的相容性？关系模型如何加以保证？

7

9. 开发一个图书借阅管理系统时，构建了下面的E-R模型，请将它转换为等价的关系模型，

并指明各个关系的主键。

10. 某简化的网上购物系统的E-R图如下，数据间有这样的关系：

（1）一个客户（编号唯一）可以拥有多个订单，每个订单仅属于一个客户；

（2）一个订单只能订购一种商品，每种商品可以出现在多张订单中。

请说明“拥有”联系、“出现”联系分别是哪种实体型联系，并在图中标示出来。给出“订

单”关系模式，指出它的主键和外键。

第4章 数据结构

二、填空题

1．向一个长度为n的顺序表的第i个位置(1≤i≤n+1)插入一个元素时，需向后移动（ ）

个元素。

2．顺序表中逻辑上相邻的元素的物理位置（ ）相邻。

3．单链表中逻辑上相邻的元素的物理位置（ ）相邻。

4．在单链表中，除了首结点外，任一结点的存储位置由（ ）指示。

5．只允许在（ ）进行插入、删除运算的线性表，称为“栈”。

6．在栈中存取数据遵从的原则是（ ）。

7．单链表表示法的基本思想是用（ ）表示结点间的逻辑关系。

8．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是（ ）。

9．数据的逻辑结构又可以分为（ ）、树形结构、图形结构和集合结构四大类。

10．深度为5的二叉树，最多有（ ）个结点。

11．对任何二叉树，若度为2的节点数为n

2

，则叶子数n

0

=（ ）。

12．每个二叉链表的访问只能从指向（ ）结点的指针开始，该指针具有标识二叉链表

的作用。

13．二叉链表中每个链结点的每个指针域必须有一个值，这个值或者是指向该结点的一个孩

8

子的指针，或者是（ ）。

14．具有n个结点的二叉树中,一共有（ ）个指针域。

15．在二叉树中，第i层的结点总数不超过（ ）。

16．若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根

遍历序列中的（ ）个结点。

17．任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为

（ ）个。

18．数据的（ ）就是数据元素间具有的逻辑关系。

19．一棵有n个结点的满二叉树有（ ）个度为1的结点。

20．深度为k的完全二叉树至少有（ ）个结点。

21．具有256个结点的完全二叉树的深度为（ ）。

22．深度为h 的完全二叉树至多有（ ）棵。

23．一棵有n个结点的满二叉树深度为（ ）。

24．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是（ ）。

25．链表对于数据元素的插入和删除不需移动结点，只需改变（ ）。

三、判断题

1．（ ）线性表的逻辑顺序与存储顺序总是一致的。

2. （ ）每种数据结构都只具备三种基本运算：插入、删除和查找。

3. （ ）顺序存储的线性表可以按序号随机存取。

4. （ ）顺序栈是一种规定了元素进栈顺序的栈。

5. （ ）若一个树叶是某二叉树的前序遍历的最后一个结点，则它必是该二叉树的中序

遍历最后一个结点。

6. （ ）顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。

7. （ ）取顺序表的第i个元素的时间同i的大小有关。

8．（ ）已知指针P指向单链表L的某结点，执行语句P=P->next不会删除该链表中的结

点。

9．（ ）在一棵非空二叉树的中序遍历序列中，根结点的后边是其右子树的所有结点。

10．（ ）数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。

11. （ ）队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型

结构。

12. （ ）完全二叉树一定存在度为1的结点。

13. （ ）二叉树只能用二叉链表表示。

14. （ ）在单链表中，指针p指向元素为x的结点，实现"删除x的后继"的语句是

p->next=p->next->next。

15. （ ）单链表从任何一个结点出发，都能访问到所有结点。

16. （ ）若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列

1，5，4，6，2，3。

17. （ ）栈和队列都是顺序存储结构的线性结构。

18. （ ）线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特

性，因此是属于同一数据对象。

19. （ ）在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

20. （ ）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是

随机存取的存储结构。

21. （ ）在线性链表中删除中间结点时，只需将被删结点释放。

9

22. （ ）完全二叉树中，若一个结点没有左孩子，则它必是树叶。

23. （ ）完全二叉树的存储结构通常采用顺序存储结构。

24. （ ）在一颗二叉树中，假定每个节点只有左子女，没有右子女，对它分别进行前序

和后序遍历，则具有相同的结果。

25. （ ）在栈满的情况下不能作入栈运算，否则产生“上溢”。

四、计算题

1. 设有一个顺序栈S,元素s1,s2.s3.s4.s5.s6依次进栈，如果6个元素的出栈顺序为

s2,s3,s4,s6,s5,s1,则顺序栈的容量至少应为多少？

2. 一棵有124个叶子的完全二叉树，最底层至少有多少个结点？

3. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是？

4. 已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子有多少个？

5. 一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有多少个结点？

6. 深度为h的满m叉树的第k层有多少个结点？ (1=

7. 高度为 K的二叉树最大的结点数为？

8. 已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？

9. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元

素是？

10. 有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，

D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？

五、简答题

1. 数据的逻辑结构可以分为几类？哪几类？

2. 数据的物理结构可以分为几类？哪几类？

3. 说明线性表、栈与队的异同点

4. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？

5. 设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列

车开出车站的所有可能的顺序。

6. 一个队列的入队序列是1，2，3，4，则队列的输出序列是什么？

7. 给定K(K>=1),对一棵含有N个结点的K叉树（N＞０）、请讨论其可能的最大高度和最

小高度。

8. 已知一棵二叉树的中序（或中根）遍历结点排列为DGBAECHIF，后序（或后根）遍历

结点排列为GDBEIHFCA。试画出该二叉树。

9. 写出图中二叉树的前序，中序和后序的序列

A

B

D

E

H

C

F

I

10. 已知某二叉树的前序序列为：DBACFEG，中序序列为ABCDEFG。请画出该二叉树。

10

参考答案

第1章 计算机基础知识

二、填空题

1、主频 2、输出 3、编译

4、高级语言 5、字形 6、数据

7、16 8、系统软件 9、人工智能

10、存储程序 11、内存 12、程序

13、硬件 14、高速缓冲存储器 15、二

16、应用软件 17、硬件 18、语言处理程序

19、运算器 20、超大规模集成电路 21、符号位

22、字长 23、尾数 24、串行

25、速度

三、判断题

1、错 2、对 3、错 4、错 5、错

6、错 7、对 8、错 9、对 10、错

11、错 12、错 13、对 14、错 15、错

16、对 17、对 18、对 19、对 20、错

21、对 22、对 23、对 24、错 25、错

四、计算题

1、10110100对应的原码是：10110011 对应的十进制数是：-76

2、十六进制数30E对应的十进制数为：782

八进制数21734对应的十进制数为：9180

30E与八进制数21734的和为：782+9180=9962

3、1000*32*32/8/1024=125KB

4、255*2048*63*512/1024/1024/1024=15.75GB

5、4KB/2=4*1024*1024/2=2097152个

6、十进制数-101的原码为：11100101

补码为：10011010+1=10011011

7、(2036)

D

=(1424)

H

国标码：(1424)

H

+(2020)

H

=(3444)

H

机内码：(3444)

H

+(8080)

H

=(B4C4)

H

8、 16*1024*1024*1024/1024/128/512=256个

9、(4F2.A)

H

=(1.1010)

B

=(2362.5)

O

10、(345.44)

O

=3*82+4*8+5+4*8

-1

+4*8

-2

=229+0.5+0.0625=229.5625

五、综合题

1、总线是—组能为多个部件分时共享的公共信息传送线路。按照任务可以分为，内部总线、

系统总线和外部总线。

2、机器语言、汇编语言和高级语言

面向过程语言：Fortran、Pascal、COBOL、 C语言等

面向对象语言：VB、VC++、Delphi、Java等

3、

名称

内存储器

简称

内存

用途

存放程序运行期间所

需的程序和数据

特点

存储容量小，存取速度快

断电后所存储的信息全部丢失

11

外存储器 外存

长期存放大量程序和

数据

存储容量大，存储速度相对内存慢；

存储的信息稳定，无需电源支持，关机后信息

仍保存（不丢失）

4、关系是：若地址总线为n位，则可寻址空间为2

n

字节。

寻址空间为：2

24

B=4096MB

5基数为r；整数部分右数第i位的位权是r

i-1

,小数部分左数第i位的位权是r

-i

6、 易于物理实现：因为具有两种稳定状态的物理器件很多;

机器可靠性高：

运算规则简单：二进制数的运算法则比较简单。

7. 1) 运算速度快 2) 计算精度高 3) 具有超强的“记忆”能力

4) 具有逻辑判断能力 5) 自动化程度高。

8、管理计算机系统的全部硬件资源、软件资源及数据资源，

提供用户与计算机硬件之间的接口

9、 将汇编语言程序翻译成机器语言程序的程序

将高级语言程序翻译成机器语言程序的程序

10、控制器、运算器、存储器、输入设备、输出设备。

第2章 计算机网络技术基础

二、填空题

1、局域网 2、域名 3、客户机

4、网络协议 5、网络适配器 6、48

7、语法 8、邮局 9、邮件客户端程序

10、TCP /IP 11、ADSL 12、TCP /IP

13、IP地址 14、WAN 15、只读存储器

16、物理 17、网络 18、FTP

19、广播 20、介质访问 21、网络层

22、ipconfig/all 23、32

24、与 25、调制解调器

三、判断题

1、错 2、错 3、错 4、对 5、错

6、对 7、对 8、错 9、错 10、对

11、错 12、对 13、错 14、对 15、对

16、对 17、错 18、对 19、错 20、错

21、对 22、错 23、错 24、错 25、错

四、计算题

1、先将IP地址与子网掩码换成二进制

188.188.0.111为 10111100.10111100.00000000.01101111

188.188.5.222为 10111100.10111100.00000101.11011110

255.255.254.0为 11111111.11111111.11111110.00000000

将两个IP地址分别与子网掩码进行按位与运算，得

10111100.10111100.00000000.00000000

10111100.10111100.00000100.00000000

网络标识不一样，即不在同一网段

2、在数据通信中，64kbps=64000bps在计算机中100kB=1024B=100*1024*8bit

则传输时间=文件大小/速率=(100*1024*8)bit/(64*1000)bps=12.8s

12

3、 要划分4个子网用2位主机地址，子网掩码统一为255.255.255.192。

第一个子网有效主机ip地址为：222.97.255.1-222.97.255.62

第二个子网有效主机ip地址为：222.97.255.65-222.97.255.126

第三个子网有效主机ip地址为：222.97.255. 129-222.97.255.190

第四个子网有效主机ip地址为：222.97.255. 193-222.97.255.254

4、248化为二进制位11111000，用三位给子网内主机编号，

3

则可容纳的主机数为2-2=6台

5、要划分8个子网用3位主机地址，最后八位为：11100000

所以子网掩码统一为255.255.255.224。

6、 将子网掩码 255.255.240.0

化成二进制得 11111111 11111111 11110000 00000000

12

即最大主机数为2-2=4096-2=4094台

7、 将01100010化成十进制为98；

将11000110化成十进制为198；

将00001101化为十进制为13；

将00100010化为十进制为34；

因此IP地址为00100010的点分十进制表示为98.198.13.34

8、将98化成十进制为01100010；将198化成十进制为11000110；

将13化为十进制为00001100；将34化为十进制为00100010；

因此IP地址的二进制表示为00100010

9、1Gbps=1000*1000bps则2s传输1000*1000bps*2s/8=250000Byte数据

10

10、10Gbps*1s=10bit

五、综合题

1、逻辑链路控制子层主要提供建立和释放数据链路层逻辑连接提供与高层的接口差错控制

等功能。

2、对CSMA/CD协议的工作过程通常可以概括为：

“发前先听、边发边听、冲突停发、随机重发”。

3、计算机名：hrbeu-44f4d2510网卡地址：00-E0-4C-60-04-BC

IP地址：222.27.255.67子网掩码：255.255.255.0

默认网关：222.27.255.1首选DNS：202.118.176.2

备用DNS：202.97.24.69

4、下一层为上一层服务，上一层依托下一层完成任务。

5、发送端发送数据前向目的端发送一个“连接请求”报文，目的端收到该报文后回送一个

“连接确认”报文，发送端收到“连接确认”报文后，再发送一个“对连接确认的确认”报

文。

6、路由器可以实现网络层以下各层协议的转换。

完成路径选择、流量控制、过滤功能、分割子网和路由选择功能。

7、网络接口层、网际层、传输层和应用层。

8、TCP采用了由接收端控制发送端的数据发送的流量控制策略。发送方按约定连续数量发

送几个数据包后暂停，接收端收到数据包后将其存入缓存，检查收到包的序号，将按序收到

的联号的数据包组成报文上传给上层后，在缓存中删除这些包，然后给发送方发出一个可以

继续发送的消息。发送方收到可继续发送的消息后才继续发送数据包。

9、浏览器与Web服务器建立TCP连接，浏览器通过TCP连接发出一个HTTP请求消息给Web

服务器。Web服务器收到请求后，向浏览器返回该响应消息。浏览器收到该响应消息后释放

13

TCP连接，并解析该超文本文件显示在指定窗口中。

10、决定局域网特征的主要技术有三个：组成网络的拓扑结构、传输介质及介质访问控制方

式；IEEE 802.3标准是总线型网络协议，IEEE 802.5标准是环型网络协议。

第3章 数据库基础

二、填空题

1. 可共享 2. 数据操纵 3. 数据库管理系统 4. 修改

5. 概念数据模型 或 概念模型 6. 实体 7. 元组

8. 关系数据结构 9. 关系 10. 空 或 空值 或 NULL

11. 关系 12. 关系模式 13. 元组 14. 连接 或 自然连接

15. 选择和投影 16. 参照完整性 17. 用户定义的 18. 拒绝

19. 实体 20. Max(成绩) 21. distinct 22. R.A=S.A

23. 关系数据库 24. 结构化查询 或 SQL 25. DBMS 或 RDBMS

三、判断题

1. 错2. 错3. 对4. 错5. 错6. 对7. 错8. 对 9. 错10. 对11. 对12. 错13. 错14. 错15. 错

16. 错17. 对18. 对19. 对20. 错21. 对22. 对23. 错24. 对25. 错

四、计算题

1. σ

班级

=”090511”

∧性别

=”

男

”

（学生）

2. π

课程号

,

成绩

（σ

学号

=”09051109”

∧成绩

<60

（选课））

3. π

课程号

,

成绩

（σ

姓名

=”

李莉

”

∧班级

=”090511”

（学生选课））

4. 090511班女同学名单

5. 查询选修了“数据库原理及应用”课程的学生名单

6. 查询选修计算机原理课程的学生的学号和成绩

7. SELECT 学号 FROM 选课 WHERE 课程号=”06001” AND 成绩>=90

8. SELECT 姓名, 成绩 FROM 学生, 选课 WHERE 学生.学号=选课.学号 AND 课程号

=”06001”

9. SELECT COUNT(*) FROM 学生 WHERE 班级=”090511”

10. SELECT MAX(成绩) FROM 选课 WHERE 课程号=”06001”

五、简答题

1. 答：是数据库管理系统，是位于用户与操作系统之间的一层数据管理软件。它是数据库

系统的组成部分，处于核心地位。其功能：（1）数据定义 （2）数据操纵 （3）数据控制 （4）

数据维护

2．答： 3. 答：

4. 答：二者都是用来抽象和表示事物及事物之间的联系的，但是概念模型是面向用户的，

便于数据库的设计者与客户进行有效的沟通；而逻辑模型则是从DBMS的角度进行描述的，

14

便于在数据库系统实现。设计数据库时，首先建立概念模型，然后依据概念模型再建立逻辑

模型，才能在具体的DBMS中建立数据库。

5. 答：关系的数据结构、关系的操作集合、关系的完整性约束。

6. 答：一个关系中，可以唯一确定一个元组的最小属性集合称为关系的候选键。如课程关

系中，“课程号”属性的每一种取值都会唯一确定一个元组（即一门课程）， 则课程号是关

系的一个候选键。一个关系至少有一个候选键，也可以有多个。

7. 答：不正确。DBMS会自动地对用户添加的数据按照事先定义的完整性规则进行检查，

如果添加的数据违反规则，会加以拒绝。

8. 答：指有些数据的取值应该相互参照且保持一致。例如，选课关系的学号属性的取值应

该参照学生关系中学号的取值，不存在的学生不应该有选课记录，即二者应该是一致的。关

系模型定义了参照完整性约束（规则）来保证数据的相容性。

9. 答：关系模型：

读者(借书证号,姓名,单位) 主键为：借书证号

图书(书号,书名,数量,位置,出版社名) 主键为：书号

出版社(出版社名,电话,邮编,地址,传真) 主键为：出版社名

借阅(借书证号,书号,借阅日期,还书日期) 主键为(借书证号,书号,借书日期)

10. 答：客户与订单：一对多，品与订单：一对多，订单”关系模式：

订单（订单编号，订购数量，支付金额，订购时间，客户编号，商品编号）

外键：订单编号 外键：客户编号、商品编号

第4章 数据结构

二、填空题

1. n-i+1 2. 必定 3. 不一定 4. 其直接前驱结点的指针域的值

5. 一端 6. 后进先出 7. 指针 8. 先进先出 9. 线性结构

10. 31 11. n

2

+1 12. 根 13. 空指针NULL 14. 2n

15. 2

i-1

16. 第一 17. n-2m+1 18. 逻辑结构 19. 0

20. 2

k-1

21. 9 22. 2

h-1

23. log

2

(n+1)

24. n 25. 指针

三、判断题

1. 错 2. 错 3. 对 4. 错 5. 错6. 错7. 错8. 对9. 对10. 错11. 错12. 错

13. 错14. 对15. 错16. 错17. 错 18. 对19. 对 20. 错21. 错22. 对

23. 对24. 错25. 对

四、计算题

1. 至少为3

2. 深度为8的树的叶子最多有128个，所以减去8个叶子同时会在上一层增加4个叶子结

点，此时叶子结点数为128-8+4=124，而最底层结点数为128-8=120，故最底层至少有120

个结点。

3. 11

4. 一棵深度为h的满二叉树的结点个数为2

h

-1，则有：

20≤2

h

-1≤40 即 21≤2

h

≤41 ，h=5

满二叉树中叶子结点均集中在最底层，所以结点个数=2

5-1

=16

5. 2h-1 6. m

k-1

7. 2

k

-1

8. 235。由于本题求二叉树的结点数最多是多少，第7层共有2

7-1

=64个结点，已知有10个

叶子，其余54个结点均为分支结点。它在第八层上有108个叶子结点。所以该二叉树的结

点数最多可达(2

7

-1+108)=235。(注意；本题并未明说完全二叉树的高度，但根据题意，只能

8层。)

15

9. n-i+1 10. 三个：CDEBA，CDBEA，CDBAE

五、简答题

1. 答：数据的逻辑结构可以分成四类，分别是：线性结构、树形结构、图形结构和集合结

构。

2. 答：数据的物理结构可分成两类，分别是：顺序存储结构、链式存储结构。

3. 答：相同点：都属于线性结构。都可以用顺序存储或链式存储；栈和队列是两种特殊的

线性表，即受限的线性表。

不同点：操作方法不同，线性表可以在指定位置插入或删除元素，而栈是只允许在一端进行

插入、删除运算，因而是后进先出的线性表（LIFO）；队列是只允许在一端进行插入、另一

端进行删除运算，因而是先进先出的线性表（FIFO）。

4. 答：① 顺序存储

优点：只存放数据元素，无须额外空间开销；

可快速随机存取任意元素，效率高。

缺点：需要事先申请一片连续空间，且空间大小不易估计，当不合适时会导致空间不足

或浪费；插入或删除元素时需要移动元素，效率低。

②链式存储

优点：无须连续空间，且大小可以不定；

插入或删除元素时效率高。

缺点：指针需要额外空间开销。

若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较

大，且其主要操作是插入、删除操作，则采用链表。

5. 答：至少有14种。

① 全进之后再出情况，只有1种：4，3，2，1

② 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4

③ 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,3,1,4

④ 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3

6. 答：1，2，3，4

7. 答：N个结点的K叉树，最大高度N（只有一个叶结点的任意k叉树）。设最小高度为H，

第i(1<=i<=H)层的结点数K

i-1

，则N=1+k+k

2

+…+ k

H-1

，由此得H=log

K

(N(K-1)+1)

8. 答：

16

A

B

C

D

E

F

G

H

I

9. 答：前序：ABDEHCFI

中序：DBHEACIF

后序：DHEBIFCA

10. 答：

D

B

ACE

F

G

17