数据结构与算法课后习题解答.doc

文档介绍：第一章绪论(参考答案)
(1) O(n)
(2) (2) O(n)
(3) (3) O(n)
(4) (4) O(n1/2)
(5) (5) 执行程序段的过程中,x,y值变化如下:
循环次数 x y
0(初始) 91 100
1 92 100
2 93 100
………………
9 100 100
10 101 100
11 91 99
12 92 100
………………
20 101 99
21 91 98
………………
30 101 98
31 91 97
到y=0时,要执行10*100次,可记为O(10*y)=O(n)
2100 , (2/3)n , log2n , n1/2 , n3/2 , (3/2)n , nlog2n , 2 n , n! , n n

第二章线性表(参考答案)

在以下习题解答中,假定使用如下类型定义:
(1)顺序存储结构:
#define MAXSIZE 1024
typedef int ElemType;// 实际上,ElemType可以是任意类型
typedef struct
{ ElemType data[MAXSIZE];
int last; // last表示终端结点在向量中的位置
}sequenlist;
(2)链式存储结构(单链表)
typedef struct node
{ElemType data;
struct node *next;
}linklist;
(3)链式存储结构(双链表)
typedef struct node
{ElemType data;
struct node *prior,*next;
}dlinklist;
(4)静态链表
typedef struct
{ElemType data;
int next;
}node;
node sa[MAXSIZE];

头指针:指向链表的指针。因为对链表的所有操均需从头指针开始,即头指针具有标识链表的作用,所以链表的名字往往用头指针来标识。如:链表的头指针是la,往往简称为“链表la”。
头结点:为了链表操作统一,在链表第一元素结点(称为首元结点,或首结点)之前增加的一个结点,该结点称为头结点,其数据域不无实际意义(当然,也可以存储链表长度,这只是副产品),其指针域指向头结点。这样在插入和删除中头结点不变。
开始结点:即上面所讲第一个元素的结点。
只设尾指针的单循环链表,从尾指针出发能访问链表上的任何结点。
2·3
void insert(ElemType A[],int elenum,ElemType x)
// 向量A目前有elenum个元素,且递增有序,本算法将x插入到向量A中,并保持向量的递增有序。
{ int i=0,j;
while (i<elenum && A[i]<=x) i++; // 查找插入位置
for (j= elenum-1;j>=i;j--) A[j+1]=A[j];// 向后移动元素
A[i]=x; // 插入元素
} // 算法结束

2·4
void rightrotate(ElemType A[],int n,k)
// 以向量作存储结构,本算法将向量中的n个元素循环右移k位,且只用一个辅助空间。
{ int num=0; // 计数,最终应等于n
int start=0; // 记录开始位置(下标)
while (num<n)
{ temp=A[start]; //暂存起点元素值,temp与向量中元素类型相同
empty=start; //保存空位置下标
next=(start-K+n) %n; // 计算下一右移元素的下标
while (next !=start)
{ A[empty]=A[next];// 右移
num++; // 右移元素数加1
empty=next;
next=(next-K+n) %n; // 计算新右移元素的下标
}
A[empty]=temp; // 把一轮右移中最后一个元素放到合适位置
num++;
start++; // 起点增1,若num<n则开始下一轮右移。
}
} // 算法结束
算法二
算法思想:先将左面n-k个元素逆置,接着将右面k个元素逆置,最后再将这n个元素逆置。
void rightrotate(ElemType A[],int n,k)
// 以向量作存储结构,本算法将向量中的n个元素循环右移k位,且只用一个辅助空间。
{ ElemType temp;
for(