1、2018 年華技大學 834 計算機專業(yè)基礎綜合復習八套卷四（版）參考一填空題（20 分，每題 2 分）1.順序結構是通過表示元間的關系的;鏈式結構是通過表示元間的關系的。已知指針 p 指向單鏈表 L 中的某結點，則刪除其后繼結點的語句是：2.。3.設數(shù)組 A0.8,1.10,數(shù)組中任一元素 Ai,j均占內(nèi)存 48 個二進制位，從首地址 2000 開始連續(xù)存放在主內(nèi)存里，主內(nèi)存字長為 16 位，那么設數(shù)組A0.8,1.10,數(shù)組中任一元素 Ai,j均占內(nèi)存 48 個二進制位，從首地址 2000 開始連續(xù)存放在主內(nèi)存。里，主內(nèi)存字長為 16 位，那么數(shù)組按列時，元素 A5,8的起始地址是4.一棵

2、樹 T 中，包括一個度為 1 的結點，兩個度為 2 的結點，三個度為 3 的結點，四個度為 4 的結點和若干葉子結點，則 T 的葉結點數(shù)為 21。5.6.7.。如果結點 A 有 3 個兄弟，而且B 是 A 的雙親，則B 的度是個頂點。G 是一個非連通無向圖，共有 28 條邊，則該圖至少有換式網(wǎng)絡是以交換器為中心構造的網(wǎng)絡體系，它們工作在 OSI 參考模型的第，它們在不同的端口之間傳遞數(shù)據(jù)。8.9.文件傳輸協(xié)議的英文縮寫為。由于幀中繼可以不用網(wǎng)絡層而使用鏈路層來實現(xiàn)復用和轉接，所以幀中繼通信節(jié)點的層次結構中只有和鏈路層。10. 常用的 IP地址有 A、B、C三類，1 主機標識（hosted）為。

3、二判斷題（20 分，每個 2 分）1.若一棵二叉樹中的結點均無右孩子，則該二叉樹的中根遍歷和后根遍歷序列正好相反。（ ）2.3.對具有 n 個結點的堆進行一個元素運算的時間復雜度為 O(n)。( )在散列法中采取開散列（鏈地址）法來解決 (0,1)之間。( )時, 其裝載因子的取值一定在4.圖的深度優(yōu)先搜索是一種典型的回溯搜索的例子，可以通過遞歸算法求解。()No.12345678910Answer3.31物理層FTP二層942204p-next=u-next; free(u);u=p-next;指針物理上相鄰5.6.對任何用頂點表示活動的網(wǎng)絡（AOV 網(wǎng)）進行拓撲排序的結果都是唯一的。( )

4、鄰接矩陣適用于稠密圖（邊數(shù)接近于頂點數(shù)的平方），鄰接表適用于稀疏圖（邊數(shù)遠小于頂點數(shù)的平方。( )ISO 劃分網(wǎng)絡層次的基本原則是：不同節(jié)點具有相同的層次，不同節(jié)點的相同層次有相同的功能。( )所有以太網(wǎng)交換機端口既支持 10BASET 標準，又支持 100BASET 標準。( )7.8.9.RIP（Routing Information Protocol）是一種路由協(xié)議。()10. 在局域網(wǎng)標準定義了四個層。( )三選擇題（30 分，每個 3 分）1.某算法的時間復雜度為 O(n2)，表明該算法的（ C ）。n2A.問題規(guī)模是n2B.執(zhí)行時間等于C.執(zhí)行時間與 n2 成正比D.問題規(guī)模與 n

5、2 成正比靜態(tài)鏈表中指針表示的是（ C ）.2.A 內(nèi)存地址C下一元素地址B數(shù)組下標D左.右孩子地址3.已知有向圖 G=(V,E)，其中 V=V1,V2,V3,V4,V5,V6,V7，E=,G 的拓撲序列是（ A ）。AV1,V3,V4,V6,V2,V5,V7 CV1,V3,V4,V5,V2,V6,V7下列排序算法中，其中（A. 堆排序，冒泡排序BV1,V3,V2,V6,V4,V5,V7 DV1,V2,V5,V3,V4,V6,V7D ）是穩(wěn)定的。B. 快速排序，堆排序4.C. 直接選擇排序，歸并排序D. 歸并排序，冒泡排序5. 若以 1234 作為雙端隊列的輸入序列，則既不能由輸入受限的雙端隊

6、列得到，也不能由輸出受限的雙端隊列得到的輸出序列是( C )。A.1234B.4132C. 4231D. 42136. 下列關于 AOE 網(wǎng)的敘述中，不正確的是（ B ）。A關鍵活動不按期完成就會影響整個工程的完成時間 B任何一個關鍵活動提前完成，那么整個工程將會提前完成 C所有的關鍵活動提前完成，那么整個工程將會提前完成 D某些關鍵活動提前完成，那么整個工程將會提前完成7. TCPIP 網(wǎng)絡中，某主機的 IP 地址為 35，子網(wǎng)掩碼為 92，那么該主機所在的子網(wǎng)的網(wǎng)絡地址是（ C）。No.12345678910AnswerCCADCBCBCBA B C28 D55【】題中子網(wǎng)掩碼的前三個字節(jié)

7、用二進制表示時全為“1”，第節(jié)轉換為二進制后為 11000000，使用子網(wǎng)掩碼的二進制形式和 IP 地址的二進制表示形式相與后得到該 IP地址所在子網(wǎng)的網(wǎng)絡地址為28。8. IP 數(shù)據(jù)報的報文格式如下圖所示。在沒有選項和填充的情況下，報頭長度域的值為（ B）。A3 B5 C10 D20【】本題考查 IP 數(shù)據(jù)報的格式，計算報文頭長度時，以 4 字節(jié)為，不含選項和填充的報文正好是IP 數(shù)據(jù)報的固定部分，共 20 個字節(jié)，因此，報頭長度為 2045。9. 分組交換對報文交換的主要改進是（ CA差錯控制更加完善 B路由算法更加簡單）C傳輸D傳輸更小且有固定的最大長度更大且有固定的最大長度【】相對于報

8、文交換而言，分組交換中將報文劃分為一個個具有固定最大長度的分組，以分組為進行傳輸。波特率等于（ B ）。每秒鐘傳輸?shù)谋忍孛棵腌娍赡馨l(fā)生的信號變化的次數(shù) C每秒傳輸?shù)闹芷跀?shù)D每秒傳輸?shù)淖止?jié)數(shù)【】波特率是指數(shù)據(jù)信號對載波的調(diào)制速率，它用時間內(nèi)載波調(diào)制狀態(tài)改變的次數(shù)來表示，其是波特（Baud）。波特率與比特率的關系是比特率波特率單個調(diào)制狀態(tài)對應的二進制位數(shù)。四簡答題（60 分）1. 用一維數(shù)組存放的一棵完全二叉樹如下圖所示：寫出后序遍歷該二叉樹時答：HIDJKEBLFGCA結點的順序2.判斷下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，請將它們調(diào)整為堆）。（1）100，85，98，77，80

9、，60，82，40，20，10，66（2）100，98，85，82，80，77，66，60，40，20，10（3）100，85，40，77，80，60，66，98，82，10，20答：(1)是大堆；(2)是大堆；(3)不是堆，調(diào)成大堆 100，98，66，85，80，60，40，77，82，10，203.已知某圖的鄰接表為21（1）寫出此鄰接表對應的鄰接矩陣；（2）寫出由 v1 開始的深度優(yōu)先遍歷的序列；（3）寫出由 v1 開始的深度優(yōu)先的生成樹；（4）寫出由 v1 開始的廣度優(yōu)先遍歷的序列；（5）寫出由 v1 開始的廣度優(yōu)先的生成樹。答：（1）略（2）V1V2V5V3V4V6（3）V4V1V

10、5V3(4) V1V2V3V4V5V6(5)V1V2V3V4V6V56311244355v1v2v3v4v5v6ABCDEFGHIJKL4. 簡述 TCP 和 UDP 協(xié)議的主要特點和應用場合。答：UDP 的主要特點是：傳送數(shù)據(jù)前無需建立連接，沒有流量控制機制，數(shù)據(jù)到達后也無需確認。不可靠交付，只有有限的差錯控制機制。（3）報文頭部短，傳輸開銷小，時延較短。 因此，UDP 協(xié)議簡單，在一些特定的應用中運行效率高。通常用于可靠性較高的網(wǎng)絡環(huán)境（如局域網(wǎng)）或不要求可靠傳輸?shù)膱龊希硗庖渤Ｓ糜诳蛻魴C服務器模式中。TCP 的主要特點是：面向連接，提供了可靠的建立連接和拆除連接的方法，還提供了流量控制和

11、擁塞控制的機制?？煽拷桓?，提供了對報文段的檢錯、確認、重傳和排序等功能。報文段頭部長，傳輸開銷大。 因此，TCP 常用于不可靠的互聯(lián)網(wǎng)中為應用程序提供面向連接的、可靠的、端到端的字節(jié)流服務。5. 設某路由器建立如下路由表：（1） 現(xiàn)收到 5 個分組，其目的 IP 地址分別為：0，0，53，0。2，試分別計算其下一跳。路由協(xié)議的作用是什么？在什么情況下要選擇多協(xié)議路由器？答：（1）目的 IP 地址 0 與子網(wǎng)掩碼 28 相與得 ，可見該分組經(jīng)接口 0 轉發(fā)。目的 IP 地址 0 與子網(wǎng)掩碼 28 相與得 .不等于。與子網(wǎng)掩碼 28 相與得 ，經(jīng)查路由表可知，該項分組經(jīng) R2 轉發(fā)。目的網(wǎng)絡子網(wǎng)掩

12、碼下一條路由器28接口 02828接口 128R296R3（默認）R4目的 IP 地址 51 與子網(wǎng)掩碼 28 相與后得 28，與子網(wǎng)掩碼 92 相與后得 28，經(jīng)查路由表知，該分組轉發(fā)選擇默認路由，經(jīng) R4 轉發(fā)。目的 IP 地址 7 與子網(wǎng)掩碼 28 相與后得 。與子網(wǎng)掩碼 92 相與后得 ，經(jīng)查路由表知，該分組經(jīng) R3 轉發(fā)。目的 IP 地址 0 與子網(wǎng)掩碼 28 相與后得 。與子網(wǎng)掩碼 92 相與后得 4，經(jīng)查路由表知，該分組轉發(fā)選擇默認路由，經(jīng) R4 轉發(fā)。（2）路由協(xié)議用于路由器之間不斷地交換路由信息，并根據(jù)接到的信息，運行路由算法，優(yōu)化更新路由，維持路由器有一個動態(tài)的優(yōu)化的路由表

13、。（3）路由器可以通過不同類型的網(wǎng)卡分別連接不同類型的局域網(wǎng)。如果互聯(lián)的局域網(wǎng)采用了不同協(xié)議，這時就需要使用多協(xié)議路由器。五算法設計（20 分）（請使用類 C 語言進行編程，如果編碼可以寫偽代碼，會適當扣分）設計算法：二叉樹結點的平衡因子（bf）定義為該結點的樹高度與右子樹高度之差。樹的結構如下圖所示 編寫遞歸算法計算二叉樹中各個結點的平衡因子。（20 分）typedef struct BiTreedata；bf； /平衡因子struct BiTree *rchild； struct BiTree *lchild； * BiTree；題目分析 由定義，結點的平衡因子 bf 等于結點的樹高度與右子樹高度之差，設計一遍歷算法，在遍歷結點時，求結點的樹和右子樹的高度，然后得到結點的平衡因子。Height(BiTree bt)/求二叉樹 bt 的深度hl,hr; if (bt=null)return(0);else hl=Height(bt-lchild); hr=Height(bt-rchild); if(hlhr)return (hl+1);