2020-10-24

1. 可以用（D）定义一个完整的数据结构
2. 数据元素
3. 数据对象
4. 数据关系
5. 抽象数据类型

解析：抽象数据类型（ADT）描述了数据的逻辑结构和抽象运算，通常用数据对象，数据关系，基本操作集这样的三元组来表示，从而构成一个完整的数据结构定义。

B项数据对象和C项数据关系都是ADT（抽象数据类型）三元组的一部分。

A项数据元素是B项数据对象的一部分。

数据项：一个数据元素由若干数据项组成

数据元素：组成数据对象的基本单位

数据对象：性质相同的数据元素的集合（类似于数组）

1. 以下数据结构中，（A）是非线性数据结构。
2. 树
3. 字符串
4. 队列
5. 栈

解析：数和图是典型的非线性数据结构，其它选项都属于线性数据结构。

线性结构是一个有序数据元素的集合。

常见的线性结构有：线性表，栈，队列，双队列，数组，串

常见的非线性结构有：二维数组，多维数组，广义表，树（二叉树等），图

线性结构的特点是数据元素之间存在一对一的线性对应关系

1. 以下数据逻辑结构的是（C）
2. 顺序表
3. 哈希表
4. 有序表
5. 单链表

解析：有序表使用的时候只关注逻辑结构，而其他三个选项是即知道物理结构，也知道逻辑结构。

1. 链式存储设计时，节点内的存储单元地址（A）
2. 一定连续
3. 一定不连续
4. 不一定连续
5. 部分连续，部分不连续

解析：此处问的是节点内的存储单元，所以一定是连续的，而不是结点间的，结点间的存储是以指针的形式指向下一个结点，所以不一定是连续的。

1. 以下与数据的存储结构无关的术语是（D）
2. 循环队列
3. 链表
4. 哈希表
5. 栈

解析：数据的存储结构：顺序存储，链式存储，索引存储和散列存储

1. 循环队列本身是用数据表（存储）表示的队列（逻辑）。易错选项。注意题目说法是与存储结构无关的是”，而不是“不是存储结构的是”

B,C：链表、哈希表，都是存储结构，链表是链式存储，哈希表是散列存储。

D：栈，逻辑结构。既可以链式存储，也可以顺序存储，与存储结构无关。

1. 以下关于数据结构的说法中，正确的是（A）
2. 数据的逻辑结构独立于其存储结构。
3. 数据的存储结构独立于逻辑结构
4. 数据的逻辑结构唯一决定了其存储结构
5. 数据结构仅由其逻辑结构和存储结构决定

解析：A中，数据的逻辑结构是以面向实际问题的角度出发的，只采用抽象表达方式，独立于存储结构。

B中，数据的存储结构是逻辑结构在计算机上的映射，它不能独立于逻辑结构而存在。

C中，满二叉树（逻辑上是一棵树）既可以用顺序存储方式存储，亦可以用链式存储结构存储。

D中，数据结构包括三个要素（逻辑结构，存储结构，数据运算），缺一不可。

逻辑结构有四种基本类型：集合结构，线性结构，树状结构和网络结构

两种基本的存储结构：顺序存储结构和链式存储结构。

1. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（C）
2. 数据的操作方法
3. 数据元素的类型
4. 数据元素之间的关系
5. 数据的存取方法

解析：抽象数据类型（ADT）=（数据对象，数据关系，基本操作集），其中，前两个为数据存储的时候所需要的。整个ADT分为两大部分，一个数据，一个是操作。

在存储数据时，不仅要存储数据元素的值，还要存储数据元素之间的关系。

A中，存储数据时无需存储操作方法，存储数据结构时才需要这样。

B中，数据元素的类型隐含与数据元素之中，不需要额外存储。

D中，数据的存取方法是A中操作方法的一部分。（存取操作）

1. 对于两种不同的数据结构，逻辑结构或物理结构一定不相同吗？

答：对于两种不同的数据结构，逻辑结构或物理结构不一定相同

分析：数据结构的三要素：逻辑结构、存储结构、数据运算

因此，两种不同的数据结构，逻辑结构与物理结构可以不同（正常情况下）；

也可以相同（数据运算不同，逻辑结构与物理结构不同也称为两种数据结构）

例子：二叉树与二叉排序树，两种不同的数据结构。

二者均可以使用二叉树的逻辑结构和物理结构

但是建立树、插入结点、删除结点和查找结点等数据运算是不同的。

1. 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。

分析：存储方式分为顺序存储和链式存储

所以举一个例子分别为顺序存储和链式存储，对其进行插入或删除操作。

其中，对于顺序存储，插入指定位置需要元素后移，同理删除也需要元素前移（这里指中间位置，不考虑最好的情况）

而对于链式存储，无论是最好情况还是最坏情况，对于结点的插入或删除都只需要修改指针即可。

由此可见运算效率的不同。

分析：第一层for循环，i从n-1~1,也可以写成1~n-1

      第二层for循环，j从1~i

随着i的增大，j循环的次数也会增多，所以我们可以用递推法算出

当n=2时，j循环的次数为0

当n=3时，j循环的次数为1~2

当n=4时，j循环的次数为1~3

所以一直递推下去就为：0+1+2+3+4+……+n=n(n-1)/2

得到时间复杂度为O(n^2)

分析：从for语句进行分析：

第一个for语句中：i从1~n

第二个for语句中：j从1~2i

所以看第二个for语句的执行次数，为：

2i=1*2+2*2+3*2+……=2（1+2+……+n）2[n(n+1)/2]=n(n+1)

1. 下面说法错误的是（B）
2. 算法原地工作的含义是指不需要任何额外的辅助空间
3. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
4. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
5. 同一个算法，实现语言的级别越高，执行效率就越低
6. （1）
7. （1）（2）
8. （1）（4）
9. （3）

解析：算法原地工作：O(1),常数个辅助空间

算法优于算法，程序的执行时间特例不构成反例

计算机是一门严谨的学科，以最负责的角度思考问题即可

有过争议，大致理解，记住结论

答案：B

解析：看while循环，n>=(x+1)^2  可以看成n>=x^2,所以x的循环就是逐步变成根号n,逐渐加一，所以对于x的复杂度数量级也是根号n.

分析：若n=1,都为常数1，故不用看，看n>1的情况：T（n）=2T(n/2)+n,继续写下去

第一个：O(n)

第二个:O(n^1/2)

第三个：O(n^3)

第四个：O(nm)

1. 一个算法应该是（B）
2. 程序
3. 问题求解步骤的描述
4. 要满足五个基本特性
5. A和C

解析：算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，能够对一定规范的输入，在有限时间内获得所要求的输出。

程序不一定满足有穷性，如死循环、操作系统等，而算法必须有穷。算法代表了对问题求解步骤的描述，而程序则是算法在计算机上的特定的实现。

A程序：程序是一组计算机能识别和执行的指令，运行于电子计算机上，满足人们某种需求的信息化工具。程序是一个指令序列。

C：算法的定义（什么是算法）和算法的特性（算法怎么样）是不同的方面，注意区分。

算法的五个基本特性：（1）有穷性（2）确定性（3）可行性（4）输入（5）输出

1. 某算法的时间复杂度为O(n^2),表明该算法的（C）
2. 问题规模是n^2
3. 执行时间等于n^2
4. 执行时间与n^2成正比
5. 问题规模与n^2成正比

解析：问题的时间复杂度：O(F(n))意味着在任何情况下，规模为n的前提下，所花费的时间<=K*F(n),其中K是与n无关的常数。

1. 问题规模是n，与具体的表达式无关
2. 执行时间为<=Kn^2,这里的时间复杂度一般为最坏时间复杂度。
3. 没问题。常数K的意义就在于成正比。
4. 问题规模是默认为n，所以选项中问题规模有关的选项逗号判断。

分析：时间复杂度的经典问题。给定问题规模n,判断核心操作的次数

本题中，核心操作：i=i*2,判断此步的运算次数。

提问：从1开始，一直乘2，乘多少次是N呢？

转化：2的几次方是N呢？2^X=N   X=log2 N

得出：log2 n(以2为底n的对数)

解析：读程序：x在不断地*2，最终的限制条件是x<n/2.

X=2*2*2*2*……一直乘到达到n/2为止。

但是其实乘到n/2和乘到n只差了1次，是可以忽略的常数，因此当作n来看就行。

转化：X=2*2*2……，乘多少次2达到n?答：log2 n以2为底n的对数，然后实际次数是要-1的，但依然是O(log2 n)的时间复杂度。

分析：读程序：其实就是个递归。

而整个程序的基础操作只有递归处的乘法。

一次递归是一次乘法运算(return处)，而值为n的情况下递归嵌套n次。

那么值为n,n次嵌套递归，一次递归就是一次乘法，所以值为n是n次乘法。时间复杂度就是O(n).

1. 已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（D）
2. O(n)
3. O(mn)
4. O(min(m,n))
5. O(max(m,n))

解析：基础题。有几点变化：

①变成降序，与变成升序无异，只需在合并新链表的时候使用头插法即可。

②问的是时间复杂度。原题是问的最坏情况下比较次数，是m+n-1.(M1~m-1N1~nMm)

那么m+n-1的时间复杂度是多少？是O(max(m,n)).

2max(m,n)>m+n-1,而2作为常数省略掉。

1. 下列程序段的时间复杂度是（C）

Count=0;

For(k=1;k<=n;k*=2)

   For(j=1;j<=n;j++)

        Count++;

1. O(log2n)【以2为底n的对数】
2. O(n)
3. O(nlog2n)
4. O(n^2)

解析：基础操作：count++.

第一层：k的取值分别是1,2,4,8,16……一直到n为止，log2n次循环

第二层：无论k的取值是多少，第二层都是自加n次。

那么一共自加的次数就是nlog2n次。