數(shù)據(jù)結(jié)構(gòu)與算法 上海第二工業(yè)大學(xué) 二工大 期末考試 試卷.doc

一、 選擇題：1、在數(shù)據(jù)結(jié)構(gòu)中，線(xiàn)性結(jié)構(gòu)中元素之間存在_關(guān)系。A: 一對(duì)一B: 一對(duì)多C: 多對(duì)一D: 多對(duì)多 2、數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的_和運(yùn)算等的學(xué)科。A: 結(jié)構(gòu)B: 關(guān)系C: 操作D: 算法3、算法分析的兩個(gè)主要方面是_。A: 空間復(fù)雜度和時(shí)間復(fù)雜度B: 正確性和簡(jiǎn)明性C: 可讀性和文檔性D: 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性4、順序表中邏輯上相鄰的節(jié)點(diǎn)其物理位置也_。A: 一定相鄰B: 不必相鄰C: 按某種規(guī)律排列D: 無(wú)要求5、在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行_。A: s-next=p-next; p-next=s;B: p-next=s-next; s-next=p;C: q-next=s; s-next=p;D: p-next=s; s-next=q;6、一個(gè)棧的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列是_。A: edcbaB: decbaC: dceabD: abcde7、循環(huán)隊(duì)列用數(shù)組A0,m-1存放其元素值，已知其頭尾指針?lè)謩e是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是_。A: (rear-front+m)%mB: rear-front+1C: rear-front-1D: rear-front8、關(guān)于空格串，下列說(shuō)法中正確的有_。A: 空格串就是空串B: 空格串是零個(gè)字符的串C: 空格串的長(zhǎng)度為零D: 空格串的長(zhǎng)度就是其包含的空格個(gè)數(shù)9、數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A85的起始地址為_(kāi)。A: SA+140B: SA+144C: SA+222D: SA+22510、對(duì)于一棵滿(mǎn)二叉樹(shù)，m個(gè)樹(shù)葉，n個(gè)節(jié)點(diǎn)，深度為h，則_。A: n=h+mB: h+m=2nC: m=h-1D: n=2h-111、具有65個(gè)結(jié)點(diǎn)的完全二叉樹(shù)其深度為_(kāi)。（根的層次號(hào)為1）A: 8B: 7C: 6D: 512、滿(mǎn)二叉樹(shù)_二叉樹(shù)。A: 一定是完全B: 不一定是完全C: 不是D: 不是完全13、將一棵有100個(gè)節(jié)點(diǎn)的完全二叉樹(shù)從上到下，從左到右依次對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)，根節(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的節(jié)點(diǎn)的左孩子編號(hào)為_(kāi)。A: 99B: 98C: 50D: 4814、如果T2是由森林T轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么T中結(jié)點(diǎn)的后序遍歷就是T2中結(jié)點(diǎn)的_。A: 先序遍歷B: 中序遍歷C: 后序遍歷D: 層次遍歷15、將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用_。A: 棧B: 隊(duì)列C: 鏈表D: 樹(shù)16、如果某二叉樹(shù)的前序?yàn)閟tuwv，中序?yàn)閡wtvs，那么該二叉樹(shù)的后序?yàn)開(kāi)。A: uwvtsB: vwutsC: wuvtsD: wutsv17、設(shè)有13個(gè)值，用它們組成一棵哈夫曼樹(shù)，則該哈夫曼樹(shù)中共有_個(gè)結(jié)點(diǎn)。A: 13B: 12C: 26D: 2518、按照二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有_種。A: 3B: 4C: 5D: 619、如圖所示的4棵二叉樹(shù)中，_不是完全二叉樹(shù)。A: B: C: D: 20、所謂稀疏矩陣指的是_。A: 零元素個(gè)數(shù)較多的矩陣B: 零元素個(gè)數(shù)占矩陣元素總個(gè)數(shù)一半的矩陣C: 零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)多于非零元素個(gè)數(shù)且分布沒(méi)有規(guī)律的矩陣D: 包含有零元素的矩陣二、序列(a,b,c,d,e)已存在靜態(tài)鏈表如下圖a，頭指針指向1號(hào)結(jié)點(diǎn)。請(qǐng)完成：1在靜態(tài)鏈表中標(biāo)出此序列的邏輯關(guān)系。2畫(huà)出依次執(zhí)行了b前插入f，刪除e，c后插入g操作后的新的靜態(tài)鏈表圖b。112c23e34a45d56b677圖a圖b三、已知一個(gè)稀疏矩陣如下：1給出它的三元組順序表表示2. 給出它逆置后的三元組順序表3.給出它的十字鏈表表示020000100000030000000040050006ijvijv A B四、對(duì)下圖的二叉樹(shù)完成如下要求：1寫(xiě)出該樹(shù)的深度2寫(xiě)出該深度的滿(mǎn)二叉數(shù)的總結(jié)點(diǎn)數(shù)3寫(xiě)出二叉樹(shù)的后序遍歷的序列4將二叉樹(shù)還原成森林 A B FC G H D I JE五、假設(shè)用于通信的電文僅由8個(gè)字母（AH）組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試用這8個(gè)字母進(jìn)行以下操作：1構(gòu)造一棵赫夫曼樹(shù)（左結(jié)點(diǎn)的權(quán)小于右結(jié)點(diǎn)的權(quán)）2求出帶權(quán)路徑的長(zhǎng)度3設(shè)計(jì)赫夫曼編碼（左分支為“0”，右分支為“1”）六、任意一棵有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，已知它有M個(gè)葉子結(jié)點(diǎn)。試證明非葉子結(jié)點(diǎn)中度數(shù)為2的有M-1個(gè)，其余的度數(shù)為1。七、簡(jiǎn)述以下算法的功能（棧和隊(duì)列的元素類(lèi)型為int）。void algo (Queue &Q) Stack S; int d; InitStack(S);While (!QueueEmpty(Q) DeQueue(Q,d); Push (S,d);While (!StackEmpty(S) Pop(S,d); EnQueue (Q,d);八、算法題：1、設(shè)計(jì)一個(gè)算法按層次輸出二叉樹(shù)中的所有結(jié)點(diǎn)，要求同一層次的從左向右輸出（存儲(chǔ)按二叉樹(shù)表）。2、已知一單鏈表，頭指針為h，指向表頭結(jié)點(diǎn)，請(qǐng)寫(xiě)出算法對(duì)此單鏈表就地逆轉(zhuǎn)。（h仍舊為逆轉(zhuǎn)后的單鏈表的頭指針指向表頭結(jié)點(diǎn)）。注：逆轉(zhuǎn)為：原單鏈表的序列為（a1,a2an），則逆轉(zhuǎn)后為（an,an-1,a1）3、寫(xiě)一算法，實(shí)現(xiàn)統(tǒng)計(jì)帶表頭的單鏈表中元素值為奇數(shù)的接點(diǎn)個(gè)數(shù)。九、已知線(xiàn)性鏈表如下圖，頭指針為L(zhǎng)a，寫(xiě)出語(yǔ)句序列使左圖中的指針指向改成右圖中的指針指向。a b c La a b c La 十、在一個(gè)C語(yǔ)言程序中，有結(jié)構(gòu)類(lèi)型STUDENT的定義和結(jié)構(gòu)數(shù)組allstudents的聲明如下：struct STUDENT char name8; int number;STUDENT allstudents1050; allstudents是一個(gè)二維數(shù)組，它的每個(gè)元素都是包含name和number的結(jié)構(gòu)類(lèi)型。已知在C語(yǔ)言中，二維數(shù)組使用以行序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)，char類(lèi)型占用1字節(jié)，int類(lèi)型占用4字節(jié)。 假定allstudents在內(nèi)存中的起始存儲(chǔ)位置是2000，請(qǐng)寫(xiě)出計(jì)算allstudentsij的存儲(chǔ)位置的算式，并計(jì)算allstudents35的存儲(chǔ)位置。十一、用下標(biāo)從0到4的一維數(shù)組存儲(chǔ)一個(gè)循環(huán)隊(duì)列，目前其中有兩個(gè)元素A、B，狀態(tài)如圖(a)。如果此后有17個(gè)數(shù)據(jù)元素C、D、P、Q、R、S依次進(jìn)隊(duì)列，其間又有16個(gè)元素先后出隊(duì)列，請(qǐng)?jiān)趫D(b)中填寫(xiě)隊(duì)列最后的狀態(tài)，包括其中的元素和指針的位置。rearBfrontA (a) (b)十二、附加題：1、Josephus問(wèn)題是下面的游戲：N個(gè)人從1到N編號(hào)，圍坐成一個(gè)圓圈。從1號(hào)開(kāi)始傳遞一個(gè)熱土豆。經(jīng)過(guò)M次傳遞后拿著熱土豆的人被清除離座，圍坐的圓圈縮小，由坐在被清除的人后面的人拿土豆繼續(xù)進(jìn)行游戲。最后剩下的人取勝。因此，如果M=0和N=5，則依次被清除的人的順序是2，4，1，5。a.寫(xiě)一個(gè)算法思想解決M和N在一般值下的Josephu