下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第一章复习题本章重点掌握:基本概念,时间复杂度的计算1. 通常是以算法执行所耗费的(时间)和所占用的(空间)来判断一个算法的优劣。2. 算法具有输入、输出、( 确定性 )、有穷性和可执行性等特性。算法效率的度量分为( 事后统计 )和( 事前分析估算 )。( 事后统计 )主要通过在算法的某些部位插装时间函数来测定算法完成某一规定功能所需的时间。而( 事前分析估算 )不实际运行算法,它是分析算法中语句的执行次数来度量算法的时间复杂性。3. 什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。【解答】通常,定义算法为“对特定问题求解步骤的一种描述,是指令的有限序列。”一个算法应
2、当具有以下特性: 有输入。一个算法必须有0个或多个输入。 有输出。一个算法应有一个或多个输出。 确定性。算法的每一步都应确切地、无歧义地定义。对于每一种情况,需要执行的动作都应严格地、清晰地规定。 有穷性。一个算法无论在什么情况下应在执行有穷步后结束。 可行性。算法和程序不同,程序可以不满足上述的特性(4)。例如,一个操作系统在用户未使用前一直处于“等待”的循环中,直到出现新的用户事件为止。这样的系统可以无休止地运行,直到系统停工。4. ( 数据结构 )由某一数据对象和该对象中各个数据成员间的关系组成。依据所有数据成员之间关系的不同,( 数据结构 )分为两大类:( 线性结构 )和( 非线性结构
3、 )。在( 线性结构 )中的各个数据成员依次排列在一个线性序列中;(非线性结构)的各个数据成员不再保持在一个线性序列中,每个数据成员可能与零个或多个其他数据成员发生联系。根据视点的不同,数据结构分为数据的(逻辑结构)和(存储结构)。(逻辑结构)是面向问题的,(存储结构 )是面向计算机的。5. 判断下列叙述的对错。如果正确,在题前打“Ö”,否则打“´”。 (1) 数据元素是数据的最小单位。´ (应为数据项)(2) 数据结构是数据对象与对象中数据元素之间关系的集合。Ö(3) 数据的逻辑结构是指各数据元素之间的逻辑关系,是用户按使用需要建立的。Ö(4
4、) 算法和程序原则上没有区别,在讨论数据结构时二者是通用的。´ (5) 所谓数据的逻辑结构是指数据元素之间的逻辑关系。Ö(6) 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。´ (数据元素的性质相同)(7) 数据的逻辑结构与数据元素本身的内容和形式无关。Ö(8)从逻辑关系上讲,数据结构主要分为两大类:线性结构和非线性结构。Ö6. 下面程序段的时间复杂度为_C_。for ( int i = 0; i < m; i+ ) for ( int j = 0; j < n; j+ ) aij = i*
5、j;A:O(m2)B:O(n2) C:O(m*n) D:O(m+n)7. 执行下面程序段时,执行S语句的次数为_D_。for ( int i = 1; i <= n; i+ ) for ( int j = 1; j <= i; j+ ) S;A:n2 B:n2/2C:n(n+1)D:n(n+1)/218. 下面算法的时间复杂度为_B_。int f ( unsigned int n ) if ( n=0 | n=1 ) return 1; else return n*f (n-1);A:O(1)B:O(n)C:O(n2)D:O(n!)9. 设n为正整数, 分析下列各程序段中加下划线的语句的程序步数。 (1) for (int i = 1; i <= n; i+) for (int j = 1; j <= n; j+) cij = 0.0; for (int k = 1; k <= n; k+) cij = cij + aik * bkj; (2) x = 0; y = 0; for (int i = 1;
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2023年银川市第二十五中学招聘考试真题
- 房地产居间服务合同格式2024年
- 《电力机车乘务作业》课程教案学习情境1-7 机车乘务员呼唤应答标准用语
- 北流市属事业单位笔试真题
- 江西省重点中学协作体2023-2024学年高一下学期期末联考考试+地理试卷(含答案)
- 房产协议书2024年
- 2024-2030年中国智能卡结算系统行业发展状况与投资效益预测报告
- 电脑维护合同范本2024年
- 涂料产品质量承诺保证书2024年
- 2024-2030年中国普洱茶行业竞争策略与投资效益预测研究报告
- 历史类常识经典考试题100题附参考答案(达标题)
- 第2课《树立科学的世界观》第1框《世界的物质性》-【中职专用】《哲学与人生》同步课堂课件
- (正式版)JBT 9229-2024 剪叉式升降工作平台
- 2023版押品考试题库必考点含答案
- VTE健康宣传手册
- 在比较还原中解读《秋天的怀念》
- 基于S7200PLC的全自动洗衣机控制系统设计毕业设计(论文)
- 证券营销银行驻点工作心得体会与总结
- 心肺听诊知识
- 有理数的加法第一课时说课稿
- XX年面神经炎疗效评价、分析及总结
评论
0/150
提交评论