單項(xiàng)選擇題1、向一個(gè)有255個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)〔〕個(gè)元素。A.8

B.127.5

C.127

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

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

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

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

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

)

A.e

B.2e

C.n2－e

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

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

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

〕條邊A.n+1

B.n

C.n-1

D.08、無(wú)向圖中一個(gè)頂點(diǎn)的度是指圖中(

)A.通過(guò)該頂點(diǎn)的簡(jiǎn)單路徑數(shù)

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

D.與該頂點(diǎn)連通的頂點(diǎn)數(shù)9、在以下排序算法中，()算法的最壞情況下時(shí)間復(fù)雜度不高于O(nlog2n)。A.起泡排序B.希爾排序C.歸并排序D.快速排序10、以下說(shuō)法中錯(cuò)誤的選項(xiàng)是()A.n個(gè)結(jié)點(diǎn)的樹的各結(jié)點(diǎn)度數(shù)之和為n-1B.n個(gè)結(jié)點(diǎn)的無(wú)向圖最多有n*(n-1)條邊C.用相鄰矩陣存儲(chǔ)圖時(shí)所需存儲(chǔ)空間大小與圖的結(jié)點(diǎn)數(shù)有關(guān),而與邊數(shù)無(wú)關(guān)D.散列表中碰撞的可能性大小與負(fù)載因子有關(guān)1、向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)〔〕。A．先移動(dòng)棧頂指針，再存入元素 B．先存入元素，再移動(dòng)棧頂指針C．先后次序無(wú)關(guān)緊要D．同時(shí)進(jìn)行2、設(shè)有向圖有n個(gè)頂點(diǎn)和e條邊，采用領(lǐng)接表作為其存儲(chǔ)表示，在進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為〔〕。A．O〔nlog2e〕B．O〔n+e〕 C．O(ne)D．O(n2)3、線性鏈表不具有的特點(diǎn)是〔〕。A．隨機(jī)訪問(wèn) B．不必事先估計(jì)所需存儲(chǔ)空間大小C．插入與刪除時(shí)不必移動(dòng)元素D．所需空間與線性表長(zhǎng)度成正比4、設(shè)有一個(gè)10階的對(duì)稱矩陣A[10][10]，采用壓縮存儲(chǔ)方式按行將矩陣中下三角局部的元素存入一維數(shù)組B[]中，A[0][0]存入B[0]中，那么A[8][5]在B[]中〔〕位置。A．32 B．33 C．41D．655、設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非葉結(jié)點(diǎn)，那么B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有〔〕個(gè)。A．n-1B．nC．n+1D．n+26、具有65個(gè)結(jié)點(diǎn)的完全二叉樹的高度為〔〕。〔根的層次號(hào)為0〕A．8B．7C．6D．57、假設(shè)待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序，那么采用〔〕方法比擬次數(shù)最少。A．直接插入排序B．快速排序 C．歸并排序D．直接選擇排序8、在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的〔〕倍。A．3B．2C．1D．1/29、某二叉樹進(jìn)行前序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，那么后序遍歷的結(jié)果為〔〕。A.DBFEACB.DFEBCA C.BDFECAD.BDEFAC10、假定有k個(gè)關(guān)鍵字互為同義詞，假設(shè)用線性探測(cè)法把這k個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行多少次探測(cè)？()1、用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的〔〕位置。A.鏈頭 B.鏈尾 C.鏈中2、只想得到1024個(gè)元素組成的序列中第5個(gè)最小元素之前的局部排序的序列，用〔〕方法最快。A.起泡排序B.快速排序 C.簡(jiǎn)單項(xiàng)選擇擇排序D.堆排序3、假設(shè)待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，那么稱該排序算法是不穩(wěn)定的?！病尘褪遣环€(wěn)定的排序方法。A.起泡排序B.歸并排序 C.直接插入排序D.簡(jiǎn)單項(xiàng)選擇擇排序4.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的〔〕結(jié)構(gòu)；A.存儲(chǔ) B.物理 C.邏輯 D.物理和存儲(chǔ)5.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)〔〕個(gè)元素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的從序號(hào)i開始的j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，那么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.它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ); B.它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ);C.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ);D.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用8.有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有〔〕條邊。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é)點(diǎn)都沒(méi)有左孩子D.有多種,但根結(jié)點(diǎn)都沒(méi)有右孩子A．k-1次B.k次C.k+1次D.k(k+1)/2次1、設(shè)H為帶頭結(jié)點(diǎn)單向循環(huán)鏈表的頭指針，指針域?yàn)閘ink，P為移動(dòng)指針，那么表尾的判斷條件是〔〕A.H->link=HB.P=HC.P->link=NULLD.P->link=H2、假設(shè)一個(gè)棧的輸入序列是1，2，3，…，n,輸出序列的第一個(gè)元素是n,那么第x個(gè)輸出元素是〔〕A．n-x B．n-x+1 C．x D．n-x-13、廣義表A=(a,(b),(),(c,d,e))的長(zhǎng)度為(

)A4

B5

C6

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

B．O(n+e)

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

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