數(shù)據(jù)結(jié)構(gòu)與算法 上海第二工業(yè)大學(xué) 二工大 期末考試 試卷.doc_第1頁
數(shù)據(jù)結(jié)構(gòu)與算法 上海第二工業(yè)大學(xué) 二工大 期末考試 試卷.doc_第2頁
數(shù)據(jù)結(jié)構(gòu)與算法 上海第二工業(yè)大學(xué) 二工大 期末考試 試卷.doc_第3頁
數(shù)據(jù)結(jié)構(gòu)與算法 上海第二工業(yè)大學(xué) 二工大 期末考試 試卷.doc_第4頁
數(shù)據(jù)結(jié)構(gòu)與算法 上海第二工業(yè)大學(xué) 二工大 期末考試 試卷.doc_第5頁
已閱讀5頁,還剩4頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

一、 選擇題: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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論