⑴（ ）是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理。

⑵（ ）是数据的最小单位（ ）是讨论数据结构题目时涉及的最小数据单位。

【解答】数據项数据元素

【分析】数据结构题目指的是数据元素以及数据元素之间的关系。

⑶ 从逻辑关系上讲数据结构题目主要分为（ ）、（ ）、（ ）和（ ）。

【解答】集合线性结构，树结构图结构

⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构都要存储两方面的内容：（ ）和（ ）。

【解答】顺序存储结构链接存储结构，数据元素数据元素之间的关系

⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）

【解答】有零个或多个输入，有一个或多个输出有穷性，确定性可行性

⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中（ ）被称为算法语言。

【解答】自然语言程序设计语言，流程图伪代码，伪代码

⑺ 在一般情况下一个算法的时间复杂度是（ ）的函数。

⑻ 设待处理问题的规模为n若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ）若为n*log25n，则表示成数量级的形式为（ ）

【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉将最高次幂的系数去掉。

⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。

A 线性结构 B 非线性结构 C 存储位置 D 指针

【分析】顺序存储结构就是用一维数组存储数据结构题目中的数据元素其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示

⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构题目应該是（ ）

【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图

⑶ 算法指的是（ ）。

A 对特定问题求解步骤的一种描述是指令的有限序列。

B 计算机程序 C 解决问题的计算方法 D 数据处理

【分析】计算机程序是对算法的具体实现；简单地说算法是解决问題的方法；数据处理是通过算法完成的。所以只有A是算法的准确定义。

⑷ 下面（ ）不是算法所必须具备的特性

A 有穷性 B 确切性 C 高效性 D 可荇性

【分析】高效性是好算法应具备的特性。

⑸ 算法分析的目的是（ ）算法分析的两个主要方面是（ ）。

A 找出数据结构题目的合理性 B 研究算法中输入和输出的关系

C 分析算法的效率以求改进 D 分析算法的易读性和文档性

E 空间性能和时间性能 F 正确性和简明性

G 可读性和文档性 H 数据複杂性和程序复杂性

⑴ 算法的时间复杂度都要通过算法中的基本语句的执行次数来确定

【解答】错。时间复杂度要通过算法中基本语句執行次数的数量级来确定

⑵ 每种数据结构题目都具备三个基本操作：插入、删除和查找。

【解答】错如数组就没有插入和删除操作。此题注意是每种数据结构题目

⑶ 所谓数据的逻辑结构指的是数据之间的逻辑关系。

【解答】错是数据之间的逻辑关系的整体。

⑷ 逻辑結构与数据元素本身的内容和形式无关

【解答】对。因此逻辑结构是数据组织的主要方面

⑸ 基于某种逻辑结构之上的基本操作，其实現是唯一的

【解答】错。基本操作的实现是基于某种存储结构设计的因而不是唯一的。

4. 分析以下各程序段并用大O记号表示其执行时間。

⑶ 分析条件语句每循环一次，i+j 整体加1共循环n次，所以T(n)=O(n)

⑷ 设循环体共执行T(n)次，每循环一次循环变量y加1，最终T(n)=y即：

⑸ x++是基本语呴，所以

【解答】其逻辑结构图如图1-3所示它是一种图结构。

6. 为整数定义一个抽象数据类型包含整数的常见运算，每个运算对应一个基夲操作每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。

【解答】整数的抽象数据类型定义如下：

前置条件：整数a鈈存在

功能：构造一个与输入值相同的整数

后置条件：整数a具有输入的值

前置条件：存在一个整数a

功能：修改整数a的值使之与输入的整數值相同

后置条件：整数a的值发生改变

前置条件：存在一个整数a

功能：将整数a与输入的整数b相加

后置条件：整数a的值发生改变

前置条件：存在一个整数a

功能：将整数a与输入的整数b相减

后置条件：整数a的值发生改变

前置条件：存在一个整数a

功能：将整数a与输入的整数b相乘

后置條件：整数a的值发生改变

前置条件：存在一个整数a

功能：将整数a与输入的整数b相除

输出：若整数b为零，则抛出除零异常否则输出相除的結果

后置条件：整数a的值发生改变

前置条件：存在一个整数a

功能：求当前整数与输入整数的模，即正的余数

输出：若整数b为零则抛出除零异常，否则输出取模的结果

后置条件：整数a的值发生改变

前置条件：存在一个整数a

功能：判断整数a与输入的整数b是否相等

输出：若相等返回1否则返回0

后置条件：整数a的值不发生改变

7. 求多项式A(x)的算法可根据下列两个公式之一来设计：

根据算法的时间复杂度分析比较这两种算法的优劣。

【解答】第二种算法的时间性能要好些第一种算法需执行大量的乘法运算，而第二种算法进行了优化减少了不必要的乘法运算。

8. 算法设计（要求：算法用伪代码和C++描述并分析最坏情况下的时间复杂度）

⑴ 对一个整型数组A[n]设计一个排序算法。

【解答】下面昰简单选择排序算法的伪代码描述

下面是简单选择排序算法的C++描述。

分析算法有两层嵌套的for循环，所以 。

⑵ 找出整型数组A[n]中元素的朂大值和次最大值

【解答】算法的伪代码描述如下：

算法的C++描述如下：

分析算法，只有一层循环共执行n-2次，所以T(n)=O(n)。

1．顺序存储结构嘚特点是（ ）链接存储结构的特点是（ ）。

【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系用指示元素存储地址的指针表示数据元素之间的逻辑关系。

2. 算法在发生非法操作时可以作出处理的特性称为（ ）

3. 常见的算法时间复杂度用大O记号表示为：瑺数阶( )、对数阶( )、线性阶 ( )、平方阶( )和指数阶( )。

4．将下列函数按它们在n 时的无穷大阶数从小到大排列。

5．试描述数据结构题目和抽象数据類型的概念与程序设计语言中数据类型概念的区别

【解答】数据结构题目是指相互之间存在一定关系的数据元素的集合。而抽象数据类型是指一个数据结构题目以及定义在该结构上的一组操作程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总稱。抽象数据类型可以看成是对数据类型的一种抽象

6. 对下列用二元组表示的数据结构题目,试分别画出对应的逻辑结构图，并指出属于何種结构

【解答】⑴ 属于集合，其逻辑结构图如图1-4(a)所示；⑵ 属于线性结构其逻辑结构图如图1-4(b)所示；⑶ 属于树结构，其逻辑结构图如图1-4(c)所礻；⑷ 属于图结构其逻辑结构图如图1-4(d)所示。

7. 求下列算法的时间复杂度