信息学奥赛初赛复习
前车小学信息组
第一部分：选择题
一、、计算机发展历程
（NOI2007笔试复习题，部分）
1、NOI机试使用的操作系统是：
A. Windows B. Linux C. MacOS D. Vxworks
2、Linux中为文件改名使用的命令是：
A. mv B. ren C. chroot D. su
3、在Linux中返回上一级目录使用的命令是：
A. cd B. cd . C. cd .. D. cd ./
4、使用高级语言编写的程序称之为：
A. 源程序 B. 编辑程序 C. 编译程序 D. 链接程序
5、 属于面向对象程序设计语言的是：
A. C B. C++ C. Pascal D. Basic
6、在Linux系统中，下面的说法中正确的是：
A. 文件夹中的文件可以与该文件夹同名 B. 文件夹中的文件不能与该文件夹同名
C. 在不同文件夹中的两个文件不可以使用相同的文件名 D. 以上说法都不对
7、 一个完整的计算机系统应包括_______。
A.系统硬件和系统软件 B.硬件系统和软件系统
C.主机和外部设备 D.主机、键盘、显示器和辅助存储器
8、目前微型计算机中采用的逻辑组件是_______。
A.小规模集成电路 B.中规模集成电路 C.大规模和超大规模集成电路 D.独立组件
9、 软件与程序的区别是_______。
A.程序价格便宜、软件价格昂贵 B.程序是用户自己编写的，而软件是由厂家提供的
C.程序是用高级语言编写的，而软件是由机器语言编写的
D.软件是程序以及开发、使用和维护所需要的所有文档的总称,而程序是软件的一部分
10、IT表示_______。
A. 通信技术 B. 信息技术 C. 网络技术 D. 信息学
11、计算机中央处理器简称为_______
A. IBM B.UBS C.CPU D.Computer
11、计算机内存储器的作用是_______
A.用来存放暂时不用的程序和数据 B.用来存放当前CPU正在使用的程序和数据
C.用来存放要删除的信息 D.仅用来存储选手的数据和程序
12、用来全面管理计算机硬件和软件资源的软件叫_______
A．操作系统 B．应用软件 C．管理软件 D. 系统平台
13、 LAN是指_______
A．互联网 B．局域网 C．广域网 D. 城域网
14、在微机中，bit 的中文含义是_____。
A. 二进制位 B. 字 C. 字节 D. 双字
15、为了避免混淆，十六进制数在书写时常在后面加字母_____。
A. H B. O C. D D. B
16、.计算机所能辨认的最小信息单位是_______。
A. 位 B. 字节 C. 字 D. 字符串"
17、ASCII的含义是________。
A.条件码 B.二－十进制编码 C.二进制码 D.美国信息交换标准代码
18、在计算机术语中经常用RAM表示________。
A、只读存储器 B、可编程只读存储器 C、动态随机存储器 D、随机存取存储器 19、RAM存储器在断电后，其中的数据会_______。
A.丢失 B.自动保存 C.不变化 D.需人工保存
20、ROM存储器在断电后，其中的数据会_______。
A.丢失 B.自动保存 C.不变化 D.需人工保存
21、现代计算机所应用的存储程序原理是_________提出的。
A.图灵 B.布尔 C.冯·诺依曼 D.爱因斯坦
22、计算机内所有的信息都是以_______数码形式表示的。
A.八进制 B.十进制 C.二进制 D.十六进制
23、计算机能直接识别和执行的语言是________。
A. 机器语言 B. 汇编语言 C. C语言 D. Pascal语言
24、Linux是一个_______操作系统，意思是源码可以免费获得。
A. 开源的 B. 有使用许可的 C. 不开放源代码的
25、NOI的中文意思是：
A. 中国信息学奥赛 B. 中国国家奥委会 C. 国际信息学奥赛D. 中国信息学联赛
[重要作业]
1、微机内的存储器的地址是以（ ）编址的。
A．二进制位 B．字长 C．字节 D．微处理器的型号
2、在24*24 点阵的字库中，汉字“一 ”与“编”的字模占用字节数分别是（ ）。
A．32、32 B．32、72 C．72、72 D．72、32
3、不同的计算机，其指令系统也不相同，这主要取决于 （ ）。
A．所用的操作系统 B．系统的总体结构
C．所用的 CPU D．所用的程序设计语言
4、2KB的内存能存储( )个汉字的机内码
A)1024 B)516 C)2048 D)218
5、下列哪个（些）软件不是操作系统软件的名字（ ）。
A）WindowsXP B) DOS C) Linux D) OS/2 E) ARCH/INFO
6、美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献是（ ）。
A. 提出理想计算机的数学模型，成为计算机科学的理论基础。
B. 是世界上第一个编写计算机程序的人。
C. 提出存储程序工作原理，并设计出第一台具有存储程序功能的计算机EDVAC。
D. 采用集成电路作为计算机的主要功能部件。
E、指出计算机性能将以每两年翻一番的速度向前发展。
7、下列哪个不是CPU（中央处理单元）（ ）。
A. Intel Itanium B. DDR SDRAM C. AMD Athlon64
D. AMD Opteron E. IBM Power 5
8、下面哪个部件对于个人桌面电脑的正常运行不是必需的（ ）。
A. CPU B. 图形卡（显卡） C. 光驱 D. 主板 E. 内存
9、下列哪个软件属于操作系统软件（ ）。
A. Microsoft Word B. 金山词霸 C. Foxmail D. WinRAR E. RED HAT LINUX
10、下列哪个不是计算机的存储设备（ ）。
A. 文件管理器 B. 内存 C. 高速缓存 D. 硬盘 E. U盘
11、下列哪个程序设计语言不支持面向对象程序设计方法（ ）。
A. C++ B. Object Pascal C. TURBO PASCAl D. Smalltalk E. Java
12、设有一个十阶的对称矩阵A．采用压缩存储方式，以行序为主存储，a11为第一个元素。其存储地址为1，每个元素占1个地址空间，则a85的地址为( )。
A) 13 B) 33 C) 18 D) 50
13、奔腾的地址线是32根，最大存储量为 （ ）
A．4GB B．4MB C．32MB
14、JPEG是一种（ ）的图象压缩方式 （ ）
A．有损压缩 B．无损压缩 C．不可压缩 D．以上都正确
15、一台计算机的字长是8字节，表示是 （ ）
A．能处理的数字最大是8个十进制数99999999
B．能处理的字符串最多由8个英文字母组成
C．在CPU中作为一个整体加以传送处理二进制代码为64位
D．CPU的运行的最大结果为2的64次方
16、微型计算机内存储器是按 （ ）
A．二进制位编码 B．字节编码
C．字长编码 D．CPU的型号不同而编址不同
17、下列叙述中正确的是 （ ）
A．汉字的计算机内存是国际码
B．存储器具有记忆能力，其中的信息任何时候都不会消失
C．所有十进制数都能准确的转换为二进制数
D．正数的二进制原码的补码是原码本身
18、PASCAL编译程序的功能是 （ ）
A．把PASCAL源程序转换成可运行的EXE文件
B．生成和修改一个PASCAL源程序
C．实现PASCAL的源程序到等价的目标程序的转换
D．实现PASCAL的源程序到等价的目标码程序的转换
19、操作系统是对什么进行管理的系统软件 （ ）
A．软件 B．硬件 C．计算机资源 D．应用程序
20、计算机处理信息的精度决定于 （ ）
A、CPU主频 B、硬盘的容量 C、系统总线的传输频率 D、CPU字长
21、计算机的基本硬件结构一直沿袭（ ）设计的框架。
A、比尔.盖茨 B、冯.诺依曼 C、布尔 D、图灵
22、在流程图的符号中，菱形框一般作为（ ）
A、起止框 B、输入输出框 C、判断框 D、处理工作框
23、算法的3种结构是（ ）
A、顺序、分支、循环 B、顺序、重复、循环
C、顺序、分支、判断 D、顺序、流程、循环
24、用于管理计算机资源，方便用户使用计算机的是（ ）
A、数据库 B、应用软件 C、操作系统 D、计算机语言
25、分辨率为1280*1024真彩色（16位）的17英寸显示器的显存容量应为（ ）MB。
A、1 B、2.5 C、4 D、8
26、计算机的主存储器容量达到1GB时，其地址的表示至少需要使用（ ）个2进制位。
A、10位 B、20位 C、30位 D、40位
27、PASCAL程序运行时，是在哪种存储器中进行。（ ）
A、硬盘 B、RAM C、ROM D、CACHE
三、计算机中数的表示
1、十进制算术表达式 ：3*512 + 7*64 + 4*8 + 5的运算结果，用二进制表示为（ ）。
A．[1**********] B．[1**********] C．[1**********] D．[1**********]
2、计算机中的数有浮点与定点数两种，其中用浮点数表示的数，通常由（ ）这两部分组成。
A．指数与基数 B．尾数与小数 C．阶码与尾数 D．整数与小数
3、[x]补码=10011000，其原码为( )
A)011001111 B)11101000 C)11100110 D)01100101
4、表达式(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-*/
5、8位无符号二进制数能够表示的最大十进制数是（ ）。
A） 255 B） 256 C） 64 D） 63
6、已知A=(72E)H，B=(1315)D，则A-B的结果是 ( )。
A） (674)O B） (1AD)H C） (523)D D）(101101011)B
7、产生100至300之间的随机整数(Random)，且包含100，300两个整数的表达式（ ）
A．Random(100)+200 B．Random(200)+100
C．RANDOM(201)+100 D．Random(300)
8、在微型计算机中，常用（ ）码实现十进制数与二进制数之间的自动转换 （ ）
A．BCD码 B．ASCII码 C．海明码 D．机内码
9、设有一个十阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为 （ ）
A．13 B．33 C．18 D．50
10、ASCII码的主要作用是 （ ）
A．便与信息交换 B．便于信息存储 C．便于管理 D．便于输出
11、二进制数-0.1101010的补码是（ ）
A、0010101 B、10010110 C、10010101 D、01101010
12、国际信息交换码ASCII码的长度为1个字节，其中的最高位为0，因此ASCII码表中的符号有（ ）个。
A、127 B、128 C、255 D、256
13、十进制数100的反码和补码表示分别是（ ）
A、9BH和64H B、64H和9BH C、64H和64H D、9BH和9BH
14、关于“零”的原码、反码、补码，下列说法正确的是（ ）
A、零的原码表示只有一种 B、零的反码表示只有一种
C、零的补码表示只有一种 D、零的原码、反码、补码表示都有两种
四、网络知识
1、调制解调器又称为Modem，可用于连结计算机与电话线拨号上网。调制是指 （ ）
A．把电信号转换成光信号 B．把光信号转换成电信号
C．把模拟信号转换成数字信号 D．把数字信号转换成模拟信号
2、OSI的7层协议中，最底层是 （ ）
A．会话层 B．数据链接层 C．物理层 D．网络层
3、“网络通信协议”，如：Internet采用的TCP/IP协议是一组 （ ）
A．软件 B．存储器 C．外部设备 D．约定的规则
4、国际互联网的目的在于使不同网络上的用户相互通信，交换信息，那么用于网络之间互连的中继设备称 （ ）
A．放大器 B．网桥 C．网关 D．网间连接器
5、在TCP/IP协议中，TCP和IP分别提供什么服务 （ ）
A．传输层、网络层 B．链路层、网络层
C．传输层、会话层 D．物理层、链路层
6、TCP/IP协议是指 （ ）
A．文件传输协议/远程登陆协议 B．邮件传输协议/远程登陆协议
C．传输控制协议/因特网互联协议 D．文件传输协议/邮件传输协议
7、Intel 给我们提供了资源共享、浏览、检索信息和远程登录等多种服务，下面几个选项中用于远程登录的是（ ）
A、Telnet B、E-Mail C、TCP/IP D、WWW
8、IE是目前流行的浏览器软件，它的工作基础是解释执行用（ ）语言书写的文件。
A、VC B、C++ C、HTML D、HTTP
9、计算机网络最大的优点是（ ） 。
A、精度高 B、资源共享 C、运行速度快 D、存储容量大 E、逻辑判断能力强
10、TCP/IP协议共有( )层协议
A)3 B)4 C)5 D)6
11、IP v4地址是由( ) 位二进制数码表示的。
A) 16 B) 32 c) 24 D) 8
五、二进制的逻辑运算
1、已知 A=11001010B B=00001111B C=01011100B, A∨B∧C=( )B.
A、11001110 B、01110110 C、11101110 D、01001100
2、已知A = 35H，A /\ 05H \/ A /\ 30H 的结果是：（ ）。提示：先化成二进制。
A）30H B）05H C）35H D）53H
3、假设A=true，B=false，C=true，D=true，逻辑运算表达式A∧B∨C∧D的值是( )。
A)true B)false C)0 D)1 E)NULL
4、逻辑代数式子f=AB+ABC+AB(C+D), 则f的简化式子为( )。
A) AB B) A+B C) ABC D) ABCD
5、两个十进制数13与14，将它们进行“与”运算，其值为（ ）
A、27 B、12 C、15 D、11
6、在Pascal程序中，表达式（200 or 10）的值是（ ）。
A．20 B．1 C．220 D．202
7、在 Pascal 语言中，表达式 (23 or 2 xor 5)的值是（ ）
A. 18 B. 1 C.23 D.32
六、集合运算
1、设全集E={1，2，3，4，5}，集合A={1，4}，B={1，2，5}，C={2，4}，则集合（A ∩B）∪～
C 为（ ）。
A） 空集 B） {1} C） {3，5} D）{1，5} E） {1，3，5}
2、设全集I = {a, b, c, d, e, f, g}，集合A = {a, b, c}，B = {b, d, e}，C = {e, f, g}，那么集合(AB)(~CB)为（ ）。
A. {a, b, c, d} B. {a, b, d, e} C. {b, d, e} D. {b, c, d, e} E. {d, f, g}
3、已知集合E={2，３，５，１，６}，请问Ｅ的所有子集个数是多少？（ ）
Ａ) 25 Ｂ) 10 Ｃ) 32 Ｄ) 64
4、设全集E={1,2,3,4,5},集合A={1,2,5},B={1,4},C={2,4}，则集合(A+B)*C-(A*B)为（ ）。
A、空集 B、{1} C、{2，4} D、{1，3，5}
七、数据结构
1、已知队列（13，2，11，34，41，77，5，7，18，26，15），第一个进入队列的元素是13，则第五个出队列的元素是（ ）。
A） 5 B） 41 C） 77 D） 13 E） 18
2、线性表若采用链表存贮结构，要求内存中可用存贮单元地址（ ）．
A．必须连续 B．部分地址必须连续
C．一定不连续 D．连续不连续均可
3、下列叙述中，正确的是（ ）．
A． 线性表的线性存贮结构优于链表存贮结构
B． 队列的操作方式是先进后出
C． 栈的操作方式是先进先出
D．二维数组是指它的每个数据元素为一个线性表的线性表
4、某数列有1000个各不相同的单元，由低至高按序排列；現要对该数列進行二分法检索（binary search），在最坏的情況下，需检视（ ）个单元。
A．1000 B．10 C．100 D．500
5、在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为( )
A)2 B)3 C)4 D)5
6、以下哪一个不是栈的基本运算( )
A)删除栈顶元素 B)删除栈底的元素
C)判断栈是否为空 D)将栈置为空栈
7、设栈S和队列Q的初始状态为空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通过栈S，一个元素
出栈后即进入队列Q，若出队的顺序为e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈S的容量至少应该为（ ）。
A）2 B）3 C）4 D）5
8、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e2,e4,e3,e6,e5,e1，则栈S的容量至少应该为（ ）
Ａ) 2 Ｂ) 3 Ｃ) 4 Ｄ) 5
9、对按关键字排序好的线性表进行二分查找，该线性表适合的存储结构为 （ ）
A．顺序结构 B．链接存储 C．索引存储 D．散列存储
10、在数据结构中，链表是（ ）
A、顺序存储的线性表结构 B、非顺序存储的线性表结构
C、非顺序存储的非线性结构 D、顺序存储的非线性表结构
11、在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主要将要输出打印的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个（ ）结构。
A．堆栈 B．数组 C．线性表 D．队列 E．链表
例1：设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一个位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有15元素。答案：50-45+10=15。
如果反过来，头10，尾45，则元素个数是45-10=35。
元素的个数是：当队尾>队头的时候，队尾减去队头。反之，容量-队头+队尾）
例2、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。
（A）1和5 （B）2和4 （C）4和2 （D）5和1
例3、设循环队列中数组的下标范围是1–n，其头尾指针分别为f和r，则其元素个数为（ ）．
A．r- f B．r- f +1
C．（r- f ） MOD n+1 D．（r- f + n） MOD n
八、树（详见高级本P108-111）
[补充作业]
1、给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA 画出此二叉树。 2、已知，按中序遍历二叉树的结果为：abc
问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。5种
3、一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有( )个结点
h A)2-1 B)2h-1 C)2h+1 D)h+1
4、按照二叉数的定义，具有3个结点的二叉树有（ ）种。
A）3 B）4 C）5 D）6
（卡特兰数，NOI专刊 第3期 25页）
5、设有一棵k叉树，其中只有度为0和k两种结点，设n 0 ，n k ，分别表示度为0和度为k的结
点个数，试求出n 0 和n k之间的关系（n 0 = 数学表达式，数学表达式仅含n k 、k和数字）。
6、一个高度为h的二叉树最小元素数目是( )。
A)2h+l B)h C)2h-1 D)2h E)2h-l
7、一棵含有101个结点的完全二叉树存储在数组A[1..101]中， 对1≤k≤101,若A[k]是叶子结点，则k的最小值是: ( )
A) 51 B) 50 C) 49 D) 48
8、如果一棵m度树中有n1个度为1的结点，n2个度为2的结点，„„.有
nm个度为m的结点,则该树中叶结点的的个数( ).
A） N1 B） M-N1-N2
C） N1+2N2+……+(M-1)NM-1+1 D） N2+2N3+……+(M-1)NM+1
9、对于一颗二叉树T，设n0、n1、n2分别是度数为0、1、2的顶点数，则下列判断中正确的是（ ）
A、n0=n2+1 B、n1=n0+1 C、n2=n0+1 D、n2=n1+1
10、一棵n个节点的完全二叉树，则该树的高度h 为（ ）
A、n/2 B、log (n) C、log(n)/2 D、[log(n)]+1
四、图（详见高级本P123-126）
运用prim算法和kruskal算法分别画出图1的最小生成
程。
2 3 4 4 5 7 12 树形成的过
九、排序算法（详见高级本）
[重要作业]
1、下列排序算法中，最坏情况下的时间复杂度最低的是（ ）
A、堆排序 B、选择排序 C、快速排序 D、插入排序
2、在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是（ ）．
A 堆排序 B 希尔排序 C 冒泡排序 D 快速排序
3、利用改进的选择排序算法（从小到大）对以下数据（75、84、65、73、55、52、79、66） 进行一趟操作的结果是（ ）。
A、52、75、84、65、73、55、66、79 B、75、65、73、55、52、79、66、84
C、52、84、65、73、55、75、79、66 D、52、84、75、73、65、55、79、66
4、对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为。
A、1，2，3 B、9，5，2，3 C、9，5，3 D、9，4，2，3
5、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ）。
A．{38，46，79，56，40，84} B．{38，79，56，46，40，84}
C．{40，38，46，56，79，84} D．{38，46，56，79，40，84}
综合练习
1、计算机各部分之间的信息传输是通过总线结构来实现的。总线又分为三部分，下列不是总线三部分的是( )
A. 地址总线 B. 数据总线 C. 指令总线 D. 控制总线
2. 计算机指令是由一些简单的电信号来控制的。机器指令通常包括
( )
A. 地址码、控制码 B. 控制码、操作码
C. 识别码、操作码 D. 操作码、地址码
3. 计算机网络的主要目的是实现资源共享，它采用了多种连接方式将多台计算机连接在一起。以下不属于计算机网络采用的拓扑结构是( )
A. 总线结构 B. 星型结构 C. 树型结构 D. 环型结构
4、在计算机中，防火墙的作用是（ ）。
A. 防止火灾蔓延 B. 防止网络攻击
C. 防止计算机死机 D. 防止使用者误删除数据
5、 网络协议是支撑网络运行的通信规则，因特网上最基本的通信协议是( )。
A. HTTP协议 B. TCP/IP协议
C. POP3协议 D. FTP协议
6、 某处于环境恶劣高山之巅的气象台要在短期内接入Internet网，现在要选择连接山上山下节点的传输介质，恰当的选择是：( )
A. 无线传输 B. 光缆 C. 双绞线 D. 同轴电缆
7、在下列关于计算机算法的说法中，不正确的是（ ）。
A. 一个正确的算法至少要有一个输入
B. 算法的改进，在很大程度上推动了计算机科学与技术的进步
C. 判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性
D. 目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法
8、线性表（ a1,a2,„,an）以链表方式存储时，访问第i位置元素的时间复杂性为( )
A．O（i） B．O（1） C．O（n） D．O（i-1）
9、．一个n个顶点的强连通图，至少有多少个有向边( )。
A．n-1 B．（n-1）n C．（n-1）n/2 D．n
10. 对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为( )。
A. 1，2，3 B. 9，5，2，3
C. 9，5，3 D.9，4，2，3
10、树形结构中数据元素之间存在（ ）的关系。
A. 一对一 B. 一对多 C. 多对一 D. 无法确定
11、链表不具有的特点是（ ）。
A. 可随机访问任一元素 B. 插入删除不需要移动元素
C. 不必事先估计存储空间 D. 所需空间与线性表长度成正比
12、广义表A＝（a，（a，（a）））的深度为（ ）。
A. 3 B. 4 C. 5 D. 6
13、请指出在顺序表 { 2、5、7、10、14、15、18、23、35、41、52 }中，用二分法查找关键码12需做多少次关键码比较。（ ）
A． 2 B. 3 C. 4 D. 5
14、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ）。
A．{38，46，79，56，40，84} B．{38，79，56，46，40，84}
C．{40，38，46，56，79，84} D．{38，46，56，79，40，84}
15、 一数组构造双栈，栈1的栈底在数组的低端，栈2的栈底在数组的高端，如果进栈的序列为A、
B、C、D、E，则执行操作栈1进栈、栈2进栈、栈2出栈、栈1出栈、栈2进栈、栈2进栈、栈1进栈、栈2出栈、栈1出栈、栈2出栈后得到的序列为
A．BAEDC B CEDAB C BADEC D ABCDE
16、对于线性表L=（a1，a2，„，an），下列说法正确的是（ ）。
A、每个元素都有一个直接前驱和一个直接后继
B、线性表中至少要有一个元素
C、表中所有元素的大小排列顺序必须是由小到大或由大到小
D、除第一个和最后一个元素外，每个元素都有且仅有一个直接前驱和一个直接后继
17、利用改进的选择排序算法（从小到大）对以下数据（75、84、65、73、55、52、79、66） 进行一趟操作的结果是（ ）。
A、52、75、84、65、73、55、66、79 B、75、65、73、55、52、79、66、84
C、52、84、65、73、55、75、79、66 D、52、84、75、73、65、55、79、66
18、以下（ ）不是栈的基本运算？
A、删除栈顶元素 Ｂ、删除栈底元素
Ｃ、判断栈是否为空 Ｄ、将栈置为空栈
19、将下三角矩阵A[1．．8，L．8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7，5]的地址为 。
A、1020 B、1100 C、1080 D、1120
20、两个栈共享一个存储空间的好处是（ ）。
A、节省存储空间，降低上溢发生的机率 B、减少存取时间，降低下溢发生的机率
C、节省存储时间，降低下溢发生的机率 D、减少存取时间，降低上溢发生的机率
21、一个递归算法必须包括（ ）
A. .递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部分
22、以下哪一个不是栈的基本运算（ ）
A、删除栈顶元素 B、删除栈底元素 C、判断栈是否为空 D、将栈置为空栈
23、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ）。
A．{38，46，79，56，40，84} B．{38，79，56，46，40，84}
C．{40，38，46，56，79，84} D．{38，46，56，79，40，84}
24、线性表L=（a1，a2，„，an），下列说法正确的是（ ）。
A. 每个元素都有一个直接前驱和一个直接后继
B. 线性表中至少要有一个元素
C. 表中诸元素的排列顺序必须是由小到大或由大到小
D. 除第一个和最后一个元素外，每个元素都有一个仅有一个直接前驱和直接后继
25、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ）。
A．{38，46，79，56，40，84} B．{38，79，56，46，40，84}
C．{40，38，46，56，79，84} D．{38，46，56，79，40，84}
26、一棵二叉树如下图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 l，若某结点的下标为 i，则其左孩子位于下标 2i 处、右孩子位于下标2i＋1 处），则该数组的大
小
至少为 （ ） A．6 B．10 C．12 D．15
27、为了提高测试的效率，应该( )
A)随机选取测试数据
B)取一切可能的输入数据作为测试数据
C)在完成编码以后制定软件的测试计划
D)集中对付那些错误群集的程序
28、算法的时间复杂度是指( )
A)执行算法程序所需要的时间 B)算法程序的长度
C)算法执行过程中所需要的基本运算次数 D)算法程序中的指令条数
29、树是节点的集合，它的根节点数目是( )
A)有且只有1 B)1或多于1
C)0或1 D)至少2
30、在编程时（使用任一种高级语言，不一定是 C++或者是PASCAL），如果需要从磁盘文件中输入一个很大的二维数组（例如 1000*1000 的 double 型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（ ）。
A)没有区别 B) 按行读的方式要高一些
C) 按列读的方式要高一些 D) 取决于数组的存储方式。
31、下列排序算法中，( )每一趟都能选出一个元素放在其最终位置上，并且是不稳定的。
A)冒泡排序 B)希尔排序
C)直接选择排序 D)直接插入排序
32、64KB的存储器用十六进制表示，它的最大的地址码是( ) A)10000 B)FFFF C)1FFFF D)EFFFF
33、PC机中CPU进行算术和逻辑运算时，可处理的信息的长度为：( )
位 B) 16位 C) 8位 D) 都可以
34、一棵完全二叉树,如果其上有一个结点的编号为11,则其父结点的编号为(▲ ).
A)22 B)12 C)10 D)5
35、下面关于主存储器（也称为内存)的叙述中，不正确的是：
当前正在执行的指令与数据都必须存放在主存储器内，否则处理器不能进行处理
存储器的读、写操作一次读出或写入一个字节
字节是主存储器中信息的基本编址单位
从程序设计的角度来看，cache（高速缓存）也是主存储器
36、计算机的主存储器容量达到1GB时，其地址的表示至少需要使用多少个2进位？
位 B) 20位 C) 30位 D) 40位
37、MIPS是衡量CPU处理速度的一种常用指标，它的含义是：
每秒钟平均可执行的单字长定点指令的数目
每秒钟平均可执行指令的数目
每秒钟平均可执行的浮点指令的数目
每秒钟平均可执行的算术运算指令的数目
38、一幅1024×768的彩色图像，其数据量达2.25MB左右，若图像数据没有经过压缩处理，则该图像中的每一个像素是使用多少个二进位表示的？
位B) 16位C) 24位D) 32位
39、互联网络上的服务都是基于一种协议，WWW服务基于______协议。
A）SMIP B）HTTP C）SNMP D）TELNET
40、无向图G=(V，E)，其中V={a,b,c,d,e,f} E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}对该图进行深度优先遍历,得到的顶点序列正确的是( )
(A)a,b,e,c,d,f (B)a,c,f,e,b,d (C)a,e,b,c,f,d (D)a,b,e,d,f,c
第二部分 问题求解
排列与组合（详见高级本） 数据结构 奥数 递推等
[重要作业]
1、平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？
2、（子集划分）将n个数（1，2，„，n）划分成r个子集。每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为S(n,r)。例如，S(4,2)=7，这7种不同的划分方法依次为{(1),(234)}，{(2),(134)}，{(3),(124)}，{(4),(123)}，{(12),(34)}，{(13),(24)}，{(14),(23)}。当n=6，r=3时，S(6,3)=_________。
（提示：先固定一个数，对于其余的5个数考虑S(5,3)与S(5,2)，再分这两种情况对原固定的数进行分析。）
提示：S(6,3)=S(5,2)+3*S(5,3)
S(m,n)=s(m-1,n-1)+n*S(m-1,n)
3、某商店有m种不同颜色的小球且每种小球的数量都足够多。要在这m种不同颜色的小球里挑选出n个小球，设共有s种不同的选法。例如当m=2，n=3时，s等于4，也就是说，共有4种不同的选法。（分别为：【0，3】，【1，2】，【2，1】，【3，0】）。现在，令m=6，n=5，试求出选法数s=_______。
4、给出一组顶点（顶点值用A，B，C，D，E，F表示），其对应权值分别为2，3，1，7，8，4。请以A，B，C，D，E，F为叶子顶点构造一棵哈夫曼树，并求出它的最小带权路径长度WPL的值。
5、今天是放寒假的最后一天，马上迎来2011年春节，住在同一个宿舍的四名同学为了相互祝愿，每人各设计了一张贺年卡送给别人，为了避免矛盾，他们将贺年卡先集中起来，然后让每人从中拿一张别人送的贺年卡，问四张不同的贺年卡有多少种不同的取法。
错排问题
8、金中机器人小P由P1，P2，P3，P4，P5，P6六个子部件组成，这些子部件之间有下列关系：P1>P2, P1>P3, P1>P4, P2>P3, P2>P5, P3>P5,P3>P6, P4>P3,P4>P6, P5>P6
(‘>’表示先于关系，如P1>P2表示P1子部件完成安装后才能进行子部件P2的安装工作)，请搞信息学竞赛的你告诉金中机器人兴趣小组的同学该如何安装小P。(注意：一个时间段只能安装一个子部件，如果有多种安装方法，只需给出其中一种安装秩序)
9、设计法码称重。要求：
(1)不同重量的法码最多设计一个，
(2)必须能称出规定重量以内所有物品的重量
(3)设计最少的法码；
如要称4克以内的重量，可设计2种不同重量的法码(1克和3克，可称1克到4克重量) 若称1000克以内重量的物品，需要设计的最少法码个数。
10、 有14个人排队买票，每人要买一张票，票价每张50元，恰有7个人只有50元钞票，7个人只有100元钞票，已知开始售票之前售票员无零钱，问有多少种排法使得售票员不至于找不开钱（拿着同样面值钞票的人视为等价）。
11、一位大城市的律师在他住所以北n个街区和以东n个街区处工作。每天他走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
12、 设有一棵k叉树，其中只有度为0和k两种结点，设n 0 ，n k ，分别表示度为0和度为k的结点个数，试求出n 0 和n k之间的关系。
度之和=nk*k 结点数=
13、一棵二叉树的先序、中序、后序遍历序列分别如下，其中有一部分未显示出来，请补全各序列。 先序 ABDFKICEHJG
中序 DBKFIAHEJCG
后序 DKIFBHJEGCA
14、假定一个AOV网的顶点集和边集为：
V={0,1,2,3,4,5,6,7,8,9}
E={,,,,,,,,,,,,,,};若在他的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则写出唯一一种拓朴序列。
15
、如图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，
如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。
16、对于下面这棵树，写出它的先根遍历结果（2
分），然后将该树转换成二叉树。
17、对下图所示的带权无向图，写出深度优先搜索
序列（从1出发）（3分），并按克鲁斯卡算法求其最小生成树。
18、对于下面的有向图，有多少种不同的拓朴序列。
第三部分 写程序运行结果
一、模拟法----“死算”
1、var a,work:array[1..100] of integer;
i,j,x,d,max:integer;
begin
read(max);
for i:=1 to max do begin read(a[i]); work[i]:=a[i]; end;
d:=max div 2;
while d>=1 do
begin
for i:=d+1 to max do
begin
x:=work[i];
j:=i-d;
while (j>0) and (x
begin
work[j+d]:=work[j];
dec(j,d);
end;
work[j+d]:=x;
end;
d:=d div 2;
end;
for i:= max downto 1 do
begin
if a[i]=work[i] then write('1')
else write('0');
end;
end.
输入：10 71 149 32 11 90 119 9 130 95 144
2、const maxn=100；
type arr=array[0.. maxn] of integer ;
var ans：array[1..maxn] of arr；
n：integer；i，J：integer；
procedure main；
begin
fillchar(ans,sizeof(ans)，0)；
for i：=1 to n do ans[1，i]：=1；
for i:=2 to n do
begin
for J：=1 to i-1 do
ans[i,j]：=ans[i-j, j]+ ans[i, j-1];
for J：=i to n do ans[i，J]：=ans[i, i-l ]+1；
end：
end;
begin
readln(n);
main;
write(ans[n,n])；
end. 输入n=7时，其运行结果是
3、var i,zimu,j,k:char;
begin
repeat
readln(zimu);
zimu:=upcase(zimu); {upcase 是小写转大写} until (zimu>='A') and (zimu
for i:='A' to zimu do begin
write(' ':(ord(zimu)-ord(i))+1);
for j:='A' to i do write(j); for j:=pred(i) downto 'A' do write(j); if (ord(i)-64) mod 25=0 then readln else writeln;
end;
end.
输入 E 输出：
4、Var I,j:integer;
A:array[1..3,1..3] of integer;
Begin
For i:=1 to 3 do
Begin
For j:= 1 to 3 do
Begin
If i=3 then
a[I,j]:=a[i-1,a[i-1,j]]+1
else
a[I,j]:=j;
write(a[I,j]);
end;
writeln;
end;
end.
5、var i,j,l,n,k,s,t: integer;
b: array[1..10] of 0..9;
begin
readln(l,n);s:=l; k:=1; t:=l;
while s
begin
k:=k+1;t:=t*l; s:=s+t;
end;
s:=s-t; n:=n-s-1;
for i:=1 to 10 do b[i]:=0;
j:=11;
while n>0 do
begin
j:=j-1;b[j]:=n mod l; n:=n div l;
end;
for i:=10-k+1 to 10 do write(chr(ord('A')+b[i]));
END.
输入：5 257
二、分析公式、规律
1、Var g:integer; k,t:real; m:integer; Begin
K:=0;g:=0;
For m:=1 to 49 do
Begin
g:=g+1;
k:=k+1/(g*(g+1));
end;
writeln(k:10:2);
End.
2、var n,i:integer;
total:longint;
function work(a,b:integer) : longint;
var c,d,e:longint;
i:integer;
begin
c:=1;
for i:= 2 to a do c:= c*i;
d:=1;
for i:= 2 to b do d:= d*i;
e:=1;
for i:= 2 to a-b do e:= e*i;
exit(c div d div e);
end;
begin
read(n);
total:=0;
for i:= 1 to n do total:=total + work(n,i); write(total);
end.
输入：12
3、var a,b,c:integer;
function D(b:integer):integer;
var t:integer;
begin if b=0 then D:=1
else begin t:=D(b div 2);
t:=t*t mod c;
if odd(b) then D:=t*a mod c else D:=t
end;
end;
begin readln(a,b,c); writeln(D(b)); end. 输入： 993 294 10 输出：
4、Var M,n,I,p,k:integer;
r:array[1...200] of integer;
b:Boolean;
begin
m:=6;n:=2;
for i:=1 to m-1 do r[i]:=i+1;
r[m]:=1;i:=0;p:=1;b:=true;
while b do
begin
i:=i+1;k:=p;P:=r[p];
if k=p then
begin writeln(p);b:=false; end; else if i=n+1 then
begin
write(p,’ ’);i:=0;p:=r[p];r[k]:=p; end;
end;
end.
5、var a:array[1..10] of integer;
s,n,m:longint;
flag:set of byte;
procedure try(dep:integer);
var i:integer;
begin
for i:=1 to n do
if not(i in flag) then
begin
flag:=flag+[i];
a[dep]:=i;
if dep=m then inc(s) else try(dep+1); flag:=flag-[i];
end;
end;
begin
readln(m,n);
flag:=[];s:=0;
try(1);
writeln(s);
end;
输入：4 5
三、字符串处理
1、Var N,I,tem,t:longint;
S:string;
Begin
readln(n);
S:=’1’;
Repeat
I:=length(s);
While s[i]=’1’ do
Begin
S[i]:=’0’;dec(i);
End;
If i>0 then s[i]:=’1’ else s:=’1’+s; Val(s,t,tem);
Until t mod n =0;
Writeln(n,’*’,t div n,’=’,s);
End.
输入：6
2、var s:string; n,p,q,i:integer;
a:array[1..10]of char; c:char;
begin
readln(n);
s:='OIFans.cn-Fly with the same dream'; p:=pos('s',s);
s:=copy(s,p+19,255);
s:=copy(s,n,255);
c:='a'; q:=1;
for i:=1 to length(s) do
if s[i]>c then
begin
a[q]:=s[i]; c:=a[q]; inc(q);
end;
dec(q);
for i:=1 to q do write(a[i]);
end.
输入：2
3、var len,n:word;
string0:string;
function l(st:string;i:integer):string;
begin
len:=length(st);
if (len=0) or (len
function r(st:string;n:integer):string;
begin
len:=length(st);
if (len=0) or (len
begin
readln(string0);
readln(n);
writeln(l(string0,n));
writeln(r(string0,n));
end.
输入：aabbccwwabcabc
6
四、函数与过程
[要点]参数，前面加VAR的参数，在函数与过程中变量的结果会向主程序中传递。
1、Var a,b:integer;
Procedure p1(x:integer;var y:integer);
Begin
x:=x+y; y:=x+y;
End;
begin
a:=5;b:=8;
p1(a,b);writeln(a:3;b:3);
p1(b-a,b);writeln(a:3;b:3);
end.
2、var x，s:Integer；
function ms(a，b:Integer；VAR x : Integer) : Integer；
begin
x:=3*a-4*b+x；
ms:=x MOD 10
end；
begin
x:=3；
s:=ms(ms(1，2，x)，2*ms(1，2，x)，x)；
writeln (‘x=’，x) ;
end.
3、var n,i,min,k,buf:word;
b:array[0..3000] of byte;
function max(a,b:byte):byte;
begin
if a>b then max:=a else max:=b;
end;
begin
b[0]:=0;b[1]:=0;b[2]:=1 write(‘n=’);readln(n);
for i:=3 to n do
begin
min:=999;
for k:=1 to i div 2 do
begin
buf:=max(b [i-2*k],b[k]);
if min>buf then min:=buf;
end;
b[i]:=1+min;
end;
writeln(b[n]);
end.
输入：n=32
4、var x,y,z:integer;
proedure silly(x:integer;var y:integer);
begin
x:=5;y:=6;z:=3;
writeln(x:2,y:2,z:2);
end;
begin
x:=1;y:=2;z:=3;
silly(x,y);
writeln(x:2,y:2,z:2);
end.
五、递归
1、 Function f(var x:integer; y, z:integer):integer;
Begin
X:=x+y+z;
F:=x
End;
Begin
x:=1; y:=2; z:=3;
y:=f(x,f(x,y+z,z+x),y);
Writeln(x:4,y:4,z:4)
End.
2、Const n=10;
Function fn(n:integer):integer;
Begin
If n
Else if n=1 then
Fn:=1
Else
Fn:=fn(n-1)+n;
End;
Begin
Writeln(fn(n));
Readln;
End.
3、function fac(n:integer):integer;
var t:integer;
begin if (n=1) or (n=2) then fac:=n
else fac:=fac(n-1)+fac(n-2);
end;
begin write(fac(6));
end.
4、var n:integer;
function count(n:integer):integer;
begin
if n=1 then count:=0
else if n mod 2=0 then count:=count(n div 2)+1
else count:=count(n*3+1)+1;
end;
begin
readln(n);
writeln(count(n));
end.
输入：77
5、Function Fun(X:Integer):Integer;
Begin
If (X=0) Or (X=1) Then Fun:=3
Else Fun:=X-Fun(X-2);
End;
Begin
WriteLn(Fun(9));
End.
6、Var k,j:Integer; A:Array[1..10] Of Integer;
Procedure Try(i:Integer);
Begin
For j:=1 To 3 Do
Begin
A[i]:=j;
If i=2 Then Begin
For k:=1 To 2 Do
Write(A[k]);
Writeln;
End
Else Try(i+1);
End;
End;
Begin
Try(1);
End.
7、var i,j:integer;
function p(n,x:integer):integer;
begin
if n=0 then p:=1 else if n=1 then p:=x
else P := trunc(((2*n)*p(n-1,x)-(n-1)*p(n-2,x))/n);
end;
begin
readln(i,j);
writeln(p(i,j));
end.
输入：3 5
8、var a,b:integer;
function fun(a,b:integer):integer;
var k:integer;
begin
if a
else
if b=0 then fun:=a
else if not odd(a) then
if not odd(b) then fun:=fun(a div 2,b div 2)*2
else fun:=fun(a div 2,b)
else
if not odd(b) then fun:=fun(a,b div 2)
else fun:=fun(b,a-b)
end;
begin
a:=234; b:=432;
writeln(fun(a,b));
end.
输出的结果是：
9. var a : array [1..50] of integer;
n, i, sum : integer;
procedure work(p, r: integer);
var i, j, temp : integer;
begin
if p
i := p - 1;
for j := p to r - 1 do
if a[j] >= a[r] then begin
inc(i);
temp := a[i]; a[i] := a[j]; a[j] := temp;
end;
temp := a[i + 1]; a[i + 1] := a[r]; a[r] := temp;
work(p, i);
work(i + 2, r);
end;
end;
begin
read(n);
for i := 1 to n do read(a[i]);
work(1, n);
for i := 1 to n - 1 do sum := sum + abs(a[i + 1] - a[i]);
writeln(sum);
end.
输入：8 16 34 12 25 78 43 6 9
输出的结果是：
第四部分 完善程序
1、输入一个正整数，然后与它倒过来的数相加。先将读入的正整数进行数字分离，分离出的个位、十位、百位„„数字，依次存放到a[10]、a[9]、a[8]、„„各下标变量中，然后再将它们合并成一个倒过来的数y，再与原数相加。
var a : array[1..10] : integer ;
i , j , x , x1 , y : integer;
begin
readln(x);
x1 := x ;
j := ① ;
while ② do
begin
j := j – 1 ;
a[j] := x mod 10 ;
x := ③ ;
end;
y := 0;
for i := ④ do
y := y * 10 + a[i] ;
x := ⑤ ;
writeln(x)
end.
2． 读入N个不相同且不为0的数（1≤N≤100），求出其中第R个大的数（1≤R≤N）。 例如：输入3，14，22，15，17，6，其中第3个大的数为15。
以数组A[100]记录读入的N个数，并以0为结束（0本身不是N个数中的），然后从第一个数开始，将它与其余的数进行比较，并记录出比它大的数的个数（存于变量y中），若y=R-1时，得到所求结果，否则对下一个数进行同样的处理。
var a : array[1..100] : integer ;
i , j , k , x , y : integer;
begin
read( R );
j := 0 ;
read(x);
while ① do
begin
j := ② ;
a[j] := x ;
read(x)
end;
i := 0;
repeat
i := i+1;
x := a[i] ;
y := 0 ;
for k :=1 to ③ do
if x
until ⑤ ;
write(a[i]);
end.
3、从三个元素（例如1，2，3）的字符表中选取字符，生成一个有n个符号的序列，使得其中没有2个相邻的子序列相等。如长度n=5的序列“12321”是合格的，而“12323”和“12123”都是不合格的。
Const n=5;
Var a:array [1..n] of integer;
K,h:integer;
Procedure recn(I:integer);
Var j,k:integer;
S:set of 1..3;
Begin
S:=[1..3];
For j:=1 to I-1 do
If a[I]=a[j] then s:=s-[ ];
If s then
For k:=1 to do
If k in s then
Begin
A[I+1]:= ;
If I+1=n then
Begin
For j:=1 to n do
Write(a[j]:3);
H:=h+1;
If h mod 6=0 then writeln
End
Else recn( )
End;
End;
Begin
(6) ;
For k:=1 to 3 do
Begin
(7)
Recn(1);
End;
Writeln(‘h=’,h);
End.
4、以下程序是将一组整数按从小到大的顺序排列。排序的方法是将长度为n的数a分为两个长度为(n div 2)与（n-n div 2）的子数组，a1,a2，然后递归调用排序过程，将a1,a2分别排序，最后将a1,a2归并成数组a。例如a=(3,1,2,4)，那么a1=(3,1),a2=(2,4)。调用排序过程将a1,a2排序，得到a1=(1,3),a2=(2,4),然后进行合并排序。从键盘输入数的n以及n个整数，存在数组a中，调用子过程sort进行排序，最后输出排序结果。
const maxn =100;
type arr=array[1..maxn] of integer;
var a:arr;
n,i:integer;
procedure sort(n:integer; var a:arr);
var
i,p1,p2,n1,n2:integer; a1,a2:arr;
begin
if n=1 then exit;
fillchar(a1,Sizeof(a1),0);
fillchar(a2,sizeof(a2),0);
n1:=0; n2:=0;
n1:=n div 2; n2:= ⑴ ;
for i:=1 to n1 do a1[i]:=a[i];
for i:=1 to n2 do a2[i]:= ⑵ ;
⑶ ;
sort(n2,a2);
p1:=1; p2:=1;
n:=0;
while(p1
begin
n:=n+1;
if ⑸ then begin a[n]:=a1[p1];inc(p1);end
else begin ⑹ ;inc(p2);end;
end;
if p1
else for i:=p2 to ⑺ do begin n:=n+1; a[n]:=a2[i]; end;
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
sort(n,a);
for i:=1 to n do write(a[i],' ');
end.
5、求N个数中的第K小的数。程序利用快排（递归、分治算法），当找到第N个小的数时候就停止。
样例：输入：5 {N}
5 6 4 1 8 {N个数}
2 {第2小的数}
输出：4 {第2小的数是4}
var i,j,k,n:integer;
a:array[1..100] of integer;
procedure search(b,e:integer);
var i,m,t:integer;
begin
if b=e then ___;
i:=b; j:=e; m:=a[k];
repeat
while t:=a[i];a[i]:=a[j];a[j]:=t end;
until i>=j;
if i=k then exit;
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
readln(k);
search(1,n);
writeln(a[k]);
end.
6、根据二叉树的前序遍历和中序遍历，求出树的后序遍历。
样例输入：abdec （前序） 输出：debca（后序）
dbeac （中序）
var s1, s2 : string;
procedure try(L1, r1, L2, r2 : integer);
var m : integer;
begin
m := pos(s1[L1], s2);
if m >L2 then try( );
if m
write(s1[L1])
end;
begin
readln(s1); readln(s2);
try(1, length(s1), 1, length(s2));
end.
7、一个整数的整数子串是由该整数的连续数位的数字构成。
例如： 6518的子串包括6，5，1，8，65，51，18，651，518，6518
任务：找出最大的质数子串
输入：整数N（0
输出：N的最大质数子串，若所有的子串都是非质数，则输出“No primes”
样例：输入：2319 输出：31
var maxp,max,k:longint;
n,s:string; len,I,j:integer; code,bj:word;
begin
___ ___①_____; _____②_____;
for I:=1 to len do
for j:=1 to len-I+1 do
begin
s:=copy(n,j,I);
val(s,maxp,code);
bj:=0;
for k:=2 to trunc(sqrt(maxp)) do
if maxp mod k=0 then
begin
____③_ __;
k:=trunc(sqrt(maxp));
end;
if maxp=1 then __④____;
if ___⑤____ then max:=maxp;
end;
if max=0 then writeln('no primes') else writeln(max);
end.
8、字符串变换。设有2个字符串A$,B$, B$经过一系列的变换变成A$, 变换的规则为：可以在任意位置加入、删除、变换字符。例如：A$=’abcde’, B$=’bcwye’,此时B$可在b前面加入一个a成为’abcwye’,再将w变为d,成为’abcdye’,最后删除y,成为’abcde’,即B$经过3次变换,成为A$, 本程序就是要求最少变换次数。
程序说明：A$、B$分别用字符串数组a、b存放，采用动态规划求解，g[m,n]表示B数组的前m个字符要变成A数组的前n个字符所需要的最少次数。
Var a,b:string; g:array[0..100,0.100] of integer;
I,j,k,lg1,lg2,min:integer;
Begin readln(a);readln(b);
Lg1:=length(a); ___ _______________________;
For i:=0 to lg1 do g[0,i]:=I;
For i:=1 to lg2 do
Begin ____ ____________;
For j:=1 to lg1 do
If (a[j]=b[i]) then g[I,j]:=__ ___
Else begin min:=__ __;
If (min>g[i-1,j]) then min:=g[i-1,j];
If (min>g[I,j-1]) then min:=g[I,j-1];
G[I,j]:=min+1;
End;
End;
Writeln(____);
End.
9、挖宝藏。现有n个藏宝室，每个室中有一定数量的的宝藏，同时给出从一个室到另一个室的通行时间，约定从1室开始挖，挖宝藏的时间可以忽略，每个室只能经过一次，任意两个室都相通，当然所用的时间不相同，给定一个时间tk,求在这个时间内最多能挖到多少宝藏。{回溯算法} 输入： n tk {第一行两个数，分别为宝藏室个数和给定时间}
d1,d2,d3,„„，dn {第二行为每个室中宝藏数}
g11,g12,g13,„„g1n {以下数据用g数组存放，g[I,j]表示从i室到j室所 g21,g22,g23,„„g2n 需的时间}
„„
gn1,gn2,gn3,„„gnn
样例：输入：4 10 输出：11
3 2 1 5 {走的路线是：1-2-4-3}
0 3 2 6
1 0 2 4
1 4 0 8
1 3 3 0
var I,j,k,n,s0,tk,t,cmax,top:integer;
stack,d,flag:array[1..30] of integer; g:array[1..30,1..30]of integer;
begin readln(n,tk); for i:=1 to n do read(d[i]);
for i:=1 to n do
for j:=1 to n do read(g[I,j]);
for i:=1 to n do flag[i]:=0; k:=0; t:=tk; cmax:=d[1]; s0:=d[1]; top:=1;
_________; flag[1]:=1;
While (top>=0) do
Begin k:=k+1; if (k>n) then begin k:=stack[top];top:=top-1;
t:=t+g[stack[top],k]; flag[k]:=0;
s0:=___ ______
end
else if ((flag[k]=0) and ( ________)) then
begin s0:=s0+d[k]; _ ______________;
if (s0>cmax) then cmax:=s0;
t:=t-g[stack[top],k];
top:=top+1; stack[top]:=k;__ _______________;
End;
End; writeln(cmax);
End.
10、求元素之和最大的子方阵：在m×n（m，n≤20）的正整数数字方阵中，找出一个p×q的子阵（1≤p≤m，1≤q≤n）使其元素之和最大。例如，下面5×4的数字阵中，元素之和最大的一个2×3子阵。
5×4数字阵元素之和最大的2×3子阵为
VAR A:ARRAY[1..20,1..20] OF INTEGER;
M,N,P,Q,I,J,MAX,PL,QL,S,IL,JL:INTEGER;
BEGIN
FOR I:=1 TO 20 DO FOR J:=1 TO 20 DO A[I,J]:=0; READLN(M,N); FOR I:=1 TO M DO BEGIN FOR J:=1 TO N DO READ(A[I,J]); READLN; 第
END; READLN(P,Q);
MAX:=O
信息学奥赛初赛复习
前车小学信息组
第一部分：选择题
一、、计算机发展历程
（NOI2007笔试复习题，部分）
1、NOI机试使用的操作系统是：
A. Windows B. Linux C. MacOS D. Vxworks
2、Linux中为文件改名使用的命令是：
A. mv B. ren C. chroot D. su
3、在Linux中返回上一级目录使用的命令是：
A. cd B. cd . C. cd .. D. cd ./
4、使用高级语言编写的程序称之为：
A. 源程序 B. 编辑程序 C. 编译程序 D. 链接程序
5、 属于面向对象程序设计语言的是：
A. C B. C++ C. Pascal D. Basic
6、在Linux系统中，下面的说法中正确的是：
A. 文件夹中的文件可以与该文件夹同名 B. 文件夹中的文件不能与该文件夹同名
C. 在不同文件夹中的两个文件不可以使用相同的文件名 D. 以上说法都不对
7、 一个完整的计算机系统应包括_______。
A.系统硬件和系统软件 B.硬件系统和软件系统
C.主机和外部设备 D.主机、键盘、显示器和辅助存储器
8、目前微型计算机中采用的逻辑组件是_______。
A.小规模集成电路 B.中规模集成电路 C.大规模和超大规模集成电路 D.独立组件
9、 软件与程序的区别是_______。
A.程序价格便宜、软件价格昂贵 B.程序是用户自己编写的，而软件是由厂家提供的
C.程序是用高级语言编写的，而软件是由机器语言编写的
D.软件是程序以及开发、使用和维护所需要的所有文档的总称,而程序是软件的一部分
10、IT表示_______。
A. 通信技术 B. 信息技术 C. 网络技术 D. 信息学
11、计算机中央处理器简称为_______
A. IBM B.UBS C.CPU D.Computer
11、计算机内存储器的作用是_______
A.用来存放暂时不用的程序和数据 B.用来存放当前CPU正在使用的程序和数据
C.用来存放要删除的信息 D.仅用来存储选手的数据和程序
12、用来全面管理计算机硬件和软件资源的软件叫_______
A．操作系统 B．应用软件 C．管理软件 D. 系统平台
13、 LAN是指_______
A．互联网 B．局域网 C．广域网 D. 城域网
14、在微机中，bit 的中文含义是_____。
A. 二进制位 B. 字 C. 字节 D. 双字
15、为了避免混淆，十六进制数在书写时常在后面加字母_____。
A. H B. O C. D D. B
16、.计算机所能辨认的最小信息单位是_______。
A. 位 B. 字节 C. 字 D. 字符串"
17、ASCII的含义是________。
A.条件码 B.二－十进制编码 C.二进制码 D.美国信息交换标准代码
18、在计算机术语中经常用RAM表示________。
A、只读存储器 B、可编程只读存储器 C、动态随机存储器 D、随机存取存储器 19、RAM存储器在断电后，其中的数据会_______。
A.丢失 B.自动保存 C.不变化 D.需人工保存
20、ROM存储器在断电后，其中的数据会_______。
A.丢失 B.自动保存 C.不变化 D.需人工保存
21、现代计算机所应用的存储程序原理是_________提出的。
A.图灵 B.布尔 C.冯·诺依曼 D.爱因斯坦
22、计算机内所有的信息都是以_______数码形式表示的。
A.八进制 B.十进制 C.二进制 D.十六进制
23、计算机能直接识别和执行的语言是________。
A. 机器语言 B. 汇编语言 C. C语言 D. Pascal语言
24、Linux是一个_______操作系统，意思是源码可以免费获得。
A. 开源的 B. 有使用许可的 C. 不开放源代码的
25、NOI的中文意思是：
A. 中国信息学奥赛 B. 中国国家奥委会 C. 国际信息学奥赛D. 中国信息学联赛
[重要作业]
1、微机内的存储器的地址是以（ ）编址的。
A．二进制位 B．字长 C．字节 D．微处理器的型号
2、在24*24 点阵的字库中，汉字“一 ”与“编”的字模占用字节数分别是（ ）。
A．32、32 B．32、72 C．72、72 D．72、32
3、不同的计算机，其指令系统也不相同，这主要取决于 （ ）。
A．所用的操作系统 B．系统的总体结构
C．所用的 CPU D．所用的程序设计语言
4、2KB的内存能存储( )个汉字的机内码
A)1024 B)516 C)2048 D)218
5、下列哪个（些）软件不是操作系统软件的名字（ ）。
A）WindowsXP B) DOS C) Linux D) OS/2 E) ARCH/INFO
6、美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献是（ ）。
A. 提出理想计算机的数学模型，成为计算机科学的理论基础。
B. 是世界上第一个编写计算机程序的人。
C. 提出存储程序工作原理，并设计出第一台具有存储程序功能的计算机EDVAC。
D. 采用集成电路作为计算机的主要功能部件。
E、指出计算机性能将以每两年翻一番的速度向前发展。
7、下列哪个不是CPU（中央处理单元）（ ）。
A. Intel Itanium B. DDR SDRAM C. AMD Athlon64
D. AMD Opteron E. IBM Power 5
8、下面哪个部件对于个人桌面电脑的正常运行不是必需的（ ）。
A. CPU B. 图形卡（显卡） C. 光驱 D. 主板 E. 内存
9、下列哪个软件属于操作系统软件（ ）。
A. Microsoft Word B. 金山词霸 C. Foxmail D. WinRAR E. RED HAT LINUX
10、下列哪个不是计算机的存储设备（ ）。
A. 文件管理器 B. 内存 C. 高速缓存 D. 硬盘 E. U盘
11、下列哪个程序设计语言不支持面向对象程序设计方法（ ）。
A. C++ B. Object Pascal C. TURBO PASCAl D. Smalltalk E. Java
12、设有一个十阶的对称矩阵A．采用压缩存储方式，以行序为主存储，a11为第一个元素。其存储地址为1，每个元素占1个地址空间，则a85的地址为( )。
A) 13 B) 33 C) 18 D) 50
13、奔腾的地址线是32根，最大存储量为 （ ）
A．4GB B．4MB C．32MB
14、JPEG是一种（ ）的图象压缩方式 （ ）
A．有损压缩 B．无损压缩 C．不可压缩 D．以上都正确
15、一台计算机的字长是8字节，表示是 （ ）
A．能处理的数字最大是8个十进制数99999999
B．能处理的字符串最多由8个英文字母组成
C．在CPU中作为一个整体加以传送处理二进制代码为64位
D．CPU的运行的最大结果为2的64次方
16、微型计算机内存储器是按 （ ）
A．二进制位编码 B．字节编码
C．字长编码 D．CPU的型号不同而编址不同
17、下列叙述中正确的是 （ ）
A．汉字的计算机内存是国际码
B．存储器具有记忆能力，其中的信息任何时候都不会消失
C．所有十进制数都能准确的转换为二进制数
D．正数的二进制原码的补码是原码本身
18、PASCAL编译程序的功能是 （ ）
A．把PASCAL源程序转换成可运行的EXE文件
B．生成和修改一个PASCAL源程序
C．实现PASCAL的源程序到等价的目标程序的转换
D．实现PASCAL的源程序到等价的目标码程序的转换
19、操作系统是对什么进行管理的系统软件 （ ）
A．软件 B．硬件 C．计算机资源 D．应用程序
20、计算机处理信息的精度决定于 （ ）
A、CPU主频 B、硬盘的容量 C、系统总线的传输频率 D、CPU字长
21、计算机的基本硬件结构一直沿袭（ ）设计的框架。
A、比尔.盖茨 B、冯.诺依曼 C、布尔 D、图灵
22、在流程图的符号中，菱形框一般作为（ ）
A、起止框 B、输入输出框 C、判断框 D、处理工作框
23、算法的3种结构是（ ）
A、顺序、分支、循环 B、顺序、重复、循环
C、顺序、分支、判断 D、顺序、流程、循环
24、用于管理计算机资源，方便用户使用计算机的是（ ）
A、数据库 B、应用软件 C、操作系统 D、计算机语言
25、分辨率为1280*1024真彩色（16位）的17英寸显示器的显存容量应为（ ）MB。
A、1 B、2.5 C、4 D、8
26、计算机的主存储器容量达到1GB时，其地址的表示至少需要使用（ ）个2进制位。
A、10位 B、20位 C、30位 D、40位
27、PASCAL程序运行时，是在哪种存储器中进行。（ ）
A、硬盘 B、RAM C、ROM D、CACHE
三、计算机中数的表示
1、十进制算术表达式 ：3*512 + 7*64 + 4*8 + 5的运算结果，用二进制表示为（ ）。
A．[1**********] B．[1**********] C．[1**********] D．[1**********]
2、计算机中的数有浮点与定点数两种，其中用浮点数表示的数，通常由（ ）这两部分组成。
A．指数与基数 B．尾数与小数 C．阶码与尾数 D．整数与小数
3、[x]补码=10011000，其原码为( )
A)011001111 B)11101000 C)11100110 D)01100101
4、表达式(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-*/
5、8位无符号二进制数能够表示的最大十进制数是（ ）。
A） 255 B） 256 C） 64 D） 63
6、已知A=(72E)H，B=(1315)D，则A-B的结果是 ( )。
A） (674)O B） (1AD)H C） (523)D D）(101101011)B
7、产生100至300之间的随机整数(Random)，且包含100，300两个整数的表达式（ ）
A．Random(100)+200 B．Random(200)+100
C．RANDOM(201)+100 D．Random(300)
8、在微型计算机中，常用（ ）码实现十进制数与二进制数之间的自动转换 （ ）
A．BCD码 B．ASCII码 C．海明码 D．机内码
9、设有一个十阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为 （ ）
A．13 B．33 C．18 D．50
10、ASCII码的主要作用是 （ ）
A．便与信息交换 B．便于信息存储 C．便于管理 D．便于输出
11、二进制数-0.1101010的补码是（ ）
A、0010101 B、10010110 C、10010101 D、01101010
12、国际信息交换码ASCII码的长度为1个字节，其中的最高位为0，因此ASCII码表中的符号有（ ）个。
A、127 B、128 C、255 D、256
13、十进制数100的反码和补码表示分别是（ ）
A、9BH和64H B、64H和9BH C、64H和64H D、9BH和9BH
14、关于“零”的原码、反码、补码，下列说法正确的是（ ）
A、零的原码表示只有一种 B、零的反码表示只有一种
C、零的补码表示只有一种 D、零的原码、反码、补码表示都有两种
四、网络知识
1、调制解调器又称为Modem，可用于连结计算机与电话线拨号上网。调制是指 （ ）
A．把电信号转换成光信号 B．把光信号转换成电信号
C．把模拟信号转换成数字信号 D．把数字信号转换成模拟信号
2、OSI的7层协议中，最底层是 （ ）
A．会话层 B．数据链接层 C．物理层 D．网络层
3、“网络通信协议”，如：Internet采用的TCP/IP协议是一组 （ ）
A．软件 B．存储器 C．外部设备 D．约定的规则
4、国际互联网的目的在于使不同网络上的用户相互通信，交换信息，那么用于网络之间互连的中继设备称 （ ）
A．放大器 B．网桥 C．网关 D．网间连接器
5、在TCP/IP协议中，TCP和IP分别提供什么服务 （ ）
A．传输层、网络层 B．链路层、网络层
C．传输层、会话层 D．物理层、链路层
6、TCP/IP协议是指 （ ）
A．文件传输协议/远程登陆协议 B．邮件传输协议/远程登陆协议
C．传输控制协议/因特网互联协议 D．文件传输协议/邮件传输协议
7、Intel 给我们提供了资源共享、浏览、检索信息和远程登录等多种服务，下面几个选项中用于远程登录的是（ ）
A、Telnet B、E-Mail C、TCP/IP D、WWW
8、IE是目前流行的浏览器软件，它的工作基础是解释执行用（ ）语言书写的文件。
A、VC B、C++ C、HTML D、HTTP
9、计算机网络最大的优点是（ ） 。
A、精度高 B、资源共享 C、运行速度快 D、存储容量大 E、逻辑判断能力强
10、TCP/IP协议共有( )层协议
A)3 B)4 C)5 D)6
11、IP v4地址是由( ) 位二进制数码表示的。
A) 16 B) 32 c) 24 D) 8
五、二进制的逻辑运算
1、已知 A=11001010B B=00001111B C=01011100B, A∨B∧C=( )B.
A、11001110 B、01110110 C、11101110 D、01001100
2、已知A = 35H，A /\ 05H \/ A /\ 30H 的结果是：（ ）。提示：先化成二进制。
A）30H B）05H C）35H D）53H
3、假设A=true，B=false，C=true，D=true，逻辑运算表达式A∧B∨C∧D的值是( )。
A)true B)false C)0 D)1 E)NULL
4、逻辑代数式子f=AB+ABC+AB(C+D), 则f的简化式子为( )。
A) AB B) A+B C) ABC D) ABCD
5、两个十进制数13与14，将它们进行“与”运算，其值为（ ）
A、27 B、12 C、15 D、11
6、在Pascal程序中，表达式（200 or 10）的值是（ ）。
A．20 B．1 C．220 D．202
7、在 Pascal 语言中，表达式 (23 or 2 xor 5)的值是（ ）
A. 18 B. 1 C.23 D.32
六、集合运算
1、设全集E={1，2，3，4，5}，集合A={1，4}，B={1，2，5}，C={2，4}，则集合（A ∩B）∪～
C 为（ ）。
A） 空集 B） {1} C） {3，5} D）{1，5} E） {1，3，5}
2、设全集I = {a, b, c, d, e, f, g}，集合A = {a, b, c}，B = {b, d, e}，C = {e, f, g}，那么集合(AB)(~CB)为（ ）。
A. {a, b, c, d} B. {a, b, d, e} C. {b, d, e} D. {b, c, d, e} E. {d, f, g}
3、已知集合E={2，３，５，１，６}，请问Ｅ的所有子集个数是多少？（ ）
Ａ) 25 Ｂ) 10 Ｃ) 32 Ｄ) 64
4、设全集E={1,2,3,4,5},集合A={1,2,5},B={1,4},C={2,4}，则集合(A+B)*C-(A*B)为（ ）。
A、空集 B、{1} C、{2，4} D、{1，3，5}
七、数据结构
1、已知队列（13，2，11，34，41，77，5，7，18，26，15），第一个进入队列的元素是13，则第五个出队列的元素是（ ）。
A） 5 B） 41 C） 77 D） 13 E） 18
2、线性表若采用链表存贮结构，要求内存中可用存贮单元地址（ ）．
A．必须连续 B．部分地址必须连续
C．一定不连续 D．连续不连续均可
3、下列叙述中，正确的是（ ）．
A． 线性表的线性存贮结构优于链表存贮结构
B． 队列的操作方式是先进后出
C． 栈的操作方式是先进先出
D．二维数组是指它的每个数据元素为一个线性表的线性表
4、某数列有1000个各不相同的单元，由低至高按序排列；現要对该数列進行二分法检索（binary search），在最坏的情況下，需检视（ ）个单元。
A．1000 B．10 C．100 D．500
5、在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为( )
A)2 B)3 C)4 D)5
6、以下哪一个不是栈的基本运算( )
A)删除栈顶元素 B)删除栈底的元素
C)判断栈是否为空 D)将栈置为空栈
7、设栈S和队列Q的初始状态为空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通过栈S，一个元素
出栈后即进入队列Q，若出队的顺序为e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈S的容量至少应该为（ ）。
A）2 B）3 C）4 D）5
8、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e2,e4,e3,e6,e5,e1，则栈S的容量至少应该为（ ）
Ａ) 2 Ｂ) 3 Ｃ) 4 Ｄ) 5
9、对按关键字排序好的线性表进行二分查找，该线性表适合的存储结构为 （ ）
A．顺序结构 B．链接存储 C．索引存储 D．散列存储
10、在数据结构中，链表是（ ）
A、顺序存储的线性表结构 B、非顺序存储的线性表结构
C、非顺序存储的非线性结构 D、顺序存储的非线性表结构
11、在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主要将要输出打印的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个（ ）结构。
A．堆栈 B．数组 C．线性表 D．队列 E．链表
例1：设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一个位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有15元素。答案：50-45+10=15。
如果反过来，头10，尾45，则元素个数是45-10=35。
元素的个数是：当队尾>队头的时候，队尾减去队头。反之，容量-队头+队尾）
例2、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。
（A）1和5 （B）2和4 （C）4和2 （D）5和1
例3、设循环队列中数组的下标范围是1–n，其头尾指针分别为f和r，则其元素个数为（ ）．
A．r- f B．r- f +1
C．（r- f ） MOD n+1 D．（r- f + n） MOD n
八、树（详见高级本P108-111）
[补充作业]
1、给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA 画出此二叉树。 2、已知，按中序遍历二叉树的结果为：abc
问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。5种
3、一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有( )个结点
h A)2-1 B)2h-1 C)2h+1 D)h+1
4、按照二叉数的定义，具有3个结点的二叉树有（ ）种。
A）3 B）4 C）5 D）6
（卡特兰数，NOI专刊 第3期 25页）
5、设有一棵k叉树，其中只有度为0和k两种结点，设n 0 ，n k ，分别表示度为0和度为k的结
点个数，试求出n 0 和n k之间的关系（n 0 = 数学表达式，数学表达式仅含n k 、k和数字）。
6、一个高度为h的二叉树最小元素数目是( )。
A)2h+l B)h C)2h-1 D)2h E)2h-l
7、一棵含有101个结点的完全二叉树存储在数组A[1..101]中， 对1≤k≤101,若A[k]是叶子结点，则k的最小值是: ( )
A) 51 B) 50 C) 49 D) 48
8、如果一棵m度树中有n1个度为1的结点，n2个度为2的结点，„„.有
nm个度为m的结点,则该树中叶结点的的个数( ).
A） N1 B） M-N1-N2
C） N1+2N2+……+(M-1)NM-1+1 D） N2+2N3+……+(M-1)NM+1
9、对于一颗二叉树T，设n0、n1、n2分别是度数为0、1、2的顶点数，则下列判断中正确的是（ ）
A、n0=n2+1 B、n1=n0+1 C、n2=n0+1 D、n2=n1+1
10、一棵n个节点的完全二叉树，则该树的高度h 为（ ）
A、n/2 B、log (n) C、log(n)/2 D、[log(n)]+1
四、图（详见高级本P123-126）
运用prim算法和kruskal算法分别画出图1的最小生成
程。
2 3 4 4 5 7 12 树形成的过
九、排序算法（详见高级本）
[重要作业]
1、下列排序算法中，最坏情况下的时间复杂度最低的是（ ）
A、堆排序 B、选择排序 C、快速排序 D、插入排序
2、在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是（ ）．
A 堆排序 B 希尔排序 C 冒泡排序 D 快速排序
3、利用改进的选择排序算法（从小到大）对以下数据（75、84、65、73、55、52、79、66） 进行一趟操作的结果是（ ）。
A、52、75、84、65、73、55、66、79 B、75、65、73、55、52、79、66、84
C、52、84、65、73、55、75、79、66 D、52、84、75、73、65、55、79、66
4、对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为。
A、1，2，3 B、9，5，2，3 C、9，5，3 D、9，4，2，3
5、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ）。
A．{38，46，79，56，40，84} B．{38，79，56，46，40，84}
C．{40，38，46，56，79，84} D．{38，46，56，79，40，84}
综合练习
1、计算机各部分之间的信息传输是通过总线结构来实现的。总线又分为三部分，下列不是总线三部分的是( )
A. 地址总线 B. 数据总线 C. 指令总线 D. 控制总线
2. 计算机指令是由一些简单的电信号来控制的。机器指令通常包括
( )
A. 地址码、控制码 B. 控制码、操作码
C. 识别码、操作码 D. 操作码、地址码
3. 计算机网络的主要目的是实现资源共享，它采用了多种连接方式将多台计算机连接在一起。以下不属于计算机网络采用的拓扑结构是( )
A. 总线结构 B. 星型结构 C. 树型结构 D. 环型结构
4、在计算机中，防火墙的作用是（ ）。
A. 防止火灾蔓延 B. 防止网络攻击
C. 防止计算机死机 D. 防止使用者误删除数据
5、 网络协议是支撑网络运行的通信规则，因特网上最基本的通信协议是( )。
A. HTTP协议 B. TCP/IP协议
C. POP3协议 D. FTP协议
6、 某处于环境恶劣高山之巅的气象台要在短期内接入Internet网，现在要选择连接山上山下节点的传输介质，恰当的选择是：( )
A. 无线传输 B. 光缆 C. 双绞线 D. 同轴电缆
7、在下列关于计算机算法的说法中，不正确的是（ ）。
A. 一个正确的算法至少要有一个输入
B. 算法的改进，在很大程度上推动了计算机科学与技术的进步
C. 判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性
D. 目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法
8、线性表（ a1,a2,„,an）以链表方式存储时，访问第i位置元素的时间复杂性为( )
A．O（i） B．O（1） C．O（n） D．O（i-1）
9、．一个n个顶点的强连通图，至少有多少个有向边( )。
A．n-1 B．（n-1）n C．（n-1）n/2 D．n
10. 对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为( )。
A. 1，2，3 B. 9，5，2，3
C. 9，5，3 D.9，4，2，3
10、树形结构中数据元素之间存在（ ）的关系。
A. 一对一 B. 一对多 C. 多对一 D. 无法确定
11、链表不具有的特点是（ ）。
A. 可随机访问任一元素 B. 插入删除不需要移动元素
C. 不必事先估计存储空间 D. 所需空间与线性表长度成正比
12、广义表A＝（a，（a，（a）））的深度为（ ）。
A. 3 B. 4 C. 5 D. 6
13、请指出在顺序表 { 2、5、7、10、14、15、18、23、35、41、52 }中，用二分法查找关键码12需做多少次关键码比较。（ ）
A． 2 B. 3 C. 4 D. 5
14、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ）。
A．{38，46，79，56，40，84} B．{38，79，56，46，40，84}
C．{40，38，46，56，79，84} D．{38，46，56，79，40，84}
15、 一数组构造双栈，栈1的栈底在数组的低端，栈2的栈底在数组的高端，如果进栈的序列为A、
B、C、D、E，则执行操作栈1进栈、栈2进栈、栈2出栈、栈1出栈、栈2进栈、栈2进栈、栈1进栈、栈2出栈、栈1出栈、栈2出栈后得到的序列为
A．BAEDC B CEDAB C BADEC D ABCDE
16、对于线性表L=（a1，a2，„，an），下列说法正确的是（ ）。
A、每个元素都有一个直接前驱和一个直接后继
B、线性表中至少要有一个元素
C、表中所有元素的大小排列顺序必须是由小到大或由大到小
D、除第一个和最后一个元素外，每个元素都有且仅有一个直接前驱和一个直接后继
17、利用改进的选择排序算法（从小到大）对以下数据（75、84、65、73、55、52、79、66） 进行一趟操作的结果是（ ）。
A、52、75、84、65、73、55、66、79 B、75、65、73、55、52、79、66、84
C、52、84、65、73、55、75、79、66 D、52、84、75、73、65、55、79、66
18、以下（ ）不是栈的基本运算？
A、删除栈顶元素 Ｂ、删除栈底元素
Ｃ、判断栈是否为空 Ｄ、将栈置为空栈
19、将下三角矩阵A[1．．8，L．8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7，5]的地址为 。
A、1020 B、1100 C、1080 D、1120
20、两个栈共享一个存储空间的好处是（ ）。
A、节省存储空间，降低上溢发生的机率 B、减少存取时间，降低下溢发生的机率
C、节省存储时间，降低下溢发生的机率 D、减少存取时间，降低上溢发生的机率
21、一个递归算法必须包括（ ）
A. .递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部分
22、以下哪一个不是栈的基本运算（ ）
A、删除栈顶元素 B、删除栈底元素 C、判断栈是否为空 D、将栈置为空栈
23、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ）。
A．{38，46，79，56，40，84} B．{38，79，56，46，40，84}
C．{40，38，46，56，79，84} D．{38，46，56，79，40，84}
24、线性表L=（a1，a2，„，an），下列说法正确的是（ ）。
A. 每个元素都有一个直接前驱和一个直接后继
B. 线性表中至少要有一个元素
C. 表中诸元素的排列顺序必须是由小到大或由大到小
D. 除第一个和最后一个元素外，每个元素都有一个仅有一个直接前驱和直接后继
25、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ）。
A．{38，46，79，56，40，84} B．{38，79，56，46，40，84}
C．{40，38，46，56，79，84} D．{38，46，56，79，40，84}
26、一棵二叉树如下图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 l，若某结点的下标为 i，则其左孩子位于下标 2i 处、右孩子位于下标2i＋1 处），则该数组的大
小
至少为 （ ） A．6 B．10 C．12 D．15
27、为了提高测试的效率，应该( )
A)随机选取测试数据
B)取一切可能的输入数据作为测试数据
C)在完成编码以后制定软件的测试计划
D)集中对付那些错误群集的程序
28、算法的时间复杂度是指( )
A)执行算法程序所需要的时间 B)算法程序的长度
C)算法执行过程中所需要的基本运算次数 D)算法程序中的指令条数
29、树是节点的集合，它的根节点数目是( )
A)有且只有1 B)1或多于1
C)0或1 D)至少2
30、在编程时（使用任一种高级语言，不一定是 C++或者是PASCAL），如果需要从磁盘文件中输入一个很大的二维数组（例如 1000*1000 的 double 型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（ ）。
A)没有区别 B) 按行读的方式要高一些
C) 按列读的方式要高一些 D) 取决于数组的存储方式。
31、下列排序算法中，( )每一趟都能选出一个元素放在其最终位置上，并且是不稳定的。
A)冒泡排序 B)希尔排序
C)直接选择排序 D)直接插入排序
32、64KB的存储器用十六进制表示，它的最大的地址码是( ) A)10000 B)FFFF C)1FFFF D)EFFFF
33、PC机中CPU进行算术和逻辑运算时，可处理的信息的长度为：( )
位 B) 16位 C) 8位 D) 都可以
34、一棵完全二叉树,如果其上有一个结点的编号为11,则其父结点的编号为(▲ ).
A)22 B)12 C)10 D)5
35、下面关于主存储器（也称为内存)的叙述中，不正确的是：
当前正在执行的指令与数据都必须存放在主存储器内，否则处理器不能进行处理
存储器的读、写操作一次读出或写入一个字节
字节是主存储器中信息的基本编址单位
从程序设计的角度来看，cache（高速缓存）也是主存储器
36、计算机的主存储器容量达到1GB时，其地址的表示至少需要使用多少个2进位？
位 B) 20位 C) 30位 D) 40位
37、MIPS是衡量CPU处理速度的一种常用指标，它的含义是：
每秒钟平均可执行的单字长定点指令的数目
每秒钟平均可执行指令的数目
每秒钟平均可执行的浮点指令的数目
每秒钟平均可执行的算术运算指令的数目
38、一幅1024×768的彩色图像，其数据量达2.25MB左右，若图像数据没有经过压缩处理，则该图像中的每一个像素是使用多少个二进位表示的？
位B) 16位C) 24位D) 32位
39、互联网络上的服务都是基于一种协议，WWW服务基于______协议。
A）SMIP B）HTTP C）SNMP D）TELNET
40、无向图G=(V，E)，其中V={a,b,c,d,e,f} E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}对该图进行深度优先遍历,得到的顶点序列正确的是( )
(A)a,b,e,c,d,f (B)a,c,f,e,b,d (C)a,e,b,c,f,d (D)a,b,e,d,f,c
第二部分 问题求解
排列与组合（详见高级本） 数据结构 奥数 递推等
[重要作业]
1、平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？
2、（子集划分）将n个数（1，2，„，n）划分成r个子集。每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为S(n,r)。例如，S(4,2)=7，这7种不同的划分方法依次为{(1),(234)}，{(2),(134)}，{(3),(124)}，{(4),(123)}，{(12),(34)}，{(13),(24)}，{(14),(23)}。当n=6，r=3时，S(6,3)=_________。
（提示：先固定一个数，对于其余的5个数考虑S(5,3)与S(5,2)，再分这两种情况对原固定的数进行分析。）
提示：S(6,3)=S(5,2)+3*S(5,3)
S(m,n)=s(m-1,n-1)+n*S(m-1,n)
3、某商店有m种不同颜色的小球且每种小球的数量都足够多。要在这m种不同颜色的小球里挑选出n个小球，设共有s种不同的选法。例如当m=2，n=3时，s等于4，也就是说，共有4种不同的选法。（分别为：【0，3】，【1，2】，【2，1】，【3，0】）。现在，令m=6，n=5，试求出选法数s=_______。
4、给出一组顶点（顶点值用A，B，C，D，E，F表示），其对应权值分别为2，3，1，7，8，4。请以A，B，C，D，E，F为叶子顶点构造一棵哈夫曼树，并求出它的最小带权路径长度WPL的值。
5、今天是放寒假的最后一天，马上迎来2011年春节，住在同一个宿舍的四名同学为了相互祝愿，每人各设计了一张贺年卡送给别人，为了避免矛盾，他们将贺年卡先集中起来，然后让每人从中拿一张别人送的贺年卡，问四张不同的贺年卡有多少种不同的取法。
错排问题
8、金中机器人小P由P1，P2，P3，P4，P5，P6六个子部件组成，这些子部件之间有下列关系：P1>P2, P1>P3, P1>P4, P2>P3, P2>P5, P3>P5,P3>P6, P4>P3,P4>P6, P5>P6
(‘>’表示先于关系，如P1>P2表示P1子部件完成安装后才能进行子部件P2的安装工作)，请搞信息学竞赛的你告诉金中机器人兴趣小组的同学该如何安装小P。(注意：一个时间段只能安装一个子部件，如果有多种安装方法，只需给出其中一种安装秩序)
9、设计法码称重。要求：
(1)不同重量的法码最多设计一个，
(2)必须能称出规定重量以内所有物品的重量
(3)设计最少的法码；
如要称4克以内的重量，可设计2种不同重量的法码(1克和3克，可称1克到4克重量) 若称1000克以内重量的物品，需要设计的最少法码个数。
10、 有14个人排队买票，每人要买一张票，票价每张50元，恰有7个人只有50元钞票，7个人只有100元钞票，已知开始售票之前售票员无零钱，问有多少种排法使得售票员不至于找不开钱（拿着同样面值钞票的人视为等价）。
11、一位大城市的律师在他住所以北n个街区和以东n个街区处工作。每天他走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
12、 设有一棵k叉树，其中只有度为0和k两种结点，设n 0 ，n k ，分别表示度为0和度为k的结点个数，试求出n 0 和n k之间的关系。
度之和=nk*k 结点数=
13、一棵二叉树的先序、中序、后序遍历序列分别如下，其中有一部分未显示出来，请补全各序列。 先序 ABDFKICEHJG
中序 DBKFIAHEJCG
后序 DKIFBHJEGCA
14、假定一个AOV网的顶点集和边集为：
V={0,1,2,3,4,5,6,7,8,9}
E={,,,,,,,,,,,,,,};若在他的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则写出唯一一种拓朴序列。
15
、如图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，
如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。
16、对于下面这棵树，写出它的先根遍历结果（2
分），然后将该树转换成二叉树。
17、对下图所示的带权无向图，写出深度优先搜索
序列（从1出发）（3分），并按克鲁斯卡算法求其最小生成树。
18、对于下面的有向图，有多少种不同的拓朴序列。
第三部分 写程序运行结果
一、模拟法----“死算”
1、var a,work:array[1..100] of integer;
i,j,x,d,max:integer;
begin
read(max);
for i:=1 to max do begin read(a[i]); work[i]:=a[i]; end;
d:=max div 2;
while d>=1 do
begin
for i:=d+1 to max do
begin
x:=work[i];
j:=i-d;
while (j>0) and (x
begin
work[j+d]:=work[j];
dec(j,d);
end;
work[j+d]:=x;
end;
d:=d div 2;
end;
for i:= max downto 1 do
begin
if a[i]=work[i] then write('1')
else write('0');
end;
end.
输入：10 71 149 32 11 90 119 9 130 95 144
2、const maxn=100；
type arr=array[0.. maxn] of integer ;
var ans：array[1..maxn] of arr；
n：integer；i，J：integer；
procedure main；
begin
fillchar(ans,sizeof(ans)，0)；
for i：=1 to n do ans[1，i]：=1；
for i:=2 to n do
begin
for J：=1 to i-1 do
ans[i,j]：=ans[i-j, j]+ ans[i, j-1];
for J：=i to n do ans[i，J]：=ans[i, i-l ]+1；
end：
end;
begin
readln(n);
main;
write(ans[n,n])；
end. 输入n=7时，其运行结果是
3、var i,zimu,j,k:char;
begin
repeat
readln(zimu);
zimu:=upcase(zimu); {upcase 是小写转大写} until (zimu>='A') and (zimu
for i:='A' to zimu do begin
write(' ':(ord(zimu)-ord(i))+1);
for j:='A' to i do write(j); for j:=pred(i) downto 'A' do write(j); if (ord(i)-64) mod 25=0 then readln else writeln;
end;
end.
输入 E 输出：
4、Var I,j:integer;
A:array[1..3,1..3] of integer;
Begin
For i:=1 to 3 do
Begin
For j:= 1 to 3 do
Begin
If i=3 then
a[I,j]:=a[i-1,a[i-1,j]]+1
else
a[I,j]:=j;
write(a[I,j]);
end;
writeln;
end;
end.
5、var i,j,l,n,k,s,t: integer;
b: array[1..10] of 0..9;
begin
readln(l,n);s:=l; k:=1; t:=l;
while s
begin
k:=k+1;t:=t*l; s:=s+t;
end;
s:=s-t; n:=n-s-1;
for i:=1 to 10 do b[i]:=0;
j:=11;
while n>0 do
begin
j:=j-1;b[j]:=n mod l; n:=n div l;
end;
for i:=10-k+1 to 10 do write(chr(ord('A')+b[i]));
END.
输入：5 257
二、分析公式、规律
1、Var g:integer; k,t:real; m:integer; Begin
K:=0;g:=0;
For m:=1 to 49 do
Begin
g:=g+1;
k:=k+1/(g*(g+1));
end;
writeln(k:10:2);
End.
2、var n,i:integer;
total:longint;
function work(a,b:integer) : longint;
var c,d,e:longint;
i:integer;
begin
c:=1;
for i:= 2 to a do c:= c*i;
d:=1;
for i:= 2 to b do d:= d*i;
e:=1;
for i:= 2 to a-b do e:= e*i;
exit(c div d div e);
end;
begin
read(n);
total:=0;
for i:= 1 to n do total:=total + work(n,i); write(total);
end.
输入：12
3、var a,b,c:integer;
function D(b:integer):integer;
var t:integer;
begin if b=0 then D:=1
else begin t:=D(b div 2);
t:=t*t mod c;
if odd(b) then D:=t*a mod c else D:=t
end;
end;
begin readln(a,b,c); writeln(D(b)); end. 输入： 993 294 10 输出：
4、Var M,n,I,p,k:integer;
r:array[1...200] of integer;
b:Boolean;
begin
m:=6;n:=2;
for i:=1 to m-1 do r[i]:=i+1;
r[m]:=1;i:=0;p:=1;b:=true;
while b do
begin
i:=i+1;k:=p;P:=r[p];
if k=p then
begin writeln(p);b:=false; end; else if i=n+1 then
begin
write(p,’ ’);i:=0;p:=r[p];r[k]:=p; end;
end;
end.
5、var a:array[1..10] of integer;
s,n,m:longint;
flag:set of byte;
procedure try(dep:integer);
var i:integer;
begin
for i:=1 to n do
if not(i in flag) then
begin
flag:=flag+[i];
a[dep]:=i;
if dep=m then inc(s) else try(dep+1); flag:=flag-[i];
end;
end;
begin
readln(m,n);
flag:=[];s:=0;
try(1);
writeln(s);
end;
输入：4 5
三、字符串处理
1、Var N,I,tem,t:longint;
S:string;
Begin
readln(n);
S:=’1’;
Repeat
I:=length(s);
While s[i]=’1’ do
Begin
S[i]:=’0’;dec(i);
End;
If i>0 then s[i]:=’1’ else s:=’1’+s; Val(s,t,tem);
Until t mod n =0;
Writeln(n,’*’,t div n,’=’,s);
End.
输入：6
2、var s:string; n,p,q,i:integer;
a:array[1..10]of char; c:char;
begin
readln(n);
s:='OIFans.cn-Fly with the same dream'; p:=pos('s',s);
s:=copy(s,p+19,255);
s:=copy(s,n,255);
c:='a'; q:=1;
for i:=1 to length(s) do
if s[i]>c then
begin
a[q]:=s[i]; c:=a[q]; inc(q);
end;
dec(q);
for i:=1 to q do write(a[i]);
end.
输入：2
3、var len,n:word;
string0:string;
function l(st:string;i:integer):string;
begin
len:=length(st);
if (len=0) or (len
function r(st:string;n:integer):string;
begin
len:=length(st);
if (len=0) or (len
begin
readln(string0);
readln(n);
writeln(l(string0,n));
writeln(r(string0,n));
end.
输入：aabbccwwabcabc
6
四、函数与过程
[要点]参数，前面加VAR的参数，在函数与过程中变量的结果会向主程序中传递。
1、Var a,b:integer;
Procedure p1(x:integer;var y:integer);
Begin
x:=x+y; y:=x+y;
End;
begin
a:=5;b:=8;
p1(a,b);writeln(a:3;b:3);
p1(b-a,b);writeln(a:3;b:3);
end.
2、var x，s:Integer；
function ms(a，b:Integer；VAR x : Integer) : Integer；
begin
x:=3*a-4*b+x；
ms:=x MOD 10
end；
begin
x:=3；
s:=ms(ms(1，2，x)，2*ms(1，2，x)，x)；
writeln (‘x=’，x) ;
end.
3、var n,i,min,k,buf:word;
b:array[0..3000] of byte;
function max(a,b:byte):byte;
begin
if a>b then max:=a else max:=b;
end;
begin
b[0]:=0;b[1]:=0;b[2]:=1 write(‘n=’);readln(n);
for i:=3 to n do
begin
min:=999;
for k:=1 to i div 2 do
begin
buf:=max(b [i-2*k],b[k]);
if min>buf then min:=buf;
end;
b[i]:=1+min;
end;
writeln(b[n]);
end.
输入：n=32
4、var x,y,z:integer;
proedure silly(x:integer;var y:integer);
begin
x:=5;y:=6;z:=3;
writeln(x:2,y:2,z:2);
end;
begin
x:=1;y:=2;z:=3;
silly(x,y);
writeln(x:2,y:2,z:2);
end.
五、递归
1、 Function f(var x:integer; y, z:integer):integer;
Begin
X:=x+y+z;
F:=x
End;
Begin
x:=1; y:=2; z:=3;
y:=f(x,f(x,y+z,z+x),y);
Writeln(x:4,y:4,z:4)
End.
2、Const n=10;
Function fn(n:integer):integer;
Begin
If n
Else if n=1 then
Fn:=1
Else
Fn:=fn(n-1)+n;
End;
Begin
Writeln(fn(n));
Readln;
End.
3、function fac(n:integer):integer;
var t:integer;
begin if (n=1) or (n=2) then fac:=n
else fac:=fac(n-1)+fac(n-2);
end;
begin write(fac(6));
end.
4、var n:integer;
function count(n:integer):integer;
begin
if n=1 then count:=0
else if n mod 2=0 then count:=count(n div 2)+1
else count:=count(n*3+1)+1;
end;
begin
readln(n);
writeln(count(n));
end.
输入：77
5、Function Fun(X:Integer):Integer;
Begin
If (X=0) Or (X=1) Then Fun:=3
Else Fun:=X-Fun(X-2);
End;
Begin
WriteLn(Fun(9));
End.
6、Var k,j:Integer; A:Array[1..10] Of Integer;
Procedure Try(i:Integer);
Begin
For j:=1 To 3 Do
Begin
A[i]:=j;
If i=2 Then Begin
For k:=1 To 2 Do
Write(A[k]);
Writeln;
End
Else Try(i+1);
End;
End;
Begin
Try(1);
End.
7、var i,j:integer;
function p(n,x:integer):integer;
begin
if n=0 then p:=1 else if n=1 then p:=x
else P := trunc(((2*n)*p(n-1,x)-(n-1)*p(n-2,x))/n);
end;
begin
readln(i,j);
writeln(p(i,j));
end.
输入：3 5
8、var a,b:integer;
function fun(a,b:integer):integer;
var k:integer;
begin
if a
else
if b=0 then fun:=a
else if not odd(a) then
if not odd(b) then fun:=fun(a div 2,b div 2)*2
else fun:=fun(a div 2,b)
else
if not odd(b) then fun:=fun(a,b div 2)
else fun:=fun(b,a-b)
end;
begin
a:=234; b:=432;
writeln(fun(a,b));
end.
输出的结果是：
9. var a : array [1..50] of integer;
n, i, sum : integer;
procedure work(p, r: integer);
var i, j, temp : integer;
begin
if p
i := p - 1;
for j := p to r - 1 do
if a[j] >= a[r] then begin
inc(i);
temp := a[i]; a[i] := a[j]; a[j] := temp;
end;
temp := a[i + 1]; a[i + 1] := a[r]; a[r] := temp;
work(p, i);
work(i + 2, r);
end;
end;
begin
read(n);
for i := 1 to n do read(a[i]);
work(1, n);
for i := 1 to n - 1 do sum := sum + abs(a[i + 1] - a[i]);
writeln(sum);
end.
输入：8 16 34 12 25 78 43 6 9
输出的结果是：
第四部分 完善程序
1、输入一个正整数，然后与它倒过来的数相加。先将读入的正整数进行数字分离，分离出的个位、十位、百位„„数字，依次存放到a[10]、a[9]、a[8]、„„各下标变量中，然后再将它们合并成一个倒过来的数y，再与原数相加。
var a : array[1..10] : integer ;
i , j , x , x1 , y : integer;
begin
readln(x);
x1 := x ;
j := ① ;
while ② do
begin
j := j – 1 ;
a[j] := x mod 10 ;
x := ③ ;
end;
y := 0;
for i := ④ do
y := y * 10 + a[i] ;
x := ⑤ ;
writeln(x)
end.
2． 读入N个不相同且不为0的数（1≤N≤100），求出其中第R个大的数（1≤R≤N）。 例如：输入3，14，22，15，17，6，其中第3个大的数为15。
以数组A[100]记录读入的N个数，并以0为结束（0本身不是N个数中的），然后从第一个数开始，将它与其余的数进行比较，并记录出比它大的数的个数（存于变量y中），若y=R-1时，得到所求结果，否则对下一个数进行同样的处理。
var a : array[1..100] : integer ;
i , j , k , x , y : integer;
begin
read( R );
j := 0 ;
read(x);
while ① do
begin
j := ② ;
a[j] := x ;
read(x)
end;
i := 0;
repeat
i := i+1;
x := a[i] ;
y := 0 ;
for k :=1 to ③ do
if x
until ⑤ ;
write(a[i]);
end.
3、从三个元素（例如1，2，3）的字符表中选取字符，生成一个有n个符号的序列，使得其中没有2个相邻的子序列相等。如长度n=5的序列“12321”是合格的，而“12323”和“12123”都是不合格的。
Const n=5;
Var a:array [1..n] of integer;
K,h:integer;
Procedure recn(I:integer);
Var j,k:integer;
S:set of 1..3;
Begin
S:=[1..3];
For j:=1 to I-1 do
If a[I]=a[j] then s:=s-[ ];
If s then
For k:=1 to do
If k in s then
Begin
A[I+1]:= ;
If I+1=n then
Begin
For j:=1 to n do
Write(a[j]:3);
H:=h+1;
If h mod 6=0 then writeln
End
Else recn( )
End;
End;
Begin
(6) ;
For k:=1 to 3 do
Begin
(7)
Recn(1);
End;
Writeln(‘h=’,h);
End.
4、以下程序是将一组整数按从小到大的顺序排列。排序的方法是将长度为n的数a分为两个长度为(n div 2)与（n-n div 2）的子数组，a1,a2，然后递归调用排序过程，将a1,a2分别排序，最后将a1,a2归并成数组a。例如a=(3,1,2,4)，那么a1=(3,1),a2=(2,4)。调用排序过程将a1,a2排序，得到a1=(1,3),a2=(2,4),然后进行合并排序。从键盘输入数的n以及n个整数，存在数组a中，调用子过程sort进行排序，最后输出排序结果。
const maxn =100;
type arr=array[1..maxn] of integer;
var a:arr;
n,i:integer;
procedure sort(n:integer; var a:arr);
var
i,p1,p2,n1,n2:integer; a1,a2:arr;
begin
if n=1 then exit;
fillchar(a1,Sizeof(a1),0);
fillchar(a2,sizeof(a2),0);
n1:=0; n2:=0;
n1:=n div 2; n2:= ⑴ ;
for i:=1 to n1 do a1[i]:=a[i];
for i:=1 to n2 do a2[i]:= ⑵ ;
⑶ ;
sort(n2,a2);
p1:=1; p2:=1;
n:=0;
while(p1
begin
n:=n+1;
if ⑸ then begin a[n]:=a1[p1];inc(p1);end
else begin ⑹ ;inc(p2);end;
end;
if p1
else for i:=p2 to ⑺ do begin n:=n+1; a[n]:=a2[i]; end;
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
sort(n,a);
for i:=1 to n do write(a[i],' ');
end.
5、求N个数中的第K小的数。程序利用快排（递归、分治算法），当找到第N个小的数时候就停止。
样例：输入：5 {N}
5 6 4 1 8 {N个数}
2 {第2小的数}
输出：4 {第2小的数是4}
var i,j,k,n:integer;
a:array[1..100] of integer;
procedure search(b,e:integer);
var i,m,t:integer;
begin
if b=e then ___;
i:=b; j:=e; m:=a[k];
repeat
while t:=a[i];a[i]:=a[j];a[j]:=t end;
until i>=j;
if i=k then exit;
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
readln(k);
search(1,n);
writeln(a[k]);
end.
6、根据二叉树的前序遍历和中序遍历，求出树的后序遍历。
样例输入：abdec （前序） 输出：debca（后序）
dbeac （中序）
var s1, s2 : string;
procedure try(L1, r1, L2, r2 : integer);
var m : integer;
begin
m := pos(s1[L1], s2);
if m >L2 then try( );
if m
write(s1[L1])
end;
begin
readln(s1); readln(s2);
try(1, length(s1), 1, length(s2));
end.
7、一个整数的整数子串是由该整数的连续数位的数字构成。
例如： 6518的子串包括6，5，1，8，65，51，18，651，518，6518
任务：找出最大的质数子串
输入：整数N（0
输出：N的最大质数子串，若所有的子串都是非质数，则输出“No primes”
样例：输入：2319 输出：31
var maxp,max,k:longint;
n,s:string; len,I,j:integer; code,bj:word;
begin
___ ___①_____; _____②_____;
for I:=1 to len do
for j:=1 to len-I+1 do
begin
s:=copy(n,j,I);
val(s,maxp,code);
bj:=0;
for k:=2 to trunc(sqrt(maxp)) do
if maxp mod k=0 then
begin
____③_ __;
k:=trunc(sqrt(maxp));
end;
if maxp=1 then __④____;
if ___⑤____ then max:=maxp;
end;
if max=0 then writeln('no primes') else writeln(max);
end.
8、字符串变换。设有2个字符串A$,B$, B$经过一系列的变换变成A$, 变换的规则为：可以在任意位置加入、删除、变换字符。例如：A$=’abcde’, B$=’bcwye’,此时B$可在b前面加入一个a成为’abcwye’,再将w变为d,成为’abcdye’,最后删除y,成为’abcde’,即B$经过3次变换,成为A$, 本程序就是要求最少变换次数。
程序说明：A$、B$分别用字符串数组a、b存放，采用动态规划求解，g[m,n]表示B数组的前m个字符要变成A数组的前n个字符所需要的最少次数。
Var a,b:string; g:array[0..100,0.100] of integer;
I,j,k,lg1,lg2,min:integer;
Begin readln(a);readln(b);
Lg1:=length(a); ___ _______________________;
For i:=0 to lg1 do g[0,i]:=I;
For i:=1 to lg2 do
Begin ____ ____________;
For j:=1 to lg1 do
If (a[j]=b[i]) then g[I,j]:=__ ___
Else begin min:=__ __;
If (min>g[i-1,j]) then min:=g[i-1,j];
If (min>g[I,j-1]) then min:=g[I,j-1];
G[I,j]:=min+1;
End;
End;
Writeln(____);
End.
9、挖宝藏。现有n个藏宝室，每个室中有一定数量的的宝藏，同时给出从一个室到另一个室的通行时间，约定从1室开始挖，挖宝藏的时间可以忽略，每个室只能经过一次，任意两个室都相通，当然所用的时间不相同，给定一个时间tk,求在这个时间内最多能挖到多少宝藏。{回溯算法} 输入： n tk {第一行两个数，分别为宝藏室个数和给定时间}
d1,d2,d3,„„，dn {第二行为每个室中宝藏数}
g11,g12,g13,„„g1n {以下数据用g数组存放，g[I,j]表示从i室到j室所 g21,g22,g23,„„g2n 需的时间}
„„
gn1,gn2,gn3,„„gnn
样例：输入：4 10 输出：11
3 2 1 5 {走的路线是：1-2-4-3}
0 3 2 6
1 0 2 4
1 4 0 8
1 3 3 0
var I,j,k,n,s0,tk,t,cmax,top:integer;
stack,d,flag:array[1..30] of integer; g:array[1..30,1..30]of integer;
begin readln(n,tk); for i:=1 to n do read(d[i]);
for i:=1 to n do
for j:=1 to n do read(g[I,j]);
for i:=1 to n do flag[i]:=0; k:=0; t:=tk; cmax:=d[1]; s0:=d[1]; top:=1;
_________; flag[1]:=1;
While (top>=0) do
Begin k:=k+1; if (k>n) then begin k:=stack[top];top:=top-1;
t:=t+g[stack[top],k]; flag[k]:=0;
s0:=___ ______
end
else if ((flag[k]=0) and ( ________)) then
begin s0:=s0+d[k]; _ ______________;
if (s0>cmax) then cmax:=s0;
t:=t-g[stack[top],k];
top:=top+1; stack[top]:=k;__ _______________;
End;
End; writeln(cmax);
End.
10、求元素之和最大的子方阵：在m×n（m，n≤20）的正整数数字方阵中，找出一个p×q的子阵（1≤p≤m，1≤q≤n）使其元素之和最大。例如，下面5×4的数字阵中，元素之和最大的一个2×3子阵。
5×4数字阵元素之和最大的2×3子阵为
VAR A:ARRAY[1..20,1..20] OF INTEGER;
M,N,P,Q,I,J,MAX,PL,QL,S,IL,JL:INTEGER;
BEGIN
FOR I:=1 TO 20 DO FOR J:=1 TO 20 DO A[I,J]:=0; READLN(M,N); FOR I:=1 TO M DO BEGIN FOR J:=1 TO N DO READ(A[I,J]); READLN; 第
END; READLN(P,Q);
MAX:=O