通过海量题库、编程比赛和实时排名,系统化提升您的编程能力。
"考研真题" 试卷中 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计算机统考真题在线评测(附答案)
有如下程序(if-else判断输入字符相关),输入字符
下列情况中,不会调用拷贝构造函数的是。
必须用一对大括号括起来的程序段是。
设二叉树如下:则中序遍历为( )。
数据库的故障恢复一般是由( )来执行恢复。
有以下程序程序的运行结果是( )。
C语言程序中,若函数无返回值,则应该对函数说明的类型是
表达式'%s'%65==str(65)的值为_____
表达式{1,2,3}&{2,3,4}的值为______
给定程序中,函数fun功能是:找出100~999之间
传输介质是通信网络中发送方和接收方之间的 ( ) 通路
在 Linux 系统中,压缩文件后生成后缀为.gz文件
Linux系统有几种类型文件?它们分别是什么?有哪些相
磁盘限额管理可以使用 ______ 软件工具,其中硬限
设计一个shell程序,添加一个新组为class1,然
如何查看一个RPM软件的配置文件的存放位置?
在SELECT子句中用 表示所有字段。
只能用于恢复数据表中数据的命令是
不能激活触发器执行的操作是
FTP工作于
假设输入的n是绝对值不超过1000的整数,完成下面的判
(14分)某机器字长为32位的计算机M,采用请求调页存
某无噪声理想信道带宽为4MHz,采用OAM调制,若该信
一个C程序的执行是从本程序文件的第一个函数开始,到本程
若有以下数组a,数组元素:a[0]~a[9],其值为9
假设变量a、b均为整型,表达式(a=5,b=2,a>b
在主函数中从键盘输入若干个数放入数组中,用0结束输入并
方程a*b = (aorb) *(aandb),在a,
输入:15输出:( )
(交朋友)根据社会学研究表明,人们都喜欢找和自己身高相
更多选择题
更多填空题
第十章 C++流
第九章 C++模板
第八章 C++运算符重载
C++语言程序设计真题5
C++语言程序设计真题4
C++语言程序设计真题3
C++语言程序设计真题2