數(shù)據(jù)結(jié)構(gòu)課后習(xí)題及答案

1、填空題（ 10 * 1 = 10 ）一、概念題2.2.當(dāng)對一個線性表經(jīng)常進(jìn)行的是插入和刪除操作時，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)為宜。2.3.當(dāng)對一個線性表經(jīng)常進(jìn)行的是存取操作，而很少進(jìn)行插入和刪除操作時，最好采用順序存儲結(jié)構(gòu)。2.6.帶頭結(jié)點(diǎn)的單鏈表L中只有一個元素結(jié)點(diǎn)的條件是L->Next->Next=Null。3.6.循環(huán)隊(duì)列的引入，目的是為了克服假溢出。4.2.長度為0的字符串稱為空串。4.5.組成串的數(shù)據(jù)元素只能是字符。4.8.設(shè)T和P是兩個給定的串，在T中尋找等于P的子串的過程稱為模式匹配 ，又稱P為模式。 7.2.為了實(shí)現(xiàn)圖的廣度優(yōu)先搜索，除一個標(biāo)志數(shù)組標(biāo)志已訪問的圖的結(jié)點(diǎn)外，還需

2、要隊(duì)列存放被訪問的結(jié)點(diǎn)實(shí)現(xiàn)遍歷。5.7.廣義表的深度是廣義表中括號的重數(shù)7.8.有向圖G可拓?fù)渑判虻呐袆e條件是有無回路。7.9.若要求一個稠密圖的最小生成樹，最好用Prim算法求解。8.8. 直接定址法法構(gòu)造的哈希函數(shù)肯定不會發(fā)生沖突。9.2.排序算法所花費(fèi)的時間，通常用在數(shù)據(jù)的比較和交換兩大操作。1.1.通常從正確性可讀性健壯性時空效率等幾個方面評價算法的（包括程序）的質(zhì)量。1.2.對于給定的n元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有集合關(guān)系線性關(guān)系 樹形關(guān)系圖狀關(guān)系四種。1.3.存儲結(jié)構(gòu)主要有順序存儲鏈?zhǔn)酱鎯λ饕鎯ι⒘写鎯λ姆N 。1.4.抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與存儲結(jié)構(gòu)無關(guān)，

3、即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部使用。1.5.一個算法具有五大特性：有窮性確定性可行性，有零個或多個輸入有一個或多個輸入。2.8.在雙向鏈表結(jié)構(gòu)中，若要求在p指針?biāo)傅慕Y(jié)點(diǎn)之前插入指針為s所指的結(jié)點(diǎn)，則需執(zhí)行下列語句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。2.9.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是不管單鏈表是否為空表，頭結(jié)點(diǎn)的指針均不空，并使得對單鏈表的操作（如插入和刪除）在各種情況下統(tǒng)一。3.1.隊(duì)列是限制在表的一端進(jìn)行插入和在另一端進(jìn)行刪除的線性表

4、，其運(yùn)算遵循先進(jìn)先出原則。3.2.棧是限定盡在表位進(jìn)行插入或刪除操作的線性表。3.5.在鏈?zhǔn)疥?duì)列中，判定只有一個結(jié)點(diǎn)的條件是(Q->rear=Q->front)&&(Q->rear!=NULL)。3.7.已知鏈隊(duì)列的頭尾指針分別是f和r，則將x入隊(duì)的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) r->next=p; r=p; else r=p; f=p;。3.8.循環(huán)隊(duì)列的滿與空的條件是(rear+1)%MAXSIZE=fornt和(front=-1&

5、;&rear+1=MAXSIZE)。4.3.串是一種特殊的線性表，其特殊性表現(xiàn)在數(shù)據(jù)元素都是由字符組成。4.7.字符串存儲密度是串值所占存儲位和實(shí)際分配位的比值，在字符串的鏈?zhǔn)酱鎯Y(jié)構(gòu)中其結(jié)點(diǎn)大小是可變的。5.3.所謂稀疏矩陣指的是矩陣中非零元素遠(yuǎn)遠(yuǎn)小于元素總數(shù)，則稱該矩陣為矩陣中非零元素遠(yuǎn)遠(yuǎn)小于元素總數(shù)，則稱該矩陣為稀疏矩陣。5.4.一維數(shù)組的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)；對二維或多維數(shù)組，分別按行優(yōu)先和列優(yōu)先兩種不同的存儲方式。7.4.在有向圖的鄰接矩陣表示中，計(jì)算第i個頂點(diǎn)入度的方法是求鄰接矩陣中第i列非0元素的個數(shù)。7.10.AOV網(wǎng)中，結(jié)點(diǎn)表示活動，邊表示活動之

6、間的優(yōu)先關(guān)系，AOE網(wǎng)中，結(jié)點(diǎn)表示事件 ，邊表示活動。9.1.按排序過程中依據(jù)不同原則對內(nèi)部排序方法進(jìn)行分類，主要有選擇排序交換排序插入排序 歸并排序等4類。9.3.在堆排序、快速排序和歸并排序中若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選擇歸并排序 方法；若只從平均情況下排序最快考慮，則應(yīng)選擇快速排序方法；若只從最壞情況下排序最快且要節(jié)省類存考慮，則應(yīng)選擇堆排序方法。9.4.直接插入排序用監(jiān)視哨的作用是存當(dāng)前要的插入記錄，可又省去查找插入位置時對是否出界的判斷。9.6.設(shè)表中元素的初始狀態(tài)是按鍵值遞增的，則直接插入排序最省時間，快速排序最費(fèi)時間。4.9.下列程序判斷字符串s是否對稱，對稱則返回1，否則

7、返回0；如(“abba”)返回1，（”abab”）返回0. Int f (char*s)Int i=0,j=0; while(sj) j+; /*求串長*/ for(j-;i<j && si=sj;i+,j+);return( i>=j);二、結(jié)論題2.7.在具有n個結(jié)點(diǎn)有序單鏈表中插入一個新結(jié)點(diǎn)并仍然有序的時間復(fù)雜度為O(n)。2.10.對于一個具有n個結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為O(1)，在給定值為x的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為O(n)。4.1.設(shè)正文產(chǎn)長度為n，模式串長度為m，則簡單模式匹配算法的時間復(fù)雜度為 O(m*n

8、) 。9.5.對n個記錄進(jìn)行快速排序時，遞歸調(diào)用而是用的棧所能達(dá)到的最大深度為O(n)，平均深度為O(log2n) 。7.1.克魯斯卡爾算法的時間復(fù)雜度為O(eloge)，它對稀疏圖較為合適。6.3.在一棵二叉樹中，度為0的結(jié)點(diǎn)的個數(shù)為N0，度為2的結(jié)點(diǎn)個數(shù)為N2，則有N0= N2+1。6.8 深度為k的完全二叉樹至少有2k-1個結(jié)點(diǎn)，至多有2k-1 個結(jié)點(diǎn)。7.3.具有n個結(jié)點(diǎn)e條邊的有向圖和無向圖用鄰接表表示，則鄰接表的邊結(jié)點(diǎn)個數(shù)分別為e和2e條。7.5.若n個頂點(diǎn)的連通圖是一個環(huán)，則它有n 棵生成樹。7.6.n個頂點(diǎn)的連通圖用連接矩陣表示時，該矩陣至少有2(n-1)個非零元素。7.7.有

9、n個頂點(diǎn)的有向圖，至少需要n條弧才能保證是連通的。9.7.歸并排序除了在遞歸是現(xiàn)實(shí)所用的log2n個?？臻g外，還用n個輔助空間。2.1.對于采用順序存儲結(jié)構(gòu)的線性表，當(dāng)隨機(jī)插入一個數(shù)據(jù)元素時，平均移動表中n/2元素；刪除一個數(shù)據(jù)元素時，平均移動表中(n-1)/2元素。2.4.在一個長度為n的順序存儲結(jié)構(gòu)的線性表中，向第i個元素（1in+1)之前插入一個新元素時，需向后邊移動n-i+1個元素。2.5.從長度為n的采用順序存儲結(jié)構(gòu)的線性表中刪除第i個元素（1in）,需向前移動n-1個元素。3.4.當(dāng)兩個棧共享一存儲區(qū)時，存儲區(qū)用一維數(shù)組stack（1，n）表示，兩棧頂指針為top【1】與top【2

10、】，則當(dāng)棧1空時。top【1】為0，棧2空時top【2】為n+1，棧滿的條件是top1+1=top2。8.1.順序查找n個元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為n次；當(dāng)使用監(jiān)視哨時，若查找失敗，則比較關(guān)鍵字的次數(shù)為n+1。6.5.設(shè)一顆完全二叉樹葉子結(jié)點(diǎn)數(shù)為k，最后一層結(jié)點(diǎn)數(shù)為偶數(shù)時，則該二叉樹的高度為+1，最后一層結(jié)點(diǎn)數(shù)為奇數(shù)時，則該二叉樹的高度為+1。9.8.對n個記錄建立一個堆的方法是：首先將要排序的所有記錄分到一棵二叉樹的各個結(jié)點(diǎn)中，然后從i=的結(jié)點(diǎn)ki，逐漸把以kn/2,kn/2-1kn/2-2,為根的子樹排成堆，直到以k1根的樹排成堆，就完成了初次建堆的過程。三、計(jì)算題

11、4.4.StrIndex(“MY STUDENT”,”STU”)=4。5.5.求下列廣義表的運(yùn)算結(jié)果：Get TailGetHeada,b,c,d=（b）。6.7.已知二叉樹先序?yàn)?，中序?yàn)椋瑒t后序一定是DGEBFCA。5.8.廣義表a,a,b,d,e,i,j,k的長度是5，深度是3。6.9.具有10個葉子的哈夫曼樹，其最大高度為9，最小高度為5。6.1.已知二叉樹有50個葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少是99。6.10.設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非終端節(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有n+1個。3.10. 表達(dá)式23+（12*13-2）/4+34*5/7）+108/9

12、的后綴表達(dá)式是23 12 3*2-4/34 5*7/+108 9/+。3.3. 用s表示入棧操作。X表示出棧操作，若元素入棧的順序?yàn)?,2,3,4,為了得到1,3,4,2出棧順序，相應(yīng)的s和x的操作串為SXSSXSXX。5.6.廣義表A=a,b,c,d,e,取出A中的原子e的操作是：GetTail(GetTail(GetTail(GetHead(A)。9.10.一組記錄的鍵值為12,38,35,25,74,50,63,90，按二路歸并排序方法對該序列進(jìn)行一趟歸并后的結(jié)果是12,38,25,35,50,74,63,90。3.9. 一個棧的輸出序列是，1，2，3，4，5，則不同的輸出序列有42種4

13、.6.設(shè)串S的長度為4，則S的子串個數(shù)最多為10。6.6.有5種不同形態(tài)的二叉樹可以按中序遍歷得到相同的abc序列。9.9.若用冒泡排序?qū)﹃P(guān)鍵字序列50,45,35,19,9,3進(jìn)行從小到大的排序，所需進(jìn)行的關(guān)鍵字比較總次數(shù)是15。5.1.二維數(shù)組A68采用行序?yàn)橹鞣绞酱鎯Γ總€元素占4個儲存單元，已知A的起始儲存地址基地址是1000，則A23的地址是1076。6.4.葉子權(quán)值（5,6,17,8,19）所構(gòu)造的哈夫曼樹帶權(quán)路徑長度為121。8.2.在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半法查找關(guān)鍵字20，需要的關(guān)鍵字比較次數(shù)為4。8.3.對于具有14

14、4個記錄的文件，若采用分塊查找法，且每塊長度為8，則平均查找長度為8.25或14。5.2.設(shè)數(shù)組A910，數(shù)組中任一元素均占內(nèi)存48個二進(jìn)制位，從首地址2000開始連續(xù)存放在主內(nèi)存里，主內(nèi)存字長為16位，那么：1存放該數(shù)組至少需要的單元數(shù)是270。2存放數(shù)組的第8列的所有元素至少需要的單位數(shù)是27。3數(shù)組按列存儲時，元素A58的起始地址是2231。選擇題（ 15 * 1 = 15 ）一、敘述類1.1.根據(jù)數(shù)據(jù)元素之間關(guān)系的不同性，以下解釋錯誤的是（ ）。A集合中任何兩個結(jié)點(diǎn)之間都有邏輯關(guān)系但組織形式松散B線性結(jié)構(gòu)中結(jié)點(diǎn)形成1對1的關(guān)系C樹形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點(diǎn)像自然界中的樹D圖狀

15、結(jié)構(gòu)中的各個結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任何兩個結(jié)點(diǎn)都可以鄰接1.2.關(guān)于邏輯結(jié)構(gòu)，以下說法錯誤的是（ ）。A邏輯結(jié)構(gòu)是獨(dú)立于計(jì)算機(jī)的B運(yùn)算的定義與邏輯結(jié)構(gòu)無關(guān) C同一邏輯結(jié)構(gòu)可以采用不同的存儲結(jié)構(gòu) D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu) E邏輯結(jié)構(gòu)是數(shù)據(jù)組織的某種“本質(zhì)性”的東西1.3.下面關(guān)于算法的說法正確的是（ ）。A算法的時間效率取決于算法所花費(fèi)的CPU時間 B在算法設(shè)計(jì)中不能用犧牲空間代價來換取好的時間效率 C算法必須具有有窮性、確定性等5個特性 D通常用時空效率來衡量算法的優(yōu)劣1.4.下面關(guān)于算法說法錯誤的是（ ）。A計(jì)算機(jī)程序一定是算法 B算法只能用計(jì)算機(jī)高級語言來描述 C算

16、法的可行性是指指令不能有二義性 D以上幾個都是錯誤的1.6.以下說法正確的是（ ）。A數(shù)據(jù)元素是數(shù)據(jù)的最小單位 B數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位 C原子類型不可再分解 D數(shù)據(jù)項(xiàng)只能是原子類型2.1.線性表是（ ）A.一個有限序列，可以為空 B.一個有限序列，不能為空 C.一個無限序列，可以為空 D.一個無限序列，不能為空2.3.線性表采用鏈?zhǔn)酱鎯r，其各元素存儲地址（ ）。A.必須是連續(xù)的 B.部分地址必須是連續(xù)的 C.一定是不連續(xù)的 D.連續(xù)與否均可以2.4.用鏈表表示線性表的優(yōu)點(diǎn)是（ ）。A. 便于隨機(jī)存取 B.花費(fèi)的存儲空間較順序存儲少C.便于插入和刪除 D.數(shù)據(jù)元素的物理順序與邏輯順序相同2.

17、5.（ ）插入、刪除速度快，但不能隨機(jī)存取。A. 鏈接表 B.順序表 C.順序有序表 D.上述三項(xiàng)無法比較2.6.若希望從鏈表中快速確定一個結(jié)點(diǎn)的前驅(qū)，則鏈表最好采用（ ）方式。A. 單鏈表 B.循環(huán)單鏈表 C.雙向鏈表 D.任意2.7.下面關(guān)于線性表的敘述錯誤的是（ ）。A. 線性表采用順序存儲，必須占用一片地址連續(xù)的單元 B.線性表采用順序存儲，便于進(jìn)行插入和刪除操作C.線性表采用鏈?zhǔn)酱鎯?，不必占用一片地址連續(xù)的單元 D.線性表采用鏈?zhǔn)酱鎯Γ阌谶M(jìn)行插入和刪除操作2.9.若某線性表中最常用的操作的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）存儲方法最節(jié)省運(yùn)算時間。A.

18、 單鏈表 B.僅有頭指針的單循環(huán)鏈表C.雙鏈表 D.僅有尾指針的單循環(huán)鏈表3.1.棧和隊(duì)列的共同點(diǎn)是（ ）。A.都是先進(jìn)先出 B.都是先進(jìn)后出 C.只允許在端點(diǎn)處插入和刪除元素 D.沒有共同點(diǎn)3.4.遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。A.隊(duì)列 B.多維數(shù)組 C.棧 D.線性表3.6.用鏈?zhǔn)酱鎯Φ年?duì)列，在進(jìn)行刪除運(yùn)算時（ ）。A.僅修改頭指針 B.僅修改尾指針 C.頭、尾指針都要修改 D.頭、尾指針可能都要修改3.7.棧應(yīng)用在（ ）。A.遞歸調(diào)用 B.子程序調(diào)用 C.表達(dá)式求值 D.A,B,C4.1.如下陳述中正確的事（ ）A.串是一種特殊的線性表 B.串的

19、長度必須大于零 C.串中元素只能是字母 D.空串就是空白串4.2.設(shè)有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（ ）A.求子串 B.聯(lián)接 C.匹配 D.求串長4.4.串是（ ）A.不少于一個字母的序列 B.任意個字母的序列 C.串中所含不同字符的個數(shù) D.串中所含非空格字符的個數(shù)4.5.串的長度是指（ ） A.串中所含不同字母的個數(shù) B.串中所含字符的個數(shù) C.串中所含不同字符的個數(shù) D.串中所含非空格字符的個數(shù)5.4.對矩陣壓縮儲存是為了（ ）A方便壓縮 B.節(jié)省空間 C.方便存儲 D.提高運(yùn)算速度6.1.如果T2是由樹T轉(zhuǎn)換而來的二叉樹，那么對T中結(jié)點(diǎn)的后根遍歷就

20、是對T2中結(jié)點(diǎn)的（ ）遍歷。 A 先序 B中序C后序D層次序6.4.二叉樹在線索后，仍不能有效求解的問題是（）。A 先序線索二叉樹中求先序后繼 B 中序線索二叉樹求中序后繼C 中序線索二叉樹中求中序前驅(qū) D 后序線索二叉樹中求后序后繼6.8 某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則此二叉樹一定是（）。A 空或只有一個結(jié)點(diǎn) B 完全二叉樹 C單枝樹 D 高度等于結(jié)點(diǎn)數(shù)6.9.在二叉樹結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（）。A 都不相同 B 完全相同 C 先序和中序相同而后序不同 D中序和后序相同而與先序不同7.5.圖的廣度優(yōu)先搜索類似于樹的（ ）遍歷。 A.先序

21、 B.中序 C.后序 D.層次7.8.下面（ ）方法可以判斷出一個有向圖是否有環(huán)（回路）。A.深度優(yōu)先遍歷 B.拓?fù)渑判?C.求最短路徑 D.求關(guān)鍵路徑7.9.在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（ ）。 A.G中有弧<Vi,Vj> B.G中有一條從Vi到Vj的路徑 C. G中沒有弧<Vi,Vj> D.G中有一條從Vj到Vi的路徑7.10.下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（ ）。 A.關(guān)鍵活動不按期完成就會影響整個工程的完成時間 B.任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成 C.所有的關(guān)鍵活動提前完成，那么整個工程將會

22、提前完成 D.某些關(guān)鍵活動提前完成，整個工程將會提前完成8.3.當(dāng)采用分塊查找時，數(shù)據(jù)的組織方式為（） A.數(shù)據(jù)分塊若干塊，每塊內(nèi)數(shù)據(jù)有序 B.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊 C.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊 D.數(shù)據(jù)分成若干塊，沒塊（除最后一塊外）中數(shù)據(jù)個數(shù)需相同8.5.下面關(guān)于折半查找的敘述正確的是（）。 A.表必須有序，表可以順序方式存儲，也可以鏈表方式存儲 B.表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型 C.表必須有序，而且只能從小到大排序 D.表必須有序，且表只能一順序方式存儲8.11

23、.下面關(guān)于哈希查找的說法正確的是（） A.哈希函數(shù)構(gòu)造的越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好、沖突小 B.除留余數(shù)法是所有哈希函數(shù)中最好的 C.不存在特別好與壞的哈希函數(shù)，要視情況而定 D.若需在哈希表中刪去一個元素，不管用何種方法解決沖突都只要簡單地將該元素刪去即可8.12.將10個元素散列到100000個單元的哈希表中，則（）產(chǎn)生沖突。 A.一定會 B.一定不會 C.仍可能會9.1.下列排序算法中，其中（ ）是穩(wěn)定的。A.堆排序和冒泡排序 B.快速排序和堆排序C.簡單選擇排序和歸并排序 D.歸并排序和冒泡排序9.3.以下時間復(fù)雜度不是O（nlog2n）的排序方法是（ ）。A.堆排序 B.直接插入排

24、序 C.二路歸并排序 D.快速排序9.4.若需在O（nlog2n）的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可以選擇的排序方法是（ ）。A.快速排序 B.堆排序 C.直接插入排序 D.歸并排序9.7.在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ）。A直接插入排序 B.快速排序 C.簡單選擇排序 D.歸并排序9.8.就排序算法所用的輔助空間而言，堆排序、快速排序、歸并排序的關(guān)系是（ ）。A.堆排序<快速排序<歸并排序 B.堆排序<歸并排序<快速排序C.堆排序>歸并排序>快速排序 D.堆排序>快速排序>歸并排序9.9.一個序列有

25、10 000個元素，若只想得到其中前10個最小的元素，最好采用（ ）方法。A.二路歸并排序 B.直接選擇排序C .Shell排序 D .堆排序9.10.設(shè)有字符序列Q,H,C,Y,P,A,M,S,R,D,F,X，新序列D,H,C,F,P,A,M,Q,R,S,Y,X是下列（ ）算法一趟排序的結(jié)果。A.冒泡排序 B.初始步長為4的Shell排序C.二路歸并排序 D. 快速排序 二、數(shù)字類1.5.程序段for(i=n-1;i>=0;i-) for(j=1;j<=n;j+) if Aj>Aj+1Aj與Aj+1互換; 其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（ ）。A.O(n

26、) B.O(n2) C.O(n3) D.O(nlog2n)2.2.從一個具有n個結(jié)點(diǎn)的單鏈表中查找值為x結(jié)點(diǎn)，在查找成功情況下，需要平均比較（ ）個結(jié)點(diǎn)。A. n B.n/2 C.（n-1）/2 D.（n+1）/22.8.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（ ）。A. head=NULL B.head>next=NULLC.head>next=head D.head!=NULL2.10.在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是（ ）。A. p>next=s;s>prior=p;p>next>prior=s;s>next=p>nex

27、t;B. p>next=s;p>next>prior=s;s>prior=p;s>next=p>next;C. s>prior=p;s>next=p>next;p>next=s;p>next>prior=s;D. s>prior=p;s>next=p>next;p>next>prior=s;p>next=s;3.2.若一個棧的輸入序列為1，2，3，n，輸出序列的第一個元素是n,則第i個輸出元素是（ ）。A.n-i-1 B.n-i C.n-i+1 D.不確定3.3.設(shè)a,b,c,d,e,f

28、以給定的次序進(jìn)棧，若在進(jìn)棧操作時，允許出棧操作，則下面得不到的序列為（ ）。A.f,e,d,c,b,a B.b,c,a,f,e,d C.d,c,e,f,b,a D.c,a,b,d,e,f3.5.若一個棧以向量V1.n存儲，初始棧頂指針top為n+1，則下面x入棧的正確操作是（ ）。A.top=top+1;Vtop=x B. Vtop=x;top=top+1 C.top=top-1;Vtop=x D.Vtop=x;top=top-13.8.中級表達(dá)式 A-(B+C/D)×E的后綴形式是（ ）。A.AB-C+D/E× B.ABC+D/E× C.ABCD/E×

29、+- D.ABCD/+E×-3.9、假設(shè)以數(shù)組A【m】存放循環(huán)隊(duì)列的元素，其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個數(shù)為（ ）A、(rear-front+m)%m B、rear-front+1C、（front-rear+m）%m D、（rear-front）%m3.10、循環(huán)隊(duì)列存儲在數(shù)組A【0.m】中，則入隊(duì)時隊(duì)尾的操作為（ ）A、rear=rear+1 B、rear=（rear+1）%（m-1）C、rear=（rear+1）%m D、rear=（rear+1）%（m+1）3.11、若元素a，b，c，d，e，f依次進(jìn)棧，允許進(jìn)棧，退棧操作交替進(jìn)行，單不允許連續(xù)三次進(jìn)

30、行進(jìn)退棧工作，則不可能得到的出棧序列是（ ）A、dcebfa B、cbdaef C、dbcaef D、afedcb3.12、某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許再一端進(jìn)行出隊(duì)操作，則不可能得到的順序是（ ）A、bacde B、dbace C、dbcae D、ecbad3.13、如果棧s和隊(duì)列q的初始狀態(tài)均為空，元素a，b，c，d，e，f，g依次進(jìn)入棧s，如果每個元素出棧立即進(jìn)入隊(duì)列q，且7個元素出隊(duì)的順序是b，d，c，f，e，a，g，則棧s的容量至少是（ ）A、1 B、2 C、3 D、44.3.串“ababaaababaa”的next數(shù)組為（ ）4.6.若s=”1234ab567abcda

31、b0”,t=”ab”,r=”(空串)，串替換StrRep(s,t,r)的結(jié)果是（ ）A.”1234ab567abcdab0” B.”1234ab567abcd” C.”1234567cd0” D.”1234 567 cd 0”4.7.S為一個長度為n的字符串，其中字符各不相同，則S中的互逆的非平凡子串（非空且不同于S本身）的個數(shù)（ ）A.2n-1 B.n² C.(n²/2)+(n/2) D.(n²/2)+(n/2)-1 4.8.若串S=”English”,其中串的個數(shù)是（ ）A.9 B.16 C.36 D.285.1.數(shù)組A56的每個元素占5個字節(jié)，將其按列優(yōu)先次

32、序存儲在起始地址為1000的內(nèi)存單元中，則元素A45的地址是（1145 ）5.2.若對n階對稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯堑脑兀òㄖ鲗蔷€上所有元素）依次存放于一維數(shù)組B1.(n（n+1）)/2中，aoo存放于數(shù)組B1中，則在B中確認(rèn)定aij（i<j）的位置k的關(guān)系為（ ）Ai×（i+1）/2+j B.j×（j+1）/2+I C.i×（j-1） D.j×m+i-15.3.設(shè)二維數(shù)組A1.m，1.n按行存儲在數(shù)組B1.m×n中，則二維數(shù)組元素Aij在一維數(shù)組B中的下標(biāo)為（ ）A.（i-1）×n+j B.(i-1)×

33、;n+j-1 C.i×(j-1) D.j×m+i-15.5.設(shè)廣義表L=（a，b，c），則L的長度和深度分別為（ ）A1和1 B.1和3 C.1和2 D.2和35.6.有一個100×90的稀疏矩陣，非0元素有10個，設(shè)每個整型數(shù)占兩個字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是（ ）A.60 B.66 C.18000 D.335.7.已知廣義表LS=（a，b，c），（d，e，f），運(yùn)用Get Head和Get Tail函數(shù)取出LS中原子e的運(yùn)算是（ ）A.GteHead（Get Tail（LS）B. Get Tail（GteHead（LS）C. GteHead（G

34、et Tail（GteHead（Get Tail（LS）D. GteHead（Get Tail（Get Tail（GteHead（LS）5.8.已知廣義表：A=(a，b)，B=（A,A）,C=(a，（b，A），B),求下列運(yùn)算的結(jié)果：Get Tail（GteHead（Get Tail（C）=（ ）A.(a) B.A C.a D.(b) E.b F.(A)6.2.設(shè)樹T的度為4，其中度為1 、2、3、4的結(jié)點(diǎn)個數(shù)分別是4、2、1、1則T中的葉子數(shù)位（） A 5 B 6 C 7 D 86.3.由4個結(jié)點(diǎn)可以構(gòu)造出（）種不同的二叉樹。A 10 B 12 C 14 D 166.5.若一棵二叉樹具有10

35、個度為2的結(jié)點(diǎn)，5個度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個數(shù)是（）A 9 B 11 C 15 D 不確定6.6 設(shè)高度為h 的二叉樹只有度為0和2的結(jié)點(diǎn)則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（）個。 A 2h B 2h-1 C 2h+1 D h+16.7設(shè)給定權(quán)值的葉子總數(shù)有n 個，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為（）。A 不確定 B 2n C 2n+1 D 2n-16.10.根據(jù)使用頻率，為5個字符設(shè)計(jì)的哈夫曼編碼不可能是（）。A 111,110,10,01,00 B 000,001,010,011,1 C 100,11,10,1,0 D 001,000,01,11,107.1.無向圖G=（V,E）V=a,b,c

36、,d,e,E=(a,b)(a,e),（a,c),(b,e),(c,f),(f,d),(e,d),其中對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（ ） A a,b,e,c,d,f B a,c,f,e,b,d C a,e,b,c,f,d D a,e,d,f,c,b7.2.一個n個頂點(diǎn)的連通無向圖，其邊的個數(shù)至少為（ ） A.n-1 B.n C.n+1 D.nlog2n7.3.在圖采用鄰接表存儲時，求最小生成樹的Prim算法的時間復(fù)雜度為（ ）A.O(n) B.O(n+e) C.O(n2) D.O(n3)7.4.G是一個非連通的無向組，共有28條邊，則該圖至少有（ ）個頂點(diǎn)。 A. 6 B.7

37、C.8 D.97.6.一個有n個頂點(diǎn)的無向圖，最少有（ ）個連通分量，最多有（ ）個連通分量。 A.0 B.1 C.n-1 D.n7.7.在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（ ）倍，在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（ ）倍。 A.12 B.2 C.1 D.48.1.若查找每個記錄的概率均等，則在具有n個記錄的順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為（ ）A.（n-1）/2 B.n/2 C.(n+1)/2 D.n8.2.具有12個關(guān)鍵字的有序表，折半查找的平均查找長度為（） A. 3.1 B. 4 C.2.5 D. 5 8.10.假定有k

38、個關(guān)鍵字互為同義詞，若用線性探測法把這k個關(guān)鍵字存入散列表中，至少要進(jìn)行（）次探測。 A.k-1次 B. k次 C.k+1次 D.k(k+1)/2次9.2.若對N個元素進(jìn)行快速排序，如果初始數(shù)據(jù)已經(jīng)有序，則時間復(fù)雜度為（ ）。A.O（1） B.O（n） C.O（n2） D.O（log2n）9.5.一組記錄的關(guān)鍵字問46,79,56,38,40,84，則利用快速排序方法，以第一個記錄為軸值得到的一次劃分結(jié)果為（ ）。A.38,40,46,56,79,84, B.40,38,46,79,56,84 C.40,38,46,56,79,84 D.40，38，46,84,56,799.6.一組記錄的關(guān)鍵

39、字為45,80，55，40,42,85，則利用堆排序方法建立的初始堆為（ ）。A.80,45,50,40,42,85 B.85,80,55,40,42,45 C.85,80,55,45,42,40 D.85,55,80,42,45,40判斷題（ 15 * 1 = 15 ）一、正確（35個）1.5.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲形式。2.2.順序存儲的線性表可以按序號隨機(jī)存取。2.3.線性表采用鏈?zhǔn)奖泶鎯r，存儲空間可以是不連續(xù)的。2.7.循環(huán)鏈表可以在尾部設(shè)置頭指針。2.8.為了方便插入和刪除，可以使用雙向鏈表存放數(shù)據(jù)。3.2.棧是實(shí)現(xiàn)過程和函數(shù)調(diào)用所必須的結(jié)構(gòu).3.3.兩個棧共享

40、一片連續(xù)內(nèi)存空間時,為提高內(nèi)存利用率,減少溢出的機(jī)會,應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端.3.5.棧與隊(duì)列是一種特殊的線性表3.7.循環(huán)隊(duì)列通常會浪費(fèi)一個存儲空間.3.8.循環(huán)隊(duì)列也存在空間溢出問題.3.9.棧和隊(duì)列的存儲方式,既可以是順序方式,又可以是鏈?zhǔn)椒绞?3.10.任何一個遞歸過程都可以轉(zhuǎn)換成非遞歸過程.4.1.KMP算法的特點(diǎn)是在模式匹配時指示主串的指針不會變小。4.3.nest函數(shù)值序列的產(chǎn)生僅與模式串有關(guān)。4.6.串名的存儲應(yīng)先高就是按串名訪問串值的一種方法。4.8.在插入和刪除操作中，鏈?zhǔn)酱欢ū软樞虼奖恪?.10.在串的順序存儲中，通常將0作為串的結(jié)束標(biāo)記。5.2.

41、二維以上的數(shù)組其實(shí)是一種特殊的廣義表。5.3.稀疏矩陣壓縮存儲后，必會失去隨機(jī)存取功能。 5.5.線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是原子，則廣義表便成為線性表。5.6.一個廣義表可以為其他廣義表所共享 。5.9.廣義表是由零或多個原子或子表所組成的有限序列，所以廣義表可能為空表。 5.10.任何一個非空廣義表 ，其表頭可能是單個元素或廣義表，其表尾必定是廣義表。 6.1.哈夫曼樹的結(jié)點(diǎn)個數(shù)不可能是偶數(shù)。6.4.哈夫曼編碼是前綴編碼。6.5.非空的二叉樹一定滿足：某結(jié)點(diǎn)若有左孩子，則其中序前驅(qū)一定沒有右孩子。6.7.由先序和后序遍歷序列不能唯一確定一棵二叉樹。6.9.一棵樹的葉結(jié)點(diǎn)，在先序遍歷和后序遍歷下，皆以相同的相對位置出現(xiàn)。7.4.哈夫曼編碼是前綴編碼。7.6.必須把一般樹轉(zhuǎn)成二叉樹后才能進(jìn)行存儲。7.10.在哈夫曼樹中，權(quán)值相同的葉結(jié)點(diǎn)都在同一層上。8.10.裝填因子是哈希表的一個重要參數(shù)，他反應(yīng)哈希表的裝滿成度。 9.2.在大根堆中，