{
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-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＝＝NULL
C．head_>next＝＝head D．head!＝NULL
解析：在不带头结点的单链表head中，head指向第一个数据结点。空表即该表没有结
点，head＝＝NULL表示该单链表为空。本题答案为：A。
[例7-4] 带头结点的单链表head为空的判定条件是( )。
A．head＝＝NULL B．head—>next＝＝NULL
C．head—> next＝＝head D．head!＝NULL
解析：在带头结点的单链表head中，head指向头结点。空表即该表只有头结点，head—>next＝＝NULL 表示该单链表为空。本题答案为：B。
[例7-5] 带头结点的循环单链表head中，head为空的判定条件是( )。
A．head＝＝NULL B．head—>next＝＝NULL
C．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。
