2022年數(shù)據(jù)結(jié)構(gòu)習(xí)題

..精品文本精品文本.精品文本第一章知識點(diǎn)：1.根本概念：數(shù)據(jù)結(jié)構(gòu)分類、特點(diǎn)等：如線性結(jié)構(gòu)，是數(shù)據(jù)元素之間存在一種〔一對一關(guān)系〕數(shù)據(jù)元素的概念〔數(shù)據(jù)項(xiàng)〕2.時空復(fù)雜度1、設(shè)有數(shù)據(jù)結(jié)構(gòu)〔D，R〕，其中D={d1,d2,d3,d4,d5,d6},R=r,r={(d1,d2),(d2,d3),(d3,d4),(d2,d5),(d3,d5)}試按照圖論中的畫法畫出其邏輯結(jié)構(gòu)圖。d1d1d2d31d5d4d62、稱算法的時間復(fù)雜度為O(f(n))，其含義是指算法的執(zhí)行時間和_【1】_的數(shù)量級相同。3.計算下面程序段的時間復(fù)雜度。x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;解：因?yàn)閤++共執(zhí)行了n-1+n-2+……＋1=n(n-1)/2，所以執(zhí)行時間為O〔n2〕.4.計算下面程序段的時間復(fù)雜度。x=n;y=0;//n是不小于1的常數(shù)while(x>=(y+1)*(y+1)){y++;}1.解：設(shè)@執(zhí)行了t(n)次，那么(t(n)+1)2<=n，推出t(n)<=n1/2-1。所以時間復(fù)雜度為O〔n1/2〕.5.分析下面各程序段的時間復(fù)雜度〔1〕O(n*m)(2)O(log3n)1〕for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;2〕i=1;while(i<=n)i=i*3;6.在n個結(jié)點(diǎn)的順序表中，算法的時間復(fù)雜度是O〔1〕的操作是：A訪問第i個結(jié)點(diǎn)〔1≤i≤n〕和求第i個結(jié)點(diǎn)的直接前驅(qū)〔2≤i≤n〕在第i個結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)〔1≤i≤n〕刪除第i個結(jié)點(diǎn)〔1≤i≤n〕將n個結(jié)點(diǎn)從小到大排序第二章線性表知識點(diǎn)：順序表、單鏈表、雙向鏈表〔插入、查找、刪除運(yùn)算〕循環(huán)鏈表(單雙向)特點(diǎn)，考點(diǎn)：根本操作、復(fù)雜度、特點(diǎn)、算法應(yīng)用1.在一個單鏈表中，假設(shè)p所指結(jié)點(diǎn)是q所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，那么刪除結(jié)點(diǎn)q的正確操作是〔B〕A.p->next=q B.p->next=q->nextC.p=q->next D.p->next=q->next->next2、在一個頭指針為head的帶頭結(jié)點(diǎn)單鏈表中，要向表頭插入一個由指針p指向的結(jié)點(diǎn),那么應(yīng)執(zhí)行【4】p->next=head->next;、【5】head->next=p。4.在雙鏈表中，在指針P所指結(jié)點(diǎn)前面插入一個結(jié)點(diǎn)S時的語句序列是：S->next=P;S->prior=P->prior;P->prior=S;____S->prior->next=S___；3.在雙向鏈表指針p的結(jié)點(diǎn)前插入一個指針q的結(jié)點(diǎn)操作是〔C〕。A.p->Prior=q;q->Next=p;p->Prior->Next=q;q->Prior=p->Prior;B.p->Prior=q;p->Prior->Next=q;q->Next=p;q->Prior=p->Prior;C.q->Next=p;q->Prior=p->Prior;p->Prior->Next=q;p->Prior=q;D.q->Prior=p->Prior;q->Next=p;p->Prior=q;p->Prior->Next=q;4.p結(jié)點(diǎn)是某雙向鏈表的中間結(jié)點(diǎn)，要刪除p結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是：Dp->next->next->prior=p;p->next=p->next->next;q=p->next;free(q);q=p->next;p->next=p->next->next;p->next->next->prior=p;free(q);q=p->next;p->next->prior=p;p->next=p->next->next;free(q);q=p->next;p->next=p->next->next;p->next->prior=p;free(q);5.設(shè)r指向單鏈表的最后一個結(jié)點(diǎn)，要在最后一個結(jié)點(diǎn)之后插入s所指的結(jié)點(diǎn)，需執(zhí)行的三條語句是___P->next==NULL________；r=s;r->next=null;。6.在單鏈表中，指針p所指結(jié)點(diǎn)為最后一個結(jié)點(diǎn)的條件是_Ls==NULL、ls=ls->link。7對于一個具有n個結(jié)點(diǎn)的單鏈表，在的結(jié)點(diǎn)*p后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為O(1),在給定值為x的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為O(n)___。8.在順序表中訪問任意一結(jié)點(diǎn)的時間復(fù)雜度均為O(1)，因此順序表也稱為隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)?！睞〕1.在n個結(jié)點(diǎn)的順序表中，算法的時間復(fù)雜度是O〔1〕的操作是：訪問第i個結(jié)點(diǎn)〔1≤i≤n〕和求第i個結(jié)點(diǎn)的直接前驅(qū)〔2≤i≤n〕在第i個結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)〔1≤i≤n〕刪除第i個結(jié)點(diǎn)〔1≤i≤n〕將n個結(jié)點(diǎn)從小到大排序9、線性鏈表不具有的特點(diǎn)是〔A〕。A．隨機(jī)訪問B．不必事先估計所需存儲空間大小C．插入與刪除時不必移動元素D．所需空間與線性表長度成正比10.假設(shè)某鏈表最常用的操作是在最后一個結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)和刪除最后一個結(jié)點(diǎn)，那么采用(C)存儲方式最節(jié)省時間。A.單鏈表 B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D.單循環(huán)鏈表11.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是__L->next=L->prior或L->next=L_____。12.不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是head=NULL。13．一個帶表頭結(jié)點(diǎn)的單循環(huán)鏈表，指針P指向鏈的某一個結(jié)點(diǎn)，假設(shè)P->next->next->next==P，那么此鏈表的長度可能是0或2。14.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動〔B〕個元素A.8B.63.5C.63D.715.對于長度為n的順序表執(zhí)行刪除操作，那么其結(jié)點(diǎn)的移動次數(shù)〔C〕A.最少為0，最多為n B.最少為1，最多為nC.最少為0，最多為n-1 D.最少為1，最多為n-116.線性表的長度是線性表所占用的存儲空間的大小。(F)

17.雙循環(huán)鏈表中，任意一結(jié)點(diǎn)的后繼指針均指向其邏輯后繼。(T)

18、線性表Ｌ在B情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。Ａ、需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值Ｂ、需不斷對Ｌ進(jìn)行刪除插入Ｃ、Ｌ中含有大量的結(jié)點(diǎn)Ｄ、Ｌ中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜19假設(shè)某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，那么采用〔④〕存儲方式最節(jié)省時間。①單鏈表②雙鏈表③單向循環(huán)④順序表1.假設(shè)線性表L=(a1,a2,……,an)用帶頭結(jié)點(diǎn)的單鏈表存儲表示，試編寫算法對其實(shí)現(xiàn)就地逆置，即利用原鏈表中每一個結(jié)點(diǎn)存儲空間，使得元素的邏輯次序改變?yōu)?an,……,a2,a1)。2．試編寫算法，以統(tǒng)計帶頭結(jié)點(diǎn)單鏈表的元素個數(shù)。3.設(shè)某單鏈表Ｌ的結(jié)點(diǎn)結(jié)構(gòu)為data|next,試編寫算法判斷該鏈表的元素是否是遞增的。4.單鏈表L是一個遞增有序表，試寫一高效算法，刪除表中值大于min

且小于max的結(jié)點(diǎn)(假設(shè)表中有這樣的結(jié)點(diǎn))，同時釋放被刪結(jié)點(diǎn)的空間，這里min

和

max是兩個給定的參數(shù)。請分析你的算法的時間復(fù)雜度。

第3章棧和隊列知識點(diǎn)：棧、循環(huán)隊列考點(diǎn)：出入棧操作、棧和隊列特點(diǎn)、循環(huán)隊列操作〔元素個數(shù)、隊頭隊尾指針〕、應(yīng)用1．一個棧的入棧序列是1、2、3、4，假設(shè)第二個出棧的元素是4，那么最后出棧的元素可能是１或２。2.一個棧的輸入序列為12345，那么以下序列中不可能是棧的輸出序列的是(B)A.23415 B.54132C.23145 D.154323.在對鏈隊列作出隊操作時，不會改變front指針的值。(T)4.假設(shè)一個棧的輸入序列為123…n，其輸出序列的第一個元素為n，那么其輸出序列的每個元素ai一定滿足ai=n-i+1(i=1,2...,n)(T)5.棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂,不允許插入和刪除運(yùn)算的一端稱為棧底。6、如果入棧序列是1，3，5，…，97，99，且出棧序列的第一個元素為99，那么出棧序列中第30個元素為____41__。7．有5個元素，其入棧次序?yàn)椋篈，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧〔即C第一個且D第二個出?！车拇涡蛴心膸讉€？答：三個：CDEBA，CDBEA，CDBAE8、向順序棧中壓入新元素時，應(yīng)當(dāng)〔A〕。A．先移動棧頂指針，再存入元素B．先存入元素，再移動棧頂指針C．先后次序無關(guān)緊要D．同時進(jìn)行9.設(shè)一個鏈棧的棧頂指針是ls，棧中結(jié)點(diǎn)格式為info|link,棧空的條件是__________.如果棧不為空，那么退棧操作為p=ls；__Ls==NULL、ls=ls->link._；free(p);。10.如果以鏈表作為棧的存儲結(jié)構(gòu)，那么退棧操作時〔③〕必須判別棧是否滿對棧不作任何判別必須判別棧是否空判別棧元素的類型11.判定一個棧ST〔最多元素為m0〕為空的條件是BＡ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0〔D〕12．?dāng)?shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當(dāng)前隊列頭元素的前一位置，ｒ?yàn)殛犖苍氐奈恢?，假定隊列中元素的個數(shù)小于ｎ，計算隊列中元素的公式為〔Ａ〕r－f;〔Ｂ〕〔n＋f－r〕%n;〔Ｃ〕n＋r－f;〔Ｄ〕〔n＋r－f〕%n13.判定一個隊列QU〔最多元素為m0〕為滿隊列的條件是AA．QU->rear－QU->front==m0B．QU->rear－QU->front－1==m0C．QU->front==QU->rearD．QU->front==QU->rear+114.設(shè)循環(huán)隊列的容量為40〔序號從0到39〕，現(xiàn)經(jīng)過一系列的入隊和出隊運(yùn)算后，有①front=11，rear=19;②front=19，rear=11；問在這兩種情況下，循環(huán)隊列中各有元素多少個？答：①L=〔40＋19－11〕%40=8②L=〔40＋11－19〕%40=3215、假設(shè)為循環(huán)隊列分配的向量空間為Q[20]，假設(shè)隊列的長度和隊頭指針值分別為13和17，那么當(dāng)前尾指針的值為__10____。16.設(shè)數(shù)組Data[0..m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，那么執(zhí)行出隊操作的語句為〔④〕①front=front+1②front=(front+1)%m③rear=(rear+1)%m④front=(front+1)%(m+1)12.在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是〔A〕A．隊列

B．棧C．線性表

D．有序表13.用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時，通常是采用C來實(shí)現(xiàn)算法的。A．樹B.隊列C.棧D.圖17.簡述以下算法的功能〔棧和隊列的元素類型均為int〕。voidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);};while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}答：該算法的功能是：利用堆棧做輔助，將隊列中的數(shù)據(jù)元素進(jìn)行逆置。

第4章串知識點(diǎn)：定義、串的根本操作、根據(jù)KMP算法原理，分別求出它們的Next函數(shù)值作業(yè)1.串是任意有限個〔③〕①符號構(gòu)成的序列②符號構(gòu)成的集合③字符構(gòu)成的序列④字符構(gòu)成的集合2、設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作：〔Ｂ〕Ａ．連接Ｂ．模式匹配Ｃ．求子串Ｄ．求串長3、串是一種特殊的線性表，其特殊性表達(dá)在：〔Ｂ〕Ａ．可以順序存儲Ｂ．?dāng)?shù)據(jù)元素是一個字符Ｃ．可以鏈?zhǔn)酱鎯Γ模當(dāng)?shù)據(jù)元素可以是多個字符5、設(shè)S=“A;/document/Mary.doc〞，那么strlen(s)=20。6.設(shè)目標(biāo)T=〞abccdcdccbaa〞，模式P=“cdcc〞，那么第6次匹配成功。7.設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號i開始的j個字符組成的子串，len(s)返回串s的長度，那么con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是BCDEFEF。8.設(shè)串sl=″DataStructureswithJava″,s2=″it″，那么子串定位函數(shù)index(s1,s2)的值為〔D〕A．15

B．16C．17

D．189.令t=‵abcaabcab′，根據(jù)KMP算法原理，分別求出它們的Next函數(shù)值。i123456789串tabcaabcabNext(i)

第5章數(shù)組和廣義表知識點(diǎn)：二維數(shù)組的存儲、特殊矩陣、廣義表作業(yè)P31-331.假設(shè)有二維數(shù)組A6×8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。A的起始存儲位置〔基地址〕為1000，那么數(shù)組A的體積〔存儲量〕為288；末尾元素A57的第一個字節(jié)地址為1282；假設(shè)按行存儲時，元素A14的第一個字節(jié)地址為1072；假設(shè)按列存儲時，元素A47的第一個字節(jié)地址為1276。〔〕2.假設(shè)有60行70列的二維數(shù)組a[1…60,1…70]以列序?yàn)橹餍蝽樞虼鎯?，其基地址?000，每個元素占2個存儲單元，那么第32行第58列的元素a[32,58]的存儲地址為(Ｃ)?！矡o第0行第0列元素〕(Ａ)．4454(Ｂ)．6904(Ｃ)．7902(Ｄ)．答案A,B,C均不對3．?dāng)?shù)組A［５］［６］的每個元素占5個單元，將其按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，那么元素A［５，５］的地址為(A)A.1140 B.1145C.1120 D.11254.二維數(shù)組A［15］［20］采用按行為主序的存儲方式，每個元素占4個存儲單元，假設(shè)A［0］［0］的存儲地址為300，那么A［10］［10］的地址為〔D〕A.700 B.1120C.1180 D.11405．寫出廣義表操作的結(jié)果：GetTail【GetHead【GetTail【((a,b),(x,y))】】】===(y)。5.取出廣義表A=(x,(a,b,c,d))中原子x的函數(shù)是___head(A)____。7.以下各三元組表分別表示一個稀疏矩陣，試寫出它們的稀疏矩陣。ijv7661472183594276537318、設(shè)有一個10階的對稱矩陣A[10][10]，采用壓縮存儲方式按行將矩陣中下三角局部的元素存入一維數(shù)組B[]中，A[0][0]存入B[0]中，那么A[8][5]在B[]中〔C〕位置。A．32B．33C．41D．659、假設(shè)有100行200列的二維數(shù)組a[100][200]以列序?yàn)橹餍蝽樞虼鎯?，其基地址?0000，每個元素占2個存儲單元，那么第45行第67列的元素a[44][66]的存儲地址為23288。10、廣義表L=〔〔〔〔a〕，b〕〕，〔〔〔〕，d〕，〔e，f〕〕〕，〔1〕寫出廣義表L的頭、尾；〔2〕計算L的深度；〔3〕畫出L的頭尾鏈表存儲結(jié)構(gòu)圖。11.設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角局部〔如以下列圖所示〕按行序存放在一維數(shù)組B中〔注：B下標(biāo)從0開始〕，求矩陣中任一元素ai,j(i≤j)和一維數(shù)組B中下標(biāo)k的對應(yīng)關(guān)系。解：對應(yīng)關(guān)系如下：

第6章二叉樹知識點(diǎn)：樹、二叉樹〔完全二叉樹〕、森林根本概念〔度、〕，存儲結(jié)構(gòu)，遍歷，轉(zhuǎn)換，線索1、設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非葉結(jié)點(diǎn)，那么B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有〔C〕個。A．n-1B．nC．n+1D．n+2一棵度為3的樹有2個度為1的結(jié)點(diǎn)，3個度為2的結(jié)點(diǎn)，4個度為3的結(jié)點(diǎn)，那么該樹中有_____12_______個葉子的結(jié)點(diǎn)。樹有三種常用的存儲結(jié)構(gòu)，即孩子鏈表法、孩子兄弟鏈表法和_____雙親表示法。4.把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是A。A.唯一的B.有多種C.有多種，但根結(jié)點(diǎn)都沒有左孩子D.有多種，但根結(jié)點(diǎn)都沒有右孩子5、假設(shè)一棵二叉樹中度為2的結(jié)點(diǎn)數(shù)是10，那么葉子結(jié)點(diǎn)數(shù)為11個。10、3個結(jié)點(diǎn)可構(gòu)成2棵不同形態(tài)的樹。5棵不同形態(tài)的二叉樹。6.深度為6〔根的層次為1〕的二叉樹至多有〔④〕結(jié)點(diǎn)。64②32③31④637.將含100個結(jié)點(diǎn)的完全二叉樹從根這一層開始，每層上從左到右依次對結(jié)點(diǎn)編號，根結(jié)點(diǎn)的編號為1。編號為49的結(jié)點(diǎn)X的雙親編號為〔①〕①24②25③23④無法確定8.設(shè)一棵完全二叉樹具有1000個結(jié)點(diǎn)，那么此完全二叉樹有500個葉子結(jié)點(diǎn)；有499個度為2的結(jié)點(diǎn)，有1個度為1的結(jié)點(diǎn)。9.一棵具有２５７個結(jié)點(diǎn)的完全二叉樹，它的深度為9。10、完全二叉樹的第8層有8個結(jié)點(diǎn)，那么其葉子結(jié)點(diǎn)數(shù)是68。

11.在完全的二叉樹中，假設(shè)一個結(jié)點(diǎn)沒有A，那么它必定是葉結(jié)點(diǎn)。A.左子結(jié)點(diǎn)B.右子結(jié)點(diǎn)C.左子結(jié)點(diǎn)或者沒有右子結(jié)點(diǎn)D.兄弟

12.某二叉樹的先序序列和后序序列正好相同，那么該二叉樹一定是(.A)的二叉樹。A.空或只有一個結(jié)點(diǎn) B.高度等于其結(jié)點(diǎn)數(shù)C.任一結(jié)點(diǎn)無左孩子 D.任一結(jié)點(diǎn)無右孩子13.在有n個結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個數(shù)為(A)A.n-1 B.2n-1C.n+1 D.2n+114.一棵左右子樹均不空的二叉樹在先序線索化后，其空指針域數(shù)為(.B)A.0 B.1C.2 D.不確定15.DFS算法的時間復(fù)雜度為(C)A.O(n) B.O(n3)C.O(n2) D.O(n+e)16、有n個葉子結(jié)點(diǎn)的哈夫曼〔Huffman〕樹所具有的結(jié)點(diǎn)數(shù)為

2n-117.判斷線索二叉樹中某結(jié)點(diǎn)指針P所指結(jié)點(diǎn)有左孩子的條件是___P->ltag=1____。18、二叉樹在線索化后，仍不能有效求解的問題是〔

D〕。A.先序線索二叉樹中求先序后繼

B.

中序線索二叉樹中求中序后繼

C.中序線索二叉樹中求中序前驅(qū)

D.

后序線索二叉樹中求后序后繼

19、將以下列圖中的樹用孩子-兄弟鏈表來表示?！?〕畫出該二叉鏈表；〔2〕對該二叉鏈表進(jìn)行何種遍歷方式可實(shí)現(xiàn)樹的后根遍歷？寫出后根序列。求出以下列圖的一棵最小生成樹。21.指出下面函數(shù)FS的功能。其中，p指向先序線索二叉樹的某個結(jié)點(diǎn)。

typedefenum{LINK，THERAD}flag;

typedefcharDataType;

typedefstructnode{

DataTypedata;

flagltag，rtag;

structnode*lchild，*rchild;

}BinNode;

BinNode*FS(BinNode*p)

{

if(p->ltag==LINK)

returnp->lchild;

else

returnp->rchild;

}函數(shù)功能：在先序線索二叉樹中查找某結(jié)點(diǎn)的后繼。22.給定二叉樹的兩種遍歷序列，分別是：中序遍歷序列：DCBGEAHFIJK；后序遍歷序列：DCEGBFHKJIA。請畫出該樹。畫出與〔1〕求得的二叉樹對應(yīng)的森林。23.假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為abcdefgh0.070.190.020.060.320.030.210.10要求：為這8個字母設(shè)計哈夫曼編碼，并畫出哈夫曼樹。求該哈夫曼樹的帶權(quán)路徑長度。24．樹的后根遍歷方法是：假設(shè)樹非空那么〔1〕依據(jù)次后根遍歷根的各個子樹Ｔ１，Ｔ２，……Ｔm;〔2〕訪問根結(jié)點(diǎn)。對以下列圖所示的樹，用后根遍歷方法進(jìn)行遍歷，請寫出遍歷所得到的結(jié)點(diǎn)訪問序列。AABACADAEAFAGAHAIJKA25.假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。請畫出該樹。畫出與〔1〕求得的二叉樹對應(yīng)的森林。26.一樹的雙親表示法如下，其中各兄弟結(jié)點(diǎn)是依次出現(xiàn)的，畫出該樹及對應(yīng)的二叉樹。123456789101112131415dataABCDEFGHIJKLMNOparent0111223344566781.計算二叉樹的深度的算法IntdeepTree(p)//P為指向二叉樹之根{If(p==NULL)returnt;ElseIf(deepTree(p->Lchild)>deepTree(p->Rchild))ReturndeepTree(p->Lchild)+1;ElseReturndeepTree(p->Rchild)+1;}2、讀程序

二叉樹以二叉鏈表作為存儲結(jié)構(gòu)，其定義如下：

Typedef

struct

Node{char

data;

Struct

Node

*lc,*rc;

/*lc,rc分別指向左，右子樹*/

}BiTNode,*BiTree;

Int

n=0;

二叉樹如右圖，根的地址為root，請給出：

〔1〕

以下函數(shù)的功能

〔2〕

調(diào)用語句prek(root,5);輸出結(jié)果是什么？

Void

prek(BiTree

T,int

k)

{if(T&&n<k)

{prek(T->lc,k);

Prek(T->rc,k);

N++;printf(“%c〞,T->data);

}

}

3、編寫遞歸算法，計算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。4．設(shè)二叉樹以二叉鏈表為存儲結(jié)構(gòu)，結(jié)點(diǎn)結(jié)構(gòu)為lchild|data|rchild。設(shè)計一個算法，求在前根序列中處于第k個位置的結(jié)點(diǎn)Bitreptrsearch(bitreptrt,intk){if(t!=null){count++;if(count==k)return(t);else{search(t->lchild,k);search(t->rchild,k);}}}5.以線索鏈表作為存儲結(jié)構(gòu)，寫出后序線索樹中查找*p的后序前驅(qū)的算法。

第七章圖知識點(diǎn)：根本概念〔度、完全圖、連通子圖、生成樹、最小生成樹〕，圖的存儲〔鄰接矩陣、鄰接表〕，圖的遍歷，最小生成樹，拓?fù)渑判?，最短路徑，關(guān)鍵路徑1求最短路徑的DIJKSTRA算法的時間復(fù)雜度為(C)A.O(n) B.O(n+e)C.O(n2) D.O(n×e)2.有向圖用鄰接矩陣表示后，頂點(diǎn)i的入度等于鄰接矩陣中第i列的非零元個數(shù)。(T)3.有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)數(shù)一定相同。(T)4.圖G的拓?fù)湫蛄形ㄒ?，那么其弧?shù)必為n-1(其中n為G的頂點(diǎn)數(shù))。(F)5.在一個圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的C倍。A．1/2B.1C.2D.46.在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的B倍。A．1/2B.1C.2D.47.圖的鄰接表如以下列圖1所示，根據(jù)算法，那么從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是DA．0132B.0231C.0321D.01238．有n個頂點(diǎn)的強(qiáng)連通有向圖G至少有n條弧。9、設(shè)有向圖有n個頂點(diǎn)和e條邊，采用鄰接表作為其存儲表示，在進(jìn)行拓?fù)渑判驎r，總的計算時間為〔B〕。A．O〔nlog2e〕B．O〔n+e〕C．O(ne)D．O(n2)10、求最短路徑的FLOYD算法的時間復(fù)雜度為〔D〕。

A.O(n)

B.O(n+e)

C.O(n2)

D.O(n3)

11、假設(shè)要求一個稀疏圖G的最小生成樹，最好用A算法來求解。A．克魯斯卡爾(Kruskal)B.普里姆(Prim)C．迪杰斯特拉〔Dijkstra〕D.以上均可，沒有區(qū)別12設(shè)有一個無向圖G=〔V，E〕和G’=〔V’，E’〕如果G’為G的生成樹，那么下面不正確的說法是〔②〕①G’為G的子圖②G’為G的邊連通分量③G’為G的極小連通子圖且V’=V④G’為G的一個無環(huán)子圖13一個有向圖G中假設(shè)有弧<vi,vj>、<vj,vk>和<vi,vk>,那么在圖G的拓?fù)湫蛄兄?，頂點(diǎn)vi,vj和vk的相對位置為___i,j,k____。14.有8個結(jié)點(diǎn)的有向圖最多有56條邊。15.用普里姆(Prim)算法求具有n個頂點(diǎn)e條邊的圖的最小生成樹的時間復(fù)雜度為O(n2)；用克魯斯卡爾(Kruskal)算法的時間復(fù)雜度是O(elog2e)?！睞〕16用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時，通常是采用來實(shí)現(xiàn)算法的。(A)．隊列(B).棧(C).樹(D).圖17.用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時，通常是采用C來實(shí)現(xiàn)算法的。A．樹B.隊列C.棧D.圖1、請對以下列圖的無向帶權(quán)圖：寫出它的鄰接矩陣；寫出它的鄰接表；設(shè)起點(diǎn)為a，按普里姆算法或克魯斯卡爾算法求其最小生成樹。 2.圖的鄰接矩陣，根據(jù)算法，分別求從頂點(diǎn)0出發(fā)按深度和廣度優(yōu)先遍歷的結(jié)點(diǎn)序列。解：按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是0134256；按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是0123465。3.對于以下列圖所示的AOE網(wǎng)絡(luò)，計算各活動弧的e(ai)和l(aj)的函數(shù)值，各事件〔頂點(diǎn)〕的ve(vi)和vl(vj)函數(shù)值，列出各條關(guān)鍵路徑。v2v4v2v4v1v5v3v616211114336191865求最小生成樹，兩種方案5.某有向圖的鄰接矩陣如右圖所示，要求：確定圖中每個頂點(diǎn)的入/出度；畫出該圖；畫出該圖的鄰接表畫出該圖的逆鄰接表。6利用Dijkstra算法求圖中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)。第8章查找知識點(diǎn)：折半查找過程，堆概念，二叉排序樹，哈希查找，平衡二叉樹。1.對有18個元素的有序表作二分查找，那么查找A［3］的比較序列的下標(biāo)依次為(D)A.1，2，3 B.9，5，2，3C.9，5，3 D.9，4，2，32、對表長為900的索引順序表進(jìn)行分塊查找，假設(shè)每一塊的長度均為15，且以順序查找確定塊，那么在各記錄的查找概率均相等的情況下，其查找成功的平均查找長度為__38.5___。3.在表長為ｎ的鏈表中進(jìn)行線性查找，它的平均查找長度為(ｎ＋１)/２。4.在各種查找方法中，平均查找長度與結(jié)點(diǎn)個數(shù)n無關(guān)的查找方法是散列查找?！玻谩?．在對有6400個記錄的索引順序表進(jìn)行查找，最理想的塊長為.(Ａ).64(Ｂ).100(Ｃ)80(Ｄ)log264006、在平衡二叉樹中插入一個結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡點(diǎn)為A，并A的左孩子的平衡因子為-1，右孩子的平衡因子為0，那么做〔B〕型調(diào)整以使其平衡。

A.LL

B.LR

C.RL

D.RR

7、〕假定對有序表：〔3，4，5，7，24，30，42，54，63，72，87，95〕進(jìn)行折半查找。畫出描述折半查找過程的判定樹；假設(shè)查找元素54，需依次與哪些元素比較？假設(shè)查找元素90，需依次與哪些元素比較？假定每個元素的查找概率相等，求查找成功時的平均查找長度。8、設(shè)哈希〔Hash〕表的地址范圍為0～15，哈希函數(shù)為：H〔Key〕＝Keymod13。Key為關(guān)鍵字，用線性探測法再散列法處理沖突，輸入關(guān)鍵字序列：〔10，24，32，17，31，30，46，48，41，65，49〕造出Hash表，試答復(fù)以下問題：畫出哈希表的示意圖；假設(shè)查找關(guān)鍵字30，需要依次與哪些關(guān)鍵字進(jìn)行比較？計算填充因子；假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。9.長度為12的表：〔Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec〕試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。10．在一棵空的二叉查找樹中依次插入關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，請畫出所得到的二叉查找樹，并求出其平均查找長度。11、有一個40000項(xiàng)的表,要采用等分區(qū)間順序查找的索引(分塊)查找法,問:(1)每塊理想長度是多少?(2)最理想的塊數(shù)是多少?(3)計算平均查找長度ASL。(4)假設(shè)每塊長度為100,計算ASL。12.下面是將鍵值為x的結(jié)點(diǎn)插入到二叉排序樹中的算法，請在劃線處填上適當(dāng)?shù)膬?nèi)容。typedefstructpnode{intkey;structpnode*left,*right;}pnode;voidsearchinsert(intx,pnodet)/*t為二叉排序樹根結(jié)點(diǎn)的指針*／{if(){p=malloc(size);p->key=x;p->lchild=null;p->rchild=null;t=p;}elseif(x<t->key)searchinsert(x,t->lchild)else_________;}13．設(shè)n個元素的有序表為Ｒ，Ｋ為一個給定的值，二分查找算法如下：intbinsearch(sqlistR,keytypeK){j=1;h=n;suc=0;while((j<=h)&&(!suc)){mid=(j+h)/2;switch{caseK=R[mid].key:suc=1;break;caseK<R[mid].key:h=mid-1;break;caseK>R[mid].key:j=mid+1}}if(suc)return(mid);elsereturn(0);} 將上述算法中劃線語句改為：K<R[mid].key:h=mid.〔1〕改動后，算法能否正常工作？請說明原因?！?〕假設(shè)算法不能正常工作，給出一個查找序列和一個出錯情況的查找鍵值；假設(shè)能正常工作，請給出一個查找序列和查找某個鍵值的比較次數(shù)。14.從空樹起，依次插入關(guān)鍵字37，50，42，18，12，56，30，23，構(gòu)造一棵二叉排序樹。畫出該二叉排序樹。畫出從〔1〕所得樹中刪除關(guān)鍵字為37的結(jié)點(diǎn)之后的二叉排序樹。15.某哈希表的裝載因子小于1，哈希函數(shù)H(key)為關(guān)鍵字〔標(biāo)識符〕的第一個字母在字母表中的序號，處理沖突的方法為線性探測開放定址法。試編寫一個按第一個字母的順序輸出哈希表中所有關(guān)鍵字的算法。第九章排序知識點(diǎn)：堆的判定，排序算法的穩(wěn)定性，各類排序算法執(zhí)行過程、復(fù)雜性分析，1.以下關(guān)鍵字序列中，Ｄ是堆。Ａ.16,72,31,23,94,53Ｂ.94,23,31,72,16,53Ｃ.16,53,23,94，31,72Ｄ.16,23,53,31,94,722以下排序方法中穩(wěn)定的是：Ｃ.Ａ.希爾排序Ｂ.快速排序Ｃ.歸并排序Ｄ.堆排序3.設(shè)表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對其進(jìn)行〔按遞增排序〕，冒泡排序最省時間，快速排序最費(fèi)時間。4.堆是一個鍵值序列{k1,k2,…,kn},對i=1,2,…,|_n/2_|,滿足()①ki≤k2i≤k2i+1②ki<k2i+1<k2i③ki≤k2i且ki≤k2i+1(2i+1≤n)④ki≤k2i