1. 绪 论
1．将下列复杂度由小到大重新排序：
A．2n B．n! C．n5 【答】10 000< n*log2(n)< n5< 2n < n! 2．将下列复杂度由小到大重新排序：
A．n*log2(n) B．n + n2 + n3 【答】24< n0.5< n*log2 (n) < n + n2 + n3 3．用大“O”表示法描述下列复杂度：
A．5n5/2 + n2/5
C．3n4+ n* log2(n) 【答】A：O (n5/2) B：O (n)
D．10 000 E．n*log2 (n)
C．24
D．n0.5
B．6*log2(n) + 9n D．5n2 + n3/2 C：O (n4) D：O (n2)
4．按照增长率从低到高的顺序排列以下表达式：4n2 , log3n, 3n , 20n , 2000 , log2n ,
n2/3。又n！应排在第几位？
【答】按照增长率从低到高依次为：2000, log3n, log2n , n2/3 , 20n , 4n2 , 3n。 n！的增长率比它们中的每一个都要大，应排在最后一位。 5. 计算下列程序片断的时间代价：
int i=1; while(i<=n) {
printf(“i=%d\\n”,i); i=i+1; }
【答】循环控制变量i从1增加到n，循环体执行n次，第一句i的初始化执行次数为1，第二句执行n次，循环体中第一句printf执行n次，第二句i从1循环到n，共执行n次。所以该程序段总的时间代价为：
T(n) = 1 + n + 2n = 3n+ 1 = O(n)
6. 计算下列程序片断的时间代价：
int i=1; while(i<=n) { int j=1; while(j<=n) { int k=1; while(k<=n) {
printf(“i=%d,j=%d,k=%d\\n”,I,j,k);
k=k+1; } j=j+1; } i=i+1; }
【答】循环控制变量i从1增加到n，最外层循环体执行n次，循环控制变量j从1增加到n，中间层循环体执行n次，循环控制变量k从1增加到n，最内层循环体执行n次，所以该程序段总的时间代价为：
T(n) = 1 + n + n｛1 + n + n[1 + n + 2n +1] +1 +1｝+ 1
= 3n3 + 3n2 +4n +2 = O(n3)
2. 线性表
1.试写一个插入算法int insertPost_seq(palist, p, x )，在palist所指顺序表中，下标为p的元素之后，插入一个值为x的元素，返回插入成功与否的标志。
【答】
数据结构
采用2.1.2节中顺序表定义。
int insertPost_seq(PseqList palist, int p, DataType x )?{ /* 在palist所指顺序表中下标为p的元素之后插入元素x */ int q;
if ( palist->n >= palist-> MAXNUM ) { printf(“Overflow!\\n”); return 0; }
if (p<0 || p>palist->n-1 ) {
printf(“Not exist! \\n”); return 0; }
for(q=palist->n - 1; q>=p+1; q--) /* 插入位置及之后的元素均后移一个位置 */ palist->element[q+1] = palist->element[q]; palist->element[p+1] = x; palist->n = palist->n + 1; return 1; }
/* 插入元素x */ /* 元素个数加1 */
/* 不存在下标为p的元素 */
/* 溢出 */
2试写一个删除算法deleteV_seq(palist, x )，在palist所指顺序表中，删除一个值为x的元素，返回删除成功与否的标志。
【答】
数据结构
采用2.1.2节中顺序表定义。
int deleteV_seq(PseqList palist, p, DataType x ) { /* 在palist所指顺序表中删除值为x的元素 */ int p,q;
for(p=0;p
for(q=p; q
/* 元素个数减1 */
} return 0; }
3. 设有一线性表e = (e0, e1 , e2 , ? , en?1 )，其逆线性表定义为e?= (en?1 , ? , e2 , e1 ,e0)。请设计一个算法，将用顺序表表示的线性表置逆，要求逆线性表仍占用原线性表的空间。 【答】
数据结构
采用2.1.2节中顺序表的定义。
思路
考虑对数组element[ ]进行置逆，即把第一个元素和最后一个元素换位置，把第二个
元素和倒数第二个元素换位置……。 ? 注意
这种调换的工作只需对数组的前一半元素进行，所以设置整数变量count用于存放数组长度的一半的值。大家可以考虑一下：为什么不能对整个数组进行如上的对元素“换位置”的工作？（提示：这样会将本来已经置逆的线性表又置逆回来，即又变成了原来的表。）
顺序表的置逆算法
void rev_seq(PSeqList palist){
DataType x; int count, i;
if (palist->n == 0 || palist->n == 1) return; count = palist->n / 2; for ( i = 0; i < count; i++){
x = palist->element[i];
palist->element[i] = palist->element[palist->n ? 1 ? i]; palist->element[palist->n ? 1 ? i] = x; } }
/*只需调换半个表的元素*/ /*空表或只有一个元素，直接返回*/
代价分析
该算法中包含一个for循环，其循环次数为n/2。因此，算法的时间代价为O(n)。 4. 已知长度为n的线性表A采用顺序存储结构，请写一算法，找出该线性表中值最小的数据元素。
【答】
数据结构
采用2.1.2节中顺序表定义。 思路
设置变量min，遍历整个表，不断更新当前已经经历过的元素的最小值即可。 为方便起见，事先假设表不为空。 算法
DataType min_seq(PSeqList palist){
DataType min; int i;
/*求非空顺序表中的最小数据元素*/
min = palist->element[0]; for ( i = 1; i < palist->n; i++)
if (min > palist->element[i]) min = palist->element[i]; return min; }
/*初始化min*/
/*min中保存的总是当前的最小数据*/
代价分析
该算法访问顺序表中每个元素各一次，时间代价为O(n)。
? 讨论
读者可以试图对上面的算法进行修改，使返回的值不是最小元素的值而是它的下标。
5. 已知线性表A的长度为n，并且采用顺序存储结构。写一算法，删除线性表中所有值为x的元素。 【答】 数据结构
采用2.1.2节中顺序表的定义。 思路
为了减少移动次数，可以采用快速检索的思想，用两个变量i, j记录顺序表中被处理
的两端元素的下标，开始时i = 0，j = n?1，边检索第i个元素边增加i，直到找到一个元素值等于x，再边检索第j个元素边减少j，直到找到一个元素值不等于x，把下标为j的元素移到下标为i的位置后重复上述过程，直到i ≥ j。另用一变量count记录删除了多少个元素。
算法
void delx_seq(PSeqList p, DataType x){
/*删除顺序表中所有值为x的元素，新顺序表可能不保持原有顺序*/
int i = 0, j = p->n ? 1, count = 0; while ( i < j) {
if (p->element[i] == x) {
/*找到了一个要删除的元素*/
while ((p->element[j] == x) && (i != j)) {
/*从后往前找不会被删除的元素，当i, j相等时退出循环，count记录从后往前找的过程中遇到了多少个要删的元素*/
j? ?; count++; }
if ( i = = j) {
p->n = p->n ? count ? 1; return; } else{
p->element[i] = p->element[j]; count++; j? ?; } } i++; }
/*i定位于顺序表开始处，j定位于顺序表最后*/