数据结构习题及答案

1第 1章 算法一、选择题1. 算法的时间复杂度是指（ ） 。A）执行算法程序所需要的时间 B）算法程序中的指令条数C）算法执行过程中所需要的基本运算次数D）算法程序的长度2. 算法的空间复杂度是指（ ） 。A）算法程序的长度 B）算法程序所占的存储空间C）算法执行过程中所需要的存储空间 D）算法程序中的指令条数3.下面（ ）的时间复杂度最好（即执行时间最短） 。A）O(n ) B）O( ) n2logC）O(n ) D）O(n 2)n2log4.下面累加求和程序段的时间复杂度为（ ） 。int sum(int a,int n) int i, s=0;for (i=0;ix) return 1;else return 0;A）O(1 ) B）O( ) n2logC）O(n ) D）O( ) 8.下面程序段的时间复杂度为（ ）int fun(int n)int i=1,s=1;while(s a2、a1 = a2、a1” 、 “=”、 “a2)return “;elase if(a1=a2)5return “=“;elase return “200)return 0; /数组中数据有错，统计失败for(j=0;j,则该数据结构具有 结构。6.一种数据结构的元素集合为 D，它在 D上的二元关系 R为：D=a,b,c,d,e,f,g,hR=,则该数据结构具有 结构。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.非线性（或树形）87. 树和图三、简答题1. 答案：数据结构主要研究的三个问题是：数据的逻辑结构，数据的存储结构，对各种数据结构进行的运算。2. 答案：一个数据结构应包含两方面的信息：表示数据元素的信息；表示各数据元素之间的前后件关系。3. 答案：在数据的存储结构中，顺序存储方式的含义如下：顺序存储方式：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里，数据元素之间的逻辑关系由存储单元的邻接关系来体现。4. 答案：在数据的存储结构中，链式存储方式的含义如下：链式存储方式：使用指针表示数据元素之间的逻辑关系，各个数据元素的存储位置可以随意，不要求逻辑上相邻的数据元素在物理位置上也相邻。第 3 章 线性表及其存储结构一、单选题1. 在一个长度为 n的顺序存储的线性表中，向第 i个元素（1 i n+1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。A）n-i B）ni+1 C）ni-1 D）i2. 在一个长度为 n的顺序存储的线性表中，删除第 i个元素（1 i n+1）时，需要从前向后依次前移（ ）个元素。A）n-i B）ni+1 C）ni-1 D）i3. 在一个长度为 n的顺序表中，存在值为 x的元素。在此表中用顺序搜索法，查找值为 x的元素，在等概率情况下，查找成功时的平均查找长度为（ ）。A）n B）n/2 C）(n+1)/2 D）(n - 1)/24. 在一个长度为 n的顺序表中，删除值为 x的元素时，需要比较元素的次数和移动元素次数的和为（ ）。A）n/2 B）(n+1)/2 C）n D）n+15. 在一个顺序表的表尾，插入一个元素时的时间复杂度为（ ）。A）O(1) B）O( ) n2logC）O(n) D）O(n 2)6. 在一个顺序表的任意位置，插入一个元素的时间复杂度为（ ）。A）O(1) B）O( ) 2lC）O(n) D）O(n/2)7. 线性表的顺序存储比链式存储最有利于进行（ ）操作。A）查找 B）表尾插入或删除C）按值插入或删除 D）表头插入或删除98. 线性表的链式存储比顺序存储最有利于进行（ ）操作。A）查找 B）表尾插入或删除C）按值插入或删除 D）表头插入或删除9. 在一个单链表中，若要在 pre所指向的结点之后插入一个新结点，则相继修改（ ）个指针域的值。A）2 B）1 C）3 D）410. 在带表头结点的单链表中，插入一个新结点所用算法的时间复杂度为（ ） 。A）O(1) B）O( ) n2logC）O(n) D）O(n/2)11.以下关于线性表的链式存储结构的叙述中，正确的是（ ）。A）存储密度大B）逻辑上相邻的结点物理上不必相邻C）可以通过计算直接确定第 i个结点的存储地址D）插入、删除运算操作不方便12.带头结点的单链表 H为空的判定条件是（ ）。A）H=NULL B）H-next=NULLC）H-next=H D）H!=NULL13.不带头结点的单链表 H为空的判定条件是（ ）。A）H=NULL B）H-next=NULLC）H-next=H D）H!=NULL14.在一个带头结点的单链表 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=NULLC）p-next=H D）p=H16.链表不具备的特点是（ ）。A）插入删除不需要移动元素 B）可随机地访问任一结点C）不必事先估计存储空间 D）所需空间与其长度成正比17.设线性表有 n个元素，以下算法中，（ ）在顺序表上实现比在链表上实现的效率更高。A）输出第 i（0in-1）个元素B）交换第 0个元素与第 1个元素的值C）顺序输出这 n个元素的值D）输出与给定值 x相等的元素在线性表中的序号18.设线性表中有 2n个元素，以下算法中，（ ）在单链表上实现要比在顺序表上实现效率更高。A）删除所有值为 X 的元素B）在最后一个元素的后面插入一个新元素C）顺序输出前 k个元素D）交换第 i个元素和第 2ni-1个元素的值（i = 0，1，n-1）10二、填空题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.由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的 。三、简答题