數(shù)據(jù)結(jié)構(gòu)期末習(xí)題答案

1、第一章 緒 論一，選擇題1組成數(shù)據(jù)的基本單位是（）A數(shù)據(jù)項(xiàng)B數(shù)據(jù)類型C數(shù)據(jù)元素D數(shù)據(jù)變量2數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（）以及它們之間的相互關(guān)系。A理想結(jié)構(gòu)，物理結(jié)構(gòu) B理想結(jié)構(gòu)，抽象結(jié)構(gòu)C物理結(jié)構(gòu)，邏輯結(jié)構(gòu) D抽象結(jié)構(gòu)，邏輯結(jié)構(gòu)3算法分析的兩個(gè)主要方面是（ ）A正確性和簡(jiǎn)單性 B可讀性和文檔性C數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 D時(shí)間復(fù)雜度和空間復(fù)雜度4算法分析的目的是（）。A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系C分析算法的效率以求改進(jìn)D分析算法的易懂性和文檔性5. 算法的時(shí)間復(fù)雜度取決于（ ）A問(wèn)題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B 以上都不是6一個(gè)算法應(yīng)該是（ ）。 A程序 B

2、問(wèn)題求解步驟的描述 C要滿足五個(gè)基本特性 DA和C. 7. 下面關(guān)于算法說(shuō)法錯(cuò)誤的是（ ）A算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B.為解決某問(wèn)題的算法同為該問(wèn)題編寫的程序含義是相同的C. 算法的可行性是指指令不能有二義性 D. 以上幾個(gè)都是錯(cuò)誤的8從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類。A動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)9程序段 for ( i=n-1;i=1;i-) for (j=1jAj+1) Aj與Aj+1對(duì)換；其中 n為正整數(shù)，則最后一行的語(yǔ)句頻度在最壞情況下是（ ）A O（n） B O(nlogn) C.O(n3) DO(n2) 10連

3、續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（ ）。A一定連續(xù) B一定不連續(xù) C不一定連續(xù) D部分連續(xù)，部分不連續(xù)二，判斷題1數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。( ) 2數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對(duì)象與對(duì)象中數(shù)據(jù)元素之間關(guān)系的集合。3在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。( )4數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用的需要建立的。5算法和程序原則上沒(méi)有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)是兩者是通用的。6同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)都相等。7數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。8算法的優(yōu)劣與算法描述語(yǔ)言無(wú)關(guān)，但與所用計(jì)算機(jī)有關(guān)。( )9

4、健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。( )10算法可以用不同的語(yǔ)言描述，如果用C 語(yǔ)言或PASCAL語(yǔ)言等高級(jí)語(yǔ)言來(lái)描述，則算法實(shí)際上就是程序了。( ) 一，選擇題1C2C3D4C5C6B7D8C9D10A二，判斷題1. 2. 3. 4. 5.6. 7. 8.9. 10.三，填空1數(shù)據(jù)的物理結(jié)構(gòu)包括 的表示和 的表示。2. 對(duì)于給定的n個(gè)元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有 ， ， ，_ _四種。3一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中 稱為存儲(chǔ)結(jié)構(gòu)。4抽象數(shù)據(jù)類型的定義僅取決于它的一組_ _，而與_ _無(wú)關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的_ _不變，都不影響其外部使用。5線性結(jié)構(gòu)中元素之間存在

5、關(guān)系,樹(shù)形結(jié)構(gòu)中元素之間存在 關(guān)系,圖形結(jié)構(gòu)中元素之間存在 關(guān)系。6一個(gè)算法有5個(gè)特性: 、 、 ，有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。7已知如下程序段for （i= n；i=1;i+） 語(yǔ)句1x:=x+1； 語(yǔ)句2for( j=n;j=i ;j+) 語(yǔ)句3 y:=y+1; 語(yǔ)句4語(yǔ)句1執(zhí)行的頻度為 ；語(yǔ)句2執(zhí)行的頻度為 ；語(yǔ)句3執(zhí)行的頻度為 ；語(yǔ)句4執(zhí)行的頻度為 。8在下面的程序段中，對(duì)的賦值語(yǔ)句的頻度為_(kāi)（表示為n的函數(shù)） for(i1;i=n;i+)for(j;j=i;j+)for(k1;k=j;j+)delta；9. 計(jì)算機(jī)執(zhí)行下面的語(yǔ)句時(shí)，語(yǔ)句s的執(zhí)行次數(shù)為 _ 。 for(i=l；

6、i=i;j-) s; 10. 下面程序段的時(shí)間復(fù)雜度為_(kāi)。(n1) sum=1； for (i=0;sumn;i+) sum+=1; 三，填空題1數(shù)據(jù)元素 數(shù)據(jù)元素間關(guān)系 2集合 線性結(jié)構(gòu) 樹(shù)形結(jié)構(gòu) 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)3表示（又稱映像）。 4邏輯特性 在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn) 數(shù)學(xué)特性5 一對(duì)一一對(duì)多多對(duì)多6 有窮性 確定性 可行性7 n+1 n n(n+3)/2 n(n+1)/281+（1+2+（1+2+3）+（1+2+n）=n(n+1)(n+2)/6 O(n3)9. (n+3)(n-2)/2 10. O(n)四，應(yīng)用題1什么是數(shù)據(jù)? 它與信息是什么關(guān)系?2什么是數(shù)據(jù)結(jié)構(gòu)? 數(shù)據(jù)結(jié)構(gòu)是研究

7、什么內(nèi)容的學(xué)科？有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論涉及哪三方面?3評(píng)價(jià)一個(gè)好的算法，從哪幾方面考慮？4. 若將數(shù)據(jù)結(jié)構(gòu)定義為一個(gè)二元組（D，R）,說(shuō)明符號(hào)D，R 應(yīng)分別表示什么？5解釋算法與程序的區(qū)別？6有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，畫出它們分別對(duì)應(yīng)的邏輯圖形表示，并指出它們分別屬于何種結(jié)構(gòu)。（1）A=（K，R），其中：K=a，b，c，d，e，f，gR=rr=a，b，b，c，c，d，d，e，e，f，f，g（2）B=（K，R），其中：K=a，b，c，d，e，f，g，hR=rr=d，b，d，g，d，a，b，c，g，e，g，h，a，f（3）C=（K，R），其中：K=1，2，3，4，5，6R=rr=(1, 2)，

8、(2, 3)，（2，4），（3，4），（3，5），（3，6），（4，5），（4,6）這里的圓括號(hào)對(duì)表示兩結(jié)點(diǎn)是雙向的。7分析以下程序段的時(shí)間復(fù)雜度。（1）a=0；b=1；for（i=2；i=n；i+）s=a+b；b=a；a=S；（2）inti，j，k；for（i=0；in；i+for（j=0；jn；j+cij=0；for（k=0；kn；k+cij=cij+aik+bkj；8求下列算法段的語(yǔ)句頻度及時(shí)間復(fù)雜度（1）for(i=1; i=n; i+)for(j =1; j =i ; j+)x=x+1;（2）for （i=1;i=n;i+）for (j=1;j=i;j+)for ( k=1;knex

9、t=h B. p-next=NIL C. p-next-next=h D. p-data=-12下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（ ）A線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。3線性表是具有n個(gè)（ ）的有限序列（n0）。 A表元素 B字符 C數(shù)據(jù)元素 D數(shù)據(jù)項(xiàng) 4若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ ）存儲(chǔ)方式最節(jié)省時(shí)間。A順序表 B雙鏈表 C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D單循環(huán)鏈表5某線性表中最常用的

10、操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表6設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用( )最節(jié)省時(shí)間。A. 單鏈表 B.單循環(huán)鏈表 C. 帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表7在帶有頭結(jié)點(diǎn)的單鏈中插入一個(gè)新結(jié)點(diǎn)時(shí)不可能修改（ ）。A 頭指針 B頭結(jié)點(diǎn)指針域 C 開(kāi)始結(jié)點(diǎn)指針域 D其它結(jié)點(diǎn)指針域8 雙向鏈表中有兩個(gè)指針域，llink和rlink，分別指向前驅(qū)及后繼，設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(xiàn)要求在p前插入q，則正確的插入為（ ）。

11、 A. p-llink=q; q-rlink=p; p-llink-rlink=q; q-llink=p-llink;B. q-llink=p-llink; p-llink-rlink=q; q-rlink=p; p-llink=q-rlink; C. q-rlink=p; p-rlink=q; p-llink-rlink=q; q-rlink=p;D. p-llink-rlink=q; q-rlink=p; q-llink=p-llink; p-llink=q;9對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（ ）。Ahead=NULL Bheadnext=NULL Ch

12、eadnext=head Dhead!=NULL10在順序表中查找第i個(gè)元素的時(shí)間效率最高的算法時(shí)間復(fù)雜度是（ ）。AO(1) BO() CO(log2n) DO(n) 11最好的情況下，在順序表中按值查找一個(gè)元素的算法時(shí)間復(fù)雜度是（ ）。AO(n) BO() CO(log2n) DO(1) 12. 若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（ ）(1=ilink=head Bp-link=NIL Cp=NIL Dp= head一，選擇1.A2.B3.C4.A5.D6.D7.A8.D9.B10.A11D12.C13.C14.C15.A二，判斷1. 鏈表

13、中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用。( ) 2線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。( )3順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。( )4順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。( )5線性表的鏈接存儲(chǔ)，表中元素的邏輯順序與物理順序一定相同。6. 線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。( )7. 取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān)。 ( )8. 循環(huán)鏈表不是線性表。 ( ) 9. 線性表就是順序存儲(chǔ)的表。( )10. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。( )二，判斷1. 2. 3.4. 5. 6.7.8.9. 10.三，填空1

14、當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用_存儲(chǔ)結(jié)構(gòu)。2線性表L=（a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是_。3在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1=inext=p； s-prior= _；p-prior=s；_=s；7.順序存儲(chǔ)結(jié)構(gòu)通過(guò)_表示元素之間的關(guān)系;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通過(guò)_表示元素之間的關(guān)系。8. 對(duì)于雙向鏈表,在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共 _個(gè)，單鏈表為_(kāi)個(gè)。9. 已知指針p指向單鏈表L中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語(yǔ)句是：_,時(shí)間復(fù)雜度是 。10. 帶

15、頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是： 。三，填空1順序 2（n-1）/2 3 n-i+14O(1)，O(n) 5f-next=p-next; f-prior=p; p-next-prior=f; p-next=f;6p-prior s-prior-next7物理上相鄰 指針 84 29u=p-next; p-next=u-next; free(u); O(1) ; 10L-next-next=L 四，算法設(shè)計(jì)1試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作LOCATE（L，X）。2試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作LENGTH（L）。3試寫一算法實(shí)現(xiàn)順序表的就地逆置

16、，即利用原表的存儲(chǔ)空間將線性表（a1, a2, ,an）逆置為（an, an-1, ,a1）。4 試寫一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。5 設(shè)線性表A =（a1， a2， ,an），B=（b1, b2, ,bn），試寫一個(gè)按下列規(guī)則合并A，B為線性表C的算法，即使得C=（a1, b1, , am ,bm ,bm+1, ,bn） 當(dāng)mn時(shí)；線性表A，B和C均以單鏈表作存儲(chǔ)結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：?jiǎn)捂湵淼拈L(zhǎng)度值m和n均未顯式存儲(chǔ)。1LNode* Locate(LinkList L,int x)/鏈表上的元素查找,返回指針for(p=l-next;p&p-data!=x;p=p

17、-next);return p;/Locate 2int Length(LinkList L)/求鏈表的長(zhǎng)度f(wàn)or(k=0,p=L;p-next;p=p-next,k+);return k;/Length3void reverse(SqList &A)/順序表的就地逆置for(i=0,j=A.length-1;ij;i+,j-)A.elemiA.elemj;/reverse 4void LinkList_reverse(Linklist &L)/鏈表的就地逆置;為簡(jiǎn)化算法,假設(shè)表長(zhǎng)大于2p=L-next;q=p-next;s=q-next;p-next=NULL;while(s-next)q-

18、next=p;p=q;q=s;s=s-next; /把L的元素逐個(gè)插入新表表頭q-next=p;s-next=q;L-next=s;/LinkList_reverse分析:本算法的思想是,逐個(gè)地把L的當(dāng)前元素q插入新的鏈表頭部,p為新表表頭.5void merge1(LinkList &A,LinkList &B,LinkList &C)/把鏈表A和B合并為C,A和B的元素間隔排列,且使用原存儲(chǔ)空間p=A-next;q=B-next;C=A;while(p&q)s=p-next;p-next=q; /將B的元素插入if(s)t=q-next;q-next=s; /如A非空,將A的元素插入p=s

19、;q=t;/while/merge1第三章 棧和隊(duì)列一，選擇1. 對(duì)于棧操作數(shù)據(jù)的原則是（ ）。A. 先進(jìn)先出 B. 后進(jìn)先出 C. 后進(jìn)后出 D. 不分順序3. 最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是 （ ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front4當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top= =n表示?？?，則向這個(gè)棧插入一個(gè)元素時(shí)首先應(yīng)執(zhí)行 語(yǔ)句修改top指針。Atop+ Btop- Ctop=0 Dtop5. 若已知一個(gè)棧的入棧序

20、列是1,2,3,n，其輸出序列為p1,p2,p3，pN,若pN是n，則pi是( )。 A. i B. n-i C. n-i+1 D. 不確定6. 一個(gè)遞歸算法必須包括（ ）。A. 遞歸部分 B. 終止條件和遞歸部分 C. 迭代部分 D.終止條件和迭代部分7. 執(zhí)行完下列語(yǔ)句段后，i值為：（ ） int f(int x) return (x0) ? x* f(x-1):2); int i ; i =f(f(1);A2 B. 4 C. 8 D. 無(wú)限遞歸8. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2，e4

21、，e3,e6,e5,e1則棧S的容量至少應(yīng)該是( )。A 6 B. 4 C. 3 D. 29. 棧和隊(duì)列的共同點(diǎn)是（ ）。A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒(méi)有共同點(diǎn)10. 設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲(chǔ)結(jié)構(gòu) B. 隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D. 棧11. 用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)( )。A僅修改隊(duì)頭指針 B. 僅修改隊(duì)尾指針 C. 隊(duì)頭、隊(duì)尾指針都要修改 D. 隊(duì)頭,隊(duì)尾指針都可能要修改12. 遞歸過(guò)程

22、或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列 B多維數(shù)組 C棧 D. 線性表13. 假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素,其頭尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m14. 循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A0.m中，則入隊(duì)時(shí)的操作為（ ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 15. 若用一個(gè)

23、大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 一，選擇1.B3.B4 B5.D6.B7.B8.C9.C10.D11.D12.C13.A14.D15.B二，填空1_是限定僅在表尾進(jìn)行插入或刪除操作的線性表。3中綴表達(dá)式3*（x+2）-5所對(duì)應(yīng)的后綴表達(dá)式為 ；后綴表達(dá)式“45*32+-”的值為 。4. 順序棧用data1.n存儲(chǔ)數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是_。5向一個(gè)循環(huán)隊(duì)列中插入一元素時(shí)，需首先移動(dòng) ，

24、然后再向所指位置 新插入的元素。 6用下標(biāo)0開(kāi)始的N元數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列時(shí)，為實(shí)現(xiàn)下標(biāo)變量M加1后在數(shù)組有效下標(biāo)范圍內(nèi)循環(huán)，可采用的表達(dá)式是： M= _7用長(zhǎng)度為n的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，若用top= =n表示棧空，則表示棧滿的條件為 。二，填空1棧 33 x 2 + * 5 - 154data+top=x； 5 隊(duì)尾指針 寫入6(M+1) MOD N (M+1)% N； 7top=0三，應(yīng)用題1指出下列程序段的功能(1) void Demo1(SeqStack *S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S);for (i=0,

25、 i n; i+) Push(S, arri); /Demo1(2) SeqStack S1, S2, tmp;DataType x;./假設(shè)棧tmp和S2已做過(guò)初始化while ( ! StackEmpty (&S1)x=Pop(&S1) ;Push(&tmp,x);while ( ! StackEmpty (&tmp) )x=Pop( &tmp);Push( &S1,x);Push( &S2, x);(1)程序段的功能是將一棧中的元素按反序重新排列，也就是原來(lái)在棧頂?shù)脑胤诺綏５?，棧底的元素放到棧頂。此棧中元素個(gè)數(shù)限制在64個(gè)以內(nèi)。(2)程序段的功能是利用tmp棧將一個(gè)非空棧s1的所有元素

26、按原樣復(fù)制到一個(gè)棧s2當(dāng)中去。四，算法設(shè)計(jì)題1 回文是指正讀反讀均相同的字符序列，如abba和abdba均是回文，但good不是回文。試寫一個(gè)算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)1 根據(jù)提示，算法可設(shè)計(jì)為：/以下為順序棧的存儲(chǔ)結(jié)構(gòu)定義#define StackSize 100 /假定預(yù)分配的?？臻g最多為100個(gè)元素typedef char DataType;/假定棧元素的數(shù)據(jù)類型為字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwen( char *t)/判斷t字符向量是否為回文，若是，返回

27、1，否則返回0SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); /求向量長(zhǎng)度f(wàn)or ( i=0; ilen/2; i+)/將一半字符入棧Push( &s, ti);while( !EmptyStack( &s)/ 每彈出一個(gè)字符與相應(yīng)字符比較temp=Pop (&s);if( temp!=Si) return 0 ;/ 不等則返回0else i+;return 1 ; / 比較完畢均相等則返回 1第四章 串一，選擇1下面關(guān)于串的的敘述中，哪一個(gè)是不正確的？（ ）A串是字符的有限序列 B空串是由空格構(gòu)成的串C模式匹配是串

28、的一種重要運(yùn)算 D串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)2設(shè)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（ ）A求子串 B聯(lián)接 C匹配 D求串長(zhǎng)3串的長(zhǎng)度是指（ ）A串中所含不同字母的個(gè)數(shù) B串中所含字符的個(gè)數(shù)C串中所含不同字符的個(gè)數(shù) D串中所含非空格字符的個(gè)數(shù)4若串S=software,其子串的數(shù)目是（ ）。A8 B37 C36 D9一，選擇 1.B2.C3B4.B二，填空1空格串是指_，其長(zhǎng)度等于_。 2組成串的數(shù)據(jù)元素只能是_。 3一個(gè)字符串中_稱為該串的子串 。 4INDEX（DATASTRUCTURE， STR）=_。7設(shè)T和P是兩個(gè)給定的串，在T中尋找等于

29、P的子串的過(guò)程稱為_(kāi)，又稱P為_(kāi)。二，填空1由空格字符（ASCII值32）所組成的字符串 空格個(gè)數(shù) 2字符3任意個(gè)連續(xù)的字符組成的子序列 45 7模式匹配 模式串 第五章 數(shù)組和廣義表一，選擇1. 已知廣義表L=（x,y,z），a，（u，t，w），從L表中取出原子項(xiàng)t的運(yùn)算是（ ）。A. head（tail（tail（L） B. tail（head（head（tail（L） C. head（tail（head（tail（L） D. head（tail(head（tail（tail（L）)）2. 廣義表A=(a,b,(c,d),(e,(f,g),則下面式子的值為（ ）。Head(Tail(Hea

30、d(Tail(Tail(A)A. (g) B. (d) C. c D. d3.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種,即（）A 二維數(shù)組和三維數(shù)組 B三元組和散列C三元組和十字鏈表 D散列和十字鏈表4. 二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，其行下標(biāo)i=0,1,8,列下標(biāo)j=1,2,10。若A按行先存儲(chǔ)，元素A8,5的起始地址與當(dāng)A按列先存儲(chǔ)時(shí)的元素（ ）的起始地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。A. A8,5 B. A3,10 C. A5,8 D. A0,95. 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)目的是（ ）。A便于進(jìn)行矩陣運(yùn)算 B便于輸入和輸出 C節(jié)省存儲(chǔ)空間 D降低運(yùn)算的時(shí)間復(fù)雜度6. 設(shè)A是n*n的對(duì)稱

31、矩陣，將A的對(duì)角線及對(duì)角線上方的元素以列為主的次序存放在一維數(shù)組B1.n(n+1)/2中，對(duì)上述任一元素aij(1i，jn，且ij)在B中的位置為( )。A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-17. AN，N是對(duì)稱矩陣，將下面三角（包括對(duì)角線）以行序存儲(chǔ)到一維數(shù)組TN（N+1）/2中，則對(duì)任一上三角元素aij對(duì)應(yīng)Tk的下標(biāo)k是（ ）。A i（i-1）/2+j B j（j-1）/2+i C i（j-i）/2+1 D j（i-1）/2+18. 設(shè)廣義表L=（a,b,c），則L的長(zhǎng)度和深度分別為（ ）。 A. 1和1 B.

32、 1和3 C. 1和2 D. 2和3 9. 數(shù)組A0.4,-1.-3,5.7中含有元素的個(gè)數(shù)（ ）。A 55 B45 C 36 D1610. 下面說(shuō)法不正確的是( )。 A. 廣義表的表頭總是一個(gè)廣義表 B. 廣義表的表尾總是一個(gè)廣義表C. 廣義表難以用順序存儲(chǔ)結(jié)構(gòu) D. 廣義表可以是一個(gè)多層次的結(jié)構(gòu)一，選擇 1.D2.D3.C4.B5.C6.B7.B8.C9.B10.A二，判斷1 一個(gè)稀疏矩陣Am*n采用三元組形式表示， 若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把m和n的值互換，則就完成了Am*n的轉(zhuǎn)置運(yùn)算。（ ）2. 從邏輯結(jié)構(gòu)上看，n維數(shù)組的每個(gè)元素均屬于n個(gè)向量。（ ）3. 稀疏矩陣

33、壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。（ ）4. 對(duì)長(zhǎng)度為無(wú)窮大的廣義表，由于存儲(chǔ)空間的限制，不能在計(jì)算機(jī)中實(shí)現(xiàn)。（ ）5. 數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣可對(duì)它進(jìn)行插入，刪除操作。（ ） 6. 所謂取廣義表的表尾就是返回廣義表中最后一個(gè)元素。（ ）7. 二維以上的數(shù)組其實(shí)是一種特殊的廣義表。（ ） 8. 廣義表的取表尾運(yùn)算，其結(jié)果通常是個(gè)表，但有時(shí)也可是個(gè)單元素值。（ ）9. 若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。（ ）10. 廣義表中的元素或者是一個(gè)不可分割的原子，或者是一個(gè)非空的廣義表。（ ）二，判斷1.2.3.4. 5.6. 7.8.9.10.四應(yīng)用題1. 畫出下列

34、廣義表的兩種存儲(chǔ)結(jié)構(gòu)圖(),A,(B,(C,D),(E,F)。2. 設(shè)某表H如下：ABCXa1a2 b1 c1c2其中A,B,C為子表名，a1,a2,b1,c1,c2,x為其元素。試用廣義表形式表示H,并寫出運(yùn)算HEAD(H)和TAIL(H) 函數(shù)從H中取出單元素a2的運(yùn)算；（1）H(A(a1,a2）,B(b1）,C(c1，c2）,x）HEAD(TAIL(HEAD(H)=a2五，算法設(shè)計(jì)1 設(shè)任意n個(gè)整數(shù)存放于數(shù)組A(1:n)中，試編寫程序，將所有正數(shù)排在所有負(fù)數(shù)前面 2. 設(shè)二維數(shù)組a1.m, 1.n 含有m*n 個(gè)整數(shù)。判斷a中所有元素是否互不相同?輸出相關(guān)信息(yes/no)。1.本題屬

35、于排序問(wèn)題，只是排出正負(fù)，不排出大小?？稍跀?shù)組首尾設(shè)兩個(gè)指針i和j，i自小至大搜索到負(fù)數(shù)停止，j自大至小搜索到正數(shù)停止。然后i和j所指數(shù)據(jù)交換，繼續(xù)以上過(guò)程，直到 i=j為止。void Arrange(int A,int n) /n個(gè)整數(shù)存于數(shù)組A中，本算法將數(shù)組中所有正數(shù)排在所有負(fù)數(shù)的前面 int i=0,j=n-1,x; /用類C編寫，數(shù)組下標(biāo)從0開(kāi)始 while(ij)while(i0) i+;while(ij & Aj0) j-; if(ij) x=Ai; Ai+=Aj; Aj-=x; /交換Ai 與Aj /算法Arrange結(jié)束.算法討論對(duì)數(shù)組中元素各比較一次，比較次數(shù)為n。最佳情況(已排好,正數(shù)在前,負(fù)數(shù)在后)不發(fā)生交換，最差情況(負(fù)數(shù)均在正數(shù)前面)發(fā)生n/2次交換。用類c編寫，數(shù)組界偶是0.n-1。空間復(fù)雜度為O(1).2.判斷二維數(shù)組中元素是否互不相同，只有逐個(gè)比較,找到一對(duì)相等的元素，就可結(jié)論為不是互不相同。如何達(dá)到每個(gè)元素同其它元素比較一次且只一次？在當(dāng)前行，每個(gè)元素要同本行后面的元素比較一次（下面第一個(gè)循環(huán)控制變量p的for循環(huán)），然后同第i+1行及以后各行元素比較一次，這就是循環(huán)控制變量k和p的二層for循環(huán)。int JudgEqual(ing amn,int m,n) /判斷二維數(shù)組中所有元素是否互不相同，如是，返回1；否則，返回0。fo