算法與數(shù)據(jù)結(jié)構(gòu)線性表答案

算法與數(shù)據(jù)結(jié)構(gòu)線性表答案第2章線性表一、判斷題1線性關(guān)系的邏輯構(gòu)造與存儲構(gòu)造總是一致的。解：錯。單鏈表的邏輯構(gòu)造與存儲構(gòu)造有可能是不一致的，有可能兩個相鄰結(jié)點的存儲地址并不是相鄰的。2每種數(shù)據(jù)構(gòu)造都包括插入、刪除和查找這三種根本運算。解：錯。散列構(gòu)造無插入與刪除運算；棧沒有查找，查找須配有另一個棧。3線性表中的每個結(jié)點最多只有一個前驅(qū)和一個后繼。解：對。線性表的定義為：表中任意一個元素至多有一個前驅(qū)，至多有一后繼。4線性的數(shù)據(jù)構(gòu)造既可以順序存儲，也可以鏈接存儲；非線性的數(shù)據(jù)構(gòu)造那么只能鏈接存儲。解：錯。對于非線性的數(shù)據(jù)構(gòu)造，假設(shè)對它的數(shù)據(jù)規(guī)定某種次序之后，也可以順序存儲。如，樹的前、中、后序遍歷之后的存儲，一個前驅(qū)可能對應(yīng)多個后繼。5順序存儲方式只能用于存儲線性構(gòu)造。解：錯。非線性構(gòu)造也可采用順序存儲。6多維數(shù)組是向量的推廣。解：對。多維向量的存儲方式實際上與一維向量是一致的。7設(shè)串s的長度為n，那么s的子串個數(shù)最多為n(n+1)/2。解：錯。s的長度為n，故它含有n個字符，它的子串應(yīng)包括：1個字符的子串，2個字符的子串，…，n個字符的子串；這些子串的個數(shù)分別為8單鏈表從任何一個結(jié)點出發(fā)，都能訪問到所有結(jié)點。解：錯。單鏈表僅能從頭結(jié)點出發(fā)去訪問所有結(jié)點，不能訪問前驅(qū)。9線性表的長度是線性表所占用的存儲空間的大小。解：錯。線性表所占用的存儲空間大小為：每個結(jié)點所占用的存儲字節(jié)數(shù)乘以線性表的長度。10雙循環(huán)鏈表中，任意一結(jié)點的后繼指針均指向其邏輯后繼。解：錯。任意結(jié)點的后繼結(jié)點包含有兩個指針llink和rlink，只有rlink指向其邏輯后繼，而llink指向其邏輯前驅(qū)。11數(shù)據(jù)構(gòu)造、數(shù)據(jù)元素、數(shù)據(jù)項在計算機中的映象(或表示)分別稱為存儲構(gòu)造、結(jié)點、數(shù)據(jù)域。解：對。12線性表的順序存儲構(gòu)造優(yōu)于鏈?zhǔn)酱鎯?gòu)造。解：錯。各有優(yōu)缺點。順序存儲構(gòu)造的優(yōu)點是：〔1〕存儲效率高?！?〕可隨機訪問任意結(jié)點，存取速度快。順序存儲構(gòu)造的缺點是：〔1〕插入與刪除操作費事?！?〕順序表的長度擴大費事。鏈?zhǔn)酱鎯?gòu)造的優(yōu)點是：〔1〕插入與刪除方便?！?〕順序表的長度可任意〔動態(tài)分配內(nèi)存〕。鏈?zhǔn)酱鎯?gòu)造的缺點是：算法與數(shù)據(jù)結(jié)構(gòu)線性表答案全文共9頁，當(dāng)前為第1頁?！?〕存儲效率低?！?〕對結(jié)點的訪問不方便。算法與數(shù)據(jù)結(jié)構(gòu)線性表答案全文共9頁，當(dāng)前為第1頁。二、選擇題1假設(shè)長度為n的線性表采用順序存儲構(gòu)造，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為C，元素的挪動次數(shù)為F(0≤i≤n)。(A)．O(0)(B)．O(1)(C)．O(n)(D)．O(n2)(E)．n-i+1(F)．n-i(G)．i(H)．i-1解：選C與E。因為，需要第i個位置至第n個位置的n-i+1個元素向后逐一挪動，因此，共做n-i+1次賦值運算，故T(n)=n-i+1，即T(n)=O(n)。2在長度為n的順序存儲的線性表中，刪除第i個元素(0≤i≤n-1)時，需要從前向后依次前移C個元素。(A)．n-i(B)．n-i+1(C)．n-i-1(D)．i解：選C。因為前移元素的個數(shù)為n-i。3從解決問題的需要出發(fā)，為實現(xiàn)必要的功能所建立的數(shù)據(jù)構(gòu)造，稱為B。(A)．物理構(gòu)造(B)．邏輯構(gòu)造(C)．?dāng)?shù)據(jù)類型(D)．?dāng)?shù)據(jù)對象解：選B。4假設(shè)長度為n的線性表采用順序存儲構(gòu)造，在其第i(0≤i≤n)個位置插入一個新元素的平均挪動元素挪動次數(shù)為C，在其第i(0≤i≤n-1)個位置刪除一個元素的平均挪動元素挪動次數(shù)為D。(A)．n(B)．(n+1)/2(C)．n/2(D)．(n-1)/2解：選C。因為，在第0個位置插入新元素應(yīng)挪動n個元素，而在第1個位置插入新元素應(yīng)挪動n-1個元素，一般地，在第i(0≤i≤n)個位置插入一個新元素應(yīng)挪動n-i個元素，而在某個位置上插入新元素的概率為1/〔n+1〕，故平均挪動的次數(shù)為n/(n+1)+(n-1)/(n+1)+…+(n-i)/(n+1)+…+1/(n+1)+0/(n+1)=n/2選D。因為，在第0個位置刪除一個元素應(yīng)挪動n-1個元素，而在第1個位置刪除元素應(yīng)挪動n-2個元素，一般地，在第i(0≤i≤n-1)個位置刪除一個元素的應(yīng)挪動n-i-1個元素，而在某個位置上刪除元素的概率為1/n，故平均挪動的次數(shù)為(n-1)/n+(n-2)/n+…+(n-i-1)/n+…+1/n+0/n=(n-1)/25假設(shè)長度為n的無序線性表采用順序存儲構(gòu)造，在其中查找某個元素的平均比較的次數(shù)為D。(A)．n(B)．(n-1)/2(C)．n/2(D)．(n+1)/2解：選D。n個元素的排列方式有n!種，而某個指定元素排在第i個位置的種數(shù)為(n-1)!，故某個指定元素恰好排在第i個位置的概率為(n-1)!/n!=1/n。這說明，待查找的元素恰好排在第1個位置、第2個位置、…和第n個位置的概率均為1/n。假設(shè)待查找的元素排在第i個位置，那么查找的次數(shù)為i次〔1≤i≤n〕，故平均查找次數(shù)為1/n+2/n+…+i/n+…+n/n=(n+1)/26對于只在首、尾兩端進展插入操作的線性表，宜采用的存儲構(gòu)造為。(A)．順序表(B)．帶頭指針的單鏈表(C)．帶尾指針的單循環(huán)鏈表(D)．單鏈表解：選C。7在一個單鏈表中，假設(shè)要在指針q所指結(jié)點的后面插入一個由指針p所指向的結(jié)點，那么執(zhí)行。(A)．q->link=p->link；p->link=q；(B)．p->link=q->link；q=p；算法與數(shù)據(jù)結(jié)構(gòu)線性表答案全文共9頁，當(dāng)前為第2頁。(C)．q->link=p->link；p=q；(D)．p->link=q->link；q->link=p算法與數(shù)據(jù)結(jié)構(gòu)線性表答案全文共9頁，當(dāng)前為第2頁。解：選D。8在一個單鏈表HL中，假設(shè)要向表頭插入一個由指針p指向的結(jié)點，那么執(zhí)行。(A)．HL=p;p->next=HL;(B)．p->link=HL;HL=p;(C)．p->link=HL;p=HL;(D)．p->link=HL->link;HL->link=p;解：假設(shè)單鏈表不帶頭結(jié)點，那么應(yīng)選B。假設(shè)單鏈表帶頭結(jié)點，那么應(yīng)選D。9在一個單鏈表HL中，假設(shè)要刪除由指針q所指向結(jié)點的后繼結(jié)點，那么執(zhí)行。(A)．p=q->link;p->link=q->link;deletep;(B)．p=q->link;q->link=p;deletep;(C)．p=q->link;q->link=p->link;deletep;(D)．q->link=q->link->link;q->link=q;解：選C。假設(shè)選D，那么鏈表中沒有了q的后繼結(jié)點，但未刪除。僅C選項可使q的后繼結(jié)點被刪除，并按原有結(jié)點順序重新拉鏈。10設(shè)p為有頭結(jié)點雙向循環(huán)鏈表中某結(jié)點的指針，lLink為左鏈指針，rLink為右鏈指針，那么下述表達(dá)式中，不恒為真。(A)．p->rLink->lLink==p(B)．p->rLink->lLink==p->lLink->rLink(C)．p->lLink->rLink==p(D)．p->rLink->rLink==p->lLink->lLink解：選D。因為p->rLink->lLink==p==p->lLink->rLink，故只有D不一定為真。11假設(shè)某鏈表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，那么采用存儲方式最節(jié)省時間。(A)．單鏈表(B)．雙向鏈表(C)．帶頭結(jié)點的雙循環(huán)鏈表(D)．單循環(huán)鏈表解：選C。12鏈表不具有的特點是。(A)．可隨機訪問任一元素(B)．插入刪除不需要挪動元素(C)．不必事先估計存儲空間(D)．所需空間與線性表長度成正比解：選A。13線性表采用鏈?zhǔn)酱鎯r，其地址。(A)．連續(xù)的(B)．局部連續(xù)的(C)．一定是不連續(xù)的(D)．連續(xù)與否均可解：選D。14設(shè)有一8×8下三角矩陣A[8][8]，采用按行壓縮存儲的方式存放在一維數(shù)組B[]中，那么數(shù)組B[]的容量至少需要B個元素空間。(A)．32(B)．36(C)．16(D)．64解：選B。矩陣的第1行有8個非零元素，第2行有7個非零元素，…，第8行有1個非零元素，故需要存儲的非零元素的個數(shù)為8+7+6+5+4+3+2+1=8*(1+8)/2=36三、填空題1對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為，在表尾插入元素的時間復(fù)雜度為。解：在表頭〔即第0個位置〕插入元素，需挪動的元素個數(shù)為n，然后再做1次賦值操作，故T(n)=n+1=O(n)。在表尾插入元素?zé)o需挪動表中已有元素，只需1次賦值操作，故T(n)=1=O(1)。算法與數(shù)據(jù)結(jié)構(gòu)線性表答案全文共9頁，當(dāng)前為第3頁。2在線性表的單鏈接存儲中，假設(shè)一個元素所在結(jié)點的地址為p，那么其后繼結(jié)點的地址為，假設(shè)假定p為一個數(shù)組a中的下標(biāo)，那么其后繼結(jié)點的下標(biāo)為算法與數(shù)據(jù)結(jié)構(gòu)線性表答案全文共9頁，當(dāng)前為第3頁。解：應(yīng)填入p->link，p+13在單循環(huán)鏈表中，最后一個結(jié)點的指針指向結(jié)點。解：表頭結(jié)點。4在雙向鏈表中每個結(jié)點包含有兩個指針域，一個指向其結(jié)點，另一個指向其結(jié)點。解：應(yīng)填入前驅(qū)，后繼。5在雙向循環(huán)鏈表中表頭結(jié)點的左指針域指向結(jié)點，最后一個結(jié)點的右指針域指向結(jié)點。解：應(yīng)填入表尾，表頭。6在以HL為表頭指針的帶附加表頭結(jié)點的單鏈表和單循環(huán)鏈表中，鏈表為空的條件分別為和。解：HL->link==NULL,HL->link==HL7在雙循環(huán)鏈表L中，指針p所指結(jié)點為尾結(jié)點的條件為。解：p!=first&&p==first->link8在單鏈表中，假設(shè)要使指針p指向它所指結(jié)點的后繼結(jié)點，其語句是。解：p=p->link9在一個稀疏矩陣中，每個非零元素所對應(yīng)的三元組包括該元素的、和三項。解：為了節(jié)省對矩陣的存儲空間，稀疏矩陣采用僅存儲非零元素的行下標(biāo)、列以下與非零元素值的方式存儲。10二維數(shù)組A[4][5]按行優(yōu)先存儲方法存儲在內(nèi)存中，假設(shè)每個元素占2個存儲單元，且數(shù)組中第一個元素的存儲地址為120，那么元素A[3][4]的存儲地址為。假設(shè)其余條件不變，但是數(shù)組的存放方式變?yōu)榱行騼?yōu)先，那么元素A[3][4]的存儲地址變?yōu)?。解：行?yōu)先方式存儲：第0行、第1行、第2行的5個元素依次占據(jù)3*5*2=30個存儲單元。而第3行的前4個元素占據(jù)4*2=8個存儲單元，故A[3][4]的存儲地址為120+30+8=158列優(yōu)先方式存儲：第0列、第1列、第2列、第3列的4個元素依次占據(jù)4*4*2=32個存儲單元。而第4列的前3個元素占據(jù)3*2=6個存儲單元，故A[3][4]的存儲地址為120+32+6=158四、算法設(shè)計1編寫算法將以數(shù)組表示方式的順序表原地逆置。解：#include<iostream>usingnamespacestd;#defineN10voidDisplay(inta[],intn){for(inti=0;i<n;i++)cout<<a[i]<<"\t";cout<<endl;}//逆置函數(shù)1voidInvert1(inta[],intn){inttemp,i,j;算法與數(shù)據(jù)結(jié)構(gòu)線性表答案全文共9頁，當(dāng)前為第4頁。for(i=0,j=n-1;i<j;i++,j--)算法與數(shù)據(jù)結(jié)構(gòu)線性表答案全文共9頁，當(dāng)前為第4頁。 {temp=a[i];a[i]=a[j];a[j]=temp;}}//逆置函數(shù)2voidInvert2(inta[],intn){inttemp,i;for(i=0;i<n/2;i++){temp=a[i];a[i]=a[n-1-i];a[n-1-i]=temp;}}//主函數(shù)voidmain(){inti,a[N]={0,1,2,3,4,5,6,7,8,9};Display(a,N);Invert1(a,N);Display(a,N); Invert2(a,N);Display(a,N);}2對于帶附加頭結(jié)點的單鏈表，給出以下算法的代碼。(1)假設(shè)單鏈表中結(jié)點的數(shù)據(jù)域中數(shù)據(jù)依升序排列，將名為newNode，數(shù)據(jù)域數(shù)據(jù)為x的結(jié)點插入到該單鏈表中。(2)從無序的單鏈表中查找出所有元素的最大值，該值由函數(shù)返回；假設(shè)單鏈表為空，那么顯示出錯信息并停頓運行。(3)統(tǒng)計出單鏈表中結(jié)點的值等于給定值x的結(jié)點數(shù)。解:#include<iostream>usingnamespacestd;//定義結(jié)點structNode{ intdata; structNode*next;};//插入函數(shù)voidInsert(Node*&head,intx){Node*p,*q,*r,*newnode;newnode=newNode;//創(chuàng)立新結(jié)點 newnode->data=x; newnode->next=NULL; if(head->next==NULL)//假設(shè)鏈表空 head->next=newnode;//頭指針指向新結(jié)點 else//假設(shè)鏈表非空 { //獲取鏈尾指針 p=head; while(p->next!=NULL) p=p->next; r=p;算法與數(shù)據(jù)結(jié)構(gòu)線性表答案全文共9頁，當(dāng)前為第5頁。算法與數(shù)據(jù)結(jié)構(gòu)線性表答案全文共9頁，當(dāng)前為第5頁。 if(newnode->data<head->data)//假設(shè)新結(jié)點數(shù)據(jù)小于頭結(jié)點數(shù)據(jù) { newnode->next=head; head=newnode;//新結(jié)點插入鏈頭 } elseif(newnode->data>=r->data)//假設(shè)新結(jié)點數(shù)據(jù)大于或等于鏈尾結(jié)點數(shù)據(jù) r->next=newnode;//新結(jié)點插入鏈尾else {//新結(jié)點插入鏈表中間 p=head; while(newnode->data>=p->data) {q=p;p=p->next;} newnode->next=q->next; q->next=newnode; } }}//求最大值函數(shù)voidMax(Node*&head,int&maxValue){Node*p=head->next;if(p==NULL)//空表{cout<<"鏈表為空，退出!"<<endl;return;}maxValue=p->data;while(p->next!=NULL){ p=p->next;if(p->data>maxValue) maxValue=p->data;}}//計算值為x的結(jié)點個數(shù)函數(shù)voidCount(Node*&head,intx,int&countNum){ countNum=0;Node*p=head->next;if(p==NULL)//空表 {cout<<"鏈表為空，退出!"<<endl;return;}do {if(p->data==x)countNum++;p=p->next; }while(p!=NULL);}//輸出函數(shù)voidDisplay(Node*head){ Node*p=head->next;算法與數(shù)據(jù)結(jié)構(gòu)線性表答案全文共9頁，當(dāng)前為第6頁。算法與數(shù)據(jù)結(jié)構(gòu)線性表答案全文共9頁，當(dāng)前為第6頁。 {cout<<"鏈表空，退出!"<<endl;return;}while(p!=NULL) {cout<<"["<<p->data<<"]->"; p=p->next; } cout<<"NULL"<<endl;}//主函數(shù)voidmain(){ Node*head; head=newNode; head->next=NULL;//創(chuàng)立帶附加頭結(jié)點的局部指針 intx,maxValue,countNum; intn=5; cout<<"輸入"<<n<<"個數(shù),創(chuàng)立升序鏈表"<<endl; for(inti=1;i<=n;i++) { cin>>x; Insert(head,x);//調(diào)用插入法創(chuàng)立升序鏈表 }Display(head);//調(diào)入輸出函數(shù) Max(head,maxValue);//求結(jié)點值最大者 cout<<"最大值x="<<x<<endl; cout<<"輸入需查找的結(jié)點值x=";cin>>x; Count(head,x,countNum);//調(diào)用計算結(jié)點值為x的結(jié)點個數(shù) cout<<"值為"<<x<<"的結(jié)點個數(shù)為"<<countNum<<endl;}五、閱讀算法并描繪其功能1intfun1(int&x){ inti=0;while(i<=last&&data[i]!=x)i++;if(i>=0&&i<=last) {last--;for(intj=i;j<=last;j++)data[j]=data[j+1];return1;}return0;}解：該函數(shù)的功能是，假設(shè)在全局?jǐn)?shù)組data[0…last]中找到值為x的元素，將它刪除并返回1；否那么返回0。2intfun2(intx)算法與數(shù)據(jù)結(jié)構(gòu)線性表答案全文共9頁，當(dāng)前為第7頁。算法與數(shù)據(jù)結(jié)構(gòu)線性表答案全文共9頁，當(dāng)前為第7頁。while(i<=last&&!found) if(data[i]!=x)i++; elsefound=1;returnfound;}解：該函數(shù)的功能是，假設(shè)在全局?jǐn)?shù)組data[0…last]中，找到值為x的元素，那么返回1；否那么返回0。驗證程序如下：#include<iostream>usingnamespacestd;intdata[10]={1,2,3,4,5,6,7,8,9,10};intlast=9;//函數(shù)1intfun1(intx){inti=0;while(i<=last&&data[i]!=x) i++;if(i>=0&&i<=last){ last--