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

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