假设sqrt(n)函数中涉及的算法时间复杂度为O(1)，那么下面的算法是判断n是否为素数，其时间复杂度为（      ）。void prime(int n){   for (i=2; i<sqrt(n) && (n % i)!=0; i++) ;    if (i>sqrt(n))            printf(“%d is a prime number”， n);     else          printf(“%d is not a prime number”， n);} 

A:O(n)
B:O(1)
C:O(sqrt(n))    sqrt表示对n取根方
D:O(n-i)
答案: O(sqrt(n))    sqrt表示对n取根方

A:T(n) = O(nnn)
B:T(n) = O(nn)
C:T(n) = O(   (nnn+nn+n)/n  )
D:T(n) = O(nn+n)
答案: T(n) = O(nn)

A:数据
B:数据对象
C:数据元素
D:数据项
答案: 数据元素

A:集合
B:线性
C:树
D:图
答案: 集合;
线性;
树;
图

A:0个或多个输入；至少1个输出
B:正确性
C:确定性
D:可行性和有限性
答案: 0个或多个输入；至少1个输出;
确定性;
可行性和有限性

A:正确性
B:可读性
C:健壮性
D:高效率和低存储
答案: 正确性;
可读性;
健壮性;
高效率和低存储

A:顺序存储
B:非顺序存储
C:图结构
D:树结构
答案: 顺序存储;
非顺序存储

A:一个数据对象
B:元素的存储结构
C:元素间的关系
D:一组操作
答案: 一个数据对象;
元素间的关系;
一组操作

A:正确
B:错误
答案: 错误
分析：线性、非线性结构是元素间的逻辑关系。
顺序、非顺序存储时元素的存储结构。
二者没有明显的一一对应关系。

也就是说，无论元素的逻辑关系如何，顺序和非顺序存储结构都是可以的。

A:正确
B:错误
答案: 错误
分析：程序是用某种程序设计语言对算法的实现。二者不同。

A:正确
B:错误
答案: 正确

A:正确
B:错误
答案: 错误
分析：可行性指算法咋原则上要能实现；每一条指令需要由明确含义是算法的确定性。

A:正确
B:错误
答案: 正确

A:正确
B:错误
答案: 错误
分析：二者是算法的设计要求，但不是全部。还包括正确性、可读性、鲁棒性（健壮性）

A:正确
B:错误
答案: 错误
分析：数据类型是一组性质相同的元素及在其上的一组操作的总称。其并不占内存空间。
而变量是某种数据类型具体表现，需要占内存空间。

A:正确
B:错误
答案: 正确

A:正确
B:错误
答案: 错误
分析：哪种存储结构更优，取决于其操作。二者各有优缺点。

A:正确
B:错误
答案: 错误
分析：还有集合结构，既不属于线性，也不属于非线性。集合结构中，元素间没有任何关系。

第二章 线性表（一）（总时长：72分22秒，共6讲） 第二章 单元测试（1）

A:O(logn)(以2为底)
B:O(1)  
C:O(n)   
D:O(n*n)
答案: O(n)   

A:n-i
B:i
C:n-i+1
D:n-i-1
答案: n-i+1

A:插入、删除不需要移动元素
B:可随机访问任一元素
C:不必事先估计存储空间
D:所需存储空间与线性表程度成正比
答案: 可随机访问任一元素

A:p->next=p->next->next;  free(p->next);
B:free(p->next);p->next=p->next->next;
C: p=p->next;
D:s=p->next;p->next=s->next;free(s);
答案: s=p->next;p->next=s->next;free(s);

A:n
B:(n+1)/2
C:(n-1)/2
D:n/2
答案: (n-1)/2

A:Base+(i-1)×m              
B:Base+i×m          
C:Base-i×m              
D:Base+(i+1)×m 
答案: Base+(i-1)×m              

A:i>0    
B:1≤i≤n+1 
C:1≤i≤n-1
D:0≤i≤n+1
答案: 1≤i≤n+1 

A:p==NULL
B:p->next==NULL
C:p->next==P
D:p->next!=NULL
答案: p->next==NULL

A:504
B:508
C:516
D:528
答案: 528

A:n-i
B:n-i+1
C:n-i-1
D:i
答案: n-i

A:O(1)
B:O(n)
C:O(logn）（以2为底）
D:O(nlogn)
答案: O(1)

A:i++
B:j++
C:i–
D:j–
答案: j++

A:free(p); pre->next=p->next;
B:free(p->next);pre->next=p->next;
C:pre->next=p->next; free(p); 
D:p->next=pre->next;free(p);
答案: pre->next=p->next; free(p); 

A:正确
B:错误
答案: 错误
分析：添加头结点的目的是，简化操作，使得在表头和中间位置对链表的操作统一化。不一定是为了存储链表的长度。

A:正确
B:错误
答案: 错误

A:正确
B:错误
答案: 错误
分析：顺序表中，查找第i个元素，时间是常量。

A:正确
B:错误
答案: 错误
分析：首元素没有前驱，尾元素没有后继。

A:正确
B:错误
答案: 错误
分析：两种存储结构各有优缺点。要根据实际问题选择合适的存储结构。

A:正确
B:错误
答案: 错误
分析：前半句正确，后半句错误。
顺序存储中，插入和删除的效率比较低。

A:正确
B:错误
答案: 错误

A:正确
B:错误
答案: 错误
分析：数组本身不能进行插入和删除，因为数组的长度是不可变的。（在某些语言中）

A:正确
B:错误
答案: 正确

A:正确
B:错误
答案: 正确

A:正确
B:错误
答案: 正确

A:正确
B:错误
答案: 正确

A:p->next==NULL
B:p==NULL
C:p->next==L
D:p==L
答案: p->next==L

A:顺序表    
B:双向链表
C:带头结点的双循环链表
D:单循环链表
答案: 顺序表    

A:单链表  
B:仅有头指针的单循环链表 
C:双链表
D:带尾指针的单循环链表
答案: 带尾指针的单循环链表

A:2
B:3
C:4
D:5
答案: 4

A:O(m)
B:O(n)
C:O(m+n)
D:O(m*n)
答案: O(n)

A:1
B:2
C:3
D:4
答案: 2

A:p->prior->next = p->next
B:p->next = p->prior
C:p->prior = p->next
D:p->prior->next = p
答案: p->prior->next = p->next

A:s->next=p->next;p->next=s;  //将s结点插入到p之后t=s->data;s->data=p->data;p->data;   //s结点和p结点的值互换
B:q=p->next;while(q->next!=p)  q=q->next;s->next=p; q->next=s;
C:q=p->next;while(q->next!=p)  q=q->next;q->next=s; s->next=p;
D:在p结点前插入s结点，而且要求在O(1)内，无法实现。
答案: s->next=p->next;p->next=s;  //将s结点插入到p之后t=s->data;s->data=p->data;p->data;   //s结点和p结点的值互换

A:可采用以下算法实现：第一步：先将两个链表各自遍历一遍，统计出两个单链表的长度m和n。假设m>n，k=m-n第二步：长链表先走k步：用指针p从长链表头开始，先走k步，此时p指向长链表的第k+1个结点。第三步：q从短链表头开始，和p一起走。p和q相等时，即为交点；如果p和q不相交，则两个链表不相交。
B:可采用以下算法实现：第一步：用两个指针p和q，分别从两个链表头开始，向后走。第二步：如果两个指针相等，即指向同一个结点，则说明相交，该结点就是交点。
C:可采用以下算法实现：第一步：将两个链表分别逆置。第二步：从头开始，什么时候链表分叉，该分叉的结点就是相交的结点。
D:该问题无法求解。
答案: 可采用以下算法实现：第一步：先将两个链表各自遍历一遍，统计出两个单链表的长度m和n。假设m>n，k=m-n第二步：长链表先走k步：用指针p从长链表头开始，先走k步，此时p指向长链表的第k+1个结点。第三步：q从短链表头开始，和p一起走。p和q相等时，即为交点；如果p和q不相交，则两个链表不相交。

A:采用快慢指针方法。即：第一步：一个指针走的快，每次走2个结点；一个指针走的慢，每次走1个结点。第二步：当快指针到结尾或空时，慢指针所指结点即为中间结点。注：遇到链表结点为奇数或偶数时，需稍加改进即可。
B:第一步：遍历一遍链表，求出其长度n。第二步：再从头开始遍历链表，到n/2处即可。若n为偶数，中间结点则有2个；若n为奇数，则只有1个。需稍加处理。
C:第一步：将链表中的结点依次放入一个数组中，同时记录结点个数；第二步：数组中间位置即为中间结点。
D:无法实现
答案: 采用快慢指针方法。即：第一步：一个指针走的快，每次走2个结点；一个指针走的慢，每次走1个结点。第二步：当快指针到结尾或空时，慢指针所指结点即为中间结点。注：遇到链表结点为奇数或偶数时，需稍加改进即可。

A:第一步：将单链表逆置；第二步：输出单链表中的元素；第三步：将单链表逆置，即恢复之前的单链表。
B:第一步：将单链表中的 元素依次放入一个数组中第二步：逆序输出该数组中的元素。
C:可用如下代码实现：void reversePrint(Node *p//p初值为单链表第一个结点{       while(p!=NULL)      {  reversePrint(p->next);         printf(“%c  “，p->data);  //假设结点值为字符}
D:算法思想：第一步：从头到尾找到最后一个结点；第二步：从最后一个结点向前依次输出每个结点的值。
答案: 算法思想：第一步：从头到尾找到最后一个结点；第二步：从最后一个结点向前依次输出每个结点的值。

A:正确
B:错误
答案: 错误
分析：静态链表本质仍然是链表，所以它不具有顺序表的优点。

A:正确
B:错误
答案: 错误
分析：前驱和后继是元素间的逻辑关系。
循环单链表是元素的存储关系，只是为了操作方便而采用循环链表，并不会改变元素的逻辑关系。