文档介绍：第1章绪论
。
(1)O(1)
(2)O(m*n)
(3)O(n2)
(4)O(log3n)
(5)因为x++共执行了n-1+n-2+……+1= n(n-1)/2,所以执行时间为O(n2)
(6)O()
第2章线性表
babadbcabdcddac
(6)设计一个算法,通过一趟遍历在单链表中确定值最大的结点。
ElemType Max (LinkList L ){
if(L->next==NULL) return NULL;
pmax=L->next; //假定第一个结点中数据具有最大值
p=L->next->next;
while(p != NULL ){//如果下一个结点存在
if(p->data > pmax->data) pmax=p;
p=p->next;
}
return pmax->data;
(7)设计一个算法,通过遍历一趟,将链表中所有结点的链接方向逆转,仍利用原表的存储空间。
void inverse(LinkList &L) {
// 逆置带头结点的单链表 L
p=L->next; L->next=NULL;
while ( p) {
q=p->next; // q指向*p的后继
p->next=L->next;
L->next=p; // *p插入在头结点之后
p = q;
}
}
(10)已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素。
[题目分析] 在顺序存储的线性表上删除元素,通常要涉及到一系列元素的移动(删第i个元素,第i+1至第n个元素要依次前移)。本题要求删除线性表中所有值为item的数据元素,并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针(i=1,j=n),从两端向中间移动,凡遇到值item的数据元素时,直接将右端元素左移至值为item的数据元素位置。
void Delete(ElemType A[ ],int n)
∥A是有n个元素的一维数组,本算法删除A中所有值为item的元素。
{i=1;j=n;∥设置数组低、高端指针(下标)。
while(i<j)
{while(i<j && A[i]!=item)i++; ∥若值不为item,左移指针。
if(i<j)while(i<j && A[j]==item)j--;∥若右端元素值为item,指针左移
if(i<j)A[i++]=A[j--];
}
[算法讨论] 因元素只扫描一趟,算法时间复杂度为O(n)。删除元素未使用其它辅助空间,最后线性表中的元素个数是j。
第3章栈和队列
CCDAADABCDDDBCB
(2)回文是指正读反读均相同的字符序列,如“abba”和“abdba”均是回文,但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈) 
根据提示,算法可设计为:
//以下为顺序栈的存储结构定义
#define StackSize 100 //假定预分配的栈空间最多为100个元素
typedef char DataType;//假定栈元素的数据类型为字符
typedef struct{
DataType data[StackSize];
int top;
}SeqStack; 
int IsHuiwen( char *t)
{//判断t字符向量是否为回文,若是,返回1,否则返回0
SeqStack s;
int i , len;
char temp;
InitStack( &s);
len=strlen(t); //求向量长度
for ( i=0; i<len/2; i++)//将一半字符入栈
Push( &s, t[i]);
while( !EmptyStack( &s))
{// 每弹出一个字符与相应字符比较
temp=Pop (&s);
if( temp!=S[i])  return 0 ;// 不等则返回0
else i++;
} 
return 1 ; // 比较完毕均相等则返回 1
}
(7)假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag,以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时,队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法