數據結構真題分類整理new

1、第一章 概述 真題16.下列程序段的時間復雜度為_。for(i=1；i=n；i+)for(j=1；j=n；j+)for(k=1；k=n；k+)s=i+j+k；17.在數據結構中，各個結點按邏輯關系互相纏繞，任意兩個結點可以鄰接的結構稱為_。16.下列程序段的時間復雜度為_。i=0；s=0；while（in） i+；s=s+i；17.數據的邏輯結構被分為集合結構、_、樹形結構和圖狀結構4種。1.數據的不可分割的最小標識單位是（）A.數據項 B.數據記錄 C.數據元素 D.數據變量2. for（i=0；im；i+）for（j=0；jt；j+）cij=0；for（i=0；im；i+）for（j=0；

2、jt；j+）for（k=0；kn；k+）cij=cij+aik*bkj；上列程序的時間復雜度為（） A.O(m+nt) B.O(m+n+t) C.O(mnt) D.O(mt+n)16.在數據結構中，數據的存儲結構有順序存儲方式、鏈式存儲方式、_和散列存儲方式等四種。17.作為一個算法輸入的數據所含數據元素的數目，或與此數目有關的其他參數，稱為_。 1.從邏輯上可以把數據結構分為（） A.動態(tài)結構、靜態(tài)結構 B.順序結構、鏈式結構 C.線性結構、非線性結構 D.初等結構、構造型結構2.關于算法的描述，不正確的是（） A.算法最終必須由計算機程序實現 B.所謂時間復雜度是指最壞情況下，估算算法執(zhí)行

3、時間的一個上界 C.健壯的算法不會因非法的輸入數據而出現莫名其妙的狀態(tài) D.算法的優(yōu)劣與算法描述語言無關16.在任何問題中，數據元素都不是孤立的，它們之間總存在某種關系，通常稱這種關系為_。 17.存儲結點之間通常有四種基本存儲方式，即順序存儲方式、索引存儲方式、_和散列存儲方式。1.在數據結構中，數據的基本單位是( ) A.數據項 B.數據元素 C.數據對象 D.數據文件2. k=1; for（i=0；in；i+）for（j=0；jn；j+） Aij=k+；上述程序段的時間復雜度為( ) A.O（n2） B.O（n） C.O（2n） D.O（1）16.數據的邏輯結構通常包括集合、線性結構、_

4、和圖狀結構。1.在數據結構中，從邏輯上可以把數據結構分成( )A.線性結構和非線性結構 B.緊湊結構和非緊湊結構C.動態(tài)結構和靜態(tài)結構 D.內部結構和外部結構2.for（i=0；im；i+）for（j=0；jn；j+）Aij=i*j；上面算法的時間復雜度為( ) A.O(m2) B.O(n2) C.O(mn) D.O(m+n）16.如果操作不改變原邏輯結構的“值”，而只是從中提取某些信息作為運算結果，則稱該類運算為_ _型運算。3從邏輯關系來看，數據元素的直接前驅為0個或1個的數據結構只能是（ ）A線性結構 B.樹形結構 C.線性結構和樹型結構 D.線性結構和圖狀結構16在數據結構中，各個結點

5、按邏輯關系互相纏繞，任意兩個結點可以鄰接的結構稱為_。17每個存儲結點只含一個數據元素，所有存儲結點連續(xù)存放。此外增設一個索引表，索引表中的索引指示各存儲結點的存儲位置或位置區(qū)間端點。按這種方式組織起來的存儲結構稱為_。1.數據的基本單位是（）A.數據項 B.數據類型 C.數據元素 D.數據變量2.下列程序的時間復雜度為（）i=0；s=0；while（sn） i+；s=s+i；A.O（） B.O（） C.O（n） D.O（n2）16.在數據結構中，數據的邏輯結構分為集合、_、樹形結構和圖狀結構等四類。17.通常從正確性、易讀性、_和高效率等4個方面評價算法（包括程序）的質量。1.數據結構中所定

6、義的數據元素，是用于表示數據的（）A.最小單位 B.最大單位 C.基本單位 D.不可分割的單位2.數據的四種基本存儲結構是指（）A.順序存儲結構、索引存儲結構、直接存儲結構、倒排存儲結構B順序存儲結構、索引存儲結構、鏈式存儲結構、散列存儲結構C順序存儲結構、非順序存儲結構、指針存儲結構、樹型存儲結構D.順序存儲結構、鏈式存儲結構、樹型存儲結構、圖型存儲結構16.數據表示和_是程序設計者所要考慮的兩項基本任務。17.一個算法通常可從正確性、易讀性、健壯性和_等四個方面評價、分析。1.若要描述數據處理的變化過程，其正確的次序應為( )A.處理要求、基本運算和運算、算法 B.處理要求、算法、基本運算

7、和運算C.基本運算和運算、處理要求、算法 D.算法、處理要求、基本運算和運算2.從運算類型角度考慮，屬于引用型的運算是( )A.插入、刪除B.刪除、修改 C.查找、讀取D.查找、刪除16.算法通常可分為程序、偽語言算法和_三種類型。17.時間復雜性描述量級中，若某算法達到_量級，則該算法通常是不可計算的。1.數據的四種基本邏輯結構是指( )A.數組、鏈表、樹、圖形結構 B.線性表、鏈表、棧隊列、數組廣義表C.線性結構、鏈表、樹、圖形結構 D.集合、線性結構、樹、圖形結構2.數據結構中，通常采用兩種方法衡量算法的時間復雜性，即( )A.最大時間復雜性和最小時間復雜性B.最好時間復雜性和最壞時間復

8、雜性C.部分時間復雜性和總體時間復雜性 D.平均時間復雜性和最壞時間復雜性16.根據不同的描述方式，對數據的操作運算通?？煞譃榧庸ば瓦\算和_兩種基本類型。17.數據結構中的算法，通常采用最壞時間復雜度和_兩種方法衡量其效率。1.要將現實生活中的數據轉化為計算機所能表示的形式，其轉化過程依次為（）A.邏輯結構、存儲結構、機外表示B.存儲結構、邏輯結構、機外表示C.機外表示、邏輯結構、存儲結構D.機外表示、存儲結構、邏輯結構2.若評價算法的時間復雜性，比較對數階量級與線性階量級，通常（）A.對數階量級復雜性大于線性階量級 B.對數階量級復雜性小于線性階量級C.對數階量級復雜性等于線性階量級 D.兩

9、者之間無法比較16.從數據結構的觀點，數據通?？煞譃槿齻€層次，即：數據、數據元素和_。17.用程序設計語言、偽程序設計語言并混合自然語言描述的算法稱為_算法。1下列數據組織形式中，（）的各個結點可以任意鄰接。A集合B樹形結構 C線性結構D圖狀結構2設某二維數組A1.n，1.n，則在該數組中用順序查找法查找一個元素的時間復雜性的量級為（AO（log2n）BO(n) CO(nlog2n)DO(n2)16下列程序段的時間復雜性量級是_。for (i=1;in; i+) for (j=1; jnext=pnextnext B.p=pnext C.p=pnextnext D.pnext=p5.向一個棧頂

10、指針為hs的鏈棧中插入一個*s結點時，應執(zhí)行的操作為（） A.hsnext=s; B.snext=hs;hs=s; C.snext=hsnext;hsnext=s; D.snext=hs;hs=hsnext;6.設循環(huán)隊列的元素存放在一維數組Q030中，隊列非空時，front指示隊頭元素的前一個位置，rear指示隊尾元素。如果隊列中元素的個數為11，front的值為25，則rear應指向的元素是（） A.Q4 B.Q5 C.Q14 D.Q157.定義二維數組A18，010，起始地址為LOC，每個元素占2L個存儲單元，在以行序為主序的存儲方式下，某數據元素的地址為LOC+50L，則在以列序為主序

11、的存儲方式下，該元素的存儲地址為（） A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L18.在雙鏈表中，存儲一個結點有三個域，一個是數據域，另兩個是指針域，分別指向_和_。 19.在有n個元素的鏈隊列中，入隊和出隊操作的時間復雜度分別為_和_。 20.在棧結構中，允許插入的一端稱為_;在隊列結構中，允許插入的一端稱為_。 21.在循環(huán)隊列中，存儲空間為0n-1。設隊頭指針front指向隊頭元素前一個空閑元素，隊尾指針指向隊尾元素，那么其隊空標志為rear=front，隊滿標志為_。 3.在單鏈表中，存儲每個結點需要有兩個域，一個是數據域，另一個是指針域，指針域指向

12、該結點的（） A.直接前趨 B.直接后繼 C.開始結點 D.終端結點4.將兩個各有n個元素的有序表合并成一個有序表，其最少的比較次數為（） A.n B.2n-1 C.2n D.n25.棧和隊列共同具有的特點是（）A.都是先進后出 B.都是先進先出 C.只允許在端點進行操作運算 D.既能先進先出，也能先進后出6.若用一個有6個單元的數組來實現循環(huán)隊列，rear和front的初值分別為0和3。則從隊列中刪除一個元素，再添加兩個元素后，rear和front的值分別為（） A.1和5 B.2和4 C.4和2 D.5和17.數組A0.50.5的每個元素占5個字節(jié)，將其以列為主序存儲在起始地址為1000的

13、內存單元中，則元素A55的地址是（） A.1175 B.1180 C.1205 D.121018.在一個長度為n的順序表中第i個元素（1in）之前插入一個元素時，需向后移動_個元素。24.兩個串是相等的，當且僅當兩個串的長度相等且_的字符都相同。 34.設兩個數據元素均為整型數據的線性表A=(a1，a2，an)和B=(b1，b2，bm)。若n=m且ai=bi（i=1，2,，n）則認為A=B；若ai=bi（i=1，2,，j）且aj+1BJ+1，（Jnext-next!=h) p=p-next;p-next=h; 后（其中，p-next為p指向結點的指針域），則( )A.p-next指針指向鏈尾結

14、點 B.h指向鏈尾結點 C.刪除鏈尾前面的結點 D.刪除鏈尾結點 5.設順序表有19個元素，第一個元素的地址為200，且每個元素占3個字節(jié)，則第14個元素的存儲地址為( ) A.236 B.239 C.242 D.2456.一個棧的入棧序列是a,b,c,d,e，則棧的輸出序列不可能是( )A.dceab B.decba C.edcba D.abcde7.元素大小為1個單元，容量為n個單元的非空順序棧中，以地址高端為棧底，以top作為棧頂指針，則出棧處理后，top的值應修改為( ) A.top=top B.top=n-1 C.top=top-1 D.top=top+117.設雙鏈表中結點的前趨指

15、針和后繼指針的域名分別為t1和r1，指針s指向雙鏈表中的一個結點（該結點既非頭結點，也非尾結點），則刪除s指針所指向結點的操作為“s-tl-r1=s-r1；”和“_”。32.如題32圖所示，在棧的輸入端有6個元素，順序為A，B，C，D，E，F。能否在棧的輸出端得到序列DCFEBA及EDBFCA？若能，給出棧操作的過程，若不能，簡述其理由。 35.某帶頭結點的單鏈表的結點結構說明如下： typedef struct node1 int data; struct node1 *next node；試設計一個算法int copy(node *head1, node *head2)，將以head1為頭

16、指針的單鏈表復制到一個不帶頭結點且以head2為頭指針的單鏈表中。3.設順序表有9個元素，則在第3個元素前插入一個元素所需移動元素的個數為( )A.5 B.6 C.7 D.94.設p為指向雙向循環(huán)鏈表中某個結點的指針，p所指向的結點的兩個鏈域分別用pllink和prlink表示，則同樣表示p指針所指向結點的表達式是( )A.pllink B.prlink C.pllinkllink D.pllinkrlink5.一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的存儲地址是( )A. 110 B. 108 C. 100 D. 1206.設有一個棧，按A、B、C、D的順序進棧

17、，則可能為出棧序列的是( )A.DCBA B.CDAB C.DBAC D.DCAB7.在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top為棧頂指針，則當做出棧處理時，top變化為( )A.top+ B.top- C.top不變 D.top=017.設有指針head指向不帶表頭結點的單鏈表，用next表示結點的一個鏈域，指針p指向與鏈表中結點同類型的一個新結點?，F要將指針p指向的結點插入表中，使之成為第一個結點，則所需的操作為“pnext=head；”和“_”。18.單鏈表中邏輯上相鄰的兩個元素在物理位置上_相鄰。19.在一個長度為n的數組中刪除第i個元素（1in）時，需

18、要向前移動的元素的個數是_。31.如題31圖所示，輸入元素為A，B，C，在棧的輸出端得到一個輸出序列ABC，試寫出在棧的輸入端三個可能的輸入序列。34.下面程序段為刪除循環(huán)鏈表中第一個info域值等于x的結點，請?zhí)钌铣绦蛑腥鄙俚牟糠?。循環(huán)鏈表的結構如題34圖所示：struct node int info;struct node *link; int Delete (struct node *head, int x) struct node *p, *q; /*p:當前處理的結點；q：p的前驅結點*/ if (! head ) return (0);if (headlink =head) if

19、(headinfo=x) free (head); head=NULL； return (x) return (0); p=head; q=head; while (qlink!=head) q=(1) ; while (plink!=head) if (pinfo=x) (2) ; if (p=head) head=(3) ; free (p);return (x); else q=p ;（4） ; return (0);1關于棧和隊列的說法中正確的是（ ）A棧和隊列都是線性結構 B.棧是線性結構，隊列不是線性結構 C.棧不是線性結構，隊列是線性結構 D.棧和隊列都不是線性結構2關于存儲相同

20、數據元素的說法中正確的是（ ）A順序存儲比鏈式存儲少占空間 B.順序存儲比鏈式存儲多占空間C.順序存儲和鏈式存儲都要求占用整塊存儲空間 D.鏈式存儲比順序存儲難于擴充空間3從邏輯關系來看，數據元素的直接前驅為0個或1個的數據結構只能是（ ）A線性結構 B.樹形結構 C.線性結構和樹型結構 D.線性結構和圖狀結構4已知一個單鏈表中，指針q指向指針p的前趨結點，若在指針q所指結點和指針p所指結點之間插入指針s所指結點，則需執(zhí)行（ ）Aqnext=s；pnext=s；B.qnext=s；snext=p； C.qnext=s；qnext=p；D.qnext=s；snext=q；5在長度為n的線性表中刪

21、除一個指針p所指結點的時間復雜度是（ ）AO(n) B.O(1) C.O(log2n) D.O(n2)6設一個棧的輸入序列是a,b,c,d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現的是（ ）Aa，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b7關于串的敘述中，正確的是（ ）A空串是只含有零個字符的串 B.空串是只含有空格字符的串C.空串是含有零個字符或含有空格字符的串 D.串是含有一個或多個字符的有窮序列8在具有m個單元的循環(huán)隊列中，隊頭指針為front，隊尾指針為rear，則隊滿的條件是（ ）Afront=rear B.(front+1)%m=rear C.

22、rear+1=front D.(rear+1)%m=front9設有二維數組Ann表示如下： ， 則Aii（0in-1）的值為（ ）Ai*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2 D.i2/218在順序表上讀表元算法的時間復雜度為_。19雙鏈表中前驅指針為prior，后繼指針為next，在指針P所指結點前插入指針S所指的結點，需執(zhí)行下列語句：Snext=P;Sprior=Pprior;Pprior=S;_;20設數組A0.80.8的起始元素位置為a，每個元素占2 L個存儲單元，按行序為主序存儲。若元素Aij的存儲位置為a+66 L，則元素Aji的存儲位置為_。29

23、有一字符串序列為5*-x-y/x+2，利用棧的運算將其輸出結果變?yōu)?x-*yx+/-2，試寫出該操作的入棧和出棧過程（采用push(a)表示a入棧，pop(a)表示a出棧）。34設單鏈表的結點結構如下：struct nodedatatype data;struct node*next;試編寫一個函數int count(struct node *head,datatype x)統(tǒng)計單鏈表中數據域為x的結點個數。3.若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則最節(jié)省運算時間的存儲方式是（）A.單鏈表 B.僅有頭指針的單循環(huán)鏈表 C.雙鏈表 D.僅有尾指針的單循環(huán)鏈表

24、4.從一個長度為n的順序表中刪除第i個元素（1in）時，需向前移動的元素的個數是（）A.n-i B.n-i+1 C.n-i-1 D.i5.順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數組，則元素e進棧操作的主要語句為（）A.s.elemtop=e；s.top=s.top+1；B.s.elemtop+1=e；s.top=s.top+1；C.s.top=s.top+1；s.elemtop+1=e； D.s.top=s.top+1； s.elemtop=e；6.循環(huán)隊列sq中，用數組elem025存放數據元素，sq.front指示隊頭元素的前一個位置，sq.rear指示隊尾

25、元素的當前位置，設當前sq.front為20，sq.rear為12，則當前隊列中的元素個數為（）A.8 B.16 C.17 D.187.設有一個10階的對稱矩陣A，采用壓縮存儲方式以行序為主序存儲，a00為第一個元素，其存儲地址為0，每個元素占有1個存儲地址空間，則a45的地址為（）A.13 B.35 C.17 D.3618.順序表的存儲密度為_，而鏈表的存儲密度為_。19.對于棧只能在_插入和刪除元素。20.在循環(huán)隊列中，存儲空間為0n-1,設隊頭指針front指向隊頭元素前一個空閑元素，隊尾指針指向隊尾元素，那么隊滿標志為front=(rear+1)%n，隊空標志為_。3.對于長度為n的順

26、序表執(zhí)行刪除操作，則其結點的移動次數（）A.最少為0，最多為n B.最少為1，最多為n C.最少為0，最多為n-1 D.最少為1，最多為n-14.在一個單鏈表中，若p所指結點是q所指結點的前驅結點，則刪除結點q的正確操作是（A. p-next=q B. p-next=q-next C. p=q-next D. p-next=q-next-next5.有關棧的描述，正確的是（）A.棧是一種先進先出的特殊的線性表B.只能從棧頂執(zhí)行插入、刪除操作C.只能從棧頂執(zhí)行插入、棧底執(zhí)行刪除D.棧頂和棧底均可執(zhí)行插入、刪除操作6.二維數組A1020采用按行為主序的存儲方式，每個元素占4個存儲單元，若A00的存

27、儲地址為300，則A1010的地址為（）A.700 B.1120 C.1180 D.114018.對長度為n的順序表執(zhí)行刪除操作，其刪除算法在最壞情況下的時間復雜性為_。19.串是一種特殊的線性表，串常見的存儲結構有順序存儲和_兩種方式。20.我們通常把隊列中允許插入的一端稱為_。21.二維數組在機器級的具體實現，通常均采用_存儲結構。34.試編寫一個函數，以讀取單鏈表的第i個元素。3.若在長度為n的順序表中插入一個結點，則其結點的移動次數( )A.最少為0，最多為nB.最少為1，最多為n C.最少為0，最多為n+1D.最少為1，最多為n+14.在一個單鏈表中，若p所指結點是q所指結點的前驅結

28、點，則在結點p、q之間插入結點s的正確操作是( )A.s-next=q；p-next=s-next B.p-next=q；p-next=s C.s-next=q-next；p-next=s D.s-next=q-next；p-next=s-next5.若有一串數字5、6、7、8入棧，則其不可能的輸出序列為( )A.5、6、7、8B.8、7、6、5 C.8、7、5、6D.5、6、8、76.FORTRAN語言對數組元素的存放方式通常采用( )A.按行為主的存儲結構B.按列為主的存儲結構 C.按行或列為主的存儲結構D.按行和列為主的存儲結構18.對順序表執(zhí)行刪除操作，其刪除算法的平均時間復雜性為_。

29、19.若head表示循環(huán)鏈表的頭指針，t表示尾結點，則頭指針head與尾結點t之間的關系可表示為_。20.我們通常把隊列中允許刪除的一端稱為_。21.二維數組A56采用按列為主序的存儲方式，每個元素占3個存儲單元，若A00的存儲地址是100，則A43的存儲地址是_。34.若循環(huán)單鏈表長度大于1，p為指向鏈表中某結點的指針，試編寫一算法刪除p結點的前驅結點。3.下列關于線性表的敘述中，不正確的是( )A.線性表是n個結點的有窮序列 B.線性表可以為空表C.線性表的每一個結點有且僅有一個前趨和一個后繼 D.線性表結點間的邏輯關系是1:1的聯(lián)系4.在一個單鏈表中，若p所指結點不是最后結點，則刪除p所

30、指結點的后繼結點的正確操作是( )A.p=p-next B.p-next=p-next C.p-next=p-next-next D.p-next=p5.棧和隊列( )A.共同之處在于二者都是先進先出的特殊的線性表 B.共同之處在于二者都是先進后出的特殊的線性表C.共同之處在于二者都只允許在頂端執(zhí)行刪除操作 D.沒有共同之處6.二維數組A56采用按列為主序的存儲方式，每個元素占3個存儲單元，若A00的存儲地址是100，則A43的存儲地址是( )A.127 B.142 C.150 D.15718.判斷帶頭結點head的單鏈表為空的條件是_。19.若順序表每個元素長度均為5，其中第一個元素的存儲地

31、址為30，則第6個元素的存儲地址為_。20.若front和rear分別表示循環(huán)隊列Q的頭指針和尾指針，m0表示該隊列的最大容量，則判斷循環(huán)隊列為滿的條件是_。21.對于順序存儲結構的二維數組，通常采用_兩種存放方式存儲數據元素。34.試編寫一算法，以完成在帶頭結點單鏈表L中第i個位置前插入元素X的操作。3.下列關于線性表的基本操作中，屬于加工型的操作是（）A.初始化、求表長度、插入操作B.初始化、插入、刪除操作C.求表長度、讀元素、定位操作D.定位、插入、刪除操作4.在一個單鏈表中，若p所指結點不是最后結點，s指向已生成的新結點，則在p之后插入s所指結點的正確操作是（）A.snext=pnex

32、t; pnext=s;B.pnext=snext; snext=p;C.snext=p; pnext=s;D.snext=pnext; p=s;5.若有三個字符的字符串序列執(zhí)行入棧操作，則其所有可能的輸出排列共有（）A.3種B.4種 C.5種D.6種6.C語言對數組元素的存放方式通常采用（）A.按行為主的存儲結構B.按列為主的存儲結構C.按行或列為主的存儲結構D.具體存儲結構無法確定18.對順序表執(zhí)行插入操作，其插入算法的平均時間復雜性為_。19.在具有n個單元、且采用順序存儲的循環(huán)隊列中，隊滿時共有_個元素。20.若front和rear分別表示循環(huán)隊列Q的頭指針和尾指針，m0表示該隊列的最大

33、容量，則循環(huán)隊列為空的條件是_。21.二維數組A1020采用按行為主序的存儲方式，每個元素占4個存儲單元，若A00的存儲地址為300，則A1010的地址為_。34.設某單鏈表中，存在多個結點其數據值均為D，試編寫一算法統(tǒng)計該類結點的個數。2設某二維數組A1.n，1.n，則在該數組中用順序查找法查找一個元素的時間復雜性的量級為（AO（log2n）BO(n) CO(nlog2n)DO(n2)3在線性表的下列存儲結構中，讀取元素花費時間最少的是（）A單鏈表B雙鏈表 C循環(huán)鏈表D順序表4將一個頭指針為p的單鏈表中的元素按與原單鏈表相反的次序存放，則下列算法段中的空白處應為（）q=NULL;while

34、(p!=NULL)（）p=q;Ar=q; q=p; p=p - next; q - next=r; Bq=p; r=q; p=p - next; q - next=r;Cr=q; p=p - next; q=p; q - next=r; Dq=p; p=p - next; r=q; q - next=r;5數組通常具有兩種基本運算，即（）A創(chuàng)建和刪除B索引和修改 C讀和寫D排序和查找17在順序存儲的線性表（a1,a2，an）中的第i (1in)個元素之前插入一個元素，則需向后移動_個元素。18在棧的順序實現中，若棧不滿，則進棧操作可以用下列算法片斷實現：_；sq - datasq - top=

35、x；19鏈隊列實際上是一個同時帶有頭指針和尾指針的單鏈表，尾指針指向該單鏈表的_。29如圖所示，輸入元素為A，B，C，在棧的輸出端得到一個輸出序列ABC，求出在棧的輸入端所有可能的輸入序列。（5分）34設某頭指針為head的單鏈表的結點結構說明如下：（6分）typedef struct node1int data;struct node1*nextnode;試設計一個算法void change (node*head),將該單鏈表中的元素按原單鏈表相反的次序重新存放，即第一個結點變成最后一個結點，第二個結點變?yōu)榈箶档诙€結點，如此等等。35編寫一個算法void DisplayQueue ()，產

36、生50個300600之間的隨機整數（調用一次MyRand()可產生一個符合條件的隨機整數）。每產生一個數據，若是奇數，則入隊列，若是偶數，則從隊首取出一個數據。要求：（8分）（1）隊列用鏈表實現；（2）每產生一個數顯示一次相應操作后的隊列當前狀態(tài)；（3）無需定義函數int MyRand()；（4）顯示隊列可調用函數void DisOne (QueptrTp lq)，也無需定義；（5）設鏈隊列定義為：typedef struct linked_queue int data; struct linked_queue*next;LqueueTp;typedef struct queueptr Lqu

37、eueTp *front, *rear;QueptrTp;QueptrTp lq;第四章 樹 真題2.某二叉樹的后根遍歷序列為dabec，中根遍歷序列為debac，則先根遍歷序列為（ ）A.acbed B.becab C.deabc D.cedba3.含有n個結點的二叉樹用二叉鏈表表示時，空指針域個數為( )A.n-1 B.n C.n+1 D.n+212.有關樹的敘述正確的是( )A.每一個內部結點至少有一個兄弟 B.每一個葉結點均有父結點C.有的樹沒有子樹 D.每個樹至少有一個根結點與一個葉結點。24.對于一棵滿二叉樹，若有m個葉子，則樹中結點數為_。30.已知一棵二叉樹的先根遍歷序列為AB

38、CDEGHF，中根遍歷序列為CBEDAGFH，畫出該二叉樹。34.二叉樹按二叉鏈表形式存儲，編寫一個算法判別給定的二叉樹是否為完全二叉樹。5.由帶權為9，2，5，7的四個葉子結點構造一棵哈夫曼樹，該樹的帶權路徑長度為（ ）A.23 B.37 C.44 D.4612.用n個值構造一棵二叉排序樹，它的最大高度為（ ）A.n/2 B. n C. n+1 D.log2n21.若滿二叉樹的結點數為n，則其高度為_。22.在一棵具有n個結點的完全二叉樹中，從樹根起，自上而下、從左到右地給所有結點編號。若編號為i的結點有父結點，那么其父結點的編號為_。23.深度為k的二叉樹，結點數最多有_個。24.某二叉樹

39、的后根遍歷為ABKCBPM，則該二叉樹的根為_。29.某通訊電文由A，B，C，D，E，F六個字符編碼組成，每個字符編碼在電文中出現的次數分別是6，5，9，10，20，1，試畫出這六個字符編碼所用的哈夫曼樹。30.已知一棵二叉樹的順序存儲結構如題30圖所示，其中表示虛結點，試構造該二叉樹。ABGCDHEF題30圖34.若兩棵二叉樹B1和B2皆為空，或者皆不空且B1的左、右子樹和B2的左、右子樹分別相似，則稱二叉樹B1和B2相似。試編寫算法，判別給定兩棵二叉樹是否相似。8.具有n個結點的二叉樹，擁有指向孩子結點的分支數目是（） A.n-1 B.n C.n+1 D.2n9.對一棵有100個結點的完全

40、二叉樹按層序編號，則編號為49的結點，它的左孩子的編號為（） A.99 B.98 C.97 D.5010.有m個葉子結點的哈夫曼樹，其結點總數是（）A.2m-1 B.2m C.2m+1 D.2(m+1)22.深度為k的二叉樹至多有_個結點，最少有_個結點。 29.已知一棵二叉樹的前序序列是ABCDEFG，中序序列是CBDAEGF。請構造出該二叉樹，并給出該二叉樹的后序序列。 30.將題30圖所示的由三棵樹組成的森林轉化為一棵二叉樹。8.含有n個結點的二叉樹采用二叉鏈表存儲時，空指針域的個數為（） A.n-1 B.n C.n+1 D.n+2 9.在一棵深度為H的完全二叉樹中，所含結點的個數不少于

41、（）A.2H-1-1 B.2H-1 C.2H-1 D.2H19.對一棵深度為10的滿二叉樹按層編號，則編號為51的結點，它的雙親結點編號為_。 21.具有n個葉子結點的哈夫曼樹，其結點總數為_。22.一棵具有n個結點的樹，所有非終端結點的度均為k，則該樹中葉子結點個數為_。 25.某二叉樹的后根遍歷序列為abd，中根遍歷序列為adb，則它的先根遍歷序列為_。 30.畫出題30圖所示的二叉樹的二叉鏈表存儲結構。 35.設二叉樹的結點類型定義如下： typedef struct node datatype data; struct node*lchild,*rchild;Bitree;Bitree

42、*t; 試編寫一個計算二叉樹深度的遞歸算法(int Depth(Bitree*t)。8.某二叉樹的先根遍歷序列和后根遍歷序列正好相反，則該二叉樹具有的特征是( )A.高度等于其結點數 B.任一結點無左孩子 C.任一結點無右孩子 D.空或只有一個結點9.在完全二叉樹中，若一個結點是葉結點，則它沒有( )A.左孩子結點 B.右孩子結點 C.左孩子結點和右孩子結點 D.左孩子結點，右孩子結點和兄弟結點12.若構造一棵具有n個結點的二叉排序樹，最壞的情況下其深度不超過( )A.n/2 B.n C.n+1/2 D.n+119.在一個具有n個結點的單鏈表中查找值為m的某結點，若查找成功，則需平均比較的結點數為_。20.深度為15的滿二叉樹上，第11層有_個結點。21.對一棵有100個結點的完全二叉樹按層編號，則編號為49的結點，它的左孩子的編號為_。30.已知一棵二叉樹的中根遍歷序列和后根遍歷序列分別為BDAFEHGC和DBFHGECA，試畫出這棵二叉樹。8.除根結點外，樹上每個結點( )A