全国青少年信息学奥赛《基础知识纲要》和《单元测试》
第1单元：计算机和信息社会
1、信息就是对人们有用的数据、消息。例如，计算机病毒不属于信息范畴；信息技术，简称IT，是以微电子和光电技术为基础，以计算机和通信技术为支撑，以信息处理技术为主题的技术系统的总称，是一门综合性的技术。比如，手工制造不属于信息技术范畴。
2、第一台计算机ENIAC是1946年在美国宾夕法尼亚大学诞生。美籍匈牙利数学家冯·诺依曼在理论上作了指导，他解决了三大问题：一是计算机的逻辑组成；二是机内二进制体系；三是存储程序原理。他设计出第一台具有存储程序功能的计算机EDVAC，存储程序原理实现了计算机自动化，对现代电子计算机的发展产生深远影响。
3、图灵是英国著名科学家，国际设立了一个计算机科研领域的最高奖项――“图灵奖”。 4、计算发展大致经历了四代：计算机的发展至今经历了四代：第一代 电子管计算机(比如：第一台电子计算机ENIAC)；第二代 晶体管计算机；第三代 集成电路计算机；第四代 大规模超大规模集成电路计算机(现在的微型计算机，简称微机，比如P4)。
5、计算机按容量与速度分：巨、大、中、小、微；发展方向：巨、微、网、智、多媒体。 6、我国计算机的发展：1956年起步；1983年1亿次“银河-1”；1992年10亿次“银河-2”；1997年130亿次“银河-3”；1999年3840亿次“神威-1”，形成了“曙光”、“银河”、“神州”、“神威”四大高性能计算机系列，目前只有美、日、中具有开发能力。
7、计算机的特点：(1)、运算速度快，精度高；(2)、具有存储与记忆能力；(3)、具有逻辑判断能力；(4)、自动化程度高。
8、计算机的应用领域：(1)、数据计算(科学计算)：比如人造卫星、导弹的飞行轨道计算；第一台电子计算机ENIAC诞生，主要应用于数据计算。(2)、自动控制(3)计算机辅助设计(CAD)，比如影视特技设计。(4)、办公自动化(OA) ：在办公生活中，利用计算机处理文件，管理事务，查找资料，收发电子邮件，是属于计算机办公自动化的应用。(5)、计算机辅助教学(CAI)(6)、远程教育(7)、人工智能(8)计算机辅助制造(CAM)(9)信息处理：比如学校用计算机对教职工人事档案进行管理。(10)、其它CAT计算机辅助测试，CAE计算机辅助教育，CAP计算机辅助排版系统等。
9、信息学奥赛活动：NOIP(全国信息学奥林匹克分区联赛)、NOI(全国信息学奥林匹克竞赛)、IOI(国际信息学奥林匹克竞赛)、夏令营冬令营集训活动；NOIP 竞赛(复赛)推荐使用的语言环境有gcc/g++、RHIDE、free pascal，注意如Turbo Pascal、Turbo c不是推荐使用语言。
第1单元测试 等级： 1、“计算机辅助教学”的英文缩写为（ ）。
A、CAI B、AI C、CAD D、OA
2、下面有关计算机的特点叙述，不正确的是（ ）。
A．运算速度快 B．有记忆和逻辑判断能力 C．具有自动执行程序的能力 D．至今没有任何人能给出如何求解方法的难题，计算机也都能求出解来
3、自1946年世界上第一台计算机ENIAC诞生至今，计算机性能和硬件技术获得了突飞猛进的发展，五十余年来大致可分为四代，现在应该是（ ）时代。 A．电子管计算机 B．大规模、超大规模集成电路计算机 C．晶体管计算机 D．中小规模集成电路计算机 4、国际设立了一个计算机科研领域的最高奖项――“图灵奖”，他是（ ）科学家。
A、英国 B、美国 C、德国 D、中国 5、IT的含义是（ ）。
A．通信技术 B．信息技术 C．网络技术 D．信息学
6、在下列各软件，不属于NOIP竞赛（复赛）推荐使用的语言环境有（ ）。
A．gcc B．g++ C．Turbo C D．Free Pascal
7、微型计算机的问世是由于（ ）的出现。
A、中小规模集成电路 B、晶体管电路 C、（超）大规模集成电路 D、电子管电路
第2单元：信息的表示与处理
在计算机内部用来传递，存贮，加工处理的数据或指令是二进形式进行的。采用二进制主要因为简单性，易实现性，可靠性，逻辑性。
一、生活中常见进制数以及相互转化
1、十进制数： 数码：0~9； 基数：10； 位权：相应位的权值为10m；逢十进一；
比如十进制数按位权展开：(123.456)10=1*102+2*101+3*100+4*10-1+5*10-2+6*10-3 2、二进制数： 数码：0~1； 基数：2； 位权：相应位的权值为2m；逢二进一； 3、八进制数： 数码：0~7； 基数：8； 位权：相应位的权值为8m；逢八进一； 4、十六进制数：数码：0~F；基数：16； 位权：相应位的权值为16m；逢十六进一； 5、不同进制之间转化：(自己动笔计算转化一遍) (1)、非十进制数转成十进制数：按位权展开。
例：(110101)2=(53)10 (305)8=(197)10 (32CF.48)16=(13007.28125)10
(456.124)8=(302.1640625)10
(2)、十进制数转换非十进制数：整数部分——除以基数(2，8，16)反向取余法；
小数部分——乘以基数(2，8，16)正向取整法。
例：(125.6875)10=(1111101.1011)2 (1725.6875)10=(3275.54)8
(12345.671875)10=(3039.AC)16
(3)、非十进制数之间的相互转换 ①、八→二：一位变三位
例：(714.431)8=(111 001 100.100 011 001)2 (11101110.00101011)2=(345.126)8 ②、十六→二：一位变四位
例：(1AC0.6D)16=(1101011000000.01101101)2 (10111100101.00011001101)2=(5E5.19A)16 ③、二→八：三位变一位。
例：(11101110.00101011)2= (356.126)8 ④、二→十六：四位变一位。
例：(10111100101.00011001101)2=(5E5.19A)
综合题：与十进制数1770对应的八进制数是（ C ）。
A．3350 B．3351 C．3352 D．3540
综合题：(2047)10一(3FF)16+(2000)8的结果是( A )。
A、 (2048)10 B、(2049)10 C、(3746)8 D、 (1AF7)16
注意点：2进制可用字母B表示；8进制可用字母O表示；10进制可用字母D表示；16进制可用字母H表示。
二、计算机的数据与编码 1、数据的单位
位：计算机中最小的数据单位是二进制位，简称位或比特(bit )，m个二进位可以表示2m状态。字节：拜特(Byte, B)，是计算机中用来表示存储空间大小的最基本的容量单位。英文字符一般占一个字节；汉字一般占两个字节。与其它单位的换算关系：1B=8bit，1KB=1024B，1MB=1024KB，1GB=1024MB，1TB=1024 GB。（1024=210）
2、字符编码(对非数值的文字、字符处理进行数字化，即二进制编码) (1)、BCD编码。
(2)、ASCII码：美国信息交换码，它是目前国际上最普遍采用的英文字符编码，有7位和8位两种版本，7位ASCII码可表示27=128个元素。了解ASCII码表，注意0~9，a~z，A~Z，是有序的。
综合题：已知ASCII码表中的大写字母后有6个其它字符，接着便是小写字母。A字母的ASCII码为(41)16，试求如下字母用十进制表示的ASCII码： G →(71 )10 b→ (98 )10
(3)、汉字编码
GB2312-80汉字信息交换码：规定了6763个汉字和682个非汉字图形符号。此标准中，每
个汉字都采两个字节，每个字节只用低7位，此标准的汉字编码表有94行、94列。行号称为区号，列号称位号，行号和列号表示的称区位码。 GB2312-80汉字分：一级汉字有3755个，先按拼音，后按起笔形排列；二级汉字有3008个，按部首排列。
汉字机内码：将区位码的每个字节的第8位“置1”所对应的二进制表示。
汉字输入码(外码)：通常键盘输入而设计的代码，有流水码，音码，形码，音形结合码，比如智能ABC，全拼，五笔字型等。
字形码：是汉字库中存储汉字字形的数字化信息，用用汉字的显示和打印。目前方式为点阵式。如16*16点阵则要占用16*16/8=32字节。字库分为软汉字字库和硬汉字库。
编码关系：汉字输入码(外码)→内部编码→字形码。
综合题：”教授”(JIAO SHOU),”副教授”(FU JIAO SHOU)与”讲师”(JIANG SHI)这三个词的汉字，在GB2312-80字符集中都是一级汉字，对这三个词排序的结果是( D)。
A教授 副教授 讲师 B副教授 教授 讲师 C讲师 副教授 教授 D副教授 讲师 教授 (4)、图像编码
图像文件的字节数=图像分辨率*颜色深度/8，例如：一幅640*480图像分辨率、RGB色一般为24位真彩色，图像未经压缩的数据容量为：640*480*24/8＝921600字节=900KB。
综合题：一位艺术史学家有20000 幅1024 * 768 的真彩色图像，如果将这些图像以位图形式保存在CD 光盘上(一张CD 光盘的容量按600M计算)，大约需要( C )张CD光盘。
A、1 B、 10 C、100 D、1000 E、10000
3、数的表示：计算机中参加运算的数有正负之分，计算机中数的数字和符号用二进制数表示称为机器数，0表示正号，1表示负号；计算机中运算的数一种是规定小数点的位置固定不变——定点数，表示范围太窄，微机多使用定点数；另一种是小数点的位置可以浮动的——浮点数，表示数据范围扩大，多用于数值计算的计算机中，它包括阶码和尾数。
第2单元测试 等级： 1、十进制数42/128的运算结果，可用二进制数码序列表示为（ ）。
A、101010/10000000 B、101010/1000000 C、0.0101010 D、0.101010 2、与十进制数1770对应的八进制数是（ ）。
A、3350 B、3351 C、3352 D、3540 3、已知A=(72E)H，B=(1315)D，则A-B的结果是（ ）。
A、(674)O B、(1AD)H C、(523)D D、(101101011)B 4、(3725)8 + (B)16的运算结果是（ ）。
A、(3736)8 B、 (2016)10 C、 (1111110000)2 D、 (3006)10 E、(7B0)16 5、字节是计算机科学中的一个常用单位，它的英文表达式是（ ）。
A、bit B、byte C、bout D、baud 6、在下列式子中，正确的是（ ）。
A、1KB=1024B，1MB=1024KB B、1KB=1024B，1MB=1000KB C、1KB=1000B，1MB=1024KB D、1KB=1000B，1MB=1000KB 7、在计算机中，一个汉字占（ ）英文字符长度。 A、一个 B、 两个 C、半个 D、 1024个
8、某台计算机的内存容量为640K, 这里的640K 容量是指( ) 字节．
A．640 个 B．640*1000 个 C．640 * 1024个 D．640*1024*1024 个 9、在计算机内部，用来传送、存储、加工处理的数据或指令都是以（ ）形式进行的。 A．十进制码 B．智能拼音码 C．二进制码 D．五笔字型码 10、下列各种说法中，正确的是（ ）。
A、计算机中所有信息都采用二进制编码 B、汉字的计算机机内码就是区位码 C、所有的十进制小数都能准确地转换为有限位二进制小数 D、存储器具有记忆能力，其中的信息任何时候都不会丢失 11、GB2312-80 规定一级汉字3755个，二级汉字3008个，其中二级汉字字库中的汉字是（ ）为序排序的。
A．以笔划多少 B．以部首 C．以ASCII码 D．以机内码
第 4 页 共 20 页
12、在24*24点阵的字库中，汉字‘一’与‘编’的字模占用字节数分别是 （ ）。 A．32，32 B．32，72 C．72，72 D．72，32 13、五笔字型编码属于（ ）。
A．国际码 B．机内码 C．输入码 D．字形码
14、已知小写字母’m'的十六进制的ASCII码值是6D，则小写字母’c'的十六进制的ASCII码值是（ ）。
A．98 B．62 C．99 D．63
15、使用WORD进行文书处理时，伴随“输入——存储——打印”的过程，所涉及的汉字编码分别是（ ）。
A、输入码、机内码、字型码 B、拼音、机内码、交换码 C、拼音、ASCII码、字型码 D、输入码、机内码、打印码 16、至少需要多大的存储容量才能存放一幅分辨率是1024×800的黑白图像（不压缩）（ ）。
A、100G B、100M C、100K D、10M
17、在下列各项中，只有（ ）不是计算机存储容量的常用单位。
A．Byte B．KB C．UB D．TB 18、ASCII码的含义是（ ）。
A．二→十进制转换码 B．美国信息交换标准代码
C．数字的二进制编码 D．计算机可处理字符的唯一编码 19、8位无符号二进制数能够表示的最大十进制数是（ ）。
（A）255 （B）256 （C）64 （D）63
20、假设一台PC机使用32位的地址线管理内存，则内存的最大容量可达到（ ）。
（A）16MB （B）4GB （C）8GB （D）256MB
第3单元：计算机组成及工作原理
1、逻辑功能来讲计算机由五大部件组成：控制器、运算器、存储器、输入设备(如键盘、鼠标、话筒、扫描仪、数字化仪、触摸屏)、输出设备(如显示器、耳机、音箱、绘图仪、打印机、触摸屏)。一个完整的计算机系统是由硬件和软件组成。
2、计算机的硬件
(1)、主板：最大的一块电路板。BIOS基本输入输出系统就是固化在主板上一个 ROM 芯片中。 (2)、中央处理器CPU：它是核心部件，基本功能就是执行指令，不同厂家生产的CPU所能处理的指令集可能不同的，主要由运算器和控制器组成，运算器由算术逻辑单元(ALU)、累加寄存器、数据缓冲寄存器和状态条件寄存器组成。
CPU的主要性能指标是主频和字长。主频就是CPU在1秒内完成的指令周期数，单位有MHZ(兆赫)，GHZ等，比如Pentium III 733 MHZ、Pentium IV 1.8GHZ等，它们主频分别是733 MHZ，1.8GHZ，其中1.8GHZ是最高，主频越高速度越快；字长是计算机进行数据处理时一次存取、加工和传送的数据长度，字长越大速度越快，它决定着计算机内部寄存器、ALU和数据总线的位数，直接影响着机器的硬件规模和造价。Intel公司开发的CPU发展，8086(首推字长16位)，8088，80286，80386(迈进字长32位)，80486，Pentium，PentiumⅡ，Pentium III，Pentium IV，Itanium(字长64位)，酷睿表示计算机CPU的型号和档次，档次最高的是酷睿。Intel公司也自己开发了的首颗64位处理器是P4 660。AMD CPU产品有Athlon 64(速龙64位)、AMD Opteron；IBM 开发的有IBM Power 5。
(3)、存储器分为主存储器和辅助存储器 ①主存储器，又称内存储器(简称内存)：包含RAM和ROM两部分。RAM(比如DDR SDRAM)中的信息随时可读写，它的信息是计算机工作时随机写入的，断电信息完全丢失；ROM中的信息是出厂时固化的一些系统程序等，可读不可写，断电信息不丢失。RAM越大，速度越快，没内存计算机无法工作。在内存中，为了区分不同的存储单元，一个内存地址编码对应唯一的一个内存单元，对内存进行读或写操作时，都要给出地址来选择具体单元，每个存储单元占用一个字节。程序和数据在内存中都是用二进制码表示的。
②辅助存储器，又称外存储器(简称外存)：长期保存的数据，断电后信息不丢失，如软盘，
硬盘，光盘，可移动盘，CD-ROM光盘(只能读不能写)等。
综合题：一个向量第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是( B )。 A、 110 B、108 C、 100 D、109
综合题：线性表若采用链表存贮结构，要求内存中可用存贮单元地址( D )。
A、必须连续 B、部分地址必须连续 C、一定不连续 D、连续不连续均可 综合题：设数组a[10..100,20..100]以行优先的方式顺序存储，每个元素占4个字节，且已知a[10,20]的地址为1000，则a[50,90]的地址是( B )。 A、14350 B、 14240 C、15340 D、13250
综合题：微机内的存储器的地址是以( C )编址的。
A、二进制位 B、字长 C、字节 D、微处理器的型号
(4)、高速度缓存(CACHE，又称快存)：解决内存与CPU速度不配匹问题题，存放使用频率较高数据。
(5)、显卡：作用是将视频信号处理后输出到到显示器。集成显卡和独立显卡的区别主要是：独立显卡有自己本身的显示缓存(显存)、而集成显卡则是依赖主机的内存作为显存。断电后显存内容丢失。
(6)、打印机：分击打式和非击打式。击打式有针式打印机，非击打式有喷墨打印机和激光打印机等。激光打印机是用静电吸附墨粉后转移到纸张上。分辨率越高打印质量越好。
(7)、其它设备：无线连接设备——红外方式连接设备、蓝牙方式连接设备、无线网卡方式连接设备；彩色显示器是由红、蓝、绿三色混合而成的，分辨率越大越清晰。
注意点：①CPU访问的速度由高到低：自身寄存器——CACHE——内存——外存(硬盘 、光盘、软盘)；②微型计算机的运算器、控制器及内存储器的总称主机；③对于个人电脑的正常运行必需的组成部件有主板、CPU、内存储器、显卡等，不是必需的部件有外存储器(硬盘 、光盘、软盘、U盘)、外部设备(打印机、扫描仪、耳机、音箱、话筒、网卡等)等，一般只有外存存储器(硬盘 、光盘、软盘、U盘)和ROM断电后仍能保存数据。
3、计算机的工作原理 工作原理：将指挥计算机工作的命令存放在存储中(存储程序)，控制器从存储器(从外存读出到内存后)中逐条取出命令，然后向其它部件发出指令，指挥各部件协调地工作，从完成信息输入，信息加工处理运算或信息输出任务，最后把计算机内存中的数据写入磁盘。计算机处理信息的原理和过程即是输入——存储——处理——输出。
(1)、总线是连接各部件的一组公共信号线，是计算机中传送数据、信息的公共通道。总线由数据总线DB、地址总线AB和控制总线CB的三组信号线组成。总线可分为：ISA总线，VESA总线，PCI总线，MCA总线。目前微机中最常见的是PCI总线。数据总线的宽度决定了一次传递数据量的大小；地址总线决定了CPU所能访问的最大内存空间的大小。
(2)、指令：是一组二进制代码，规定由计算机执行的程序的一步操作。计算机的工作就是顺序地执行放在内存中的一系列指令。指令由操作码和操作数组成，计算机工作时操作码送往控制器的指令寄存器和指令译码器中，并用程序计数器(PC)保存指令的下一条地址，而操作数送往运算器的通用寄存器和算术逻辑单元中。
(3)、计算机的指令系统是这种计算机所能识别并执行的全部指令的集合，它与计算机的硬件密切相关，主要取决于CPU，不同计算机指令系统可能不同。
(4)、为了解决某一问题而设计的一系列指令称为程序。程序是指令的序列，它有顺序、分支和循环三种结构。结构化程序设计思想是自顶向下，逐步求精的设计方法，实现程序的模块化(子程序)。
4、计算机的软件
(1)软件概念：它是计算机程序、方法、规则相关的文档以及在机上运行时所必须的数据。软件发展史上最有名的人物是微软公司总裁比尔·盖茨，它为MITS公司编写了第一个微电脑的BASIC程序设计软件。1980年开发了MS—DOS操作系统软件，使PC(个人计算机)的研制得以成功，以后他又开发了FORTRAN、COBOL等高级程序设计语言软件。90年代以后，推出了窗口操作系统软件。第一个给计算机写程序的人是Ada Lovelace。
(2)软件分类：系统软件和应用软件，系统软件是应用软件的基础。
①系统软件包括操作系统、程序设计语言、诊断测试软件、数据库管理系统等。常见的操作系统有DOS、Ucdos、Windows 95、Windows 98、Windows 2000、Windows XP、Windows Vista、Unix、Linux、os/2等。操作系统是管理计算机软、硬件资源，控制程序运行，改善人机界面和
为应用软件提供运行环境的系统软件。常见的程序设计语言有：Basic、Pasca、c、c++、fortran、vb、vc++、delphi、java等程序设计语言。常见的数据库管理系统有Foxpro、SQL Server、Oracle、 Access等，而且这些是关系型(二维表形式)的数据库管理系统。
②应用软件是指用来完成具体任务的软件。如文字处理软件WPS和Word、电子表格excel、发送接收电子邮件软件Outlook Express、画图软件、多媒体创作工具PowerPoint、网络浏览软件IE(微软公司开发的Internet Explorer)、图像处理软件(photoshop)、游戏软件、动画制作软件(flash、3dmax)、打字练习软件、瑞星杀毒软件、金山影霸、WinRAR、Winzip、超级解霸、Foxmail、迅雷、即时通信软件(网易泡泡、MSN Messsenger、Google talk、QQ)等等。计算机软件保护法保护着软件的著作权。
(3)计算机语言：
①、机器语言：能直接被计算机接受并执行的指令称机器指令，运行效率特别高。全部机器指令构成计算机的机器语言。机器语言就是二进制代码，它能直接被计算机识别并执行。缺点：不好记忆、阅读、书写。
②、汇编语言：是面向机器的语言，用助记符号表示二进制代码形式的机器语言，运行效率也较高。克服了机器语言的缺点。汇编语言源程序必须经过汇编程序汇编成目标程序(也就机器语言)，才能被CPU运行。
③、高级语言：高级语言同自然语言和数学语言比较接近的计算机程序设计语言。常见的语言：basic、fortran(第一面向科学计算，第一个高级语言)、pascal、c、Smalltalk(第一面向对象，发明者Alan Kay)、c＋＋(面向对象)、Object Pascal(面向对象)、vb(面向对象)、vc＋＋(面向对象)、delphi(面向对象)、java(面向对象)等。
④、高级语言源程序是通过编译器转成目标程序(也就机器语言)，这就是编译。编译是将整个高级语言源程序翻译成目标程序(机器语言程序)，然后交计算机执行，如Pascal和C；还有一种方式叫解释，解释是对高级语言源程序逐句进行分析，解释执行，不形成目标程序，如：BASIC程序。
注意点：高级语言程序比汇编语言程序执行效率低，但更容易从一种计算机移植到另一种计算机上；与汇编语言相比，高级语言程序更容易阅读；各种高级语言之间语法略有不同；对于同样一段高级语言程序不同的编译器可能产生不同的可执行程序。
第3单元测试 等级： 1、一个计算机系统通常是指（ ）。
A、硬件和固件 B、计算机的CPU C、计算机的硬件 D、计算机的硬件系统和软件系统 2、计算机的主机包括（ ）。
A、运算器和控制器 B、运算器、控制器和硬磁盘存储器 C、CPU 和内存储器 D、CPU和键盘
3、 计算机的显示器属于（ ）。
A、输入设备 B、输出设备 C、输入输出设备 D、数码设备 4、CPU是（ ）。
A、内存 B、处理器 C、输入设备 D、输入出设备 5、RAM是（ ）。
A、光盘 B、随机存储器 C、中央处理器 D、只读存储器 6、下列存储器中，存储速度最快的是（ ）。
A、软磁盘 B、硬磁盘 C、光盘 D、内存 7、硬盘同U盘比较，硬盘的优点是 （ ）。
A、比U盘硬，不易折断 B、便于携带 C、可以写保护 D、 容量大，读写速度快 8、鼠标器通常连接在（ ）。
A、 并行接口上 B、串行接口上 C、 显示器接口上 D、打印机接口上 9、计算机软件系统一般包括（ ）。
A、操作系统和应用软件 B、系统软件和管理软件
C、系统软件和应用软件 D、操作系统、管理软件和工具软件。 10、操作系统是一种（ ）。
第 15 页 共 20 页
Ord(求ASCII码表中一个字符对应的整数；或求布尔值true则为1，false则为0。)
odd(如是奇数则为真，否则为假) pred (求前驱) succ(求后继) length(求字符串的长度) pos(求一字符在另一字符中的开始位置) copy(在一字符串中的某位置获取一定长度的子串) 5、标准过程：(过程本身无返回值，应直接调用)
dec(计数变量减1) inc(计数变量加1) break(退出当前整个循环) continue(继续当前循环的下一次循环) exit(退出子程序返回上一个调用的程序，如在主程则退出整个程序) halt(退出整个程序) Str(将一个整数转为字符串) val(将数串转为数，如不能转换返回错误位置给第三个参数) insert(将字符串中插入一个字符串在某个位置)
Delete(在一个字符串中从某位置删除一定长度的字符串)
第8单元测试 等级： 1、假设：年龄=25，性别=“女”，婚否=FALSE，职称=“讲师”，工资=450，用T：表示真，F：表示假，则下列表达式的结果分别是（ ）。
①（NOT 婚否) AND （性别=“女”） ②（性别=“女”） AND （职称=“教授”） AND (工资<=400) OR (年龄>30) ③（（年龄>20） OR （工资<=400））AND （NOT 职称=“讲师”） （A）T F F （B）F T T （C）F F T （D）T F T 2、已知A = 35H，A /\ 05H \/ A /\ 30H 的结果是（ ）。
A）30H B）05H C）35H D）53H
3、设A = true，B = false，C = false，D = true，以下逻辑运算表达式值为真的是（ ）。
A、 (A ∧B)∨(C ∧D) B、 ((A∧B)∨C)∧D C、A∧((B∨C)∧D) D、 (A∧(B∨C)) ∨D E、(A ∨B)∧(C ∧D)
4、假设A=true，B=false，C=true，D=true，逻辑运算表达式A∧B∨C∧D的值是( )。 （A）true （B）false （C）0 （D）1 (E)NULL
5、在Pascal语言中，表达式 （23 or 2 xor 5）的值是（ ）。 A．18 B．1 C．23 D．32 6、在Pascal语言中，判断整数a等于0或b等于0或c等于0的正确的条件表达式是（ ）。 A．not ((a<>0) or (b<>0) or (c<>0)) B．not ((a<>0) and (b<>0) and (c<>0)) C．not ((a=0) and (b=0)) or (c<>0) D．(a=0) and (b=0) and (c=0)
7、设A=B=True，C=D=False，下列逻辑运算表达式值为假的有（ ）。 A．(﹁A∧B)∨(C∧D∨A) B．﹁(((A∧B)∨C)∧D) C．A∧(B∨C∨D)∨D D．(A∧(D∨C))∧B
第9单元：算法常识
1、算法是指完成某一项任务的方法和步骤，对程序设计而言是对解题过程的准确而完整的描述。算法的性质，有限性；确定性；可行性。对于输入输出，可以没有输入项，但一定要有输出项；算法的改进，在很大程度上推动了计算机科学与技术的进步；判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性；目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法。
2、常见的算法有：穷举、迭代、递推、高精度、递归、回溯、排序、查找等。
（1）谈谈二分查找算法 (只能对有序的顺序表而不能是动态链式表)：如顺序表为小到大，设top为查找区域的开始位置，bot为查找区域的末尾位置，mid为区域的中间位置(top+bot) div 2。如要查找的数X，过程为：X与a[mid］(mid＝(top+bot)div2)比较, 若x=a[mid]则查找到；若x<a[mid]则进一步查找，top不变，bot变成mid-1;若x>a[mid]则进一步查找，top变成mid+1，bot不变；循环到top>bot时找不到停止或找到时停止。
综合题：在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为 (C )。 A、2 B、3 C、4 D、5
（2）递归和非递归算法相比，一般对于较复杂的问题，用递归方式编程一般较简洁，是解
第 16 页 共 20 页
决较复杂问题的强有力的工具，但运行效率要低。在1977年前后形成标准的计算机高级语言“FORTRAN77”禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间。
（3）任何编译系统都不做死循环检查，死循环不属于语法错误，系统也无法检测。
3、算法流程描述可以用：自然语言、程序流程图、N-S图、类程序设计语言(伪码)、程序设计语言。
4、各种排序算法比较：
(1)稳定性比较： 插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的； 选择排序、希尔排序、快速排序、堆排序是不稳定的。
(2)时间复杂性比较：插入排序、冒泡排序、选择排序的时间复杂性为O(n2)； 其它非线形排序的时间复杂性为O(n log2 n)； 线形排序的时间复杂性为O(n)。
(3)其它比较：插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。在“排序的序列局部或整体无序”情况下，快速排序反而慢了。
当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序；当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序；当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序；当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序；在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是选择排序；在待排序的数据表已经为有序时，排序算法中花费时间反而多的是快速排序；实现基数排序不需要进行记录关键字之间的比较，它是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
第9单元测试 等级： 1、算法是指（ ）。
A、为解决问题而编制的计算机程序 B、为解决问题而采取的方法与步骤 C、为解决问题而需要采用的计算机语言 D、为解决问题而采用的计算方法 2、在下列关于计算机算法的说法中，不正确的是（ ）。 A、一个正确的算法至少要有一个输入
B、算法的改进，在很大程度上推动了计算机科学与技术的进步
C、判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性
D、目前仍然存涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法 3、在下列各种排序算法中，不是以“比较”作为主要操作的算法是（ ）。 A、选择排序 B、冒泡排序 C、插入排序 D、基数排序 4、在待排序的数据表已经为有序时，排序算法中花费时间反而多的是（ ）。 A、快速排序 B、插入排序 C、基数排序 D、选择排序 5、近20年来，许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具。在下列关于递归算法的说法中，正确的是（ ）。
A．在1977年前后形成标准的计算机高级语言“FORTRAN77”禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间
B．和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些 C．对于较复杂的问题，用递归方式编程一般比非递归方式更难一些
D．对于已经定义好的标准数学函数 sin(x)，应用程序中的语句“y=sin(sin(x));”就是一种递归调用 6、一个无法靠自身的控制终止的循环成为“死循环”，例如，在Pascal语言程序中，语句“while true do writeln(‘*’);”就是一个死循环，运行时它将无休止地打印*号。下面关于死循环的说法中，只有（ ）是正确的。
A．不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环，因而，任何编译系统都不做死循环检查 B．有些编译系统可以检测出死循环
C．死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查出死循环 D．死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也可以检
第 17 页 共 20 页
测的
第10单元：散列表(哈希表)
1、概念：散列表是存储线性表的又一种方式(顺序，链式)，基本思想是，以线性表中的每个元素的为自变量，通过一种函数h(k)计算函数值，把这个值解释为一块边续存储空间(即数组空间)的单元地址(即下标)，将该元素存储到这个单元中。散列存储中使用的函数h(k),称为散列函数或哈希函数。这个使用的数组空间称哈希表或散列表。
比如：一个线性表：a(18，75，60，43，54，90，46)，选取的散列函数为：h(k)=k mod m(m为散列表的长度)。则对应的散列表为：
这是一种理想的情况，不会有冲突。但在散列存储中，冲突是很难避免的。通常把这种具有不同关键字而具有相同散列地址的元素称为做“同义词”，此叫同义词冲突。
2、散列函数
□直接定址法：h(k)=k+c；如果c取0，则散列地址就是关键字。关键字不同则没有冲突。 □余数法：h(k)=k mod m □数字分析法 □平方取中法 □折叠法 3、处理冲突的方法：
□开放定址法：是从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元并插入的一类处理冲突的方法。以下处理冲突的三种探查法：
(1)、线性探查法：是一种最简单的探查方法，它从发生冲突的d单元起，依次探查下一个单元，直到碰到一个空闲单元为止。探查序列表达式为：(d+i) mod m (0<=i<=m-1)，默认i为1。
(2)、平方探查法、双散列函数探查法。
第10单元测试 等级： 1、设有一个含有13个元素的Hash表(0~12)，Hash函数是：H(key)=key % 13，其中%是求余数运算。用线性探查法解决冲突，则对于序列(2、8、31、20、19、18、53、27)，18应放在第几号格中( )。 A、 5 B、 9 C、4 D、0
第11单元：数据结构
数据结构是指数据与数据之间存在的一定的内在联系，具有一定的逻辑关系，称之为数据的逻辑结构。数据存储在计算机的存储器上，存在着一定的存储联系，称之数据的物理结构，或者存储结构。通常我们所讲的数据结构是指逻辑结构。数据之间的内在联系有多种，常见的数据结构有线性表、栈、队列、矩阵、树、图。
1、线性表
1)定义：线性表是指具有相同性质的数据元素的一个有限序列，该序列中的数据元素，除第一个和最后一个元素外，都有一个直接的前驱元素和一个直接的后继元素。如下的N个元素即为为线性表。如(A1，A2，A3，„„Ak，„„，An)，其中A1称为表头，An称为表尾，表中元素的个数称为表长。在线性表中，元素的位置是有序的，第k个元素Ak的前驱是Ak-1，后继是Ak+1，数据元素之间的这样有序性就是一种线性的关系。
2)存储结构
顺序存储：在内存中为线性表开辟一块连续的存储空间，可用数组描述；静态，程序运行中所占空间不变，进行插入、删除将引起数据的移动。
链接存储：每个结点至少两域，数据域和地址域，利用地址域的指针变量将结点按序连接。动态存储，空间临时申请，使用完后，可以将空间归还。对链表结构进行访问、查找没数组方便，若要查找到某个结点，必须从表头开始顺序查找，直到找到所找结点为止，但如果进行插入、删除操作，则不会引起大量数据移动。
综合题：线性表若采用链表存贮结构，要求内存中可用存贮单元地址(D)
A．必须连续 B．部分地址必须连续 C．一定不连续 D．连续不连续均可 2、栈：它是一种特殊的线性表，仅允许在表的一端进行插入和删除运算。这一端被称为栈
顶，相对一端称为栈底。向一个栈插入新元素又称为进栈、入栈或压栈。它将新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使相临的元素成为新的栈顶元素。所以这样的操作称为后进先出。
综合题：若已知一个栈的入栈顺序是1，2，3，„，n，其输出序列为P1，P2，P3，„，Pn，若P1是n，则Pi是( C )。
A、i B、n-1 C、n-i+1 D、不确定 综合题：设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ C ）。
A、a, b, c, e, d B、 b, c, a, e, d C、a, e, c, b, d D、 d, c, e, b, a
3、队列：它也是一种特殊的线性表，其操作运算是允许在表的一端进行插入运算，而在表的另一端进行删除运算。在运算中，规定插入新元素在表尾进行，删除元素在表头进行。向队列中插入元素称为入队，从队列中删除元素，称之为出队。由于队列的操作分别在表的两端进行，删除操作是将先进去的元素最先出队，后进去的元素后出队，所以这样的操作称为先进先出。
综合题：下列叙述中，正确的是( D )
A、线性表的线性存贮结构优于链表存贮结构 B、队列的操作方式是先进后出
C、栈的操作方式是先进先出 D、二维数组是指它的每个数据元素为一个线性表的线性表。 4、树
(1)、结点的度：子树的个数；树的深度：是树中结点的最大层数。
(2)、二叉树是所有结点的度不大于2的树，结点的子树区分左右，所以二叉树是有序树。它可以是空树，或者是一棵由一个根和两棵互不相交的分别称作左子树和右子树所组成的非空树，左和右子树又同是二叉树，所以二叉树的定义是递归定义。
一棵二叉树中，当第I层的结点为2I-1个时，则称此层的结点数是满的，当树中的每一层都满时，则称此树为满二叉树。
一棵二叉树中，除最后一层外都是满的，并且最后一层或者是满的，或者是在右边缺少连续若个结点，则称此树为完全二叉树。
二叉树性质：二叉树的第N层上最多有2N-1个结点； 深度为K的二叉树最多有2k-1个结点，最少K个结点。
二叉树遍历：先序遍历：先访问根结点，再访问左子树，最后访问右子树。 中序遍历：先访问左子树，再访问根结点，最后访问右子树。 后序遍历：先访问左子树，再访问右子树，最后访问根结点。
说明：已知中序、后序或已知先序、中序可确定二叉树；已知先序、后序不能唯一确定。 (3)、存储结构：静态存储和链式存储。
综合题：完全二叉树的结点个数为11，则它的叶结点个数为（ E ）。
A、4 B、3 C、5 D、2 E、6
综合题：二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D 是G 的父结点，F 是I 的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知F的父结点是（C）
A、无法确定 B、B C、C D、D E、E
综合题：给一棵二叉树的中序遍历为DBGEACHFI和后序遍历为DGEBHIFCA，请画出此二叉树。解如下：
综合题：二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为( B )。
A、4 2 5 7 6 3 1 B、4 2 7 5 6 3 1 C、4 2 7 5 3 6 1 D、4 7 2 3 5 6 1 E、4 5 2 6 3 7 1 综合题：已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6(数字为结点的编号，以下同)后根遍历是 3 2 5 6 4 1，则该二叉树的可能的中根遍历是( B )
A、 3 2 1 4 6 5 B、 3 2 1 5 4 6 C、 2 1 3 5 4 6 D、 2 3 1 4 6 5
(4)、哈夫曼树
叶结点的路径长度：叶结点到根结点路径长度之和。树的带权路径长度（WPL）：所有叶结点的权与它到根结点路径长度的乘积之和。哈夫曼树就是构建WPL最小，基本做法就是要让权大的叶子离根最近。具体做法如下：先从所有结点中找出最小的两个结点作为哈夫曼树的左子树和右子树，产生新
结点并删除此两个最小结点，再从剩余的结点中重复上面操作，直到最后剩余一个结点。比如图C就是结点序列（7，5，2，4）的哈夫曼树。
综合题：构造结点序列（6，5，3，7，1）的哈夫曼树。
解如下：
5、图
(1)图的定义：图是由顶点和边组成的，边表示顶点之间的内在联系。图分为无向图和有向图。图的全部顶点的度数等于所有边数的2倍。
(2)完全图：对于无向图，每两个顶点之间存在着一条边；对于有向图，每两个顶点之间都存在着方向相反的两条边，称此图为完全图。
综合题：无向图G有16条边，有3个4度顶点，4个3度顶点，其余顶点的度均小于3，则G至少（ B ）个顶点。 A、 8 B、 11 C、16 D、 9 E、 10
(3)图的遍历算法：深度优先(遍历时用到栈实现)——从某个顶点开始，搜索相关的下一个结点，再从找到的结点深度优先开始搜索。广度优先(遍历时用队列实现)——从某个顶点开始，搜索出所有的相关结点，再从下个结点广度优先找出相关的所有结点。
(4)图的最小生成树
①有N点的图，用N-1条边连接N个点得到这一棵树，这棵树中各边的权值之和称为这棵生成树的代价，代价最小的生成树称为图的“最小代价生成树”。
②最小生成树kruskal算法：先把所有边排序，一开始生成树为空，每次取当前的最小边，判断它对应的两个顶点是否在生成树中形成“回路”，是则不要把这条边加入生成树，而是换下一条边，否则把这条边加到生成树里。这样做了n-1次后（n为顶点个数），就是最小生成树。
综合题：平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图G 的顶点，每两点之间的直线距离是图G 中对应边的权值。以下哪条边不是图G 的最小生成树中的边( D )。 A、 AD B、 BD C、CD D、 DE E、EA
第11单元测试 等级： 1、线性表若采用链表存贮结构，要求内存中可用存贮单元地址（ ）。
A、必须连续 B、部分地址必须连续 C、一定不连续 D、连续不连续均可 2、若让元素1、2、3依次进栈，则出栈次序不可能出现（ ）的情况。
（A）3、2、1 （B）2、1、3 （C）3、1、2 （D）1、3、2 3、设栈S的初始状态为空，元素a, b, c, d, e, f, g依次入栈，以下出栈序列不可能出现的是（ ）。
A、a, b, c, e, d, f, g B、 b, c, a, f, e, g, d C、a, e, d, c, b, f, g D、d, c, f, e, b, a, g E、g, e, f, d, c, b, a
4、已知队列(13，2，11，34，41，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的元素是( )。 A、5 B、41 C、77 D、13 5、按照二叉数的定义，具有3个结点的二叉树有（ ）种。 A）3 B）4 C）5 D）6
6 9 5 4 1 3 7
13 22
第 20 页 共 20 页
6、完全二叉树的结点个数为11，则它的叶结点个数为（ ）。
A、 4 B、3 C、5 D、2 E、6 7、表达式(1+34)*5-56/7 的后缀表达式为（ ）。
A） 1+34*5-56/7 B） -*+1 34 5/56 7 C） 1 34 +5*56 7/-
D） 1 34 5* +56 7/- E） 1 34+5 56 7-*/
8、高度为 n 的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为 n-1 的满二叉树。 在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有 2381 个结点， 则该树的树高为（ ）
A、10 B、11 C、12 D、13 9、已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同）后根遍历是 3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ ）
A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 1 3 5 4 6 D. 2 3 1 4 6 5 10、 二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D 是G 的 父结点，F 是I 的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知F的父结点是（ ）。
A、 无法确定 B、 B C、 C D、 D E、 E
11、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A、1/2 B、1 C、2 D、4
12、平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图G 的顶点，每两点之间的直线距离是图G 中对应边的权值。以下哪条边不是图G 的最小生成树中的边（ ）。
A、AD B、BD C、 CD D、DE E、EA
13、无向图G有16条边，有3个4度顶点，4个3度顶点，其余顶点的度均小于3，则G至少（ ）个顶点。
A、 8 B、 11 C、16 D、 9 E、 10
14、地面上有标号为A、B、C的三根柱，在A柱上放有10个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3„„，将A柱上的部分盘子经过B柱移入C柱，也可以在B柱上暂存。如果B柱上的操作记录为“进、进、出、进、进、出、出、进、进、出、进、出、出”。那么，在C柱上，从下到上的编号为（ ）。
A．2 4 3 6 5 7 B．2 4 1 2 5 7 C．2 4 3 1 7 6 D．2 4 3 6 7 5
15、已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为节点的编号，以下同），中根遍历是4 2 6 5 1 7 3，则该二叉树的后根遍历是（ ）。
A．4 6 5 2 7 3 1 B．4 6 5 2 1 3 7 C．4 2 3 1 5 4 7 D．4 6 5 3 1 7 2