通过海量题库、编程比赛和实时排名,系统化提升您的编程能力。
"考研真题" 试卷中 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计算机统考真题在线评测(附答案)
下列关于运算符重载的叙述中,错误的是
若定义int a[]={0,1,2,3,4,5,6,7
有两个关系R和S如下:RA B Ca 1 2b 2 1
软件生命周期是指( )。
下面属于应用软件的是( )。
以下叙述正确的是( )。
有以下程序:程序运行后的输出结果是。
Python软件包自带的集成开发环境是( )。
已知 x= [[1]]*3,那么执行语句x[0][0]
以下哪个语句的运行结果为True。
#编写一个函数,从键盘上输入两个数,求最大公约数和最小
表达式{1,2,3} | {2,3,4}的值为____
下列选项中,磁盘逻辑格式化程序所做的工作是( )。Ⅰ.
将当前目录下的文件man.config 压缩为man.
字符界面下使用shutdown命令重启计算机时所用的参
若下达rmdir命令来删除某个已存在的目录,但无法成功
前台起动的进程使用( )终止。
包含在某些候选码中的属性,称为 。
用二维表来表示实体类型及实体间联系的数据模型称为
当待排序的元素很大时,为了交换元素的位置,移动元素要占
构造连通网最小生成树的两个典型算法是( )
成本估计方法主要有 、 和算法模型估计三种类型
则x的值为_____。
(交朋友)根据社会学研究表明,人们都喜欢找和自己身高相
如果开始时计算机处于小写输入状态,现在有一只小老鼠反复
输入:NOI2016 will be held in
(子矩阵) 给输入一个 n1*m1 的矩阵 a,和 n
主存储器的存取速度比中央处理器 (CPU )的工作速度
输入: 5 4 -6 -11 6 -59 22 -6
输出:_____________
更多选择题
更多填空题
第十章 C++流
第九章 C++模板
第八章 C++运算符重载
C++语言程序设计真题5
C++语言程序设计真题4
C++语言程序设计真题3
C++语言程序设计真题2