數(shù)據(jù)結(jié)構(gòu)(C語言版)(第2版)課后習(xí)題答案

word文檔精品文檔分享數(shù)據(jù)構(gòu)造〔C語言版〕〔第2版〕課后習(xí)題答案李冬梅2021.3word文檔精品文檔分享目錄第1章緒論1第2章線性表5第3章棧和隊列14第4章串、數(shù)組和廣義表27第5章樹和二叉樹34第6章圖44第7章查找55第8章排序66word文檔精品文檔分享IIword文檔精品文檔分享第1章緒論1．簡述以下概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)構(gòu)造、邏輯構(gòu)造、存儲結(jié)構(gòu)、抽象數(shù)據(jù)類型。答案：數(shù)據(jù)：是客觀事物的符號表示，指所有能輸入到計算機中并被計算機程序處理的符號的總稱。如數(shù)學(xué)計算中用到的整數(shù)和實數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、圖像、聲音、動畫等通過特殊編碼定義后的數(shù)據(jù)。數(shù)據(jù)元素：是數(shù)據(jù)的根本單位，在計算機中通常作為一個整體進展考慮和處理。在有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、記錄等。數(shù)據(jù)元素用于完整地描述一個對象，如一個學(xué)生記錄，樹中棋盤的一個格局〔狀態(tài)〕、圖中的一個頂點等。數(shù)據(jù)項：是組成數(shù)據(jù)元素的、有獨立含義的、不可分割的最小單位。例如，學(xué)生根本信息表中的學(xué)號、XX、性別等都是數(shù)據(jù)項。數(shù)據(jù)對象：是性質(zhì)一樣的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如：整數(shù)數(shù)據(jù)對象是集合 N={0，±1，±2，?}，字母字符數(shù)據(jù)對象是集合C={‘A’，‘ B’，?，‘Z’，‘a(chǎn)’，‘b’，?，‘z’}，學(xué)生根本信息表也可是一個數(shù)據(jù)對象。數(shù)據(jù)構(gòu)造：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說，數(shù)據(jù)結(jié)構(gòu)是帶“構(gòu)造〞的數(shù)據(jù)元素的集合，“構(gòu)造〞就是指數(shù)據(jù)元素之間存在的關(guān)系。邏輯構(gòu)造：從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。因此，數(shù)據(jù)的邏輯構(gòu)造可以看作是從具體問題抽象出來的數(shù)學(xué)模型。存儲構(gòu)造：數(shù)據(jù)對象在計算機中的存儲表示，也稱為物理構(gòu)造。抽象數(shù)據(jù)類型：由用戶定義的，表示應(yīng)用問題的數(shù)學(xué)模型，以及定義在這個模型上的一組操作的總稱。具體包括三局部：數(shù)據(jù)對象、數(shù)據(jù)對象上關(guān)系的集合和對數(shù)據(jù)對象的根本操作的集合。2．試舉一個數(shù)據(jù)構(gòu)造的例子，表達其邏輯構(gòu)造和存儲構(gòu)造兩方面的含義和相互關(guān)系。答案：例如有一X學(xué)生根本信息表，包括學(xué)生的學(xué)號、XX、性別、籍貫、專業(yè)等。每個學(xué)生根本信息記錄對應(yīng)一個數(shù)據(jù)元素，學(xué)生記錄按順序號排列，形成了學(xué)生根本信息記錄的線性序列。對于整個表來說，只有一個開場結(jié)點(它的前面無記錄)和一個終端結(jié)點(它的后面無記錄)，其他的結(jié)點那么各有一個也只有一個直接前趨和直接后繼。學(xué)生記錄之間的這種關(guān)系就確定了學(xué)生表的邏輯構(gòu)造，即線性構(gòu)造。這些學(xué)生記錄在計算機中的存儲表示就是存儲構(gòu)造。如果用連續(xù)的存儲單元(如用數(shù)組表)來存放這些記錄，那么稱為順序存儲構(gòu)造；如果存儲單元不連續(xù)，而是隨機存放各個記錄，然后用指針進展，那么稱為鏈?zhǔn)酱鎯?gòu)造。即一樣的邏輯構(gòu)造，可以對應(yīng)不同的存儲構(gòu)造。3．簡述邏輯構(gòu)造的四種根本關(guān)系并畫出它們的關(guān)系圖。word文檔精品文檔分享1word文檔精品文檔分享答案：〔1〕集合構(gòu)造數(shù)據(jù)元素之間除了“屬于同一集合〞的關(guān)系外，別無其他關(guān)系。例如，確定一名學(xué)生是否為班級成員，只需將班級看做一個集合構(gòu)造?！?〕線性構(gòu)造數(shù)據(jù)元素之間存在一對一的關(guān)系。例如，將學(xué)生信息數(shù)據(jù)按照其入學(xué)報到的時間先后順序進展排列，將組成一個線性構(gòu)造?！?〕樹構(gòu)造數(shù)據(jù)元素之間存在一對多的關(guān)系。例如，在班級的管理體系中，班長管理多個組長，每位組長管理多名組員，從而構(gòu)成樹形構(gòu)造?！?〕圖構(gòu)造或網(wǎng)狀構(gòu)造數(shù)據(jù)元素之間存在多對多的關(guān)系。例如，多位同學(xué)之間的朋友關(guān)系，任何兩位同學(xué)都可以是朋友，從而構(gòu)成圖形構(gòu)造或網(wǎng)狀構(gòu)造。其中樹構(gòu)造和圖構(gòu)造都屬于非線性構(gòu)造。四類根本邏輯構(gòu)造關(guān)系圖4．存儲構(gòu)造由哪兩種根本的存儲方法實現(xiàn)？答案：〔1〕順序存儲構(gòu)造順序存儲構(gòu)造是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常借助程序設(shè)計語言的數(shù)組類型來描述?！?〕鏈?zhǔn)酱鎯?gòu)造順序存儲構(gòu)造要求所有的元素依次存放在一片連續(xù)的存儲空間中，而鏈?zhǔn)酱鎯?gòu)造，無需占用一整塊存儲空間。但為了表示結(jié)點之間的關(guān)系，需要給每個結(jié)點附加指針字段，用于存放后繼元素的存儲地址。所以鏈?zhǔn)酱鎯?gòu)造通常借助于程序設(shè)計語言的指針類型來描述。5．選擇題〔1〕在數(shù)據(jù)構(gòu)造中，從邏輯上可以把數(shù)據(jù)構(gòu)造分成〔〕。A．動態(tài)構(gòu)造和靜態(tài)構(gòu)造B．緊湊構(gòu)造和非緊湊構(gòu)造word文檔精品文檔分享2word文檔精品文檔分享C．線性構(gòu)造和非線性構(gòu)造D．內(nèi)部構(gòu)造和外部構(gòu)造答案：C〔2〕與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的〔〕。A．存儲構(gòu)造B．存儲實現(xiàn)C．邏輯構(gòu)造D．運算實現(xiàn)答案：C〔3〕通常要求同一邏輯構(gòu)造中的所有數(shù)據(jù)元素具有一樣的特性，這意味著〔〕。．?dāng)?shù)據(jù)具有同一特點B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要一樣，而且對應(yīng)數(shù)據(jù)項的類型要一致C．每個數(shù)據(jù)元素都一樣D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等答案：B〔4〕以下說法正確的選項是〔〕。A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位B．?dāng)?shù)據(jù)項是數(shù)據(jù)的根本單位C．?dāng)?shù)據(jù)構(gòu)造是帶有構(gòu)造的各數(shù)據(jù)項的集合D．一些外表上很不一樣的數(shù)據(jù)可以有一樣的邏輯構(gòu)造答案：D解釋：數(shù)據(jù)元素是數(shù)據(jù)的根本單位，數(shù)據(jù)項是數(shù)據(jù)的最小單位，數(shù)據(jù)構(gòu)造是帶有構(gòu)造的各數(shù)據(jù)元素的集合?！?〕算法的時間復(fù)雜度取決于〔〕。A．問題的規(guī)模B．待處理數(shù)據(jù)的初態(tài)C．計算機的配置D．A和B答案：D解釋：算法的時間復(fù)雜度不僅與問題的規(guī)模有關(guān)，還與問題的其他因素有關(guān)。如某些排序的算法，其執(zhí)行時間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時會對算法有最好、最壞以及平均時間復(fù)雜度的評價。〔6〕以下數(shù)據(jù)構(gòu)造中，〔〕是非線性數(shù)據(jù)構(gòu)造A．樹B．字符串C．隊列D．棧答案：A6．試分析下面各程序段的時間復(fù)雜度。1〕x=90;y=100;while(y>0)if(x>100){x=x-10;y--;}elsex++;答案：O(1)解釋：程序的執(zhí)行次數(shù)為常數(shù)階。word文檔精品文檔分享3word文檔精品文檔分享2〕for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;答案：O(m*n)解釋：語句a[i][j]=0;的執(zhí)行次數(shù)為m*n。3〕s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;2解釋：語句s+=B[i][j];的執(zhí)行次數(shù)為n2。4〕i=1;while(i<=n)i=i*3;答案：O(log3n)解釋：語句i=i*3;的執(zhí)行次數(shù)為log3n。5〕x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;2解釋：語句x++;的執(zhí)行次數(shù)為n-1+n-2+??＋1=n(n-1)/2。6〕x=n;//n>1y=0;while(x≥(y+1)*(y+1))y++;答案：O(n)解釋：語句y++;的執(zhí)行次數(shù)為n。word文檔精品文檔分享4word文檔精品文檔分享第2章線性表1．選擇題〔1〕順序表中第一個元素的存儲地址是100，每個元素的長度為2，那么第5個元素的地址是〔〕。A．110B．108C．100D．120答案：B解釋：順序表中的數(shù)據(jù)連續(xù)存儲，所以第5個元素的地址為：100+2*4=108?！?〕在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O(1)的操作是〔〕。A．訪問第i個結(jié)點〔1≤i≤n〕和求第i個結(jié)點的直接前驅(qū)〔2≤i≤n〕B．在第i個結(jié)點后插入一個新結(jié)點〔1≤i≤n〕C．刪除第i個結(jié)點〔1≤i≤n〕D．將n個結(jié)點從小到大排序答案：A／解釋：在順序表中插入一個結(jié)點的時間復(fù)雜度都是O(n2)，排序的時間復(fù)雜度為O(n2)或O(nlog2n)。順序表是一種隨機存取構(gòu)造，訪問第i個結(jié)點和求第i個結(jié)點的直接前驅(qū)都可以直接通過數(shù)組的下標(biāo)直接定位，時間復(fù)雜度是O(1)?！?〕向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動的元素個數(shù)為〔〕。A．8B．63.5C．63D．7答案：B解釋：平均要移動的元素個數(shù)為：n/2?！?〕存儲的存儲構(gòu)造所占存儲空間〔〕。．分兩局部，一局部存放結(jié)點值，另一局部存放表示結(jié)點間關(guān)系的指針．只有一局部，存放結(jié)點值．只有一局部，存儲表示結(jié)點間關(guān)系的指針．分兩局部，一局部存放結(jié)點值，另一局部存放結(jié)點所占單元數(shù)答案：A〔5〕線性表假設(shè)采用鏈?zhǔn)酱鎯?gòu)造時，要求內(nèi)存中可用存儲單元的地址〔〕。A．必須是連續(xù)的B．局部地址必須是連續(xù)的C．一定是不連續(xù)的D．連續(xù)或不連續(xù)都可以答案：D〔6〕線性表Ｌ在〔〕情況下適用于使用鏈?zhǔn)綐?gòu)造實現(xiàn)。A．需經(jīng)常修改Ｌ中的結(jié)點值Ｂ．需不斷對Ｌ進展刪除插入C．Ｌ中含有大量的結(jié)點Ｄ．Ｌ中結(jié)點構(gòu)造復(fù)雜word文檔精品文檔分享5word文檔精品文檔分享答案：B解釋：鏈表最大的優(yōu)點在于插入和刪除時不需要移動數(shù)據(jù)，直接修改指針即可?！?〕單鏈表的存儲密度〔〕。A．大于 1B．等于 1C．小于 1D．不能確定答案：C解釋：存儲密度是指一個結(jié)點數(shù)據(jù)本身所占的存儲空間和整個結(jié)點所占的存儲空間之比，假設(shè)單鏈表一個結(jié)點本身所占的空間為D，指針域所占的空間為N，那么存儲密度為：D/(D+N)，一定小于1?！?〕將兩個各有n個元素的有序表歸并成一個有序表，其最少的比擬次數(shù)是〔〕。A．nB．2n-1C．2nD．n-1答案：A解釋：當(dāng)?shù)谝粋€有序表中所有的元素都小于〔或大于〕第二個表中的元素，只需要用第二個表中的第一個元素依次與第一個表的元素比擬，總計比擬n次?！?〕在一個長度為n的順序表中，在第i個元素〔1≤i≤n+1〕之前插入一個新元素時須向后移動〔〕個元素。A．n-iB．n-i+1C．n-i-1D．I答案：B(10)線性表L=(a1，a,??a)，以下說法正確的選項是〔〕。2n．每個元素都有一個直接前驅(qū)和一個直接后繼．線性表中至少有一個元素．表中諸元素的排列必須是由小到大或由大到?。谝粋€和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼。答案：D(11)創(chuàng)立一個包括n個結(jié)點的有序單鏈表的時間復(fù)雜度是〔〕。A．O(1)B．O(n)C．O(n2)D．O(nlog2n)答案：C解釋：單鏈表創(chuàng)立的時間復(fù)雜度是O(n)，而要建立一個有序的單鏈表，那么每生成一個新結(jié)點時需要和已有的結(jié)點進展比擬，確定適宜的插入位置，所以時間復(fù)雜度是O(n2)。(12)以下說法錯誤的選項是〔〕。．求表長、定位這兩種運算在采用順序存儲構(gòu)造時實現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?gòu)造時實現(xiàn)的效率低．順序存儲的線性表可以隨機存?。捎陧樞虼鎯σ筮B續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活．線性表的鏈?zhǔn)酱鎯?gòu)造優(yōu)于順序存儲構(gòu)造答案：D解釋：鏈?zhǔn)酱鎯?gòu)造和順序存儲構(gòu)造各有優(yōu)缺點，有不同的適用場合。word文檔精品文檔分享6word文檔精品文檔分享(13)在單鏈表中，要將s所指結(jié)點插入到p所指結(jié)點之后，其語句應(yīng)為〔〕。A．s->next=p+1;p->next=s;B．(*p).next=s;(*s).next=(*p).next;C．s->next=p->next;p->next=s->next;D．s->next=p->next;p->next=s;答案：D(14)在雙向鏈表存儲構(gòu)造中，刪除p所指的結(jié)點時須修改指針〔〕。A．p->next->prior=p->prior;p->prior->next=p->next;B．p->next=p->next->next;p->next->prior=p;C．p->prior->next=p;p->prior=p->prior->prior;D．p->prior=p->next->next;p->next=p->prior->prior;答案：A(15)在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點后插入q所指向的新結(jié)點，其修改指針的操作是〔〕。A．p->next=q;q->prior=p;p->next->prior=q;q->next=q;B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;答案：C2．算法設(shè)計題〔1〕將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間,不另外占用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。[題目分析 ]合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表 La和Lb的工作指針 ,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開場進展比擬，當(dāng)兩個鏈表La和Lb均為到達表尾結(jié)點時，依次摘取其中較小者重新在Lc表的最后。如果兩個表中的元素相等，只摘取La表中的元素，刪除Lb表中的元素，這樣確保合并后表中無重復(fù)的元素。當(dāng)一個表到達表尾結(jié)點，為空時，將非空表的剩余元素直接在Lc表的最后。[算法描述 ]voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc){//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向pa=La->next;pb=Lb->next;//pa和pb分別是鏈表 La和Lb的工作指針 ,初始化為相應(yīng)鏈表的第一個結(jié)點Lc=pc=La;//用La的頭結(jié)點作為Lc的頭結(jié)點while(pa&&pb){if(pa->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;}//取較小者 La中的元素，將pa在 pc的后面， pa指針后移elseif(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;}word文檔精品文檔分享7word文檔精品文檔分享//取較小者 Lb中的元素，將pb在 pc的后面， pb指針后移else//相等時取La中的元素，刪除Lb中的元素{pc->next=pa;pc=pa;pa=pa->next;q=pb->next;deletepb;pb=q;}}pc->next=pa?pa:pb; //插入剩余段deleteLb;//釋放Lb的頭結(jié)點}〔2〕將兩個非遞減的有序鏈表合并為一個非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間,不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。[題目分析 ]合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表 La和Lb的工作指針 ,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開場進展比擬，當(dāng)兩個鏈表La和Lb均為到達表尾結(jié)點時，依次摘取其中較小者重新在Lc表的表頭結(jié)點之后，如果兩個表中的元素相等，只摘取 La表中的元素，保存Lb表中的元素。當(dāng)一個表到達表尾結(jié)點，為空時，將非空表的剩余元素依次摘取，在Lc表的表頭結(jié)點之后。[算法描述 ]voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc,){//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向pa=La->next;pb=Lb->next;//pa和pb分別是鏈表 La和Lb的工作指針 ,初始化為相應(yīng)鏈表的第一個結(jié)點Lc=pc=La;//用La的頭結(jié)點作為Lc的頭結(jié)點Lc->next=NULL;while(pa||pb){//只要存在一個非空表，用q指向待摘取的元素if(!pa){q=pb;pb=pb->next;}//La表為空，用q指向pb，pb指針后移elseif(!pb){q=pa;pa=pa->next;}//Lb表為空，用q指向pa，pa指針后移elseif(pa->data<=pb->data){q=pa;pa=pa->next;}//取較小者〔包括相等〕La中的元素，用q指向pa，pa指針后移else{q=pb;pb=pb->next;}//取較小者Lb中的元素，用q指向pb，pb指針后移q->next=Lc->next;Lc->next=q;//將q指向的結(jié)點插在Lc表的表頭結(jié)點之后}deleteLb;//釋放Lb的頭結(jié)點word文檔精品文檔分享8word文檔精品文檔分享}〔3〕兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請設(shè)計算法求出A與B的交集，并存放于A鏈表中。[題目分析 ]只有同時出現(xiàn)在兩集合中的元素才出現(xiàn)在結(jié)果表中,合并后的新表使用頭指針Lc指向。pa和pb分別是鏈表La和Lb的工作指針 ,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開始進展比擬，當(dāng)兩個鏈表La和Lb均為到達表尾結(jié)點時，如果兩個表中相等的元素時，摘取La表中的元素，刪除Lb表中的元素；如果其中一個表中的元素較小時，刪除此表中較小的元素，此表的工作指針后移。當(dāng)鏈表La和Lb有一個到達表尾結(jié)點，為空時，依次刪除另一個非空表中的所有元素。[算法描述 ]voidMix(LinkList&La,LinkList&Lb,LinkList&Lc){pa=La->next;pb=Lb->next;pa和pb分別是鏈表La和Lb的工作指針 ,初始化為相應(yīng)鏈表的第一個結(jié)點Lc=pc=La;//用La的頭結(jié)點作為Lc的頭結(jié)點while(pa&&pb){if(pa->data==pb->data)∥交集并入結(jié)果表中。{pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;deleteu;}elseif(pa->data<pb->data){u=pa;pa=pa->next;deleteu;}else{u=pb;pb=pb->next;deleteu;}}while(pa){u=pa;pa=pa->next;deleteu;}∥釋放結(jié)點空間while(pb){u=pb;pb=pb->next;deleteu;}∥釋放結(jié)點空間pc->next=null;∥置鏈表尾標(biāo)記。deleteLb;//釋放Lb的頭結(jié)點}〔4〕兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請設(shè)計算法求出兩個集合A和B的差集〔即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合〕，并以同樣的形式存儲，同時返回該集合的元素個數(shù)。[題目分析 ]求兩個集合A和B的差集是指在A中刪除 A和B中共有的元素，即刪除鏈表中的相應(yīng)結(jié)點,所以要保存待刪除結(jié)點的前驅(qū)，使用指針pre指向前驅(qū)結(jié)點。pa和pb分別是鏈表La和Lb的工作指針 ,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開場進展比擬，當(dāng)兩個鏈表La和Lb均為到達表尾結(jié)點時，如果La表中的元素小于Lb表中的元素，pre置為La表的工作指針pa刪除Lb表中的元素；如果其中一個表中的元素較小時，刪除此表中較小的元素，此表的工作指針后移。當(dāng)鏈表 La和Lb有一個為空時，依次刪除另一個非空表中的所有元素。word文檔精品文檔分享9word文檔精品文檔分享[算法描述 ]voidDifference〔LinkList&La,LinkList&Lb,int*n〕{∥差集的結(jié)果存儲于單鏈表La中，*n是結(jié)果集合中元素個數(shù)，調(diào)用時為0pa=La->next;pb=Lb->next;∥pa和pb分別是鏈表 La和Lb的工作指針 ,初始化為相應(yīng)鏈表的第一個結(jié)點pre=La;∥pre為La中pa所指結(jié)點的前驅(qū)結(jié)點的指針while〔pa&&pb〕{if〔pa->data<q->data〕{pre=pa;pa=pa->next;*n++;}∥A鏈表中當(dāng)前結(jié)點指針后移elseif〔pa->data>q->data〕q=q->next;∥B鏈表中當(dāng)前結(jié)點指針后移else{pre->next=pa->next;∥處理A，B中元素值一樣的結(jié)點，應(yīng)刪除u=pa;pa=pa->next;deleteu;}∥刪除結(jié)點}}〔5〕設(shè)計算法將一個帶頭結(jié)點的單鏈表A分解為兩個具有一樣構(gòu)造的鏈表B、C，其中B表的結(jié)點為A表中值小于零的結(jié)點，而C表的結(jié)點為 A表中值大于零的結(jié)點〔鏈表A中的元素為非零整數(shù)，要求B、C表利用A表的結(jié)點〕。[題目分析 ]B表的頭結(jié)點使用原來A表的頭結(jié)點，為C表新申請一個頭結(jié)點。從A表的第一個結(jié)點開場，依次取其每個結(jié)點p，判斷結(jié)點 p的值是否小于0，利用前插法，將小于0的結(jié)點插入B表,大于等于 0的結(jié)點插入C表。[算法描述 ]voidDisCompose(LinkedListA){ B=A;B->next=NULL;∥B表初始化C=newLNode;∥為C申請結(jié)點空間C->next=NULL;∥C初始化為空表p=A->next;∥p為工作指針while(p!=NULL){r=p->next;∥暫存p的后繼if(p->data<0){p->next=B->next;B->next=p;}∥將小于0的結(jié)點鏈入 B表,前插法else{p->next=C->next;C->next=p;}∥將大于等于0的結(jié)點鏈入 C表,前插法p=r;∥p指向新的待處理結(jié)點。}}〔6〕設(shè)計一個算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點。word文檔精品文檔分享10word文檔精品文檔分享[題目分析 ]假定第一個結(jié)點中數(shù)據(jù)具有最大值，依次與下一個元素比擬，假設(shè)其小于下一個元素，那么設(shè)其下一個元素為最大值，反復(fù)進展比擬，直到遍歷完該鏈表。[算法描述 ]ElemTypeMax(LinkListL){if(L->next==NULL)returnNULL;pmax=L->next;//假定第一個結(jié)點中數(shù)據(jù)具有最大值p=L->next->next;while(p!=NULL){//如果下一個結(jié)點存在if(p->data>pmax->data)pmax=p;//如果p的值大于pmax的值，那么重新賦值p=p->next;//遍歷鏈表}returnpmax->data;7〕設(shè)計一個算法，通過遍歷一趟，將鏈表中所有結(jié)點的方向逆轉(zhuǎn)，仍利用原表的存儲空間。[題目分析 ]從首元結(jié)點開場，逐個地把鏈表L的當(dāng)前結(jié)點p插入新的鏈表頭部。[算法描述 ]voidinverse(LinkList&L){//逆置帶頭結(jié)點的單鏈表Lp=L->next;L->next=NULL;while(p){q=p->next; //q指向*p的后繼p->next=L->next;L->next=p;//*p插入在頭結(jié)點之后p=q;}}〔8〕設(shè)計一個算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素〔 mink和maxk是給定的兩個參數(shù)，其值可以和表中的元素一樣，也可以不同〕。[題目分析 ]分別查找第一個值>mink的結(jié)點和第一個值≥maxk的結(jié)點，再修改指針，刪除值大于mink且小于maxk的所有元素。[算法描述 ]voiddelete(LinkList&L,intmink,intmaxk){p=L->next;//首元結(jié)點while(p&&p->data<=mink){pre=p;p=p->next;}//查找第一個值>mink的結(jié)點word文檔精品文檔分享11word文檔精品文檔分享if(p){while(p&&p->data<maxk)p=p->next;//查找第一個值≥maxk的結(jié)點q=pre->next; pre->next=p;//修改指針while(q!=p){s=q->next;deleteq;q=s;}//釋放結(jié)點空間}//if}〔9〕 p指向雙向循環(huán)鏈表中的一個結(jié)點，其結(jié)點構(gòu)造為data、prior、next三個域，寫出算法change(p),交換p所指向的結(jié)點和它的前綴結(jié)點的順序。[題目分析 ]知道雙向循環(huán)鏈表中的一個結(jié)點，與前驅(qū)交換涉及到四個結(jié)點〔p結(jié)點，前驅(qū)結(jié)點，前驅(qū)的前驅(qū)結(jié)點，后繼結(jié)點〕六條鏈。[算法描述 ]voidExchange〔LinkedListp〕∥p是雙向循環(huán)鏈表中的一個結(jié)點，本算法將p所指結(jié)點與其前驅(qū)結(jié)點交換。{q=p->llink；q->llink->rlink=p；∥p的前驅(qū)的前驅(qū)之后繼為pp->llink=q->llink；∥p的前驅(qū)指向其前驅(qū)的前驅(qū)。q->rlink=p->rlink；∥p的前驅(qū)的后繼為p的后繼。q->llink=p；∥p與其前驅(qū)交換p->rlink->llink=q；∥p的后繼的前驅(qū)指向原p的前驅(qū)p->rlink=q；∥p的后繼指向其原來的前驅(qū)}∥算法 exchange完畢。〔10〕長度為n的線性表 A采用順序存儲構(gòu)造，請寫一時間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。[題目分析 ]在順序存儲的線性表上刪除元素，通常要涉及到一系列元素的移動〔刪第i個元素，第i+1至第n個元素要依次前移〕。此題要求刪除線性表中所有值為item的數(shù)據(jù)元素，并未要求元素間的相對位置不變。因此可以考慮設(shè)頭尾兩個指針〔i=1，j=n〕，從兩端向中間移動，凡遇到值item的數(shù)據(jù)元素時，直接將右端元素左移至值為item的數(shù)據(jù)元素位置。[算法描述 ]voidDelete〔ElemTypeA[]，intn〕∥A是有 n個元素的一維數(shù)組，本算法刪除A中所有值為 item的元素。{i=1；j=n；∥設(shè)置數(shù)組低、高端指針〔下標(biāo)〕。while〔i<j〕{while〔i<j&&A[i]!=item〕i++；∥假設(shè)值不為item，左移指針。if〔i<j〕while〔i<j&&A[j]==item〕j--；∥假設(shè)右端元素為item，指針左移word文檔精品文檔分享12word文檔精品文檔分享if〔i<j〕A[i++]=A[j--]；}word文檔精品文檔分享13word文檔精品文檔分享第3章棧和隊列1．選擇題〔1〕假設(shè)讓元素 1，2，3，4，5依次進棧，那么出棧次序不可能出現(xiàn)在〔〕種情況。A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，1答案：C解釋：棧是后進先出的線性表，不難發(fā)現(xiàn)C選項中元素 1比元素 2先出棧，違背了棧的后進先出原那么，所以不可能出現(xiàn)C選項所示的情況?！?〕假設(shè)一個棧的入棧序列是1，2，3，?，n，其輸出序列為p1，p2，p3，?，pn，假設(shè)p1=n，那么 pi為〔〕。A．iB．n-iC．n-i+1D．不確定答案：C解釋：棧是后進先出的線性表，一個棧的入棧序列是1，2，3，?，n，而輸出序列的第一個元素為n，說明 1，2，3，?，n一次性全部進棧，再進展輸出，所以p1=n，p2=n-1，?，pi=n-i+1?！?〕數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當(dāng)前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(shù)小于ｎ，計算隊列中元素個數(shù)的公式為〔〕。A．r-fB．(n+f-r)%nC．n+r-fD．〔n+r-f)%n答案：D解釋：對于非循環(huán)隊列，尾指針和頭指針的差值便是隊列的長度，而對于循環(huán)隊列，差值可能為負數(shù)，所以需要將差值加上MAXSIZE〔此題為n〕，然后與 MAXSIZE〔此題為n〕求余，即〔n+r-f)%n。〔4〕鏈?zhǔn)綏＝Y(jié)點為：(data,link)，top指向棧頂.假設(shè)想摘除棧頂結(jié)點，并將刪除結(jié)點的值保存到x中,那么應(yīng)執(zhí)行操作〔〕。A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；答案：A解釋：x=top->data將結(jié)點的值保存到x中，top=top->link棧頂指針指向棧頂下一結(jié)點，即摘除棧頂結(jié)點。〔5〕設(shè)有一個遞歸算法如下intfact(intn){//n大于等于 0if(n<=0)return1;elsereturnn*fact(n-1);}那么計算 fact(n)需要調(diào)用該函數(shù)的次數(shù)為〔〕。A．n+1B．n-1C． nD． n+2答案：Aword文檔精品文檔分享14word文檔精品文檔分享解釋：特殊值法。設(shè)n=0，易知僅調(diào)用一次fact(n)函數(shù)，應(yīng)選A?！?〕棧在〔〕中有所應(yīng)用。A．遞歸調(diào)用B．函數(shù)調(diào)用C．表達式求值D．前三個選項都有答案：D解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達式求值均用到了棧的后進先出性質(zhì)。7〕為解決計算機主機與打印機間速度不匹配問題，通常設(shè)一個打印數(shù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機那么依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯構(gòu)造應(yīng)該是〔〕。A．隊列B．棧C．線性表D．有序表答案：A解釋：解決緩沖區(qū)問題應(yīng)利用一種先進先出的線性表，而隊列正是一種先進先出的線性表?！?〕設(shè)棧 S和隊列 Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進入棧S，一個元素出棧后即進入Q，假設(shè)6個元素出隊的序列是e2、e4、e3、e6、e5和e1，那么棧 S的容量至少應(yīng)該是〔〕。A．2B．3C．4D． 6答案：B解釋：元素出隊的序列是e2、e4、e3、e6、e5和e1，可知元素入隊的序列是e2、e4、e3、e6、e5和e1，即元素出棧的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次進入棧，易知棧S中最多同時存在3個元素，故棧S的容量至少為3。〔9〕假設(shè)一個棧以向量V[1..n]存儲，初始棧頂指針top設(shè)為n+1，那么元素 x進棧的正確操作是()。A．top++;V[top]=x;B．V[top]=x;top++;C．top--;V[top]=x;D．V[top]=x;top--;答案：C解釋：初始棧頂指針top為n+1，說明元素從數(shù)組向量的高端地址進棧，又因為元素存儲在向量空間V[1..n]中，所以進棧時top指針先下移變?yōu)閚，之后將元素x存儲在V[n]?！?0〕設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用〔〕數(shù)據(jù)構(gòu)造最佳。A．線性表的順序存儲構(gòu)造B．隊列C.線性表的鏈?zhǔn)酱鎯?gòu)造D.棧答案：D解釋：利用棧的后進先出原那么?！?1〕用方式存儲的隊列，在進展刪除運算時〔〕。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改答案：D解釋：一般情況下只修改頭指針，但是，當(dāng)刪除的是隊列中最后一個元素時，隊尾指word文檔精品文檔分享15word文檔精品文檔分享針也喪失了，因此需對隊尾指針重新賦值。〔12〕循環(huán)隊列存儲在數(shù)組A[0..m]中，那么入隊時的操作為〔〕。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)答案：D解釋：數(shù)組A[0..m]中共含有m+1個元素，故在求模運算時應(yīng)除以m+1?！?3〕最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是 front，那么隊空的條件是〔〕。A.(rear+1)%n==frontB.rear==frontC．rear+1==frontD.(rear-l)%n==front答案：B解釋：最大容量為 n的循環(huán)隊列，隊滿條件是(rear+1)%n==front，隊空條件是rear==front?！?4〕棧和隊列的共同點是〔〕。A.都是先進先出B.都是先進后出C.只允許在端點處插入和刪除元素D.沒有共同點答案：C解釋：棧只允許在棧頂處進展插入和刪除元素，隊列只允許在隊尾插入元素和在隊頭刪除元素?！?5〕一個遞歸算法必須包括〔〕。A.遞歸局部B.終止條件和遞歸局部C.迭代局部D.終止條件和迭代局部答案：B2．算法設(shè)計題〔1〕將編號為 0和1的兩個棧存放于一個數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?0號棧的棧頂指針top[0]等于-1時該棧為空，當(dāng)?shù)?號棧的棧頂指針top[1]等于 m時該棧為空。兩個棧均從兩端向中間增長。試編寫雙棧初始化，判斷?？?、棧滿、進棧和出棧等算法的函數(shù)。雙棧數(shù)據(jù)構(gòu)造的定義如下：Typedefstruct{inttop[2],bot[2];//棧頂和棧底指針SElemType*V;//棧數(shù)組intm;//棧最大可容納元素個數(shù)}DblStack[題目分析 ]兩棧共享向量空間，將兩棧棧底設(shè)在向量兩端，初始時，左棧頂指針為-1，右棧頂為m。兩棧頂指針相鄰時為棧滿。兩棧頂相向、迎面增長，棧頂指針指向棧頂元素。[算法描述 ](1)棧初始化word文檔精品文檔分享16word文檔精品文檔分享intInit(){S.top[0]=-1;S.top[1]=m;return1;//初始化成功}入棧操作：intpush(stkS,inti,intx)∥i為棧號， i=0表示左棧， i=1為右棧， x是入棧元素。入棧成功返回1，失敗返回 0{if(i<0||i>1){cout<<“棧號輸入不對〞<<endl;exit(0);}if(S.top[1]-S.top[0]==1){cout<<“棧已滿〞<<endl;return(0);}switch(i){case0:S.V[++S.top[0]]=x;return(1);break;case1:S.V[--S.top[1]]=x;return(1);}}∥push退棧操作ElemTypepop(stkS,inti)∥退棧。 i代表棧號， i=0時為左棧， i=1時為右棧。退棧成功時返回退棧元素∥否那么返回-1{if(i<0||i>1){cout<<“棧號輸入錯誤〞<<endl；exit(0);}switch(i){case0:if(S.top[0]==-1){cout<<“?？炸?lt;<endl；return〔-1〕；}elsereturn(S.V[S.top[0]--]);case1:if(S.top[1]==m{cout<<“?？炸?lt;<endl;return(-1);}elsereturn(S.V[S.top[1]++]);}∥switch}∥算法完畢判斷?？読ntEmpty();{return(S.top[0]==-1&&S.top[1]==m);}[算法討論 ]請注意算法中兩棧入棧和退棧時的棧頂指針的計算。左棧是通常意義下的棧，而右棧入棧操作時，其棧頂指針左移〔減1〕，退棧時，棧頂指針右移〔加1〕?！?〕回文是指正讀反讀均一樣的字符序列，如“abba〞和“abdba〞均是回文，但“good〞不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)[題目分析 ]word文檔精品文檔分享17word文檔精品文檔分享將字符串前一半入棧，然后，棧中元素和字符串后一半進展比擬。即將第一個出棧元素和后一半串中第一個字符比擬，假設(shè)相等，那么再出棧一個元素與后一個字符比擬，??，直至?？眨Y(jié)論為字符序列是回文。在出棧元素與串中字符比擬不等時，結(jié)論字符序列不是回文。[算法描述 ]#defineStackSize100//假定預(yù)分配的?？臻g最多為100個元素typedefcharDataType;//假定棧元素的數(shù)據(jù)類型為字符typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;intIsHuiwen(char*t){//判斷t字符向量是否為回文，假設(shè)是，返回1，否那么返回 0SeqStacks;inti,len;chartemp;InitStack(&s);len=strlen(t);//求向量長度for(i=0;i<len/2;i++)//將一半字符入棧Push(&s,t[i]);while(!EmptyStack(&s)){//每彈出一個字符與相應(yīng)字符比擬temp=Pop(&s);if(temp!=S[i])return0;//不等那么返回0elsei++;}return1;//比擬完畢均相等那么返回1}3〕設(shè)從鍵盤輸入一整數(shù)的序列：a1,a2,a3，?，an，試編寫算法實現(xiàn)：用棧構(gòu)造存儲輸入的整數(shù)，當(dāng)ai≠-1時，將ai進棧；當(dāng)ai=-1時，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況〔入棧滿等〕給出相應(yīng)的信息。[算法描述 ]#definemaxsize棧空間容量voidInOutS(ints[maxsize])//s是元素為整數(shù)的棧，本算法進展入棧和退棧操作。{inttop=0;//top為棧頂指針，定義top=0時為?？?。for(i=1;i<=n;i++) //n個整數(shù)序列作處理。{cin>>x); //從鍵盤讀入整數(shù)序列。word文檔精品文檔分享18word文檔精品文檔分享if(x!=-1)//讀入的整數(shù)不等于-1時入棧。｛if(top==maxsize-1){cout<<“棧滿〞<<endl;exit(0);}elses[++top]=x;//x入棧。｝else //讀入的整數(shù)等于-1時退棧。{if(top==0){cout<<“棧空〞<<endl;exit(0);}elsecout<<“出棧元素是〞<<s[top--]<<endl;}}}//算法完畢。〔4〕從鍵盤上輸入一個后綴表達式，試編寫算法計算表達式的值。規(guī)定：逆波蘭表達式的長度不超過一行，以$符作為輸入完畢，操作數(shù)之間用空格分隔,操作符只可能有+、-、*、/四種運算。例如：23434+2*$。[題目分析 ]逆波蘭表達式(即后綴表達式 )求值規(guī)那么如下：設(shè)立運算數(shù)棧OPND,對表達式從左到右掃描(讀入)，當(dāng)表達式中掃描到數(shù)時，壓入OPND棧。當(dāng)掃描到運算符時，從OPND退出兩個數(shù)，進展相應(yīng)運算，結(jié)果再壓入OPND棧。這個過程一直進展到讀出表達式完畢符$，這時OPND棧中只有一個數(shù)，就是結(jié)果。[算法描述 ]floatexpr()//從鍵盤輸入逆波蘭表達式，以‘$’表示輸入完畢，本算法求逆波蘭式表達式的值。｛floatOPND[30]; //OPND是操作數(shù)棧。init(OPND);//兩棧初始化。floatnum=0.0; //數(shù)字初始化。cin>>x;//x是字符型變量。while(x!=’$’){switch{case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’)//拼數(shù)if(x!=’.’) //處理整數(shù){num=num*10+〔ord(x)- ord(‘0’)〕 ;cin>>x;}else//處理小數(shù)局部。{scale=10.0;cin>>x;while(x>=’0’&&x<=’9’){num=num+(ord(x)-ord(‘0’)/scale;scale=scale*10;cin>>x;}}//elsepush(OPND,num);num=0.0;//數(shù)壓入棧，下個數(shù)初始化word文檔精品文檔分享19word文檔精品文檔分享casex=‘ ’:break;//遇空格，繼續(xù)讀下一個字符。casex=‘+’:push(OPND,pop(OPND)+pop(OPND));break;casex=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;casex=‘*’:push(OPND,pop(OPND)*pop(OPND));break;casex=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;default://其它符號不作處理。}//完畢 switchcin>>x;//讀入表達式中下一個字符。}//完畢 while〔x！=‘$’〕cout<<“后綴表達式的值為〞<<pop(OPND);}//算法完畢。[算法討論]假設(shè)輸入的后綴表達式是正確的，未作錯誤檢查。算法中拼數(shù)局部是核心。假設(shè)遇到大于等于‘0’且小于等于‘ 9’的字符，認(rèn)為是數(shù)。這種字符的序號減去字符‘0’的序號得出數(shù)。對于整數(shù)，每讀入一個數(shù)字字符，前面得到的局部數(shù)要乘上10再加新讀入的數(shù)得到新的局部數(shù)。當(dāng)讀到小數(shù)點，認(rèn)為數(shù)的整數(shù)局部已完，要接著處理小數(shù)局部。小數(shù)局部的數(shù)要除以10〔或10的冪數(shù)〕變成十分位，百分位，千分位數(shù)等等，與前面局部數(shù)相加。在拼數(shù)過程中，假設(shè)遇非數(shù)字字符，表示數(shù)已拼完，將數(shù)壓入棧中，并且將變量num恢復(fù)為0，準(zhǔn)備下一個數(shù)。這時對新讀入的字符進入‘+’、‘-’、‘*’、‘/’及空格的判斷，因此在完畢處理數(shù)字字符的case后，不能參加break語句?！?〕假設(shè)以 I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否那么稱為非法序列。①下面所示的序列中哪些是合法的？A.IOIIOIOO B.IOOIOIIOC.IIIOIOIO D.IIIOOIOO②通過對①的分析，寫出一個算法，判定所給的操作序列是否合法。假設(shè)合法，返回true，否那么返回false〔假定被判定的操作序列已存入一維數(shù)組中〕。答案：①A和D是合法序列，B和C是非法序列。②設(shè)被判定的操作序列已存入一維數(shù)組A中。intJudge(charA[])//判斷字符數(shù)組A中的輸入輸出序列是否是合法序列。如是，返回true，否那么返回false。{i=0;//i為下標(biāo)。j=k=0;//j和k分別為I和字母O的的個數(shù)。while(A[i]!=‘ 0’)//當(dāng)未到字符數(shù)組尾就作。{switch(A[i]){case‘I’:j++;break;//入棧次數(shù)增1。case‘O’:k++;if(k>j){cout<<“序列非法〞 <<ednl；exit(0);}word文檔精品文檔分享20word文檔精品文檔分享}i++;//不管A[i]是‘I’或‘O’，指針i均后移。 }if(j!=k){cout<<“序列非法〞<<endl；return(false);}else{cout<<“序列合法〞<<endl；return(true);}}//算法完畢。[算法討論 ]在入棧出棧序列〔即由‘I’和‘O’組成的字符串〕的任一位置，入棧次數(shù)〔‘I’的個數(shù)〕都必須大于等于出棧次數(shù)〔即‘O’的個數(shù)〕，否那么視作非法序列，立即給出信息，退出算法。整個序列〔即讀到字符數(shù)組中字符串的完畢標(biāo)記‘\0’〕，入棧次數(shù)必須等于出棧次數(shù)〔題目中要求棧的初態(tài)和終態(tài)都為空〕，否那么視為非法序列。(6〕假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾元素站點(注意不設(shè)頭指針 )，試編寫相應(yīng)的置空隊、判隊空、入隊和出隊等算法。[題目分析 ]置空隊就是建立一個頭節(jié)點，并把頭尾指針都指向頭節(jié)點，頭節(jié)點是不存放數(shù)據(jù)的；判隊空就是當(dāng)頭指針等于尾指針時，隊空；入隊時，將新的節(jié)點插入到鏈隊列的尾部，同時將尾指針指向這個節(jié)點；出隊時，刪除的是隊頭節(jié)點，要注意隊列的長度大于1還是等于 1的情況，這個時候要注意尾指針的修改，如果等于1，那么要刪除尾指針指向的節(jié)點。[算法描述 ]//先定義鏈隊構(gòu)造:typedefstructqueuenode{Datatypedata;structqueuenode*next;}QueueNode;//以上是結(jié)點類型的定義typedefstruct{queuenode*rear;}LinkQueue;//只設(shè)一個指向隊尾元素的指針置空隊voidInitQueue(LinkQueue*Q){//置空隊：就是使頭結(jié)點成為隊尾元素QueueNode*s;Q->rear=Q->rear->next;//將隊尾指針指向頭結(jié)點while(Q->rear!=Q->rear->next)//當(dāng)隊列非空，將隊中元素逐個出隊{s=Q->rear->next;Q->rear->next=s->next;deletes;}//回收結(jié)點空間}word文檔精品文檔分享21word文檔精品文檔分享判隊空intEmptyQueue(LinkQueue*Q){//判隊空。當(dāng)頭結(jié)點的next指針指向自己時為空隊returnQ->rear->next->next==Q->rear->next;}入隊voidEnQueue(LinkQueue*Q,Datatypex){//入隊。也就是在尾結(jié)點處插入元素QueueNode*p=newQueueNode;//申請新結(jié)點p->data=x;p->next=Q->rear->next;//初始化新結(jié)點并鏈入Q-rear->next=p;Q->rear=p;//將尾指針移至新結(jié)點}(4)出隊DatatypeDeQueue(LinkQueue*Q){//出隊,把頭結(jié)點之后的元素摘下Datatypet;QueueNode*p;if(EmptyQueue(Q))Error("Queueunderflow");p=Q->rear->next->next;//p指向?qū)⒁碌慕Y(jié)點x=p->data;//保存結(jié)點中數(shù)據(jù)if(p==Q->rear){//當(dāng)隊列中只有一個結(jié)點時，p結(jié)點出隊后，要將隊尾指針指向頭結(jié)點Q->rear=Q->rear->next;Q->rear->next=p->next;}elseQ->rear->next->next=p->next;//摘下結(jié)點pdeletep;//釋放被刪結(jié)點returnx;}〔7〕假設(shè)以數(shù)組 Q[m]存放循環(huán)隊列中的元素,同時設(shè)置一個標(biāo)志tag，以tag== 0和tag==1來區(qū)別在隊頭指針(front)和隊尾指針 (rear)相等時，隊列狀態(tài)為“空〞還是“滿〞。試編寫與word文檔精品文檔分享22word文檔精品文檔分享此構(gòu)造相應(yīng)的插入(enqueue)和刪除(dlqueue)算法。[算法描述 ]初始化SeQueueQueueInit(SeQueueQ){//初始化隊列Q.front=Q.rear=0;Q.tag=0;returnQ;}入隊SeQueueQueueIn(SeQueueQ,inte){//入隊列if((Q.tag==1)&&(Q.rear==Q.front))cout<<"隊列已滿"<<endl;else{Q.rear=(Q.rear+1)%m;Q.data[Q.rear]=e;if(Q.tag==0)Q.tag=1;//隊列已不空}returnQ;}(3)出隊ElemTypeQueueOut(SeQueueQ){//出隊列if(Q.tag==0){cout<<"隊列為空"<<endl;exit(0);}else{Q.front=(Q.front+1)%m;e=Q.data[Q.front];if(Q.front==Q.rear)Q.tag=0;//空隊列}return(e);}(8〕如果允許在循環(huán)隊列的兩端都可以進展插入和刪除操作。要求：①寫出循環(huán)隊列的類型定義；②寫出“從隊尾刪除〞和“從隊頭插入〞的算法。[題目分析 ]用一維數(shù)組v[0..M-1]實現(xiàn)循環(huán)隊列，其中M是隊列長度。設(shè)隊頭指針front和隊尾指針rear，約定 front指向隊頭元素的前一位置，rear指向隊尾元素。定義front=rear時為隊空， (rear+1)%m=front為隊滿。約定隊頭端入隊向下標(biāo)小的方向開展，隊尾端入隊向下標(biāo)大的方向開展。word文檔精品文檔分享23word文檔精品文檔分享[算法描述 ]①#defineM隊列可能到達的最大長度typedefstruct{elemtpdata[M];intfront,rear;}cycqueue;②elemtpdelqueue(cycqueueQ)//Q是如上定義的循環(huán)隊列，本算法實現(xiàn)從隊尾刪除，假設(shè)刪除成功，返回被刪除元素，否那么給出出錯信息。{if(Q.front==Q.rear){cout<<"隊列空"<<endl;exit(0);}Q.rear=(Q.rear-1+M)%M;//修改隊尾指針。return(Q.data[(Q.rear+1+M)%M]);//返回出隊元素。}//從隊尾刪除算法完畢voidenqueue(cycqueueQ,elemtpx)//Q是順序存儲的循環(huán)隊列，本算法實現(xiàn)“從隊頭插入〞元素x。{if(Q.rear==(Q.front-1+M)%M){cout<<"隊滿"<<endl;exit(0);)Q.data[Q.front]=x;//x入隊列Q.front=(Q.front-1+M)%M;//修改隊頭指針。}//完畢從隊頭插入算法。9〕Ackermann函數(shù)定義如下:①寫出計算Ack(m,n)的遞歸算法，并根據(jù)此算法給出出Ack(2,1)的計算過程。②寫出計算Ack(m,n)的非遞歸算法。[算法描述 ]intAck(intm,n){if(m==0)return(n+1);elseif(m!=0&&n==0)return(Ack(m-1,1));elsereturn(Ack(m-1,Ack(m,m-1));}//算法完畢① Ack(2,1)的計算過程Ack(2,1)=Ack(1,Ack(2,0))//因m<>0,n<>0而得=Ack(1,Ack(1,1))//因m<>0,n=0而得word文檔精品文檔分享24word文檔精品文檔分享=Ack(1,Ack(0,Ack(1,0)))//因m<>0,n<>0而得=Ack(1,Ack(0,Ack(0,1)))//因m<>0,n=0而得=Ack(1,Ack(0,2))//因m=0而得=Ack(1,3)//因m=0而得=Ack(0,Ack(1,2))//因m<>0,n<>0而得=Ack(0,Ack(0,Ack(1,1)))//因m<>0,n<>0而得=Ack(0,Ack(0,Ack(0,Ack(1,0))))//因m<>0,n<>0而得=Ack(0,Ack(0,Ack(0,Ack(0,1))))//因m<>0,n=0而得=Ack(0,Ack(0,Ack(0,2)))//因m=0而得=Ack(0,Ack(0,3))//因m=0而得=Ack(0,4)//因n=0而得=5//因n=0而得②intAckerman(intm,intn){intakm[M][N];inti,j;for(j=0;j<N;j++)akm[0][j]=j+1;for(i=1;i<m;i++){akm[i][0]=akm[i-1][1];for(j=1;j<N;j++)akm[i][j]=akm[i-1][akm[i][j-1]];}return(akm[m][n]);}//算法完畢10〕f為單鏈表的表頭指針,鏈表中存儲的都是整型數(shù)據(jù)，試寫出實現(xiàn)以下運算的遞歸算法：求鏈表中的最大整數(shù)；②求鏈表的結(jié)點個數(shù)；③求所有整數(shù)的平均值。[算法描述 ]①intGetMax(LinkListp){if(!p->next)returnp->data;else{intmax=GetMax(p->next);word文檔精品文檔分享25word文檔精品文檔分享returnp->data>=max?p->data:max;}}②intGetLength(LinkListp){if(!p->next)return1;else{returnGetLength(p->next)+1;}}③doubleGetAverage(LinkListp,intn){if(!p->next)returnp->data;else{doubleave=GetAverage(p->next,n-1);return(ave*(n-1)+p->data)/n;}}word文檔精品文檔分享26word文檔精品文檔分享第4章串、數(shù)組和廣義表1．選擇題〔1〕串是一種特殊的線性表，其特殊性表達在〔〕。A．可以順序存儲B．?dāng)?shù)據(jù)元素是一個字符C．可以鏈?zhǔn)酱鎯．?dāng)?shù)據(jù)元素可以是多個字符假設(shè)答案：B〔2〕串下面關(guān)于串的的表達中，〔〕是不正確的？A．串是字符的有限序列B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運算D．串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯Υ鸢福築解釋：空格常常是串的字符集合中的一個元素，有一個或多個空格組成的串成為空格串，零個字符的串成為空串，其長度為零?！?〕串“ababaaababaa〞的 next數(shù)組為〔〕。A．012345678999B．012121111212C．011234223456D．0123012322345答案：C〔4〕串“ababaabab〞的nextval為〔〕。A．010104101B．010102101C．010100011D．010101011答案：A〔5〕串的長度是指〔〕。A．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù)C．串中所含不同字符的個數(shù)D．串中所含非空格字符的個數(shù)答案：B解釋：串中字符的數(shù)目稱為串的長度。〔6〕假設(shè)以行序為主序存儲二維數(shù)組A=array[1..100,1..100]，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10，那么LOC[5,5]=〔〕。A．808B．818C．1010D．1020答案：B解釋：以行序為主，那么LOC[5,5]=[〔5-1〕*100+〔5-1〕]*2+10=818。〔7〕設(shè)有數(shù)組 A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為 1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開場順序存放，當(dāng)用以列為主存放時，元素A[5,8]的存儲首地址為〔〕。A．BA+141B．BA+180C．BA+222D．BA+225答案：B解釋：以列序為主，那么LOC[5,8]=[〔8-1〕*8+〔5-1〕]*3+BA=BA+180?！?〕設(shè)有一個 10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，那么a85的地址為〔〕。word文檔精品文檔分享27word文檔精品文檔分享A．13B．32C．33D．40答案：C〔9〕假設(shè)對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B[1..(n(n+1))/2]中，那么在B中確定aij〕?！瞚<j〕的位置k的關(guān)系為〔A．i*(i-1)/2+jB．j*(j-1)/2+iC．i*(i+1)/2+jD．j*(j+1)/2+i答案：B〔10〕二維數(shù)組A的每個元素是由10個字符組成的串，其行下標(biāo)i=0,1,?,8,列下標(biāo)j=1,2,?,10。假設(shè)A按行先存儲，元素A[8,5]的起始地址與當(dāng)A按列先存儲時的元素〔〕的起始地址一樣。設(shè)每個字符占一個字節(jié)。A．A[8,5]B．A[3,10]C.A[5,8]D．A[0,9]答案：B解釋：設(shè)數(shù)組從內(nèi)存首地址M開場順序存放，假設(shè)數(shù)組按行先存儲，元素A[8,5]的起始地址為：M+[〔8-0〕*10+〔5-1〕]*1=M+84；假設(shè)數(shù)組按列先存儲，易計算出元素A[3,10]的起始地址為：M+[〔10-1〕*9+〔3-0〕]*1=M+84。應(yīng)選B。〔11〕設(shè)二維數(shù)組A[1..m，1..n]〔即m行n列〕按行存儲在數(shù)組B[1..m*n]中，那么二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為〔〕。A．(i-1)*n+jB．(i-1)*n+j-1C．i*(j-1)D．j*m+i-1答案：A解釋：特殊值法。取i=j=1，易知A[1,1]的的下標(biāo)為1，四個選項中僅有A選項能確定的值為1，應(yīng)選A。〔12〕數(shù)組 A[0..4,-1..-3,5..7]中含有元素的個數(shù)〔〕。A．55B．45C．36D．16答案：B解釋：共有5*3*3=45個元素?！?3〕廣義表 A=(a,b,(c,d),(e,(f,g)))，那么Head(Tail(Head(Tail(Tail(A)))))的值為〔〕。A．(g)B．(d)C．cD．d答案：D解釋：Tail(A)=(b,(c,d),(e,(f,g)))；Tail(Tail(A))=((c,d),(e,(f,g)))；Head(Tail(Tail(A)))=(c,d)；Tail(Head(Tail(Tail(A))))=(d)；Head(Tail(Head(Tail(Tail(A)))))=d?！?4〕廣義表((a,b,c,d))的表頭是〔〕，表尾是〔〕。A．a(chǎn)B．()C．(a,b,c,d)D．(b,c,d)答案：C、B解釋：表頭為非空廣義表的第一個元素，可以是一個單原子，也可以是一個子表，((a,b,c,d))的表頭為一個子表(a,b,c,d)；表尾為除去表頭之外，由其余元素構(gòu)成的表，表為一定是個廣義表，((a,b,c,d))的表尾為空表()?！?5〕設(shè)廣義表 L=((a,b,c))，那么L的長度和深度分別為〔〕。A．1和1B．1和3C．1和2D．2和3答案：Cword文檔精品文檔分享28word文檔精品文檔分享解釋：廣義表的深度是指廣義表中展開后所含括號的層數(shù)，廣義表的長度是指廣義表中所含元素的個數(shù)。根據(jù)定義易知L的長度為 1，深度為2。2．應(yīng)用題〔1〕模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個字符對應(yīng)的next和nextval函數(shù)值。答案：模式串t的next和nextval值如下：j123456789101112t串a(chǎn)bcaabbabcabnext[j]011122312345nextval[j]011021301105〔2〕設(shè)目標(biāo)為 t=“abcaabbabcabaacbacba〞,模式為p=“abcabaa〞①計算模式p的naxtval函數(shù)值；②不寫出算法,只畫出利用KMP算法進展模式匹配時每一趟的匹配過程。答案：①p的nextval函數(shù)值為0110132?！瞤的next函數(shù)值為0111232〕。②利用KMP(改良的nextval)算法，每趟匹配過程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配：abcaabbabcabaacbacba(成功)abcabaa(i=15,j=8)〔3〕數(shù)組 A中，每個元素 A[i,j]的長度均為32個二進位 ,行下標(biāo)從 -1到9，列下標(biāo)從 1到11，從首地址 S開場連續(xù)存放主存儲器中，主存儲器字長為16位。求：①存放該數(shù)組所需多少單元？②存放數(shù)組第4列所有元素至少需多少單元？③數(shù)組按行存放時，元素A[7,4]的起始地址是多少？④數(shù)組按列存放時，元素A[4,7]的起始地址是多少？答案：每個元素 32個二進制位，主存字長16位，故每個元素占2個字長，行下標(biāo)可平移至1到11?！?〕242〔2〕22〔3〕s+182〔4〕s+142word文檔精品文檔分享29word文檔精品文檔分享(4)請將香蕉banana用工具H()—Head()，T()—Tail()從L中取出。L=(apple,(orange,(strawberry,(banana)),peach),pear)答案：H〔H〔T〔H〔T〔H〔T〔L〕〕〕〕〕〕〕3．算法設(shè)計題〔1〕寫一個算法統(tǒng)計在輸入字符串中各個不同字符出現(xiàn)的頻度并將結(jié)果存入文件〔字符串中的合法字符為A-Z這26個字母和 0-9這10個數(shù)字〕。[題目分析 ]由于字母共 26個，加上數(shù)字符號10個共 36個，所以設(shè)一長36的整型數(shù)組，前10個分量存放數(shù)字字符出現(xiàn)的次數(shù)，余下存放字母出現(xiàn)的次數(shù)。從字符串中讀出數(shù)字字符時，字符的ASCII代碼值減去數(shù)字字符‘0’的ASCII代碼值，得出其數(shù)值(0..9)，字母的ASCII代碼值減去字符‘A’的ASCII代碼值加上10，存入其數(shù)組的對應(yīng)下標(biāo)分量中。遇其它符號不作處理，直至輸入字符串完畢。[算法描述 ]voidCount〔〕統(tǒng)計輸入字符串中數(shù)字字符和字母字符的個數(shù)。｛inti，num[36]；charch；for〔i＝0；i<36；i++〕num[i]＝０；//初始化while〔〔ch＝getchar〔〕〕!=‘#’〕//‘#’表示輸入字符串完畢。if〔‘0’<=ch<=‘9’〕｛i=ch－48;num[i]++；｝//數(shù)字字符elseif〔‘A’<=ch<=‘Z’〕｛i=ch-65+10;num[i]++；｝//字母字符for〔i=0；i<10；i++〕 //輸出數(shù)字字符的個數(shù)cout<<“數(shù)字〞 <<i<<“的個數(shù)=〞<<num[i]<<endl;for〔i＝10；i<36；i++〕//求出字母字符的個數(shù)cout<<“字母字符〞 <<i+55<<“的個數(shù)=〞<<num[i]<<endl;｝〔2〕寫一個遞歸算法來實現(xiàn)字符串逆序存儲，要求不另設(shè)串存儲空間。[題目分析 ]實現(xiàn)字符串的逆置并不難，但此題“要求不另設(shè)串存儲空間〞來實現(xiàn)字符串逆序存儲，即第一個輸入的字符最后存儲，最后輸入的字符先存儲，使用遞歸可容易做到。[算法描述 ]void InvertStore(char A[])字符串逆序存儲的遞歸算法。{char ch;staticint i=0;//需要使用靜態(tài)變量cin>>ch;if(ch!='.') //規(guī)定'.'是字符串輸入完畢標(biāo)志word文檔精品文檔分享30word文檔精品文檔分享{InvertStore(A);A[i++]=ch;//字符串逆序存儲}A[i]='\0';//字符串結(jié)尾標(biāo)記}〔3〕編寫算法，實現(xiàn)下面函數(shù)的功能。函數(shù)voidinsert(char*s,char*t,intpos)將字符串t插入到字符串s中，插入位置為pos。假設(shè)分配給字符串s的空間足夠讓字符串t插入?！舱f明：不得使用任何庫函數(shù)〕[題目分析 ]此題是字符串的插入問題，要求在字符串s的pos位置，插入字符串t。首先應(yīng)查找字符串s的pos位置，將第pos個字符到字符串s尾的子串向后移動字符串t的長度，然后將字符串t復(fù)制到字符串s的第pos位置后。對插入位置pos要驗證其合法性，小于1或大于串 s的長度均為非法，因題目假設(shè)給字符串s的空間足夠大，故對插入不必判溢出。[算法描述 ]voidinsert(char*s,char*t,intpos)//將字符串 t插入字符串s的第pos個位置。{inti=1,x=0;char*p=s,*q=t;//p，q分別為字符串s和t的工作指針if(pos<1){cout<<“pos參數(shù)位置非法〞<<endl;exit(0);}while(*p!=’0’&&i<pos){p++;i++;}//查pos位置//假設(shè)pos小于串 s長度，那么查到pos位置時，i=pos。if(*p=='/0'){cout<<pos<<"位置大于字符串s的長度";exit(0);}else//查找字符串的尾while(*p!='/0'){p++; i++;}//查到尾時，i為字符‘\0’的下標(biāo)，p也指向‘\0’。while(*q!='\0'){q++; x++; } //查找字符串t的長度 x，循環(huán)完畢時q指向'\0'。for(j=i;j>=pos;j--){*(p+x)=*p;p--;}//串s的pos后的子串右移，空出串t的位置。q--;//指針q回退到串 t的最后一個字符for(j=1;j<=x;j++)*p--=*q--;//將t串插入到s的pos位置上[算法討論 ]串s的完畢標(biāo)記('\0')也后移了，而串t的結(jié)尾標(biāo)記不應(yīng)插入到s中?！?〕字符串S1中存放一段英文，寫出算法format(s1,s2,s3,n),將其按給定的長度n格式化成兩端對齊的字符串S2,其多余的字符送S3。[題目分析 ]此題要求字符串s1拆分成字符串s2和字符串 s3，要求字符串s2“按給定長度n格式化成兩端對齊的字符串〞，即長度為n且首尾字符不得為空格字符。算法從左到右掃描字符串s1，找到第一個非空格字符，計數(shù)到n，第n個拷入字符串s2的字符不得為空格，然后將余下字符復(fù)制到字符串s3中。[算法描述 ]word文檔精品文檔分享31word文檔精品文檔分享voidformat(char*s1,*s2,*s3)//將字符串 s1拆分成字符串s2和字符串 s3，要求字符串s2是長 n且兩端對齊{char*p=s1,*q=s2;inti=0;while(*p!='\0'&&*p=='')p++;//濾掉s1左端空格if(*p=='\0'){cout<<"字符串s1為空串或空格串"<<endl;exit(0);}while(*p!='\0'&&i<n){*q=*p;q++;p++;i++;}字符串s1向字符串s2中復(fù)制if(*p=='\0'){cout<<"字符串s1沒有"<<n<<"個有效字符"<<endl;exit(0);}if(*(--q)=='')//假設(shè)最后一個字符為空格，那么需向后找到第一個非空格字符{p--;//p指針也后退while(*p==''&&*p!='\0')p++;//往后查找一個非空格字符作串s2的尾字符if(*p=='\0'){cout<<"s1串沒有"<<n<<"個兩端對齊的字符串"<<endl;exit(0);}*q=*p;//字符串s2最后一個非空字符*(++q)='\0'; //置s2字符串完畢標(biāo)記}*q=s3;p++;//將s1串其余局部送字符串s3。while(*p!='\0'){*q=*p;q++;p++;}*q='\0';//置串s3完畢標(biāo)記}〔5〕設(shè)二維數(shù)組a[1..m,1..n]含有m*n個整數(shù)。①寫一個算法判斷a中所有元素是否互不一樣?輸出相關(guān)信息 (yes/no)；②試分析算法的時間復(fù)雜度。①[題目分析 ]判斷二維數(shù)組中元素是否互不一樣，只有逐個比擬,找到一對相等的元素，就可結(jié)論為不是互不一樣。如何到達每個元素同其它元素比擬一次且只一次？在當(dāng)前行，每個元素要同本行后面的元素比擬一次〔下面第一個循環(huán)控制變量p的for循環(huán)〕，然后同第i+1行及以后各行元素比擬一次，這就是循環(huán)控制變量k和p的二層 for循環(huán)。[算法描述 ]intJudgEqual(inga[m][n],intm,n)//判斷二維數(shù)組中所有元素是否互不一樣，如是，