2025年初中信息学奥赛模拟试题及及答案.docxVIP

2025年初中信息学奥赛模拟试题及及答案

一、单项选择题（共10题，每题3分，共30分）

1.二进制数101101.101转换为十进制数是（）。

A.45.625B.45.5C.46.625D.46.5

2.以下排序算法中，时间复杂度在最坏情况下为O(n2)且是稳定排序的是（）。

A.快速排序B.冒泡排序C.堆排序D.希尔排序

3.一个栈的输入序列是1,2,3,4,5，不可能的输出序列是（）。

A.5,4,3,2,1B.3,4,5,1,2C.2,3,1,5,4D.1,2,3,4,5

4.一棵完全二叉树有100个节点，其叶子节点的个数是（）。

A.49B.50C.51D.52

5.执行以下伪代码后，输出结果是（）。

```python

n=5

result=0

foriinrange(1,n+1):

forjinrange(i,n+1):

result+=1

print(result)

```

A.10B.15C.20D.25

6.已知字符A的ASCII码是65，字符7的ASCII码是55，则字符C的ASCII码是（）。

A.66B.67C.68D.69

7.对图的深度优先遍历（DFS）和广度优先遍历（BFS），以下说法正确的是（）。

A.DFS使用队列，BFS使用栈

B.DFS适用于寻找最短路径，BFS适用于寻找连通分量

C.两种遍历的时间复杂度均为O(V+E)（V为顶点数，E为边数）

D.遍历结果唯一，与起始点无关

8.递归函数求解问题的核心是（）。

A.定义初始条件和递归关系式B.减少循环次数

C.提高空间复杂度D.避免栈溢出

9.哈希表中解决冲突的方法不包括（）。

A.开放定址法B.链地址法C.再哈希法D.二分查找法

10.以下不属于信息编码方式的是（）。

A.二进制编码B.霍夫曼编码C.十进制编码D.图像压缩编码

二、填空题（共5题，每题4分，共20分）

1.执行以下冒泡排序代码后，数组变为[3,1,4,2]，则原始数组可能是（）（写出一个可能的答案）。

```python

arr=[待排序数组]

n=len(arr)

foriinrange(n1):

forjinrange(ni1):

ifarr[j]arr[j+1]:

arr[j],arr[j+1]=arr[j+1],arr[j]

最终数组：[3,1,4,2]

```

2.递归函数f(n)定义如下：

```python

deff(n):

ifn==0:

return0

elifn==1:

return1

else:

returnf(n1)+2f(n2)

```

则f(5)的值是（）。

3.动态规划求解“最长递增子序列”问题时，状态定义为dp[i]表示以第i个元素结尾的最长递增子序列长度，状态转移方程为（）。

4.字符串s=ababa中，长度为3的回文子串个数是（）（回文子串指正读和反读相同的子串）。

5.有向图中，节点A到B的最短路径长度为5，A到C的最短路径长度为3，C到B的最短路径长度为3，则A到B的最短路径实际应为（）。

三、编程题（共3题，每题20分，共60分）

1.单词频率统计

问题描述：给定一个英文文本字符串，统计其中每个单词的出现频率（大小写不敏感），并排除以下停用词：[a,an,the,and,or,but]。

输入格式：输入一行字符串，包含字母、空格和标点（标点仅包含逗号和句号）。

输出格式：按频率从高到低输出单词及其频率，频率相同则按字典序升序排列；若所有单词均为停用词或无有效单词，输出“None”。

示例输入：

Hello!Thisisacat,andthatisadog.Thedogiscute.

示例输出：

is3

dog2

cat1

cute1

that1

hello1

this1

2.运动会积分统计

问题描述：某学校运动会设有跑步、跳高、跳远三个项目，每个项目的前3名