數(shù)據(jù)結構復習題

單項選擇題1、向一個有255個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動〔〕個元素。A.8

B.127.5

C.127

D.72、帶頭結點的單鏈表first為空的判定條件是：()A.first==NULLB.first->link==NULLC.first->link==firstD.first!=NULL3、

設某線性鏈表的頭結點指針為L,L->data表示該鏈表的結點個數(shù)，L->next指向該鏈表的第一個結點，p指向新建立的結點，其類型與L相同。在建立該鏈表的過程中，假設希望L->next始終指向新輸入的結點，可采用如下的C語言語句實現(xiàn)：A.p->next=L->next,L->next=p，L->data++;B.p->next=NULL,L->next=p,L->data++;C.L->data++,L->next=p->next,p->next=L;D.以上都不是。 4、設A、B、C三個字符按先后順序依次進棧，下面哪個序列為不合法的出棧序列：A.ABC B.ACB C.BAC D.CAB5、如下陳述中正確的選項是〔

〕A．串是一種特殊的線性表

B．串的長度必須大于零C．串中元素只能是字母

D．空串就是空白串6、在二叉樹的第4層上至多有多少個結點：A.10個 B.8個 C.16個D.以上都不是。7、假設一棵二叉樹具有8個度為2的結點，那么該二叉樹的葉子個數(shù)是〔〕A.9B.11C.7D.8、在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為(

)

A.e

B.2e

C.n2－e

D.n2－2e9、5個不同的數(shù)據(jù)元素進行直接插入排序，最多需要進行〔〕次比擬。A.8 B.10 C.14 D10、設有關鍵碼初始序列{Q,H,C,Y,P,A,M,S,R,D,F,X}，新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}是采用以下哪種排序方法對初始序列進行第一趟掃描的結果？A.直接插入排序B.二路歸并排序C.以第一元素為分界元素的快速排序D.基數(shù)排序1、在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為()。A.O(n)B.O(n/2)C.O(1)D.O(n2)2、當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為()A.n-2B.n-1C.nD.n+13、鏈表表示線性表的優(yōu)點是:A.便于隨機存取B.花費的存儲空間比順序表少C.便于插入與刪除D.數(shù)據(jù)元素的物理順序與邏輯順序相同4、設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作〔〕A.連接B.模式匹配C.求子串D.求串長5、設有一個二元數(shù)組A[m][n],假設A[0][0]存放位置在644(10),A[2][2]存放位置在676(10)，每個元素占一個空間，那么A[4][5]在〔

〕位置,(10)說明用10進數(shù)表示。A.692(10)B.626(10)

C.709(10) D.724(10)6、在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加()。A.2B.-1C.07、n個頂點的連通圖至少有〔

〕條邊A.n+1

B.n

C.n-1

D.08、無向圖中一個頂點的度是指圖中(

)A.通過該頂點的簡單路徑數(shù)

B.與該頂點相鄰接的頂點數(shù)C.通過該頂點的回路數(shù)

D.與該頂點連通的頂點數(shù)9、在以下排序算法中，()算法的最壞情況下時間復雜度不高于O(nlog2n)。A.起泡排序B.希爾排序C.歸并排序D.快速排序10、以下說法中錯誤的選項是()A.n個結點的樹的各結點度數(shù)之和為n-1B.n個結點的無向圖最多有n*(n-1)條邊C.用相鄰矩陣存儲圖時所需存儲空間大小與圖的結點數(shù)有關,而與邊數(shù)無關D.散列表中碰撞的可能性大小與負載因子有關1、向順序棧中壓入新元素時，應當〔〕。A．先移動棧頂指針，再存入元素 B．先存入元素，再移動棧頂指針C．先后次序無關緊要D．同時進行2、設有向圖有n個頂點和e條邊，采用領接表作為其存儲表示，在進行拓撲排序時，總的計算時間為〔〕。A．O〔nlog2e〕B．O〔n+e〕 C．O(ne)D．O(n2)3、線性鏈表不具有的特點是〔〕。A．隨機訪問 B．不必事先估計所需存儲空間大小C．插入與刪除時不必移動元素D．所需空間與線性表長度成正比4、設有一個10階的對稱矩陣A[10][10]，采用壓縮存儲方式按行將矩陣中下三角局部的元素存入一維數(shù)組B[]中，A[0][0]存入B[0]中，那么A[8][5]在B[]中〔〕位置。A．32 B．33 C．41D．655、設F是一個森林，B是由F轉換得到的二叉樹，F(xiàn)中有n個非葉結點，那么B中右指針域為空的結點有〔〕個。A．n-1B．nC．n+1D．n+26、具有65個結點的完全二叉樹的高度為〔〕?！哺膶哟翁枮?〕A．8B．7C．6D．57、假設待排序對象序列在排序前已按其排序碼遞增順序排序，那么采用〔〕方法比擬次數(shù)最少。A．直接插入排序B．快速排序 C．歸并排序D．直接選擇排序8、在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的〔〕倍。A．3B．2C．1D．1/29、某二叉樹進行前序遍歷的結果為ABDEFC，中序遍歷的結果為DBFEAC，那么后序遍歷的結果為〔〕。A.DBFEACB.DFEBCA C.BDFECAD.BDEFAC10、假定有k個關鍵字互為同義詞，假設用線性探測法把這k個關鍵字存入散列表中，至少要進行多少次探測？()1、用單鏈表表示的鏈式隊列的隊頭在鏈表的〔〕位置。A.鏈頭 B.鏈尾 C.鏈中2、只想得到1024個元素組成的序列中第5個最小元素之前的局部排序的序列，用〔〕方法最快。A.起泡排序B.快速排序 C.簡單項選擇擇排序D.堆排序3、假設待排序序列中兩個數(shù)據(jù)元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，那么稱該排序算法是不穩(wěn)定的?！病尘褪遣环€(wěn)定的排序方法。A.起泡排序B.歸并排序 C.直接插入排序D.簡單項選擇擇排序4.數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的〔〕結構；A.存儲 B.物理 C.邏輯 D.物理和存儲5.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動〔〕個元素A.8 B.63.5 C.63 D.76.設串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))的結果串是〔〕。A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF7．二叉樹是非線性數(shù)據(jù)結構，所以〔〕。A.它不能用順序存儲結構存儲; B.它不能用鏈式存儲結構存儲;C.順序存儲結構和鏈式存儲結構都能存儲;D.順序存儲結構和鏈式存儲結構都不能使用8.有8個結點的無向連通圖最少有〔〕條邊。A．5B.6C.7D.9．折半查找有序表〔4,6,10,12,20,30,50,70,88,100〕。假設查找表中元素58，那么它將依次與表中〔〕比擬大小，查找結果是失敗。A．20,70,30,50B．30,88,70,50C．20,5010．把一棵樹轉換為二叉樹后，這棵二叉樹的形態(tài)是〔〕。A.有多種 B.唯一的C.有多種,但根結點都沒有左孩子D.有多種,但根結點都沒有右孩子A．k-1次B.k次C.k+1次D.k(k+1)/2次1、設H為帶頭結點單向循環(huán)鏈表的頭指針，指針域為link，P為移動指針，那么表尾的判斷條件是〔〕A.H->link=HB.P=HC.P->link=NULLD.P->link=H2、假設一個棧的輸入序列是1，2，3，…，n,輸出序列的第一個元素是n,那么第x個輸出元素是〔〕A．n-x B．n-x+1 C．x D．n-x-13、廣義表A=(a,(b),(),(c,d,e))的長度為(

)A4

B5

C6

D74、將一個A[1..100,1..100]的下三對角矩陣，按以行優(yōu)先存入一維數(shù)組B[1..298]中，A中元素a66,65(即該元素下標i=66,j=65)在數(shù)組中的位置k為〔〕。 A194 B195 C196 D1975、以{4，5，6，7，8}作為葉子結點的權值構造哈夫曼樹，那么其帶權路徑長度是〔〕。A65 B67 C68 D 696、具有200個結點的完全二叉樹的深度為()A6 B7 C8 D97、有向圖的鄰接矩陣是一個()A對稱矩陣 B上三角矩陣 C對角矩陣D上述說法都不對8、對線性表進行折半查找時，要求線性表必須〔〕A以順序方式存儲 B以鏈接方式存儲C以順序方式存儲，且結點按關鍵字有序排列D以鏈接方式存儲，且結點按關鍵字有序排列9、快速排序在〔〕情況下最不利于發(fā)揮其特長。 A被排序的數(shù)據(jù)量太大 B被排序的含有多個相同值 C被排序的數(shù)據(jù)已根本有序 D被排序的數(shù)據(jù)中有實數(shù)10、以下序列不是堆的是〔〕A(100,85,98,77,80,60,82,40,20,10,66〕B(100,95,85,82,80,77,66,60,40,20,10)C(10,20,40,60,66,77,80,82,85,98,100) D(100,85,40,77,80,60,66,98,82,10,20)1.算法分析的兩個主要方面是〔〕A.空間復雜性和時間復雜性 B.正確性和簡明性C.可讀性和文檔性 D.數(shù)據(jù)復雜性和程序復雜性2.鏈表是一種采用〔〕存儲結構存儲的線性表A.順序 B.鏈式 C.星式 D.網(wǎng)狀3、在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機那么從該緩沖區(qū)中取走數(shù)據(jù)打印。該緩沖區(qū)應該是一個〔〕結構。 A堆棧 B數(shù)組 C隊列 D線性表4．線性表Ｌ在〔〕情況下適用于使用鏈式結構實現(xiàn)。A.需經(jīng)常修改Ｌ中的結點值 B.Ｌ中結點結構復雜C.Ｌ中含有大量的結點 D.需不斷對Ｌ進行刪除插入5、先序遍歷能得到A，B，C序列的不同二叉樹，最多有幾種〔〕A4B5 C6 D76、假設樹中用一條線段把兩個結點連接起來，那么〔〕。 A不一定出現(xiàn)環(huán) B一定出現(xiàn)環(huán) C使樹的度數(shù)增1 D前面說法都不正確7、在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的〔〕倍。A1/2 B1 C2 D48、無向圖中定義頂點Vi與Vj之間的路徑為從Vi到達Vj的一個〔〕A頂點和邊序列B邊的條數(shù)C權值總和D邊序列9、任何一個無向連通圖的最小生成樹〔〕A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在10.折半查找與二叉排序樹查找的時間性能〔〕A.相同B.完全不同C.數(shù)量級都是O(log2n)D.有時不相同1．在以下存儲結構中，具備隨機存取特性的是〔〕A．順序表B．單鏈表C．單循環(huán)鏈表D．帶頭結點的雙循環(huán)鏈表2．在循環(huán)雙向鏈表的p所指結點之后插入q所指結點，可執(zhí)行〔〕操作來完成。A．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;B．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;C．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;D．p->next=q;q->prior=p;p->next->prior=q;q->next=p->next;3．假設一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，…，pi，…，pn，假設p1=n，那么pi為〔〕A．iB．n=iC.n-i+1D.不確定4．數(shù)組q[0..maxsize-1]作為循環(huán)隊列Q的存儲空間，front為隊頭指針，rear為隊尾指針，那么出隊操作為〔〕A.front=front+1B.front=(front+1)%maxsizeC.front=(rear-front+1)%maxsizeD.front=(rear-front+maxsize)%maxsize5．設有二維數(shù)組A[1..6][1..8]，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。起始地址為1000，假設按行優(yōu)先方式存儲，元素A[1，4]的地址是〔〕A．1024B．1018C．1004D．10036.在一棵非空樹中，〔〕沒有雙親結點。A.根結點B.葉子結點C.分支結點D.內部結點7．具有3個結點的二叉樹的形態(tài)有〔〕種。A．2B．3C．4D．58．圖G有n個結點和e條邊,在用鄰接表表示該圖時，建立圖的算法的時間復雜度為〔〕A．O〔n〕

B．O(n+e)

C．O〔n3〕D．O〔n2〕9.在以下無向圖G中，頂點V2的度是〔〕A.3B.A.3B.2C.4D.010．用二分查找法進行查找時，要求查找表中各元素按鍵值〔〕排列。A．遞增 B．遞減 C．遞增或遞減 D．無序二、填空題1、數(shù)據(jù)結構的形式定義為：數(shù)據(jù)結構是一個二元組Data_Structure=(D，S)，其中D是_________________、S是_________________.2、在一個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動__________個元素。3、________是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。4.設S=”A;/document/Mary.doc”，那么strlen(s)=____________,“/”的字符定位的位置為_______。5、在哈希造表過程中，處理沖突的方法主要有：________________，________________，________________，________________。6、所謂稀疏矩陣指的是_______。7在圖結構中，如果一個從Vp到Vq的路徑上除Vp和Vq可以相同外，其它結點都不相同，那么稱此路徑為________________。8.一棵深度為6的滿二叉樹有__________個分支結點和___________個葉子。9、對于n個記錄的表進行2路歸并排序，整個歸并排序需進行_______趟〔遍〕。1、數(shù)據(jù)結構有如下四類根本結構：集合、_________________、_________________、_________________。2、在順序表中插入或刪除一個元素，需要平均移動__________元素，具體移動的元素個數(shù)與________________有關。3.棧是一種特殊的線性表，允許插入和刪除運算的一端稱為________。不允許插入和刪除運算的一端稱為________。4、____________________________________稱為空串；5、假設有二維數(shù)組A6×8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址，那么數(shù)組A的體積〔存儲量〕為_______________。6、一棵具有257個結點的完全二叉樹，它的深度為________。7.有向圖G用鄰接表矩陣存儲，其第i行的所有元素之和等于頂點i的_______。8、圖的深度優(yōu)先遍歷序列______惟一的。9、從平均時間性能而言，__________排序最正確。10、線性有序表〔a1，a2，a3，…，a256〕是從小到大排列的，對一個給定的值k，用折半法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索______次。設有100個結點，用折半查找時，最多比擬次數(shù)是______。1、數(shù)據(jù)結構包括數(shù)據(jù)的邏輯結構、數(shù)據(jù)的_________和數(shù)據(jù)的_________這三個方面的內容。2、在n個結點的單鏈表中要刪除結點*p，需找到它的____________________，其時間復雜度為__________。3、循環(huán)隊列的引入，目的是為了克服_______。4、子串的定位運算稱為串的模式匹配；____________________稱為目標串，____________________稱為模式。5、三元組表中的每個結點對應于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的__________、__________和__________。6、由3個結點所構成的二叉樹有__________種形態(tài)。7、n個頂點e條邊的圖，假設采用鄰接矩陣存儲，那么空間復雜度為__________。8、對于n個記錄的集合進行冒泡排序，在最壞的情況下所需要的時間是________。假設對其進行快速排序，在最壞的情況下所需要的時間是__________。9、在數(shù)據(jù)的存放無規(guī)律的線性表中進行檢索的最正確方法是________________。1、數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的_________以及它們之間的_________和運算等的學科。2、在一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動__________個元素。3、用S表示入棧操作，X表示出棧操作，假設元素入棧的順序為1234，為了得到1342出棧順序，相應的S和X的操作串為_______。4、設S=“A:/document/Mary.doc”，那么strlen(s)=_________________,“/”的字符定位的位置為___________。5、設數(shù)組a[1…60,1…70]的基地址為2048，每個元素占2個存儲單元，假設以列序為主序順序存儲，那么元素a[32,58]的存儲地址為___________。6、一棵含有n(n>1)個結點的k叉樹，可能到達的最大深度為___________，最小深度為___________。7、設有一稀疏圖G，那么G采用___________存儲較省空間。8、在插入和選擇排序中，假設初始數(shù)據(jù)根本正序，那么選用___________；假設初始數(shù)據(jù)根本反序，那么選用___________。9、折半查找有序表〔4,6,12,20,28,38,50,70,88,100〕，假設查找表中元素20，它將依次與表中元素______________________比擬大小。10、在哈希函數(shù)H〔key〕=key%p中，p值最好取________________________________。11、哈夫曼樹是__________________________________________________。1.算法的五個重要特征是、、可行性、輸入、輸出。2.將長度為n的線性表順序存儲，在表中插入或刪除一個元素，在平均情況下其時間復雜度為。3.在雙向鏈表中，每個結點含有兩個指針域，一個指向前驅,一個指向。4.數(shù)組與廣義表可視為的推廣。5.在樹中，樹中所有結點度的最大值是樹的，樹中所有結點層次的最大值是樹的。6.一棵深度為k〔k>=1〕的二叉樹，它的第i〔i>=1〕層上最多有個結點，整棵樹最多有個結點。7.在一個圖中,如果頂點之間的連線是沒有方向的，那么稱該圖為圖；如果頂點之間的連線是有方向的，那么稱該圖為圖。8.直接插入排序算法的平均時間復雜度是，排序過程中僅需用個輔助單元。9.查找表是同一種數(shù)據(jù)類型的數(shù)據(jù)元素的有限集合，查找表分為________查找表和________查找表。1.線性結構中元素之間存在____________關系，樹形結構中元素之間存在__________________關系，2．鏈接存儲的特點是利用_______________來表示數(shù)據(jù)元素之間的邏輯關系。循環(huán)單鏈表的最大優(yōu)點是：_______________________。3、在順序表中插入或刪除一個元素，需要平均移動______________元素，具體移動的元素個數(shù)與______________有關。4.二維數(shù)組A[10…20][5…10]采用行序為主方式存儲，每個元素占4個存儲單元，并且A[10][5]的存儲地址是1000，那么A[18][9]的地址是____________。5.廣義表((a),((b),c),((d)))的表頭是_________，表尾是___________________。6．在二叉樹中，指針p所指結點為葉子結點的條件是______。7.無向圖G=〔V，{E}〕中從頂點v到頂點v’的路徑是一個____________序列。8.G是一個非連通無向圖，共有28條邊，那么該圖至少有___________個頂點。9．設n0為哈夫曼樹的葉子結點的數(shù)目，那么哈夫曼樹共有___________個結點。10.設要將序列〔Q,H,C,Y,P,A,M,S,R,D,F,X〕中的關鍵碼按字母順序的升序重新排列，那么：冒泡排序一趟掃描的結果是____________________________________.11.對于長度為255的表，采用分塊查找，每塊的最正確長度為__________。1.樹形結構中元素之間存在__________關系，圖形結構中元素之間存在________________關系。2.在一個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動__________個元素。3.設一棵完全二叉樹中有500個結點，那么該二叉樹的深度為__________。4._________是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。5.設無向圖G中有n個頂點和e條邊，那么其對應的鄰接表中有_________個表頭結點和_________個表結點。6.設有n個結點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，那么第i個結點的雙親結點編號為____________，右孩子結點的編號為___________。7.AOV網(wǎng)中,結點表示______,邊表示______。AOE網(wǎng)中,邊表示__________。8.設用希爾排序對數(shù)組{98，36，-9，0，47，23，1，8，10，7}進行排序，給出的步長〔也稱增量序列〕依次是4，2，1那么排序需__________趟，寫出第一趟結束后，數(shù)組中數(shù)據(jù)的排列次序___________________________________。9.在數(shù)據(jù)的存放無規(guī)律的線性表中進行檢索的最正確方法是____________________。三、判斷題()1、數(shù)據(jù)結構一般包括數(shù)據(jù)之間的邏輯結構，數(shù)據(jù)在計算機中的存儲方式和數(shù)據(jù)的運算三個方面。()2、單鏈表從任何一個結點出發(fā)，都能訪問到所有結點()3、線性表中的每個結點最多只有一個前驅和一個后繼。()4、一個nXn的對稱矩陣，如果采用壓縮存儲，其容量為n(n+1)/2。()5、n個結點的樹的各結點度數(shù)之和為n-1()6、霍夫曼樹一定是滿二叉樹。()7、只允許最下面的二層結點的度數(shù)小于2的二叉樹是完全二叉樹。

()8、在有向圖G中，所有結點的出度之和一定等于所有結點的出度之和()9、順序查找法與折半查找法對存儲結構的要求是：順序查找與折半查找既適用于順序表，也適用于鏈表()10、散列表中碰撞的可能性大小與負載因子有關()1.記錄是數(shù)據(jù)處理的最小單位。()2.鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算時機自動將后續(xù)各個單元向前移動。()3.棧和隊列是一種非線性數(shù)據(jù)結構。()4．假設輸入序列為1,2,3,4,5,6,那么通過一個?？梢暂敵鲂蛄?,5,4,6,2,3。()5.從邏輯結構上看，n維數(shù)組的每個元素均屬于n個向量。()6.稀疏矩陣壓縮存儲后，必會失去隨機存取功能。()7.二叉樹中每個結點的兩棵子樹的高度差等于1。()8．強連通圖的各頂點間均可達。()9．當待排序的元素很大時，為了交換元素的位置，移動元素要占用較多的時間，這是影響時間復雜度的主要因素。()10．采用線性探測法處理散列時的沖突，當從哈希表刪除一個記錄時，不應將這個記錄的所在位置置空，因為這會影響以后的查找。()1、記錄是數(shù)據(jù)處理的最小單位。()2、線性表的邏輯順序與存儲順序總是一致的。()3、在表結構中最常用的是線性表，棧和隊列不太常用。()4、一個稀疏矩陣Am*n采用三元組形式表示，假設把三元組中有關行下標與列下標的值互換，并把m和n的值互換，那么就完成了Am*n的轉置運算。()5、二維以上的數(shù)組其實是一種特殊的廣義表。()6.假設二叉樹用二叉鏈表作存貯結構，那么在n個結點的二叉樹鏈表中只有n-1個非空指針域。()7．強連通圖的各頂點間均可達。()8．對一個AOV網(wǎng)，從源點到終點的路徑最長的路徑稱作關鍵路徑。()9．當待排序的元素很大時，為了交換元素的位置，移動元素要占用較多的時間，這是影響時間復雜度的主要因素。()10．采用線性探測法處理散列時的沖突，當從哈希表刪除一個記錄時，不應將這個記錄的所在位置置空，因為這會影響以后的查找?！病?、數(shù)據(jù)的根本單位是數(shù)據(jù)項?！病?、帶權的無向連通圖的最小生成樹是唯一的。〔〕3、數(shù)組元素之間的關系，既不是線性的，也不是樹形的?！病?、對于有n個對象的待排序序列進行歸并排序，所需平均時間為O〔nlog2n〕?！病?、用鄰接矩陣法存儲一個圖所需的存儲單元數(shù)目與圖的邊數(shù)有關?！病?、在霍夫曼編碼中，當兩個字符出現(xiàn)的頻率相同時，其編碼也相同，對于這種情況應當特殊處理?！病?、線性表采用順序存儲表示時，必須占用一片連續(xù)的存儲單元?！病?、由樹轉化成二叉樹，其根的右子女指針總是空的?！病?、直接選擇排序是一種穩(wěn)定的排序方法。〔〕10、裝載因子是散列表的一個重要參數(shù)，它反映了散列表的裝滿程度?！病?．數(shù)據(jù)元素是構成數(shù)據(jù)的根本單位，具有相對獨立的含義而且是不可再分的?！病?．在單鏈表中任何兩個元素的存儲位置之間都有固定的聯(lián)系，因為可以從頭結點進行查找任何一個數(shù)據(jù)元素。〔〕3．鏈棧的元素入棧操作需先判斷棧滿?！病?．如果兩個串含有相同的字符，那么這兩個串相同?！病?．廣義表C=〔a，〔b，c，d〕〕，取尾操作Tail〔C〕=(d)?！病?．具有n(n>0)個結點的完全二叉樹的深度為[log2(n)]。〔〕7．完全二叉樹未必是滿二叉樹,滿二叉樹也未必是完全二叉樹。〔〕8．一個具有n個頂點的完全有向圖的弧數(shù)為n*(n-1)?！病?．對任意一個圖來說，從它的某個頂點出發(fā)進行一次廣度優(yōu)先搜索便能立刻訪問到該圖的所有頂點?！病?0．對一個堆進行按層次遍歷，不一定能得到一個有序序列。()1.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()2．線性表采用鏈表存儲時，結點和結點內部的存儲空間可以是不連續(xù)的。()3.用鏈表表示線性表的優(yōu)點是便于隨機存取。()4.長度為1的串和字符是相同的。()5.對于一棵非空二叉樹，它的根結點作為第一層，那么它的第i層上最多能有2i－1個結點。()6.AOV網(wǎng)的含義是以邊表示活動的網(wǎng)?！病?)7.路徑長度最長的路徑叫做關鍵路徑。()8.用二叉樹的先序遍歷和中序遍歷可以導出后序遍歷。()9.快速排序的速度在所有排序方法中為最快，而且所附加空間也最小。()10.負載因子(裝填因子)是散列表的一個重要參數(shù),它反映散列表的裝滿程度〔〕1．在待排數(shù)據(jù)根本有序的情況下，快速排序效果最好。〔〕2．稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。〔〕3.無向圖的鄰接矩陣可用一維數(shù)組存儲?！病场病?．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹?！病?.二叉樹中所有結點，如果不存在非空左子樹，那么不存在非空右子樹?！病?.假設輸入序列為1,2,3,4,5,6,那么通過一個?？傻玫捷敵鲂蛄?,2,5,6,4,1.〔〕7.線性表只能用順序存儲結構實現(xiàn)?！病?．堆是滿二叉樹。〔〕9．完全二叉樹中的葉子結點只可能在最后兩層中出現(xiàn)。〔〕10．Hash表的平均查找長度與處理沖突的方法無關四、簡答、應用題1、設n為正整數(shù)，給出以下程序段的時間復雜度。voidfunc(intn){intk;k=1;while(k<n)k=k*3;}2、列出先序遍歷能得到ABC序列的所有不同的二叉樹。3、某算法如下，試說明該算法實現(xiàn)的功能。#defineMax100302302034516856321379217{intst[Max],top=0;while(num!=0){st[top++]=num%r;num=num/r;}while(top>0)cout<<st[--top]<<““;cout<<endl;}4、G是一個非連通無向圖，共有28條邊，那么該圖至少有多少個頂點？〔5、對于以下圖所示的有向圖G，給出從頂點0到其余各頂點的最短路徑及路徑長度。(上圖)6某二叉樹先序遍歷的結果為：ABDGECFH，其中序遍歷的結果為：DGBEAHFC，試畫出這棵二叉樹。7對關鍵字序列〔7，4，1，14，100，30，5，9，20，134〕，設哈希函數(shù)為h(k)=k%13,試給出表長為13的哈希表〔用線性探測開放定址法處理沖突〕，并求出在等概率情況下，查找成功的平均查找長度。1、數(shù)據(jù)結構的主要研究對象是什么？2．線性表有兩種存儲結構：一是順序表，二是鏈表。試問：〔1〕如果有n個線性表同時并存,并且在處理過程中各表的長度會動態(tài)變化,線性表的總數(shù)也會自動地改變。在此情況下，應選用哪種存儲結構？為什么？〔2〕假設線性表的總數(shù)根本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應采用哪種存儲結構？為什么？3.設循環(huán)隊列的容量為40(序號從0到39)，現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有：①front=11，rear=19;②front=19，rear=11；問在這兩種情況下，循環(huán)隊列中各有元素多少個？4.二維數(shù)組Am×m采用按行優(yōu)先順序存放，每個元素占K個存儲單元，并且第一個元素的存儲地址為Loc(a11)，請寫出求Loc(aij)的計算公式。5.一棵度為2的樹與一棵二叉樹有何區(qū)別？6.圖1所示的有向圖，請給出該圖的:(8分)(1)每個頂點的入/出度；(2)鄰接矩陣；(3)鄰接表； (4)逆鄰接表。頂點頂點123456入度出度7．設有5個互不相同的元素a、b、c、d、e，能否通過7次比擬就將其排好序？如果能，請列出其比擬過程；如果不能，那么說明原因?！?分〕12101461210146820152552圖16537163214S：頂點號Edge：〔頂點，頂點，權值〕①〔，，〕①〔，，〕①〔，，〕①〔，，〕①〔，，〕①(,,)2、某二叉樹的結點數(shù)據(jù)采用順序存儲表示如下：012345678910111213141516171819EAF0D0H00C000GI0000B〔1〕試畫出此二叉樹的圖形表示?！?〕將此二叉樹看作森林的二叉樹表示，試將它復原為森林。3、設散列表的長度為11，散列函數(shù)為H(k)=k%11，給定的關鍵碼序列為56,74,23,11,69,22,59,29。試畫出用線性探查法解決沖突時所構成的散列表。0123456789104.一棵度為m的樹中有n1個度為1的結點，n2個度為2的結點，…nm個度為m的結點，問該樹中有多少片葉子？5．對于堆排序法，快速排序法和歸并排序法，假設僅從節(jié)省存儲空間考慮，那么應該首先選取其中哪種方法？其次選取哪種方法？假設僅考慮排序結果的穩(wěn)定性，那么應該選取其中哪種方法？6、如果輸入序列為123456,試問能否通過棧結構得到以下兩個序列:435612和135426;請說明為什么不能或如何才能得到。1.設循環(huán)隊列的容量為40(序號從0到39)，現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有①front=11,rear=19;②front=19,rear=11;問在這兩種情況下,循環(huán)隊列中各有元素多少個？2.假設在樹中，結點x是結點y的雙親時，用(x,y)來表示樹邊。一棵樹邊的集合為：{(i,m),(i,n),(b,e),(e,i),(b,d),(a,b),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用樹形表示法畫出此樹?！?．簡述樹和二叉樹之間的區(qū)別與聯(lián)系？4、一棵高度為h的滿k叉樹有如下性質：第h層上的結點都是葉結點，其余各層上每個結點都有k棵非空子樹，如果按層次自頂向下，同一層自左向右，順序從l開始對全部結點進行編號，試問：〔1〕第j層的結點個數(shù)是多少〔j=1，2，…h(huán)〕？〔2〕編號為i的結點的父結點〔假設存在〕的編號是多少？〔3〕編號為i的結點的第m個孩子結點〔假設存在〕的編號是多少？5．設一組初始記錄關鍵字序列為(25，50，35，15，80，85，40，20，36，70)，用二路歸并排序法排序并給出每一趟的排序結果。6.試比擬順序存儲結構和鏈式存儲結構的優(yōu)缺點?！?．〔1〕．如果G1是一個具有n個頂點的連通無向圖，那么G1最多有多少條邊？G1最少有多少條邊？〔2〕．如果G2是一個具有n個頂點的強連通有向圖，那么G2最多有多少條邊？G2最少有多少條邊？1、數(shù)據(jù)結構的主要研究對象是什么？2.試寫出如以下圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結點序列。3．假設一顆完全二叉樹包含A,B,…,G七個結點，寫出其鄰接表和鄰接矩陣。4.對具有10個數(shù)據(jù)的初始序列{100，86，48，73，35，39，42，57，66，21}，寫出采用二路歸并排序算法排序的每一趟的結果。5.請對如以下圖所示的無向帶權圖，寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹6.假定對有序表：〔3，4，5，7，24，30，42，54，63，72，87，95〕進行折半查找，試答復以下問題：(1)畫出描述折半查找過程的判定樹；(2)假設查找元素54，需依次與哪些元素比擬？1、設n為正整數(shù)，寫出以下程序段的時間復雜度(1) i=1;while(i<=n)i=i*3; }(2) I=1;j=0;while(I+j<=n){if(I<j)j++;elseI++;} 2、寫一算法，輸入一個任意的非負十進制數(shù)，將其轉換為等值的10進制數(shù)3、給定以下網(wǎng)G:(1)試著找出網(wǎng)G的最小生成樹，畫出其邏輯結構圖；(2)用兩種不同的表示法畫出網(wǎng)G的存儲結構圖；4．一關鍵碼序列為：3