通过海量题库、编程比赛和实时排名,系统化提升您的编程能力。
"考研真题" 试卷中 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计算机统考真题在线评测(附答案)
下列关于虚函数的说明中,正确的是。
有以下程序执行时输入:1 2 3 <回车>,则输出结果
请编写一个函数fun,它的功能是:找出一堆整型数组元素
下面关于数据库三级模式结构的叙述中,正确的是( )。
下列叙述中正确的是( )。
以下选项中,合法的一组C语言数值常量是。
有以下程序:程序的运行结果是。
以下叙述中错误的是( )。
请在下面程序的横线处填上适当内容,以使程序完整,并使程
表达式long(intVar)也可表示为_______
可以使用内置函数_______查看包含当前作用域内所有
在函数内部可以通过关键字____________未定义
使用del命令或者列表对象的remove( )方法删除
在C语言中,用关键字____________定义单精度
设有一个12×12的对称矩阵M,将其上三角部分的元素m
对于Shell脚本程序,若输入参数数量多于9个,则程序
在数据库的E-R图中,椭圆框表达的是实体集的 。
在SQL中,建立基本表的命令是( )。
排序算法中的比较次数与初始元素序列的排列无关。
下列哪些列类型是数值型的数据( )。
(6 分)已知某排序算法:请回答下列问题。(1)若有
单元测试一般以 测试为主, 测试为辅。
设x和y均为int型变量,则以下for循环中的scan
功能:编写函数fun(int m)求1000以内(不包
将函数funl的入口地址赋给指针变量p的语句是____
某二叉树的中序序列为DCBAEFG,后序序列为DCBG
输入 :15输出 :________
一个人站在坐标(0,0)处,面朝 x 轴正方向。第一轮
中国计算机学会于( )年创办全国青少年计算机程序设计竞
(双栈模拟数组) 只使用两个栈结构 stack1 和
更多选择题
更多填空题
第十章 C++流
第九章 C++模板
第八章 C++运算符重载
C++语言程序设计真题5
C++语言程序设计真题4
C++语言程序设计真题3
C++语言程序设计真题2