- 相關推薦
大學數據結構課后習題答案
參考答案
第一章、緒論
一、選擇題 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、前驅，1，后繼，任意多個；4、一對一，一對多，多對多；5、時間復雜度，空間復雜度；6、集合，線性結構，樹形結構，圖形結構；
7、順序結構，鏈式結構，索引結構，散列結構；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 ) 較優，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、便于訪問尾結點和頭結點；6、前驅；7、L->next== L且L->prior== L；8、順序。
三、問答題與算法題
1、頭指針：結點或頭結點的指針變量。其作用是存放第一個結點或頭結點的地址，從頭指
針出發可以找到鏈表中所有結點的信息。
頭結點：是附加在鏈表的第一個結點之前的一個特殊結點，其數據域一般不存放信息。
其作用是為了簡化運算，將空表與非空表統一起來，將第一個結點與其他結點的處理統一起來。
首結點：是鏈表的第一個結點。
2、(1)基于空間的考慮。當要求存儲的線性表長度變化不大，易于事先確定其大小時，為了節約存儲空間，宜采用順序表；反之，當線性表長度變化大，難以估計其存儲規模時，采用動態鏈表作為存儲結構為好。
(2)基于時間的考慮。若線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順序表做存儲結構為宜；反之， 若需要對線性表進行頻繁地插入或刪除等的操作時，宜采用鏈表做存儲結構。并且，若鏈表的插入和刪除主要發生在表的首尾兩端，則采用尾指針表示的單循環鏈表為宜。
3、尾指針是指向終端結點的指針，用它來表示單循環鏈表可以使得查找鏈表的開始結點和終端結點都很方便，設一帶頭結點的單循環鏈表，其尾指針為rear，則開始結點和終端結點的位置分別是rear->next->next 和 rear, 查找時間都是O(1)。若用頭指針來表示該鏈表，則查找終端結點的時間為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、:將開始結點摘下鏈接到終端結點之后成為新的終端結點，而原來的第二個結點成為新的開始結點，返回新鏈表的頭指針
6、15，26，51，37，48，,55。
7、CreatList_L(LinkList &L int n) {
L= (LinkList) molloc (sizeof (Lnode));//頭結點
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; //插在最后一個結點的后面
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; //僅有一個結點的表
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; //第一個結點
}
}
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指向第一個結點 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、靜態分配的順序串、動態分配順序串、塊連串；3、?? 4、塊的大小；
5、２；6、StrAssing，StrCompare，StrLength，Concat，SubString；7、13,6；8、模式，目標（主）。
三、問答題與算法題
1、 ●空串是指不包含任何字符的串，它的長度為零。
空格串是指包含一個或多個空格的串，空格也是字符, 長度不為零。
●串常量是指在程序中只可引用但不可改變其值的串。
串變量是可以在運行中改變其值的。
●主串和子串是相對的，一個串中任意個連續字符組成的串就是這個串的子串，而包含
子串的串就稱為主串。
●目標串和模式串:在串匹配運算過程中，將主串稱為目標串，而將需要匹配的子串稱為
模式串，兩者是相對的。
2、(１) "Stocktom, March51999"；(２) 正數；(３) 正數；(４)１８
3、void StrInsert(char *S, char *T, int i)
{//將串T插入到串S的第i個位置上
char *Temp;
if(i<=strlen(S))
{Temp=(char *)malloc(sizeof(char[Maxsize])); // 設置一個臨時串
strcpy(Temp,&S[i]); //將第i位起以后的字符拷貝到臨時串中
strcpy(&S[i], T); /將串T拷貝到串S的第i個位置處，覆蓋后面的字符
strcat(S,Temp); //把臨時串中的字符聯接到串S后面
free( Temp );
}
}
４、void StrDelete(char *S, int i , int m) //串刪除
{ char Temp[Maxsize]; //定義一個臨時串
if(i+m<strlen(S))
45
【大學數據結構課后習題答案】相關文章：
雷雨課后習題答案12-09
《匆匆》課后習題答案12-09
童趣課后習題及答案12-09
善良課后習題答案12-08
《雷雨》課后習題答案12-09
社戲課后習題答案12-09
童趣課后習題答案12-09
《關雎》課后習題答案03-09