2023年數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題庫考前必備

第一章緒論一．選擇題1．?dāng)?shù)據(jù)結(jié)構(gòu)被形式地定義為（K，R），其中K是①_B_的有限集合，R是K上的②_D_的有限集合。①A．算法B．?dāng)?shù)據(jù)元素C．?dāng)?shù)據(jù)操作D．邏輯結(jié)構(gòu)②A．操作B．映象C．存儲D．關(guān)系2．算法分析的目的是①C，算法分析的兩個重要方面是②A。①A．找出數(shù)據(jù)結(jié)構(gòu)的合理性B．研究算法中的輸入和輸出的關(guān)系C．分析算法的效率以求改善D．分析算法的易懂性和文檔性②A．空間復(fù)雜性和時間復(fù)雜性B．對的性和簡明性C．可讀性和文檔性D．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性3．在計算機存儲器內(nèi)表達時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為(B)A．邏輯結(jié)構(gòu)B．順序存儲結(jié)構(gòu)C．鏈表存儲結(jié)構(gòu)D．以上都不對4．?dāng)?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)和外部結(jié)構(gòu)5．以下屬于順序存儲結(jié)構(gòu)優(yōu)點的是（A）。A．存儲密度大B．插入運算方便C．刪除運算方便D．可方便地用于各種邏輯結(jié)構(gòu)的存儲表達6．?dāng)?shù)據(jù)結(jié)構(gòu)研究的內(nèi)容是（D）。A．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)B．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)C．建立在相應(yīng)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)上的算法D．涉及以上三個方面7．鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)所占存儲空間（A）。A．分兩部分，一部分存放結(jié)點值，另一部分存放表達結(jié)點間關(guān)系的指針B．只有一部分，存放結(jié)點值C．只有一部分，存儲表達結(jié)點間關(guān)系的指針D．分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)8．一個對的的算法應(yīng)當(dāng)具有5個特性，除輸入、輸出特性外，此外3個特性是（A）。A．?dāng)M定性、可行性、有窮性B．易讀性、擬定性、有效性C．有窮性、穩(wěn)定性、擬定性D．可行性、易讀性、有窮性9．以下關(guān)于數(shù)據(jù)的邏輯結(jié)構(gòu)的敘述中對的的是（A）。A．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述B．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)反映了數(shù)據(jù)在計算機中的存儲方式C．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)分為順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)D．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)分為靜態(tài)結(jié)構(gòu)和動態(tài)結(jié)構(gòu)10．算法分析的重要任務(wù)是（C）。A．探討算法的對的性和可讀性B．探討數(shù)據(jù)組織方式的合理性C．為給定問題尋找一種性能良好的解決方案D．研究數(shù)據(jù)之間的邏輯關(guān)系二．解答設(shè)有一數(shù)據(jù)的邏輯結(jié)構(gòu)為：B=(D,S)，其中：D={d1,d2,…,d9}S={<d1,d3>,<d1,d8>,<d2,d3>,<d2,d4>,<d2,d5>,<d3,d9>,<d4,d7>,<d4,d6>,<d5,d6>,<d8,d9>,<d9,d7>}畫出這個邏輯結(jié)構(gòu)示意圖。d1d1d8d3d2d4d5d9d7d6第二章線性表一、選擇題1．下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？（A）A．存儲密度大B．插入運算方便C．刪除運算方便D．可方便地用于各種邏輯結(jié)構(gòu)的存儲表達2．下面關(guān)于線性表的敘述中，錯誤的是哪一個？（B）A．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B．線性表采用順序存儲，便于進行插入和刪除操作。C．線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D．線性表采用鏈接存儲，便于插入和刪除操作。3．若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則運用（A）存儲方式最節(jié)省時間。A．順序表B．雙鏈表C．帶頭結(jié)點的雙循環(huán)鏈表D．單循環(huán)鏈表4．某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（D）存儲方式最節(jié)省運算時間。A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙鏈表D．僅有尾指針的單循環(huán)鏈表5．在一個長度為n的順序表中刪除第i個元素(0<=i<=n)時，需向前移動（A）個元素A．n-i B．n-i+l C．n-i-1 D．i6．從一個具有n個結(jié)點的單鏈表中查找其值等于x的結(jié)點時，在查找成功的情況下，需平均比較（C）個元素結(jié)點A．n/2 B．n C．（n+1）/2 D．（n-1）/27．設(shè)單鏈表中指針p指向結(jié)點m，若要刪除m之后的結(jié)點（若存在），則需修改指針的操作為（A）A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;8．在一個單鏈表中，已知q結(jié)點是p結(jié)點的前趨結(jié)點，若在q和p之間插入s結(jié)點，則須執(zhí)行（B）A．s->next=p->next;p->next=sB．q->next=s;s->next=pC．p->next=s->next;s->next=pD．p->next=s;s->next=q9．線性表的順序存儲結(jié)構(gòu)是一種（A）的存儲結(jié)構(gòu)。A．隨機存取 B．順序存取 C．索引存取 D．散列存取二、填空1．在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過物理位置相鄰決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過指針決定的。2．在雙向鏈表中，每個結(jié)點具有兩個指針域，一個指向.直接前驅(qū)結(jié)點，另一個指向直接后繼結(jié)點。3．當(dāng)對一個線性表經(jīng)常進行存取操作，而很少進行插入和刪除操作時，則采用_順序存儲結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進行的是插入和刪除操作時，則采用鏈?zhǔn)酱鎯Y(jié)構(gòu)為宜。三、算法設(shè)計1．設(shè)有一個正整數(shù)序列組成的有序單鏈表（按遞增順序有序，且允許有相等的整數(shù)存在），試編寫能實現(xiàn)下列功能的算法（規(guī)定用最少的時間和最小的空間）=1\*GB3①擬定在序列中比正整數(shù)x大的數(shù)有幾個（相同的數(shù)只計算一次）=2\*GB3②將單鏈表中比正整數(shù)x小的偶數(shù)從單鏈表中刪除intcount(Linklisth,intx){intnum=0;Linknode*p;p=h->next;while(p&&p->data<=x)//p指針向后移動，直至p指向第一個值大于x的結(jié)點p=p->next;while(p)if(p->next&&p->data==p->next->data)//若p沒有指向鏈表中同一數(shù)值的最后一個結(jié)點，則向后移動p=p->next;else//若p指向數(shù)值相同的結(jié)點中的最后一個，則num加1，p指針后移，繼續(xù)執(zhí)行while循環(huán){num++;p=p->next;}returnnum;}=2\*GB3②voiddelevenl(Linklist&h,intx){Linknode*p,*r;p=h->next;r=h;while(p&&p->data<x){if(p->data%2==0){r->next=p->next;free(p);p=r->next;}else{r=p;p=p->next;}}}2．設(shè)有一個表頭指針為h的單鏈表。試設(shè)計一個算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點的鏈接方向逆轉(zhuǎn)，如下圖所示。規(guī)定逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最后一個結(jié)點。ΛpΛphΛhΛhhΛΛ2．voidconverse(Linklist&h){ Linknode*p,*q; p=h->next; h->next=NULL;q=p->next; while(q) { p->next=h; h=p; p=q;q=q->next; }p->next=h;h=p;}3．設(shè)計算法將一個帶頭結(jié)點的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點為A表中值小于零的結(jié)點，而C表的結(jié)點為A表中值大于零的結(jié)點（鏈表A的元素類型為整型，規(guī)定B、C表運用A表的結(jié)點）。3．voiddecompose(LinklistLa,Linklist&Lb,Linklist&Lc){ Linknode*p; Lc=(Linknode*)malloc(sizeof(Linknode)); Lc->next=NULL; p=La->next; Lb=La; Lb->next=NULL; while(p) { La=p->next; if(p->data>0) { p->next=Lc->next; Lc->next=p; } else { p->next=Lb->next; Lb->next=p; } p=La; }}4.假設(shè)鏈表A、B分別表達一個集合，試設(shè)計算法以判斷集合A是否是集合B的子集，若是，則返回1，否則返回0，并分析算法的時間復(fù)雜度。4．intsubset(LinkListla,LinkListlb){LinkNode*pa,*pb;pa=la->next;while(pa){pb=lb->next;while(pb&&(pb->data!=pa->data))pb=pb->next; if(!pb)return0; pa=pa->next; }return1;}算法時間復(fù)雜度O（A.Length*B.Length）5．設(shè)有一單循環(huán)鏈表la，其結(jié)點有三個域：prior、data與next，其中data為數(shù)據(jù)域,，next域指向直接后繼，prior域應(yīng)指向直接前驅(qū)，但目前空著。試寫一算法將此單循環(huán)鏈表改造為雙向循環(huán)鏈表。5．voidpriorset(DuLinkList&la){p=la;q=la->next;while(q!=la){q->prior=p;p=q;q=q->next;}q->prior=p;}第三章棧和隊列一、選擇題1．已知棧的最大容量為4。若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行,則也許出現(xiàn)的出棧序列為（C）A.5，4，3，2，1，6 B.2，3，5，6，1，4C.3，2，5，4，1，6 D.1，4，6，5，2，3設(shè)有一個棧，元素的進棧順序為A,B,C,D,E,下列是不也許的出棧序列（C）A．A,B,C,D,E B．B,C,D,E,AC．E,A,B,C,D D．E,D,C,B,A2．在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧解決時，top變化為（C）A．top不變 B．top=0 C．top-- D．top++3．向一個棧頂指針為hs的鏈棧中插入一個s結(jié)點時，應(yīng)執(zhí)行（B）A．hs->next=s;B．s->next=hs;hs=s;C．s->next=hs->next;hs->next=s;D．s->next=hs;hs=hs->next;4．在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為（D）A．rear％n==front B．（front+l）％n==rearC．rear％n-1==frontD．(rear+l)％n==front5．在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊空的條件為（C）A．rear％n==front B．front+l=rearC．rear==front D．(rear+l)％n=front6．在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結(jié)點的操作為（A）A．front=front->nextB．rear=rear->nextC．rear=front->nextD．front=rear->next7．某堆棧的輸入序列為1，2，3，…，n，輸出序列的第一個元素是n，則第i個輸出元素為（C）A．iB．n-iC．n-i+1D．哪個元素?zé)o所謂8．用不帶頭結(jié)點的單鏈表存儲隊列時,其隊頭指針指向隊頭結(jié)點,其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時(D)。A．僅修改隊頭指針B.僅修改隊尾指針C.隊頭、隊尾指針都要修改D.隊頭,隊尾指針都也許要修改二、解答題1．一個雙向棧S是在同歷來量空間內(nèi)實現(xiàn)的兩個棧，它們的棧底分別設(shè)在向量空間的兩端。試為此雙向棧設(shè)計初始化InitStack(S)、入棧Push(S,i,x)和出棧Pop(S,i)等算法，其中i為0或1，用以表達棧號。1．雙向棧棧底1棧底1……….………棧底2棧底2//雙向棧類型定義#defineSTACK_SIZE100;Typedefstruct{SElemType*base_one,*base_two;//棧底指針SElemType*top_one,*top_two;//棧頂指針intstacksize;}SqStack;StatusInitStack(SqStack&S){//初始化雙向棧S.base_one=S.top_one=(SElemType*)malloc(STACK_SIZE*sizeof(SElemType));//第一個棧底和棧頂指向數(shù)組起點S.base_two=S.top_two=S.base_one+STACK_SIZE-1;//第二個棧底和棧頂指向數(shù)組終點S.stacksize=STACK_SIZE;returnOK;}//InitStackStatusPush(SqStack&S,inti,SElemTypee){//入棧操作，i=0時將e存入前棧，i=1時將e存入后棧if(S.top_two<S.top_one)returnOVERFLOW;//棧滿，不考慮追加空間if(i==0)*S.top_one++=e;else*S.top_two--=e;returnOK;}//PushSElemTypePop(SqStack&S,inti){//出棧操作，i=0出前棧，i=1出后棧if(i==0){if(S.top_one==S.base_one)returnERROR;S.top_one--;e=*S.top_one;}else{if(S.top_two==S.base_two)returnERROR;S.top_two++;e=*S.top_two;}returne;}//Pop2．運用兩個棧S1、S2模擬一個隊列時，如何使用棧的運送實現(xiàn)隊列的插入、刪除運算。2．#defineM3structStack{ Qelemtypedata[M]; inttop;};structQueue{ Stacks1; Stacks2;};voidInitQueue(Queue&Q)//初始化隊列{ Q.s1.top=0; Q.s2.top=0;}intIsEmpty(Queue&Q)//判斷隊列是否為空{(diào) if(Q.s1.top==0&&Q.s2.top==0) return1; if(Q.s2.top==0&&Q.s1.top!=0) { while(Q.s1.top!=0) Q.s2.data[Q.s2.top++]=Q.s1.data[--Q.s1.top]; } return0;}intIsFull(Queue&Q){ if(Q.s1.top==M&&Q.s2.top!=0) return1; if(Q.s1.top==M&&Q.s2.top==0) { while(Q.s1.top!=0) Q.s2.data[Q.s2.top++]=Q.s1.data[--Q.s1.top]; return0; } if(Q.s1.top!=M) return0;}voidInQueue(Queue&Q,Qelemtypee){ if(IsFull(Q)) { cout<<"OVERFLOW"<<endl; return; } Q.s1.data[Q.s1.top++]=e;}voidDeQueue(Queue&Q,Qelemtype&e){ if(IsEmpty(Q)) { cout<<"UNDERFLOW"<<endl; return; } e=Q.s2.data[--Q.s2.top];}3．已知一個棧S的輸入序列為abcd，下面兩個序列能否通過棧的push和pop操作輸出？假如能，請寫出操作序列；假如不能，請寫明因素。(1)dbca(2)cbda3．(1)不能（2）可以因素略4．假設(shè)以帶頭結(jié)點的循環(huán)鏈表表達隊列，并且只設(shè)一個指針指向隊尾元素結(jié)點(注意不設(shè)頭指針)，試編寫相應(yīng)的置空隊、判隊空、入隊和出隊等算法。4．structQueueNode{ Qelemtypedata; QueueNode*next;};structLinkQueue{ QueueNode*rear;};voidInitQueue(LinkQueue&Q)//置空隊{ Q.rear=newQueueNode; Q.rear->next=Q.rear;}intEmptyQueue(LinkQueueQ)//判隊空{(diào) returnQ.rear==Q.rear->next;}voidEnQueue(LinkQueue&Q,Qelemtypee)//元素入隊{ QueueNode*p;//新建一個結(jié)點，并置其值為e p=newQueueNode; p->data=e;//將結(jié)點插入隊列末尾 p->next=Q.rear->next; Q.rear->next=p;//修改隊尾指針 Q.rear=p;}voidDeQueue(LinkQueue&Q,Qelemtype&e)//元素出隊{ QueueNode*p; if(EmptyQueue(Q))//若隊中無元素，則無法執(zhí)行出隊操作 { cout<<"error"<<endl; return; } p=Q.rear->next->next;//讓p指向隊頭元素 e=p->data;if(p==Q.rear)//如隊中只有一個元素，則要rear指向頭結(jié)點，頭結(jié)點的next指針指向自身{ Q.rear=Q.rear->next;Q.rear->next=Q.rear;}else//若隊中不只一個元素，則刪除p所指向的結(jié)點。 Q.rear->next->next=p->next; deletep;//釋放被刪除結(jié)點的存儲空間}5．假設(shè)以I和O表達入棧和出棧操作，棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表達為僅由I和O組成的序列。稱可以操作的序列為合法序列，否則稱為非法序列。(1)下面所示的序列中哪些是合法的？A．IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO(2)通過對問題⑴的分析，寫出一個算法鑒定所給的操作序列是否合法。若合法返回TRUE，否則返回FALSE。（假定被鑒定的操作序列已經(jīng)存入一維數(shù)組中）5．typedefstruct{chardata[10];inttop;}stack;intdescion(char*str){stacks;inti;s.top=0;for(i=0;str[i];i++){switch(str[i]){case'I':s.data[s.top++]=str[i];break;//若為I，則如棧case'O':if(s.top==0)return0;s.top--;//若為O，則從棧中彈出一個I}}if(s.top==0)return1;elsereturn0;}第四章串一．選擇題1.若串S='software',其子串的數(shù)目是（B）A.8B.37C2.設(shè)有兩個串p和q,求q在p中初次出現(xiàn)的位置的運算稱作（B）A.連接B.模式匹配C.求串長D

.求子串3．設(shè)字符串S1=“ABCDEFG”，S2=“PQRST”，則運算：S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值為（D）A．ABCDEFB．BCDEFGC．BCDPQRSTD．

BCDEFEF4.下面的說法中，只有（A）是對的的A.串是一種特殊的線性表B.串的長度必須大于零C.串中元素只能是字母D.空串就是空白串5.兩個字符串相等的條件是（D）A.兩串的長度相等B.兩串包含的字符相同C.兩串的長度相等，并且兩串包含的字符相同D.兩串的長度相等，并且相應(yīng)位置上的字符相同二、填空題1.

令t1=“aaab”,t2=“abcabaa”,t3=“abcaabbabcabaacba”，試分別求出他們的nex函數(shù)值0123,0111232,32211。2.空格串的長度為．空格數(shù)，空串的長度為0。3.設(shè)串S=’Howareyou’，則串的長度為11。三、問答題回文是指正讀反讀均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。試寫一個算法鑒定給定的字符變量是否為回文。StatusIsHuiwen(char*S){i=0;while(s[i]!=’\0’i=i-1;j=0;while(j<i)if(s[j]!=s[i])return0;else{j++;i--;}return1;}第五章數(shù)組和廣義表一．選擇題1.設(shè)有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A[5，8]的存儲首地址為(B)A.BA+141B.BA+180C.BA+222D.BA+2252.假設(shè)以行序為主序存儲二維數(shù)組A=array[1..100，1..100]，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC[5，5]=（B）A.808B.818C.1010D.10203對稀疏矩陣進行壓縮存儲目的是（C）A．便于進行矩陣運算B．便于輸入和輸出C．節(jié)省存儲空間D．減少運算的時間復(fù)雜度4.廣義表A=(a,b,(c,d),(e,(f,g))),則下面式子的值為（D）。Head(Tail(Head(Tail(Tail(A)))))A.(g)B.(d)C.cD.d5.設(shè)廣義表L=（（a,b,c）），則L的長度和深度分別為（B）。A.1和1B.1和3C.1和2D.2和36.假設(shè)以三元組表表達稀疏矩陣，則與如圖所示三元組表相應(yīng)的4×5的稀疏矩陣是（注：矩陣的行列下標(biāo)均從1開始）（B）A. B.C. D.7.一個非空的廣義表的表尾（B）A.不能是子表B.只能是子表C.只能是原子D.是原子或子表8.假如將矩陣An×n的每一列當(dāng)作一個子表，整個矩陣當(dāng)作是一個廣義表L，即L=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通過求表頭head和求表尾tail的運算求取矩陣中的每一個元素，則求得a21的運算是（A）A.head(tail(head(L))) B.head(head(head(L)))C.tail(head(tail(L))) D.head(head(tail(L)))二．填空題1.己知三對角矩陣A[1..9,1..9]的每個元素占2個單元，現(xiàn)將其三條對角線上的元素逐行存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A[7,8]的地址為__1038____2.設(shè)廣義表L=((),()),則head(L)是_()；tail(L)是(())_；L的長度是2_；深度是2_。3.廣義表A=（（（a，b），（c，d，e））），試用求表頭和表尾的操作Head()和Tail()取出A中的原子e的操作是:_Head(Tail(Tail(Head(Tail(Head(A))))))__.三．解答下列各題1．已知一個6行5列的稀疏矩陣中非零元的值分別為：-90，41，-76，28，-54，65，-8，它們在矩陣中的列號依次為：1，4，5，1，2，4，5。當(dāng)以帶行表的三元組表作存儲結(jié)構(gòu)時，其行表中的值依次為0，0，2，2，3，5（行列下標(biāo)均從1開始），寫出該稀疏矩陣。0000000000-9000410000000000-7628-5400000065-82．寫出廣義表B=(a,b),C=(a,(b,c,(d,e))),D=(a,B,C),E=((a,b),E)的存儲結(jié)構(gòu)（任一種存儲方法均可）110a1∧0bB10a1∧C110b0c1∧10d1∧0e110a1∧D11∧1∧0bE10a第六章樹和二叉樹一．選擇題{CDDACADDEDBCCBBCACCC}1．假如在數(shù)據(jù)結(jié)構(gòu)中每個數(shù)據(jù)元素只也許有一個直接前驅(qū)，但可以有多個直接后繼，則該結(jié)構(gòu)是（）A.棧 B.隊列C.樹 D.圖2．設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1則T中的葉子數(shù)為（）A．5B．6C．7D．83．已知一棵含50個結(jié)點的二叉樹中只有一個葉子結(jié)點，則該樹中度為1的結(jié)點個數(shù)為（）A.0 B.14．樹的先根序列等同于與該樹相應(yīng)的二叉樹的（）A．先序序列B．中序序列C．后序序列 D．層序序列5.用二叉鏈表表達具有n個結(jié)點的二叉樹時，值為空的指針域的個數(shù)為（）A．n-1B．nC．n+l D．2n6.設(shè)森林F相應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（）A．m-nB．m-n-1C．n+1D7.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1，則T中的葉子數(shù)為（）A．5B．6C．7D．88．設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F相應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（）A．M1B．M1+M2C．M3D．M2+M39．一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）A．250B．500C．254D．505E．以上答案都不對10．有n個葉子的哈夫曼樹的結(jié)點總數(shù)為（）A．不擬定B．2nC．2n+1D．2n-111．一棵二叉樹高度為h,所有結(jié)點的度或為0，或為2，則這棵二叉樹最少有()結(jié)點A．2hB．2h-1C．2h+1D．h+112．將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度（）A．4B．5C．6D．713．若度為m的哈夫曼樹中，其葉結(jié)點個數(shù)為n，則非葉結(jié)點的個數(shù)為（）A．n-1B．n/m-1C．(n-1)/(m-1)D．n/(m-1)-1E．(n+1)/(m+1)-114．若下面幾個符號串編碼集合中，不是前綴編碼的是（）。A．{0,10,110,1111}B．{11,10,001,101,0001}C．{00,010,0110,1000}D．{b,c,aa,ac,aba,abb,abc}15．一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列也許是（）A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG16．線索二叉樹是一種（）結(jié)構(gòu)。A．邏輯B．邏輯和存儲C．物理D．線性17．引入二叉線索樹的目的是（）A．加快查找結(jié)點的前驅(qū)或后繼的速度B．為了能在二叉樹中方便的進行插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結(jié)果唯一18．n個結(jié)點的線索二叉樹上具有的線索數(shù)為（）A．2nB．n－lC．n＋lD．n19．若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則x的前驅(qū)為()A.X的雙親B.X的右子樹中最左的結(jié)點C.X的左子樹中最右結(jié)點D.X的左子樹中最右葉結(jié)點20．某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹A．空或只有一個結(jié)點B．任一結(jié)點無左子樹C．高度等于其結(jié)點數(shù)D．任一結(jié)點無右子樹二．填空題1.假定一棵樹的嵌套括號表達法為A（B（E），C（F（H，I，J），G），D），則該樹的度為______，樹的深度為_____，終端點的個數(shù)為____，但分支結(jié)點的個數(shù)為_____，雙分支結(jié)點為_____，三分支結(jié)點的個數(shù)為______，C結(jié)點的雙親結(jié)點為_________，其孩子結(jié)點為__________和為_________結(jié)點。2．

一棵深度為K的滿二叉樹結(jié)點總數(shù)為___________，一棵深度為K的完全二叉樹的結(jié)點總數(shù)的最小值為________，最大值為____________。3．

由三個結(jié)點構(gòu)成的二叉樹，共有_____________種不同的形態(tài)。4．

具有100個葉子結(jié)點的完全二叉樹的深度為5．

高為h（h>0）的滿二叉樹相應(yīng)森林的由棵樹構(gòu)成。三．已知一個二叉樹的中序序列為CBEDAHGIJF,后序序列為CEDBHJIGFA。1．畫出該二叉樹。2．畫出該二叉樹的先序線索二叉樹。四．試找出分別滿足下列條件的所有二叉樹：1．先序序列和中序序列相同。2．中序序列和后序序列相同。3．先序序列和后序序列相同。五、設(shè)二叉樹用二叉鏈表表達，設(shè)計算法求二叉樹的高度。intDepth(BiTreet)（后序遍歷）{if(！t)d=0；else{dl=Depth(t->lchild);dr=Depth(t->rchild);d=1+(dl>dr?dl:dr);}returnd;}六、設(shè)T是一棵具有n個結(jié)點的二叉樹，若給定二叉樹T的先序序列和中序序列，并假設(shè)T的先序序列和中序序列分別放在數(shù)組PreOrder[1..n]和InIrder[1..n]中，設(shè)計一個構(gòu)造二叉樹T的二叉鏈表存儲結(jié)構(gòu)的算法。六//根據(jù)二叉樹的先序序列和中序序列創(chuàng)建二叉鏈表voidcreateBiTree(charpre[],charin[],intstart,intend,int&count,BiTree&T)//按先序順序創(chuàng)建二叉鏈表，pre為存放先序序列的字符數(shù)組，in為存放中序序列的字符數(shù)組，//count為二叉樹的根結(jié)點在先序序列中的序號//start和end為以pre[count]為根的二叉樹在中序序列中的起始位置和結(jié)束位置//T為二叉鏈表的根指針，{ if(start>end)T=0; else {T=(BiTNode*)malloc(sizeof(BiTNode));//新建根結(jié)點 if(!T)exit(0); T->data=pre[count];T->lchild=T->rchild=0;for(inti=0;in[i]!='\0';i++)//查找根結(jié)點在中序序列in[]中的下標(biāo)if(in[i]==pre[count])break;count++;if(in[i]=='\0')cout<<"inputerror"<<endl;else{createBiTree(pre,in,start,i-1,count,T->lchild);//根據(jù)先序序列和中序序列創(chuàng)建左子樹createBiTree(pre,in,i+1,end,count,T->rchild);//根據(jù)先序序列和中序序列創(chuàng)建右子樹}七、設(shè)用于通信的電文由字符集｛a,b,c,d,e,f,g｝中的字母構(gòu)成，它們在電文中出現(xiàn)的頻率分別為｛0.31,0.16,0.10,0.08,0.11,0.20,0.04｝，回答下列問題：⑴為這7個字母設(shè)計哈夫曼編碼⑵若對這7個字母進行等長編碼，至少需要幾位二進制數(shù)？、哈夫曼樹a:10b:110c:010d:1110e:011f::00g等長編碼至少需要3位二進制位。八．設(shè)計算法以輸出二叉樹中先序序列的前k（k>0）個結(jié)點的值。八voidpreintraverse(BiTreeT,int&n){if(T){n++;if(n<=k){cout<<T->data;intraverse(T->lchild,n);intraverse(T->rchild,n);}}}九．編寫算法，對一棵二叉樹記錄葉子的個數(shù)九、voidCountLeaf(BiTreet，int&count)（先序遍歷）{if(t){if((t->lchild==NULL)&&(t->rchild==NULL))count++;CountLeaf(t->lchild，&count);CountLeaf(t->rchild,&count);}第七章圖一．選擇題1．n個頂點，e條邊的有向圖的鄰接矩陣中非零元素有C個。A.nB.2eC.eD.n+e2．用鄰接表存儲圖所用的空間大?。ˋ）A．與圖的頂點數(shù)和邊數(shù)都有關(guān)B．只與圖的邊數(shù)有關(guān)C．只與圖的頂點數(shù)有關(guān)D．與邊數(shù)的平方有關(guān)3．有n條邊的無向圖的鄰接表存儲法中，鏈邊中結(jié)點的個數(shù)是（B）個。A．nB．2nC．n/2D．n*n4．一個帶權(quán)無向連通圖的最小生成樹（A）。A．有一棵或多棵.B．只有一棵C．一定有多棵D．也許不存在二．如下所示有向圖：1．請給出每個頂點的度，入度和出度。ABCD入度1121出度2111度32322．請畫出其鄰接矩陣、鄰接表、逆鄰接表、十字鏈表。010100100101001010000010鄰接矩陣ABCD13∧2∧0∧2∧鄰接表3ABCD2∧0∧0逆鄰接表313∧AABCD01∧03∧∧12∧20∧∧32∧∧十字鏈表三．試對下圖所示的AOE網(wǎng)絡(luò)，解答下列問題。1．求每個事件的最早發(fā)生時間ve[i]和最遲發(fā)生時間vl[i]。2．求每個活動的最早開始時間ee(s)和最遲開始時間el(s)。3．指出哪些活動加速可使整個工程提前完畢。事件ABCDEF最早發(fā)生時間ve[i]032668最遲發(fā)生時間vl[i]042678活動a1a2a3a4a5a6a7a8最早開始時間00332266最遲開始時間10442567關(guān)鍵活動為a2a5a四．寫出下圖所示的AOV網(wǎng)的所有拓撲有序序列。四、拓撲有序序列ABCDEFABCEDFACBDEFACBEDFACEBDF第九章查找一．填空題１．采用二分法進行查找的查找表，應(yīng)選擇___順序_________方式的存儲結(jié)構(gòu)２．設(shè)在有序表A[0……9]中進行二分查找，比較一次查找成功的結(jié)點數(shù)為_1____，比較二次查找成功的結(jié)點數(shù)為__2____，比較三次查找成功的結(jié)點數(shù)為__4___，比較四次查找成功的結(jié)點數(shù)為__3___，比較五次查找成功的結(jié)點數(shù)為__0___，平均查找長度為___（1+2*2+3*4+4*3）/10=2.9___。（3）設(shè)在線性表R[0……59]中進行分塊查找，共分10塊，每塊長度為6，若運用順序查找法對索引表和子塊進行查找，則查找每個元素的平均查找長度為___9_______。二．選擇題１．對線性表進行二分查找時，規(guī)定線性表必須（B）A．鍵值有序的鏈接表B．鍵值有序的順序表C．鏈接表但鍵值不一定有序D．順序但鍵值不一定有序２．有一個有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99},當(dāng)用二分查找法查找鍵值為84的結(jié)點時，經(jīng)（C）比較后查找成功。A．2B．3C．4D．12３．順序檢索一個具有n個數(shù)據(jù)元素的線性表，其時間復(fù)雜度為_____，二分檢索一個具有n個數(shù)據(jù)元素的線性表，其時間復(fù)雜度為（AB）A．O(n)B．O(log2n)C．O(n2)D．O(nlog2n)４．設(shè)散列表長度為m，散列函數(shù)為H（key）=key%p，為了減少發(fā)生沖突的也許性，p應(yīng)取（B）A．小于m的最大奇數(shù)B．