2014浙江省学习数据库入门(5)

2014浙江省学习数据库入门

for(j=i+1;j<n;j++) if(p[j]<min) {k=j; min=p[j];} //记新的最小值及行号. if(i!=k) //若最小行不是当前行,要进行交换(行元素及行元素之和) {pk=matrix+n*k; //pk指向第k行第1个元素.

pi=matrix+n*i; //pi指向第i行第1个元素.

for(j=0;j<n;j++) //交换两行中对应元素.

{sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;}

sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和.

}//if

}//for i

free(p); //释放p数组.

}// Translation

[算法分析] 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n2).

11、设从键盘输入一整数的序列：a1, a2, a3， ，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。

设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，Wn。问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。

Knap(S，n)

若S=0

则Knap←true

否则若（S<0）或(S>0且n<1)

则Knap←false

否则若Knap(1) , _=true

则print(W[n])；Knap ←true

否则 Knap←Knap(2) _ , _

设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如：

设str1和str2是分别指向两个单词的头结点，请设计一个尽可能的高效算法，找出两个单词共同后缀的起始位置，分析算法时间复杂度。

将n(n>1)个整数存放到一维数组R中。设计一个尽可能高效（时间、空间）的算

法，将R中保存的序列循环左移p（0<p<n）个位置，即将R中的数据（x0, x1, x2, , xn-1），变换为(xp， xp＋1, , xn-1 ,x0 , x1, , xp-1)。