下载文档原格式
青少年信息学奥林匹克竞赛试题与解析一、选择题（每题3分，共30分）以下关于二进制数的描述，哪一项是错误的？A. 二进制数只有0和1两个数字B. 二进制数的每一位称为比特（bit）C. 二进制数可以直接在计算机中存储和运算D. 二进制数的每一位都代表一个十进制的2的幂次方下列哪个算法的时间复杂度是O(n^2)？A. 冒泡排序B. 选择排序C. 插入排序D. 快速排序（在平均和最坏情况下）在关系型数据库中，以下哪个术语用于描述表与表之间的关系？A. 实体B. 属性C. 关键字D. 外键以下哪项不是计算机网络的基本功能？A. 数据通信B. 资源共享C. 分布式处理D. 数据加密以下哪个算法用于查找无序列表中的元素？A. 二分查找B. 顺序查找C. 插入排序D. 快速排序在面向对象编程中，以下哪个术语用于描述对象的行为？A. 属性B. 方法C. 继承D. 封装以下哪个协议用于在互联网上传输电子邮件？A. FTPB. SMTPC. HTTPD. DNS以下哪个数据结构适用于实现栈？A. 数组B. 链表C. 哈希表D. 二叉树以下哪个术语用于描述计算机程序的指令集合？A. 代码B. 程序C. 算法D. 数据结构以下哪个术语用于描述计算机网络中数据传输的速率？A. 带宽B. 延迟C. 吞吐量D. 丢包率二、填空题（每题4分，共16分）在计算机科学中，__________ 是一种特殊类型的循环，其中循环的每次迭代都依赖于前一次迭代的结果。
在关系型数据库中，__________ 是用于唯一标识表中每一行数据的字段或字段组合。
在计算机网络中，__________ 是指从一个节点发送数据到另一个节点所需的总时间。
在面向对象编程中，__________ 是一种机制，允许一个类继承另一个类的属性和方法。
三、简答题（每题12分，共24分）描述算法的基本组成部分，并解释它们的作用。
解释计算机网络中的TCP/IP协议栈，并说明各层的主要功能。
一、选择题：1. 下面哪个是关系型数据库管理系统（RDBMS）？A. MongoDBB. OracleC. HadoopD. Redis答案：B2. 在面向对象编程中，封装的主要目的是：A. 提高程序的执行效率B. 减少代码的复用性C. 控制类与类之间的依赖关系D. 隐藏实现细节，保护数据的安全性答案：D3. 以下哪种算法不属于常见的排序算法？A. 冒泡排序B. 插入排序C. 快速排序D. 广度优先搜索答案：D4. 下面哪个网络协议主要用于将网页从Web服务器传送到Web浏览器？A. FTPB. HTTPC. SMTPD. SNMP答案：B5. 常用的编程语言C++是基于以下哪种编程语言发展而来的？A. C语言B. JavaC. PythonD. Ruby答案：A二、填空题：1. 在计算机领域中，HTTP是指______________。
答案：超文本传输协议2. 在关系型数据库中，使用的是______________查询语言。
答案：结构化查询语言3. 在计算机网络中，TCP/IP协议簇中的IP是指______________协议。
答案：Internet协议4. 在面向对象编程中，继承可以实现代码的______________。
答案：重用和扩展5. 在计算机科学中，OS是指______________。
答案：操作系统三、简答题：1. 请解释一下什么是数据库索引？答案：数据库索引是一种用于提高数据库查询性能的数据结构。
它通过创建特定的数据结构，来加速对数据库表中数据的查询。
索引会根据指定的列或字段的值来对数据进行排序和组织，使得查询操作可以更快地定位到所需的数据。
索引的创建和维护可能会占用额外的存储空间和计算资源，但可以大大提高查询操作的效率。
2. 请简述面向对象编程的特点和优势。
答案：面向对象编程（OOP）是一种程序设计的范式，其特点包括封装、继承和多态。
面向对象编程的优势包括代码的重用性、可维护性和扩展性。
2023年义乌市小学信息学奥林匹克竞赛试题一、（小学组 pascal语言二小时完毕）姓名:二、单选（每题1.5分共30分）1.与十进制数29等值的二进制数是（A ）A. 11101B.11001C.10111D.110112.右图是一张黑白两色位图, 假如使用0表达白色, 1表达黑色那么这幅黑白两色位置相应的二进制编码为（B ）A. 0100011B.1011100C.1000011D.01000013.上题中的黑白两色位置假如要在计算机内部完整地保存, 在不进行压缩的前提下, 最少需要多少存储空间（C）A.8ByteB.8KBC.8bitD.8MB4.下列计算机设备中, 属于存储设备的是（B）A. 键盘B.RAMC.显示器D.CPU5.下列选项中, 对计算机运营速度的快慢没有影响的是: （D）A. CPUB.内在C.硬盘缓存D.显示器的屏幕尺寸6.下面是计算机操作系统的是（D）A. Free PascalB.Adobe PhotoshopC.Microsoft WordD.Linux7、下列关于计算机病毒的描述中, 对的的是（C）A. 假如某人有感冒病毒, 那么他使用的计算机就有也许感染病毒, 并最终发展为计算机病毒B.假如计算机在生产厂家组装时周边环境不好（有灰尘等）, 计算机就会有计算机病毒C.计算机病毒实质上是一段计算机程序D.计算机病毒只能通过计算机网络传播8、关于网页中的超链接, 下列说法对的的是: （A）A. 超链接的HTML标志是<a>B.一张网页只能包含一个超链接C.将网页保存为文本文献后，超链接仍然存在D.超链接的对象只能是另一张网页。
9、下面列出的文献, 不能用windows附件中画图程序打开的是（C）A. apple.bmpB.banana.jpgC.orange.rawD.pear.png10、关于电子邮件的叙述, 对的的是（B）A. 发送方和接受方必须同时开机才干传送电子邮件B.打开电子邮件的附件也许会传染计算机病毒C.同一个E－Mail帐号不能同时设立在多台计算机上D.发送电子邮件是, 接受方地址不能与发送方相同。
高中信息奥赛试题及答案一、选择题（每题3分，共30分）1. 在计算机科学中，以下哪个选项不是数据结构的基本类型？A. 数组B. 链表C. 堆D. 函数答案：D2. 以下哪个算法的时间复杂度是O(n^2)?A. 归并排序B. 快速排序C. 插入排序D. 选择排序答案：C3. 在关系型数据库中，用于从表中删除数据的SQL语句是？A. SELECTB. INSERTC. UPDATED. DELETE答案：D4. 下列哪种加密算法属于非对称加密算法？A. DESB. AESC. RSAD. MD5答案：C5. 在HTML中，用于创建超链接的标签是？A. <a>B. <link>C. <anchor>D. <hyper>答案：A6. 在编程语言中，以下哪个关键字用于定义一个类？A. functionB. classC. structD. interface答案：B7. 以下哪个选项是正确的二进制数表示？A. 1010B. 1020C. 1102D. 2100答案：A8. 在C++中，以下哪个操作符用于定义友元函数？A. ::B. #C. *D. %答案：A9. 以下哪个选项是正确的HTML文档结构？A. <html><head></head><body></body></html>B. <html><body><head></head></body></html>C. <head><body><html></html></body></head>D. <body><html><head></head></body></html>答案：A10. 在Python中，以下哪个函数用于计算列表中元素的和？A. sum()B. product()C. average()D. count()答案：A二、填空题（每题4分，共20分）1. 在计算机编程中，通常使用_________来表示逻辑上的真值。
第1~10题为基础题，第11~20题为提高题，第21~33为综合题注：因为在本文档中需要用到一些特殊的数学符号（如：求和号、分数等），所以当您在百度文库中浏览时，一些数学符号可能会显示不出来，不过当您把本文档下载下来在本地浏览时，所有的符号即可全部都显示出来。
^_^基础题：【1 Prime Frequency】【问题描述】给出一个仅包含字母和数字（0-9, A-Z 以及a-z）的字符串，请您计算频率（字符出现的次数），并仅报告哪些字符的频率是素数。
输入：输入的第一行给出一个整数T( 0<T<201)，表示测试用例个数。
后面的T行每行给出一个测试用例：一个字母-数字组成的字符串。
字符串的长度是小于2001的一个正整数。
输出：对输入的每个测试用例输出一行，给出一个输出序列号，然后给出在输入的字符串中频率是素数的字符。
这些字符按字母升序排列。
所谓“字母升序”意谓按ASCII 值升序排列。
如果没有字符的频率是素数，输出“empty”（没有引号）。
注：试题来源：Bangladesh National Computer Programming Contest在线测试：UV A 10789提示先离线计算出[2‥2200]的素数筛u[]。
然后每输入一个测试串，以ASCLL码为下标统计各字符的频率p[]，并按照ASCLL码递增的顺序（0≤i≤299）输出频率为素数的字符（即u [p[i]]=1且ASCLL码值为i的字符）。
若没有频率为素数的字符，则输出失败信息。
【2 Twin Primes】【问题描述】双素数（Twin Primes）是形式为(p, p+2)，术语“双素数”由Paul Stäckel (1892-1919)给出，前几个双素数是(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)。
在本题中请你给出第S对双素数，其中S是输入中给出的整数。
信息学奥赛基础测试题及答案1、计算机的基本硬件结构一直沿袭()设计的框架。
A.比尔•；盖茨B.冯•；诺依曼C.布尔D.图灵答案：B 2、下列无符号数中，最小的数是()A.(11011001)2B.(75)10C.(37)8D.(2A)16答案：C 3、在外部设备中，绘图仪属于()A.输入设备B.输出设备C.辅(外)存储器D.主(内)存储器答案：B 4、计算机主机是由CPU与()构成的A.控制器B.输入、输出设备C.运算器D.内存储器答案：D 5、计算机病毒的特点是()A.传播性、潜伏性、易读性与隐蔽性B.破坏性、传播性、潜伏性与安全性C.传播性、潜伏性、破坏性与隐蔽性D.传播性、潜伏性、破坏性与易读性答案：C 6、WINDOWS 9X是一种()操作系统A.单任务字符方式B.单任务图形方式C.多任务字符方式D.多任务图形方式答案：D 7、Internet的规范译名应为()A.英特尔网B.因特网C.万维网D.以太网答案：B 8、计算机网络是一个()系统A.管理信息系统B.管理数据系统C.编译系统D.在协议控制下的多机互连系统答案：D 9、计算机系统总线上传送的信号有()A.地址信号与控制信号B.数据信号、控制信号与地址信号C.控制信号与数据信号D.数据信号与地址信号答案：B 10、计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。
处理器一次能处理的数据量叫字长。
已知64位的奔腾处理器一次能处理64个信息位，相当于()字节。
A.8个B.1个C.16个D.2个答案：A 11、某种计算机的内存容量是640K，这里的640K容量是指()个字节A.640B.640*1000C.640*1024D.640*1024*1024答案：C 12、下面哪些计算机网络不是按覆盖地域划分的()A.局域网B.都市网C.广域网D.星型网答案：D 13、在有N个叶子节点的哈夫曼树中，其节点总数为()A.不确定B.2N-1C.2N+1D.2N答案：B 14、已知数组中A中，每个元素A(I，J)在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。
青少年中学生信息学奥赛试题精选33题(附带题解)第1~10题为基础题，第11~20题为提高题，第21~33为综合题基础题：【1 Prime Frequency】【问题描述】给出一个仅包含字母和数字（0-9, A-Z 以及a-z）的字符串，请您计算频率（字符出现的次数），并仅报告哪些字符的频率是素数。
输入：输入的第一行给出一个整数T( 0<T<201)，表示测试用例个数。
后面的T行每行给出一个测试用例：一个字母-数字组成的字符串。
字符串的长度是小于2001的一个正整数。
输出：对输入的每个测试用例输出一行，给出一个输出序列号，然后给出在输入的字符串中频率是素数的字符。
这些字符按字母升序排列。
所谓“字母升序”意谓按ASCII 值升序排列。
如果没有字符的频率是素数，输出“empty”（没有引号）。
试题来源：Bangladesh National Computer Programming Contest在线测试：UVA 10789提示先离线计算出[2‥2200]的素数筛u[]。
然后每输入一个测试串，以ASCLL码为下标统计各字符的频率p[]，并按照ASCLL码递增的顺序（0≤i≤299）输出频率为素数的字符（即u[p[i]]=1且ASCLL码值为i的字符）。
若没有频率为素数的字符，则输出失败信息。
【2 Twin Primes】【问题描述】双素数（Twin Primes）是形式为(p, p+2)，术语“双素数”由Paul Stäckel (1892-1919)给出，前几个双素数是(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)。
在本题中请你给出第S对双素数，其中S是输入中给出的整数。
输入：输入小于10001行，每行给出一个整数S (1≤ S≤ 100000)，表示双素数对的序列编号。
输入以EOF结束。
输出：对于输入的每一行，输出一行，给出第S对双素数。
信息学奥赛基础知识习题（答案版)一、选择题（下列各题仅有一个正确答案，请将你认为是正确的答案填在相应的横线上）1．我们把计算机硬件系统和软件系统总称为 C 。
（A）计算机CPU （B）固件(C)计算机系统（D）微处理机2．硬件系统是指 D .（A)控制器，运算器 (B）存储器，控制器(C)接口电路，I/O设备 (D）包括(A）、(B）、(C) 3。
计算机软件系统包括 B .A) 操作系统、网络软件 B）系统软件、应用软件C）客户端应用软件、服务器端系统软件 D）操作系统、应用软件和网络软件4．计算机硬件能直接识别和执行的只有 D .（A）高级语言（B)符号语言(C)汇编语言 (D）机器语言5．硬盘工作时应特别注意避免 B .（A）噪声（B）震动 (C）潮湿 (D）日光6．计算机中数据的表示形式是 C 。
(A）八进制 (B)十进制 (C)二进制（D)十六进制7．下列四个不同数制表示的数中，数值最大的是 A .(A）二进制数11011101 （B)八进制数334(C)十进制数219 （D)十六进制数DA 8．Windows 9x操作系统是一个 A 。
(A)单用户多任务操作系统（B)单用户单任务操作系统(C)多用户单任务操作系统（D)多用户多任务操作系统9．局域网中的计算机为了相互通信,必须安装___B__。
（A）调制解调器（B）网卡（C）声卡（D）电视卡10．域名后缀为edu的主页一般属于__A____。
（A）教育机构（B）军事部门（C）政府部门（D）商业组织11。
香港在世界上注册的顶级域名是__A____。
（A）hk（B）cn（C）tw（D)com12．计算机能够自动、准确、快速地按照人们的意图进行运行的最基本思想是（ D )。
(A）采用超大规模集成电路（B）采用CPU作为中央核心部件（C）采用操作系统 (D)存储程序和程序控制13．设桌面上已经有某应用程序的图标，要运行该程序，可以 C 。
（A)用鼠标左键单击该图标 (B)用鼠标右键单击该图标（C）用鼠标左键双击该图标（D）用鼠标右键双击该图标14．若己选定某文件，不能将该文件复制到同一文件夹下的操作是 C 。
信息学奥赛考试题型及答案一、选择题1. 在计算机科学中，以下哪个选项不是数据结构的基本类型？A. 线性结构B. 树形结构C. 图形结构D. 量子结构答案：D2. 以下哪种算法不是排序算法？A. 快速排序B. 归并排序C. 深度优先搜索D. 堆排序答案：C二、填空题1. 在信息学奥赛中，常用的图遍历算法有深度优先搜索（DFS）和______。
答案：广度优先搜索（BFS）2. 哈希表是一种通过______来访问数据的数据结构。
答案：键值对三、简答题1. 描述二分查找算法的基本步骤。
答案：二分查找算法的基本步骤包括：首先确定要查找的元素所在的区间，然后取区间的中间值与目标值进行比较。
如果中间值等于目标值，则查找成功；如果中间值小于目标值，则在区间的右半部分继续查找；如果中间值大于目标值，则在区间的左半部分继续查找。
重复以上步骤，直到找到目标值或区间为空。
2. 解释什么是递归，并给出一个递归算法的例子。
答案：递归是一种在函数中调用自身的编程技巧，用于解决可以分解为相似子问题的问题。
一个递归算法的例子是计算阶乘，即n的阶乘（n!）可以通过递归函数实现：n! = n * (n-1)!，其中基本情况是0! = 1。
四、编程题1. 给定一个整数数组，请编写一个函数，找出数组中第二大的数。
答案：以下是一个可能的解决方案的伪代码：```function findSecondLargest(nums):if length of nums < 2:return nullmax1 = max2 = -∞for num in nums:if num > max1:max2 = max1max1 = numelse if num > max2 and num != max1:max2 = numreturn max2```2. 实现一个函数，判断一个链表是否为回文结构。
答案：以下是一个可能的解决方案的伪代码：```function isPalindrome(head):if head is null or next of head is null:return truefast = slow = headwhile fast and next of fast:fast = next of next of fastslow = next of slowsecondHalf = reverse(slow)while secondHalf:if head.value != secondHalf.value:return falsehead = next of headsecondHalf = next of secondHalfreturn true```注意：以上编程题答案中的伪代码仅供解题思路参考，实际编程语言实现可能有所不同。
第七届全国青少年信息学奥林匹克分区联赛初赛试题一、选择一个正确答案代码(A/B/C/D)，填入每题的括号内(每题 1.5分，多选无分，共30分)1、在计算机内部，一切信息存取、处理和传递的形式是( C )A：ASCⅡ码B：BCD码C：二进制D：十六进制2、在树型目录结构中，不允许两个文件相同主要指的是( D )A：同一个磁盘的不同目录下B：不同磁盘的同一个目录下C：不同磁盘伯不同目录下D：同一个磁盘的同一个目录下3、WORD是一种( B )A：操作系统B：文字处理软件C：多媒体制作软件D：网络浏览器4、计算机软件保护法是用来保护软件( D )的。
A：编写权B：复制权C：使用权D：著作权5、下面关于算法的错误说法是( B )A：算法必须有输出B：算法必须在计算机上用某种语言实现C：算法不一定有输入D：算法必须在有限步执行后能结束6、解释程序的功能是( C )A：将高级语言程序转换为目标程序B：将汇编语言程序转换为目标程序C：解释执行高级语言程序D：解释执行汇编语言程序7、与二进制数101.01011等值的十六进制数为( B )A：A.BB：5.51C：A.51D：5.588、断电后计算机信息依然存在的部件为( C )A：寄存器B：RAM存储器C：ROM存储器D：运算器9、2KB的内存能存储( A )个汉字的机内码A：1024B：516C：2048D：21810、DOS暂驻区中的程序主要是用于( A )A：执行DOS内部命令B：执行DOS外部命令C：执行DOS所有命令D：基本输入输出11、若我们说一个微机的CPU是用的PⅡ300，此处的300确切指的是( A ) A：CPU的主时钟频率B：CPU产品的系列号C：每秒执行300百万条指令D：此种CPU允许最大内存容量12、运算17 MOD 4的结果是( C )A：7B：3C：1D：413、应用软件和系统软件的相互关系是( B )A：后者以前者为基础B：前者以后者为基础C：每一类都以另一类为基础D：每一类都不以另一类为基础14、以下对WINDOWS的叙述中，正确的是( A )A：从软盘上删除文件和文件夹，不送回到回收站B：在同一个文件夹中，可以创建两个同类、同名的文件C：删除了某个应用程序的快捷方式，将删除该应用程序对应的文件D：不能打开两个写字板应用程序15、E-mail邮件本质上是一个( A )A：文件B：电报C：电话D：传真16、计算机病毒是( B )A：通过计算机传播的危害人类健康的一种病毒B：人为制作的能够侵入计算机系统并给计算机带来故障的程序或指令集合C：一种由于计算机元器件老化而产生的对生态环境有害的物质D：利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒17、下列设备哪一项不是计算机输入设备( D )A：鼠标B：扫描仪C：数字化仪D：绘图仪18、在计算机硬件系统中，cache是( D )存储器A：只读B：可编程只读C：可擦可编程只读D：高速缓冲19、在顺序表(2,5,7,10,14,15,18,23,35,41,52)中，用二分法查找12，所需的关键码比较的次数为( C )A：2B：3C：4D：520、若已知一个栈的入栈顺序是1,2,3,…,n，其输出序列为P1,P2,P3,…Pn，若P1是n，则Pi是( C )A：iB：n-iC：n-i+1D：不确定二、问题求解(5+7=12分)1、在a,b,c,d,e,f六件物品中，按下面的条件能选出的物品是： a,b,c,f⑴a,b两样至少有一样⑵a,d不能同时取⑶a,e,f中必须有2样⑷b,c要么都选，要么都不选⑸c,d两样中选一样⑹若d不选，则e也不选2、平面上有三条平行线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一直线上。
信息学奥赛试题及答案信息学奥赛试题一、填空题（共20题，每题1.5分，共计30分。
每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。
1.微型计算机的性能主要取决于（）。
A）内存B）主板C）中央处理器D）硬盘E）显示器2.能将高级语言程序转换为目标程序的是( ).A）调试程序B）解释程序C）编辑程序D）编译程序E）连接程序3．A=B,B=B,C=B,则A∨B∧C=( )A） B） C） D） E)4.计算机设备，既是输入设备，又是输出设备的是( )。
A)键盘B)触摸屏C)扫描仪D)投影仪E)数字化仪5.计较机病毒沾染的需求前提是( )。
A)在内存中运转病毒步伐B)对磁盘举行读写操纵C)在内存中运行含有病毒的可执行程序D)复制文件E)删除文件6．行列(13，2，11，34，4l，77，5，7，18，26，15)，第一个进入行列的元素是13，则第五个出行列的元素是( )。
A)5 B)41 C)77 D)13 E)187.在利用E-mail前，需求对Outlook举行设置，个中ISP 发送电子邮件的效劳器称为( )效劳器。
A)POP3 B)SMTPC)DNS D)FTP E)HTTP8.对给定的整数序列(54,73,21,35,67,78,63,24,89)举行从小到大的排序时,接纳快速排序的第一趟扫描的成效是( ).A)(24,21,35,54,67, 78,63,73,89) B)(24,35,21,54,67, 78,63,73,89)C)(24,21,35,54,67, 63,73,78,89) D)(21,24,35,54,63, 67,73,78,89)E)(24,21,35,54,67, 63,73,78,89)9.编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1，2，3，……,一圈又一圈,问当数到数字n ,所在的纸牌编号为多少?A) n mod 13 B)1+(n-1) mod 13 C)(n+1) mod 13-1 D)(n+1) mod 13 E) (n-1) mod 1310.对下图进行广度优先拓朴排序得到的顶点序列正确的是( ).A) 1,2,3,4,5,6 B) 1,3,2,4,5,6 C) 1,3,2,4,6,5D) 1,2,3,4,6,5, E) 1,3,2,4,5,611.下列属于冯.诺依曼计算机模型的核心思想是( ).A)采用二进制表示数据和指令; B)采用”存储程序”工作方式C)计算机硬件有五大部件(运算器、控制器、存储器、输入和输出设备)D)结构化程序设计方法E)计算机软件只有系统软件12．CPU访问内存的速度比访问下列哪个(些)存储设备要慢( )。
A)寄放器B)硬盘C)软盘D)高速缓存E)光盘13．下列电子邮件地址，哪个(些)是正确的( )。
A)XXXC)162.105.111. 22 D) E)14．数字图象文件能够用以下哪一个(些)软件来编纂( )。
A)画笔(Paintbrush) B)记事簿(Notepad) C)Photoshop D)WmRAR E)MidiSoft15．下列哪个(些)软件不是操作系统软件的名字( )。
A)Windows XP B)DOS C)Linux D)OS／2 E)Arch／Info16.下面关于算法的正确的说法是( )A)算法必需有输出B)算法必需在计较机上用某种言语完成C)算法纷歧定有输入D)算法必需在有限步履行后能竣事E)算法的每步调必需有切实的界说17．以下逻辑运算精确的选项是（）。
A) A·（A + B）= A B) A +（A·B）= AC) A·（B + C）= A·B + A·CD)A +（B·C）=（A + B）·（A + C）E) A+1=A18.下列关于排序说法正确的是( ).A)插入排序、冒泡排序是稳定的B)选择排序的时间复杂性为O(n2)C)选择排序、希尔排序、快速排序、堆排序是不稳定的D)希尔排序、快速排序、堆排序的时间复杂性为O(nlog2n)E)快速排序是速度最快的排序19.关于一个大小为3的栈，若输入行列为，则以下输出行列有大概的是（）。
A) B) C) D) E)20.设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key)=key%13,其中%是求余数运算。
用二次探查法解决冲突,则对于序列(８、31、20、33、18、53、27),则下列说法正确的是( )。
A)27在1号格子中B) 33在6号格子中C) 31在5号格子中D) 20在7号格子中E) 18在4号格子中二.问题求解（5分*2=10分）1.某年级学生共选修6门课程，期末考试前，必须提前将这6门课程考完，每人每天只在下午至多考一门课程，设6门课程分别为c1，c2，c3，c4，c5，c6，S(ci)为研究ci的学生集合。
已知S(ci)∩S(c6)≠Ø，i=l，2，．．．，5，S(ci)∩S(ci+1)≠Ø，i=1，2，3，4，S(c5)∩S(c1)≠Ø ，问至少安排天才能考完这6门课程。
2．设有一棵k*树，其中只有度为和k两种结点，设n0，nk分别表示度为和度为k的结点个数，试求出n0和nk之间的关系(n0=数学表达式，数学表达式仅含nk、k和数字)。
三.阅读程序写出正确的程序运行结果(4 *8分=32分)1 program t1；varn，k，s：longint；beginreadln(n);k:=0；s:=1；while s <= n dobegink:=k+1;n:=n-s;s:=s+6*kend;XXX (k)end.输入:输出:2. program t2;var x,y1,y2,;beginreadln(x);y1:=0;y2:=1;y3:=1;while y2<=x dobeginy1:=y1+1;y3:=y3+2;y2:=y2+y3; end;writeln(y1);end.输人：x＝400输出：3. programt3；var m，n，i，j：integer；p，w，a，b：array[0．．19] of integer；beginread(n)；m：= 0；for i：= 0 to n-1 dobegin read (p[i])；b[i]：=1；end；for i：= 0 to n-1 dobeginif (i>0) thena[m]：= p[i]-p[i-1]elsea[m]：= p[i]；m：= m+1：while ((m>1) and (a[rn-1]=0)) dobegin m；= m-1；b[m]：= l；end；if (m>0) thenw[i]：=b[m-1]elsew[i]：=b[0]；a[m-1]：= a[m-1]-1；for j：= 0 to m-1 do b[j]；= b[j]+1；while ((m>1) and (a[m-1]=0)) dobeginm：= m-1；b[m]：=1；end;end;for i：= 0 to n-1 dobeginwrite(w[i])；write(' ');end；XXX(' ')；end．输入：44 6 6 6输出：4. program t4；constu：array[1．．4] of integer = (0，5，3，1)；v：array[1．．4] 0f integer = (0，7，6，5)；var a，b，c，d，e，f，x，y，z：integer；beginread (a，b，c，d，e，f)；z：= f + e + d + (c+3) div 4；y：= 5 * d + u [ c mod 4 ]；if (b>y) thenbeginz：= z+ (b-y+8) div 9；x：= ((b-y+8) div 9 * 9- (b-y)) * 4+11*e+V[c mod 4]；endelsex：= (y-b) *4+11*e+v[c mod 4]；if (a>x) thenz：= z + (a-x+35) div 36；writeln(z)；end．输入: 4 7 9 20 56 47输出:四.完善程序题(2分+3*4分+2分+4*3分=28分)1．问题描述：工厂在每天的生产中，需要一定数量的零件，同时也可以知道每天生产一个零件的生产单价。
在N天的生产中，当天生产的零件可以满足当天的需要，若当天用不完，可以放到下一天去使用，但要收取每个零件的保管费，不同的天收取的费用也不相同。
题目求解：求得一个N天的出产打算(即N天中天天应出产零件个数)，使总的用度起码。
输入：N(天数N<=29)天天的需求量(N个整数)每天生产零件的单价(N个整数)每天保管零件的单价(N个整数)输出：天天的出产零件个数(N个整数)比方：当N=3时，其需求与用度以下：┌────┬────┬────┬────┐││ 第一天│ 第二天│ 第三天│├────┼────┼────┼────┤│ 需要量│25│15│30│├────┼────┼────┼────┤│生产单价│20│30│32│├────┼────┼────┼────┤│保管单价│5│10││└────┴────┴────┴────┘生产计划的安排可以有许多方案，如下面的三种：┌────┬────┬────┬───────────┐│ 第一天│ 第二天│ 第三天│总的用度│├────┼────┼────┼───────────┤│25│15│30│25*20+15*30+30*32=1910│├────┼────┼────┼───────────┤│40││30│40*20+15*5+30*32=1835 │├────┼────┼────┼───────────┤│70│││70*20+45*5+30*10=1925 │└────┴────┴────┴───────────┘步伐申明：bln]：存放每天的需求量cln]：每天生产零件的单价d[n]：天天保管零件的单价e[n]：生产计划步伐：program exp5;vari,j,n,yu,jO,j1,s:integer;b, c, d, e: array[O..30] of integer;beginreadln(n);for i:=1 to n do readln(b[i] ,c[i] ,d[i]); for i:=1 to n do e[i]:=0;____(1)____:=;c[n+2]:=0;b[n+1]:=0;j=1; while (jO<=n) dobeginyu:=c[jO];j1:=jO;s:=b[jO];while ____(2)____dobegin____(3)____j1:=j1+1;s:=s+b[j1];end;____(4)____j0:=j1+1:end;for i:=1 to n do write(e[I]:4);readln;end.2.问题描述]将一个含有运算符为：(、)、+、-、*、/、^(乘幂运算)、~(求负运算)的中缀表达式，如：((1+2)*5)^2-(3+5)/2转化为后缀表达式，如：12+5*2^35+2/-．[解题思路]将中缀表达式转化为后缀表达式，首先规定运算符的优先数如下：┌───┬───┬───┬─────┬──────┬───┬───┐│运算符│( │) │+，－│*，/│~│~│├───┼───┼───┼─────┼──────┼───┼───┤│优先数│0 │1│2│3│4│5│└───┴───┴───┴─────┴──────┴───┴───┘1．若输入是运算量，则将该运算量输出；2．假如左括号“(”，则将该标记的优先数压入设置的运算符堆栈e[p]中去；3．输入运算符优先数是2，3，4，5时，假如栈空，则将运算符的优先数进栈。
