【文章內(nèi)容簡介】 60。 。答案：r=f、(r+1)%m=f27．在具有n個單元的循環(huán)隊列中，隊滿時共有_______個元素。答案：28．深度為 n(n0) 的二叉樹最多有 _______________ 個結(jié)點。答案：29．n(n0) 個結(jié)點、 (n1) 條邊的連通無向圖中，頂點度數(shù)最大值為 _______________ 。答案：30．一棵深度為6的滿二叉樹有______個非終端結(jié)點。答案：31．若一棵二叉樹中有8個度為2的結(jié)點,則它有_____個葉子。答案：32．樹中結(jié)點A的 ____________________ 稱為結(jié)點A的度。答案：33．一棵深度為4的二叉樹最多有 _______ 個結(jié)點。答案：34．將 轉(zhuǎn)化為二叉樹時，其根結(jié)點的右子樹總是空的。答案：35．哈夫曼樹是帶權(quán)路徑長度 的樹，通常權(quán)值較大的結(jié)點離根結(jié)點 。答案：36．具有n個葉子的二叉樹，每個葉子的權(quán)值為wi(1≤i≤n)其中帶權(quán)路徑最小的二叉樹被稱為 。答案：37．若已知一棵二叉樹的先序序列為 – + a * b – c d / e f，中序序列為a + b * c – d – e / f，則其后序序列為___________。答案：38．已知一棵完全二叉樹中共有768結(jié)點，則該樹中共有_____個葉子結(jié)點。答案：39．已知二叉樹有50個葉子結(jié)點，且僅有一個孩子的結(jié)點數(shù)為30，則總結(jié)點數(shù)為 。答案：40．具有10個頂點的無向圖,邊的總數(shù)最多為 _____________ 。答案：41．在有n個頂點的有向圖中，每個頂點的度最大可達 。答案：42．有向圖g用鄰接矩陣a［１…m,1…m］來存儲，其第i行的所有元素之和等于頂點i的　　　。答案：43．有n個球隊參加的足球聯(lián)賽按主客場制進行比賽，共需進行 場比賽。答案：44．帶權(quán)連通圖G=V,E，其中V={v1,v2,v3,v4,v5,},E={(v1,v2)7,(v1,v4)6，(v1,v4)9，(v2,v3)8，(v2,v4)4，(v2,v5)4，(v3,v4)6，(v4,v5)2，(注：頂點偶對右下角的數(shù)據(jù)為邊上的權(quán)值)，G的最小生成樹的權(quán)值之和為__________________ 。答案：45．順序查找n個元素的順序表,當使用監(jiān)視哨時,若查找成功,比較關(guān)鍵字的次數(shù)至少為___次, 最多為____次；若查找失敗,比較關(guān)鍵字的次數(shù)為____次。答案：46．在單鏈表上難以實現(xiàn)的排序方法有 、 和 。答案：快速排序、堆排序、希爾排序 五、簡答題/問答題/綜述題1．什么是順序表？順序表的特點是什么？答案：線性表的順序存儲是指在內(nèi)存中用一塊地址連續(xù)的存儲空間順序存放線性表的各元素，用這種形式存儲的線性表稱為順序表。數(shù)據(jù)元素在順序表中物理位置取決于數(shù)據(jù)元素在線性表中的邏輯位置，可得出順序表的特點：邏輯位置相鄰，其物理位置也相鄰。2．什么樣的圖是連通圖？答案：在無向圖G中，如果從一個頂點vi到另一個頂點vj(i≠j)有路徑，則稱頂點vi和頂點vj是連通的，若圖中任意兩頂點間都是相通的，則稱此圖是連通圖。3．二叉樹有哪幾種基本形態(tài)? 畫圖說明之。答案：六、操作題/綜合能力題1．若對序列(76，38，65，13，97，27，50，49)采用冒泡排序法(按照值的大小從小到大)進行排序，共需幾趟排序？請分別在下表中寫出每一趟的結(jié)果：原始序列 76 38 65 13 97 27 50 49答案：共需5趟第1趟結(jié)果 38 65 13 76 27 50 49 97第2趟結(jié)果 38 13 65 27 50 49 76 97第3趟結(jié)果 13 38 27 50 49 65 76 97第4趟結(jié)果 13 27 38 49 50 65 76 97第5趟結(jié)果 13 27 38 49 50 65 76 972．若對序列(76，38，65，13，97，27，50，49)采用選擇排序法(按照值的大小從小到大)進行排序，請分別在下表中寫出每一趟的結(jié)果：原始序列 76 38 65 13 97 27 50 49答案：第1趟結(jié)果 76 38 65 13 49 27 50 97第2趟結(jié)果 50 38 65 13 49 27 76 97第3趟結(jié)果 50 38 27 13 49 65 76 97第4趟結(jié)果 49 38 27 13 50 65 76 97第5趟結(jié)果 13 38 27 49 50 65 76 97第6趟結(jié)果 13 27 38 49 50 65 76 97第7趟結(jié)果 13 27 38 49 50 65 76 973．把 1 、 2 、 3 、 4依次進棧（棧初始為空），任何時刻（只要棧不空），都可以出（退）棧，試寫出所有可能的出棧序列（如 1234 ）。 答案：4．若一二叉樹有 2 度結(jié)點 100個，則其葉結(jié)點有多少個？該二叉樹可以有多少個 1 度頂點？答案：5．已知某非空二叉排序樹采用順序存儲結(jié)構(gòu)依次將所有結(jié)點的數(shù)據(jù)信息存放于一維數(shù)組ABDIC□EF□□C□□□H，請分別寫出該二叉樹的前序遍歷序列與中序遍歷序列。答案：6．二叉樹的順序存儲結(jié)構(gòu):答案：7．給定30個字符組成的電文:D D D D D A A A B E E A A F C D A A C A B B C C C B A A D D試為字符 A、B、C、D、E、F 設(shè)計哈夫曼(Huffman)編碼。 (1)畫出相應(yīng)的哈夫曼樹； (2)分別列出 A、B、C、D、E、F 的哈夫曼碼；(3)計算該樹的帶權(quán)路徑長度WPL。答案：8．試將森林 F={ T1,T2,T3,T4 }轉(zhuǎn)換為一棵二叉樹。 T1 T2 T3 T4答案：9．試畫出下列二叉樹的中序線索二叉樹存儲結(jié)構(gòu)圖。 二叉樹答案：10．試用孩子兄弟(左孩子右兄弟)表示法畫出下列樹的存儲結(jié)構(gòu)圖。 樹答案：11．已知二叉樹的前序遍歷序列和中序遍歷序列分別是：B,A,C,D,F,E,G和D,C,A,F,G,E,B, 試畫出該二叉樹。答案：12．試用雙親表示法畫出下列樹T的存儲結(jié)構(gòu)圖。答案：13．假定后序遍歷二叉樹的結(jié)果是A,C,B(1)試畫出所有可得到這一結(jié)果的不同形態(tài)的二叉樹；(2)分別寫出這些二叉樹的中序遍歷序列。答案：14．有9個帶權(quán)結(jié)點 a、b、c、d、e、f、g、h、I，分別帶權(quán) 4，2，7，12，6，10，5，9，3，試以他們?yōu)槿~子結(jié)點構(gòu)造一棵哈夫曼樹（請按照左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)的次序構(gòu)造）。答案：15．某二叉樹的結(jié)點數(shù)據(jù)采用順序存儲表示如下：(1) 試畫出此二叉樹的圖形表示。(2) 寫出結(jié)點D的雙親結(jié)點及左、右子女。(3) 將此二叉樹看作森林的二叉樹表示，試將它還原為森林。答案：16．圖的鄰接矩陣:答案：17．有向圖的逆鄰接表: 答案：18．找出下面網(wǎng)絡(luò)的最小生成樹。 答案：19．找出下面網(wǎng)絡(luò)的最小生成樹:答案：20．試畫出下列圖的鄰接表。 圖答案：21．對下面的帶權(quán)無向圖采用prim算法從頂點 ① 開始構(gòu)造最小生成樹。（寫出加入生成樹頂點集合S和選擇邊Edge的順序）S:頂點號Edge:(頂點，頂點，權(quán)值)①( ， ， )①( ， ， )① ( ， ， )①( ， ， )①( ， ， )① 答案：5462311015410304101522022．對圖所示有向圖，試用Dijkstra算法求出從源點1到其它各頂點的最短路徑，并寫出執(zhí)行算法過程中擴充結(jié)點的每次循環(huán)狀態(tài)。答案：23．已某個不帶權(quán)的無向圖采用鄰接矩陣存儲方法依次將頂點的數(shù)據(jù)信息存放于一維數(shù)組ABCDEFGH中，邊的信息存放于鄰接矩陣中，鄰接矩陣為0 1 1 0 0 0 0 01 0 0 0 1 0 1 11 0 0 1 0 1 0 00 0 1 0 0 1 0 00 1 0 0 0 0 0 10 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 請寫出從頂點A出發(fā)對該圖進行深度有限搜索后得到的頂點序列。答案：24．試按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 將所有元素插入一棵初始為空的二叉排序樹中, 使之仍是一棵二叉排序樹。 (1)試畫出插入完成之后的二叉排序樹； (2)若查找元素17,它將依次與二叉排序樹中哪些元素比較大小? (3)假設(shè)每個元素的查找概率相等,試計算該樹的平均查找長度ASL。 (4)對該樹進行中序遍歷,試寫出中序遍歷序列。答案：25．已知一關(guān)鍵字序列為（40，11，16，31，23，55，13，45，50），試生成一棵平衡的二叉排序樹,再從生成的平衡的二叉排序樹中刪除關(guān)鍵字45。3．設(shè)散列表的長度為13，散列函數(shù)為H(k) = k % 13，給頂?shù)年P(guān)鍵碼序列為19, 14, 23, 01, 68, 20, 84, 27。試畫出用線性探查法解決沖突時所構(gòu)成的散列表。答案：26．給出一組關(guān)鍵字（19，01，26，92，87，11，43，87，21）進行冒泡排序，試列出每一趟排序后關(guān)鍵字的排列次序，并比較每遍排序所進行的關(guān)鍵字比較次數(shù)。答案：27．設(shè)待排序序列為 {10, 18, 4, 3, 6, 12, 1, 9, 15, 8}，請給出用希爾排序每一趟的結(jié)果。增量序列取為5, 3, 2, 1。答案：28．對于給定鍵值： 83， 40， 63， 12， 35， 90， 65, 畫出堆排序各趟排序的結(jié)果。答案：29．若對序列(49，38，65，97，76，13，27，50)采用選擇排序法排序，則各趟結(jié)束后序列。答案：第三章 操作系統(tǒng)一、單項選擇題1. 操作系統(tǒng)的功能是進行處理機管理、（ ）管理、設(shè)備管理和文件管理。A. 進程 B. 存儲器 答案：B2. 在計算機系統(tǒng)中，操作系統(tǒng)是（ ） 答案：B3. 如果分時系統(tǒng)的時間片一定，那么（ ），則響應(yīng)時間越長。 答案：B4.　 操作系統(tǒng)中采用多道程序設(shè)計技術(shù)提高CPU和外部設(shè)備的（ ）。 　答案：A，作業(yè)的周轉(zhuǎn)時間=作業(yè)完成時間－作業(yè)的到達時間?，F(xiàn)有三個同時到達的作業(yè)J1，J2和J3，它們的執(zhí)行時間分別是T1，T2和T3，且T1T2T3。系統(tǒng)按單道方式運行且采用短作業(yè)優(yōu)先算法，則平均周轉(zhuǎn)時間是(　　)＋T2＋T3　 　B.(T1＋T2＋T3)/3＋(2/3)T2＋(1/3)T3　　D.　T1＋(1/2)T2＋T3答案：C(　　)　　　　答案：D(　　)　 　　　　 答案：D：00到達系統(tǒng)，估計運行時間為1小時，若10：00開始執(zhí)行該作業(yè)，其響應(yīng)比是(　　)　 　 　答案：A(　　)　　　　　　答案：D，對于不同用戶的文件，其文件名(　　) 　 　　　，也可以不同 答案：C，某一作業(yè)完成后，系統(tǒng)收回其主存空間，并與相鄰空閑區(qū)合并，為此需修改空閑區(qū)表，造成空閑區(qū)數(shù)減1的情況是(　　)A. 無上鄰空閑區(qū)，也無下鄰空閑區(qū)　　B. 有上鄰空閑區(qū)，但無下鄰空閑區(qū)　　C. 有下鄰空閑區(qū)，但無上鄰空閑區(qū)　　， 也有下鄰空閑區(qū)答案：D1某系統(tǒng)中有3個并發(fā)進程，都需要同類資源4個，試問該系統(tǒng)不會發(fā)生死鎖的最少資源數(shù)是（ ）。A．9 B．10 C．11 D．12答案：B1操作系統(tǒng)的基本職能是（ ）。A．控制和管理系統(tǒng)內(nèi)各種資源，有效地組織多道程序的運行 B．提供用