- 相關(guān)推薦
大學數(shù)據(jù)結(jié)構(gòu)課后習題答案
參考答案
第一章、緒論
一、選擇題 1 B；2 A； 3 B； 4 C ；5 C； 6 B；7 C；8 C； 9 D； 10 B。
二、填空題1、存儲 ；2、無 ，1，無，1； 3、前驅(qū)，1，后繼，任意多個；4、一對一，一對多，多對多；5、時間復雜度，空間復雜度；6、集合，線性結(jié)構(gòu)，樹形結(jié)構(gòu)，圖形結(jié)構(gòu)；
7、順序結(jié)構(gòu)，鏈式結(jié)構(gòu)，索引結(jié)構(gòu)，散列結(jié)構(gòu)；8、順序。
三、問答題與算法題
1、3 ；
2、T1 ( n ) = 5n 2 -O ( n ) ; T2 ( n ) = 3 n 2 + O ( n ) ; T3 ( n ) = 8 n 2 + O(log n) ; T4 ( n ) = 1.5 n 2 + O ( n ) 。T4 ( n ) 較優(yōu)，T3 ( n )較劣。
3、見課本。
第二章 線性表
一、選擇題 1C；2A；3D；4B；5D；6B；7C；8B；9A；10C；11D；12D；13C；14C.
二、填空題 1、O ( 1 ), O ( n )；2、單鏈表，雙鏈表；3、地址，指針；4、4，2；5、便于訪問尾結(jié)點和頭結(jié)點；6、前驅(qū)；7、L->next== L且L->prior== L；8、順序。
三、問答題與算法題
1、頭指針：結(jié)點或頭結(jié)點的指針變量。其作用是存放第一個結(jié)點或頭結(jié)點的地址，從頭指
針出發(fā)可以找到鏈表中所有結(jié)點的信息。
頭結(jié)點：是附加在鏈表的第一個結(jié)點之前的一個特殊結(jié)點，其數(shù)據(jù)域一般不存放信息。
其作用是為了簡化運算，將空表與非空表統(tǒng)一起來，將第一個結(jié)點與其他結(jié)點的處理統(tǒng)一起來。
首結(jié)點：是鏈表的第一個結(jié)點。
2、(1)基于空間的考慮。當要求存儲的線性表長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表；反之，當線性表長度變化大，難以估計其存儲規(guī)模時，采用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。
(2)基于時間的考慮。若線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順序表做存儲結(jié)構(gòu)為宜；反之， 若需要對線性表進行頻繁地插入或刪除等的操作時，宜采用鏈表做存儲結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。
3、尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點和終端結(jié)點的位置分別是rear->next->next 和 rear, 查找時間都是O(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n)
4、S=P->Prior; P->Prior=S->Prior; S->Prior->Next=P; S->Prior=P; S->Next=P->Next; P->Next=S;S->Next->Prior=S;
5、:將開始結(jié)點摘下鏈接到終端結(jié)點之后成為新的終端結(jié)點，而原來的第二個結(jié)點成為新的開始結(jié)點，返回新鏈表的頭指針
6、15，26，51，37，48，,55。
7、CreatList_L(LinkList &L int n) {
L= (LinkList) molloc (sizeof (Lnode));//頭結(jié)點
L->next==NULL; q=L;
For(i=1;i<=n;++i)
41
{ P= (LinkList) molloc (sizeof (Lnode));
Scanf(&(p->data));
p->next=NULL; q->next=p; q=p;}
returen OK;
}
8、Void s(Sqlist &S, int x)
{int i=0; n=S.Length;
while(x<S.elem[i]&& i<n) i++; //查找插入點
if(i==n) S.elem[n]=x; //插在最后一個結(jié)點的后面
else {for(j=n-1;j>=i;j++)
S.elem[j+1]=S.elem[j]; //元素后移
S.elem[i]=x; //插入
}
}
9、int ListLength(LinkList L)
{q=L->next; i=0;
while(q)
{i++; q=q->next; }
return i;
10、int (LinkList &L, int x) {
p=L->next; //p為定位指針
q=L; //q為定位指針的前導
while((p->data!=x) && p)
{ q=p; //q前進
p=p->next; //p前進
}
if(!q) return ERROR; //查找失敗
q->next=p->next ;
free(p);
return OK;
}
11、void mergelist(linklist &La, linklist Lb)
{pa=La->next; pb=Lb->next;pc=La;
while (pa && pb)
if (pa->data< pa->data) {pc->next=pa;pc=pa;pa=pa->next;}
else if(pa->data== pa->data) {pc->next=pa; pc=pa; pa=pa->next; pb=pb->next;} else ({pc->next=pb;pc=pb;pb=pb->next;}
pc->next=pa? pb:pb;
}
12、Void invertlinklist(linklist &L)
{if(!L) return OK; //空表
p=L->next;
if(!p) return OK; //僅有一個結(jié)點的表
else{q=p->next; //q指向p的后繼
42
p->next=NULL;
while(q)
{ r=q->next ; //r指向q的后繼
q->next=p; //逆置
p=q; //p前進
q=r; //q前進
}
L=p; //第一個結(jié)點
}
}
13、Void delDuplicate(int A[]，int & n)
{ for(i=0;i<n-1;i++)
for(j=i+1;j<=n-1;j++)
if(a[i]==a[j])
{n--;
for(k=j+1;k<=n-1;k++)
a[k-1]=a[k];
}
}
第三章 棧和隊列
一、選擇題1A；2D；3C；4C；5D；6C；7C；8B；9C；10C；11Ｄ，Ｂ；12Ｄ；13Ｂ。
二、填空題
1、棧頂；2、滿，空，n；3、后進先出，先進先出；4、頭；5、L->next==NULL，S.top==S.base， S.top-S.base==S.stacksize，L==NULL，Q.front==Q.rear，（Q.rear＋１）%maxQsize ==Q.front;
6、Q.rear-Q.front+n)%n；7、1nC2n；8、n－１。 n?1
三、問答題與算法題
1、 １３２４；
2、(1) int push_L(Linkstack &s SelemType e)
{ p= (LinkStack) molloc (sizeof (Snode));
if(!p) return ERROR;
p->data=e;
p->next=s;
s=p;
Return Ok;
}
(2)int pop_L(Linkstack &s SelemType &e)
{ if(!S) return ERROR;
q=s;
e=s->data;
s=s->next;
free(q);
Retuen Ok;
}
43
3、(1)int EnQueue_L(Queueptr &QL QelemType e) { p= Queueptr} molloc (sizeof (Qnode));
if(!p) return ERROR;
p->data=e;
p->next=QL->next->next;
QL->next->next= p;
Retuen Ok;
}
(2)int DeQueue_L(Queueptr &QL QelemType &e) { if(QL->next==QL)} return ERROR;
p= QL->next
while(p->next!=QL) p =p->next;
p->next=QL->next;
e=QL->next;
free(QL);
QL=p;
Return Ok;
}
4、(1) 棧S元素反序存放；
(2) 把棧s1復制到s2；
(3) 把棧S中值等于m的元素刪除；
(4) 隊列Q元素反序存放;
(5) 鏈表中的元素反序存放；
5、Int hw4(LinkList L)
{ initstack(S);
bool=1;n=0;
p=L->next;
while(p){n++; p=p->next;} //求串長
p=L->next; //p指向第一個結(jié)點 for(i=0; i
while(p&&bool)
{pop(S,ch);
if(ch!=p->data) bool=0;
p=p->next;
}
return bool;
｝
6、void ClearStack( LinkStack &S)。
{while(!S)
{p=s;
s=s->next;
free(p);
44
}
return OK;
}
7、int Stacksize( LinkStack S)。
{ n=0;
p=s;
While(!p)
{n++;
p=p->next;
}
return n;
}
8、見４、(5)
第四章 串
一、選擇題
1 B；2B；３D；4 B；5C；6 D。
二、填空題
１、空格串；2、靜態(tài)分配的順序串、動態(tài)分配順序串、塊連串；3、?? 4、塊的大�。�
5、２；6、StrAssing，StrCompare，StrLength，Concat，SubString；7、13,6；8、模式，目標（主）。
三、問答題與算法題
1、 ●空串是指不包含任何字符的串，它的長度為零。
空格串是指包含一個或多個空格的串，空格也是字符, 長度不為零。
●串常量是指在程序中只可引用但不可改變其值的串。
串變量是可以在運行中改變其值的。
●主串和子串是相對的，一個串中任意個連續(xù)字符組成的串就是這個串的子串，而包含
子串的串就稱為主串。
●目標串和模式串:在串匹配運算過程中，將主串稱為目標串，而將需要匹配的子串稱為
模式串，兩者是相對的。
2、(１) "Stocktom, March51999"；(２) 正數(shù)；(３) 正數(shù)；(４)１８
3、void StrInsert(char *S, char *T, int i)
{//將串T插入到串S的第i個位置上
char *Temp;
if(i<=strlen(S))
{Temp=(char *)malloc(sizeof(char[Maxsize])); // 設(shè)置一個臨時串
strcpy(Temp,&S[i]); //將第i位起以后的字符拷貝到臨時串中
strcpy(&S[i], T); /將串T拷貝到串S的第i個位置處，覆蓋后面的字符
strcat(S,Temp); //把臨時串中的字符聯(lián)接到串S后面
free( Temp );
}
}
�。础oid StrDelete(char *S, int i , int m) //串刪除
{ char Temp[Maxsize]; //定義一個臨時串
if(i+m<strlen(S))
45
【大學數(shù)據(jù)結(jié)構(gòu)課后習題答案】相關(guān)文章：
雷雨課后習題答案12-09
《匆匆》課后習題答案12-09
童趣課后習題及答案12-09
善良課后習題答案12-08
《雷雨》課后習題答案12-09
社戲課后習題答案12-09
童趣課后習題答案12-09
《關(guān)雎》課后習題答案03-09