第2章 数据结构的基本概念
一、 单选题
1.一个数据结构可形象地表示成B=(D,R)，其中D是（①）的有限集合，R是D上的（②）有限集合。
① A）算法 B）数据元素 C）数据操作 D）逻辑结构 ② A）操作 B）映像 C）存储 D）关系
2. 数据结构在计算机存储空间中的存放形式称为（ ）。
A）数据元素之间的关系 B）数据结构
C）数据的存储结构 D）数据的逻辑结构 3. 下列叙述中正确的是（ ）。
A）一个逻辑结构只能有一种存储结构
B）数据逻辑结构属于线性结构，存储结构属于非线性结构
C）一个逻辑结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑结构可以有多种存储结构，且各种存储结构影响数据处理的效率 4. 在数据结构中，与所使用的计算机无关的是数据的（ ）结构。
A）逻辑 B）存储 C）逻辑和存储 D）物理
5. 在存储数据时，通常不仅需要存储各数据元素的值，而且还要存储（ ）。
A）数据的处理方法 B）数据元素的类型 C）数据元素之间的关系 D）数据的存储方法
6. 如果一个非空的数据结构满足两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为（ ）。
A）线性结构 B）非线性结构 C）物理结构 D）逻辑结构
7. 数据的（ ）包括插入、删除、查找、更新、排序等操作类型。
A）存储结构 B）逻辑结构 C）基本运算 D）算法描述 8. 数据的存储结构是指（ ）。
A）数据所占的存储空间 B）数据的逻辑结构在计算机中的表示 C）存储在外存中的数据 D）数据在计算机中的顺序存储方式 9. 在决定选取何种存储结构时，一般不考虑（ ）。
A）结点个数的多少 B）各结点的值如何
C）对数据有哪些运算 D）所用编程语言实现这种结构是否方便 10.以下说法正确的是（ ）。
A）数据元素是数据的最小单位 B）数据项是数据的基本单位
C）数据结构是带结构的各数据项的集合
D）一些表面上很不相同的数据，可以有相同的逻辑结构 11.在数据结构中，从逻辑上可以把数据结构分成（ ）。
A）动态结构和静态结构 B）紧凑结构和非紧凑结构
6
C）线性结构和非线性结构 D）内部结构和外部结构
12.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。
A）数据元素具有同一特点
B）不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C）每个数据元素都一样
D）数据元素所包含的数据项的个数要相等
二、填空题
1.数据的基本单位是 ，数据的最小单位是 。
2. 一种数据的逻辑结构，根据需要可以表示成顺序、 、 和散列四种基本存储结构。
3. 根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据分为 两大类型。
4. 在一个线性结构中插入或删除任何一个结点后还应是 。 5.一种数据结构的元素集合为D，它在D上的二元关系R为： D={a,b,c,d,e,f,g,h}
R={,
6.一种数据结构的元素集合为D，它在D上的二元关系R为： D={a,b,c,d,e,f,g,h}
R={
7.数据的逻辑结构分为线性结构和非线性结构，其中的非线性结构有 两种基本类型。
三、 简答题
1. 数据结构主要研究的三个问题是什么？ 2. 一个数据结构应包含两方面的信息是什么？ 3. 简述数据存储结构中的顺序存储方式。 4. 简述数据存储结构中的链式存储方式
参考答案
一、单选题
1.①B，②D 2. C 3.D 4.A 5.C 6.A 7.C 8.B 9.B 10.D 11.C 12.B 二、填空题
1. 数据元素，数据项 2. 链式、索引 3. 线性结构与非线性结构 4. 线性结构
5. 线性 6.非线性（或树形）
7
7. 树和图 三、简答题
1. 答案：数据结构主要研究的三个问题是：①数据的逻辑结构，②数据的存储结构，③对各种数据结构进行的运算。
2. 答案：一个数据结构应包含两方面的信息：①表示数据元素的信息；②表示各数据元素之间的前后件关系。
3. 答案：在数据的存储结构中，顺序存储方式的含义如下： 顺序存储方式：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里，数据元素之间的逻辑关系由存储单元的邻接关系来体现。
4. 答案：在数据的存储结构中，链式存储方式的含义如下： 链式存储方式：使用指针表示数据元素之间的逻辑关系，各个数据元素的存储位置可以随意，不要求逻辑上相邻的数据元素在物理位置上也相邻。
第3章 线性表及其存储结构
一、 单选题
1. 在一个长度为n的顺序存储的线性表中，向第i个元素（1 ≤i ≤n+1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。
A）n-i B）n–i+1 C）n–i-1 D）i
2. 在一个长度为n的顺序存储的线性表中，删除第i个元素（1 ≤i ≤n+1）时，需要从前向后依次前移（ ）个元素。
A）n-i B）n–i+1 C）n–i-1 D）i
3. 在一个长度为n的顺序表中，存在值为x的元素。在此表中用顺序搜索法，查找值为x的元素，在等概率情况下，查找成功时的平均查找长度为（ ）。
A）n B）n/2 C）(n+1)/2 D）(n - 1)/2
4. 在一个长度为n的顺序表中，删除值为x的元素时，需要比较元素的次数和移动元素次数的和为（ ）。
A）n/2 B）(n+1)/2 C）n D）n+1
5. 在一个顺序表的表尾，插入一个元素时的时间复杂度为（ ）。
A）O(1) B）O(log2n) C）O(n) D）O(n)
6. 在一个顺序表的任意位置，插入一个元素的时间复杂度为（ ）。
A）O(1) B）O(log2n) C）O(n) D）O(n/2)
7. 线性表的顺序存储比链式存储最有利于进行（ ）操作。
A）查找 B）表尾插入或删除 C）按值插入或删除 D）表头插入或删除
8
2
8. 线性表的链式存储比顺序存储最有利于进行（ ）操作。
A）查找 B）表尾插入或删除 C）按值插入或删除 D）表头插入或删除
9. 在一个单链表中，若要在pre所指向的结点之后插入一个新结点，则相继修改（ ）个指针域的值。
A）2 B）1 C）3 D）4
10. 在带表头结点的单链表中，插入一个新结点所用算法的时间复杂度为（ ）。
A）O(1) B）O(log2n)
C）O(n) D）O(n/2)
11.以下关于线性表的链式存储结构的叙述中，正确的是（ ）。
A）存储密度大
B）逻辑上相邻的结点物理上不必相邻
C）可以通过计算直接确定第i个结点的存储地址 D）插入、删除运算操作不方便
12.带头结点的单链表H为空的判定条件是（ ）。
A）H==NULL B）H->next==NULL C）H->next==H D）H!=NULL
13.不带头结点的单链表H为空的判定条件是（ ）。
A）H==NULL B）H->next==NULL C）H->next==H D）H!=NULL
14.在一个带头结点的单链表H中，若要向表头插入一个由指针p指向的新结点，则应执行的操作是（ ）
A）H=p;p->next=H; B）p->next=H;H=p;
C）p->next=H;p=H; D）p->next=H->next; H->next=p; 15.非空的循环单链表H的尾结点（由p所指向）满足（ ）。
A）p==NULL B）p->next==NULL C）p->next==H D）p==H 16.链表不具备的特点是（ ）。
A）插入删除不需要移动元素 B）可随机地访问任一结点 C）不必事先估计存储空间 D）所需空间与其长度成正比
17.设线性表有n个元素，以下算法中，（ ）在顺序表上实现比在链表上实现的效率更高。
A）输出第i（0≤i≤n-1）个元素
B）交换第0个元素与第1个元素的值 C）顺序输出这n个元素的值
D）输出与给定值x相等的元素在线性表中的序号
18.设线性表中有2n个元素，以下算法中，（ ）在单链表上实现要比在顺序表上实现效率更高。
A）删除所有值为X 的元素
B）在最后一个元素的后面插入一个新元素 C）顺序输出前k个元素
D）交换第i个元素和第2n–i-1个元素的值（i = 0，1，?，n-1）
9
二、填空题
1. 在线性表中，第一个结点 前件，其余每个结点有且只有 个前件；最后一个结点 后件，其余每个结点有且只有 个后件。
2. 数据元素在线性表中的位置只取决于它们自己的 。
3. 线性表中结点的个数 n 称为线性表的 。当 n=0时，称为 。 4. 用一维数组存放线性表时，数组的基本类型要与线性表中数据元素的类型 。 5. 线性表的顺序存储结构存在插入、删除操作时需 数据元素的缺点。 6. 线性表的两种存储结构分别是 和 。
7. 线性表的顺序存储结构称为 ；线性表的链式存储结构称为 。 8. 对线性单链表进行插入操作时，没有发生数据元素的 ，只是改变了有关结点的 。
9. 在线性单链表中删除一个元素后，不需要 表中的数据元素，只需改变被删除元素所在结点的 的指针域即可。
10. 在带表头结点的单链表中，查找第i个结点。只能从单链表的 ，沿着结点的 ，直到搜索到第i个结点为止。
11. 在单链表中，若一个元素所在结点的地址为p，则其后继（件）结点的地址为 。 12. 在单链表中，删除指针p所指向结点的后继结点时，需要把 的值赋给p->next指针域。
13. 在单链表中指针p所指结点的后面，插入一个指针q所指的结点时，首先把 的值赋给q->next，然后把 的值赋给p->next。
14. 在一个带表头结点的单链表的表头插入或删除，与在其他位置插入或删除的操作过程是否相同？ 。
15. 在一个不带表头结点的单链表的表头插入或删除，与在其他位置插入或删除的操作过程是否相同？ 。
16. 在双向链表中的每一个结点，包含有两个指针域，一个指向 结点，另一个指向其 结点。
17. 在一个双向链表中，通过一个结点的prior 和 next指针域，能够分别访问到该结点的 和 结点。
18.由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的 。
三、简答题
1. 非空线性表的结构特征是什么？
2．线性表的顺序存储结构具有哪两个基本特点？ 3. 用一维数组存放线性表时，应注意什么？ 4. 简述线性表顺序存储的优点和缺点。 5. 什么是线性表的链式存储结构？
6. 在带头结点的单链表中与在顺序表中，查找与给定元素值item相等的结点的操作有何不同？
7. 带表头结点的循环链表与前面所讨论的单链表相比具有哪两个特点？
四、算法设计
1. 分别编写在顺序表和链表中统计出值为x的元素个数的函数，统计结果由函数值返回。
10