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

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

B.127.5

C.127

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

設(shè)某線性鏈表的頭結(jié)點指針為L,L->data表示該鏈表的結(jié)點個數(shù)，L->next指向該鏈表的第一個結(jié)點，p指向新建立的結(jié)點，其類型與L相同。在建立該鏈表的過程中，假設(shè)希望L->next始終指向新輸入的結(jié)點，可采用如下的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、設(shè)A、B、C三個字符按先后順序依次進(jìn)棧，下面哪個序列為不合法的出棧序列：A.ABC B.ACB C.BAC D.CAB5、如下陳述中正確的選項是〔

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

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

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

)

A.e

B.2e

C.n2－e

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

〕位置,(10)說明用10進(jìn)數(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、在以下排序算法中，()算法的最壞情況下時間復(fù)雜度不高于O(nlog2n)。A.起泡排序B.希爾排序C.歸并排序D.快速排序10、以下說法中錯誤的選項是()A.n個結(jié)點的樹的各結(jié)點度數(shù)之和為n-1B.n個結(jié)點的無向圖最多有n*(n-1)條邊C.用相鄰矩陣存儲圖時所需存儲空間大小與圖的結(jié)點數(shù)有關(guān),而與邊數(shù)無關(guān)D.散列表中碰撞的可能性大小與負(fù)載因子有關(guān)1、向順序棧中壓入新元素時，應(yīng)當(dāng)〔〕。A．先移動棧頂指針，再存入元素 B．先存入元素，再移動棧頂指針C．先后次序無關(guān)緊要D．同時進(jìn)行2、設(shè)有向圖有n個頂點和e條邊，采用領(lǐng)接表作為其存儲表示，在進(jìn)行拓?fù)渑判驎r，總的計算時間為〔〕。A．O〔nlog2e〕B．O〔n+e〕 C．O(ne)D．O(n2)3、線性鏈表不具有的特點是〔〕。A．隨機(jī)訪問 B．不必事先估計所需存儲空間大小C．插入與刪除時不必移動元素D．所需空間與線性表長度成正比4、設(shè)有一個10階的對稱矩陣A[10][10]，采用壓縮存儲方式按行將矩陣中下三角局部的元素存入一維數(shù)組B[]中，A[0][0]存入B[0]中，那么A[8][5]在B[]中〔〕位置。A．32 B．33 C．41D．655、設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非葉結(jié)點，那么B中右指針域為空的結(jié)點有〔〕個。A．n-1B．nC．n+1D．n+26、具有65個結(jié)點的完全二叉樹的高度為〔〕?！哺膶哟翁枮?〕A．8B．7C．6D．57、假設(shè)待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序，那么采用〔〕方法比擬次數(shù)最少。A．直接插入排序B．快速排序 C．歸并排序D．直接選擇排序8、在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的〔〕倍。A．3B．2C．1D．1/29、某二叉樹進(jìn)行前序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，那么后序遍歷的結(jié)果為〔〕。A.DBFEACB.DFEBCA C.BDFECAD.BDEFAC10、假定有k個關(guān)鍵字互為同義詞，假設(shè)用線性探測法把這k個關(guān)鍵字存入散列表中，至少要進(jìn)行多少次探測？()1、用單鏈表表示的鏈?zhǔn)疥犃械年狀^在鏈表的〔〕位置。A.鏈頭 B.鏈尾 C.鏈中2、只想得到1024個元素組成的序列中第5個最小元素之前的局部排序的序列，用〔〕方法最快。A.起泡排序B.快速排序 C.簡單項選擇擇排序D.堆排序3、假設(shè)待排序序列中兩個數(shù)據(jù)元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，那么稱該排序算法是不穩(wěn)定的?！病尘褪遣环€(wěn)定的排序方法。A.起泡排序B.歸并排序 C.直接插入排序D.簡單項選擇擇排序4.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的〔〕結(jié)構(gòu)；A.存儲 B.物理 C.邏輯 D.物理和存儲5.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動〔〕個元素A.8 B.63.5 C.63 D.76.設(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é)果串是〔〕。A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF7．二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以〔〕。A.它不能用順序存儲結(jié)構(gòu)存儲; B.它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲;C.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲;D.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用8.有8個結(jié)點的無向連通圖最少有〔〕條邊。A．5B.6C.7D.9．折半查找有序表〔4,6,10,12,20,30,50,70,88,100〕。假設(shè)查找表中元素58，那么它將依次與表中〔〕比擬大小，查找結(jié)果是失敗。A．20,70,30,50B．30,88,70,50C．20,5010．把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是〔〕。A.有多種 B.唯一的C.有多種,但根結(jié)點都沒有左孩子D.有多種,但根結(jié)點都沒有右孩子A．k-1次B.k次C.k+1次D.k(k+1)/2次1、設(shè)H為帶頭結(jié)點單向循環(huán)鏈表的頭指針，指針域為link，P為移動指針，那么表尾的判斷條件是〔〕A.H->link=HB.P=HC.P->link=NULLD.P->link=H2、假設(shè)一個棧的輸入序列是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(即該元素下標(biāo)i=66,j=65)在數(shù)組中的位置k為〔〕。 A194 B195 C196 D1975、以{4，5，6，7，8}作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，那么其帶權(quán)路徑長度是〔〕。A65 B67 C68 D 696、具有200個結(jié)點的完全二叉樹的深度為()A6 B7 C8 D97、有向圖的鄰接矩陣是一個()A對稱矩陣 B上三角矩陣 C對角矩陣D上述說法都不對8、對線性表進(jìn)行折半查找時，要求線性表必須〔〕A以順序方式存儲 B以鏈接方式存儲C以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列D以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排列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.空間復(fù)雜性和時間復(fù)雜性 B.正確性和簡明性C.可讀性和文檔性 D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性2.鏈表是一種采用〔〕存儲結(jié)構(gòu)存儲的線性表A.順序 B.鏈?zhǔn)? C.星式 D.網(wǎng)狀3、在解決計算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)那么從該緩沖區(qū)中取走數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個〔〕結(jié)構(gòu)。 A堆棧 B數(shù)組 C隊列 D線性表4．線性表Ｌ在〔〕情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)。A.需經(jīng)常修改Ｌ中的結(jié)點值 B.Ｌ中結(jié)點結(jié)構(gòu)復(fù)雜C.Ｌ中含有大量的結(jié)點 D.需不斷對Ｌ進(jìn)行刪除插入5、先序遍歷能得到A，B，C序列的不同二叉樹，最多有幾種〔〕A4B5 C6 D76、假設(shè)樹中用一條線段把兩個結(jié)點連接起來，那么〔〕。 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到達(dá)Vj的一個〔〕A頂點和邊序列B邊的條數(shù)C權(quán)值總和D邊序列9、任何一個無向連通圖的最小生成樹〔〕A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在10.折半查找與二叉排序樹查找的時間性能〔〕A.相同B.完全不同C.數(shù)量級都是O(log2n)D.有時不相同1．在以下存儲結(jié)構(gòu)中，具備隨機(jī)存取特性的是〔〕A．順序表B．單鏈表C．單循環(huán)鏈表D．帶頭結(jié)點的雙循環(huán)鏈表2．在循環(huán)雙向鏈表的p所指結(jié)點之后插入q所指結(jié)點，可執(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．假設(shè)一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，…，pi，…，pn，假設(shè)p1=n，那么pi為〔〕A．iB．n=iC.n-i+1D.不確定4．?dāng)?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è)有二維數(shù)組A[1..6][1..8]，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。起始地址為1000，假設(shè)按行優(yōu)先方式存儲，元素A[1，4]的地址是〔〕A．1024B．1018C．1004D．10036.在一棵非空樹中，〔〕沒有雙親結(jié)點。A.根結(jié)點B.葉子結(jié)點C.分支結(jié)點D.內(nèi)部結(jié)點7．具有3個結(jié)點的二叉樹的形態(tài)有〔〕種。A．2B．3C．4D．58．圖G有n個結(jié)點和e條邊,在用鄰接表表示該圖時，建立圖的算法的時間復(fù)雜度為〔〕A．O〔n〕

B．O(n+e)

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

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