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

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