作业讲评1-5章数据结构

算法与数据结构各章学习要点

第1章 概论 P10： 一、

1. 0 1 0 1

2. 集合、线性、树、图 3. 顺序、链式、散列、索引 4. 链式

二、1~5：CCBCD

第2章 线性表

P41： 一、

1.不一定 2. 数据域 指针域 3. O(n) O(1) 4. O(1) O(n) 5. i-1 6. p->next a[p].next 7. m+n*c

8. (1)q->next=p->next; p->next=q; (2)s=p->next; p->next=s->next; free(s); 10. 头 11. 直接前驱 直接后继 12. 最后一个 表头结点 二、1~5：BA B C C B 6~7: C D 9: C 三 1，

#define MAX 100 typedef struct

{ elemtype data[MAX];

int len; /*顺序表中元素个数*/ }Seqlist;

Seqlist *merge(Seqlist *A,Seqlist *B)

{ Seqlist *C=(Seqlist *)malloc(sizeof(Seqlist)); int i,j,k; i=j=k=0;

while(ilen&&jlen)

{ if(A->data[i]data[j]) {C->data[k]=A->data[i];i++;k++;} else {C->data[k]=B->data[j]; j++;k++;} }

while(ilen) {C->data[k]=A->data[i];i++;k++;} while(jlen) {C->data[k]=B->data[j];j++;k++;} return C; } 3，

typedef struct node { elemtype data;

struct node *next;

1

i+1 }linklist; 4

第3章 栈与队列

P64 一、

1. 队尾 队头 2.先进后出 先进先出

3. O(1) O(n) O(1) O(1) 4. 3 5. (r-f+n)%n 7. b 8. 0 max-1 二、

1~5: B B C C B 6~10:CADBD 11. D 三2.

abcde abced abdce abdec abedc acbde acbed acdbe acdeb acedb adcbe adceb adecb aedcb

bacde baced badce badec baedc bcade bcaed bcdae bcdea bceda bdcae bdcea bdeca bedca

cbade cbaed cbdae cbdea cbeda cdbae cdbea cdeba cedba

dcbae dcbea dceba decba edcba

第4章 串

P77:

一、1.空串的长度为0;空格串的长度>0

2.两个字符串的长度相等并且对应字符相等 3.顺序串和链串 二、1~4：BBBD 三:1~5:F F F F F

第5章 数组和广义表

P89:

一、1. LOC(a[0][0])+(i*(n+1)+j)*d 3. 41 4.(a) (a) 二、1.B 3.B 4.BD 三

2

1. L*N*(N+1)/2 2.

3