2008noip初赛复习题

《2008noip初赛复习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2008NOIP初赛复习题一、单项选择题（每题有且仅有一个正确答案。）1、建立了计算机最主要的结构原理的人是（）。A.图灵B.比尔·盖茨C.冯·诺伊曼D.克拉拉·丹E.哥德尔2、设a、b为两个浮点(float)型变量，下面的表达式中最有可能为真的是（）。A.a=bB.a*a+2*a*b+b*b=(a+b)*(a+b)C.(a+b)*(a-b)+b*b-a*a<0.0001D.a/b=1/(b/a)E.sqrt(a)*sqrt(b)=sqrt(a*b)3、一个三叉树（即每个节点最多有三个孩子）中，有k个孩子的结点数目表示为S(

2、k)，则下列关系一定成立的是（）。A.S(0)=2*S(3)+S(2)-1B.S(0)>3*S(3)+2*S(2)-1C.S(0)<3*S(3)+2*S(2)+1D.S(0)<2*S(3)+S(2)E.S(0)<=3*S(3)+2*S(2)4、佳佳在网上购买了一个空间，建设了一个网站。那么，他向网站上上传网页时最有可能采用的网络协议是（）。A.HTTPB.TCPC.POP3D.FTPE.BT5、一个音乐爱好者收藏有100首MP3格式的音乐，这些音乐的编码率都是192Kbps，平均每首音乐的时长为3min，他要通过网络将这些音

3、乐传送给另一个人，假设网络速度恒定为512KB/s，则他传送这些音乐大概需要（）。A.72sB.843sC.112.5minD.3h48min16sE.超过24小时6、将一台多媒体PC的某个部件拔下来后，仍能正常启动进入Windows，这个部件可能是（）。A.CMOSB.内存C.硬盘D.声卡E.显卡7、中国自主研发的通用CPU“龙芯一号”和“龙芯二号”的问世时间分别是（）。A.2002，2005B.2003，2005C.2002，2004D.2003，2006E.2001，20048、我国研制的曙光5000A超级计算机通过基

4、准程序的测试，其峰值速度约（）A.100亿次　　　B.1000亿次C.10万亿次D.100万亿次9、设待排序的记录为（49，38，65，97，76，13，27,49,55,4），经过下过程将序列排序第一趟：13,27,49,55,4,49,38,65,97,76第二趟：13,4,49,38,27,49,55,65,97,76第三趟：4,13,27,38,49,49,55,65,76,97问它所用的方法是：(A.冒泡排序B.直接选择排序C.直接插入排序D.希尔排序10、设连通图G的顶点数和边数与一立方体相同，即有8个顶点和12

5、条边。任意一棵G的生成树的总边数为（）17A．7　　　B.8C.9D.10　　　E.1111、设有两个散列函数h1(k)=kmod13和h2(k)=kmod11+1，散列表为T[0…12]，用二次散列法解决冲突。函数h1用来计算散列地址，当发生冲突时，h2作为计算下一个探测地址的地址增量。假定某一时刻散列表的状态为：0123456789101112804435下一个被插入的关键码为57，其插入的位置为()。A.4B.5C.6D.7E.8请根据下面是一段PASCAL程序,判断第12、13题。forh:=1ton-1dobegi

6、nx:=A[h+1];k:=h;while(k>=1)and(A[k]>x)dobeginA[k+1]:=A[k];k:=k–1endA[k+1]:=xend12、假设在程序开始执行时，数组A[1…n]是一组随机整数。下列答案中，哪一个最好的描述了最差情况下的程序排序的时间复杂度？（）A.O(nlog2n)B.O(n)C.O(log2n)D.O(n2)E.O(2n)13、假设在程序开始执行时，数组A[1…n]是按关键字非递减有序排列时，下列答案中，哪一个最好的描述了最好情况下的程序排序的时间复杂度？（）A.O(nlog2n)

7、B.O(n)C.O(log2n)D.O(n2)E.O(2n)14、对下列四个序列用快速排序方法进行排序，以序列的第一个元素为划分的基准，在第一趟划分过程中，元素的移动数最多的是哪一个序列（）A.70,65,34,82,53,25,90B.82,53,25,70,65,34,90C.34,25,53,65,90,82,70D.53,25,65,70,34,90,82E.65,34,82,70,25,53,9015、在计算机运行时，把程序和数据一样存放在内存中，这是1946年由_______所领导的研究小组正式提出并论证的。（）

8、A.图灵B.冯·诺依曼C.布尔D.赫夫曼E.哈希16、因特网不属于任何个人，也不属于任何组织。其中在网络知识这一块中有一个英文简写ISP，它的中文意思是（）。A．因特网连接B．因特网使用C．因特网设计D．因特网服务提供者E．信息传输17、Internet给我们提供了资源共享、浏览、检索信息