第一章 一．判断题
（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。
（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。 （×）（3）数据元素是数据的最小单位。 （×）（4）数据项是数据的基本单位。
（×）（5）数据的逻辑结构和数据的存储结构是相同的。
（√）（6）数据的逻辑结构是各数据元素之间的逻辑关系，是用户按使用需要而建立的。 （√）（7）数据的物理结构是指数据在计算机内实际的存储形式。
（√）（8）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（9）数据的存储结构是数据的逻辑结构的存储映像。 （√）（10）算法是对解题方法和步骤的描述。
二．填空题
1．数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的 关系 和运算的学科。
2．数据的存储结构形式包括：顺序存储、链式存储、 散列存储 、索引存储 。 3．数据结构按逻辑结构可分为两大类，它们分别是：线性结构和 非线性 结构。 4．一个算法的空间复杂度是指该算法所耗费的 存储空间 ，它是该算法求解问题规模n的函数。
5．数据结构有逻辑结构和 存储结构 两种结构。
6．数据的存储结构形式包括：顺序存储、链式存储、散列存储、 索引存储 。 7．一个算法的效率可分为 时间 效率和空间效率。 8．数据元素是数据的 基本单位 。
9．数据结构主要研究数据的 逻辑结构 、存储结构和算法。 11．数据的 逻辑结构 是独立于计算机的。
12．数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的 关系 的有限集合。
13．树形结构结构中的元素之间存在 一对多 的关系。
14．若一个算法中的语句频度之和为T（n）=125n+3nlog2n，则算法的时间复杂度为 O（nlog2n） 。
15．数据结构主要研究数据的逻辑结构、 存储结构 和算法。
三．选择题
1．数据结构通常是研究数据的（ A ）及它们之间的相互联系。
A. 存储结构和逻辑结构 B. 存储和抽象 C. 联系和抽象 D. 联系与逻辑 2．执行下列语句的时间复杂度为：（ B ）。
s=0;
for (i=1;i<=n; i++) s=s+i;
A. O（1） B. O（n） C. O（n2） D. O（n3） 3．数据结构中，在逻辑上可以把数据结构分成：（ C ）。
A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 4．某程序的时间复杂度为（3n+log2n+n2+15）其数量级表示为（ B ）
A. O（n） B. O（n2） C. O（log2n） D. O（nlog2n） 5．非线性结构的数据元素之间存在（ B ）。 A. 一对多关系 A. O（1）
B. 多对多关系 C. 多对一关系 D. 一对一关系 B. O（ n） C. O（log2n） D. O（n2）
6．下列时间复杂度中最坏的是（ D ）
7．以下任何两个结点之间都没有逻辑关系的是（ D ）
A. 图型结构 B. 线性结构 C. 树型结构 D. 集合 8．链接存储的存储结构所占存储空间（ A ）。
A． 分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针 B． 只有一部分，存放结点值
C． 只有一部分，存储表示结点间关系的指针
D． 分两部分，一部分存放结点值，另一部分存放结点所占单元素 9．一个存储结点存放一个（ B ）
A. 数据项 B. 数据元素 C. 数据结构 D. 数据类型 10．下列时间复杂度中最好的是（ A ） A. O（1） 储方式
A. 顺序 B. 链式 12．下列算法的实际复杂度是（ D ） for (i=0;i A. O（1） B. O（ n） C. O（log2n） D. O（n2） 13．数据元素是数据的基本单位，其内（ B ）数据项。 A. 只能包括一个 B. 可以包括多个 C. 不包括 D. 可以包括也可以不包括 14. 数据结构中，与所使用的计算机无关的是数据的（ C ）结构； A. 存储 B. 物理 C. 逻辑 D. 物理和存储 15．数据的逻辑结构是（ A ）关系的整体 A. 数据元素之间逻辑 B. 数据项之间逻辑 C. 数据类型之间 D. 存储结构之间 C. 索引 D. 散列 B. O（ n） C. O（log2n） D. O（n2） 11．每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（ B ）存 第二章 一．判断题 （×）（1）链表的物理存储结构具有同链表一样的顺序。 （×）（2）链表的每个结点都恰好包含一个指针域。 （√）（3）线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。 （×）（4）链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 （×）（5）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （√）（6）数组元素的存储位置是下标的线性函数。 （√）（7）在单链表中，元素的存储位置用指针联系，所以可以从头结点开始查找任何一个元素。 （×）（8）顺序存储线性表的插入和删除操作不需要付出很大的代价，因为平均每次移动仅一半的元素。 （×）（9）顺序存储方式的优点是存储密度大，插入、删除效率高。 （×）（10）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。 二．填空题 1．顺序表中逻辑上相邻的元素在物理位置上 必须 相连。 2．在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为 O (n) 。 3．线性表是n个结点的 有限 集合。 4．链表相对于顺序表的优点有 插入、删除 方便；缺点是存储密度小。 5．链表相对于顺序表的优点有插入、删除方便；缺点是存储密度 小 。 6．顺序表相对于链表的优点是： 节省存储 和随机存取。 7．对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是 O（1） 。 8．在链表中逻辑上相邻的元素的物理位置 不必 相连。 9．线性表中第一个结点没有直接前趋，称为 开始 结点。 10．在顺序表中访问任意一个结点的时间复杂度均为 O (1) 。 11．在n个结点的单链表中要删除已知结点*P，其时间复杂度为 O (1) 。 12．在单链表中需知道 头指针 才能遍历整个链表。 13．在一个单链表中，在指针p所指向的结点之后插入指针s所指向的结点时，应执行s->next=p->next和p->next=s 操作。 14．在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移 n- i +1 个元素。 15．在双向链表中，每个结点都有两个指针域，它们一个指向其前趋结点，另一个指向其 后继 结点。 三．选择题 1．用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是（ B ）。 A． 当前结点所在地址域 B． 指针域 A．遍历链表和求链表的第i个结点 C．删除开始结点 C． 空指针域 D． 空闲域 2．在具有n个结点的单链表中，实现（ A ）的操作，其算法的时间复杂度都是O（n）。 B．在地址为P的结点之后插入一个结点 D．删除地址为P的结点的后继结点 3．设a，b，c为三个结点，p，10，20，代表地址，则如下存储结构称为（ B ）。 P a 10 b 20 c ^ A． 循环链表 B． 单链表 C．双向循环链表 D． 双向链表 4．已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址B，则第i个结点的地址为（ A ）。 A． B+(i-1)*m B．B+i*m C． B-i*m D． B+(i+1)*m D． 不能确定 5．单链表的存储密度（ C ）。 A． 大于1 B． 等于1 C．小于1 6．在n个结点的顺序表中，算法的时间复杂度是O (1)的操作是（ A ）。 A． 访问第i个结点(1<=i<-n)和求第i个结点的直接前驱(2<=i<=n) B． 在第i个结点之后插入一个新结点(1<=i<=n) C． 删除第i个结点(1<=i<=n) D． 将n个结点从小到大排序 7．在线性表中（ B ）只有一个直接前驱和一个直接后继。 A．首元素 B． 中间元素 A．P= = L C．尾元素 D．所有元素 8．指针P指向循环链表L的首元素的条件是（ D ）。 B．L->next= = P C．P->next= = NULL D．P->next= = L 9．一维数组和线性表的区别是（ A ）。 A． 前者长度固定，后者长度可变 B． 后者长度固定，前者长度可变 C． 两者长度都固定 D． 两者长度都可变 10．指针P所指的元素是双循环链表L的尾元素的条件是（ D ）。 A．P= = L B．P->prori= = L C．P= = NULL D．P->next= =L 11．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ） A．110 B．108 C．100 D．120 12．两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（ ）。 A．P->next= =Q->next B．P->next= = Q C．Q->next= = P D．P= = Q 13．向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ B ）个元素。 A．8 B．63.5 C．63 D．7 14．用链表存储的线性表，其优点是（ C ）。 A． 便于随机存取 B． 花费的存储空间比顺序表少 C． 便于插入和删除 D． 数据元素的物理顺序与逻辑顺序相同 15．单链表的示意图如下： L A B C P Q R 指向链表Q结点的后继的指针是（ D ） A．L B．P D Λ C．Q D．R 第三章 一．判断题 （√）（1）大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两种基本操作。 （×）（2）快速排序在任何情况下都比其它排序方法速度快。 （√）（3）快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。 （×）（4）如果某种排序算法不稳定，则该排序方法就没有实际应用价值。 （√）（5）对n个记录的进行快速排序，所需要的平均时间是O（nlog2n）。 （×）（6）冒泡排序是不稳定的排序。 （√）（7）冒泡排序的时间复杂度是O（n2）。 （×）（8）堆排序所需的时间与待排序的记录个数无关。 （√）（9）对快速排序来说，初始序列为正序或反序都是最坏情况。 （√）（10）对于n个记录的集合进行归并排序，所需的平均时间为O (nlog2n)。 二．填空题 1． 根据被处理的数据在计算机中使用不同的存储设备，排序可分为： 内排序 和外排序。 2． 评价排序算法优劣的主要标准是 时间复杂性 和算法所需的附加空间。 3．插入排序、堆排序、归并排序中，排序是不稳定的有： 堆排序 。 4．在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 3 次。 5．对n个关键字进行冒泡排序，其可能的最小比较次数为： n-1 次。 6．内排序是指整个排序过程，全部在计算机的 内存 中进行。 7．大多数排序算法都有两个基本的操作： 比较 和移动。 8．在插入排序和选择排序中，若初始数据基本正序，则选用 插入排序 较好。 9．在排序前，关键字值相等的不同记录，排序后相对位置变化的排序方法，称为 不稳定 的排序方法。