6.3 典型例题一、单项选择题[例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。
其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。
①A.算法B. 数据元素C. 数据操作D. 逻辑结构②A. 操作B. 映像C. 存储D．关系解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。
[例6-2]数据的常用存储结构中不包括( )。
A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储方法和散列存储方法。
由此可知，本题答案为：B。
[例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。
①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性D．易读性、稳定性、安全性解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。
它必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。
由此可知，本题答案为：①㈠②B。
[例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。
for(i=0；i<n；i++)for(j=0；j<n；j++)x=x+l：A．O(2n) B．O(n) C．O(n2) D．O(1bn)解析：语句的执行频度即语句重复执行的次数，属于算法的时间复杂度类题目。
本题中对x的赋值语句为一个二重循环的循环体，外层循环循环n次，内层循环也循环n次，显然此语句的执行次数为n×n＝n2次。
由此可知，本题答案为：C。
二、填空题[例6-5]是数据的基本单位，通常由若干个组成，是数据的最小单位。
解析：本题是基本概念题，知识点为数据结构的相关概念。
本题答案为：数据元素；数据项；数据项。
三、应用题[例6-6] 简述数据结构的定义。
解析：数据结构是指数据元素之间的相互关系，即数据的组织形式。
数据结构通常包括三个方面的内容，分别是数据的逻辑结构、数据的存储结构(物理结构)和在这些数据上定义的运算。
用集合的观点可以把数据结构表示为一个二元组DS＝(D，R)。
其中，D是数据元素的有穷集合，R是D上关系的有限集合。
[例6-7]分析以下程序段的时间复杂度。
for(i=0；i<n；i++) //语句①{x=x+1；//语句②for(j=0；j<2*n；j++) //语句③y++；//语句④}解析：语句的执行频度指的是语句重复执行的次数。
一个算法中所有语句的执行频度之和构成了该算法的运行时间。
在本例算法中，语句①的执行频度是n+l，语句②的执行频度是n，语句③的执行频度是n(2n+2)＝2n2-2n，语句④的执行频度是n(2n+1)＝2n2+n。
该程序段的时间复杂度T(n)＝(n+1)+n+(2n2+2n)+(2n2+n)＝4n2+5n+1＝O(n2)。
实际上，可以用算法中基本操作重复执行的频度作为度量标准，而被视为基本操作的一般是最深层循环内的语句。
在上例中，语句④为基本操作，其执行频度为2n2+n，因此，该算法的时间复杂度T(n)＝2n2+n＝O(n2)。
[例6-8] 分析以下程序段的时间复杂度。
i=1；while(i<=m)i=i*2；解析：上述算法的基本操作语句是i＝i*2，设其执行频度为T(n)，则有：2T(n)≤n，即T(n)≤lbn＝O(lbn)。
因此，该程序段的时间复杂度为O(lbn)。
7.3 典型例题一、单项选择题[例7-1]在数据结构中，与所使用计算机无关的数据叫( ①)结构；链表是一种采用( ②)存储结构存储的线性表；链表适用于( ③)查找；在链表中进行( ④)操作的效率比在线性表中进行该操作的效率高。
①A．存储B．物理C．逻辑D．物理和逻辑②A．顺序B．网状C．星式D．链式③A．顺序B．二分法C．顺序及二分法D．随机④A．二分法查找B．快速查找C．顺序查找D．插入解析：本题考查的是基本概念。
本题答案为：①C；②D；③A；④D。
[例7-2] 链表不具备的特点是( )。
A．插入和删除不需要移动元素B．可随机访问任一结点C．不必预分配空间D．所需空间与其长度成正比解析：线性表可随机访问任一结点，而链表必须从第一个数据结点出发逐一查找每个结点。
本题答案为：B。
[例7-3] 不带头结点的单链表head为空的判定条件是( )。
A．head＝＝NULL B．head_>next＝＝NULLC．head_>next＝＝head D．head!＝NULL解析：在不带头结点的单链表head中，head指向第一个数据结点。
空表即该表没有结点，head＝＝NULL表示该单链表为空。
本题答案为：A。
[例7-4] 带头结点的单链表head为空的判定条件是( )。
A．head＝＝NULL B．head—>next＝＝NULLC．head—> next＝＝head D．head!＝NULL解析：在带头结点的单链表head中，head指向头结点。
空表即该表只有头结点，head —>next＝＝NULL表示该单链表为空。
本题答案为：B。
[例7-5] 带头结点的循环单链表head中，head为空的判定条件是( )。
A．head＝＝NULL B．head—>next＝＝NULLC．head—> next＝＝head D．head!＝NULL解析：在带头结点的循环单链表head中，head指向头结点。
空表即该表只有头结点，head—>next＝＝head表示该单链表为空。
本题答案为：C。
[例7-6] 线性表采用链式存储时其存储地址( )。
A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续不连续都可以解析：链式存储采用动态存储，地址一般不连续。
本题答案为：D。
[例7-7] 在双向链表的* p结点前插入新结点*s的操作为( )。
A．p—>prior=s；s—>next=p；p—>prior—>next=s；s—>prior=p—>prior；B．p—>prior=s；p—>prior—>next=s；s—>next=p；s—>prior=p—>prior；C．s—>next=p；s—>prior=p—>prior；p—prior=s；p—>prior—>next=s；D．s—>next=p；s—>prior=p—>prior；p—prior—>next=s；p—>prior=s；解析：在双向链表的* p结点前插入新结点* s的操作如图7.12所示，图中虚线为所作的操作，序号为操作顺序。
本题答案为：D。
图7.12 双向链表插入结点的过程示意图(例7-8)若某表最常用的操作是在最后一个结点后插入一个结点和删除第一个结点，则采用( )存储方式最节省运算时间。
A．单链表B．双向链表C．给出表头指针的循环单链表D．给出尾指针的循环单链表解析：在链表中插入或删除一个结点，需修改相邻结点的指针域。
上述四个选项中，只有选项D才能从尾指针经过最少的结点来进行题目要求的插入或删除操作。
本题答案为：D。
[例7-9] 若线性表中有2n个元素，算法( )在单链表上实现要比在顺序表上实现效率更高。
A．删除所有值为x的元素B．在最后一个元素的后面插入一个新元素C．顺序输出前k个元素D．交换其中某两个元素的值解析：对于选项A，在单链表上和顺序表上实现的时间复杂度都为O(n)，但后者要移动大量的元素，因此在单链表上实现效率更高。
本题答案为：A。
(例7-10) 在长度为n的( )上，删除第一个元素，其算法复杂度为O(n)。
A．只有表头指针的不带头结点的循环单链表B．只有尾指针的不带表头结点的循环单链表C．只有表尾指针的带头结点的循环单链表D．只有尾指针的带表头结点的循环单链表解析：本题答案为：A。
具体算法如下：linklist * delfirst(linklist * h){Linklist * p＝h；while(p—> next!＝h) //找到表尾结点p＝p—>next；p—>next=h—> next；free(h)；returnp一>next；//返回头指针}二、填空题[例7-11] 在单链表中结点* p后插入结点* s的指令序列为；。
解析：在单链表中结点* p后插入结点* s，即将* p 的后继结点变为* s 的后继结点，* s 则成为* p的后继结点。
操作指令序列为：s—>next＝p—>next；p—>next＝s。
[例7-12]在线性表的链式存储结构中，根据每个结点所含指针的个数，链表可分为和；而根据指针的链接方式，链表又可分为和。
解析：本题答案为：单链表；多重链表；循环链表；普通链表(非循环链表)。
[例7-13] 在单链表中，要删除某一个指定的结点，必须找到该结点的结点。
解析：由单链表的特点可知，删除某一个结点的操作是将其前驱结点的next 指针域指 向该结点的后继结点。
本题答案为：前驱。
[例7-14] 在一个长度为n 的顺序表中删除第i(0≤i ≤n 一1)个元素，需向前移动 个元素。
解析：需将第i 个元素后的元素依次前移一个位置，总共移动(n-1)-(i+1)+1个元素。
本题答案为：n-i-1。
[例7-15] 在一个具有n 个结点的单链表，在 * p 结点后插入一个新结点的时间复杂度是 ；在给定值为x 的结点后插入一个新结点的时间复杂度是 。
解析：在 * p 结点后插入一个新结点 * s 的操作是：s —> next ＝p —> next ；p —>next ＝ s ；其时间复杂度为0(1)。
在给定值为x 的结点后插入一个结点，首先要找到该结点，然后再进行插入。
找到该 结点的时间复杂度为O(n)，插入的时间复杂度为O(1)。
本题答案为：O(1)；O(n)。
三、应用题(例7-16) 设A 是一个线性表(a 0，a 1，…，a i ，…，a n-1)，采用顺序存储结构，则在等概率情况下平均每插入一个元素需要移动的元素个数是多少?若元素插在a i 和a i+1之间 (0≤i ≤n-1)的概率为1(1)/2n n n -+，则平均每插入一个元素所需要移动的元素个数是多少?解析：在等概率情况下，平均每插入一个元素需要移动的元素个数为：(012)12n n n ++++=+L 若元素插在a i 和a i+l 之间(0≤i ≤n-1)的概率为(1)/2n i n n -+，则平均每插入一个元素所需 要移动的元素个数为：10n i -=∑2222()221(1)1(1)/2(1)3n i n n n n n n n -+⎡⎤=+-++=⎣⎦++L (例7-17) 简述线性表采用顺序存储方式和链式存储方式的优缺点。
