數(shù)據(jù)結(jié)構(gòu)試卷及答案2套

1、頁眉內(nèi)容數(shù)據(jù)結(jié)構(gòu)試卷1一、單項(xiàng)選擇題：(每小題2分，共20分)1 .在一個(gè)長度為n的順序表中順序搜索一個(gè)值為x的元素時(shí)，在等概率的情況下，搜索成功時(shí)的數(shù)據(jù)平均比較次數(shù)為。A.nB.n/2C.(n+1)/2D.(n-1)/22 .不帶頭結(jié)點(diǎn)的單鏈表first為空的判定條件是。A.first->next=NULL;B.first=NULL;C.first->next=first;D.first!=NULL;3 .棧的插入和刪除操作在進(jìn)行。A.棧頂B.棧底C.任意位置D.指定位置4 .假定一個(gè)鏈?zhǔn)疥?duì)列的隊(duì)頭和隊(duì)尾指針分別為front和rear,則判斷隊(duì)空的條件為A.front=rearB

2、.front!=NULLC.rear!=NULLD.front=NULL5 .設(shè)有一個(gè)廣義表A(x,(a,b),(x,(a,b),y)，運(yùn)算Head(Head(Tail(A)的執(zhí)行結(jié)果為。A.yB.(a,b)C,(x,(a,b)D.x6 .在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于。A.nB.n-1C.n+1D.2*n7 .利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)重，生成的霍夫曼樹中共包含有個(gè)結(jié)點(diǎn)。A.nB.n+1C.2*nD.2*n-18 .設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有條邊。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)9 .任何一個(gè)無向連通圖的最小生成樹。A.只有一

3、棵B.一棵或多棵C.一定有多棵D.可能不存在10 .從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為排序法。A.選擇B.二路歸并C.交換D.插入二、填空題(每空1分，共20分)1 .數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的以及它們之間的和運(yùn)算等的學(xué)科。2 .順序表中邏輯上相鄰的元素的物理位置相鄰。單鏈表中邏輯上相鄰的元素的物理位置相鄰。3 .在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由指示。4 .是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性3表。5 .設(shè)有二維數(shù)組A0.19,0.10，其每個(gè)

4、元素占兩個(gè)字節(jié)，第一個(gè)元素的存儲(chǔ)地址為1000,若按行優(yōu)先順序存儲(chǔ)，則元素A4,6的存儲(chǔ)地址為，按列優(yōu)順序存儲(chǔ)，元素A4,6的存儲(chǔ)地址為。6 .按照二叉樹的定義，有3個(gè)結(jié)點(diǎn)的二叉樹有種形態(tài)。7 .具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。8 .含有n個(gè)頂點(diǎn)e條邊的無向連通圖，利用Kruskal算法生成最小代價(jià)生成樹其時(shí)間復(fù)雜度為,利用Prim算法生成最小代價(jià)生成樹時(shí)間復(fù)雜度為。9 .從有序表(12,18,30,43,56,78,82,95)中折半查找元素56時(shí)，其查找長度為。10 .快速排序在平均情況下的時(shí)間復(fù)雜度為，在最壞情況下的時(shí)間復(fù)雜度為三、應(yīng)用題(每小題5分，共30分)1 .輸

5、入下列整數(shù)序列，17,31,13,11,20,35,25,8,4,11,24,40,27,畫出建立的二叉排序樹，最后分別圖示將9插入，86刪除后的二叉排序樹。2 .已知二叉樹T的中序遍歷序列為DIGJLKBAECHF后序遍歷序列為ILKJGDBEHFCA,請畫出該二叉樹，并寫出先序序列。3 .對于如圖1所示的有向圖，試給出(1)每個(gè)頂點(diǎn)的入度和出度；(2)鄰接矩陣；鄰接表；4 .試對圖2所示的AOE網(wǎng)絡(luò)，解答下列問題。(1)求每個(gè)事件的最早開始時(shí)間Ve(i)和圖2,寫出a,b,c,d,e,f,g 的Huffman編碼(在構(gòu)造最遲開始時(shí)間Vl(i)。(2)求每個(gè)活動(dòng)的最早開始時(shí)間e()和最遲開始

6、時(shí)間l()。(3)確定哪些活動(dòng)是關(guān)鍵活動(dòng)。畫出由所有關(guān)鍵活動(dòng)構(gòu)成的圖，指出哪些活動(dòng)加速可使整個(gè)工程提前完成。5 .字符a,b,c,d,e,f,g的使用頻度分另I是0.07,0.09,0.12,0.22,0.20,0.27,0.03哈夫曼樹時(shí)，要求左子樹根結(jié)點(diǎn)的權(quán)值小于等于右子樹根結(jié)點(diǎn)的權(quán)值)。6 .設(shè)哈希函數(shù)H(K尸k%13,給定鍵值序列為87,25,31,8,27,13,68,95,18,12,70,63,47,處理沖突的方法為線性探測再散列，試在018的散列地址空間中對該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算該表的成功查找的平均查找長度。頁眉內(nèi)容四、算法設(shè)計(jì)題（每小題10分，共30分）1 .已知單鏈

7、表L中的元素有序，寫一算法，刪除其重復(fù)結(jié)點(diǎn)，即實(shí)現(xiàn)如圖3的操作。（a）為刪除前，（b）為刪除后。H*|十|l0IwXjH*|l5I|l5I|l8IA1Hr|十|l0IIl5I|l8IA|圖3刪除重復(fù)結(jié)點(diǎn)2 .編寫遞歸算法，求二叉樹中以元素值為x的結(jié)點(diǎn)為根的子樹的深度。3 .編寫一個(gè)雙向起泡的排序算法，即相鄰兩遍向相反方向起泡。頁眉內(nèi)容數(shù)據(jù)結(jié)構(gòu)試卷2一、單項(xiàng)選擇題(從下列各題四個(gè)備選答案中選出一個(gè)正確答案，每小題2分，共20分)1. 算法分析的兩個(gè)主要方面是()A. 空間復(fù)雜性和時(shí)間復(fù)雜性B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性2在以下的敘述種正確的是()A.線性表的順序存

8、儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B. 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C. 棧的操作方式是先進(jìn)先出D. 隊(duì)列的操作方式是后進(jìn)先出3. 循環(huán)隊(duì)列用數(shù)組A0,m-1存放其元素值，已知其頭尾指針分別是front和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是()A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front4. 帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是()A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL5. 在雙循環(huán)鏈表的p指針?biāo)附Y(jié)點(diǎn)之后插入s指針?biāo)附Y(jié)點(diǎn)的操作是()。

9、A.p->next=s;s->priou=p;p->next->priou=s;s->next=p->nextB.p->next=s;p->next->priou=s;s->priou=p;s->next=p->nextC.s->priou=p;s->next=p->next;p->next=s;p->next->priou=s;D.s->priou=p;s->next=p->next;p->next->priou=s;p->next=s;6. 稀疏矩

10、陣一般的壓縮存儲(chǔ)方法有兩種，即()A.二維數(shù)組和三維數(shù)組表B.三元組和散列C.三元組表和十字鏈表D.散列和十字鏈表7. 廣義表A=(a,b,(c,d),(e,(f,g),則下面式子的值為()；Head(Tail(Head(Tail(Tail(A)A(g)B.(d)C.cD.d8. 有分別帶權(quán)為9，2，5，7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為()A.23B.37C.44D.469. 有拓?fù)湫蛄械膱D一定是()。A.有環(huán)圖B.無向圖C.強(qiáng)連通圖D.有向無環(huán)圖10.利用逐點(diǎn)插入法建立序列(50,72,43,85,75,20,35,45,65,30)對應(yīng)的二叉排序樹以后，查找元素35要

11、進(jìn)行()元素間的比較。A.4次B.5次C.7次D.10次二、填空(每空1分，共20分)1 .長度為n的順序表，插入和刪除元素的時(shí)間復(fù)雜性為;順序存儲(chǔ)的棧和隊(duì)列，插入和刪除元素的時(shí)間復(fù)雜性為。2 .非空單循環(huán)鏈表L中，指針p所指結(jié)點(diǎn)是尾結(jié)點(diǎn)的條件是。3 .在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)由指針s所指結(jié)點(diǎn)，應(yīng)執(zhí)行s->next=;和p->next=的操作。4 .有n個(gè)結(jié)點(diǎn)的樹，則該樹中所有結(jié)點(diǎn)的度之和為。5 .設(shè)有二維數(shù)組A0.9,0.19，其每個(gè)元素占兩個(gè)字節(jié)，第一個(gè)元素的存儲(chǔ)地址為100,若按行優(yōu)先順序存儲(chǔ)，則元素A4,6的存儲(chǔ)地址為，按列優(yōu)順序存儲(chǔ)，元素A4,6的存儲(chǔ)地址為。

12、6 .試找出滿足下面條件的所有二叉樹：前序序列和中序序列相同;中序序歹”和后序序歹"相同O7 .二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，在有n(n>0)個(gè)結(jié)點(diǎn)的二叉樹中，空鏈域的個(gè)數(shù)為8 .假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18,則它的最小高度為,最大高度為。9 .一個(gè)連通圖的生成樹是一個(gè)連通子圖，n個(gè)頂點(diǎn)的生成樹有條邊。10 .具有n個(gè)頂點(diǎn)的無向完全圖，邊的總數(shù)為條；而在n個(gè)頂點(diǎn)的有向完全圖中，邊的總數(shù)為條。11 .設(shè)s='IAMASTUDENT,t='GOOD,q='WORKER;數(shù)SubString(s,5,7)的值為;函數(shù)Index(s,t)的值為;函數(shù)Replace

13、(s,'STUDENT四)值為三、回答下列問題(14題每題5分，5題10分，共30分)1 .已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ,中序遍歷的結(jié)果是EBCDAFHIGJ,試畫出這棵二叉樹。2 .假設(shè)字符a,b,c,d,e,f的使用頻度分別是0.07,0.09,0.12,0.22,0.23,0.27,構(gòu)造哈夫曼樹，并求a,b,c,d,e,f的Huffman(哈夫曼)編碼。3 .對如圖1,用prim算法構(gòu)造一棵最小生成樹，寫出構(gòu)造過程。4 .設(shè)哈希函數(shù)為H(k)=kMOD13,用線性探測法解決沖突，請畫出在012的哈?？臻g中，對于關(guān)鍵字序列32,17,10,73,45,89,92,36,80,27,19,58構(gòu)造哈希表,并計(jì)算在等5概率情況下的平均查找長度。5.試對右圖所示的AOE網(wǎng)絡(luò)，解答下列問題。(1)這個(gè)工程最早可能在什么時(shí)間結(jié)束。(2)求每個(gè)事件的最早開始時(shí)間Ve(i)和最遲開始時(shí)間Vl(i)。(3)求每個(gè)活動(dòng)的最早開始時(shí)間e()和最遲開始時(shí)間1()。(4)確定哪些活動(dòng)是關(guān)鍵活動(dòng)。畫出