《數據結構》試題4(配有答案的).docx

                《數據結構》試題4(配有答案的).docx

                1. 1、本文檔共5頁,可閱讀全部內容。
                2. 2、本文檔內容版權歸屬內容提供方,所產生的收益全部歸內容提供方所有。如果您對本文有版權爭議,可選擇認領,認領后既往收益都歸您。
                3. 3、本文檔由用戶上傳,本站不保證質量和數量令人滿意,可能有諸多瑕疵,付費之前,請仔細先通過免費閱讀內容等途徑辨別內容交易風險。如存在嚴重掛羊頭賣狗肉之情形,可聯系本站下載客服投訴處理。
                4. 文檔侵權舉報電話:19940600175。
                數據結構試題四 單項選擇題(2分X10=20分) 1 ?若某線性表中最常用的操作是刪除第 1個元素,則不宜采用(D ) 存儲方式。 A.單鏈表 B.雙鏈表 C. A.單鏈表 B.雙鏈表 C.單向循環鏈表 D」順序表 2 ?在一棵完全二叉樹的順序存儲方式中,若編號 i的結點有右孩子 1,則其右孩子的編號為 (C )。 2i B. 2i-1C. 2i+1 D. i/2 2i B. 2i-1 C. 2i+1 D. i/2 3.按照二叉樹的定義,具有3個結點的二叉樹有(C )種不同形態。A. 3B. 4C. 5D. 64.在長為n的順序表中,刪除第 3.按照二叉樹的定義,具有 3個結點的二叉樹有( C )種不同形態。 A. 3 B. 4 C. 5 D. 6 4.在長為n的順序表中, 刪除第 i個元素 (1 < i< n+1)需要向前移動( A )個元素。 A. n-i B. n-i+1 C. n-i-1 D. i 5. 一個隊的入隊順序是 1、 2、 3、 4、 則此隊的出隊順序為(D )。 A. 5 A. 5、4、3、2、1 4、5、3、2、 4、 4、3、5、1、2 1 、2、3、4、5 6.棧是一種特殊的線性表,其特殊性表現在(B )。A.可以順序存儲 6.棧是一種特殊的線性表, 其特殊性表現在( B )。 A.可以順序存儲 B.只能從端點進行插入和刪除 C.可以鏈式存儲 D.可以在任何位置進行插入和刪除 一棵二叉樹中,第 k層上最多有(D )個結點。 A. 2k B.2k-1 C.2 k D.2 k-1 一棵有18個結點的二叉樹,其高度最小為( B )層。 A. 4 B. 5 C. 6 D. 18 n個頂點的有向圖中最多有( B)條弧。 A. n(n-1)/2 B. n(n-1) C. n(n+1) D. n(n+1)/2 有向圖中,所有頂點入度和是所有頂點出度和的( B )倍。 A. 0.5 B. 1 C. 2 D. 4 判斷題(1分X1O=1O分) (X) 1.在線性結構的順序存儲結構中,邏輯上相鄰的兩個元素在物理位置上不一定相鄰。 (X ) 2.二叉樹就是度為2的樹。 (V 3.存在這樣的二叉樹,其后序遍歷與中序遍歷得到的訪問序列相同。 (V) 4.滿二叉樹一定是完全二叉樹。 (X ) 5.由空格組成的串叫空串。 (V) 6.在AOE網中,可能有多條關鍵路徑。 (V) 7. m階B-樹具有k個子樹的非葉子結點含有 k-1個關鍵字。 (V) 8.起泡排序是穩定的。 (X) 9.鏈式存儲的線性表可以實現隨機存取。 (X) 10.二叉樹按某種順序線索化后,任一結點均有指向其直接前驅和直接后繼的線索。 三、填空題(2分X8=16分) q=p->next ; p-1 ?在單鏈表中,若刪除指針 q=p->next ; p- >next=q->next 或 p->next=p->next->next ; free (q); 在有頭結點的單鏈表 L中,指針p所指結點是最后一個結點的條件是 p->n ext= =L 。 隊是一種受限制的線性表,也叫 FIFO結構,FIFO的含義是 先進先出(First In First Out )。 對于棧,只能在 棧頂插入元素,只能在 棧頂刪除元素。 數據的基本單位是數據元素,在計算機程序中通常作為一個整體進行考慮和處理。 圖的遍歷方式通常有 深度優先 遍歷和 廣度優先 遍歷兩種。 四、簡答和應用題(38 分) ( 8分)某二叉樹后序遍歷的結果是 ABCDEFG,中序遍歷的結果是 ADBCGFE. (1) 畫出此二叉樹; (1) 求各點的入度和出度; (2) 給出該圖的鄰接矩陣; (3) 給出該圖的一個拓撲排序。 答案: (1) 1 : 0, 3 2 : 2, 1 4: 1, 1 5 :1, 2 (2) 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 2. ( 9分)已知如圖所示有向圖, 3 : 3, 0 0 0 1 0 0 (3) 14523 或 15243 或 15423 3.給出下面稀疏矩陣的三元組。( 5分) 0 0 0 0 0 0 12 0 0 0 0 -1 0 0 0 0 0 0 10 0 0 0 11 0 0 0 0 9 0 0 ((2, 1, 12),( 2, 6,-1 ),( 4, 1, 10),( 4, 5, 11), (5, 4, 9))及行數n=5,列數m=6 ( 8分)已知序列 5, 3, 4 , 8 , 6。 以該序列為權構造一棵有 5個葉子結點的Huffman樹。 求上邊構造的 Huffman樹的帶權路徑長度 WPL. (1)6 (1) 6 (2) WPL=8*2+( 3+4) *3+ ( 5+6) *2=59 ( 8分)已知如圖所示的連通網。 求其最小生成

                文檔評論(0)

                dianxin1241
                該用戶很懶,什么也沒介紹

                相關文檔

                相關課程推薦

                全民乐