2020年電大數(shù)據(jù)結(jié)構(gòu)本期末考試試卷重點匯總

文檔僅供參考最新電大數(shù)據(jù)結(jié)構(gòu)[本]期末考試試卷重點匯總考試答題注意事項:1、考生答題前,先將自己的姓名、準(zhǔn)考證號等信息填寫清楚,同時將條形碼準(zhǔn)確粘貼在考生信息條形碼粘貼區(qū)。2、考試答題時,選擇題必須使用2B鉛筆填涂；非選擇題必須使用0、5毫米黑色字跡的簽字筆書寫,字體工整、筆跡清晰。3、請考生按照題號順序,在各題目的答題區(qū)域內(nèi)作答,超出答題區(qū)域書寫的答案無效；在草稿紙、試題卷上答題無效。4、請考生保持答題卡面清潔,不要折疊、弄破、弄皺,不準(zhǔn)使用涂改液、修正液、刮紙刀。【本部分作業(yè)覆蓋教材第1-2章的內(nèi)容】一、單項選擇題1、在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上能夠把數(shù)據(jù)結(jié)構(gòu)分為【C】、A、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)D、內(nèi)部結(jié)構(gòu)和外部機(jī)構(gòu)2、下面說法中,錯誤的是【D】、A、數(shù)據(jù)元素是數(shù)據(jù)的基本單位B、數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小可標(biāo)識單位C、數(shù)據(jù)可有若干個數(shù)據(jù)元素構(gòu)成D、數(shù)據(jù)項可由若干個數(shù)據(jù)元素構(gòu)成3、一個存儲結(jié)點存儲一個【B】、A、數(shù)據(jù)項B、數(shù)據(jù)元素C、數(shù)據(jù)結(jié)構(gòu)D、數(shù)據(jù)類型4、數(shù)據(jù)結(jié)構(gòu)中,和所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的【C】、A、存儲結(jié)構(gòu)B、物理結(jié)構(gòu)C、邏輯結(jié)構(gòu)D、物理和存儲結(jié)構(gòu)5、下面的敘述中,不屬于算法特性的是【D】、A、有窮性B、輸入性C、可行性D、可讀性6、算法分析的目的是【C】、A、找出數(shù)據(jù)結(jié)構(gòu)的合理性B、研究算法中的輸入和輸出的關(guān)系C、分析算法的效率以求改進(jìn)D、分析算法的易懂性和文檔性7、數(shù)據(jù)結(jié)構(gòu)是一門研究計算機(jī)中【B】對象及其關(guān)系的科學(xué)、A、數(shù)值運算B、非數(shù)值運算C、集合D、非集合8、算法的時間復(fù)雜度和【C】有關(guān)、A、所使用的計算機(jī)B、和計算機(jī)的操作系統(tǒng)C、和算法本身D、和數(shù)據(jù)結(jié)構(gòu)9、設(shè)有一個長度為n的順序表,要在第i個元素之前【也就是插入元素作為新表的第i個元素】,則移動元素個數(shù)為【A】、A、n-i+1B、n-iC、n-i-1D、i10、設(shè)有一個長度為n的順序表,要刪除第i個元素移動元素的個數(shù)為【B】、A、n-i+1B、n-iC、n-i-1D、i11、在一個單鏈表中,p、q分別指向表中兩個相鄰的結(jié)點,且q所指結(jié)點是p所指結(jié)點的直接后繼,現(xiàn)要刪除q所指結(jié)點,可用語句【C】、A、p=q->nextB、p->next=qC、p->next=qnextD、q->next=NULL12、在一個單鏈表中p所指結(jié)點之后插入一個s所指的結(jié)點時,可執(zhí)行【D】、A、p->next=s;snext=pnextB、p->next=snext;C、p=s->nextD、s->next=p->next;p->next=s;13、非空的單向循環(huán)鏈表的尾結(jié)點滿足【C】【設(shè)頭指針為head,指針p指向尾結(jié)點】、A、、P->next==NULLB、P==NULLC、P->next==headD、P==head14、鏈表不具有的特點是【A】、A、可隨機(jī)訪問任一元素B、插入刪除不需要移動元素C、不必事先估計存儲空間D、所需空間和線性表長度成正比15、帶頭結(jié)點的鏈表為空的判斷條件是【B】【設(shè)頭指針為head】、A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL16、在一個單鏈表中,p、q分別指向表中兩個相鄰的結(jié)點,且q所指結(jié)點是p所指結(jié)點的直接后繼,現(xiàn)要刪除q所指結(jié)點,可用語句【C】、A、p=q->nextB、p->next=qC、p->next=q->nextD、q->next=NULL17、在一個鏈隊中,假設(shè)f和r分別為隊頭和隊尾指針,則刪除一個結(jié)點的運算為【C】、A、r=f->next;B、r=r->next;C、f=f->next;D、f=r->next;18、在一個鏈隊中,假設(shè)f和r分別為隊頭和隊尾指針,則插入s所指結(jié)點的運算為【B】、A、f->next=s;f=s;B、r->next=s;r=s;C、s->next=r;r=s;D、s->next=f;f=s;19、一個順序表第一個元素的存儲地址是90,每個元素的長度為2,則第6個元素的地址是【B】、A、98B、100C、102D、10620、有關(guān)線性表的正確說法是【D】、A、每個元素都有一個直接前驅(qū)和一個直接后繼B、線性表至少要求一個元素C、表中的元素必須按由小到大或由大到下排序D、除了一個和最后一個元素外,其它元素都有一個且僅有一個直接前驅(qū)和一個直接后繼二、填空題1、在一個長度為n的順序存儲結(jié)構(gòu)的線性表中,向第i(1in+1)個元素之前插入新元素時,需向后移動n-i+1個數(shù)據(jù)元素、2、從長度為n的采納順序存儲結(jié)構(gòu)的線性表中刪除第i(1in+1)個元素,需向前移動n-i個元素、3、數(shù)據(jù)結(jié)構(gòu)按結(jié)點間的關(guān)系,可分為4種邏輯結(jié)構(gòu):集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)、4、數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示稱為物理結(jié)構(gòu)或存儲結(jié)構(gòu)、5、除了第1個和最后一個結(jié)點外,其它結(jié)點有且只有一個前驅(qū)結(jié)點和后繼結(jié)點的數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu),每個結(jié)點可有任意多個前驅(qū)和后繼結(jié)點數(shù)的結(jié)構(gòu)為非線性結(jié)構(gòu)、6、算法的5個重要特性是有窮性、確定性、可形性、有零個或多個輸入、有零個或多個輸出、7、數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為__圖狀結(jié)構(gòu)__結(jié)構(gòu)、8、數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為_樹形結(jié)構(gòu)__結(jié)構(gòu)、9、數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為_線性結(jié)構(gòu)_結(jié)構(gòu)、10、要求在n個數(shù)據(jù)元素中找其中值最大的元素,設(shè)基本操作為元素間的比較、則比較的次數(shù)和算法的時間復(fù)雜度分別為___n-1__和__O(n)___、11、在一個單鏈表中p所指結(jié)點之后插入一個s所指結(jié)點時,應(yīng)執(zhí)行__s->next=p->next___和p->next=s;的操作、12、設(shè)有一個頭指針為head的單向循環(huán)鏈表,p指向鏈表中的結(jié)點,若p->next==__head__,則p所指結(jié)點為尾結(jié)點、13、在一個單向鏈表中,要刪除p所指結(jié)點,已知q指向p所指結(jié)點的前驅(qū)結(jié)點、則能夠用操作_q->next=p->next__、14、設(shè)有一個頭指針為head的單向鏈表,p指向表中某一個結(jié)點,且有p->next==NULL,經(jīng)過操作__p->next=head__,就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表、15、每個結(jié)點只包含一個指針域的線性表叫單鏈表、16、線性表具有順序存儲和鏈?zhǔn)酱鎯煞N存儲結(jié)構(gòu)、17、數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù),它和數(shù)據(jù)的關(guān)系存儲結(jié)構(gòu)無關(guān),是獨立于計算機(jī)的、18、在雙向循環(huán)鏈表的每個結(jié)點中包含兩個指針域,其中next指向它的直接后繼,prior指向它的直接前驅(qū),而頭結(jié)點的prior指向尾結(jié)點,尾結(jié)點的next指向頭結(jié)點、19、單向循環(huán)鏈表是單向鏈表的一種擴(kuò)充,當(dāng)單向鏈表帶有頭結(jié)點時,把單向鏈表中尾結(jié)點的指針域由空指針改為頭結(jié)點的指針;當(dāng)單向鏈表不帶頭結(jié)點時,則把單向鏈表中尾結(jié)點的指針域由空指針改為指向指向第一個結(jié)點的指針、20、線性鏈表的邏輯關(guān)系時經(jīng)過每個結(jié)點指針域中的指針來表示的、其邏輯順序和物理存儲順序不再一致,而是一種鏈?zhǔn)酱鎯Y(jié)構(gòu),又稱為鏈表、三、問答題1、簡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的區(qū)別和聯(lián)系,它們怎樣影響算法的設(shè)計和實現(xiàn)?答:若用結(jié)點表示某個數(shù)據(jù)元素,則結(jié)點和結(jié)點之間的邏輯關(guān)系就稱為數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)在計算機(jī)中的存儲表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)、可見,數(shù)據(jù)的邏輯結(jié)構(gòu)是反映數(shù)據(jù)之間的固有關(guān)系,而數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)在計算機(jī)中的存儲表示、盡管因采納的存儲結(jié)構(gòu)不同,邏輯上相鄰的結(jié)點,其物理地址未必相同,但可經(jīng)過結(jié)點的內(nèi)部信息,找到其相鄰的結(jié)點,從而保留了邏輯結(jié)構(gòu)的特點、采納的存儲結(jié)構(gòu)不同,對數(shù)據(jù)的操作在靈活性,算法復(fù)雜度等方面差別較大、2、解釋順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點,并比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點、答:順序結(jié)構(gòu)存儲時,相鄰數(shù)據(jù)元素的存放地址也相鄰,即邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是統(tǒng)一的,,要求內(nèi)存中存儲單元的地址必須是連續(xù)的、優(yōu)點:一般情況下,存儲密度大,存儲空間利用率高、缺點:【1】在做插入和刪除操作時,需移動大量元素;【2】由于難以估計,必須預(yù)先分配較大的空間,往往使存儲空間不能得到充分利用;【3】表的容量難以擴(kuò)充、鏈?zhǔn)浇Y(jié)構(gòu)存儲時,相鄰數(shù)據(jù)元素可隨意存放,所占空間分為兩部分,一部分存放結(jié)點值,另一部分存放表示結(jié)點間關(guān)系的指針、優(yōu)點:插入和刪除元素時很方便,使用靈活、缺點:存儲密度小,存儲空間利用率低、3、什么情況下用順序表比鏈表好?答:順序表適于做查找這樣的靜態(tài)操作,鏈表適于做插入和刪除這樣的動態(tài)操作、假如線性表的變化長度變化不大,且其主要操作是查找,則采納順序表;假如線性表的長度變化較大,且其主要操作是插入、刪除操作,則采納鏈表、4、頭指針、頭結(jié)點、第一個結(jié)點【或稱首元結(jié)點】的區(qū)別是什么?頭結(jié)點是在鏈表的開始結(jié)點之前附加的一個結(jié)點;第一個結(jié)點【或稱首元結(jié)點】是鏈表中存儲第一個數(shù)據(jù)元素的結(jié)點;頭指針是指向鏈表中第一個結(jié)點【或為頭結(jié)點或為首元結(jié)點】的指針、5、解釋帶頭結(jié)點的單鏈表和不帶頭結(jié)點的單鏈表的區(qū)別、答:帶頭結(jié)點的單鏈表和不帶頭結(jié)點的單鏈表的區(qū)別主要體現(xiàn)在其結(jié)構(gòu)上和算法操作上、在結(jié)構(gòu)上,帶頭結(jié)點的單鏈表,不論鏈表是否為空,均含有一個頭結(jié)點,不帶頭結(jié)點的單鏈表不含頭結(jié)點、在操作上,帶頭結(jié)點的單鏈表的初始化為申請一個頭結(jié)點、無論插入或刪除的位置是地第一個結(jié)點還是其它結(jié)點,算法步驟都相同、不帶頭結(jié)點的單鏈表,其算法步驟要分別考慮插入或刪除的位置是第一個結(jié)點還是其它結(jié)點、因為兩種情況的算法步驟不同、四、程序填空題1、下面是用尾插法建立帶頭結(jié)點的且有n個結(jié)點的單向鏈表的算法,請在空格內(nèi)填上適當(dāng)?shù)恼Z句、NODE*create1(n)/*對線性表(1,2,、、、、、,n),建立帶頭結(jié)點的單向鏈表*/{NODE*head,*p,*q;inti;p=(NODE*)malloc(sizeof(NODE));head=p;q=p;p->next=NULL;for(i=1;i<=n;i++){p=(NODE*)malloc(sizeof(NODE));【1】p->data=i; 【2】p->next=NULL; 【3】q->next=p; 【4】q=p;}return(head);}2、下面是用頭插法建立帶頭結(jié)點的且有n個結(jié)點的單向鏈表的算法,請在空格內(nèi)填上適當(dāng)?shù)恼Z句、NODE*create2(n)/*對線性表(n,n-1,、、、、、,1),建立帶頭結(jié)點的線性鏈表*/{NODE*head,*p,*q;inti;p=(NODE*)malloc(sizeof(NODE));【1】head=p;p->next=NULL;【2】q=p;for(i=1;i<=n;i++){p=(NODE*)malloc(sizeof(NODE));p->data=i; if(i==1) 【3】p->next=NULL; else【4】p->next=q->next;【5】q->next=p;}return(head);}3、下面是在具有頭結(jié)點單向列表中刪除第i個結(jié)點,請在空格內(nèi)填上適當(dāng)?shù)恼Z句、intdelete(NODE*head,inti){NODE*p,*q;intj;q=head;j=0;while((q!=NULL)&&(j<i-1))/*找到要刪除結(jié)點的直接前驅(qū),并使q指向它*/{q=q->next;j++;}if(q==NULL)return(0);【1】p=q->next;【2】q->next=p->next;free(p);return(1);}五、完成:實驗1――線性表依據(jù)實驗要求【見教材P201-202】認(rèn)真完成本實驗,并提交實驗報告、數(shù)據(jù)結(jié)構(gòu)【本】課程作業(yè)2【本部分作業(yè)覆蓋教材第3-5章的內(nèi)容】一、單項選擇題1、若讓元素1,2,3依次進(jìn)棧,則出棧順序不可能為【C】、A、3,2,1B、2,1,3C、3,1,2D、1,3,22、一個隊列的入隊序列是1,2,3,4、則隊列的輸出序列是【B】、A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,4,13、向順序棧中壓入新元素時,應(yīng)當(dāng)【A】、A、先移動棧頂指針,再存入元素B、先存入元素,再移動棧頂指針C、先后次序無關(guān)緊要D、同時進(jìn)行4、在一個棧頂指針為top的鏈棧中,將一個p指針?biāo)傅慕Y(jié)點入棧,應(yīng)執(zhí)行【C】、A、top->next=p;B、p->next=top->next;top->next=p;C、p->next=top;top=p;D、p->next=top->next;top=top->next;5、在一個棧頂指針為top的鏈棧中刪除一個結(jié)點時,用x保存被刪結(jié)點的值,則執(zhí)行【B】、A、x=top;top=top->next;B、x=top->data;C、top=top->next;x=top->data;D、x=top->data;top=top->next;6、一般情況下,將遞歸算法轉(zhuǎn)換成等價的非遞歸算法應(yīng)該設(shè)置【A】、A、棧B、隊列C、堆棧或隊列D、數(shù)組7、表示式a*(b+c)-d的后綴表示式是【B】、A、abcd*+-B、abc+*d-C、abc*++d-D、-+*abcd8、判斷一個順序隊列sq【最多元素為m0】為空的條件是【C】、A、sq->rear-sq->front==m0B、sq->rear-sq->front-1==m0C、sq->front==sq->rearD、sq->front==sq->rear+19、判斷一個循環(huán)隊列Q【最多元素為m0】為空的條件是【A】、A、Q->front==Q->rearB、Q->front!=Q->rearC、Q->front==(Q->rear+1)%m0D、Q->front!=(Q->rear+1)%m010、判斷棧S滿【元素個數(shù)最多n個】的條件是【C】、A、s->top==0B、s->top!=0C、s->top==n-1D、s->top!=n-111、一個隊列的入隊順序是a,b,c,d,則離隊的順序是【B】、A、a,d,cbB、a,b,c,dC、d,c,b,aD、c,b,d,a12、假如以鏈表作為棧的存儲結(jié)構(gòu),則退棧操作時【C】、A、必須判斷棧是否滿B、判斷棧元素類型C、必須判斷棧是否空D、對棧不作任何判斷13、在解決計算機(jī)主機(jī)和打印機(jī)之間速度不匹配問題時一般設(shè)置一個打印數(shù)據(jù)緩沖區(qū),主機(jī)將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中,而打印機(jī)則從緩沖區(qū)中取出數(shù)據(jù)打印,該緩沖區(qū)應(yīng)該是一個【B】結(jié)構(gòu)、A、堆棧B、隊列C、數(shù)組D、先性表14、一個遞歸算法必須包含【B】、A、遞歸部分 B、終止條件和遞歸部分 C、迭代部分 D、終止條件和迭代部分15、從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時,用變量x保存被刪結(jié)點的值,則執(zhí)行【A】、A、x=top->data;top=top->next;B、x=top->data;C、top=top->next;x=top->data;D、top=top->next;x=data;16、在一個鏈隊中,假設(shè)f和r分別為隊頭和隊尾指針,則刪除一個結(jié)點的運算為【C】、A、r=f->next;B、r=r->next;C、f=f->next;D、f=r->next;17、在一個鏈隊中,假設(shè)f和r分別為隊頭和隊尾指針,則插入s所指結(jié)點的運算為【B】、A、f->next=s;f=s;B、r->next=s;r=s;C、s->next=r;r=s;D、s->next=f;f=s;18、以下陳述中正確的是【A】、A、串是一種特殊的線性表B、串的長度必須大于零C、串中元素只能是字母D、空串就是空白串19、設(shè)有兩個串p和q,其中q是p的子串,q在p中首次出現(xiàn)的位置的算法稱為【C】、A、求子串B、連接C、匹配D、求串長20、串是【D】、A、不少于一個字母的序列B、任意個字母的序列C、不少于一個字符的序列D、有限個字符的序列21、串的長度是指【B】、A、串中所含不同字母的個數(shù)B、串中所含字符的個數(shù)C、串中所含不同字符的個數(shù)D、串中所含非空格字符的個數(shù)22、若串S==“English”,其子串的個數(shù)是【D】、A、9B、16C、36D、2823、串和普通的線性表相比較,它的特殊性體現(xiàn)在【C】、A、順序的存儲結(jié)構(gòu)B、鏈接的存儲結(jié)構(gòu)C、數(shù)據(jù)元素是一個字符D、數(shù)據(jù)元素能夠任意24、空串和空格串【B】、A、相同B、不相同C、可能相同D、無法確定25、兩個字符串相等的條件是【D】、A、兩串的長度相等B、兩串包含的字符相同C、兩串的長度相等,而且兩串包含的字符相同D、兩串的長度相等,而且對應(yīng)位置上的字符相同26、在實際應(yīng)用中,要輸入多個字符串,且長度無法預(yù)定、則應(yīng)該采納【A】存儲比較合適【】、A、鏈?zhǔn)紹、順序C、堆結(jié)構(gòu)D、無法確定27、一維數(shù)組A采納順序存儲結(jié)構(gòu),每個元素占用6個字節(jié),第6個元素的存儲地址為100,則該數(shù)組的首地址是【C】、A、64B、28C、70D、9028、稀疏矩陣采納壓縮存儲的目的主要是【D】、A、表示變得簡單B、對矩陣元素的存取變得簡單C、去掉矩陣中的多余元素D、減少不必要的存儲空間的開銷29、一個非空廣義表的表頭【C】、A、不可能是原子B、只能是子表C、只能是原子D、能夠是子表或原子30、常對數(shù)組進(jìn)行的兩種基本操作是【C】、A、建立和刪除B、索引和、和修改C、查找和修改D、查找和索引31、設(shè)二維數(shù)組A[5][6]按行優(yōu)先順序存儲在內(nèi)存中,已知A[0][0]起始地址為1000,每個數(shù)組元素占用5個存儲單元,則元素A[4][4]的地址為【A】、A、1140B、1145C、1120D、112532、設(shè)有一個20階的對稱矩陣A,采納壓縮存儲的方法,將其下三角部分以行序為主序存儲到一維數(shù)組B中【數(shù)組下標(biāo)從1開始】,則矩陣中元素a9,2在一維數(shù)組B中的下標(biāo)是【D】、A、41B、32C、18D、38二、填空題1、棧是限定在表的一端進(jìn)行插入和刪除操作的線性表,又稱為后進(jìn)先出、2、循環(huán)隊列隊頭指針在隊尾指針下一個位置,隊列是”滿”狀態(tài)3、在隊列的順序存儲結(jié)構(gòu)中,當(dāng)插入一個新的隊列元素時,尾指針增1,當(dāng)刪除一個元素隊列時,頭指針增1、4、循環(huán)隊列的引入,目的是為了克服假上溢、5、向順序棧插入新元素分為三步:第一步進(jìn)行棧是否滿判斷,判斷條件是s->top=MAXSIZE-1;第二步是修改棧頂指針;第三步是把新元素賦給棧頂對應(yīng)的數(shù)組元素、一樣從順序棧刪除元素分為三步:第一步進(jìn)行棧是否空判斷,判斷條件是s->top=-1、第二步是把棧頂元素;第三步修改棧頂指針、6、假設(shè)以S和X分別表示入棧和出棧操作,則對輸入序列a,b,c,d,e一系列棧操作SSXSXSSXXX之后,得到的輸出序列為bceda、7、一個遞歸算法必須包含終止條件和遞歸部分、8、判斷一個循環(huán)隊列LU【最多元素為m0】為空的條件是LU->front==LU->rear、9、在將中綴表示式轉(zhuǎn)換成后綴表示式和計算后綴表示式的算法中,都需要使用棧,對于前者,進(jìn)入棧中的元素為表示式中的運算符,而對于后者,進(jìn)入棧的元素為操作數(shù),中綴表示式(a+b)/c-(f-d/c)所對應(yīng)的后綴表示式是ab+c/fde/--、10、向一個棧頂指針為h的鏈棧中插入一個s所指結(jié)點時,可執(zhí)行___s->next=h_____和h=s;操作、(結(jié)點的指針域為next)11、從一個棧頂指針為h的鏈棧中刪除一個結(jié)點時,用x保存被刪結(jié)點的值,可執(zhí)行x=h->data;和__h=h->next______、(結(jié)點的指針域為next)12、在一個鏈隊中,設(shè)f和r分別為隊頭和隊尾指針,則插入s所指結(jié)點的操作為___r->next=s_____和r=s;(結(jié)點的指針域為next)13、在一個鏈隊中,設(shè)f和r分別為隊頭和隊尾指針,則刪除一個結(jié)點的操作為__f=f->next______、(結(jié)點的指針域為next)14、串是一種特殊的線性表,其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是字符、15、串的兩種最基本的存儲方法是順序存儲方法和鏈?zhǔn)酱鎯Ψ椒ā?6、空串的長度是0;空格串的長度是空格字符的個數(shù)、17、需要壓縮存儲的矩陣可分為特殊矩陣和稀疏矩陣兩種、18、設(shè)廣義表L=【【】,【】】,則表頭是【】,表尾是【【】】,L的長度是2、19、廣義表A【【a,b,c】,(d,e,f)】的表尾為【【d,e,f】】、20、兩個串相等的充分必要條件是_______串長度相等且對應(yīng)位置的字符相等___、21、設(shè)有n階對稱矩陣A,用數(shù)組s進(jìn)行壓縮存儲,當(dāng)ij時,A的數(shù)組元素aij相應(yīng)于數(shù)組s的數(shù)組元素的下標(biāo)為__i(i-1)/2+j_____、【數(shù)組元素的下標(biāo)從1開始】22、對稀疏矩陣進(jìn)行壓縮存儲,矩陣中每個非零元素對應(yīng)的三元組包含該元素的___行下標(biāo)____、___列下標(biāo)___和___非零元素值____三項信息、三、問答題1、簡述棧和一般線性表的區(qū)別、答:棧是一種先進(jìn)后出的線性表,棧的插入和刪除操作都只能在棧頂進(jìn)行,而一般的線性表能夠在線性表的任何位置進(jìn)行插入和刪除操作、2、簡述隊列和一般線性表的區(qū)別、隊列是一種先進(jìn)先出的線性表,隊列的插入只能在隊尾進(jìn)行,隊列的刪除只能在隊頭進(jìn)行,而一般的線性表能夠在線性表的任何位置進(jìn)行插入和刪除操作、3、鏈棧中為何不設(shè)頭結(jié)點?答:因為鏈棧只在鏈頭插入和刪除結(jié)點,不可能在鏈表中間插入和刪除結(jié)點,算法實現(xiàn)很簡單,因此一般不設(shè)置頭結(jié)點、4、利用一個棧,則:【1】假如輸入序列由A,B,C組成,試給出全部可能的輸出序列和不可能的輸出序列、【2】假如輸入序列由A,B,C,D組成,試給出全部可能的輸出序列和不可能的輸出序列、答:【1】棧的操作特點是后進(jìn)先出,因此輸出序列有:A入,A出,B入,B出,C入C出,輸出序列為ABC、A入,A出,B入,C入,C出,B出,輸出序列為ACB、A入,B入,B出,A出,C入,C出,輸出序列為BAC、A入,B入,B出,C入,C出,A出,輸出序列為BCA、A入,B入,C入,C出,B出,A出,輸出序列為CBA、由A,B,C組成的數(shù)據(jù)項,除上述五個不同的組合外,還有一個C,A,B組合、但不可能先把C出棧,再把A出棧,【A不在棧頂位置】,最后把B出棧,因此序列CAB不可能由輸入序列A,B,C經(jīng)過棧得到、【2】按照上述方法,可能的輸出序列有:ABCD,ABDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA、不可能的輸出序列有:DABC,ADBC,DACB,DBAC,BDAC,DBCA,DCAB,CDAB,CADB,CABD5、用S表示入棧操作,X表示出棧操作,若元素入棧順序為1234,為了得到1342出棧順序,相應(yīng)的S和X操作串是什么?答:應(yīng)是SXSSXSXX、各操作結(jié)果如下:S1入棧X1出棧輸出序列:1S2入棧S3入棧X3出棧輸出序列:13S4入棧X4出棧輸出序列:134X2出棧輸出序列:13426、有5個元素,其入棧次序為:A、B、C、D、E,在各種可能的出棧次序中,以元素C、D最先的次序有哪幾個?答:從題中可知,要使C第一個且D第二個出棧,應(yīng)是A入棧,B入棧,C入棧,C出棧,D入棧、之后能夠有以下幾種情況:【1】B出棧,A出棧,E入棧,E出棧,輸出序列為:CDBAE、【2】B出棧,E入棧,E出棧,A出棧,輸出序列為CDBEA、【3】E入棧,E出棧,B出棧,A出棧,輸出序列為CDEBA因此可能的次序有:CDBAE,CDBEA,CDEBA7、寫出以下運算式的后綴算術(shù)運算式⑴3x2+x-1/x+5⑵(A+B)*C-D/(E+F)+G答;對應(yīng)的后綴算術(shù)運算式⑴3x2^*x+1x/-5+⑵AB+C*DEF+/-G+8、簡述廣義表和線性表的區(qū)別和聯(lián)系、答:廣義表是線性表的的推廣,它也是n(n>0)個元素a1,a2…ai…an的有限序列,其中ai或是原子或是一個廣義表、因此,廣義表是一種遞歸數(shù)據(jù)結(jié)構(gòu),而線性表沒有這種特性,線性表能夠看成廣義表的特殊情況,當(dāng)ai都是原子時,廣義表退化成線性表、四、程序填空題1、在下面空格處填寫適當(dāng)?shù)恼Z句,以使下面的鏈?zhǔn)疥犃腥〕鲈氐乃惴ㄍ暾?、intwrite(LinkQueue*q){QueueNode*p;if(q->front==q->rear)/*隊空*/{printf(“underflow”);exit(0);}while(q->front->next!=NULL){p=q->front->next;(1)q->front->next=p->next;printf(“%4d”,p->data);(2)free(p);}【3】q->rear=q->front;/*隊空時,頭尾指針指向頭結(jié)點*/}五、綜合題1、設(shè)棧S和隊列Q的初始狀態(tài)為空,元素e1,e2,e3,e4,e5和e6依次經(jīng)過S,一個元素出棧后即進(jìn)隊列Q,若6個元素出隊的序列是e2,e4,e3,e6,e5,e1,則棧S的容量至少應(yīng)該是多少?答:出隊序列是e2,e4,e3,e6,e5,e1的過程:⑴e1入?！緱５椎綏ｍ斣厥莈1】⑵e2入?！緱５椎綏ｍ斣厥莈1,e2】⑶e2出?！緱５椎綏ｍ斣厥莈1】⑷e3入棧【棧底到棧頂元素是e1,e3】⑸e4入?！緱５椎綏ｍ斣厥莈1,e3,e4】⑹e4出?！緱５椎綏ｍ斣厥莈1,e3】⑺e3出?！緱５椎綏ｍ斣厥莈1】⑻e5入棧【棧底到棧頂元素是e1,e5】⑼e6入棧【棧底到棧頂元素是e1,e5,e6】⑽e6出?！緱５椎綏ｍ斣厥莈1,e5】⑾e5出?！緱５椎綏ｍ斣厥莈1】⑿e1出棧【棧底到棧頂元素是空】棧中最多時有3個元素,因此棧S的容量至少是3、2、假設(shè)用循環(huán)單鏈表實現(xiàn)循環(huán)隊列,該隊列只使用一個尾指針rear,其相應(yīng)的存儲結(jié)構(gòu)和基本算法如下;【1】初始化隊列initqueue(Q):建立一個新的空隊列Q、【2】入隊列enqueue(Q,x):將元素x插入到隊列Q中、【3】出隊列delqueue(Q):從隊列Q中退出一個元素、【4】取隊首元素gethead(Q):返回當(dāng)前隊首元素、【5】判斷隊列是否為空:emptyqueue(Q)、【6】顯示隊列中元素:dispqueue(Q)、算法設(shè)計如下:/*只有一個指針rear的鏈?zhǔn)疥牭幕静僮?/#include<stdio、h>typedefcharelemtype;structnode/*定義鏈隊列結(jié)點*/ { elemtypedata; structnode*next;};typedefstructqueue/*定義鏈隊列數(shù)據(jù)類型*/{ structnode*rear;}LinkQueue;voidinitqueue(LinkQueue*Q)/*初始化隊列*/{Q=(structqueue*)malloc(sizeof(structqueue));Q->rear=NULL;}voidenqueue(LinkQueue*Q,elemtypex)/*入隊算法*/{structnode*s,*p;s=(structnode*)malloc(sizeof(structnode));s->data=x;if(Q->rear==NULL)/*原為空隊時*/{ Q->rear=s; s->next=s;}else/*原隊不為空時*/{ p=Q->rear->next;/*p指向第一個結(jié)點*/ Q->rear->next=s;/*將s鏈接到隊尾*/ Q->rear=s;/*Q->rear指向隊尾*/ s->next=p;}}voiddelqueue(LinkQueue*Q)/*出隊算法*/{structnode*t;if(Q->rear==NULL){ printf("隊列為空!\n"); return(0);}elseif(Q->rear->next==Q->rear)/*只有一個結(jié)點時*/{ t=Q->rear; Q->rear=NULL;}else/*有多個結(jié)點時*/{ t=Q->rear->next;/*t指向第一個結(jié)點*/ Q->rear->next=t->next;/*引成循環(huán)鏈*/}free(t);}elemtypegethead(LinkQueue*Q)/*取隊首元素算法*/{if(Q->rear==NULL) printf("隊列為空!\n");else return(Q->rear->next->data);}intemptyqueue(LinkQueue*Q)/*判斷隊列是否為空算法*/{if(Q->rear==NULL)return(1);/*為空,則返回true*/elsereturn(0);/*不為空,則返回flase*/}voiddispqueue(LinkQueue*Q)/*顯示隊列中元素算法*/{structnode*p=Q->rear->next;printf("隊列元素:");while(p!=Q->rear){ printf("%c",p->data); p=p->next;}printf("%c\n",p->data);}六、完成:實驗2――棧、隊列、遞歸程序設(shè)計依據(jù)實驗要求【見教材P203】認(rèn)真完成本實驗,并提交實驗報告、數(shù)據(jù)結(jié)構(gòu)【本】課程作業(yè)作業(yè)3【本部分作業(yè)覆蓋教材第6-7章的內(nèi)容】一、單項選擇題1、假定一棵二叉樹中,雙分支結(jié)點數(shù)為15,單分支結(jié)點數(shù)為30,則葉子結(jié)點數(shù)為【B】、A、15B、16C、17D、472、二叉樹第k層上最多有【B】個結(jié)點、A、2kB、2k-1C、2k-1D、2k-13、二叉樹的深度為k,則二叉樹最多有【D】個結(jié)點、A、2kB、2k-1C、2k-1D、2k-14、設(shè)某一二叉樹先序遍歷為abdec,中序遍歷為dbeac,則該二叉樹后序遍歷的順序是【C】、A、abdecB、debacC、debcaD、abedc5、將含有150個結(jié)點的完全二叉樹從根這一層開始,每一層從左到右依次對結(jié)點進(jìn)行編號,根結(jié)點的編號為1,則編號為69的結(jié)點的雙親結(jié)點的編號為【B】、A、33B、34C、35D、366、假如將給定的一組數(shù)據(jù)作為葉子數(shù)值,所構(gòu)造出的二叉樹的帶權(quán)路徑長度最小,則該樹稱為【A】、A、哈夫曼樹B、平衡二叉樹C、二叉樹D、完全二叉樹7、下面有關(guān)二叉樹的說法正確的是【A】、A、二叉樹中度為0的結(jié)點的個數(shù)等于度為2的結(jié)點的個數(shù)加1B、二叉樹中結(jié)點個數(shù)必大于0C、完全二叉樹中,任何一個結(jié)點的度,或為0或為2D、二叉樹的度是28、在一棵度為3的樹中,度為3的結(jié)點個數(shù)為2,度為2的結(jié)點個數(shù)為1,則度為0的結(jié)點個數(shù)為【C】、A、4B、5C、6D、79、在一棵度具有5層的滿二叉樹中結(jié)點總數(shù)為【A】、A、31B、32C、33D、1610、利用n個值作為葉結(jié)點的權(quán)生成的哈夫曼樹中共包含有(D)個結(jié)點、A、nB、n+1C、2*nD、2*n-111、利用3、6、8、12這四個值作為葉子結(jié)點的權(quán),生成一棵哈夫曼樹,該樹中全部葉子的最長帶權(quán)路徑長度為(A)、A、18B、16C、12D、3012、在一棵樹中,【C】沒有前驅(qū)結(jié)點、A、分支結(jié)點B、葉結(jié)點C、樹根結(jié)點D、空結(jié)點13、在一棵二叉樹中,若編號為i的結(jié)點存在右小朋友,則右小朋友的順序編號為【C】、A、2iB、2i-1D、2i+1C、2i+214、設(shè)一棵哈夫曼樹共有n個葉結(jié)點,則該樹有【B】個非葉結(jié)點、A、nB、n-1C、n+1D、2n15、設(shè)一棵有n個葉結(jié)點的二叉樹,除葉結(jié)點外每個結(jié)點度數(shù)都為2,則該樹共有【B】個結(jié)點、A、2nB、2n-1C、2n+1D、2n+216、在一個圖G中,全部頂點的度數(shù)之和等于全部邊數(shù)之和的【C】倍、A、1/2B、1C、2D、417、在一個有像圖中,全部頂點的入度之和等于全部頂點的出度之和的【B】倍、A、鄰接矩陣表示法B、鄰接表表示法C、逆鄰接表表示法D、鄰接表和逆鄰接表18、在圖的存儲結(jié)構(gòu)表示中,表示形式唯一的是【C】、A、nB、n1C、n1D、n/219、一個具有n個頂點的無向完全圖包含【A】條邊、A、n【n1】B、n【n1】C、n【n1】/2D、n【n1】/220、對于具有n個頂點的圖,若采納鄰接矩陣表示,則該矩陣的大小為【B】、A、nB、n2C、n1D、【n1】221、對于一個具有n個頂點和e條邊的無向圖,若采納鄰接表表示,則全部頂點鄰接表中的結(jié)點總數(shù)為【D】、A、nB、eC、2nD、2e22、在有向圖的鄰接表中,每個頂點鄰接表鏈接著該頂點全部【B】鄰接點、A、入邊B、出邊C、入邊和出邊D、不是入邊也不是出邊23、鄰接表是圖的一種【B】、A、順序存儲結(jié)構(gòu)B、鏈?zhǔn)酱鎯Y(jié)構(gòu)C、索引存儲結(jié)構(gòu)D、散列存儲結(jié)構(gòu)24、假如從無向圖的任一頂點出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問全部頂點,則該圖一定是【B】、A、完全圖B、連通圖C、有回路D、一棵樹25、下面有關(guān)圖遍歷的說法錯誤的是【C】、A、連通圖的深度優(yōu)先搜索是一個遞歸過程B、圖的廣度優(yōu)先搜索中鄰接點的尋找具有”先進(jìn)先出”的特點C、非連通圖不能用深度優(yōu)先搜索法D、圖的遍歷要求每一頂點僅被訪問一次26、無向圖的鄰接矩陣是一個【A】、 A、對稱矩陣B、零矩陣C、上三角矩陣D、對角矩陣27、圖的深度優(yōu)先遍歷算法類似于二叉樹的【A】遍歷、A、先序B、中序C、后序D、層次28、已知下圖所示的一個圖,若從頂點V1出發(fā),按深度優(yōu)先搜索法進(jìn)行遍歷,則可能得到的一種頂點序列為【C】、A、V1V2V4V8V3V5V6V7B、V1V2V4V5V8V3V6V7C、V1V2V4V8V5V3V6V7D、V1V3V6V7V2V4V5V8二、填空題1、結(jié)點的度是指結(jié)點所擁有的子樹樹木或后繼結(jié)點數(shù)、2、樹的度是指樹中全部結(jié)點的度的最大值、3、度大于0的結(jié)點稱作分支結(jié)點或非終端結(jié)點、4、度等于0的結(jié)點稱作葉子結(jié)點或終端結(jié)點、5、在一棵樹中,每個結(jié)點的子樹的根或說每個結(jié)點的后繼結(jié)點稱為該結(jié)點的小朋友結(jié)點,簡稱為小朋友、6、從根結(jié)點到該結(jié)點所經(jīng)分支上的全部結(jié)點稱為該結(jié)點的祖先、7、樹的深度或高度是指樹中結(jié)點的最大層數(shù)、8、具有n個結(jié)點的完全二叉樹的深度是、9、先序遍歷二叉樹的的操作定義為;若二叉樹為空,則為空操作,否則進(jìn)行如下操作,訪問二叉樹的根結(jié)點;先序遍歷二叉樹的左子樹,先序遍歷二叉樹的右子樹、10、中序遍歷二叉樹的的操作定義為;若二叉樹為空,則為空操作,否則進(jìn)行如下操作,中序遍歷二叉樹的左子樹;訪問而叉樹的根結(jié)點,中序遍歷二叉樹的右子樹、11、后序遍歷二叉樹的的操作定義為;若二叉樹為空,則為空操作,否則進(jìn)行如下操作,后序遍歷二叉樹的左子樹;后序遍歷二叉樹的右子樹,訪問而叉樹的根結(jié)點、12、將樹中結(jié)點賦上一個有著某種意義的實數(shù),稱此實數(shù)為該結(jié)點的權(quán)、13、樹的帶權(quán)路徑長度為樹中全部葉子結(jié)點的帶權(quán)路徑長度之和、14、哈夫曼樹又稱為最優(yōu)二叉樹,它是n個帶權(quán)葉子結(jié)點構(gòu)成的全部二叉樹中帶權(quán)路徑長度WPL最小的二叉樹、15、若以4,5,6,7,8作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹,則其帶權(quán)路徑長度是69、16、具有m個葉子結(jié)點的哈夫曼樹共有2m-1結(jié)點、17、在圖中,任何兩個數(shù)據(jù)元素之間都可能存在關(guān)系,因此圖的數(shù)據(jù)元素之間是一種多對多的關(guān)系、18、圖的遍歷是從圖的某一頂點出發(fā),按照一定的搜索方法對圖中全部頂點各做一次訪問的過程、19、圖的深度優(yōu)先搜索遍歷類似于樹的先序遍歷、20、圖的廣度優(yōu)先搜索類似于樹的按層次遍歷、21、具有n個頂點的有向圖的鄰接矩陣,其元素個數(shù)為n2、22、圖常見的兩種存儲結(jié)構(gòu)是鄰接矩陣和鄰接表、23、在有n個頂點的有向圖中,每個頂點的度最大可達(dá)2(n-1)、24、在一個帶權(quán)圖中,兩頂點之間的最段路徑最多經(jīng)過n-1條邊、ajfghidcebajfghidceb三、綜合題1、寫出如下圖所示的二叉樹的先序、中序和后序遍歷序列、答:二叉樹的定義是遞歸的,因此,一棵二叉樹可看作由根結(jié)點,左子樹和右子樹這三個基本部分組成,即依次遍歷整個二叉樹,又左子樹或右子樹又可看作一棵二叉樹并繼續(xù)分為根結(jié)點、左子樹和右子樹三個部分…、、,這樣劃分一直進(jìn)行到樹葉結(jié)點、(1)先序為”根左右”,先序序列為:fdbacegihl(2)中序為”左根右”,中序序列為:abcdefghij(3)后序為”左右根”,后序序列為:acbedhjigf2、已知某二叉樹的先序遍歷結(jié)果是:A,B,D,G,C,E,H,L,I,K,M,F和J,它的中序遍歷結(jié)果是:G,D,B,A,L,H,E,K,I,M,C,F和J,請畫出這棵二叉樹,并寫出該二叉樹后續(xù)遍歷的結(jié)果、【1】二叉樹圖形表示如下:【2】該二叉樹后序遍歷的結(jié)果是:G、D、B、L、H、K、M、I、E、J、F、C和A、3、已知一棵完全二叉樹共有892個結(jié)點,求⑴樹的高度⑵葉子結(jié)點數(shù)⑶單支結(jié)點數(shù)⑷最后一個非終端結(jié)點的序號答⑴已知深度為k的二叉樹最多有2k-1個結(jié)點(K≥1),29-1<892<210-1,故樹的高度為10⑵對于完全二叉樹來說,度為1的結(jié)點只能是0或1因為n=n0+n1+n2和n0=n2+1得:設(shè)n1=0,892=n0+0+n2=2n2+1得n2不為整數(shù)出錯設(shè)n1=1,892=n0+1+n2=2n2+2得n2=445→n0=n2+1=446葉子結(jié)點數(shù)為446、⑶由⑵得單支結(jié)點數(shù)為1⑷對于n個結(jié)點的完全二叉樹,最后一個樹葉結(jié)點,即序號為n的葉結(jié)點其雙親結(jié)點即為最后一個非終端結(jié)點,序號為892/2=446、4、給出滿足下面條件的全部二叉樹、【1】先序和中序相同【2】中序和后序相同【3】先序和后序相同【1】先序序列和中序序列相同的二叉樹為空樹或任一結(jié)點均無左小朋友的非空二叉樹【2】中序和后序序列相同的二叉樹為空樹或任一結(jié)點均無右小朋友的非空二叉樹【3】先序和后序序列相同的二叉樹為空樹或僅有一個結(jié)點5、假設(shè)通信用的報文由9個字母A、B、C、D、E、F、G、H和I組成,它們出現(xiàn)的頻率分別是:10、20、5、15、8、2、3、7和30、請請用這9個字母出現(xiàn)的頻率作為權(quán)值求:【1】設(shè)計一棵哈夫曼樹;【2】計算其帶權(quán)路徑長度WPL;【3】寫出每個字符的哈夫曼編碼、【1】哈夫曼樹如圖B-4所示、圖B-4【2】其帶權(quán)路徑長度WPL值為270、【3】每個字符的哈夫曼編碼為:A:100,B:11,C:1010,D:000,E:0010,F:10110,G:10111,H:0011,I:016、請依據(jù)以下帶權(quán)有向圖G【1】給出從結(jié)點v1出發(fā)分別按深度優(yōu)先搜索遍歷G和廣度優(yōu)先搜索遍歷G所得的結(jié)點序列;【2】給出G的一個拓?fù)湫蛄?【3】給出從結(jié)點v1到結(jié)點v8的最短路徑、答【1】深度優(yōu)先遍歷:v1,v2,v3,v8,v5,v7,v4,v6廣度優(yōu)先遍歷:v1,v2,v4,v6,v3,v5,v7,v8(2)G的拓?fù)湫蛄袨?v1,v2,v4,v6,v5,v5,v3,v5,v7,v8(3)最短路徑為:v1,v2,v5,v7,v87、已知無向圖G描述如下:G=【V,E】V={V1,V2,V3,V4,V5}E={【V1,V2】,【V1,V4】,【V2,V4】,【V3,V4】,【V2,V5】,【V3,V4】,【V3,V5】}【1】畫出G的圖示;【2】然后給出G的鄰接矩陣和鄰接表;【3】寫出每個頂點的度、①g1的圖示和圖g1的鄰接表如下圖所示、圖G②圖G的鄰接矩陣如下圖所示:10100011101000110011110001100圖G的鄰接矩陣圖G的鄰接表③V1、V2、V3、V4、V5的度分別為:2,3,2,3,2四、程序填空題1、下面函數(shù)的功能是返回二叉樹BT中值為X的結(jié)點所在的層號,請在劃有橫線的地方填寫合適內(nèi)容、intNodeLevel(structBinTreeNode*BT,charX){if(BT==NULL)return0;/*空樹的層號為0*/elseif(BT->data==X)return1;/*根結(jié)點的層號為1*//*向子樹中查找X結(jié)點*/else{intc1=NodeLevel(BT->left,X);if(c1>=1)___(1)returnc1+1___________;intc2=______(2)NodeLevel(BT->right,X)__________;if___(3)_(c2>=1)returnc2+1_________________;//若樹中不存在X結(jié)點則返回0elsereturn0;}}2、下面函數(shù)的功能是按照圖的深度優(yōu)先搜索遍歷的方法,輸出得到該圖的生成樹中的各條邊,請在劃有橫線的地方填寫合適內(nèi)容、voiddfstree(adjmatrixGA,inti,intn){intj;visited[i]=1;(1)for(j=0;j<n;j++)if(GA[i][j]!=0&&GA[i][j]!=MaxValue&&!visited[j]){printf("(%d,%d)%d,",i,j,GA[i][j]);(2)dfstree(GA,j,n);}}五、算法設(shè)計題1、寫一個將一棵二叉樹復(fù)制給另一棵二叉樹的算法、defineNULL0typedefstructbtnode{ elemtypedata; structbtnode*lchild,*rchild;}bitnode,*bitree;bitree*CopyTree(bitnode*p){ /*復(fù)制一棵二叉樹*/ bitnode*t; if(p!=NULL) { t=(bitnode*)malloc(sizeof(bitnode)); t->data=p->data; t->lchild=CopyTree(p->lchild); t->rchild=CopyTree(p->rchild); return(t); } else return(NULL);}/*CopyTree*/2、依據(jù)下面函數(shù)聲明編制出求一棵二叉樹中葉子結(jié)點總數(shù)的算法,該總數(shù)值由函數(shù)返回、假定參數(shù)BT初始指向二叉樹的根結(jié)點、intBTreeLeafCount(structBTreeNode*BT);intBTreeLeafCount(structBTreeNode*BT){if(BT==NULL)return0;elseif(BT->left==NULL&&BT->right==NULL)return1;elsereturnBTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);}六、完成:實驗3――棧、隊列、遞歸程序設(shè)計實驗4——圖的存儲方法和應(yīng)用依據(jù)實驗要求【見教材P203】認(rèn)真完成本實驗,并提交實驗報告、數(shù)據(jù)結(jié)構(gòu)【本】課程作業(yè)【4】【本部分作業(yè)覆蓋教材第8-9章的內(nèi)容】一、單項選擇題1、順序查找方法適合于存儲結(jié)構(gòu)為【D】的線性表、A、散列存儲B、索引存儲C、散列存儲或索引存儲D、順序存儲或鏈接存儲2、對線性表進(jìn)行二分查找時,要求線性表必須【C】、A、以順序存儲方法B、以鏈接存儲方法C、以順序存儲方法,且數(shù)據(jù)元素有序D、以鏈接存儲方法,且數(shù)據(jù)元素有序3、對于一個線性表,若要求既能進(jìn)行較快地插入和刪除,又要求存儲結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系,則應(yīng)該【B】、A、以順序存儲方法B、以鏈接存儲方法C、以索引存儲方法D、以散列存儲方法4、采納順序查找方法查找長度為n的線性表時,每個元素的平均查找長度為【C】、A、nB、n/2C、(n+1)/2D、(n-1)/25、哈希函數(shù)有一個共同的性質(zhì),即函數(shù)值應(yīng)當(dāng)以【D】取其值域的每個值、A、最大概率B、最小概率C、平均概率D、同等概率6、有一個長度為10的有序表,按折半查找對該表進(jìn)行查找,在等概率情況下查找成功的平均比較次數(shù)為【A】、A、29/10B、31/10C、26/10D、29/97、已知一個有序表為{11,22,33,44,55,66,77,88,99},則順序查找元素55需要比較【C】次、A、3B、4C、5D、68、順序查找法和二分查找法對存儲結(jié)構(gòu)的要求是【D】、A、順序查找和二分查找均只是適用于順序表B、順序查找和二分查找均既適用于順序表,也適用于鏈表C、順序查找只是適用于順序表D、二分查找適用于順序表9、有數(shù)據(jù){53,30,37,12,45,24,96},從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹,若希望高度最小,應(yīng)該選擇的序列是【B】、A、45,24,53,12,37,96,30B、37,24,12,30,53,45,96C、12,24,30,37,45,53,96D、30,24,12,37,45,96,5310、對有18個元素的有序表作二分【折半】查找,則查找A[3]的比較序列的下標(biāo)可能為【D】、A、1、2、3B、9、5、2、3C、9、5、3D、9、4、2、311、對于順序存儲的有序表{5,12,20,26,37,42,46,50,64},若采納折半查找,則查找元素26的比較次數(shù)是【C】、A、3B、3C、4D、512、在全部的排序方法中,關(guān)鍵字比較的次數(shù)和記錄初始排列秩序無關(guān)的是【C】、A、冒泡排序B、希爾排序C、直接選擇排序D、直接插入排序13、從未排序序列中依次取出元素和已經(jīng)排好序的序列中的元素作比較、將其放入已排序序列的正確的位置上,此方法稱為【A】A、插入排序B、選擇排序C、交換排序D、歸并排序14、從未排序序列中挑選元素,并將其放入已排序序列的一端,此方法稱為【C】、A、插入排序B、交換排序C、選擇排序D、歸并排序15、依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為【D】、 A、插入排序B、交換排序C、選擇排序D、歸并排序16、當(dāng)兩個元素出現(xiàn)逆序的時候就交換位置,這種排序方法稱為【B】、A、插入排序B、交換排序C、選擇排序D、歸并排序17、每次把待排序的區(qū)間劃分為左、右兩個子區(qū)間,其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄的關(guān)鍵字,右區(qū)間中記錄的關(guān)鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字,這種排序稱為【B】、A、插入排序B、快速排序C、堆排序D、歸并排序18、在正常情況下,直接插入排序的時間復(fù)雜度為【D】、A、O(log2n)B、O(n)C、O(nlog2n)D、O(n2)19、在正常情況下,冒泡排序的時間復(fù)雜度為【D】、A、O(log2n)B、O(n)C、O(nlog2n)D、O(n2)20、在待排序元素基本有序的情況下,效率最高的排序方法是【A】、A、插入排序B、快速排序C、堆排序D、歸并排序21、在下面排序方法中,關(guān)鍵字比較的次數(shù)和記錄的初始排列秩序無關(guān)的是【D】、A、希爾排序B、冒泡排序C、插入排序D、選擇排序22、下面幾種排序方法中,平均情況下占用內(nèi)存量最大的是【D】方法、A、插入排序B、選擇排序C、快速排序D、歸并排序23、對數(shù)據(jù)元素序列【49,72,68,13,38,50,97,27】進(jìn)行排序,前三趟排序結(jié)果時的結(jié)果依次為第一趟:49,72,68,13,38,50,97,27;第二趟:49,68,72,13,38,50,97,27;第三趟:13,49,68,72,38,50,97,27、該排序采納的方法是【A】、A、插入排序法B、選擇排序法C、冒泡排序法D、堆積排序法24、對具有n個元素的任意序列采納插入排序法進(jìn)行排序,排序趟數(shù)為【A】、A、n-1B、nC、n+1D、log2n25、對序列【49,38,65,97,76,13,47,50】采納直接插入排序法進(jìn)行排序,要把第七個元素47插入到已排序中,為尋找插入的合適位置需要進(jìn)行【C】次元素間的比較、A、3B、4C、5D、626、一組記錄的關(guān)鍵字序列為【46,79,56,38,40,84】,利用快速排序,以第一個關(guān)鍵字為分割元素,經(jīng)過一次劃分后結(jié)果為【C】、A、40,38,46,79,56,84B、40,38,46,84,56,79C、40,38,46,56,79,84D、38,40,46,56,79,8427、一組記錄的關(guān)鍵字序列為【46,79,56,38,40,84】,利用堆排序的方法建立的初始堆為【B】、A、79,46,56,38,40,84B、84,79,56,38,40,46C、84,79,56,46,40,38,D、84,56,79,40,46,3828、一組記錄的關(guān)鍵字序列為【25,48,16,35,79,82,23,40,36,72】,其中,含有5個長度為2的有序表,按歸并排序的方法對該序列進(jìn)行一趟歸并后的結(jié)果為【A】、A、16,25,35,48,23,40,79,82,36,72B、16,25,35,48,79,82,23,36,40,72C、16,25,48,35,79,82,23,36,40,72D、16,25,35,48,79,23,36,40,82,7229、已知10個數(shù)據(jù)元素為【54,28,16,34,73,62,95,60,26,43】,對該數(shù)列從小到到大排序,經(jīng)過一趟冒泡排序后的序列為【B】、A、16,28,34,54,73,62,60,26,43,95B、28,16,34,54,62,73,60,26,43,95C、28,16,34,54,62,60,73,26,43,95D、16,28,34,54,62,60,73,26,43,9530、用某種排序的方法對線性表【25,84,21,47,15,27,68,35,20】進(jìn)行排序時,元素序列的變化情況如下:【1】25,84,21,47,15,27,68,35,20【2】20,15,21,25,47,27,68,35,84【3】15,20,21,25,35,27,47,68,84【4】15,20,21,25,27,35,47,68,84其所采納的排序方法是【C】、A、希爾排序B、歸并排序C、快速排序D、直接選擇排序二、填空題1、在各種查找方法中,平均查找長度和結(jié)點個數(shù)n無關(guān)的查找方法是哈希表查找法、2、關(guān)鍵字是記錄某個數(shù)據(jù)項的值,用它能夠識別、確定一個記錄、3、在一個查找表中,能夠唯一地確定一個記錄的關(guān)鍵字稱為主關(guān)鍵字、4、平均查找長度是指為確定記錄在查找表中的位置,需要和給定值進(jìn)行比較的關(guān)鍵字個數(shù)的數(shù)學(xué)期望值、5、順序查找是一種最簡單的查找方法、6、折半查找又稱為二分查找、使用該查找算法的前提條件是,查找表中記錄相應(yīng)的關(guān)鍵字值必須按升序或降序排列、7、折半查找只適用于順序存儲結(jié)構(gòu)的有序表、8、分塊查找又稱為索引順序查找,它是一種介于順序查找和折半查找之間的查找方法、9、二叉排序樹或是一棵空樹,或是具有下面性質(zhì)的一棵二叉樹:【1】若左子數(shù)不空,則左子樹全部結(jié)點的值均小于根結(jié)點的值、【2】若右子數(shù)不空,則右子樹全部結(jié)點的值均大于根結(jié)點的值、【3】左右子樹又分別是二叉排序樹、10、哈希表是用來存放查找表中記錄序列的表,每一個記錄的存儲位置是以該記錄得到關(guān)鍵字為自變量,由相應(yīng)哈希函數(shù)計算所得到的函數(shù)值、11、在有序表A[1…、18]中,采納二分查找算法查找元素值等于A[17]的元素,所比較過的元素的下標(biāo)依次是9,14,16,17、12、依據(jù)排序過程中所用的存儲器不同,能夠?qū)⑴判蚍椒ǚ譃閮?nèi)部排序和外部排序、13、冒泡排序是一種比較簡單的交換排序方法、14、在對一組記錄【50,40,95,20,15,70,60,45,80】進(jìn)行直接插入排序時,當(dāng)把第7個記錄60插入到有序表時,為尋找插入位置需要比較3次、15、在歸并排序中,在第3趟歸并中,是把長度為5的有序表歸并為長度為8有序表、16、在堆排序和快速排序中,若原始記錄接近正序和反序,則選用堆排序,若原始記錄無序,則最好選用快速排序、17、對記錄序列排序是指按記錄的某個關(guān)鍵字排序,記錄序列按___主關(guān)鍵字__排序結(jié)果是唯一的、18、按某關(guān)鍵字對記錄序列排序,關(guān)鍵字相等的記錄若在排序前和排序后仍保持它們的前后關(guān)系,則排序算法是穩(wěn)定的,否則是不穩(wěn)定的、19、n個元素進(jìn)行冒泡法排序,一般需要進(jìn)行__n-1__趟冒泡,第j趟冒泡要進(jìn)行__n-j____次元素間的比較、20、當(dāng)從一個小根堆中刪除一個元素時,需要把堆尾元素填補到堆頂位置,然后再按條件把它逐層向下調(diào)整、三、綜合題1、已知序列【70,83,100,105,10,32,7,9】,請寫出對此序列采納插入排序法進(jìn)行升序排序時各趟的結(jié)果、答:原始序列:【70】,83,100,65,10,32,7,9第1趟:【70,83】,100,65,10,32,7,9第2趟:【70,83,100】,65,10,32,7,9第3趟:【65,70,83,100】,10,32,7,9第4趟:【10,65,70,83,100】,32,7,9第5趟:【10,32,65,70,83,100】,7,9第6趟:【7,10,32,65,70,83,100】,9第7趟:【7,9,10,32,65,70,83,100】已知序列【10,18,4,3,6,12,1,9,15,8】,請寫出對此序列采納歸并排序法進(jìn)行升序排序時各趟的結(jié)果、答:原始序列:10,18,4,3,6,12,1,9,15,8第1趟:[10,18][3,4][6,12][1,9][8,15]第2趟:[3,4,10,18,][1,6,9,12][8,15]第3趟:[3,4,10,18,][1