1、 1 第 1 章 算法 一、 选择题 1. 算法的时间复杂度是指（ ） 。 A）执行算法程序所需要的时间 B）算法程序中的指令条数 C）算法执行过程中所需要的基本运算次数 D）算法程序的长度 2. 算法的空间复杂度是指（ ） 。 A）算法程序的长度 B）算法程序所占的存储空间 C）算法执行过程中所需要的存储空间 D）算法程序中的指令条数 3.下面（ ）的时间复杂度 最好（即执行时间最短）。 A） O(n ) B） O( n2log ) C） O(n n2log ) D） O(n2) 4.下面累加求和程序段的时间复杂度为（ ） 。 int sum(int a,int n) int i, s=0;
2、 for (i=0;ix) return 1; else return 0; A） O(1 ) B） O( n2log ) C） O(n ) D） O( n ) 8.下面程序段的时间复杂度为（ ） int fun(int n) int i=1,s=1; while(s a2、 a1 = a2、 a1”、“ =”、“ a2) return “; elase if(a1=a2) return “=“; 5 elase return “200) return 0; /数组中数据有错，统计失败 for(j=0;j, 则该数据结构具有 结构。 6.一种数据结构的元素集合为 D， 它 在 D 上 的二元关
3、系 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.
4、非线性（或树形 ） 8 7. 树和图 三、 简答题 1. 答案：数据结构主要研究的三个问题是： 数据的逻辑结 构 ，数据的存储结构，对各种数据结构进行的运算。 2. 答案：一个数据结构应包含两方面的信息：表示数据元素的信息；表示各数据元素之间的前后件关系。 3. 答案： 在数据的存储结构中，顺序存储方式的含义如下： 顺序存储方式：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里，数据元素之间的逻辑关系由存储单元的邻接关系来体现。 4. 答案：在数据的存储结构中，链式存储方式的含义如下： 链式存储方式：使用指针表示数据元素之间的逻辑关系，各个数据元素的存储位置可以随意，不要求逻辑上相邻的数
5、据元素在物理位置上也相邻。 第 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 的 元素，在等概率情况下，查找成功时的平均查
6、找长度为（ ）。 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( n2log ) C） O(n) D） O(n2) 6. 在一个顺序表的任意位置，插入一个元素的时间复杂度为（ ）。 A） O(1) B） O( n2log ) C） O(n) D） O(n/2) 7. 线性表的顺序存储比链式存储最有利于进行（ ）操
7、作。 A）查找 B）表尾插入或删除 C）按值插入或删除 D）表头插入或删除 9 8. 线性表的链式存储比顺序存储最有利于进行（ ）操作。 A）查找 B）表尾插入或删除 C）按值插入或删除 D）表头插入或删除 9. 在一个单链表中，若要在 pre 所指向的结点之后插入一个新结点，则相继修改（ ）个指针域的值。 A） 2 B） 1 C） 3 D） 4 10. 在带表头结点的单链表中，插入一个新结点所用算法的时间复杂度为（ ）。 A） O(1) B） O( n2log ) C） O(n) D） O(n/2) 11.以下关于线性表的链式存储结构的叙述中，正确的是（ ）。 A）存储密度大 B）逻辑上相邻
8、的结点物理上不必相邻 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=
9、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（ 0in-1）个元素 B）交换第 0 个元素与第 1 个元素的值 C）顺序输出这 n 个元素的值 D）输出与给定值 x 相等
10、的元素在线性表中的序号 18.设线性表中有 2n 个元素，以下算法中，（ ）在单链表上实现要比在顺序表上实现效率更高。 A）删除所有值为 X 的元素 B）在最后一个元素的后面 插入一个新元素 C）顺序输出前 k 个元素 D）交换第 i 个元素和第 2n i-1 个元素的值（ i = 0， 1， n-1） 10 二、 填空题 1. 在线性表中，第一个结点 前件，其余每个结点有且只有 个前件；最后一个结点 后件，其余每个结点有且只有 个后件。 2. 数据元素在线性表中的位置只取决于它们自己的 。 3. 线性表中结点的个数 n 称为线性表的 。当 n=0 时，称为 。 4. 用一维数组存放线性表时，
11、数组的基本类型要与 线性表中数据元素的类型 。 5. 线 性表的顺序存储结构存在插入、删除操作时需 数据元素的缺点。 6. 线性表的两种存储结构分别是 和 。 7. 线性表的顺序存储结构称为 ；线性表的链式存储结构称为 。 8. 对线性单链表进行插入操作时，没有发生数据元素的 ，只是改变了有关结点的 。 9. 在线性单链表中删除一个元素后，不需要 表中的数据元素，只需改变 被删除元素 所在结点的 的指针域即可。 10. 在带表头结点的单链表中，查找第 i 个结点。只能从单链表的 ，沿着结点的 ，直到搜索到第 i 个结点为止。 11. 在单链表中，若一个元素所在结点的地址为 p，则其后继（件）结
12、点的地址为 。 12. 在单链表中，删除指针 p 所指向结点的后继结点时，需要把 的值赋给p-next 指针域。 13. 在单链表中指针 p所指结点的后面，插入一个指针 q所指的结点时，首先把 的值赋给 q-next，然 后把 的值赋给 p-next。 14. 在一个带表头 结点的单链表的表头插入或删除，与在其他位置插入或删除的操作过程 是否相同？ 。 15. 在一个不带表头结点的单链表的表头插入或删除，与在其他位置插入或删除的操作过程是否相同？ 。 16. 在双向链表中的每一个结点，包含有两个指针域，一个指向 结点，另一个指向其 结点。 17. 在一个双向链表中，通过一个结点的 prior
13、和 next 指针域，能够分别访问到该结点的 和 结点。 18.由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的 。 三、 简答题 1. 非空线性表的结构特征是什么？ 2 线 性表的顺序存储结构具有哪两个基本特点？ 3. 用一维数组存放线性表时，应注意什么？ 4. 简述线性表顺序存储的优点和缺点。 5. 什么是线性表的链式存储结构？ 6. 在 带 头结点的单链表中与在顺序表中，查找与给定元素值 item 相等的结点的 操作有何不同 ？ 7. 带 表头结点的循环链表与前 面所讨论的单链表相比 具有哪两个特点 ？ 四 、 算法设计 1. 分别编写在顺序表和链表中统计出值为 x的元素个数 的函数 ，统计结果由函数值返回。
