本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題目202312是非題：

1．?dāng)?shù)據(jù)項是數(shù)據(jù)的基本單位。F2．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位。F

3．?dāng)?shù)據(jù)在計算機內(nèi)的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)。T

4．算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中兩者是通用的。F

5．線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有一致的特性，因此是屬于同一數(shù)據(jù)對象。T

6．線性表的鏈式存儲結(jié)構(gòu)的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素。F7．在線性表的順序存儲結(jié)構(gòu)中，規(guī)律上相鄰的兩個元素但在物理位置上并不一定相鄰。F8．順序存儲方式只能用于存儲線性結(jié)構(gòu)。T

9．取線性表的第i個元素的時間同i的大小有關(guān)。T10．11．12．

若入棧序列為1，2，3，4，則4，2，3，1不可能是一個出棧序列。F若入隊序列為1，2，3，4，則4，3，2，1是一個出隊序列。F

求最小代價生成樹（MST）時，Prim算法適合于稀疏網(wǎng)，Kruskal算法適合于稠密

網(wǎng)。F13．

線性表可以看成是廣義表的特例，若廣義表中的每個元素都是原子，則廣義表便成

為線性表。F14．15．16．17．18．

用一維數(shù)組存儲二叉樹時，總是以先序遍歷存儲結(jié)點。T

已知二叉樹的先序遍歷和后序遍歷序列可以唯一的確定一棵二叉樹。n個頂點的連通圖至少n-1條邊。T

先根遍歷樹和先序遍歷與該樹對應(yīng)的二叉樹，其結(jié)果不同。F

設(shè)有兩個串p和q，其中q是p的子串，把q在p中首次出現(xiàn)的位置作為子串q在

p中的位置的算法稱為匹配。T19．20．

哈夫曼樹是帶權(quán)路徑長度最短的樹，路經(jīng)上權(quán)值較大的結(jié)點離根較近。F連通分量是無向圖中的微小連通子圖。F

選擇題

1．?dāng)?shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的______以及它們之間的相互關(guān)系。CA.抽象結(jié)構(gòu)和理想結(jié)構(gòu)B.物理結(jié)構(gòu)和理想結(jié)構(gòu)C.物理結(jié)構(gòu)和規(guī)律結(jié)構(gòu)D.物理結(jié)構(gòu)和抽象結(jié)構(gòu)2．計算機算法是指______。C

A．計算方法B．排序方法C．解決問題的步驟序列D．調(diào)度方法3．算法的時間繁雜度取決于______。A

A．問題的規(guī)模B．待處理數(shù)據(jù)的初態(tài)C．A與B都對D．算法的易讀性4．被計算機加工的數(shù)據(jù)元素不是孤立無關(guān)的，它們彼此之間一般存在著某種聯(lián)系。尋常將數(shù)據(jù)元素之間的這種聯(lián)系稱為______。A.規(guī)則B.集合C.結(jié)構(gòu)D.運算5．線性表是________。A

A.一個有限序列，可以為空B.一個有限序列，不能為空C.一個無限序列，可以為空D.一個無限序列，不能為空6．線性表采用鏈式存儲時，其地址______。D

A.必需是連續(xù)的B.部分地址必需是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以7．對于順序存儲的線性表，設(shè)其長度為n，在任何位置上插入或刪除操作都是等概率的。刪除一個元素時所需移動元素次數(shù)的期望值為______。C

A.n/2B.(n+1)/2C.(n-1)/2D.n

8．設(shè)單鏈表中指針p指向結(jié)點A之前，若要插入一結(jié)點S在A之前，則需修改指針的操作為________。A

A．S->next=p->next;p->next=S;B．p->next=S;S->next=p->next;C．p=p->next->nextD．S->next=p->next;

9．設(shè)單鏈表中指針p指向結(jié)點A，若要刪除A之后的結(jié)點（若存在），則需修改指針的操作為________。

A．p->next=p->next->nextB．p=p->nextC．p=p->next->nextD．p->next=p10．當(dāng)一棵有n個結(jié)點的二叉樹按層次從上到下，同層次從左到右將數(shù)據(jù)存放在一維數(shù)組A[1..n]中時，數(shù)組中第i個結(jié)點假使有左孩子，那么其左孩子結(jié)點為________。A．A[2i](2i=i;j--)S;

4．從任何一個結(jié)點開始都能成功查找其它結(jié)點的單鏈表是表。

5．有一個帶有頭結(jié)點的循環(huán)單鏈表，頭指針為head,則判斷其為空的條件為：。

6．設(shè)棧S和隊列Q的初始狀態(tài)為空，元素a,b,c,d,e,f依次通過棧S，一個元素出棧后即進入隊列Q。若這6個元素出隊列的順序是b,d,c,f,e,a,則棧S的容量至少應(yīng)當(dāng)是。

7．設(shè)SS[1..maxsize]為一個順序存儲的棧，變量top指示棧頂元素的位置，當(dāng)棧未滿時，將元素e壓入棧需執(zhí)行以下語句：和。8．設(shè)廣義表L=（（（a））），則該廣義表的長度是，深度是。9．一個n*n的對稱矩陣，假使以一致的元只存儲一次的原則進行壓縮存儲，則其壓縮后的存儲容量為。10．設(shè)n行n列的上三角矩陣A已壓縮存儲到一維數(shù)組B[1..n(n+1)/2]中，且按行為主序存儲，則aij（i,j=1,2,…,n，且i>=j）對應(yīng)的B中的存儲位置為。11．有向圖G有n個頂點{v1,v2,…,vn}，它的鄰接矩陣為A，A[i,j]=1表示vi到vj存在鄰接關(guān)系，而A[i,j]=0表示不存在鄰接關(guān)系。則G中頂點vi的出度為。12．若一個二叉樹含有n個結(jié)點，則它的二叉鏈表中必有個空的鏈域。13．若一個三叉樹含有n個結(jié)點，則它的三叉鏈表中必有個空的鏈域。14．一棵有n(n>=1)個結(jié)點的d度樹，若用多重鏈表表示，樹中每個結(jié)點都有d個鏈域，則在樹的nd個鏈域中，有_______個是空鏈域，只有_______個是非空鏈域。15．若某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總的結(jié)點數(shù)是。16．若一個二叉樹的葉子結(jié)點，是某子樹的中序遍歷序列中的最終一個結(jié)點，則它必是該子樹的序列中的最終一個結(jié)點。17．一棵有n0個葉子結(jié)點的哈夫曼樹上，其結(jié)點總數(shù)為_______。18．Dijkstra最短路徑算法從源點到其余各頂點的最短路徑長度按次序產(chǎn)生。19．下面的算法將一個帶頭結(jié)點的單鏈表la分解為兩個鏈表la，lb，使得la表中含有原表中的奇數(shù)項的結(jié)點，而lb表中含有偶數(shù)項的結(jié)點，且保持結(jié)點原有的相對順序，請補充完整。

voiddisab(LinkListr=lb;p=la->next;

while(p!=NULL__________;r->next=q;r=q;

p=p->next;}

r->next=NULL;}//disab20．判斷帶頭結(jié)點的雙向循環(huán)鏈表S是否對稱相等的算法如下所示，請?zhí)羁昭a充完整。雙向循環(huán)鏈表的存儲結(jié)構(gòu)為：typedefstructDuLNode{ElemTypedata;

structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList;intfunction(DuLinkLists){

DuLinkListp,q;intj=1;p=s->next;q=s->prior;

while(p!=q__________;}elsej=0;returnj;}

解答題

1．設(shè)循環(huán)隊列的容量為70(序號從1到70)，現(xiàn)經(jīng)過一系列的入隊與出對運算后，有:(1)front=14,rear=21;(2)front=23,rear=12。

問在這兩種狀況下，循環(huán)隊列中各有多少個元素？

2．給定一個稀疏矩陣如下,用快速轉(zhuǎn)置實現(xiàn)該稀疏矩陣的轉(zhuǎn)置，寫出轉(zhuǎn)置前后的三元組表及開始的每一列第一個非零元的位置position[col]的值。

110001006502300600000500407800800000700000?90000008600200099033883．若一棵二叉樹先序遍歷序列為ABDEHCFGI，中序遍歷序列為DBEHAFCIG，試畫出這棵二叉樹。

4．將算術(shù)表達式((a+b)+c*(d+e)+f)*(g+h)轉(zhuǎn)化為二叉樹。(注：括號無需在樹中出現(xiàn))。5．假設(shè)字符a，b，c，d，e出現(xiàn)的概率分別為：14%，10%，12%，46%，18%，求每個字符對應(yīng)的哈夫曼編碼。

6．已知一棵度為m的樹中有：n1個度為1的結(jié)點，n2個度為2的結(jié)點，……，nm個度為m的結(jié)點，計算該樹中共有多少葉子結(jié)點?有多少非終端結(jié)點？7．畫出和以下二叉樹對應(yīng)的森林。

ABCDFEGHIJK8．一有向圖如下圖所示：(1)求每個頂點的入度和出度；(2)給出其鄰接矩陣。

1243

9．畫出表長為15的折半查找判定樹，并求出在查找概率相等狀況下ASL成功的值。10．設(shè)待排序記錄的關(guān)鍵字序列為：（48，95，27，84，05，12，73），請給出快速排序的過程。

56算法設(shè)計

1．(1)設(shè)計一個算法，求出帶有頭結(jié)點的線性鏈表中數(shù)據(jù)域值為x的結(jié)點序號。該序

號應(yīng)從鏈表的第一個數(shù)據(jù)結(jié)點算起，若鏈表中無此結(jié)點則序號為0。

(2)設(shè)計一算法實現(xiàn)將兩個遞增單鏈