數(shù)據(jù)結(jié)構(gòu)試卷A開(kāi)一頁(yè)

1、復(fù)習(xí)題一、填空題(每空1分，共22分)1、 數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D, R)，其中D是 數(shù)據(jù)元素 的有限集合，R是D上的 關(guān)系有 限集合。2、一個(gè)算法的效率可分為 _時(shí)間效率和_空間效率。3、 向一個(gè)長(zhǎng)度為 n的向量的第i個(gè)元素(1 < i< n+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng)_n-i+1 個(gè)元素。4、 在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的_前一個(gè)_位置。5、 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元素。6、 向棧中壓入元素的操作是先移動(dòng)棧頂指針，后_存入元素。7、 不包含任何字符(長(zhǎng)度為0)的串稱為空串；由一個(gè)或多個(gè)空格(僅由空格符)組成的串 稱為空白串。8、

2、假設(shè)有二維數(shù)組 A6X8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。 A的 起始存儲(chǔ)位置(基地址)為 1000，那么數(shù)組A的體積(存儲(chǔ)量)為 288 B ;末尾元素A57的第 一個(gè)字節(jié)地址為1282 ;假設(shè)按行存儲(chǔ)時(shí)，元素 A14的第一個(gè)字節(jié)地址為(8+4) X 6+1000=1072 ; 假設(shè)按列存儲(chǔ)時(shí)，元素 A47的第一個(gè)字節(jié)地址為(6 X 7+ 4) X 6 + 1000)= 1276。9、 設(shè)一棵完全二叉樹(shù)具有 1000個(gè)結(jié)點(diǎn)，那么此完全二叉樹(shù)有_500個(gè)葉子結(jié)點(diǎn)，有499 個(gè) 度為2的結(jié)點(diǎn)，有_1_個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，有 _0個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。10、 線性有序表(a1，a

3、2，a3，a?56)是從小到大排列的，對(duì)一個(gè)給定的值 k，用二分法檢 索表中與k相等的元素，在查找不成功的情況下，最多需要檢索_8 _次。設(shè)有100個(gè)結(jié)點(diǎn)， 用二分法查找時(shí)，最大比擬次數(shù)是 _7_。11、散列法存儲(chǔ)的根本思想是由 關(guān)鍵字的值 決定數(shù)據(jù)的存儲(chǔ)地址。二、判斷題(每題1分，共10分)(X )9.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。(X ) 1.二叉樹(shù)中所有結(jié)點(diǎn)個(gè)數(shù)是 2k-1-1，其中k是樹(shù)的深度。(應(yīng)2i-1)(V ) 7.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。(X ) 2.二叉樹(shù)中所有結(jié)點(diǎn)，如果不存在非空左子樹(shù)，那么不存在非空右子樹(shù)

4、。X ) 3對(duì)于一棵非空二叉樹(shù)，它的根結(jié)點(diǎn)作為第一層，那么它的第i層上最多能有2i 1個(gè)結(jié)點(diǎn)。(應(yīng)2i-1)(X ) 3.鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算時(shí)機(jī)自動(dòng)地將后續(xù)的 各個(gè)單元向前移動(dòng)。(V ) 4.用二叉鏈表法(link-rlink )存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的 2n個(gè)指針區(qū)域中 有n+1個(gè)為空指針。(V ) 5.具有12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)。X ) 8.線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。(X ) 5.順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。三、單項(xiàng)選擇題(每題2分，共18 分)(C ) 1.數(shù)

5、據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí),物理地址與邏輯地址相同并且是連續(xù)的,稱之為:(A )存儲(chǔ)結(jié)構(gòu)(B)邏輯結(jié)構(gòu)(B ) 2.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是 址是(A ) 110( B) 108(C)順序存儲(chǔ)結(jié)構(gòu)100，每個(gè)元素的長(zhǎng)度為(C) 100( D)(D)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2, 那么第5個(gè)元素的地120(A ) 3.在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是0( 1)的操作是：A) 訪問(wèn)第i個(gè)結(jié)點(diǎn)(K i< n)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2< i < n)(B) 在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)( K iw n)(C) 刪除第i個(gè)結(jié)點(diǎn)(1w i w n)(D) 將n個(gè)結(jié)點(diǎn)從小到大排序(B )

6、 4.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要 移動(dòng)個(gè)元素(A.C.(A ) 8(B) 63.5( C) 63( D) 7A ) 4判定一個(gè)隊(duì)列QU (最多元素為m0)為滿隊(duì)列的條件是 QU->rear QU->fro nt = = m0QU->fro nt = = QU->rearBB. QU->rear QU->front 仁=mOD. QU->front = = QU->rear+1 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表；(C)星式6. 鏈表是一種采用(A )順序(B)鏈?zhǔn)?C)星式(D)網(wǎng)狀7. 線性表假設(shè)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)

7、，要求內(nèi)存中可用存儲(chǔ)單兀的地址(A)必須是連續(xù)的(C) 一定是不連續(xù)的& 線性表L在(A)需經(jīng)常修改L中的結(jié)點(diǎn)值(C)L中含有大量的結(jié)點(diǎn)9.假設(shè)一個(gè)棧的入棧序列是(B )局部地址必須是連續(xù)的(D)連續(xù)或不連續(xù)都可以 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。需不斷對(duì)L進(jìn)行刪除插入L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜 ,n,其輸出序列為 p1 , p2, p3,(B)(D)1 , 2, 3,C假設(shè)A. i四、1、略2、答：X= _116五、1、答：輸出為“ stack。2、答：輸出為“ char。六、解：方案1;哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹(shù)。w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)那

8、么:【(2,3), 6, (7,10)】,pn.)p1= n,那么 pi 為B. n=iC. n-i+1D.不確定Y= 0Z=100首址=_108末址=_112(100(40)1921(60)327"7)子母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10方案比擬:19, 21, 32(28)"( 11)10 6 '( 5)一 3子母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.

9、2181110.10方案 1 的 WPL = 2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案 2 的 WPL = 3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長(zhǎng)二進(jìn)制編碼六、閱讀分析題(10分)指出以下算法中的錯(cuò)誤和低效(即費(fèi)時(shí))之處，并將它改寫(xiě)為一個(gè)既正確又高效的算法。Status DeleteK(SqList&a, int i, int k)本過(guò)程從順序存儲(chǔ)結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素if ( i<1 |

10、 k<0 | i+k> a.length ) return INFEASIBLE;參數(shù)不合法elsefor(co unt = 1; count <k; count + ) 刪除一個(gè)元素for ( j = a.length; j>=i+1;j-) a.elemj-1 = a.elemj;a.len gth -;return OK; / DeleteK注：上題涉及的類型定義如下:# define LIST INIT SIZE 100# defi ne LISTINCREMENT 10typedef struct Elem Type *elem;Intlen gth;Intl

11、istsize;SqList;錯(cuò)誤有兩處:/存儲(chǔ)空間基址/當(dāng)前長(zhǎng)度/當(dāng)前分配的存儲(chǔ)容量 參數(shù)不合法的判別條件不完整。例如表長(zhǎng)為10，假設(shè)從第一位置(i=1)刪除10個(gè)元素(k=10),要求合理但會(huì)被判為非法。合法的入口參數(shù)條件為(0<i < a.length) A (0 < k< a.length-i)應(yīng)將 if ( i<1 | k<0 | i+k> a.length ) return INFEASIBLE改為：if ( ! (0<i < a.length) a (o < k< a.length-i) ) return INFE

12、ASIBLE第二個(gè)FOR語(yǔ)句中，元素前移的次序錯(cuò)誤。應(yīng)將for ( j = a.length;j>=i+1; j-) a.elemj-1=a.elemj;改為 for (j>=i+1; j = a.length; j+ ) a.elemj-1 = a.elemj; 一、填空題(每空1分，共15分)1. 向量、棧和隊(duì)列都是 _線性 _結(jié)構(gòu)，可以在向量的 任何位置插入和刪除元素；對(duì)于棧只能在 _棧頂_7插入和刪除元素；對(duì)于隊(duì)列只能在 _隊(duì)尾_插入和 _隊(duì)首_刪除2. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為_(kāi)棧頂_。不允許插入和刪除運(yùn)算的一端稱為棧底。3. 數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究

13、非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的 關(guān)系和運(yùn)算等的學(xué)科。4. 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)_表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與 _表長(zhǎng)和該元素在表中的位置 _有關(guān)。5. 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元素。8假設(shè)在有序線性表 a20上進(jìn)行折半查找，那么比擬一次查找成功的結(jié)點(diǎn)數(shù)為1；比擬兩次查找成功的結(jié)點(diǎn)數(shù)為_(kāi) 2;比擬四次查找成功的結(jié)點(diǎn)數(shù)為_(kāi) 8;平均查找長(zhǎng)度為3.7。解：顯然，平均查找長(zhǎng)度=O (log?n) <5次(25)。但具體是多少次，那么不應(yīng)當(dāng)按照公式ASL 上！|og2(n+1)來(lái)計(jì)算(即(21 Xlog 221 ) /20

14、 = 4.6次并不正確！)。因?yàn)檫@是在假設(shè)n =n2m-1的情況下推導(dǎo)出來(lái)的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為=(1 + 2 X2+ 4 X3 + 8X4 + 5 X5 )= 74 ; ASL = 74/20=3.7!二、 判斷正誤(判斷以下概念的正確性，并作出簡(jiǎn)要的說(shuō)明。)(每題1分，共10分)(X )1.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò)，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無(wú)關(guān)。(X ) 2.在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊(duì)列。(V ) 3.棧是一種對(duì)

15、所有插入、 刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。(V ) 4.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。 正確，都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。(X )5.線性表的邏輯順序與存儲(chǔ)順序總是一致的X ) 6.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。錯(cuò)，他們都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。(V ) 7.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。V ) 8.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出時(shí)機(jī)，應(yīng)把兩個(gè) 棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。(X ) 9

16、.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。錯(cuò)，后半句不對(duì)。(X) 10. 一個(gè)棧的輸入序列是 12345，那么棧的輸出序列不可能是12345。錯(cuò)，有可能。三、單項(xiàng)選擇題(每題1分，共20分)(C ) 1數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：(A )存儲(chǔ)結(jié)構(gòu)(B)邏輯結(jié)構(gòu)C ) 2假設(shè)一個(gè)棧的入棧序列是假設(shè)p1=n，那么pi為A. i B. n=i(C)順序存儲(chǔ)結(jié)構(gòu)(D)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1, 2, 3，n,其輸出序列為 p1, p2, p3，pn.C. n-i+1解釋：當(dāng)p1=n，即n是最先出棧的，根據(jù)棧的原理， 說(shuō)明了 )，那么輸入

17、順序必定是 1，2, 3，(假設(shè)不要求順序出棧，那么輸出序列不確定)(B ) 3、判定一個(gè)棧 ST (最多元素為 mO)A. ST->top<>0 B. ST->top=OD.不確定n必定是最后入棧的(事實(shí)上題目已經(jīng) n，那么出棧的序列是 n，3，2，1。為空的條件是C. ST->top<>mOD. ST->top=m0(B )4、設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角局部(如以下圖所示)按行 序存放在一維數(shù)組 B 1, n(n-1)/2 中，對(duì)下三角局部中任一元素ai,j(i< j),在一維數(shù)組B中下標(biāo)k的值是：A.i(i-1)

18、/2+j-1B. i(i-1)/2+j元素a1,1C. i(i+1)/2+j-11D. i(i+1)/2+ja2,1a2,2n,1an,nan,2n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為C ) 5.具有(A) log 2(n)( B) IL log 2(n)( C)oIL log 2(n)+1 (D ) log 2(n)+16.有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有條邊。7、89、答案：答案：答案：A =A. 5A=A =_B. 6C. 7C = _ D = _ C = D =_D. 8 E = D = E=_四、簡(jiǎn)答題(每題4分，共20分)1說(shuō)明線性表、棧與隊(duì)的異同點(diǎn)。劉答：相同點(diǎn)：都是線性結(jié)構(gòu)，

19、都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊 的線性表，即受限的線性表，只是對(duì)插入、刪除運(yùn)算加以限制。不同點(diǎn)：運(yùn)算規(guī)那么不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出 表LIFO ;隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)，隊(duì)列用于多道作業(yè)處理、指令存放及其他運(yùn)算等等。2.試寫(xiě)出如下圖的二叉樹(shù)分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。答：DLR:LDR:LRD :，例如， abba '和abcba '是回文， abcde'3假設(shè)正讀和反讀都相同的字

20、符序列為“回文和 ababab'那么不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請(qǐng)分析用線性表、堆棧和隊(duì)列等 方式正確輸出其回文的可能性？答：線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量(j-)從表尾開(kāi)始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。哪種方式最好，要具體情況具體分析。假設(shè)正文在機(jī)內(nèi)已是順序存儲(chǔ)，那么直接用線性表從 后往前讀取即可，或?qū)⒍褩ｍ旈_(kāi)到數(shù)組末尾，然后直接用POP動(dòng)作實(shí)現(xiàn)。(但堆棧是先減后壓還是)假設(shè)正文是單鏈表形式存儲(chǔ)，那么等同于隊(duì)列，需開(kāi)輔助空間，可以從鏈?zhǔn)组_(kāi)始入棧，全部 壓入后再依次輸出。4試比擬順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的

21、優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？ 答：順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰(邏輯與物理統(tǒng)一)；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲(chǔ)密度大(=1?),存儲(chǔ)空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩局部，一局部存放結(jié)點(diǎn)值，另一局部 存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度小(<1),存儲(chǔ)空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。假設(shè)線性表的長(zhǎng)度變化不大，且其主要操作是查找，那么采用順序表；假設(shè)線性表的長(zhǎng)度變化較大，且其主要操作是插入

22、、刪除操作，那么采用鏈表。5給定二叉樹(shù)的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I ；中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫(huà)出二叉樹(shù)B，并簡(jiǎn)述由任意二叉樹(shù) B的前序遍歷序列和中序遍歷序列求二叉樹(shù)B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹(shù)。然后由其左子樹(shù)的元素集合和右子樹(shù)的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，那么所有元素都將被唯一確定，問(wèn)題得解。DG FB E H五、閱讀理解(每題I5分，共20分。至少要寫(xiě)出思路)答：此題答案不唯一，但假設(shè)從已給定序

23、列中挑選，那么限制頗多。P結(jié)點(diǎn)，那么不必“順藤摸瓜，直接鏈 接即可。(4)S-> next=P-> next;(1)P-> next=S; Q=P;(11) P=L;(8) while(P->next!=Q)P=P->next;(10) P=Q;(4) S-> next=P-> next;P-> next=S;2、答：這是找結(jié)點(diǎn)后繼的程序。 共有3處錯(cuò)誤。注：當(dāng)rtag= 1時(shí)說(shuō)明內(nèi)裝后繼指針，可直接返回，第一句無(wú)錯(cuò)。當(dāng)rtag = 0時(shí)說(shuō)明內(nèi)裝右孩子指針，但孩子未必是后繼，需要計(jì)算。中序遍歷應(yīng)領(lǐng)先左再根再應(yīng)改為：while(!r-> Lt

24、ag)r=r-> Lchild;BiTree In Succ(BiTree q)/q是指向中序線索二叉樹(shù)上某個(gè)結(jié)點(diǎn)的指針，/本函數(shù)返回指向*q的后繼的指針。r=q->rchild;/應(yīng)改為 r=q ；if(!r->rtag)while(!r->rtag)r=r->rchild; / 應(yīng) 改 為 while(!r->Ltag) r=r->Lchild;return r;應(yīng)改為 return r->rchild ；1.寫(xiě)出以下程序段的輸出結(jié)果(隊(duì)列中的元素類型QElem Type為char)。void mai n( )Queue Q; In it Q

25、ueue (Q);Charx= ' e' ;y= ' c '；EnQueue (Q, ' h' Q;uEne (Q, ' r'"Queue (Q, y);DeQueue (Q,x); En Queue (Q,x);DeQueue (Q,x); EnQ ueue (Q, ' a');while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ;Prin tf(x);答：輸出為“ char。2.簡(jiǎn)述以下算法的功能(棧和隊(duì)列的元素類型均為int )。void algo3(Queue &Q)Stack S; int d;In itStack(S);wh