《算法设计与分析》知识点总结

1．算法的渐进时间复杂度分析，能够对给定的代码段（伪代码段）进行时间复杂度分析，能够对用关于问题规模n的函数表示的时间复杂度计算其渐进阶。

2．概念 ：

算法：通俗来讲，算法是指解决问题的方法或者过程，包括输入，输出，确定性，有限性。

1）子问题：结构性质与原问题相似的具有规模更小的问题。

2）可行解：满足某线性规划所有的约束条件（指全部前约束条件和后约束条件）的任意一组决策变量的取值，都称为该线性规划的一个可行解。

3）解空间：若齐次线性方程组有非零解,则其解有无穷多个,而齐次线性方程组所有解的集合构成一个向量空间,这个向量空间就称为解空间.

4）目标函数：指所关心的目标(某一变量)与相关的因素(某些变量)的函数关系。

5）最优解：使某线性规划的目标函数达到最优值（最大值或最小值）的任一可行解，都称为该线性规划的一个最优解。

6）最优化问题：一般是指按照给定的标准在某些约束条件下选取最优的解集，即使系统的某些性质能指标达到最大或最小。

7）递归算法：直接或者间接地调用自身的算法称为递归算法。

8）分治法：将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。递归地求出子问题的解，就可得到原问题的解。

9）动态规划：将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解，与分治法不同的，分解的子问题往往不是互相独立的。（为了避免指数时间，不管子问题的解会不会用到，都会填入到一个表中）

10）最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。（动态规划和贪心都有）

11）重叠子问题性质：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要此子问题时，只是简单地用常数时间查看一下结果。

12）备忘录算法：动态规划方法的变形。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上的。（其控制结构与递归方法是一样的，只是备忘录方法为每一个解过的子问题建立备忘录，以便需要时查看，避免相同子问题的重复求解）

13）贪心法：是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

14）贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。

15）回溯法：是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这

种走不通就退回再走的技术为回溯法。（第二种，以深度优先方式系统搜索问题解的算法称为回溯法）

3.分治法的算法框架

在每一层递归上都有三个步骤：

a,分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。

b，解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。

c,合并：将各子问题的解合并为原问题的解。

DividAndConquer(p(n))//分治法设计原理

{

if (n <= n0)

return Adhoc(p(n));

else

{

//将P分解为较小的子问题P1、P2、…、Pk

Divide p int o smaller subinstances P1, P2, ..., Pk;

for (i=1; i<=k; i++)

yi = DividAndConquer(pi);//递归解决Pi

return Merge(y1, y2, ..., yk);//合并子问题

}

}

4．动态规划的步骤

1）找出最优解的性质，并刻画其结构特征。

2）递归地定义最优值。

3）以自底向上的方式计算出最优值。

4）根据计算最优值时得到的信息，构造最优解。

5．动态规划的基本要素

1）最优子结构性质。

2）子问题重叠性质。

6．贪心法的步骤

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

7．贪心法的基本要素:

贪心选择性质，最优子结构性质。

8．贪心法与动态规划的比较

贪心法就是通过对每一个子问题采取最优决策，最后达到全局最优的一种策略。动态规划也是一种求解最优化问题的算法设计策略，它先求解若干子问题，再根据子问题的解来做出决策，共同点是两者所解决的问题都有很强的步骤性，都要经过各步决策最终得到最优解。区别在于贪心法要求针对问题设计最优度量标准，动态规划则是利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解。

9．备忘录算法与动态规划算法的比较

动态规划算法的最大特性是：局部最优中产生整体最优，具体方法是逐层迭代，从局部开始，一步一步达到整体。

备忘录算法是动态规划方法的变形。与动态规划算法不同的是，备忘录方法的

递归方式是自顶向下的，而动态规划算法则是自底向上的。（其控制结构与递归方法是一样的，只是备忘录方法为每一个解过的子问题建立备忘录，以便需要时查看，避免相同子问题的重复求解）

 

第二篇：计算机知识点总结

///////////////////////////////////////////////////////////////////////////////

计算机总结测试题：

1.计算机从其诞生至今已经经历了四个时代，这种对计算机划时代的原则是根据（ ）。

A）计算机所采用的电子器件（即逻辑元件） B）计算机的运算速度

C）程序设计语言 D）计算机的存储量

2. CAM的含义是（ ）。

A）计算机辅助设计 B）计算机辅助教学

C）计算机辅助制造 D）计算机辅助测试

3. 计算机中的字节是个常用的单位，它的英文名字是（ ）。

A）bit B）Byte C）net D）com

4. 在下列不同进制中的四个数，最小的一个是（ ）。

A）（11011001）二进制 B）（75）十进制

C）（37）八进制 D）（A7）十六进制

5. 要放置10个24×24点阵的汉字字模，需要的存储空间是（ ）。

A）72B B）320B C）720B D）72KB

6．一般计算机硬件系统的主要组成部件有五大部分，下列选项中不属于这五大部分的

事（ ）。

A）运算器 B）软件 C）输入设备和输出设备 D）控制器

7．下列四项中不属于计算机的主要技术指标的是（ ）。

A）字长 B）内存容量 C）重量 D）时钟脉冲

8. 在Windows系统中，打开一个菜单后，其中某菜单项会出现下属级联菜单的标志是

（ ）。

A.菜单项右侧有一组英文提示 B.菜单项右侧有一个黑色三角形

C.菜单项左侧有一个黑色圆点 D.菜单项左侧有一个“J”符号

9. 在Windows系统中快速获得硬件的有关信息可通过（ ）。

A.鼠标右键单击桌面空白区，选择“属性”菜单项

B.鼠标右键单击“开始”菜单

C.鼠标右键单击“我的电脑”，选择“属性”命令

D.鼠标右键单击任务栏空白区，选择“属性”命令

10.在WINDOWS状态下，退出正在运行的应用程序，用户可按( )键。

A.ALT+SHIFT B.ALT+ENTER C.ALT+TAB D.CTRL+ALT+DEL

11.在Windows中进行英文大小写切换的操作是（ ）

A.Space B.Shift C.Esc D.Caps Lock

12.在Windows中进行半角和全角切换的操作是（ ）

A.Ctrl+Space B.Ctrl+Shift C.Shift+Space D.Ctrl+Alt

13.在Windows中只进行中英文切换的操作是（ ）

A.Ctrl+Space B.Ctrl+Shift C.Ctrl+Esc D.Ctrl+Alt

14.在Word的编辑过程中，要将插入点直接移到文档首都，应该按（ ）。

A. End键 B.Ctrl+End键 C.Home键 D.Ctrl+Home键

15.下列关于Word分栏排版功能的叙述中，正确的是（ ）。

A.最多可设三栏 B.各栏的宽度可以不同

C.只能应用于整篇文档 D.各栏之间的间距是固定的

16.在Word文档中，如果对某个段落进行下列设置，其中不属于段落格式的是（ ）。

A.设置为1.5倍行距 B.首行缩进 C.左对齐方式 D.设置为4磅字间

17.在Word文档中，不能选定矩形区域文本的视图方式是（ ）。

A.普通视图 B.页面视图 C.大纲视图 D.全屏幕视图

18.在WORD中，对于邀请函、证书、请柬一类的大量内容相同、只是其中个人信息需

要根据情况添加的大批量文档，均可使用( )来完成。

A.合并记录 B.条件合并 C.邮件合并 D.合并文档

19.在Excel工作表中，工作簿是指（ ）。

A.操作系统 B.不能有若干类型的表格共存的单一电子表格

C.图表 D.在Excel环境中用来存储和处理工作数据的文件

20.在Excel工作表中，把鼠标指向被选中单元格边框，当指针变成箭头时，拖动鼠标

到目标单元格时，将完成（ ）操作。

A.删除 B.移动 C.自动填充 D.复制

21.在Excel工作表中，（ ）操作可以删除工作表D列。

A.单击列号D，按Delete键 B.单击列号D，选择“编辑”菜单下的“删除”

C.单击列号D，选择工具栏上的“剪切”按钮

D.单击列号D，选择“编辑”菜单下的“清除”一“全部”

22.在Excel工作表中，（ ）形式不符合日期格式。

A.“10／15/04” B.15—OCT— 04

C. 20xx／10/15 D.10 —15—04

23.如要改变Excel工作表的打印方向（如横向），可使用（ ）命令。

A.“格式”菜单中的“工作表” B.“文件”菜单中的“打印区域”

C.“文件”菜单中的“页面设置” D.“插入”菜单中的“工作表”

24.数据库系统的数据独立性是指( )

A.不会因为数据的变化而影响应用程序

B.不会因为系统数据存储结构与数据逻辑结构的变化而影响应用程序

C.不会因为数据存储策略的变化而影响数据存储结构

D.不会因为某些数据逻辑结构的变化而影响应用程序

25.以下关于MAC的说法中错误的是（ ）

A.MAC地址在每次启动后都会改变

B.MAC地址一共有48比特，它们从出厂时就被固化在网卡中

C. MAC地址也称做物理地址，或通常所说的计算机的硬件地址

26.IP 协议的核心问题是（ ）

A.传输 B. 寻径 C.封装

27.下列四项中，合法的IP地址是（ ）。

A.190. 220.5 B.206. 53.3.78

C. 206. 53. 312. 78 D.123,43,82,220

28.配置TCP/IP参数的操作主要包括三个方面：（ ）、指定网关和域名服务器地址。

A.指定本机的IP地址及子网掩码 B.指定本机的主机名

C.指定代理服务器 D.指定服务器的IP地址

29. TCP/IP协议是Internet中计算机之间通信所必需共同遵循的一种（ ）。

A.信息资源 B.通信规定 C.软件 D.硬件

30. IP地址能唯一地确定Internet上每台计算机与每个用户的（ ）。

A.距离 B.费用 C.位置 D.时间

31.下面叙述正确的是（ ）

A. 算法的执行效率与数据的存储结构无关

B. 算法的空间复杂度是指算法程序中指令（或语句）的条数（指的是算法所占用的

空间）

C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止

D. 以上三种描述都不对

32.以下数据结构中不属于线性数据结构的是（ ）

A. 队列 B. 线性表 C. 二叉树 D. 栈

33. 在一棵二叉树上第5层的结点数最多是（ ）

A. 8 B. 16 C. 32 D. 15

34.下面描述中，符合结构化程序设计风格的是（ ）

A. 使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑

B. 模块只有一个入口，可以有多个出口(可以有0个入口)

C. 注重提高程序的执行效率 D. 不使用goto语句（只是限制使用）

35.下面概念中，不属于面向对象方法的是（ ）

A. 对象 B. 继承 C. 类 D. 过程调用

36.在结构化方法中，用数据流程图（DFD）作为描述工具的软件开发阶段是（ ）

A. 可行性分析B. 需求分析 C. 详细设计 D. 程序编码

37.在软件开发中，下面任务不属于设计阶段的是（ ）

A. 数据结构设计 B. 给出系统模块结构

C. 定义模块算法 D. 定义需求并建立系统模型

38.数据库系统的核心是（ ）

A. 数据模型 B. 数据库管理系统 C. 软件工具 D. 数据库

39.下列叙述中正确的是（ ）

A. 数据库是一个独立的系统，不需要操作系统的支持

B. 数据库设计是指设计数据库管理系统

C. 数据库技术的根本目标是要解决数据共享的问题

D. 数据库系统中，数据的物理结构必须与逻辑结构一致

40.下列模式中，能够给出数据库物理存储结构与物理存取方法的是（ ）

A. 内模式 B. 外模式 C. 概念模式 D. 逻辑模式

41.算法的时间复杂度是指（ ）

A. 执行算法程序所需要的时间 B. 算法程序的长度

C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数

42.下列叙述中正确的是（ ）

A. 线性表是线性结构 B. 栈与队列是非线性结构

C. 线性链表是非线性结构 D. 二叉树是线性结构

43.结构化程序设计主要强调的是（ ）

A. 程序的规模 B. 程序的易读性 C. 程序的执行效率 D. 程序的可移植性

44.在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段

是（ ）

A. 概要设计 B. 详细设计 C. 可行性分析 D. 需求分析

45.数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下

列图符名标识的图符不属于数据流图合法图符的是（ ）

A. 控制流 B. 加工 C. 数据存储 D. 源和潭

46. 软件需求分析阶段的工作，可以分为四个方面：需求获取、需求分析、编写需求规格说明书以及（ ）

A. 阶段性报告 B. 需求评审 C. 总结 D. 都不正确

47.下述关于数据库系统的叙述中正确的是（ ）

A. 数据库系统减少了数据冗余 B. 数据库系统避免了一切冗余

C. 数据库系统中数据的一致性是指数据类型的一致

D. 数据库系统比文件系统能管理更多的数据

48.关系表中的每一横行称为一个（ ）

A. 元组 B. 字段 C. 属性 D. 码

49.数据库设计包括两个方面的设计内容，它们是（ ）

A. 概念设计和逻辑设计 B. 模式设计和内模式设计

C. 内模式设计和物理设计 D. 结构特性设计和行为特性设计

50.Internet服务提供者的简称是（ ）

A.ASP B.USP C.ISP D.NSP