《数据结构》耿国华版算法习题
第一部分线性表
1．/*有序表上插入新元素*/
typedef int datatype;
#define maxsize 1000
typedef struct
{ datatype list[maxsize];
int size; /**/
} sequenlist; /*顺序表类型定义*/
int ins2_4_1(sequenlist *L,datatype x)/*从后向前比较*/
{ int i;
if (L->size>=maxsize)
{
printf("溢出");
return 0;
}
else
{
for ( i=L->size-1 ; i>=0 ; i-- )
if( x < L->data[i])
L->data[i+1] = L->data[i] ;
else
break;
/* 以上for循环也可以改为：
for ( i=L->size-1 ; i>=0 && x < L->data[i]; i-- )
L->data[i+1] = L->data[i] ;
*/
L->data[i+1] = x ;
L->last++ ;
return 1;
}
}
ins2_4_2(sequenlist *L,datatype x) /*从前向后比较*/
{ int i,j;
if (L->size>=maxsize)
{
printf("溢出");
return 0;
}
else
{
for ( i=0 ; i<=L->last ; i++ )
if ( x<=L->data[i])
break;
/* 以上for循环也可以改为：
for ( i=0 ; i<=L->last && x>L->data[i] ; i++ ) ;
*/
for( j=L->last ; j>=I ; j--)
L->data[j+1] = L->data[j] ;
L->data[i] = x ;
L->last++ ;
return 1;
}
}
2:
删除顺序表中，从第i个元素开始的k个元素。
int DELETE( seqlist * L , int i , int k ) /*seqlist 顺序表类型*/
{ int j;
if (i > L->last ) /*起始位置超出表长，无法删除*/
{ printf ("error");
return 0;
}
else
{ if (i+k-2 > L->last ) /*从起始位置开始不足K个元素，则将起始位置到表尾全部删除*/
{ L->last = i-2; /*此时不进行元素的移动，覆盖*/
}
else
{ for ( j = i+k-1 ; j <= L->last ; j++ )
/*i+k-1下标的元素覆盖i-1, i+k下标元素覆盖i，以此类推，直到L->last */
L->data[ j-k ] = L->data[ j ];
L->last = L->last - k;
}
return 1;
}
}
3
/*删除值递增的单链表中,所有大于mink且小于maxk的元素*/
ch2_6 ( linklist H , int mink , int maxk ) /*H为带头结点的单链表?*/
if ( mink<=maxk )
{ p=H;
while ( p->next!=NULL )
{ if ( p->next->data>=mink && p->next->data { q=p->next; p->next=q->next; free(q); } else p=p->next; } } else { p=H; while ( p->next!=NULL ) { if ( p->next->data>=mink || p->next->data { q=p->next; p->next=q->next; free(q); } else p=p->next; } } } 4 ch2_7a ( seqlist *l ) /*顺序存储*/ { int I , temp ; for ( i=0 ; i<=l->last/2 ; i++ ) { temp=l->data[i]; l->data[i]=l->data[l->last-i]; l->data[l->last-i]=temp; } } /*带头结点单链表逆序*/ typedef int datatype; typedef struct node {datatype data; struct node *next; }*linklist; { linklist p,q; q=l->next; l->next=NULL; while ( q!=NULL ) { p = q ; q=q->next; p->next=l->next; l->next=p; } } 5: 非递减有序的表A,B,合并成非递增有序的表C。（存储结构，单链表）方法：依次从A或B表中得到最小值，使用前插法生成表C。typedef struct node { int data; struct node *next; } NODE , *LinkList ; LinkList union(LinkList A , LinkList B ) { LinkList C ; LinkList pa,pb,min; C＝malloc(sizeof(NODE)); C->next=NULL; pa=A->next; pb=B->next; while( pa!=NULL && pb !=NULL ) { if (pa->data < pb->data) { min=pa; pa=pa->next; } else { min =pb; pb=pb->next; } min->next=C->next; C->next=min; } while ( pa!=NULL) { min=pa; pa=pa->next; min->next=C->next; C->next=min; } while ( pb!=NULL) { min=pb; pb=pb->next; min->next=C->next; C->next=min; } return C; } 6 /*删除长度大于的1的循环单链表中s结点的先驱结点,无头结点无头指针*/ ch2_9(linklist s) {linklist p,q; p=s; while(p->next->next!=s) p=p->next; q=p->next; p->next=s; free(q); } 7 /*将一单链表中的结点按类型分为三个循环链表*/ chaifen(linklist l,linklist a,linklist b,linklist c) {linklist p,ra,rb,rc; l=l->next; ra=a; rb=b; rc=c; while(l!=NULL) { if (l->data>'0'&&l->data<'9') { ra->next=l; ra=l; } else if (l->data>'a'&&l->data<'z'||l->data>'A'&&l->data<'Z') { rb->next=l; rb=l; } else { rc->next=l; rc=l; } l=l->next; } ra->next=a; rb->next=b; rc->next=c; } 8将一个表示稀疏多项式的循环链表分解成各奇偶次项的链表*/ typedef struct polynode {int coef; int exp; struct polynode *next; }*polylist; ch2_12(polylist a,polylist b,polylist c) {polylist pa,ra,pb,pc; b=malloc(sizeof(struct polynode)); pb=b; c=malloc(sizeof(struct polynode)); pc=c; ra=a->next; while(ra!=NULL) {pa=ra; ra=ra->next; if (pa->coef%2==0) {pb->next=pa; pb=pa; } else {pc->next=pa; pc=pa; } pb->next=NULL; pc->next=NULL; free(a); } 9 /*二进制的加1运算*/ ch2_13(linklist a) {int temp=1; linklist p,q=NULL; while( temp==1) { if(q!=a->next) {p=a; while(p->next!=q) p=p->next; } else {p=malloc(sizeof(linklist)); p->data=0; p->next=a->next; a->next=p; } if(p->data==0) {p->data=1; temp=0; } else {p->data=0; q=p; } } } 第二部分栈和队列 １． 写一个算法，判断依次读入的一个以＠为结束符的字母序列，是否为形如'序列１＆序列２'模式的字符序列。其中序列１和序列２都不含字符'＆'，且序列2是序列1的逆序列。 思路：将字符串中＆符以前的符号入栈保存，跳过＆符，出栈并和新遇到的字符比较，不相等，结论为不对称，相等，继续比较，直到遇到＠符。若当前符号为＠且栈空，为对称，否则都为不对称。 typedef struct { char elem[MAX]; int top; }seqstack; int ch3_5(char *str)/*判断字符串str是否回文*/ { seqstack S; /*栈，用于存储＠符以前的字符*/ while( *str!= '@' && *str != '&' ) /*遇到符号＠，或＆以前的符号入栈*/ { push(S,*str); str++; } if (*str =='@' ) /*先遇到＠，不是回文*/ return 0; str++; /*跳过＆符号*/ while( *str !='@') /*对＆符以后，＠以前的符号做回文判断*/ { Gettop(S,&ch); if (*str == ch ) { pop( S, &ch); str ++; } else break; } if (*str=='@' && IsEmpty(S) == 1 )/*当前字符取完且栈空，是回文*/ return 1; else return 0; } ２． 例：源表达式为：(a+b*c)-d/e 逆波兰式表达式为：abc*+de/- 思路：使用栈来保存操作符，且调整操作符的运算顺序，使用队列来保存结果字符串，一旦遇到字母字符就入队，遇到操作符字符需要利用栈，和之前的操作符比较，决定入栈继续保存或是取出放在结果中。 ch3_6( char * expr , char * result) /*expr 为源表达式字符串，result为求得的逆波兰式表达式字符串*/ { seqstack S; seqqueue Q; char op; InitStack(S); /*初始化栈*/ InitQueue(Q);/*初始化队列*/ push(S,'#'); /*将符号'#'入栈*/ while(*expr !='\0') { if (*expr >='a' && *expr <='z' ) {enqueue(Q , *expr );/*字母字符入队*/ expr++; } else { gettop(S , &ch); switch ( comp( *expr, ch))/*比较当前操作符与栈顶字符的优先级*/ { '>' : push(S,*expr); expr ++; break; '=':pop (S, &ch); expr ++; break; '<' : pop (S, &ch); enqueue(Q , ch); } } } while(!IsEmptyStack(S)) /*原字符串遇到'\0'时，在栈中的操作符依次出栈，入队*/ { pop (S, &ch); enqueue(Q , ch); } while ( ! IsEmptyQueue (Q) )/*将队列中的内容按顺序出队，写入字符串result*/ { dequeue (Q,&ch); *result = ch; result ++; } *result = '\0'; } 3.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（不设头指针），试编写相应的队列初始化，入队列，出队列的算法。 注意：这是链式存储结构。 typedef struct node { Elemtype data; struct node *next; } Node, *LinkList; InitQueue ( LinkList Q ) { Q=malloc(sizeof(Node) ); Q->next = Q; } EnQueue(LinkList Q ,Elemtype x) { Node * p; p=malloc(sizeof(Node) ); p->data=x; p->next = Q->next; Q->next = p; Q = p; } DeQueue (LinkList Q ,Elemtype * x) { Node * p; p = Q->next->next; Q->next->next = p->next; *x = p->data; free(p); } 4.要求循环队列不损失一个空间全部都能得到利用，设置一个标志域tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 typedef struct { datatype data[MAX]; int f; int r; int tag;// 标志域 }seqqueue; 解法1、（设f指向队首，r指向队尾,则用tag区别f=r时，是空队还是只有一个元素的非空队,即tag=0表示空队，tag=1时表示所有非空情况，当(Q->r+1)%MAX == Q->f时表示队满；入队时，队尾指针后移，但入第一个元素时，队首指针也指向这唯一元素；出队时，队首指针后移，但当队列出到空时，两个指针都不移动） enterqueue(seqqueue *Q,datatype x) { if ( (Q->r+1)%MAX == Q->f ) {队满，退出} else { Q->r = (Q->r+1)%MAX; Q->data[Q->r] = x; if (tag==0 ) { Q->f = Q->r ; //新元素也是队首 Q->tag = 1; //空队变为非空队 } } } deletequeue(seqqueue *Q,datatype * x) { if ( Q->tag==0 ) {队空，退出} else { *x = Q->data[Q->f]; if (Q->f == Q->r)//只有一个元素的队列,因含在else分支中，条件Q->tag==1的判断可省略 { Q->f = (Q->f+1)%MAX ; Q->r = Q->f ; Q->tag = 0 ; } else { Q->f = (Q->f+1)%MAX; } } } （设f指向队首，r指向队尾,则用tag区别(r+1)%MAX = f 时，是队满还是队空,即tag=0解法2、 表示所有非满的队列，tag=1时表示队满情况，当(Q->r+1)%MAX == Q->f且tag=1时表示队满；当(Q->r+1)%MAX == Q->f且tag=1时表示队空;入队时，队尾指针后移；出队时，队首指针后移; 应当注意：此种情况下，应设初始化时，Q->f=1;Q->r=0；Q->tag=0，以与队列删除到空时的状态一致） enterqueue(seqqueue *Q,datatype x) { if ( (Q->tag==1 ) {队满，退出} else { Q->r = (Q->r+1)%MAX; Q->data[Q->r] = x; if ((Q->r+1)%MAX == Q->f) Q->tag==1; } } deletequeue(seqqueue *Q,datatype * x) { if ( Q->tag==0 && (Q->r+1)%MAX == Q->f ) { 队空，退出} else { *x = Q->data[Q->f]; Q->f = (Q->f+1)%MAX; if (Q->tag == 1)//若原队为满状态 { Q->tag = 0; //出队元素后，队为非满状态 } } } （设f指向队首，r指向队尾的下一个位置，与课本设置方法一致,则用tag区别f=r 时，解法3： 是队满还是队空,即tag=0表示队空，tag=1时表示队满，当Q->r == Q->f且tag=0 时表示队空；当Q->r== Q->f且tag=1时表示队满;入队时，队尾指针后移；出队时，队首指针后移） enterqueue(seqqueue *Q,datatype x) { if ( (Q->tag==1&& Q->f==Q->r ) {队满，退出} else { Q->data[Q->r] = x; //新元素入队尾指针当前位置 Q->r = (Q->r+1)%MAX;//队尾指针后移 if (Q->f == Q->r ) //因入队至队满 { Q->tag=1; } } } deletequeue(seqqueue *Q,datatype * x) { if ( Q->tag==0 ) { 队空，退出} else { *x = Q->data[Q->f]; Q->f = (Q->f+1)%MAX; if (Q->f == Q->r)//因出队而队空 { Q->tag = 0; } } } 第三部分:串 顺序串的定义: typedef struct { char ch[maxsize]; int len; /*表示长度,最后一个元素的下标为len-1*/ }string; (1)将顺序串r中的所有值为ch1的字符换成ch2. string replace(string *r,char ch1,char ch2) { for( i=0;i if (r->ch[i]==ch1) r->ch[i]=ch2; return r; } 要点: 1.顺序串的内容被修改,形参一定是顺序串的地址,所以r为指针类型,且在函数体内的引用一定是"r->" 2.注意本题参数有三个:顺序串,字符1,字符2.都是已知量,而且顺序串将被修改.又是结果.所以可以将顺序串做为返回值(也可以不用返回值,一样可以得到结果,但有返回值时,这个函数就可以放在表达式中被嵌套调用了). (2).串r 中所有字符按照相反的次序仍存放在r 中. 解法1: string changed(string *r) { for (i=0 ; i < (r->len)/2 ; i++ ) { t = r->ch[i]; r->ch[i] = r->ch[r->len-i-1]; r->ch[r->len-i-1] = t; } return r; } 要点: 1.函数只有一个参数:r ,为已知量,而且也是结果. 解法2.. 这样解也可以: 用两个下标,分别指向第一个元素,最后一个元素,两者交换后,两个下标再重新取值.一个递增,一个递减. string changed(string *r) { for (i=0,j=r->len -1 ; i < (r->len)/2 ; i++,j-- ) { t = r->ch[i]; r->ch[i] = r->ch[j]; r->ch[j] = t; } return r; } 解法3..如下的解法也可以,但是既花时间,又付出空间 string changed(string *r) { string s ; /*注意此时,s不能设为指针类型*/ for ( i=r->len -1 ,j=0; i>=0 ; i--,j++ ) s.ch[j]= r->ch[i]; for (i=0 ;i< s.len ; i++ ) r->ch[i]=s.ch[i]; return r; } (3) 从顺序串r中删除其值等于ch的所有字符 解法一: delete (string *r, char ch) { string s; for (i=0,j=0; i s.ch[j++] = r->ch[i]; for (i=0 ; i r->ch[i] = s.ch[i]; /*把s的内容写回到r中*/ r->len = j; /*修改r的表长*/ } 解法二: delete (string *r, char ch) { for (i=0 ; i< r->len ; ) if( r->ch[i] != ch ) /* 值非ch的字符,继续取下一个字符判断*/ i++; else /*值为ch的字符,要被删除*/ { for(j=i+1;j r->ch[j-1]=r->ch[j]; r->len --; /*修改表长*/ /*注意,删除后,下标为i的元素是一个没有判断过的新元素,不能i++*/ } } (4) 从顺序串r1中第index个字符起求出首次与串r2相同的子串的起始位置 解法一: int locate(string *r1 , int index , string * r2) { /*判断从下标为i开始的,字符串的长度为r2->len的字符串是否与r2字符串相同,若相同,i+1为串r2在主串r1中的起始地址,i 表示下标,所以初值为index-1,最后一个可以比较的字符串起始下标为r1->len - r2->len*/ for ( i = index -1 ; i<=( r1->len - r2->len) ; i++) { for( j = i , k =0 ; j < r2->len ; j ++) if (r1->ch[j] != r2->ch[k]) break; if ( j >= r2->len) return ( i+1 ) ; /*i表示与r2匹配的字符串的起始的下标,位序是i+1*/ } return ( 0 ) ; /*若外层循环能结束,遇到此语句,表示没有与r2相同的子串*/ } 解法二: int locate(string *r1 , int index , string * r2) { for ( i= index -1 ; i<=( r1->len - r2->len) ; ) { for( j = 0 ; j < r2->len ; j ++ , i ++ ) if (r1->ch[i] != r2->ch[j]) break; if ( j = = r2->len) return ( i-j +1 ) ; /*i-j表示与r2匹配的字符串的起始的下标,位序是i-j+1*/ else i = i-j+1; /*回退j个字符,从下一个开始,重新与r2比较*/ }/*注意:比较过程中,一次比较字符不相同,即表示从第i个字符开始的子串与r2不相同.而比较r2->len次都相同,即内层for循环执行r2->len次,才能表示从找到与r2 相同的子串.因此不能直接在内层for循环的if 语句后直接加else*/ return 0 ; /*若外层循环能结束,遇到此语句,表示没有与r2相同的子串*/ } (5) 从顺序串r中删除所有与串r1相同的子串. 解法一: void delete( string * r , string * r1) { for ( i = 0 ; i <= (r->len - r1->len) ; ) { j = locate ( r , i+1 , r1 ) ; /*调用第4小题的函数,求字符串r中从第i+1个位置开始,首次与r2匹配的字符的位序,位序为j */ if ( j != 0 ) /*找到,从r中删除r1,*/ { len = r1-> len ; for ( k = j-1 + len2 ; k < r1->len ; k ++) r1->ch[k - len2 ] = r1->ch[k]; r-> len = r->len - r1->len; i = j -1 ; /* 删除后,第j个位置上是一个新的字符,再次的搜索子串从此位置开始.*/ } else break ; /*若没找到,表示没有可以删除的子串,结束算法,*/ } } 解法二: void delete( string * r , string * r1) { for ( i = 0 ; i <= (r->len - r1->len) ; ) { for ( kr = i ,kr1 = 0 ; kr1 < r1->len ; kr1++ )/*查找子串*/ if ( r->ch[ kr ] != r1->ch[ kr1 ] ) break ; if ( kr1 >= r1->len ) /*从第i个下标开始的子串,与r2相同,从r 中第i个下标开始的字符串被删除.*/ { for ( k = i + r1->len ; k < r1->len ; k ++) r->ch[k - r1->len ] = r->ch[k]; r-> len = r->len - r1->len ; /* 删除后,第i个位置上是一个新的字符,再次的搜索子 串从此位置开始.所以i不能重新取值*/ } else i ++; /*第i个位置开始的子串不是r1,则从下一个字符再开始判断*/ } } 解法三: void delete( string * r , string * r1) { for ( i = 0 ; i <= (r->len - r1->len) ; ) { for ( j = 0 ; j < r1->len ; j++ )/*查找子串*/ if ( r->ch[ i ] != r1->ch[ j ] ) break ; if ( j >= r1->len ) /*从第i-j个下标开始的子串,与r2相同,从r中 第i-j个下标开始的字符串被删除.*/ { for ( k = i ; k < r1->len ; k ++) r->ch[k - r1->len ] = r->ch[ k ]; r-> len = r->len - r1->len ; /* 删除后,第i-j个位置上是一个新的字符,再次的搜索 子串从此位置开始.*/ i = i - j; } else i = i - j + 1 ; /*第i-j个位置开始的子串不是r1,则从下一个字符再开始判断*/ } } 4.10实现顺序串的基本操作strcompare( s,t ) int strcompare (string * s , string * t ) { for ( i=0 ; i < s->len && i< t->len && s->ch[i] == t->ch[i] ; i++ ) ; if ( i< s->len && i< t->len ) /*循环结束，根据不同的结束条件判断*/ return (s->ch[i] – t->ch[i] ) ; else if ( i< s->len && i>=t->len) return (s->ch[i]); else if (i>= s->len && i< t->len) return (0 – t->ch[i]); else return 0; } 第四部分数组 5.1：假设有6×8的二维数组A，每个元素占用6个字节，存储器按字节编址，已知A的基地址是1000，计算： （1）数据A共占用多少字节。 （2）数据A的最后一个元素的地址。 （3）按行存储时元素a36 的地址。 （4）按列存储时元素a36 的地址。 解：（1）元素总数6×8＝48个，每个占6个字节，共占用6×48＝288个字节。 （2）最后一个元素的地址，无论是按行序为主序，还是按列序为主序，最后一个元素之前都要存储48-1个元素。这些元素共占用：47×6＝282个存储单元。基地址为1000，故最后一个元素的地址是：1000＋282＝1282. 注意：计算时不能按1000＋288-6＋1的方法来计算这个地址。因为，288个元素，地址是0～277. （3）1000＋（（3-1）×8＋（6-1））×6＝1126 （4）1000＋（（6-1）×6＋（3-1））×6＝1192 注意：1000没有指明单位，不是16进制，按十进制运算。若指明1000H，需要用十六进制运算。 5.2设有三对角矩阵An×n，将其三条对角线上的元素逐行存于数组B［1..3n-2］中使得B ［k］＝aij求： (1)用i,j表示k 的下标变换公式 （2）用k表示i,j的下标变换公式 解：(1) 三对角矩阵中每行3个对角线元素，第一行和最后一行有2个对角线元素。 aij 是第i行，前共有（i-1）行，有(i-1)*3-1个元素。 是第j列，当前行：j=i-1是本行第一个元素，j=i是第二个，j=i＋1是第三个。所以第j列元素是本行的第j-i+2个元素。 由此，aij 是第(i-1)*3-1+j-i+2 = 2i+j-2 = 2(i-1)+j个元素。即k=2(i-1)+j (2) 三对角矩阵中，3的整数倍的元素，是每行的第一个，即k%3=0时，表示的元素特征是j=i-1.其后的元素k+1,k+2,同在一行上。此时k,k+1,k+2，做k/3运算是相等的。但k%3的值分别是0，1，2。 ???=+=??? ?-=+-==3 /1 3/1)1(203%k j k i i j j i k k 时：当 相邻的下一个元素是：?? ?+=+==1 3/1 3/13%k j k i k 时：当 同一行的最后一个元素是：? ? ?+=+==23/1 3/23%k j k i k 时：当 故可得到：?? ?+=+=3 %3/1 3/k k j k i 5.3假设稀疏阵A 和B 均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C 存放结果矩阵。 typedef struct { int row,col; ElementType e; }Triple; typedef struct { Triple data[Maxsize+1]; int m,n,len; }TSMatrix;//三元组表定义 TSMatrix Add (TSMatrix A,TSMatrix B) //三元组表相加，C=A+B { TSMatrix C; int Ai,Bi;//Ai,Bi 分别为A 表和B 表的非零元数组的下标 Ai=1; Bi=1; C.m=A.m; C.n=A.n; C.len=0; while(Ai<=A.len && Bi<=B.len) { C.len++; if (A.data[Ai].row Ai++; } else if (A.data[Ai].row>B.data[Bi].row) { C.data[C.len].row=B.data[Bi].row; C.data[C.len].col=B.data[Bi].col; C.data[C.len].e=B.data[Bi].e; Bi++; } else if (A.data[Ai].col { C.data[C.len].row=A.data[Ai].row; C.data[C.len].col=A.data[Ai].col; C.data[C.len].e=A.data[Ai].e; Ai++; } else if (A.data[Ai].col>B.data[Bi].col) { C.data[C.len].row=B.data[Bi].row; C.data[C.len].col=B.data[Bi].col; C.data[C.len].e=B.data[Bi].e; Bi++; } else { if (A.data[Ai].e+B.data[Bi].e!=0) { C.data[C.len].row=A.data[Ai].row; C.data[C.len].col=A.data[Ai].col; C.data[C.len].e=A.data[Ai].e+B.data[Bi].e; } Ai++; Bi++; } } while(Ai<=A.len) { C.len++; C.data[C.len].row=A.data[Ai].row; C.data[C.len].col=A.data[Ai].col; C.data[C.len].e=A.data[Ai].e; Ai++; } while(Bi<=B.len) 根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。要求新生成的链表中不允许有重复元素。 算法如下 ListNode * Merge ( ListNode * L1, ListNode * L2 ) {//根据两个带表头结点的有序单链表L1和L2, 生成一个新的有序单链表 ListNode *first = new ListNode; ListNode *p1 = L1->link, *p2 = L2->link, *p = first, *q; while ( p1 != NULL && p2 != NULL ) { q = new ListNode; if ( p1->data == p2->data ) { q->data = p1->data; p2 = p2->link; p1 = p1->link; } else if ( p1->data < p2->data ) { q->data = p1->data; p1 = p1->link; } else { q->data = p2->data; p2 = p2->link; } p->link = q; p = q; } while ( p1 != NULL ) { q = new ListNode; q->data = p1->data; p1 = p1->link; p->link = q; p = q; } while ( p2 != NULL ) { q = new ListNode; q->data = p2->data; p2 = p2->link; p->link = q; p = q; } p->link = NULL; return first; } 2． 设有一个线性表(e0, e1, …, e n-2, e n-1) 存放在一个一维数组A[arraysize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为(e n-1, e n-2, …, e1, e0)。 数组原地逆置算法 参数表中给出数组A[ ] 及指定的数组中前n个元素，函数执行后从A[ ] 中得到数组原地逆置后的结果。 Template 6.27 [问题] 假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。[解答] [问题] 假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。 [问题] 试利用栈的基本操作写出先序遍历二叉树的非递归算法。 [解答提示] 改写教材p.130-131算法6.2或6.3。 将if (!visit(p->data)) return ERROR;提前。 6.43 [问题] 编写递归算法，将二叉树中所有结点的左、右子树相互交换。 Status Exchange-lr(Bitree bt){ //将bt所指二叉树中所有结点的左、右子树相互交换 if (bt && (bt->lchild || bt->rchild)) { bt->lchild<->bt->rchild; Exchange-lr(bt->lchild); Exchange-lr(bt->rchild); } return OK; }//Exchange-lr 6.45 [问题] 编写递归算法，对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 [解答] Status Del-subtree(Bitree bt){ //删除bt所指二叉树，并释放相应的空间 if (bt) { Del-subtree(bt->lchild); Del-subtree(bt->rchild); free(bt); } return OK; }//Del-subtree Status Search-del(Bitree bt, TelemType x){ //在bt所指的二叉树中，查找所有元素值为x的结点，并删除以它为根的子树 if (bt){ if (bt->data=x) Del-subtree(bt); else { Search-Del(bt->lchild, x); Search-Del(bt->rchild, x); } } return OK; }//Search-Del 第六章树和二叉树 6.33 int Is_Descendant_C(int u,int v)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0 { if(u==v) return 1; else { if(L[v]) if (Is_Descendant(u,L[v])) return 1; if(R[v]) if (Is_Descendant(u,R[v])) return 1; //这是个递归算法 绪论第1章 √(2)×(3)2.(1)×C ）C（3（1）A（2）3. 的语句频度5.计算下列程序中x=x+1for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 的语句频度为：【解答】x=x+1=n(n+1)(n+2)/6 ）+……+（1+2+……+n）T(n)=1+(1+2)+（1+2+3 并确定算法中每一),p(xx+ax+a+…….+ax的值6.编写算法，求一元多项式p(x)=a n20nn20n1规定算法中不能使用要求时间复杂度尽可能小，语句的执行次数和整个算法的时间复杂度，算法的输入和输出)。n,输出为P(x求幂函数。注意：本题中的输入为a(i=0,1,…n)、x和0in采用下列方法1）通过参数表中的参数显式传递（）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实（2 现输入输出。【解答】1）通过参数表中的参数显式传递（优点：当没有调用函数时，不占用存，调用结束后形参被释放，实参维持，函数通用 性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。 ）通过全局变量隐式传递（2 优点：减少实参与形参的个数，从而减少存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数PolyValue() { int i,n; float x,a[],p; nn=”);printf(“\ scanf(“%f”,&n); nx=”);printf(“\ scanf(“%f”,&x); for(i=0;i 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 （2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A．存储结构B．存储实现 C．逻辑结构D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列B.链表C.有序表D.链栈 （6）以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i [当堂达标] 1．我们已学过的算法有一元二次方程的求根公式、加减消元法求二元一次方程组的解、二分法求函数零点等，对算法的描述有： ①对一类问题都有效； ②对个别问题有效； ③计算可以一步一步进行，每一步都有唯一结果； ④是一种通法，只要按部就班地做，总能得到结果． 以上描述正确的有( ) A ．1个 B ．2个 C ．3个 D ．4个 答案：C 解析：设计的算法应该是对一类问题都有效，而不是只对个别问题有效．所以①对，②不对．由算法的确定性、有限性、顺序性易知③④都是正确的，故描述正确的有3个． ； 2．下列所给问题中，不能设计一个算法求解的是( ) A ．用二分法求方程x 2－3＝0的近似解(精确到 B ．解方程组????? x ＋y ＋5＝0，x －y ＋3＝0 C ．求半径为2的球的体积 D ．判断y ＝x 2在R 上是否具有单调性 答案：D 解析：选项A ，B ，C 中的问题都可以设计算法求解，而D 项中的问题则不能设计算法求解． 3．“已知直角三角形两直角边长为a ，b ，求斜边长c ”的一个算法分下列三步： ①计算c ＝a 2＋b 2； ②输入直角三角形两直角边长a ，b 的值； ③输出斜边长c 的值． : 其中正确的顺序是________． 答案：②①③ 解析：根据运算顺序，易知算法顺序应是②①③. 4．已知一个学生的语文成绩为89，数学成绩为96，外语成绩为99，求它的总分和平均分的一个算法如下，请将其补充完整： 第一步：取A ＝89，B ＝96，C ＝99. 第二步，_____________________________________________. 第三步，_____________________________________________. 第四步，输出计算结果． 答案：计算总分D ＝A ＋B ＋C 计算平均分E ＝D 3 5．已知函数y ＝????? －x 2－1x ≤－1，x 3x >－1，试设计一个算法，输入x 的值，求对应的函数值． ^ 解：算法如下： 第一步，输入x 的值； 第二步，当x ≤－1时，计算y ＝－x 2－1，否则执行第三步； 第三步，计算y ＝x 3； 第四步，输出y . [课堂小结] 1．算法的特点：有限性、确定性、逻辑性、不唯一性、普遍性． 2．算法设计的要求： (1)写出的算法必须能够解决一类问题(如判断一个整数是否为质数，求任意一个方程的近似解等)，并且能够重复使用． 第1章绪论工程大数电习题答案册工程大数电习题答案 册 2.(1)×(2)×(3)√ 3.（1）A（2）C（3）C 5.计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 6.编写算法，求一元多项式p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法 （1）通过参数表中的参数显式传递 （2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i 第一章答案 1.3计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 1.4试编写算法，求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执 行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i 数据结构试卷（一） 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式 为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 习题一复杂性分析初步 1. 试确定下述程序的执行步数，该函数实现一个m×n矩阵与一个n×p矩阵之间的乘法： 矩阵乘法运算 template 找最大最小元素 方法一 template 第一章习题答案 2、××√ 3、（1）包含改变量定义的最小范围 （2）数据抽象、信息隐蔽 （3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型 （5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作 （9）有限性、输入、可行性 4、（1）A（2）C（3）C 5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定 （4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A B：H、L、I、E、A C：F、M D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C 3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。 头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首元素结点：线性表中的第一个结点成为首元素结点。 4、算法如下： int Linser(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf(“表已满无法插入”)； return(0); } while(i<=L->last&&L->elem[i] L->last++; return(1); } 5、算法如下： #define OK 1 #define ERROR 0 Int LDel(Seqlist *L,int i,int k) { int j; if(i<1||(i+k)>(L->last+2)) { printf(“输入的i，k值不合法”); return ERROR; } if((i+k)==(L->last+2)) { L->last=i-2; ruturn OK; } else {for(j=i+k-1;j<=L->last;j++) elem[j-k]=elem[j]; L->last=L->last-k; return OK; } } 6、算法如下： #define OK 1 #define ERROR 0 Int Delet(LInkList L,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink 数据结构复习题 第一章概论 一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是( A )。 A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 fori0;im;i++ forj0;jn;j++ a[i][j]i*j; A. Om2 B. On2 C. Om*n D. Om+n 6、算法是( D )。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。 A. On B. Onlog2n C. On2 D. Olog2n 8、下面程序段的时间复杂度为( C )。 i1; whilein ii*3; A. On B. O3n C. Olog3n D. On3 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是( A )。 is0; whilesn i++;s+i; A. On B. On2 C. Olog2n D. On3 11、抽象数据类型的三个组成部分分别为( A )。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在 叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图是这条河以及河上的两个岛和七座桥的草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 图 七桥问题 南区 3 输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。 编写程序，求n至少为多大时，n个“1”组成的整数能被2013整除。 #include 《算法与数据结构》习题1 第一部分 一、单项选择题 1.（）二叉排序树可以得到一个从小到大的有序序列。 A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 2.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i 结点的左孩子结点的编号为（）。 A、2i+1 B、2i C、i/2 D、2i-1 3.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序 列为（）。 A、q=p->next；p->data=q->data；p->next=q->next；free(q)； B、q=p->next；q->data=p->data；p->next=q->next；free(q)； C、q=p->next；p->next=q->next；free(q)； D、q=p->next；p->data=q->data；free(q)； 4.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得 到序列为（）。 A、BADC B、BCDA C、CDAB D、CBDA 5.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。 A、n B、n-1 C、m D、m-1 6.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。 A、O(1) B、O(log2n) C、O(nlog2n) D、O(n2) 7.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A、25 B、10 C、7 D、1 二、填空题 1.设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A 的后面插入结点X的操作序列为______=p；s->right=p->right；______=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为______。 3.设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为 3的结点数有______个。 4.后缀算式9 2 3 + - 10 2 / -的值为______。中缀算式（3+4X）-2Y/3对应的后缀算式 为______。 5.设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第______个元 素开始进行筛选。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 计算机算法设计与分析习 题及答案 Prepared on 24 November 2020 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 第一章绪论 1.数据：人们利用文字符号、数字符号及其他规定的符号对现实世界的事物及其活动的描述。凡是能被计算机输入、存储、处理和输出的一切信息都叫数据。 2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据元素的组成：一个数据元素通常由一个或若干数据项组成。 数据项：指具有独立含义的最小标识单位。 3.数据对象：性质相同的数据元素的集合，是数据的一个子集。 4.数据结构：研究的是数据的逻辑结构和物理结构，以及它们之间的相互关系和所定义的算法在计算机上运行的学科。 5.算法：是对待定问题求解步骤的一种描述，是指令的有限序列。算法应满足以下性质： 1)输入性：具有零个或若干个输入量； 2)输出性：至少产生一个输出； 3)有穷性：每条指令的执行次数是有限的； 4)确定性：每条指令的含义明确，无二义性； 5)可行性：每条指令都应在有限的时间内完成。 6.评价算法优劣的主要指标： 1)执行算法后，计算机运行所消耗的时间，即所需的机器时间； 2)执行算法时，计算机所占存储量的大小，即所需的存储空间； 3)所设计的算法是否易读、易懂，是否容易转换成其他可运行的程序语言。 7.会估算某一算法的总执行时间和时间复杂度。 8.熟悉习题P32:3(5)-(9)、4(2)(3) 第二章线性表 1.线性表(P7)：是性质相同的一组数据元素序列。 线性表的特性： 1)数据元素在线性表中是连续的，表中数据元素的个数可以增加或减少，但调整后数据元素仍必须是连续的，即线性表是一种线性结构。 2)数据元素在线性表中的位置仅取决于自己在表中的序号，并由该元素数据项中的关键字(key)加以标识。 3)线性表中所有数据元素的同一数据项，其属性是相同的，数据类型也是一致的。 线性表的主要运算有：插入、删除、查找、存取、长度、排序、复制、合并。 线性表的顺序存储结构及特点(就是把表中相邻的数据元素存放在内存邻接的存储单元，这种存储方法叫做顺序分配，又称顺序映像。其特点：逻辑上相邻的数据元素， 它们的物理次序也是相邻的。)，存储地址的计算方式(Loc(a i )=Loc(a )+i*s)。 2.线性表的查找、插入和删除 熟悉线性表的查找算法(P38)、插入算法(P39)和删除算法(P40)。 3.理解线性表的顺序存储结构的优缺点。 4.熟悉线性链表的存储结构(P43) 线性链表(由若干结点链接而成的一种存储结构。)、结点(由存放数据元素值的部分—数据域和存放另一元素存储地址的部分—指针域或链域两部分信息组成的存储结构。)、单链表(线性链表)的概念。 5.熟悉线性链表的建立(P45-47)、查找(P47-48)、插入(P49-50)和删除(P50-51)的算法； 6.明了什么是循环链表(链表中最后一个结点指针域回指向链表的第一个结点，使得整个链表通过链指针成为一个环形，这种形式的链表称为循环链表。)？ 7.明了双向链表的结构(链表中的每个结点有两个指针域，一个是向前链接的左指针(Lnext或prior)，另一个是向后链接的右指针(Rnext或next)，同时还有一个数据域(Data)。)；了解双向链表的插入和删除的算法。 8.理解链表的优缺点(P48)。 9.熟悉习题P68：1、2 第三章限定性线性表----栈和队列 1.栈和队列 明确什么是栈及其特点(只允许在一端进行插入和删除的线性表。允许插入和删除 算法分析习题参考标准答案 ————————————————————————————————作者：————————————————————————————————日期： 习题一复杂性分析初步 1. 试确定下述程序的执行步数，该函数实现一个m×n矩阵与一个n×p矩 阵之间的乘法： 矩阵乘法运算 template 找最大最小元素 方法一 template 第1章绪论 1．4 试编写算法，求一元多项式P n(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入a i(i=0,1,…,n),x和n，输出为P n(x0)。通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。void polyvalue() { int n,p,i,x,xp,sum; float a[]; float *p=a; printf("Input number of terms:"); scanf("%d",&n); printf("Input the %d coefficients from a0 to a%d:\n",n,n); for(i=0;i<=n;i++) scanf("%f",p++); printf("Input value of x:"); scanf("%f",&x); p=a;xp=1;sum=0; //xp用于存放x的i次方 for(i=0;i<=n;i++) { sum+=xp*(*p++); xp*=x; } printf("Value is:%f",sum); }//polyvalue 第二章线性表 2．4设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中 { if(va.length+1>va.listsize) return ERROR; va.length++; for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; return OK; }//Insert_SqList 2．6已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。算法题目及答案
数据结构习题答案 耿国华主编 第六章
最全数据结构课后习题答案耿国华版
数据结构与算法习题及答案
1-1算法的概念练习题及答案
最全数据结构课后习题答案(耿国华版[12bb]
耿国华数据结构习题答案完整版
算法与数据结构试题及答案
算法分析习题参考标准答案
(完整版)数据结构---C语言描述-(耿国华)-课后习题答案
数据结构与算法复习题库含答案
算法设计与分析习题答案1-6章
算法与数据结构习题
计算机算法设计与分析习题及答案
《数据结构(C语言-耿国华版)》复习大纲
算法分析习题参考标准答案
数据结构部分答案耿国华2
相关主题
文本预览