数据结构与算法离线作业【2014春】(2)

【33，10，2】在对一组关键字是（54,38,96,45,15,72,60,23,83）的记录进行直接插入排序时，当把第七个记录（关键字是60）插入到有序表时，为寻找插入位置需比较 3 次。

【34，10，4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中，不稳定的排序方法有 希尔排序、快速排序、堆排序 。

6

二、综合题（选自教材《数据结构》各章习题，采用word文件格式上传）

【1，1，3】试分析下面一段代码的时间复杂度：

if ( A > B ) {

for ( i=0; i

for ( j=N*N; j>i; j-- ) A += B; }

else {

for ( i=0; ii; j-- ) A += B; }

If A>B为真，则for语句的外循环N次，内循环为N*N-N=N（N-1）次，因此时间复杂度为O(N* N（N-1）)，也就是N的三次方。

If A>B为假，则for语句的外循环2N次，内循环为2*N-N=N次，因此时间复杂度为O（2N*N），也就是N的平方。

整段取大的，时间复杂度就是N立方。

【2，1，3】测试例1.3中秦九韶算法与直接法的效率差别。令f(x)?1??i?1xi/i，计算f(1.1)的值。利用clock()函数得到两种算法在同一机器上的运行时间。 直接法：0.1μs 秦九韶算法：0.04μs

【3，1，3】 试分析最大子列和算法1.3的空间复杂度。 【4，1，3】试给出判断N是否为质数的O(N)的算法。

int sushu(int N) { int i; int flag=1;

if (N==1) return false; if (N==2) return true; for (i=2;i<=sqrt(N);i++)

{ if (N%i==0){ flag=0 ; break; }}

7

100

return flag; }

【5，2，2】请编写程序，输入整数n和a，输出S=a+aa+aaa+…＋aa…a(n个a)的结果。

#include\int main() {

int a,b,n,i,s=0;

scanf(\ b=a;

for(i=1;i<=n;i++) {

s+=a;

a=a*10+b; }

printf(\}

【6，2，3】请编写递归函数，输出123..n的全排列（n小于10）,并观察n逐步增大时程序的运行时间。

#include #define N 8 int n = 0;

void swap(int *a, int *b) {

int m;

m= *a; *a = *b; *b = m; }

void perm(int list[], int k, int m) {

int i; if(k > m) {

for(i = 0; i <= m; i++)

printf(\ printf(\

8

n++; } else {

for(i = k; i <= m; i++) {

swap(&list[k],&list[i]); perm(list,k + 1, m); swap(&list[k],&list[i]); } } }

int main() {

int list[N];

int num,i=0;

printf(\ scanf(\ while(num != 0) {

list[i]=num; num=num/10; i++; }

perm(list,0, i-1);

printf(\ return 0; }

【7，3，2】 给定一个顺序存储的线性表L = (a1, a2, ?, an)，请设计一个算法删除所有值大于min而且小于max的元素。

#include #include #include typedef int ElemType; typedef struct LNode

{ ElemType data; /* 数据子域 */ struct LNode *next; /* 指针子域 */ }LNode; /* 结点结构类型 */

9

LNode *L;

/* 函数声明 */ LNode *creat_L();

void delete_L(LNode *L,int i); //返回值格式变为空 /* 建立线性链表*/ LNode *creat_L() { LNode *h,*p,*s; ElemType x;

h=(LNode *)malloc(sizeof(LNode)); /* 分配头结点 */ h->next=NULL; p=h;

printf(\输入一串数字（以-1结束）:\\ndata= \);

scanf(\,&x); /* 输入第一个数据元素 */ while( x!=-1) /* 输入-1，结束循环 */ {

s=(LNode *)malloc(sizeof(LNode)); /* 分配新结点 */ s->data=x; s->next=NULL; p->next=s; p=s; printf(\);

scanf(\,&x); /* 输入下一个数据*/ }

return(h); } /* creat_L */ /* 输出单链表中的数据元素*/ void out_L(LNode *L) { LNode *p; p=L->next; printf(\数据是:\); while(p!=NULL) {

printf(\,p->data); p=p->next; } } /* out_link */

/* 删除大于x小于y的值*/

void delete_L(LNode *L,int a,int b) { LNode *p,*q; p=L; q=p; p=p->next;

if(p==NULL) printf(\链表为空\); while(p!=NULL) { if((p->data >a) && (p->data next=p->next;

free(p); p=q->next; }

else { q=p; p=p->next; } } } /* delete_L */ void main() { int a,b;

L=creat_L(); out_L(L);

printf(\请输入你要删除的元素的范围min和max:\\n\);

10