《信息学奥赛初赛复习题讲解学习.doc》由会员分享，可在线阅读，更多相关《信息学奥赛初赛复习题讲解学习.doc（102页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Good is good, but better carries it.精益求精，善益求善。信息学奥赛初赛复习题-内部资料注意保密信息学奥赛初赛复习金陵中学河西分校第一部分：选择题一、计算机发展历程（NOI2007笔试复习题，部分）1、NOI机试使用的操作系统是：A.WindowsB.LinuxC.MacOSD.Vxworks2、Linux中为文件改名使用的命令是：A.mvB.renC.chrootD.su3、在Linux中返回上一级目录使用的命令是：A.cdB.cd.C.cd.D.cd./4、使用高级语言编写的程序称之为：A.源程序B.编辑程序C.编译程序D.链接程序5、属于面向对象程序设计
2、语言的是：A.CB.C+C.PascalD.Basic6、在Linux系统中，下面的说法中正确的是：A.文件夹中的文件可以与该文件夹同名B.文件夹中的文件不能与该文件夹同名C.在不同文件夹中的两个文件不可以使用相同的文件名D.以上说法都不对7、一个完整的计算机系统应包括_。A.系统硬件和系统软件B.硬件系统和软件系统C.主机和外部设备D.主机、键盘、显示器和辅助存储器8、目前微型计算机中采用的逻辑组件是_。A.小规模集成电路B.中规模集成电路C.大规模和超大规模集成电路D.独立组件9、软件与程序的区别是_。A.程序价格便宜、软件价格昂贵B.程序是用户自己编写的，而软件是由厂家提供的C.程序是用
3、高级语言编写的，而软件是由机器语言编写的D.软件是程序以及开发、使用和维护所需要的所有文档的总称,而程序是软件的一部分10、IT表示_。A.通信技术B.信息技术C.网络技术D.信息学11、计算机中央处理器简称为_A.IBMB.UBSC.CPUD.Computer11、计算机内存储器的作用是_A.用来存放暂时不用的程序和数据B.用来存放当前CPU正在使用的程序和数据C.用来存放要删除的信息D.仅用来存储选手的数据和程序12、用来全面管理计算机硬件和软件资源的软件叫_A操作系统B应用软件C管理软件D.系统平台13、LAN是指_A互联网B局域网C广域网D.城域网14、在微机中，bit的中文含义是_。
4、A.二进制位B.字C.字节D.双字15、为了避免混淆，十六进制数在书写时常在后面加字母_。A.HB.OC.DD.B16、.计算机所能辨认的最小信息单位是_。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、现代计算机所应用的存储程序原理是
5、_提出的。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点阵的字库中，汉字“一”与“编”的字模占用字节数分别是（）。A3
6、2、32B32、72C72、72D72、323、不同的计算机，其指令系统也不相同，这主要取决于（）。A所用的操作系统B系统的总体结构C所用的CPUD所用的程序设计语言4、2KB的内存能存储()个汉字的机内码A)1024B)516C)2048D)2185、下列哪个（些）软件不是操作系统软件的名字（）。A）WindowsXPB)DOSC)LinuxD)OS/2E)ARCH/INFO6、美籍匈牙利数学家冯诺依曼对计算机科学发展所做出的贡献是（）。A. 提出理想计算机的数学模型，成为计算机科学的理论基础。B. 是世界上第一个编写计算机程序的人。C. 提出存储程序工作原理，并设计出第一台具有存储程序功能
7、的计算机EDVAC。D. 采用集成电路作为计算机的主要功能部件。E、指出计算机性能将以每两年翻一番的速度向前发展。7、下列哪个不是CPU（中央处理单元）（）。A.IntelItaniumB.DDRSDRAMC.AMDAthlon64D.AMDOpteronE.IBMPower58、下面哪个部件对于个人桌面电脑的正常运行不是必需的（）。A. CPUB.图形卡（显卡）C.光驱D.主板E.内存9、下列哪个软件属于操作系统软件（）。A.MicrosoftWordB.金山词霸C.FoxmailD.WinRARE.REDHATLINUX10、下列哪个不是计算机的存储设备（）。A.文件管理器B.内存C.高速
8、缓存D.硬盘E.U盘11、下列哪个程序设计语言不支持面向对象程序设计方法（）。A.C+B.ObjectPascalC.TURBOPASCAlD.SmalltalkE.Java12、设有一个十阶的对称矩阵A采用压缩存储方式，以行序为主存储，a11为第一个元素。其存储地址为1，每个元素占1个地址空间，则a85的地址为()。A)13B)33C)18D)5013、奔腾的地址线是32根，最大存储量为（）A4GBB4MBC32MB14、JPEG是一种（）的图象压缩方式（）A有损压缩B无损压缩C不可压缩D以上都正确15、一台计算机的字长是8字节，表示是（）A能处理的数字最大是8个十进制数99999999B能
9、处理的字符串最多由8个英文字母组成C在CPU中作为一个整体加以传送处理二进制代码为64位DCPU的运行的最大结果为2的64次方16、微型计算机内存储器是按（）A二进制位编码B字节编码C字长编码DCPU的型号不同而编址不同17、下列叙述中正确的是（）A汉字的计算机内存是国际码B存储器具有记忆能力，其中的信息任何时候都不会消失C所有十进制数都能准确的转换为二进制数D正数的二进制原码的补码是原码本身18、PASCAL编译程序的功能是（）A把PASCAL源程序转换成可运行的EXE文件B生成和修改一个PASCAL源程序C实现PASCAL的源程序到等价的目标程序的转换D实现PASCAL的源程序到等价的目标
10、码程序的转换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、分辨率为128
11、0*1024真彩色（16位）的17英寸显示器的显存容量应为（）MB。A、1B、2.5C、4D、826、计算机的主存储器容量达到1GB时，其地址的表示至少需要使用（）个2进制位。A、10位B、20位C、30位D、40位27、PASCAL程序运行时，是在哪种存储器中进行。（）A、硬盘B、RAMC、ROMD、CACHE三、计算机中数的表示1、十进制算术表达式：3*512+7*64+4*8+5的运算结果，用二进制表示为（）。A10111100101B11111100101C11110100101D111111011012、计算机中的数有浮点与定点数两种，其中用浮点数表示的数，通常由（）这两部分组成。A
12、指数与基数B尾数与小数C阶码与尾数D整数与小数3、x补码=10011000，其原码为()A)011001111B)11101000C)11100110D)011001014、表达式(1+34)*5-56/7的后缀表达式为（）。A）1+34*5-56/7B）-*+1345/567C）134+5*567/-D）1345*+567/-E）134+5567-*/5、8位无符号二进制数能够表示的最大十进制数是（）。A）255B）256C）64D）636、已知A=(72E)H，B=(1315)D，则A-B的结果是()。A）(674)OB）(1AD)HC）(523)DD）(101101011)B7、产生10
13、0至300之间的随机整数(Random)，且包含100，300两个整数的表达式（）ARandom(100)+200BRandom(200)+100CRANDOM(201)+100DRandom(300)8、在微型计算机中，常用（）码实现十进制数与二进制数之间的自动转换（）ABCD码BASCII码C海明码D机内码9、设有一个十阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）A13B33C18D5010、ASCII码的主要作用是（）A便与信息交换B便于信息存储C便于管理D便于输出11、二进制数-0.1101010的补
14、码是（）A、0010101B、10010110C、10010101D、0110101012、国际信息交换码ASCII码的长度为1个字节，其中的最高位为0，因此ASCII码表中的符号有（）个。A、127B、128C、255D、25613、十进制数100的反码和补码表示分别是（）A、9BH和64HB、64H和9BHC、64H和64HD、9BH和9BH14、关于“零”的原码、反码、补码，下列说法正确的是（）A、零的原码表示只有一种B、零的反码表示只有一种C、零的补码表示只有一种D、零的原码、反码、补码表示都有两种四、网络知识1、调制解调器又称为Modem，可用于连结计算机与电话线拨号上网。调制是指（
15、）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邮件传输协
16、议/远程登陆协议C传输控制协议/因特网互联协议D文件传输协议/邮件传输协议7、Intel给我们提供了资源共享、浏览、检索信息和远程登录等多种服务，下面几个选项中用于远程登录的是（）A、TelnetB、E-MailC、TCP/IPD、WWW8、IE是目前流行的浏览器软件，它的工作基础是解释执行用（）语言书写的文件。A、VCB、C+C、HTMLD、HTTP9、计算机网络最大的优点是（）。A、精度高B、资源共享C、运行速度快D、存储容量大E、逻辑判断能力强10、TCP/IP协议共有()层协议A)3B)4C)5D)611、IPv4地址是由()位二进制数码表示的。A)16B)32c)24D)8五、二进制
17、的逻辑运算1、已知A=11001010BB=00001111BC=01011100B,ABC=()B.A、11001110B、01110110C、11101110D、010011002、已知A=35H，A/05H/A/30H的结果是：（）。提示：先化成二进制。A）30HB）05HC）35HD）53H3、假设A=true，B=false，C=true，D=true，逻辑运算表达式ABCD的值是()。A)trueB)falseC)0D)1E)NULL4、逻辑代数式子f=AB+ABC+AB(C+D),则f的简化式子为()。A)ABB)A+BC)ABCD)ABCD5、两个十进制数13与14，将它们进行
18、“与”运算，其值为（）A、27B、12C、15D、116、在Pascal程序中，表达式（200or10）的值是（）。A20B1C220D2027、在Pascal语言中，表达式(23or2xor5)的值是（）A.18B.1C.23D.32六、集合运算1、设全集E=1，2，3，4，5，集合A=1，4，B=1，2，5，C=2，4，则集合（AB）C为（）。A）空集B）1C）3，5D）1，5E）1，3，52、设全集I=a,b,c,d,e,f,g，集合A=a,b,c，B=b,d,e，C=e,f,g，那么集合为（）。A.a,b,c,dB.a,b,d,eC.b,d,eD.b,c,d,eE.d,f,g3、已知集
19、合E=2，请问的所有子集个数是多少？（）)25)10)32)644、设全集E=1,2,3,4,5,集合A=1,2,5,B=1,4,C=2,4，则集合(A+B)*C-(A*B)为（）。A、空集B、1C、2，4D、1，3，5七、数据结构1、已知队列（13，2，11，34，41，77，5，7，18，26，15），第一个进入队列的元素是13，则第五个出队列的元素是（）。A）5B）41C）77D）13E）182、线性表若采用链表存贮结构，要求内存中可用存贮单元地址（）A必须连续B部分地址必须连续C一定不连续D连续不连续均可3、下列叙述中，正确的是（）A 线性表的线性存贮结构优于链表存贮结构B 队列的操作
20、方式是先进后出C 栈的操作方式是先进先出D二维数组是指它的每个数据元素为一个线性表的线性表4、某数列有1000个各不相同的单元，由低至高按序排列；現要对该数列進行二分法检索（binarysearch），在最坏的情況下，需检视（）个单元。A1000B10C100D5005、在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为()A)2B)3C)4D)56、以下哪一个不是栈的基本运算()A)删除栈顶元素B)删除栈底的元素C)判断栈是否为空D)将栈置为空栈7、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5，e6依次通过栈
21、S，一个元素出栈后即进入队列Q，若出队的顺序为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该为（）。A）2B）3C）4D）58、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e2,e4,e3,e6,e5,e1，则栈S的容量至少应该为（）)2)3)4)59、对按关键字排序好的线性表进行二分查找，该线性表适合的存储结构为（）A顺序结构B链接存储C索引存储D散列存储10、在数据结构中，链表是（）A、顺序存储的线性表结构B、非顺序存储的线性表结构C、非顺序存储的非线性结构D、顺序存储的非线性表结构11、在解决计算机
22、主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主要将要输出打印的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个（）结构。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。当从队列中
23、删除一个元素，再加入两个元素后，rear和front的值分别为（）。（A）1和5（B）2和4（C）4和2（D）5和1例3、设循环队列中数组的下标范围是1n，其头尾指针分别为f和r，则其元素个数为（）Ar-fBr-f+1C（r-f）MODn+1D（r-f+n）MODn八、树（详见高级本P108-111）补充作业1、给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA画出此二叉树。2、已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。5种3、一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有()个结点A)2h-
24、1B)2h-1C)2h+1D)h+14、按照二叉数的定义，具有3个结点的二叉树有（）种。A）3B）4C）5D）6（卡特兰数，NOI专刊第3期25页）5、设有一棵k叉树，其中只有度为0和k两种结点，设n0，nk，分别表示度为0和度为k的结点个数，试求出n0和nk之间的关系（n0=数学表达式，数学表达式仅含nk、k和数字）。6、一个高度为h的二叉树最小元素数目是()。A)2h+lB)hC)2h-1D)2hE)2h-l7、一棵含有101个结点的完全二叉树存储在数组A1.101中，对1k101,若Ak是叶子结点，则k的最小值是:()A)51B)50C)49D)488、如果一棵m度树中有n1个度为1的结
25、点，n2个度为2的结点，.有nm个度为m的结点,则该树中叶结点的的个数().A）N1B）M-N1-N2C）N1+2N2+(M-1)NM-1+1D）N2+2N3+(M-1)NM+19、对于一颗二叉树T，设n0、n1、n2分别是度数为0、1、2的顶点数，则下列判断中正确的是（）A、n0=n2+1B、n1=n0+1C、n2=n0+1D、n2=n1+110、一棵n个节点的完全二叉树，则该树的高度h为（）A、n/2B、log(n)C、log(n)/2D、log(n)+1四、图（详见高级本P123-126）运用prim算法和kruskal算法分别画出图1的最小生成树形成的过程。23445712九、排序算法
26、（详见高级本）重要作业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、79B、75、65、73、55、52、79、66、84C、52、84、65、73、55、75、79、66D、52、84、75、73、65、55、79、664、对有18个元素的有序表作二分查找，则查找A
27、3的比较序列的下标为。A、1，2，3B、9，5，2，3C、9，5，3D、9，4，2，35、一个对象序列的排序码为46，79，56，38，40，84，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（）。A38，46，79，56，40，84B38，79，56，46，40，84C40，38，46，56，79，84D38，46，56，79，40，84综合练习1、计算机各部分之间的信息传输是通过总线结构来实现的。总线又分为三部分，下列不是总线三部分的是()A.地址总线B.数据总线C.指令总线D.控制总线2.计算机指令是由一些简单的电信号来控制的。机器指令通常包括()A.地址码、控制码B.
28、控制码、操作码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.无线
29、传输B.光缆C.双绞线D.同轴电缆7、在下列关于计算机算法的说法中，不正确的是（）。A.一个正确的算法至少要有一个输入B.算法的改进，在很大程度上推动了计算机科学与技术的进步C.判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性D.目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法8、线性表（a1,a2,an）以链表方式存储时，访问第i位置元素的时间复杂性为()AO（i）BO（1）CO（n）DO（i-1）9、一个n个顶点的强连通图，至少有多少个有向边()。An-1B（n-1）nC（n-1）n/2Dn10.对有18个元素的有序表作二分查找，则查找A3的比较序
30、列的下标为()。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，310、树形结构中数据元素之间存在（）的关系。A.一对一B.一对多C.多对一D.无法确定11、链表不具有的特点是（）。A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比12、广义表A（a，（a，（a）的深度为（）。A.3B.4C.5D.613、请指出在顺序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找关键码12需做多少次关键码比较。（）A2B.3C.4D.514、一个对象序列的排序码为46，79，56，38，40，84，采用快速排序以位
31、于最左位置的对象为基准而得到的第一次划分结果为（）。A38，46，79，56，40，84B38，79，56，46，40，84C40，38，46，56，79，84D38，46，56，79，40，8415、一数组构造双栈，栈1的栈底在数组的低端，栈2的栈底在数组的高端，如果进栈的序列为A、B、C、D、E，则执行操作栈1进栈、栈2进栈、栈2出栈、栈1出栈、栈2进栈、栈2进栈、栈1进栈、栈2出栈、栈1出栈、栈2出栈后得到的序列为ABAEDCBCEDABCBADECDABCDE16、对于线性表L=（a1，a2，an），下列说法正确的是（）。A、每个元素都有一个直接前驱和一个直接后继B、线性表中至少要有一
32、个元素C、表中所有元素的大小排列顺序必须是由小到大或由大到小D、除第一个和最后一个元素外，每个元素都有且仅有一个直接前驱和一个直接后继17、利用改进的选择排序算法（从小到大）对以下数据（75、84、65、73、55、52、79、66）进行一趟操作的结果是（）。A、52、75、84、65、73、55、66、79B、75、65、73、55、52、79、66、84C、52、84、65、73、55、75、79、66D、52、84、75、73、65、55、79、6618、以下（）不是栈的基本运算？A、删除栈顶元素、删除栈底元素、判断栈是否为空、将栈置为空栈19、将下三角矩阵A18，L8的下三角部分逐行地
33、存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A7，5的地址为。A、1020B、1100C、1080D、112020、两个栈共享一个存储空间的好处是（）。A、节省存储空间，降低上溢发生的机率B、减少存取时间，降低下溢发生的机率C、节省存储时间，降低下溢发生的机率D、减少存取时间，降低上溢发生的机率21、一个递归算法必须包括（）A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分22、以下哪一个不是栈的基本运算（）A、删除栈顶元素B、删除栈底元素C、判断栈是否为空D、将栈置为空栈23、一个对象序列的排序码为46，79，56，38，40，84，采用快速排序以位于最
34、左位置的对象为基准而得到的第一次划分结果为（）。A38，46，79，56，40，84B38，79，56，46，40，84C40，38，46，56，79，84D38，46，56，79，40，8424、线性表L=（a1，a2，an），下列说法正确的是（）。A.每个元素都有一个直接前驱和一个直接后继B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小D.除第一个和最后一个元素外，每个元素都有一个仅有一个直接前驱和直接后继25、一个对象序列的排序码为46，79，56，38，40，84，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（）。A38，46，79，56，
35、40，84B38，79，56，46，40，84C40，38，46，56，79，84D38，46，56，79，40，8426、一棵二叉树如下图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为l，若某结点的下标为i，则其左孩子位于下标2i处、右孩子位于下标2i1处），则该数组的大小至少为（）A6B10C12D1527、为了提高测试的效率，应该()A)随机选取测试数据B)取一切可能的输入数据作为测试数据C)在完成编码以后制定软件的测试计划D)集中对付那些错误群集的程序28、算法的时间复杂度是指()A)执行算法程序所需要的时间B)算法程序的长度C)算法执行过程中所需要的基
36、本运算次数D)算法程序中的指令条数29、树是节点的集合，它的根节点数目是()A)有且只有1B)1或多于1C)0或1D)至少230、在编程时（使用任一种高级语言，不一定是C+或者是PASCAL），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。A)没有区别B)按行读的方式要高一些C)按列读的方式要高一些D)取决于数组的存储方式。31、下列排序算法中，()每一趟都能选出一个元素放在其最终位置上，并且是不稳定的。A)冒泡排序B)希尔排序C)直接选择排序D)直接插入排序32、
37、64KB的存储器用十六进制表示，它的最大的地址码是()A)10000B)FFFFC)1FFFFD)EFFFF33、PC机中CPU进行算术和逻辑运算时，可处理的信息的长度为：()A)32位B)16位C)8位D)都可以34、一棵完全二叉树,如果其上有一个结点的编号为11,则其父结点的编号为().A)22B)12C)10D)535、下面关于主存储器（也称为内存)的叙述中，不正确的是：A)当前正在执行的指令与数据都必须存放在主存储器内，否则处理器不能进行处理B)存储器的读、写操作一次读出或写入一个字节C)字节是主存储器中信息的基本编址单位D)从程序设计的角度来看，cache（高速缓存）也是主存储器36
38、、计算机的主存储器容量达到1GB时，其地址的表示至少需要使用多少个2进位？A)10位B)20位C)30位D)40位37、MIPS是衡量CPU处理速度的一种常用指标，它的含义是：A)每秒钟平均可执行的单字长定点指令的数目B)每秒钟平均可执行指令的数目C)每秒钟平均可执行的浮点指令的数目D)每秒钟平均可执行的算术运算指令的数目38、一幅1024768的彩色图像，其数据量达2.25MB左右，若图像数据没有经过压缩处理，则该图像中的每一个像素是使用多少个二进位表示的？A)8位B)16位C)24位D)32位39、互联网络上的服务都是基于一种协议，WWW服务基于_协议。A）SMIPB）HTTPC）SNMP
39、D）TELNET40、无向图G=(V，E)，其中V=a,b,c,d,e,fE=(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个子集。每个数都恰好属于一个
40、子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为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)1231121131314176511525613、某商店有m种不同颜
41、色的小球且每种小球的数量都足够多。要在这m种不同颜色的小球里挑选出n个小球，设共有s种不同的选法。例如当m=2，n=3时，s等于4，也就是说，共有4种不同的选法。（分别为：【0，3】，【1，2】，【2，1】，【3，0】）。现在，令m=6，n=5，试求出选法数s=_。123451111112234563361015214455664、给出一组顶点（顶点值用A，B，C，D，E，F表示），其对应权值分别为2，3，1，7，8，4。请以A，B，C，D，E，F为叶子顶点构造一棵哈夫曼树，并求出它的最小带权路径长度WPL的值。5、今天是放寒假的最后一天，马上迎来2011年春节，住在同一个宿舍的四名同学为了相
42、互祝愿，每人各设计了一张贺年卡送给别人，为了避免矛盾，他们将贺年卡先集中起来，然后让每人从中拿一张别人送的贺年卡，问四张不同的贺年卡有多少种不同的取法。错排问题8、金中机器人小P由P1，P2，P3，P4，P5，P6六个子部件组成，这些子部件之间有下列关系：P1P2,P1P3,P1P4,P2P3,P2P5,P3P5,P3P6,P4P3,P4P6,P5P6(表示先于关系，如P1P2表示P1子部件完成安装后才能进行子部件P2的安装工作)，请搞信息学竞赛的你告诉金中机器人兴趣小组的同学该如何安装小P。(注意：一个时间段只能安装一个子部件，如果有多种安装方法，只需给出其中一种安装秩序)9、设计法码称重。
43、要求：(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两种结点，设n0，nk，分别表示度为0和度为k的结点个数，试求出n0和nk之间的关系。度之和=nk*k结点数=13