數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題(含答案)

1、數(shù)據(jù)結(jié)構(gòu)與算法2015-2016學(xué)年第1學(xué)期考試復(fù)習(xí)題一、 選擇題（下面各小題有一個(gè)正確答案，請將正確答案的編號填寫在各小題的括號內(nèi)）。1、在一棵具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（ A ）。A) 31 B）32C）33 D）162、串的邏輯結(jié)構(gòu)與（ D ）的邏輯結(jié)構(gòu)不相同。A）線性表 B）棧C）隊(duì)列 D）集合3、下列序列中，執(zhí)行第一趟快速排序后得到的序列是（ A ）。A）d,a,e,d,bfh,g B) c,e,a,dfh,g,bC) g,a,e,c,bfd,h D) a,b,c,d,fe,g,h4、n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（ A ）條邊。A）n B）n+1 C）n-1 D）n(n-1)5、數(shù)據(jù)

2、結(jié)構(gòu)中，在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ B ）。  A）動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)                       B）線性結(jié)構(gòu)和非線性結(jié)構(gòu) C）緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)              &#

3、160;     D）內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)6、鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)所占存儲空間（ A ）。  A）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針 B）只有一部分，存放結(jié)點(diǎn)值 C）只有一部分，存儲表示結(jié)點(diǎn)間關(guān)系的指針  D）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)7、有一個(gè)有序表1，4，6，10，18，35，42，53，67，71，78，84，92，99。當(dāng)用二分查找法查找鍵值為84的結(jié)點(diǎn)時(shí)，經(jīng)（ B ）比較后查找成功。 A) 4  

4、    B)3     C)2      D)128、設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要?jiǎng)h除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為（ A ）。A）p->next=p->next->next;   B） p=p->next;C）p=p->next->next;        D） p->next=p; 9

5、、n個(gè)頂點(diǎn)，e條邊的有向圖的鄰接矩陣中非零元素有（ C ）個(gè)。 A）n    B）2e         C）e       D） n+e 10、對下圖V4的度為（ C ）。A）1 B）2 C）3 D）4 v1 v2 v3 v411、在一棵度為3的樹中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2，度為2的結(jié)點(diǎn)個(gè)數(shù)為1，則度為0的結(jié)點(diǎn)個(gè)數(shù)為（ C ）。A）4 B）5C）6 D）712、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把

6、數(shù)據(jù)結(jié)構(gòu)分為（ C ）。 A）動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B）緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C）線性結(jié)構(gòu)和非線性結(jié)構(gòu) D）內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 13、用一維數(shù)組A進(jìn)行順序存儲時(shí)，若起始地址為loc(A1)，元素長度為c，則A的第i個(gè)數(shù)組單元在存放地址loc(Ai)，等于（ B ）。A）loc(A1)+i*c B）loc(A1)+(i-1)*cC）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c14、（ C ）在進(jìn)行插入操作時(shí)，常產(chǎn)生假溢出現(xiàn)象。A）順序棧 B）循環(huán)隊(duì)列C）順序隊(duì)列 D）鏈隊(duì)列15、某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ D ）存儲方式最節(jié)省

7、運(yùn)算時(shí)間。  A) 單鏈表  B) 僅有頭指針的單循環(huán)鏈表  C) 雙鏈表  D) 僅有尾指針的單循環(huán)鏈表16、向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行（ D ）。  A) hs->next=s;  B) s->next=hs->next; hs->next=s; C) s->next=hs; hs=s;  D) s->next=hs; hs=hs->next; 17、在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為

8、（ B ）。 A) rear=rear->next;     B) front=front->next; C) rear=front->next;      D) front=rear->next 18、已知棧的最大容量為4。若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行,則可能出現(xiàn)的出棧序列為（ C ）。  A) 5，4，3，2，1，6 B) 2，3，5，6，1，4  C) 3，2，5，4，1，6 

9、;D) 1，4，6，5，2，3 19、已知廣義表L=(x,y,z),a,(u,t,w)，從L 表中取出原子項(xiàng)t 的操作是（ D ）。 A) Head(Head(Tail(Tail(L) B) Tail(Head(Head(Tail(L) C) Head(Tail(Head(Tail(L) D)Head(Tail(Head(Tail(Tail(L)20、下列各種數(shù)據(jù)結(jié)構(gòu)中屬于線性結(jié)構(gòu)的有（ A ）。 A）棧 B) 二叉樹 C) 廣義表 D) 圖21、倘若在對串的插入、刪除運(yùn)算中，期望運(yùn)算速度最快，則應(yīng)采用（ C ）。 A）順序表示法 B）單字符為結(jié)點(diǎn)的單鏈表表示法 C）等量分塊表示法

10、D）不等量分塊表示法22、廣義表head(a,b),(c,d)的運(yùn)算結(jié)果為（ A ）。 A）(a,b) B）(c,d) C）空表 D）（a,b）,(c,d)）23、 n個(gè)頂點(diǎn)的圖的最小生成樹必定（ D ），是不正確的描述。 A）不唯一 B）權(quán)的總和唯一 C）不含回路 D）有n條邊24、采用鏈結(jié)構(gòu)存儲線性表時(shí)，其地址（ B ）。 A）必須是連續(xù)的 B）連續(xù)不連續(xù)都可以 C）部分地址必須是連續(xù) D）必須是不連續(xù)的25、隊(duì)列的操作的原則是（ A ）。 A）先進(jìn)先出 B) 后進(jìn)先出 C) 只能進(jìn)行插入 D) 只能進(jìn)行刪除26、以下屬于順序存儲結(jié)構(gòu)優(yōu)點(diǎn)的是（ A ）。   A) 存儲

11、密度大         B) 插入運(yùn)算方便 C）刪除運(yùn)算方便    D）可方便地用于各種邏輯結(jié)構(gòu)的存儲表示27、數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容是（ D ）。   A）數(shù)據(jù)的邏輯結(jié)構(gòu)          B）數(shù)據(jù)的存儲結(jié)構(gòu) C）建立在相應(yīng)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)上的算法    D）包括以上三個(gè)方面28、在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若

12、在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行（ A ） 。 A）q->next=s;  s->next=p;  B）s->next=p->next;  p->next=s; C）p->next=s->next;  s->next=p D）p->next=s;  s->next=q;29、若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ D ）存儲方式最節(jié)省時(shí)間。  A）順序表 

13、;B）雙鏈表C）帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D）單循環(huán)鏈表30、下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（ D ）  A）線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。 B）線性表采用鏈接存儲，便于插入和刪除操作。 C）線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。  D）線性表采用順序存儲，便于進(jìn)行插入和刪除操作。 31、在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為（ C ）。  A）top不變     B）top=0C）top-&#

14、160;  D）top+ 32、在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則插入一個(gè)結(jié)點(diǎn)的操作為（ B ）。A）front=front->next;  B） rear=rear->next; C） rear=front->next;       D） front=rear->next 33、設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳, B, C, D, E,下列是不可能的出棧序列是（ C ）。 A） A,

15、 B, C, D, E         B） B, C, D, E, A  C） E, A, B, C, D         D） E, D, C, B, A34、廣義表A=（A,B,(C,D),(E,(F,G)），則head(tail(head(tail(tail(A

16、)=（ D ）。 A） (G) B） (D) C） C D） D35、設(shè)給定問題的規(guī)模為變量n，解決該問題的算法所需時(shí)間為Tn=O(f(n),Tn表示式中記號O表示（ A ）。A）一個(gè)數(shù)量級別 B）一個(gè)平均值C）一個(gè)最大值 D）一個(gè)均方值36、線性表的鏈接實(shí)現(xiàn)有利于（ A ）運(yùn)算。A）插入 B）讀元素C）查找 D）定位37、串的邏輯結(jié)構(gòu)與（ D ）的邏輯結(jié)構(gòu)不同。A）線性表 B）棧C）隊(duì)列 D）樹38、下面程序段的時(shí)間復(fù)雜度是( A )。 s =0; for( i =0; i<n; i+) for(j=0;j<n;j+) s +=Bij; sum = s ; A） O(n2) B）

17、 O(n)C） O(m*n) D）O(1) 39、二叉樹第i(i1)層上至多有（ C ）結(jié)點(diǎn)。A）2i B）2i C）2i-1 D）2i-140、設(shè)單鏈表中指針p指著結(jié)點(diǎn)A，若要?jiǎng)h除A之后的結(jié)點(diǎn)（若存在），則需要修改指針的操作為（ A ）。A）p->next=p->next->next B）p=p->nextC）p=p->nexe->next D）p->next=p41、設(shè)一數(shù)列的順序?yàn)?，2，3，4，5，6，通過棧結(jié)構(gòu)不可能排成的順序數(shù)列為（ B ）。A）3，2，5，6，4，1 B）1，5，4，6，2，3C）2，4，3，5，1，6 D）4，5，3，6

18、，2，142、若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)的個(gè)數(shù)是( B )。 A）9 B）11 C）15 D）不能確定43、對待排序的元素序列進(jìn)行劃分，將其分為左、右兩個(gè)子序列，再對兩個(gè)子序列施加同樣的排序操作，直到子序列為空或只剩一個(gè)元素為止。這樣的排序方法是（ A ）。A）直接選擇排序 B）直接插入排序 C）快速排序 D）起泡排序44、設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯?，a11為第一個(gè)元素，其存儲地址為1，每元素占1個(gè)地址空間，則a85的地址為（ B ）。A）13 B）33 C）18 D）4045、如果結(jié)點(diǎn)A有3個(gè)兄弟，而且B為A的雙親，

19、則B的度為（ B ）。A）3 B）4 C）5 D）146、線索二叉樹中某結(jié)點(diǎn)D，沒有左孩子的條件是（ B ）。A）D->Lchild=Null B) D->ltag=1C) D->Rchild=Null D) D->ltag=047、棧進(jìn)行插入和刪除操作的特點(diǎn)是（ A ）。A）LIFO B）FIFOC）FCFS D）HPF48、與無向圖相關(guān)的術(shù)語有（ C ）。A）強(qiáng)連通圖 B）入度C）路徑 D）弧49、 n個(gè)頂點(diǎn)的圖的最小生成樹必定（ D ），是不正確的描述。A）不唯一 B）權(quán)的總和唯一C）不含回路 D）有n條邊50、若采用鄰接矩陣法存儲一個(gè)n個(gè)頂點(diǎn)的無向圖，則該鄰接矩

20、陣是一個(gè)（ D ）。A）上三角矩陣 B) 稀疏矩陣C) 對角矩陣 D) 對稱矩陣51、采用鏈結(jié)構(gòu)存儲線性表時(shí)，其地址（ B ）。A）必須是連續(xù)的 B）連續(xù)不連續(xù)都可以C）部分地址必須是連續(xù) D）必須是不連續(xù)的52、倘若在對串的插入、刪除運(yùn)算中，期望運(yùn)算速度最快，則應(yīng)采用（ B ）。A）順序表示法 B）單字符為結(jié)點(diǎn)的單鏈表表示法C）等量分塊表示法 D）不等量分塊表示法53、在循環(huán)隊(duì)列中，若front與rear 分別表示對頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是( C )。 A）front=rear+1 B）rear=front+1 C）front=rear D）front=0 二、判斷題

21、（對的打，錯(cuò)的打 ）1、算法和程序都應(yīng)具有下面一些特征：有輸入，有輸出，確定性，有窮性，有效性。（ 1 ）2、順序表和一維數(shù)組一樣，都可以按下標(biāo)隨機(jī)（或直接）訪問。（ 1 ）3、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲。（ 0 ）4、對稀疏矩陣進(jìn)行壓縮存儲是為了節(jié)省存儲空間。（ 1 ）5、數(shù)據(jù)的邏輯結(jié)構(gòu)反映了數(shù)據(jù)在計(jì)算機(jī)中的存儲方式。（ 1 ）6、從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較 (n+1)/2個(gè)元素結(jié)點(diǎn)。（ 1 ）7、在具有n個(gè)單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為：(rear+l)n=

22、60;= front。（ 1 ）8、選擇好的哈希函數(shù)就可以完全避免沖突的發(fā)生。 （ 0 ）9、棧和隊(duì)列都是順序存取的線性表，它們對存取位置的限制是一樣的。（ 0 ）10、在鐵路的列車調(diào)度中，假設(shè)兩側(cè)鐵道均為單向行駛道，如果進(jìn)站的列車序列為123456，則一定能得到435612和135426的出站序列。（ 0 ）11、廣義表是由零個(gè)或多個(gè)原子或子表所組成的有限序列，所以廣義表可能為空表。（ 0 ）12、數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系，即不是線性的也不是樹形的。（ 0 ）13、用鄰接表存儲圖所用的空間大小與圖的頂點(diǎn)數(shù)和邊數(shù)都有關(guān)。（ 0 ）14、設(shè)散列表長度為m，

23、散列函數(shù)為H（key）=key% p，為了減少發(fā)生沖突的可能性，p應(yīng)取小于m的最大奇數(shù)。（ 1 ）15、在排序前，關(guān)鍵字值相等的不同記錄間的前后相對位置保持不變的排序方法稱為穩(wěn)定的排序方法。（ 1 ）16、引入線索二叉樹的目的是為了能在二叉樹中方便的進(jìn)行插入與刪除。（ 0 ）17、算法分析的主要任務(wù)是研究數(shù)據(jù)之間的邏輯關(guān)系。（ 0 ）18、在一個(gè)長度為n的順序表中刪除第i個(gè)元素(0£i£n)時(shí)，需向前移動(dòng)n-i個(gè)元素。（ 0 ）19、在具有n個(gè)單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為：rear= = 

24、;front。（ 0 ）20、在鐵路的列車調(diào)度中，假設(shè)兩側(cè)鐵道均為單向行駛道，如果進(jìn)站的列車序列為123456，則只能得到654321的出站序列。（ 0 ）21、在一棵二叉樹中，假定每個(gè)結(jié)點(diǎn)只有左孩子，沒有右孩子，對它分別進(jìn)行前序遍歷和中根遍歷，則具有相同的結(jié)果。（ 0 ）22、廣義表(a,b),a,b)的表頭和表尾是相等的。（ 0 ）23、線性表可以看成是廣義表的特例，如果廣義表中的每個(gè)元素是原子，則廣義表便成為線性表。（ 1 ）24、插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也會經(jīng)常使用。（ 0 ）25、線索二叉樹是一種物理結(jié)構(gòu)。（ 1 ）26、一個(gè)帶權(quán)無向連通圖的

25、最小生成樹有一棵或多棵。（ 1 ）27、對線性表進(jìn)行二分查找時(shí)，要求線性表必鍵值有序的鏈接表。（ 1 ）29、樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加1。（ 0 ）30、圖的深度優(yōu)先搜索是一種典型的回溯搜索的例子，可以通過遞歸算法求解。（ 1 ）三、填空題。1、在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為： p->next->next 。2、有向圖的邊稱為 弧 ，邊的始點(diǎn)稱為 弧尾 ，邊的終點(diǎn)稱為 弧頭 。有向圖頂點(diǎn)的度為 出度 和 入度 之和。3、若一個(gè)算法中的語句頻度之和為T（n）=3n+nlog2n+n2，則算法的時(shí)間復(fù)雜度為 O(T（

26、n）)_ 。4、如下程序段的時(shí)間復(fù)雜度為_O(m*n)_ for(i=1; i<=n; i+) m=n-i; for (j=1; j<=m; j+) sum+=j;5、設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D=1，2，3，4，5，6，7，8，9，R=r，r=<1，2>，<1，3>，<1，4>，<2，5>，<2，6>，<3，7>，<3，8>，<3，9>，則該數(shù)據(jù)結(jié)構(gòu)是_樹形_結(jié)構(gòu)。6、從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，平均比較次數(shù)為：_(n+1)

27、/2_。7、在中序線索二叉樹中，左線索指向 前驅(qū)或左孩子 。8、對于一個(gè)以順序?qū)崿F(xiàn)的循環(huán)隊(duì)列Q0.m-1，隊(duì)頭、隊(duì)尾指針分別為f,r，其判空的條件是 f=r ，判滿的條件是 (r+1)%m=f 。9、若已知一個(gè)棧的進(jìn)棧序列是1，2，3， ，n，其輸出序列為p1，p2，p3， ，pn，若p1=n，則pi為_n-i+1_。10、設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個(gè)結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的編號為_2n+1_。11、在一棵二叉樹中，如果度為2的結(jié)點(diǎn)有25個(gè)，則該樹的葉子結(jié)點(diǎn)一定有_26_個(gè)。12、在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有_n(n-1)/2_條邊。1

28、3、線性結(jié)構(gòu)的邏輯特征是 除頭結(jié)點(diǎn)和尾節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)僅有一個(gè)前驅(qū)和一個(gè)后繼結(jié)點(diǎn) 。14、設(shè)一組權(quán)值集合W=2，3，4，5，6，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為_45_15、設(shè)有向圖G中有向邊的集合E=<1，2>，<1，3>，<2，4>，<3，2>，<3，4>，<4，5>，則該圖的拓?fù)湫蛄袨開13245_。16、一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則出隊(duì)序列為：_1234_。17、設(shè)有一個(gè)順序循環(huán)隊(duì)列中有M個(gè)存儲單元，則該循環(huán)隊(duì)列中最多能夠存儲_M-1_個(gè)隊(duì)列元素。18、隊(duì)列Q，經(jīng)過下列運(yùn)算：InitQueu

29、e(Q)(初始化隊(duì)列); InQueue(Q,a); InQueue(Q,b); DeQueue(Q, x); DeQueue(Q, x); 后x值是_b_。19、數(shù)據(jù)結(jié)構(gòu)包括了 數(shù)據(jù)的邏輯結(jié)構(gòu) 、 數(shù)據(jù)的存儲結(jié)構(gòu) 、 數(shù)據(jù)的運(yùn)算 三個(gè)方面的內(nèi)容。20、設(shè)一棵完全二叉樹中有300個(gè)結(jié)點(diǎn)，則該二叉樹的深度為_9_。21、在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有_n*(n-1)_條邊。22、一棵深度為 10 的完全二叉樹的結(jié)點(diǎn)總數(shù)的最小值為_29-1_，最大值為_210-1_。23、有一個(gè)有序表3，7，8，15，18，22，34， 67，75， 84，92，100,當(dāng)用二分查找法查找鍵值為92的結(jié)

30、點(diǎn)時(shí)，經(jīng)_3_次比較后查找成功。24、遞歸算法必須依賴 堆棧 的處理來實(shí)現(xiàn)。25、隊(duì)列的運(yùn)算特點(diǎn)是 先進(jìn)先出 ，棧的運(yùn)算特點(diǎn)是 先進(jìn)后出 。26、設(shè)有向圖G中有向邊的集合E=<1，2>，<2，3>，<1，4>，<4，2>，<4，3>，則該圖的拓?fù)湫蛄袨開1423_。27、在一個(gè)長度為n的順序表L中，刪除下標(biāo)為i的結(jié)點(diǎn)，需要移動(dòng)的結(jié)點(diǎn)數(shù)為_n-i-1_。28、假設(shè)用front表示隊(duì)頭元素在一維數(shù)組中的前一位置，rear表示對尾元素在一維數(shù)組中的位置，則隊(duì)列為空的條件是_front=rear_。29、一棵含7個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_3

31、_。30、已知二維數(shù)組A610，每個(gè)數(shù)組元素占4個(gè)存儲單元，若按行優(yōu)先順序存放數(shù)組元素a35的存儲地址是1000，則a00的存儲地址是_860_。31、含n個(gè)頂點(diǎn)的無向連通圖中至少含有_n-1_條邊。32、對于棧只能在_棧頂_插入和刪除元素。33、樹是n個(gè)節(jié)點(diǎn)的有限集合，其中有且僅有一個(gè)_根_節(jié)點(diǎn)沒有前趨節(jié)點(diǎn)，而包含度為0的節(jié)點(diǎn)稱為_n+1/2_節(jié)點(diǎn)。34、指向前趨節(jié)點(diǎn)和后繼節(jié)點(diǎn)的指針稱為線索，加了線索的二叉樹稱為_線索二叉樹_。35、常用的圖的遍歷方法有兩種；深度優(yōu)先搜索和_廣度優(yōu)先搜索_。36、為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問題是_構(gòu)造一個(gè)好的hash函數(shù)_和_確定解決沖

32、突的方法_。37、順序表中邏輯上相鄰的元素的物理位置 相鄰 。單鏈表中邏輯上相鄰的元素的物理位置 不 相鄰。38、在一個(gè)長度為n的數(shù)組的第i個(gè)元素(1in+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng) n-i 個(gè)元素。四、簡答題。1、已知兩個(gè)一元多項(xiàng)式A(x)和B(x)如下：A(x) = 3 + 5x + 7x5 + 9x15 B(x) = 4x 7x5+ 21x7要求給出圖形示意表示：（1）采用單鏈表表示一元多項(xiàng)式A(x)和B(x)（2）給出求和A(x)+B(x)多項(xiàng)式的單鏈表（要求給出結(jié)點(diǎn)指針變化過程）2、簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)。數(shù)據(jù)：指所有能夠輸入到計(jì)算機(jī)中并被

33、計(jì)算機(jī)程序處理的符號集合。數(shù)據(jù)元素：數(shù)據(jù)集合中的一個(gè)實(shí)體，是計(jì)算機(jī)程序中加工處理的基本單位。數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的集合。即包括數(shù)據(jù)元素的集合和數(shù)據(jù)元素之間的關(guān)系的集合。存儲結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（也稱映像）叫做物理結(jié)構(gòu)。又稱為存儲結(jié)構(gòu)。3、簡述棧和線性表的差別。4、試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語言中數(shù)據(jù)類型概念的區(qū)別。抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但含義比一般數(shù)據(jù)類型更廣、更抽象。一般數(shù)據(jù)類型由具體語言系統(tǒng)內(nèi)部定義，直接提供給編程者定義用戶數(shù)據(jù)，因此稱它們?yōu)轭A(yù)定義數(shù)據(jù)類型。抽象數(shù)據(jù)類型

34、通常由編程者定義，包括定義它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進(jìn)行的操作。5、已知一棵樹邊的集合為(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用樹形表示法畫出此樹，并回答下列問題。（1） 哪個(gè)是根結(jié)點(diǎn)？ a（2） 哪些是葉結(jié)點(diǎn)？ d m n j k f l（3） 哪個(gè)是g的雙親？ c（4） 哪些是g的祖先？ a b c（5） 哪些是g的孩子？ j k（6） 哪些是e的子孫？ i m n（7） 哪些是e的兄弟？哪些是f的兄弟？ dgfh degh（8） 結(jié)點(diǎn)b和n的層次各是多少？ 2 5（9）

35、 樹的深度是多少？ 5（10） 以結(jié)點(diǎn)c為根的子樹的深度是多少？ 2（11） 樹的度是多少？ 36、何謂隊(duì)列的“假溢出”現(xiàn)象，如何解決？假溢出是是隊(duì)列在一端進(jìn)入插入，TOP值就會增加，在另一端刪除，當(dāng)判斷TOP=MAX-1是，就會說明已經(jīng)隊(duì)滿，但實(shí)際在隊(duì)列的另一端還是有存儲空間的，這就是“假溢出”。 解決方法：設(shè)置隊(duì)列為循環(huán)隊(duì)列就可以了。TOP=（TOP+1）MOD （MAX-1）。7、簡述隊(duì)列和堆棧這兩種數(shù)據(jù)類型的相同點(diǎn)和差異處。8、abdce先序：abdce中序：bdaec后序：dbeca9、對于下圖，試給出：（1）每個(gè)頂點(diǎn)的入度，出度。d(1)+ = 1, d(1)- = 2d(2)+

36、= 2, d(1)- = 2d(3)+ = 3, d(3)- = 1d(4)+ = 3, d(4)- = 0d(5)+ = 2, d(5)- = 3d(6)+ = 1, d(6)- = 2（2）鄰接矩陣和入邊表圖示。（3）強(qiáng)連通分量。23652 1 4 5 6 2 3鄰接表 入邊表(逆鄰接表)10、已知一組元素的排序碼為:（46,74,16,53,14,26,40,38,86,65,27,34）寫出用直接選擇排序方法進(jìn)行每趟排序的結(jié)果?！?4】,74,16,53,46,26,40,38,86,65,27,34【14,16】,74,53,46,26,40,38,86,65,27,34【14,16

37、,26】,53,46,74,40,38,86,65,27,34【14,16,26,27】,46,74,40,38,86,65,53,34【14,16,26,27,34】,74,40,38,86,65,53,46【14,16,26,27,34,38】,40,74,86,65,53,46【14,16,26,27,34,38,40】,74,86,65,53,46【14,16,26,27,34,38,40,46】,86,65,53,74【14,16,26,27,34,38,40,46,53】,65,86,74【14,16,26,27,34,38,40,46,53,65】,86,74【14,16,26,

38、27,34,38,40,46,53,65,74】,86【14,16,26,27,34,38,40,46,53,65,74,86】11、設(shè)二叉樹的順序存儲結(jié)構(gòu)如下：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20E AFDHCGIB（1） 根據(jù)其存儲結(jié)構(gòu)，畫出該二叉樹。（2） 寫出按前序、中序、后序遍歷該二叉樹所得的結(jié)點(diǎn)序列。前序：EADCBFHGI中序：ABCDEFGHI后序：BCDAGIHFE（3） 畫出二叉樹的后序線索化樹。12、已知某電文中只有ABCDE共5個(gè)字母，權(quán)值集合W=0.25,0.10,0.20,0.30,0.15，試分析Hu

39、ffman樹的生成過程，畫出存儲結(jié)構(gòu)表（初態(tài)和終態(tài)），以及最終的Huffman樹，并用0/1給ABCDE這5個(gè)字母分別編碼，最后寫出電文：BAACDE的Huffman編碼。A(00),B(110),C(10),D(01),E(111).BAACDE(11000001001111);13、某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，它們分別是ABCDEFGH，其概率分別為0.05，0.19，0.18，0.09，0.12，0.23，0.13，0.01?，F(xiàn)要對這八種字符進(jìn)行Huffman編碼，寫出該編碼值。畫出該Huffman樹(權(quán)值大的結(jié)點(diǎn)做左孩子)，在所有的結(jié)點(diǎn)上標(biāo)出其權(quán)值，并求出這棵樹的帶權(quán)路徑長度

40、。 A(01010) B(11) C(000) D(0100) E(011) F(10) G(001) H(01011)L(n)=0.05*5+0.19*2+0.18*3+0.09*4+0.12*3+0.23*2+0.13*3+0.01*5 = 2.7914、已知一組元素為（46，25，78，62，12，37，70，29），試畫出按元素排列次序插入生成的一棵二叉排序樹。15、簡述起泡算法的過程，并寫出使用起泡排序方法對下面的整數(shù)數(shù)列進(jìn)行排序的結(jié)果（寫出每趟排序后的結(jié)果）： 97，66，49，38，26，17，9，6。66，49，38，26，17，9，6,(97)49，38，26，17，9，6,

41、(66, 97)38，26，17，9，6,(49, 66, 97)26，17，9，6,(38, 49, 66, 97)17，9，6,(26, 38, 49, 66, 97)9，6,(17, 26, 38, 49, 66, 97)6,(9, 17, 26, 38, 49, 66, 97)(6, 9, 17, 26, 38, 49, 66, 97)16、畫出下列二叉排序樹的平衡結(jié)果圖，要求：（1）已知初始查找表的關(guān)鍵字序列為（70,100,80,30,75），構(gòu)造并畫出初始二叉排序樹，標(biāo)明各結(jié)點(diǎn)平衡因子+。（2）插入關(guān)鍵字20，a. 畫出失衡后的二叉排序樹，標(biāo)明各結(jié)點(diǎn)平衡因子b. 畫出重新平衡后的

42、二叉排序樹，標(biāo)明各結(jié)點(diǎn)平衡因子 17、什么是有向網(wǎng)？已知有向網(wǎng)G=(V,E)，其中頂點(diǎn)集V=a,b,c,d,e，邊集為：E=<a,b,5>,<b,d,1>, <c,d,1>, <d,e,2> , <e,c,3>，E中的每條邊是一個(gè)三元組，分別表示弧尾，弧頭和邊的長度（權(quán)重）。畫出有向網(wǎng)G，寫出其鄰接矩陣。18、關(guān)鍵字集合為19, 36,23, 82,14,55,68,11, 01，哈希函數(shù)為：Hash(key)=key mod 7，試寫出哈希表的鏈地址處理圖。19、寫出如下所示二叉樹的葉子結(jié)點(diǎn)和非終端結(jié)點(diǎn)以及各結(jié)點(diǎn)所在的層次、樹的深度

43、、樹的深度，并且寫出該樹的先序遍歷、中序遍歷、后序遍歷和層次遍歷的結(jié)果。葉子結(jié)點(diǎn): GHMJ非終端結(jié)點(diǎn): ABCDEF結(jié)點(diǎn)所在層次: A(1),B(2),C(2),D(3),E(3),F(3),G(4)H(4),J(4),M(4)樹的深度: 4先序：ABDGEHCFMJ中序：DGBEHACMFJ后序：GDHEBMJFCA層次：ABCDEFGHMJ 20、用快速排序方法對數(shù)據(jù)集23 45 12 90 78 56進(jìn)行排序，寫出快速排序第一趟的詳細(xì)過程，以及簡述后面的遞歸過程。23 45 12 90 78 5623 45 12 90 78 5623 45 12 90 78 5623 45 12 56

44、 78 9023 45 12 56 78 90(23 45 12 56) 78 (90)21、對于下面兩個(gè)圖，求出：（1）無向圖中每個(gè)頂點(diǎn)的度，有向圖中每個(gè)頂點(diǎn)的入度，出度和度。d(0)=4, d(1)=2, d(2)=3, d(3)=3, d(4)=2.d(0)+ = 2, d(0)- = 2, d(1)+ = 1, d(1)- = 2, d(2)+ = 1, d(2)- = 3d(3)+ = 2, d(3)- = 1, d(4)+ = 2, d(0)- = 0（2）畫出有向圖的鄰接距陣。（3）下面是否是連通圖或強(qiáng)連通圖，如果不是，畫出連通分量或強(qiáng)連通分量。403120124322、給出下列

45、AOV網(wǎng)的可能的拓?fù)渑判蛐蛄?。拓?fù)渑判蛐蛄惺欠裎ㄒ?？在什么情況下拓?fù)渑判驘o法完成。CDBAE或DCBAE或不唯一在含有回路的時(shí)候拓?fù)渑判驘o法完成 23、已知二叉樹的先序序列和中序序列分別為HDACBGFE和ADCBHFEG。（1）畫出該二叉樹（2）寫出其后序序列；ABCDEFGH24、已知帶權(quán)無向圖的鄰接表如下所示，其中邊表結(jié)點(diǎn)的結(jié)構(gòu)為： 依此鄰接表從頂點(diǎn)C出發(fā)進(jìn)行深度優(yōu)先遍歷。（1）畫出由此無向圖；（2）寫出遍歷過程中得到的從頂點(diǎn)C開始的可能的一個(gè)頂點(diǎn)序列。DCABEF五、算法閱讀題1、閱讀下面的算法typedef int Datatype;typedef Struct node Datat

46、ype data;Struct node *next;lklist;void delredundant(lklist *&head) lklist *p,*q,*s; for(p=head;p!=0;p=p->next) for(q=p->next,s=q;q!=0; ) if (q->data= =p->data) s->next=q->next; free(q);q=s->next; else s=q;q=q->next; 問：該算法的功能是什么? 2、閱讀下面的算法typedef int Datatype;typedef Struc

47、t node Datatype data;Struct node *lchild,*rchild; bitree;bitree *q20; int r=0,f=0,flag=0;void preorder(bitree *bt, char x) if (bt!=0 && flag= =0)if (bt->data= =x) flag=1; return;else r=(r+1)%20; qr=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); void parent(bitree *bt,char x) in

48、t i; preorder(bt,x); for(i=f+1; i<=r; i+) if (qi->lchild->data=x | qi->rchild->data) break; if (flag= =0) printf("not found xn"); else if (i<=r) printf("%c",bt->data); else printf("not parent");問：該算法的功能是什么？找到根節(jié)點(diǎn)到某個(gè)節(jié)點(diǎn)的路徑3、閱讀下面的算法int minnum=-32768, fl

49、ag=1;typedef Struct nodeint key; Struct node *lchild,*rchild;bitree;void inorder(bitree *bt) if (bt!=0) inorder(bt->lchild); if(minnum>bt->key) flag=0; minnum=bt->key; inorder(bt->rchild);問：該算法的功能是什么？找最小值4、已知一個(gè)算法設(shè)計(jì)如下：LinkList mynote(LinkList L) /L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針 if(L&&L->nex

50、t) q=L；L=L>next；p=L； S1： while(p>next) p=p>next； S2： p>next=q；q>next=NULL； return L； 問： （1）說明語句S1的功能 （2）說明語句組S2的功能 （3）設(shè)鏈表表示的線性表為（a1,a2, ,an）,寫出算法執(zhí)行后的返回值所表示的線性表5、已知一個(gè)算法設(shè)計(jì)如下：int unkown(JD r ,int n,int k) int low,high,mid,found; low=1; high=n; found=0; while(low<=high)&&(found

51、= =0) mid=(low+high)/2; if(k>rmid.key) low=mid+1; else if(k= =rmid.key) found=1; else high=mid-1; if(found= =1) return(mid); else return(0);問：該算法的功能是什么？二分查找關(guān)鍵字，若找到返回其下標(biāo)，若沒有找到返回06、已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，閱讀下面算法。 typedef Struct node DateType data； Struct node * next； ListNode； typedef ListNode * LinkList ；

52、 LinkList Leafhead=NULL； Void Inorder (BinTree T) LinkList s； If(T) Inorder(T>lchild)； If (!T>lchild)&&(!T>rchild) s=(ListNode*)malloc(sizeof(ListNode)； s>data=T>data； s>next=Leafhead； Leafhead=s； Inorder(T>rchild)； 對于如下所示的二叉樹  (1) 畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)；(2) 說明該算法的功能。中序建立線索二叉樹7、 已知一個(gè)算法設(shè)計(jì)如下：void ABC(BTNode * BT) if BT ABC (BT->left); ABC (BT->right); cout<<BT->data<<' ' 問：該算法的功能是什么？后序遍歷二叉樹8、已知一個(gè)算法設(shè)計(jì)如下：void unkown(JD r ,int n) int m,i,j,flag=1