全国青少年信息学奥林匹克联赛初赛模拟考试（一）

:一、单项选择题（共 15 题，每题 2 分，共计 30 分。每题有且仅有一个正确选项。）

Q1:姓名

Q2:1、世界上公认的第一台电子计算机诞生在（　　）

Q3:2、将（2, 6, 10, 17）分别存储到某个地址区间为 0~10 的哈希表中，如果哈希函数 h(x) = （ ），将不会产生冲突，其中 a mod b 表示 a 除以 b 的余数。

Q4:3、下列二叉树，先序遍历[图片]

Q5:4、一棵二叉树中共有80个叶子结点与70个度为1的结点，则该二叉树中的总结点数为（　　）

Q6:5、假设线性表的长度为n,则在最坏情况下,冒泡排序需要的比较次数为

Q7:6、计算机技术应用广泛，以下属于科学计算方面的是（　　）

Q8:7、冯诺依曼（Von Neumann）在总结研制ENIAC计算机时，提出两个重要的改进是（　　）

Q9:8、如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是 ()

Q10:9、在标准ASCII码表中，英文字母a和A的码值之差的十进制值是（　　）

Q11:10、标准ASCII码字符集有128个不同的字符代码，它所使用的二进制位数是（　　）

Q12:11、十进制数39转换成无符号二进制整数是（　　）

Q13:12、微机中，西文字符所采用的编码是（　　）

Q14:13、下面叙述正确的是

Q15:14、某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（　　）

Q16:15、计算机的存储器中，组成一个字节（Byte）的二进制位（bit）个数是（　　）

:二、阅读程序（判断题正确的填√，错误的填×；除特殊说明外，判断题1.5分，选择题3分，共计40分）

:[图片]

:判断题

Q17:输入浮点数，程序能够得出正确结果

Q18:若将第5行的while( r ) 改为 while ( r != 0 ) 结果不会改变

Q19:若将第15行的函数调用gcd（a,b)改为gcd（b,a)效果相同（）

Q20:若b的输入为0，则程序将会异常结束（）

Q21:5、入数据 10 5，那么输出的结果为（）

Q22:6、若输入数据 10 -3，那么输出结果为（）

:[图片]

Q23:1、以上程序输出的是一个*号等腰三角形（）

Q24:2、若将第9行的j=2*i-1改为 j 2*i 效果相同（）

Q25:3、若将第7，8行代码注释掉，那么会得到一个直角三角形（）

Q26:4、若n的输入过大，图形可能无法得到三角形效果（）

Q27:5、若n=20，那么最长的那行将会有（）个星号。

Q28:6、若第9行的j=2*i-1改为j=i，输入n=10，那么图形总共有（）个星号。

:3、[图片]

Q29:1、如果sum没有初始化，那么结果不确定（）

Q30:2、若将第7行 i=n改成in,结果没有区别（）

Q31:3、若n=10，那么结果为（）。

Q32:4、若n为质数，则结果为（）。

Q33:5、如果i从2开始，i小于n那么，n = 21时结果为多少（）。

Q34:6、如果有m个数要求这个sum，那么请问时间复杂度是多少（）

:三、完善程序（每小题3分，总共30分）

:#include iostreamusing namespace std;int a[16][16];int main(){ int n; cin n; int p = 0,q = n-1; int num = 1; while( p q ) { for(int i = p;i q;i++) { __①__; } for(int i = p;i q;i++) { a[i][q] = num++; } for(int i = q; i p; i--) { __②__; } for(int i = q; i p; i--) { a[i][p] = num++; } __③__ __④__; } if( __⑤__ ) { a[n/2][n/2] = num++; } for( int i = 0; i n; i++) { for( int j = 0; j n; j++) { cout a[i][j] ; } cout endl; } return 0;}

:1、给你一个整数n，按要求输出n∗n的回型矩阵例如：输入：4输出：12 3 412 13 14 511 16 15 610 9 8 7

Q35:1）①处应填（）

:2) ②处应填（）

Q36:A．a[p][i] = num++

Q37:3) ③处应填（）

Q38:4) ④处应填（）

Q39:5) ⑤处应填（）

:2、在大规模数据处理中，经常会遇到的一类问题：在海量数据中找出出现频率最好的前k个数，或者从海量数据中找出最大的前k个数，这类问题通常被称为top K问题。例如，在搜索引擎中，统计搜索最热门的10个查询词；在歌曲库中统计下载最高的前10首歌等。下面的代码是经典的堆排序过程。请补充完整整个程序。

:#include iostream#include algorithmusing namespace std;void heap_adjust(int *arr,int i,int size){ int lchild = 2*i; int rchild = 2*i+1; int max = i; if( i = size/2 ) { if( ① ) { max = lchild; } if( ② ) { max = rchild; } if( ③ ) { swap(arr[i],arr[max]); ④ ; } }}void build_heap(int *arr,int size){ for( int i = size/2;i =1; i--) { heap_adjust(arr,i,size); }}void heap_sort(int *arr,int size){ int i; build_heap(arr,size); for( i = size; i =1; i--) { swap(arr[1],arr[i]); ⑤ ; }}void print_array(int *a,int size){ for(int i = 1; i = size; i++) { cout a[i] ; } cout endl;}int main(){ int n; cin n; int a[n+1]; for( int i = 1; i = n; i++) { cin a[i]; } print_array(a,n); heap_sort(a,n); print_array(a,n); return 0;}

Q40:1）①处应填（）

Q41:2) ②处应填（）

Q42:3) ③处应填（）

Q43:4) ④处应填（）

Q44:5) ⑤处应填（）