第2章 基本数据结构及算法习题参 考答案

习题2参考答案

1．分别写出求两个正整数最大公约数的递推与递归算法。 参考答案：

int gcd(int x, int y) { int a, b, t, r; a=x; b=y; if (a

int gcd(int x, int y) { int a, b, t, r; a=x; b=y; if (a

2．编写将一个十进制整数转换成二进制数的递归算法。 参考答案：

void dec_to_bin(int num,int base)//base为2 { if(num>0) { dec_to_bin(num/base, base); cout<

3．利用减半递推技术，写出求长度为n(n=2k)的一维数组中的最小元素的递归算法。 参考答案：

int min(int x, int y) { return x>y?y:x; }

int minnum(int a[ ],int n) {

int *p,*q;

q=&a[n/2]; p=a;

if(n==1) return a[0];

else return min(minnum(p,n/2),minnum(q,n/2));

}

4．试写出将一个元素插入到有序线性表中的算法。 参考答案：

int insert(int a[ ], int b, int n ,int m) { if (n = =m) printf(\else

{ if (n= =0) a[n]= b; else

{ i=n-1;

while((i＞=0)&&(a[i]＞b)) { a[i+1]=a[i]；i=i-1;} a[i+1]= b; }

n=n+1;

}

return n;

}

5．编写一个算法，将两个线性表合并成一个有序表。 参考答案：

void merge(int a[ ],int b[ ],int c[ ],int m,int n) { int i,j,k; i=j=k=0; while(i

6．设有两个有序线性单链表，头指针分别为ah与bh。试写出将这两个有序线性单链表合并为一个头指针为ch的有序线性单链表的算法。 参考答案：

struct node { int data;

struct node* next;

};

node *merge(node *ah,node *bh) { node *pa,*pb,*pc,*ch,*q; pa=ah;pb=bh;ch=NULL; while(pa!=NULL&&pb!=NULL) { pc=new node; if(pa->data<=pb->data) { pc->data=pa->data; pa=pa->next; } else { pc->data=pb->data; pb=pb->next; }

if(ch==NULL)

ch=pc;

else q->next=pc;

q=pc; } if(pb==NULL) while(pa!=NULL) { pc=new node; pc->data=pa->data; pa=pa->next; if(ch==NULL) ch=pc; else q->next=pc; q=pc; }

else while(pb!=NULL) { pc=new node; pc->data=pb->data; pb=pb->next; if(ch==NULL) ch=pc; else q->next=pc; q=pc; } q->next=NULL; return(ch); }

7．试写出逆转线性单链表的算法。 参考答案： struct node { char d; struct node *next };

invlst(struct node **head) { struct node *p,*q,*r; if(*head!=NULL) { p=*head;q=p->next; p->next=NULL; while(q!=NULL) { r=q->next;q->next=p; p=q;q=r; } *head=p; } }

8．写出计算线性链表长度的算法。 参考答案：

struct node /*定义线性单链表结点类型*/

{ ET d; /*定义线性单链表结点数据类型*/ struct node *next;/*结点指针*/ };

int len(struct node *head) { int n; struct node *p; n=0;

p=head;

while(p!=NULL) { n++; p=p->next; }

return n; }

9．用筛选法求1000以内的素数。用单链表存放2~1000的值，编写一个函数删除该单链表中非素数的结点（即剩下的结点中的值均为素数）。 #include

struct node { int d;

node *next; };