算數(shù)提高課件ds總復(fù)習(xí)

1總復(fù)習(xí)算法與數(shù)據(jù)結(jié)構(gòu)張路

2基本題型基本的題型選擇填空判斷解答算法設(shè)計(jì)此膠片內(nèi)容僅僅作為題型參考,決非重點(diǎn)!!!!!3主要內(nèi)容基礎(chǔ)內(nèi)容緒論線性表?xiàng)：完?duì)列樹和二叉樹字典和檢索排序圖4基礎(chǔ)部分習(xí)題數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語算法與算法評(píng)價(jià)（時(shí)間復(fù)雜性和空間復(fù)雜性）線性表的表示和實(shí)現(xiàn)順序表單鏈表循環(huán)鏈表和雙鏈表線性表的應(yīng)用棧隊(duì)列字符串5判斷題順序存儲(chǔ)的線性表可以隨機(jī)存取.在單鏈表中,任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系,因?yàn)榭梢詮念^結(jié)點(diǎn)進(jìn)行查找任何一個(gè)元素.在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰在線性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)在順序表中取出第i個(gè)元素所花費(fèi)的時(shí)間與i成正比YNYYN6選擇題數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（A）和（B），以及這個(gè)結(jié)構(gòu)具有的行為特征，定義相應(yīng)的（C），設(shè)計(jì)出相應(yīng)的（D）。供選擇的答案A.B:1.理想結(jié)構(gòu)2.抽象結(jié)構(gòu)

3.存儲(chǔ)結(jié)構(gòu)4邏輯結(jié)構(gòu)C.D:1.運(yùn)算2.算法3.結(jié)構(gòu) 4.規(guī)則5.現(xiàn)在的6.原來的34127選擇題對(duì)順序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為n，在任何位置上插入或刪除操作都是等概率的。插入一個(gè)元素時(shí)平均要移動(dòng)表中的（）個(gè)元素。A.n/2B.（n+1）/2C.（n-1）/2D.nE.n+1F.n-1A在下標(biāo)為i（第i+1個(gè)）元素之前要插入一個(gè)元素，要移動(dòng)n-(i+1)+1=n-i個(gè)元素；推理過程：8選擇題鏈表不具有的特點(diǎn)是（）。可隨機(jī)訪問任意元素插入和刪除不需要移動(dòng)元素不必事先估計(jì)存儲(chǔ)空間所需空間與線性表長(zhǎng)度成正比A9選擇題若線性表最常用的操作是讀取第i個(gè)元素及其前趨的值，則采用（）存儲(chǔ)方式節(jié)省時(shí)間。A單鏈表B雙鏈表C單循環(huán)鏈表D順序表D10選擇題在雙向鏈表存儲(chǔ)結(jié)構(gòu)中刪除p所指的結(jié)點(diǎn)時(shí)需修改指針()。A.(p－>llink)->rlink=p->rlink；

(p－>rlink)->llink=p－>llink;B.p->llink=(p->llink)->llink;((p->llink)->llink)->rlink=p;C.((p->llink)->llink)->rlink=p;p->llink=(p->llink)->llink;A11解答題1、有如下函數(shù)，分析其時(shí)間復(fù)雜度：intsum(intn){ intsum=0; inti,j,p; for(i=1;i<=n;i++) { p=1; for(j=1;j<=n;j++) p=p*j; sum=sum+p; } return(sum);}解答：該函數(shù)嵌套最深的語句是：p=p*j該語句執(zhí)行的次數(shù)為：n*n所以其時(shí)間復(fù)雜度為O(n2)12算法設(shè)計(jì)已知線性表A長(zhǎng)度為n,并且采用順序存儲(chǔ)結(jié)構(gòu)，寫一算法刪除線性表中所有值為x的元素。main(){ intsuccess,i; PSeqListpSeqList;...... for(i=0;i<pSeqList->n;i++) {if(pSeqList->element[i]==“x”) success=delete_seq(pSeqList,i); if(success==0) {printf(“fault”);exit(0); }}}13算法設(shè)計(jì)單鏈表遍歷：設(shè)計(jì)算法依次打印鏈表中所有結(jié)點(diǎn)的值voidprint(){ p=L; while(p!=NULL) { printf(p->info); p=p->link; }}將L的值賦給Pp為空？打印p的值指針p后移NendYa1a2an^……L14算法設(shè)計(jì)若鏈表L帶有頭結(jié)點(diǎn)，如何修改本算法？

a2an^……La1voidprint(){

p=L->link; while(p!=NULL) { printf(p->info); p=p->link; }}15算法設(shè)計(jì)對(duì)本算法做哪些修改可以得到鏈表的長(zhǎng)度？intprint(){

intlength;

length=0; p=L->link; while(p!=NULL) { printf(p->info); p=p->link;

length++; } return(length);}16算法設(shè)計(jì)若L為帶頭結(jié)點(diǎn)的單循環(huán)鏈表，怎樣修改本算法？

a2an

……La1voidprint(){

p=L->link;if(p==NULL)return; do { printf(p->info); p=p->link; }while(p!=L->link)}17帶頭結(jié)點(diǎn)的鏈表與不帶頭結(jié)點(diǎn)的鏈表比較若鏈表L1帶有頭結(jié)點(diǎn)，L2不帶頭結(jié)點(diǎn)，刪除a2的算法？

a2an^……L1a1voiddelete-a1(){

p=L1->link;

while(p!=NULL&&p->data!=a2) p=p->link;if(p!=NULL) {

刪除操作

}else printf(“nonode”)}a2an^……L2a1voiddelete-a2(){

if(L2!=NULL)

p=L2;else printf(“thelistisempty!”) while(p!=NULL&&p->data!=a2) p=p->link;

if(p!=NULL) {

刪除操作

}else printf(“nonode”)}18算法設(shè)計(jì)假設(shè)有兩個(gè)已排序的單鏈表A和B，編寫一個(gè)函數(shù)將它們合并成一個(gè)鏈表C而不改變其排序性思路：采用鏈表合并的方法，設(shè)原鏈表的頭指針分別為p和q，每次比較p->data和q->data的值，把值較小的結(jié)點(diǎn)作為新鏈表的結(jié)點(diǎn)，這一過程直到進(jìn)行到其中一個(gè)鏈表為空為止 當(dāng)一個(gè)鏈表為空而另一個(gè)鏈表不為空時(shí)，只要將不空的鏈表指針賦給新鏈表中最后一個(gè)結(jié)點(diǎn)的指針域即可怎樣做最節(jié)省空間？？19樹和二叉樹部分習(xí)題二叉樹基本概念、術(shù)語、性質(zhì)、兩種特殊的二叉樹二叉樹的基本運(yùn)算二叉樹的實(shí)現(xiàn)二叉樹的周游樹與樹林基本概念樹的周游哈夫曼算法及其應(yīng)用哈夫曼樹和哈夫曼算法哈夫曼編碼、譯碼20選擇題如果結(jié)點(diǎn)A有3個(gè)兄弟（不包括A本身）,而且B是A的雙親,則B的度是（）。A.3B.4C.5D.1B21如圖所示二叉樹的中序遍歷序列是（）。AabcdgefBdfebagcCdbaefcgDdefbagc選擇題Babcdgef22選擇題已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是（）。AacbedBdecabCdeabcDcedbaD23選擇題設(shè)n,m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是（）。An在m右方Bn在m祖先Cn在m左方Dn在m子孫C24選擇題某二叉樹T有n個(gè)結(jié)點(diǎn),設(shè)按某種順序?qū)中的每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)值為1,2,...n.且有如下性質(zhì)：T中任意結(jié)點(diǎn)v，其編號(hào)等于左子樹上的最小編號(hào)減一，而v的右子樹的結(jié)點(diǎn)中，其最小編號(hào)等于v左子樹上結(jié)點(diǎn)的最大編號(hào)加一，這時(shí)按()編號(hào)的。A.中序遍歷序列B.前序遍歷序列C.后序遍歷序列D.層次順序B25選擇題在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊()。A.只有右子樹上的所有結(jié)點(diǎn)B.只有右子樹上的部分結(jié)點(diǎn)C.只有左子樹上的所有結(jié)點(diǎn)D.只有左子樹上的部分結(jié)點(diǎn)A26解答假設(shè)某一類電文d={d1，d2，…，dm}組成，它們的出現(xiàn)頻率w={2，3，5，7，11，13，17，19，23，29，31，37，41}，試給出d1的哈夫曼編碼，并給出d1d2dm的編碼和解碼過程。27算法設(shè)計(jì)二叉樹采用鏈接存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)按層次順序（同一層自左向右）/后根順序遍歷二叉樹的算法解題思路：采用一個(gè)隊(duì)列q，先講二叉樹根結(jié)點(diǎn)入隊(duì)列，然后退隊(duì)列，輸出該結(jié)點(diǎn)，若它有左子樹，便將左子樹的根結(jié)點(diǎn)入隊(duì)列，若它有右子樹，便將右子樹根結(jié)點(diǎn)入隊(duì)列，如此直到隊(duì)列為空為止因?yàn)殛?duì)列是先進(jìn)先出的，從而達(dá)到按層次順序遍歷二叉樹的目的p11228字典和檢索習(xí)題順序表表示順序檢索算法\二分法檢索算法散列構(gòu)造的字典和檢索散列函數(shù)\碰撞處理二叉樹表示二叉排序樹的檢索\二叉排序樹的插入和構(gòu)造\二叉排序樹的刪除AVL樹索引簡(jiǎn)介29判斷題散列法存儲(chǔ)的基本思想是由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址一個(gè)二叉排序樹的查找時(shí)間一定小于用順序查找同樣結(jié)點(diǎn)的線形表的查找時(shí)間YN30選擇題對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須()。A.以順序方式存儲(chǔ)B.以鏈接方式存儲(chǔ)C.以順序方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序D.以鏈接方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序C31選擇題有一個(gè)有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100}，當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí)，()次比較后成功。A.1B.2C.4D.8C32選擇題采用二分查找方法進(jìn)行查找時(shí)，數(shù)據(jù)文件應(yīng)為（A），且限于（B）。要進(jìn)行順序查找，則線性表（C）。

A,B：1.有序表2.隨機(jī)表3.散列存儲(chǔ)結(jié)構(gòu)4.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)5.順序存儲(chǔ)結(jié)構(gòu)6.線性表C：1.必須以順序方式存儲(chǔ)2.必須以鏈?zhǔn)椒绞酱鎯?chǔ)3.既可以以順序方式存儲(chǔ)，也可以以鏈?zhǔn)欠绞酱鎯?chǔ)

15333解答題設(shè)一組關(guān)鍵字{19，1，14，20，84，27，53，11，56，23}，采用哈希函數(shù)：H(key)=keyMOD10，采用開放地址法的隨機(jī)探測(cè)再散列方法解決沖突，試在0～10的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造哈希表。

34排序習(xí)題排序的基本概念插入排序=>直接插入排序/折半插入排序/Shell排序選擇排序=>直接選擇排序/堆排序交換排序=>起泡排序/快速排序分配排序=>基數(shù)排序歸并排序=>歸并排序排序算法的比較和選擇35判斷題如果某種算法是不穩(wěn)定的,則該方法沒有實(shí)際應(yīng)用價(jià)值對(duì)于n個(gè)記錄的集合進(jìn)行冒泡排序，所需要的平均時(shí)間是O(n）對(duì)于n個(gè)記錄的集合進(jìn)行快速排序，在最壞情況下所需要的平均時(shí)間是O(n2）對(duì)n個(gè)元素的序列進(jìn)行起泡排序時(shí),最小的比較次數(shù)是n-1NNYY36選擇題對(duì)n個(gè)不同的排序碼的元素進(jìn)行不減序冒泡排序，在（A）情況下比較的次數(shù)最少，其比較次數(shù)為（B）;在（C）情況下比較的次數(shù)最多，其比較次數(shù)為（D）。供選擇的答案A.C:1.從大到小排列好的2.從小到大排列好的3.元素?zé)o序4元素基本有序邏輯結(jié)構(gòu)B,D:1.n+12.n3.n-14.n(n-1)/2231437選擇題排序的方法有很多種，（A）法從未排序序列中依次取出元素，與以排序序列（初始時(shí)為空）中的元素做比較，將其放入以排序序列的正確位置上。（B）法從未排序序列中挑選元素，并將其放入以排序序列的一端。交換排序法是對(duì)序列中元素進(jìn)行一系列比較，當(dāng)被比較的元素為逆序時(shí)，進(jìn)行交換；（C）和（D）是基于這類方法的兩種排序方法，而D是比C效率更高的方法。供選擇的答案1，選擇排序2，快速排序3，插入排序4，冒泡排序5，折半排序

314238選擇題在內(nèi)排序的過程中，通常需要對(duì)待排序的關(guān)鍵碼集合進(jìn)行多便掃描。采取不同排序方法會(huì)產(chǎn)生不同的排序中間結(jié)果。設(shè)要將序列{Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X}中的關(guān)鍵碼按字母序的升序重新排列，則（A）是冒泡排序的一躺掃描結(jié)果，（B）是初始步長(zhǎng)為4的希爾排序一趟的結(jié)果，（C）是二路歸并排序的一躺掃描結(jié)果。（D）是以第一個(gè)元素為分界元素的快速排序的一躺掃描結(jié)果。

供選擇的答案A~E：1，F(xiàn)，H，C，D，P，A，M，Q，R，S，Y，X2，P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y3，A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X4，H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y5，H，Q，C，Y，A，P，M，S，D，R，F(xiàn)，X

425139選擇題下述幾種排序方法中，平均情況下要求內(nèi)存量最大的是()。A.插入排序B.選擇排序C.快速排序D.冒泡排序

C40填空題在下列冒泡排序算法中填入適當(dāng)內(nèi)容,以使該算法發(fā)現(xiàn)有序時(shí)能及時(shí)停止:a為一數(shù)組,定義為inta[n]VoidBuble(int*a){inti=1;boolexchanged;do{ exchanged=false; for(intj=n-1;

;j--){ if(a[j]<a[j-1]){ ;; ;;} i++;}while(i<n&&

)}exchangedj>=iint