通过海量题库、编程比赛和实时排名,系统化提升您的编程能力。
"考研真题" 试卷中 2022年考研408计算机统考真题在线评测(附答案) 中有题目如下:
第1题
(10 分)现有 n(n>100000)个数保存在一维数组 M 中,需要在查找 M 中最小的 10 个数。 请回答下列问题。
(1)设计一个完成上述查找任务的算法,要求平均情况下的比较次数尽可能少,简述其算法 思想(不要程序实现)。
(2)说明你所设计的算法平均情况下的时间复杂度和空间复杂度。
【答案解析】
(1)算法思想
【答案一】
定义含 10 个元素的数组 A,元素值均为该数组类型能表示的最大数 MAX。
for M 中的每个元素 s
if(s<A[9]) 丢弃 A[9]并将 s 按升序插入 A 中;
当数据全部扫描完毕,数组 A 中保存的就是最小的 10 个数。
【答案二】
定义含 10 个元素的大根堆 H,元素值均为该堆元素类型能表示的最大数 MAX。
if(s<H 的堆顶元素)删除堆顶元素并将 s 插入 H 中;
当数据全部扫描完毕,堆 H 中保存的就是最小的 10 个数。
(2)算法平均情况下的时间复杂度是 O(n),空间复杂度是 O(1)
所属试卷:2022年考研408计算机统考真题在线评测(附答案)
(读者自行创建,注意每行第一个逗号后面有空格),其内容
函数fun功能是:将a、b中的两个两位正整数合并形成一
给定程序MODI1.C中函数fun的功能是:读入一个字
以下函数按每行8个输出数组中的数据:下划线处应填入的语
有以下程序:程序运行后的输出结果是。
以下关于C语言的叙述中正确的是。
有如下程序:执行这个程序输出“#”号的个数为( )。
以下程序的输出结果是( )。
Python内置函数___________用来打开或创
Python标准库os.path中用来分割指定路径中的
表达式{1,2,3} | {2,3,4}的值为____
下面程序的功能是将二维数组a中的每个元素向右移一列,最
若有说明int a[3][4];,则对a数组元素的正确
以下C程序运行结果是( )。(注:□表示空格)
函数rewind(fp)的作用是( )。
将前一个命令的标准输出作为后一个命令的标准输入,称之为
在/root文件夹下查找后缀为.cpp的文件。答:fi
安装Linux系统对硬盘分区时,必须有两种分区类型:
Linux系统使用cat命令时,使用哪个选项显示行号
下列说法错误的是( )
(7 分)下表给出了整型信号量 S 的 wait和
若多个进程共享同一个文件F ,则下列叙述中,正确的是
输入整型变量a的值:
定义int x[5],n;则x=x+n;或x++;都是
定义int a[2][3];,表示数组a中的元素个数是
在8位二进制补码中,10101011表示的数是十进制下
输入: 16输出: ______________
LZW 编码是一种自适应词典编码。在编码的过程中,开始
一个自然数在十进制下有 n位,则它在二进制下的位数与
在参加NOI系列竞赛过程中,下面哪一种行为是不被严格禁
更多选择题
更多填空题
计算机二级Python语言程序设计模拟试卷
Python第三方库
2025年考研408计算机统考真题在线评测(附答案)
Python标准库
Python函数
Python文件
Python组合数据类型