当前位置:首页 >> 学科竞赛 >>

信息学奥赛初赛复习题


内部资料 注意保密

信息学奥赛初赛复习

金陵中学河西分校

第 0



第一部分:选择题
一、 、计算机发展历程 (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. 双字
第 1 页

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. 采用集成电路作为计算机的主要功能部件。
第 2 页

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.应用程序
第 3 页









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.10111100101 B.11111100101 C.11110100101 D.11111101101 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 )。 6、已知 A=(72E)H,B=(1315)D,则 A-B 的结果是 ( ) 。 D) 63

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 的地址为 ( )
第 4 页

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
第 5 页

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},那么集合

( A ? B) ? (~ C ? B) 为( )。
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,3,5,1,6},请问E的所有子集个数是多少?( ) A) 25 B) 10 C) 32 D) 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、下列叙述中,正确的是( ) .
第 6 页

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 的容量至少应该为( ) A) 2 B) 3 C) 4 D) 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,则其元素个数为 ( ) .
第 7 页

A.r- f C. (r- f ) MOD n+1 八、树(详见高级本 P108-111)

B.r- f +1 D. (r- f + n) MOD n

[补充作业] 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、下列排序算法中,最坏情况下的时间复杂度最低的是(
第 8 页



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 位置元素的时间复杂性为( )
第 9 页

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、删除栈顶元素 B、删除栈底元素 C、判断栈是否为空 D、将栈置为空栈 19、将下三角矩阵 A[1. .8,L.8]的下三角部分逐行地存储到起始地址为 1000 的内存单 元中,已知每个元素占 4 个单元,则 A[7,5]的地址为 。 A、1020 B、1100 C、1080 D、1120
第 10 页

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) 取决于数组的存储方式。
第 11 页

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 40 、 无 向 ) (D)a,b,e,d,f,c B)HTTP 图 G=(V , C)SNMP E) , 其 中 D)TELNET 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

第二部分
排列与组合(详见高级本) 数据结构 [重要作业]

问题求解
奥数 递推等

1、平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点 都不在同一条直线上。问用这些点为顶点,能组成多少个不同三角形?
第 12 页

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) 1 2 3 1 1 2 1 1 3 1 3 1 4 1 7 6 5 1 15 25 6 1 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=_______。 1 1 2 3 4 5 6 2 1 3 6 3 1 4 10 4 1 5 15 5 1 6 21

1 2 3 4 5 6

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)必须能称出规定重量以内所有物品的重量
第 13 页

(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={<0,2>,<0,3>,<1,3>,<1,4>,<2,3>,<2,5>,<3,5>,<3,6>,<3,8>,<4,6>,<5,7>,<5,8>,<6 ,8>,<7,9>,<8,9>};若在他的邻接表存储结构中,每个顶点邻接表中的边结点都是按照终 点序号从大到小链接的,则写出唯一一种拓朴序列。

15、如图表示一个地区的通讯网,边表示城市间的通讯线路,边上的权表示架设线路花费 的代价,如何选择能沟通每个城市且总代价最省的 n-1 条线路,画出所有可能的选择。 16 、对于下面这棵树,写出它的先根遍历结果( 2 分) ,然后将该树转换成二叉树。

17、 对下图所示的带权无向图, 写 出深度优先搜索序列(从 1 出发)
第 14 页

(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<work[j]) do 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;
第 15 页

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<='Z'); 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
第 16 页

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<n do 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);
第 17 页

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
第 18 页

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
第 19 页

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<=n) then l:=st else l:=copy(st,1,n); end; function r(st:string;n:integer):string; begin len:=length(st); if (len=0) or (len<=n) then r:=st else r:=copy(st,len-n+1,n); end; begin readln(string0); readln(n); writeln(l(string0,n));
第 20 页

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]);
第 21 页

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<1 then fn:=0 Else if n=1 then Fn:=1 Else Fn:=fn(n-1)+n; End; Begin Writeln(fn(n));
第 22 页

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
第 23 页

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<b then fun:=fun(b,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 < r then begin
第 24 页

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)
第 25 页

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<a[k] then ④ ; 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
第 26 页

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);
第 27 页

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<=n1) and ⑷ do begin n:=n+1; if ⑸ then begin a[n]:=a1[p1];inc(p1);end else begin ⑹ ;inc(p2);end; end; if p1<=n1 then for i:=p1 to n1 do begin n:=n+1; a[n]:=a1[i] end 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 _ __do inc(i); while _ ____ do dec(j); if __ __ then begin t:=a[i];a[i]:=a[j];a[j]:=t end;
第 28 页

until i>=j; if i=k then exit; if i>k then __ else __ _____; 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 < r2 then try( ); 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<=1000000000) 输出: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);
第 29 页

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 {第一行两个数,分别为宝藏室个数和给定时间}
第 30 页

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 子阵为 3 8 4 22 11 5 10 2 1 21 3 7 7 6 8 12 9 2 9 3
第 31 页

5 10

21 3

6 8

VAR A:ARRAY[1..20,1..20] 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 FOR I:=1 TO M-P+1 DO FOR J:=1 TO N-Q+1 DO BEGIN ______① _______; FOR IL:=I TO __ __②____DO FOR JL:=J TO _ __③____DO ______④__ ____; IF S>MAX THEN BEGIN _______⑤ _______; PL:=I; QL:=J; END; END;

OF

INTEGER;

FOR I:=PL TO _ __⑥____DO BEGIN FOR J:=QL TO _ __⑦ ____DO WRITE(A[I,J]):3); WRITELN; END; READLN; END.

第 32




相关文章:
信息学奥赛初赛复习题
内部资料 注意保密 信息学奥赛初赛复习 金陵中学河西分校 第 0 页 第一部分:选择题一、 、计算机发展历程 (NOI2007笔试复习题,部分) 1、NOI机试使用的操作系统...
信息学奥赛普及组初赛模拟试题
信息学奥赛普及组初赛模拟试题(一) 发布: 郭琪 时间: 2011/7/6 13:56:18 讨论: 0 来源: 宁夏教研网 点击: 77 一、选择题:共 20 题,每题 1.5 分,共...
第十七届全国青少年信息学奥林匹克联赛初赛试题
第十七届全国青少年信息学奥林匹克联赛初赛试题_学科竞赛_高中教育_教育专区。第...第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 普及组●● Pascal 语言 两...
全国青少年信息学奥林匹克联赛初赛试题2009-2015
(middle, middle), target 第 34 页共 65 页 第十八届全国青少年信息学奥林匹克联赛初赛(普及组 Pascal 语言试题) 竞赛时间:2012 年 10 月 13 日 14:30~...
第十届全国青少年信息学奥林匹克联赛初赛试题及答案
第十届全国青少年信息学奥林匹克联赛初赛试题及答案_学科竞赛_高中教育_教育专区。2004 第十届全国青少年信息学奥林匹克联赛初赛试题及答案 第十届全国青少年信息学...
2016信息学竞赛选拔试题
2016信息学竞赛选拔试题_学科竞赛_小学教育_教育专区。信息学竞赛选拔试题班级___ 姓名___ 一、选择题(共 25 分) 1.一个完整的计算机系统应包括( )。 A...
青少年信息学奥林匹克初级竞赛辅导练习题
青少年信息学奥林匹克初级竞赛辅导练习题_学科竞赛_小学教育_教育专区。第一题(p236) 问题描述:将键盘输入的字符串中所有的十进制数找出来,并求它们的和。 输入:...
小学生信息学奥林匹克竞赛试题
小学生信息学奥林匹克竞赛试题_学科竞赛_小学教育_教育专区。小学信息学奥赛竞赛题 武进区小学生信息学奥林匹克竞赛试题 BASIC 语言 二小时完成 一.选择一个正确...
信息学奥赛试题精选33题(附带题解)
信息学奥赛试题精选33题(附带题解)_学科竞赛_高中教育_教育专区。信息学奥赛...信息学奥赛初赛试题(第十... 8页 1下载券 信息学奥赛基础试题解析 82页 1...
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:20...
更多相关标签: