软件技术基础复习资料

针对计算机软件技术基础复习而编,习题丰富到位,便于掌握。

第一章 算法

【内容】

算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性；

（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。

基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 用平均性态，最坏情况复杂性两种方法来分析算法的工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 【习题】 一、填空题

(1) 算法的复杂度主要包括______复杂度和空间复杂度。答：时间

(2) 算法的基本特征是可行性、确定性、______和拥有足够的情报。答：有穷性

(3) 实现算法所需的存储单元多少和算法的工作量大小分别称为算法的 ______。答：空间复杂度和时间复杂度

(4) 在算法正确的前提下，评价一个算法的两个标准是______。答：时间复杂度和空间复杂度二、选择题

(1) 下面叙述正确的是______。(C) A. 算法的执行效率与数据的存储结构无关

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

C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上三种描述都不对

(2) 算法的时间复杂度是指______。(C)

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

C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数 (3) 算法的空间复杂度是指______。(D) A. 算法程序的长度 B. 算法程序中的指令条数

C. 算法程序所占的存储空间 D. 算法执行过程中所需要的存储空间 (4) 算法一般都可以用哪几种控制结构组合而成______。(D)

A. 循环、分支、递归 B. 顺序、循环、嵌套 C. 循环、递归、选择 D. 顺序、选择、循环(5) 在下列选项中，哪个不是一个算法一般应该具有的基本特征______。(C) A. 确定性 B. 可行性C. 无穷性D. 拥有足够的情报 (6) 在计算机中，算法是指______。(C)

A. 查询方法 B. 加工方法 C. 解题方案的准确而完整的描述 D. 排序方法 (7) 算法分析的目的是______。(D)

A. 找出数据结构的合理性 B. 找出算法中输入和输出之间的关系

C. 分析算法的易懂性和可靠性 D. 分析算法的效率以求改进 (8) 算法的时间复杂度取决于______。(D)

A．问题的规模 B. 待处理数据的初态 C. A和B (9) 算法的计算量的大小称为计算的______。(B) A．效率 B. 复杂性 C. 现实性 D. 难度

(10) 计算机算法指的是（1）______，它必须具备（2）______ 这三个特性。(C) (B) (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 (11)一个算法应该是______。(D)

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. (12)下面关于算法说法错误的是______。 A．算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 (13)下面说法错误的是______。

针对计算机软件技术基础复习而编,习题丰富到位,便于掌握。

(1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B．(1),(2) C．(1),(4) D．(3) 三、简答、计算题

1. 设给定三个整数a，b，c，试写出寻找其中数的一个算法。并放分析在平均情况与最坏情况下，你的算法分别要作多少次比较？ 四、程序设计题

2. 利用减半递推技术，写出求长度为n的数组中最大元素的递归算法。设n=2k，其中K≥1

第二章 基本数据结构及其运算

【内容】

2.1 数据结构的基本基本概念

数据结构研究的三个方面：

（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息；

（2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：

（1）有且只有一个根结点；

（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。 2.2 线性表及其顺序存储结构 2.2.1线性表及其运算

线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表

又称为文件。

非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件；

（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的；

（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

ai的存储地址为：ADR(ai)=ADR(a1) (i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。

顺序表的运算：插入、删除。 （详见14--16页） 2.2.2 栈及其运算

栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。

栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 2.2.3 队列及其运算

队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。 队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。

队列运算包括 …… 此处隐藏：29752字，全部文档内容请下载后查看。喜欢就下载吧 ……