免费智能真题库 > 历年试卷 > 软件设计师 > 2010年上半年 软件设计师 上午试卷 综合知识
  第64题      
  知识点:   算法分析基础   基本操作
  关键词:   时间复杂度   算法        章/节:   计算机软件知识       

 
若某算法在问题规模为n时,其基本操作的重复次数可由下式表示,则该算法的时间复杂度为(64)。

 
 
  A.  O(n)
 
  B.  O(n2)
 
  C.  O(logn)
 
  D.  O(nlogn)
 
 
 

 
  第65题    2010年下半年  
   43%
(65)不能保证求得0-1背包问题的最优解。
  第16题    2014年下半年  
   45%
模块A、B和C都包含相同的5个语句,这些语句之间没有联系。为了避免重复把这5个语句抽取出来组成一个模块D,则模块D的内聚类型为(..
  第64题    2016年下半年  
   68%
两个矩阵Am*n和Bn*p相乘,用基本的方法进行,则需要的乘法次数为m*n*p。多个矩阵相乘满足结合律,不同的乘..
   知识点讲解    
   · 算法分析基础    · 基本操作
 
       算法分析基础
               时间复杂性
               算法的时间复杂度分析主要是分析算法的运行时间,即算法所执行的基本操作数。即使对相同的输入规模,数据分布不相同也决定了算法执行不同的路径,因此所需要的执行时间也不相同。根据不同的输入,将算法的时间复杂度分为3种情况。
               (1)最佳情况。使算法执行时间最少的输入。一般情况下,不进行算法在最佳情况下的时间复杂度分析。应用最佳情况分析的一个例子是已经证明基于比较的排序算法的时间复杂度下限为Ω(nlgn),那么就不需要白费力气去想方设法将该类算法改进为线性时间复杂度。
               (2)最坏情况。使算法执行时间最多的输入。一般会进行算法在最坏时间复杂度的分析,因为最坏情况是在任何输入下运行时间的一个上限,它提供了一个保障,情况不会比这更糟糕。另外,对于某些算法来说,最坏情况还是相当频繁的。而且大致上看,平均情况通常与最坏情况的时间复杂度一样。
               (3)平均情况。算法的平均运行时间。一般来说,这种情况很难分析。举个简单的例子,现要排序10个不同的整数,输入就有10!种不同的情况,平均情况的时间复杂度要考虑每一种输入及其该输入的概率。平均情况分析可以按以下3个步骤进行。
               ①将所有的输入按其执行时间分类。
               ②确定每类输入发生的概率。
               ③确定每类输入的执行时间。
               下式给出了一般算法在平均情况下的复杂度分析,即
               
               式中,pi为第i类输入发生的概率;ti为第i类输入的执行时间,输入分为m类。
               渐进符号
               渐进符号有以下几种。
               (1)Ο记号。给出一个函数的渐进上界。
               (2)Ω记号。给出一个函数的渐进下界。
               (3)Θ记号。给出一个函数的渐进上界和下界,即渐进确界。
               递归式
               从算法的结构上看,算法可以分为非递归形式和递归形式。非递归算法的时间复杂度分析较简单,本小节主要讨论递归算法的时间复杂度分析方法。
               (1)展开法。将递归式中等式右边的项根据递归式进行替换,称为展开。展开后的项被再次展开,如此下去,直至得到一个求和表达式及其结果。
               (2)代换法。这一名称来源于当归纳假设用较小值时,用所猜测的值代替函数的解。用代换法解递归式时需要两个步骤:猜测解的形式;用数学归纳法找出使解真正有效的常数。
               (3)递归树法。递归树法弥补了代换法猜测困难的缺点,它适于提供"好"的猜测,然后用代换法证明。在递归树中,每一个节点都代表递归函数调用集合中每一个子问题的代价。将树中每一层内的代价相加得到一个每层代价的集合,再将每层的代价相加得到递归式所有层次的总代价。当用递归式表示分治算法的时间复杂度时,递归树的方法尤其有用。
               (4)主方法。也称为主定理,给出求解以下形式的递归式的快速方法,即
               T(n)=aT(n/b)+f(n)
               式中,a≥1和b>1是常数;f(n)是一个渐进的正函数。
 
       基本操作
        Excel基本操作包括工作簿操作和工作表输入与输出。
               工作簿基本操作
               工作簿的基本操作包括新建工作簿、打开工作簿、保存工作簿和关闭工作簿。具体操作方法:选择“文件”→“新建”(或“打开”、“保存”、“关闭”)命令,在弹出的对话框中进行相应操作,单击“确定”按钮。
               工作表输入
               工作簿创建完成后,需要向单元格中输入数据,在Excel 2003的电子表格中,既可以输入数字,也可以输入汉字、英文、标点、特殊符号和公式等(若要输入中文文本,应先转换输入法,用Ctrl+Shift组合键可以改变中文输入法,用Ctrl+Space组合键可以进行中英文转换)。输入的方法有如下三种。
               .单击要输入数据的单元格,输入数据,按Enter键确认。
               .先单击选定单元格,再单击“编辑栏”的内容框,输入数据,通过单击“编辑栏”的输入按钮或取消按钮完成操作。
               .双击要输入数据的单元格,此单元格内会出现插入点,输入数据,按Enter键确认。(此方法主要用于单元格中数据的修改)
                      输入文本。
                      在Excel 2003中的文本是指字符集或数字和字符的组合,默认情况下文本向左对齐。当输入文本过长时,由于列宽所限,往往不能显示所有数据,可在单元格行或列的分界线处双击,Excel会自动调整行高或列宽,以最合适的宽度显示数据。若要在一个单元格内输入多行文本,可按Alt+Enter组合键换行。若要输入数字字符串,如身份证号、电话号码和邮政编码等,要在所输内容前加单引号“'”,以免被系统误认为是数值型数据。
                      输入数字。
                      数值型数据是最常见且最重要的数据类型,默认情况下数字向右对齐。当输入分数时,前面必须加0和空格。例如要输入“3/5”,应输入“0 3/5”,如果直接输入“3/5”,Excel会误认为是日期“3月5日”。输入负数时,可加“-”或()。例如要输入“负5”,可输入“-5”或“(5)”。
                      输入日期和时间。
                      当在单元格中输入系统可识别的时间和日期数据时,单元格的格式会自动转换为相应的“时间”和“日期”格式,无需再次设定,默认情况下向右对齐。输入日期时,用“/”或“-”分隔,如2011年10月1日的输入形式是“11/10/1”或“11-10-1”(也可输入4位年份,如“2011/10/1”)。如要输入当前日期,可按Ctrl+;(分号)。输入时间时,用“:(冒号)”分隔时分秒,有12小时制,也有24小时制,若输12小时制,其后需加空格和A(上午)或P(下午),不加A或P时默认为上午。如要输入下午2:23:45,则输入“14:23:45”或“2:23:45 P”。
                      导入外部数据。
                      Excel 2003的兼容性很强,可以从很多外部来源导入数据,避免重复输入。操作时,先在工作表中选定要导入数据的单元格,再选择“数据”→“导入外部数据”→“导入数据”命令,打开“选取数据源”对话框作进一步设置即可。
                      自动填充数据。
                      在Excel中对具有规律性的数据可采用填充和自动填充的功能,避免逐个手动输入,提高输入效率,减少输入错误。例如在相邻的几个单元格中输入序列数字一、二、三、…,或星期一、星期二、…序列。Excel内置的序列数据有日期序列、时间序列和数值序列,用户可以根据需要创建自定义序列。填充时要注意鼠标的形状,鼠标有三种形状:
                      .(空心十字形):鼠标呈空心十字形,拖曳鼠标的结果是选定区域。
                      .(实心十字形):鼠标呈实心十字形,拖曳鼠标的结果是自动填充。
                      .(空心箭头形):鼠标呈空心箭头形,拖曳鼠标的结果是移动对象。
                      .填充:选中单元格,选择“编辑”→“填充”命令,可按向上填充/向下填充/向左填充/向右填充/序列等方式填充。
                      自动填充:可使用填充柄自动填充数据。填充柄是指活动单元格或单元格区域右下角的黑色四方块。使用时,选中已有数据的单元格,如下图(a)所示的A1。用鼠标拖动填充柄可将已有数据填充至拖动位置复制单元格,如下图(b)所示。如要按序列填充,可在拖动完成后单击拖动区域右下角的“自动填充选项”按钮,选中“以序列方式填充”选项,如下图(c)所示。
                      
                      自动填充
                      自定义序列:选择“工具”→“选项”命令,打开“选项”对话框,选择“自定义序列”选项卡,在“自定义序列”列表框中列出了系统内置的序列,需要时,只要输入第一项后,用鼠标拖动填充柄就可以完成按序列形式填充内容的操作。
                      定义一个新序列:用户可以根据需要定义一个新序列。操作方法是在“输入序列”文本框中依次输入序列内容,并按Enter键分隔各项内容。编辑完新序列后,单击“添加”按钮。也可使用“导入”按钮添加已选定的数据序列。
               格式设置
               对创建好的工作表进行格式设置,包括单元格格式、条件格式和自动套用格式设置。通过设置可使表格更加美观,重点更加突出。
                      单元格格式设置。
                      可以使用“格式”工具栏上的功能按钮完成单元格设置;或者通过选择“格式”→“单元格”命令打开“单元格格式”对话框来完成单元格设置。“单元格格式”对话框中有6个选项卡,其功能如下所述。
                      .“数字”选项卡:可在“分类”列表框中选择数值类型,并对显示格式作进一步设置,如设置小数位数,日期的显示方式等。
                      .“对齐”选项卡:可对单元格中的数据对齐方式、文本方向等进行控制。
                      .“字体”选项卡:可对数据的字体、字型、字号、颜色等进行设置。
                      .“边框”选项卡:可对单元格区域的内、外边框进行设置。操作时,先选择线条的样式和颜色,再选择边框的类型。
                      .“图案”选项卡:可对单元格底纹的颜色和图案进行设置。
                      .“保护”选项卡:可对单元格的保护与隐藏进行设置。但单元格的保护与工作表的保护是联系在一起的,只有工作表处于保护状态时,单元格才能处于保护状态。
                      条件格式设置。
                      设置方法:先选定单元格区域,再选择“格式”→“条件格式”命令,系统显示“条件格式”对话框。设置条件表达式(最多能设置3项条件),并单击“格式”按钮,系统显示“单元格格式”对话框,设置满足条件的数据的显示格式。
                      条件格式设置的作用是根据指定的公式或数值来确定搜索条件,并将格式应用到符合条件的单元格区域中,目的是突出重点数据的显示。例如,在销售业绩表中,将销售业绩最高的单元格底纹设置成“绿色”,销售业绩最小的单元格底纹设置成“灰色”。
                      自动套用格式。
                      设置方法:选中单元格区域,选择“格式”→“自动套用格式”命令,打开“自动套用格式”对话框,选择所需样式。也可单击“选项”按钮,对某一格式作进一步设置。
               工作表的移动和复制
               在同一个工作簿中进行移动和复制工作表的方法有如下两种。
               (1)鼠标拖动法。用鼠标拖动要移动的工作表标签,移到合适的位置释放鼠标即可。复制工作表只要按住Ctrl键,然后拖动鼠标,即可以完成工作表的复制。
               (2)菜单法。选定要移动或复制的工作表,在选定的工作表标签上单击右键,在弹出的快捷菜单中选择“移动或复制工作表”命令,系统弹出“移动或复制工作表”对话框。在此对话框中先选择被移动或复制的工作表要放的位置,再单击“确定”按钮。如果选定对话框下边的“建立副本”复选框,则是复制操作,否则是移动操作。
               若要移动或复制工作表到另一个工作簿,则在选定要移动或复制的工作表后接着打开目标工作簿,然后在“移动或复制工作表”对话框中选择目标工作簿。
               工作表的输出
               在实际工作中,为了便于查看和保存,建立好的工作表往往需要按要求打印出来。完成工作表打印通常进行页面设置和打印范围设置。
               (1)进行打印预览。如果对打印预览的效果不满意,可对工作表重新编辑修改,然后再次进行打印预览,直至满意。
               (2)打印输出。
               由于上述操作方法与Word操作方法一致,故不再赘述。
   题号导航      2010年上半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第64题    在手机中做本题