第一章习题

考点一：数据结构基础概念

1. 下列说法中，不正确的是（）。
A. 数据元素是数据的基本单位
B. 数据项是数据元素中不可分割的最小可标识单位
C. 数据可由若干数据元素构成
D. 数据项可由若干数据元素构成

解析：
数据元素（data element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据元素又可称为元素、结点、顶点、记录等。
数据项是数据的不可分割的最小单位。

在这里补充一下：数据、数据对象、数据元素、数据项四者的关系↓

实例说明：

答案：D

2.下列关于数据结构的说法中错误的是（ ）。
A. 数据结构相同，对应的存储结构也相同
B. 数据结构设计数据的逻辑结构、存储结构和施加其上的操作
C. 数据结构操作的实现与存储结构有关
D. 定义逻辑结构时可不考虑存储结构

解析：
首先：存储结构是物理层面的，是数据结构在计算机中的存储表示，比如有顺序存储和链式存储。数据结构包括存储结构，数据的运算，和数据间的逻辑关系（也就是逻辑结构）三方面。
针对A选项：相同的逻辑结构可以用不同的存储结构来实现。由于使用了不同的存储结构，那么在其基础上的基本操作自然是不同的，就比如针对顺序表和链表的插入操作。

答案：A

3. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。
A. 数据的处理方法
B. 数据元素的类型
C. 数据元素之间的关系
D. 数据的存储方法

解析：
数据结构是指相互间存在一种或多种特定关系的数据元素的集合。
数据→具有相同属性的数据元素的集合；
结构→数据元素间存在的一种或多种关系。
对一个给定的数据结构进行分析时，一般从它的逻辑结构、存储结构及对数据元素所进行的操作三个方面进行讨论。

答案：C

考点二：数据结构的逻辑结构

1. 数据的逻辑结构是（ ）关系的整体。
A. 数据元素之间逻辑
B. 数据类型之间
C. 存储结构之间
D. 数据项之间逻辑

解析：
首先明白什么是数据结构，再次回顾一下：
数据→具有相同属性的数据元素的集合；
结构→数据元素间存在的一种或多种关系。
操作的基本单位是数据元素
再次强调一遍：逻辑关系与所使用的计算机无关。

答案：A

2. 下列术语中，（ ）与数据的存储结构无关。

A. 循环队列
B. 堆栈
C. 散列表
D. 单链表

解析：
数据的存储结构有：顺序存储、链式存储、索引存储和散列存储。
A、C、D都指出数据采用的存储结构，循环队列用的是顺序存储，链表用的是链式存储，哈希表用的是散列存储。B选项中的栈是限制了插入删除点的线性表，只是逻辑结构而无关存储结构。

答案：B

3. 下列属于线性结构的是（ ）。
A. 线性表
B. 树
C. 查找
D. 图

解析：
数据的逻辑结构（从逻辑关系上描述数据）可分为线性结构和非线性结构。
线性结构：其特点是数据元素之间存在一对一的线性关系。拥有两种不同的存储结构，即顺序存储结构和链式存储结构。
常用的线性结构有：线性表，栈，队列，双队列，数组，串。
非线性结构：各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生联系。这就是所谓的一对多或者多对一，总之不是一对一。同时也会根据关系的不同，可分为层次结构和群结构。
常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)

答案：A

考点三：数据结构的物理结构

1. 以下哪一组都是物理结构（ ）。

A. 线性表、二叉树

B. 集合、图

C. 单链表、散列表

D. 线性表、散列表

解析：

存储结构就指的是物理结构，数据的存储结构有：顺序存储、链式存储、索引存储和散列存储。

单链表在逻辑结构上划分属于线性结构、在存储结构上为链式存储。散列表就是散列存储。

总结：

答案：C

考点四：算法的基本概念

1. 一个算法具有以下5个重要特性（ ）。

A. 有穷性、确定性、可行性、输入、输出

B. 可行性、可移植性、可扩充性、输入、输出

C. 确定性、有穷性、稳定性、输入、输出

D. 易读性、稳定性、安全性、输入、输出

解析：

这个非常重要：

算法(Algorithm)是对特定的问题的求解步骤的一种描述，是指令的有限序列，其中的每条指令表示一个或者多个操作，此外，一个算法还具有下列5个重要特性：

① 有穷性：一个算法必须总在执行有穷步之后才能够结束，而且每一步都可在有穷时间内完成；

② 确定性：算法当中的每条指令必须有确切的含义，对于相同的输入只能够得出相同的输出；

③ 可行性：算法当中描述的操作都可以通过已经实现的基本运算执行有限次来实现；

④ 输入：一个算法有零个或者多个输入，这些输入取自某个特定的对象的集合；

⑤ 输出：一个算法有一个或者多个输出，这些输出是和输入有着某种特定的关系的量。

答案：A

2. 算法分析的两个主要方面是（ ）。

A. 算法的正确性和可行性

B. 算法的时间复杂度和空间复杂度

C. 算法的有穷性

D. 算法的稳定性和安全性

解析：

算法效率的度量是通过时间复杂度和空间复杂度来描述的。

答案：B

考点五：时间复杂度

1. 单链表中访问当前结点的直接后继结点的时间复杂度为（ ）。

A. O(1)

B. O(n)

C. O(n2)

D. O(logn)

解析：

单链表访问当前结点的直接后继结点的时间复杂度为O(1)，而访问其前驱结点的时间复杂度为O(n)。

因为访问后继结点只是进行一次间接寻址的操作，这个时间是常量，自然是O(1)了，但是通过单链表当前的地址，如果要访问到其前驱，必须要从头开始顺序访问，如果链表的有n个结点，平均时间为O(n)，因此时间复杂度就是O(n)了。

注意：在链表中注意区分是求前驱结点还是后继结点。

答案：A

2. 已知两个长度分别为m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是（ ）

A. O(n) 

B. O(m*n) 

C. O(min(m,n))

D. O(max(m,n))

解析：

两个升序合并为降序，操作是：两数列依次比较放入，其中一个数列结束了，剩下的就不用比了，直接依次放进去。

首先明确，题目让我们求复杂度，这里显然不是讨论移动次数，因为不论什么情况，移动次数都是(m+n)，不需要讨论，所以这里求的是合并过程中的比较次数。

最好的情况，很容易想，就是长度较短的数列中最小的数还比另一个数列最大的数字大，如(7 8 9和 1 2 3 4 )，这种情况需要比较min(m,n)次就好了，复杂度为O(min(mn))。

最差的情况，什么是最差情况，就是比较的次数最多。怎么算呢，要这样想，两个数列移动元素的次数一定是m+n，不可能比这个还多，那么如果每一次移动都需要比较，岂不就是最差情况？但是注意，最后一次移动是一定不需要比较的，因为剩最后一个元素的时候，必然另一个数列已经结束了，所以不用比。故最坏情况比较次数为(m+n -1) 次，，比较次数是 (m+n -1) 次，m和n的次幂都是1，所以复杂度也是1次就行了，那么到底是O(n)还是O(m)呢，肯定选最大的那个啊，因为是最坏情况，故复杂度为O(max(m,n))。

答案：D

考点六：空间复杂度

1. 某算法的空间花费为S(n) = 100nlogn + 0.5n2 + 50n1.5+ 100n + 2000，其空间复杂度为（）。

A. O(n)

B. O(n1.5)

C. O(n2)

D. O(nlogn)

解析：

常用的排序：

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

加法规则是选择最高项作为整个算法的空间复杂度

答案：C

2. 某算法的空间复杂度为O(1)，则（ ）。

A. 该算法执行不需要任何辅助空间

B. 该算法执行所需辅助空间大小与问题规模n无关

C. 该算法执行不需要任何空间

D. 该算法执行所需总空间大小与问题规模n无关

解析：

若算法执行时间所需要的辅助空间相对于数据量来说是个常数，则空间复杂度为，称为原地工作，此时算法所需要的辅助空间是与问题规模n无关的。

答案：B

第二章习题

考点一：

线性表的概念（线性表的定义和特点）

1. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A. 单链表

B. 仅有头指针的单循环链表

C. 双链表

D. 仅有尾指针的单循环链表

解析：

带尾指针的单循环链表，就是单独有一个指针指向最后一个元素，这样最后一个元素和第一个元素的遍历时间复杂度都是O(1)。

其形态如下：

答案：D

2. 下列关于线性表的叙述中，错误的是（ ）。

A. 线性表采用顺序存储，必须占用一片连续的存储单元
B. 线性表采用顺序存储，便于进行插入和删除操作
C. 线性表采用链式存储，不必占用一片连续的存储单元
D. 线性表采用链式存储，便于进行插入和删除操作

解析：

线性表中的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

顺序存储结构的插入与删除：

插入思路：

①、我们首先需要考虑异常（插入位置异常，插入后的长度异常等）

②、从最后一个元素遍历到插入位置，分别将每一个元素向后移动一个位置；

③、插入目标元素，表长加1；

删除思路：

①、我们仍然需要首先考虑异常（删除位置错误等）

②、查找到需要删除的位置，遍历将其后的每一个元素向前进行移动。

显然：平均的时间复杂度为O(n)

总结：

答案：B

3. 下面关于线性表的叙述中，不正确的是（）。

I. 线性表在链式存储时，查找第i个元素的时间同i的值成正比

II. 线性表在链式存储时，查找第i个元素的时间同i的值无关

III. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比

IV. 线性表在顺序存储时，查找第i个元素的时间同i的值无关

A. I、II

B. II、III

C. III、IV

D. I、IV

解析：

线性表的顺序存储和链式存储总结：

当时间复杂度为O(1)时，代表与输入规模n无关，当时间复杂度为O(n)时，代表与输入规模n成正比。

答案：B

考点二：

线性表的分类（顺序表、单链表、双链表、循环链表、静态链表、广义表）

1. 数组A[0…7][0…9]中，每个元素占用3个存储单元，起始存储地址是1000，则数组元素 A[5][3]的存储地址是（ ）。

A. 1126

B. 1141

C. 1156

D. 1159

解析：

在该题中，并没有表明到底是按照行存储还是按照列存储。所以我们需要分别计算：

按行存储：A[5][3]表明该元素前面有5个整行，另外加3个元素：（5×10+3）×3+1000=1159；

按列存储：A[5][3]表明该元素前面有3个整列，另外加5个元素：（3×8+5）×3+1000=1087；

因此对比答案可以发现时D选项。

答案：D

2. 设长度为n的顺序存储线性表，在其任何位置插入或者删除一个元素的概率相等，则删除一个元素时，平均需要移动（ ）个元素。

A. (n+1)/2

B. n/2

C. (n-1)/2

D. (n-2)/2

解析：

这个题需要我们按元素分别考虑，然后找出规律计算：

当第一个元素删除时，其后面的n-1个元素都要前移；第二个元素删除时，其后面的n-2个元素都要前移；以此类推，当最后一个元素被删除时，需要移动的次数是0次，即总的移动次数是：n-1+ n-2+…+0=n(n-1)/2，所以平均移动元素个数为：n(n-1)/2n = (n-1)/2

答案：C

3. 下列选项中，（ ）是链表不具有的特点。

A. 插入和删除运算不需要移动元素

B. 所需要的存储空间与线性表的长度成正比

C. 不必事先估计存储空间大小

D. 可以随机访问表中的任意元素

解析：

链表不能随机存取，只有线性表(数组)既可以随机又可以顺序存取。

答案：D

4. 用单链表方式存储队列（有头尾指针，非循环），在进行删除运算时（ ）。

A. 仅修改头指针

B. 仅修改尾指针

C. 头、尾指针都要修改

D. 头、尾指针可能都要修改

解析：

这种题，我们需要极端考虑：例如当我们删除第一个元素的时候就是需要修改头指针，当我们需要删除嘴都一个元素的时候，就需要修改尾指针。

答案：D

5. 在单链表中，若需在p所指结点之后插入s所指结点，可执行的语句（ ）。

A. s ->next = p; p -> next = s;

B. s ->next = p -> next; p= s;

C. s ->next = p -> next; p -> next = s;

D. p -> next = s; s ->next = p

解析：

在单链表中，锁定某个元素是需要借助其前驱结点来定位的。如果先断开原来的单链表，是没有办法锁定断开之后的元素的，造成元素丢失。

答案：C

6. 设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（ ）。

A. p-> next=s；s-> prior=p；p-> next ->prior=s；s-> prior =p->next；

B. s-> prior=p；s-> next =p-> next；p-> next =s；s-> next ->prior=s；

C. p-> prior=s；p-> next ->prior =s；s->prior=p；s-> next =p-> prior；

D. s-> prior=p；s-> next =p-> next; p-> next ->prior=s；p-> next =s ;

解析：

 A答案的第一步就把s赋值给p的后继指针，你怎么再去寻找p的原先的后继结点?很重要的一点就是先要回收后继结点，这一般是一个原则；B问题处在第三步，p->next = s；你把s赋值给p的后继指针，那么你就丢失了p的后继结点,问题和A相似；C同样和A是一个问题。

本题值得注意的是：防止断链

答案：D

7. 带头结点的单循环链表head为空的判定条件是（ ）。

A. head = = NUL

B. head->next = = NULL

C. head != NULL

D. head->next = =head

解析：

A选项是不带头节点的单循环链表的判断条件；

B选项是带头节点的单链表的判断条件；

答案：D

8. 广义表((a，b)，(( )，(c，d))）的长度是（ ）。

A. 1

B. 4

C. 3

D. 2

解析：

广义表的长度指的是广义表中数据元素的数量。这里需要指明的是，一个广义表中，一个原子算做是一个元素，一个子表也只算做一个元素。比如：空表的长度为 0，只含有一个原子的广义表长度为1。

广义表的深度，指的是广义表中括号的重数。

答案：D

9. 线性表的静态链表存储结构与顺序存储结构相比，优点是（ ）。

A. 所有的操作算法实现简单

B. 便于随机存取

C. 便于插入与删除

D. 便于利用零散的存储器空间

解析：

静态链表就像单向链表，顺序存储可以类比到数组
静态链表的优点：主要是便于数据的增和删等，对于数据交换频繁的地方有所优势

答案：C

考点三：线性表相关大题

1. 设计一个算法实现在单链表中删除值相同的多余结点的算法。

思路图解：

第一轮：

第二轮：

第三轮：

答案：

2. 描述以下三个概念的区别：头指针、头结点、表头结点。

答案：
头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。