數據結構綜合練習題(編輯修改稿)
2025-04-21 03:01 本頁面
【文章內容簡介】 給出如圖所示的無向圖G的鄰接矩陣和鄰接表兩種存儲結構。簡單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法, 試舉例說明。給出下圖鄰接矩陣和鄰接表兩種存儲結構；寫出圖的拓撲序列。V2V1V3V6V5V41 （二）參考答案一、選擇題 二、填空題1. 構造一個好的HASH函數，確定解決沖突的方法2. ++，[]=x3. 有序4. O(n2)，O(nlog2n)5. N01，2N0+N16. d/27. (31，38，54，56，75，80，55，63)8. (1，3，4，2)，(1，3，2，4)三、應用題1. (20，40，45，47，80，78)，(40，45，47，80，20，78)2. qllink=p。 qrlink=prlink。 prlinkllink=q。 prlink=q。3. 2,ASL=91*1+2*2+3*4+4*2)=25/94. 樹的鏈式存儲結構略，二叉樹略5. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6. 略簡單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法, 試舉例說明?！窘獯稹? (2) 簡單選擇排序 { 275 275* 512 061 } i = 1 { 061 275* 512 275 } i = 2 { 061 275* 512 275 } i = 3 { 061 275* 275 512 } (3) 快速排序 { 512 275 275* } { 275* 275 512 } (4) 堆排序 { 275 275* 061 170 } 已經是最大堆，交換275與170 { 170 275* 061 275 } 對前3個調整 { 275* 170 061 275 } 前3個最大堆，交換275*與061 { 061 170 275* 275 } 對前2個調整 { 170 061 275* 275 } 前2個最大堆，交換170與061 { 061 170 275* 275 } 數據結構（三）一、選擇題1．設某無向圖有n個頂點，則該無向圖的鄰接表中有（ ）個表頭結點。 (A) 2n (B) n (C) n/2 (D) n(n1)2．設無向圖G中有n個頂點，則該無向圖的最小生成樹上有（ ）條邊。 (A) n (B) n1 (C) 2n (D) 2n13．設一組初始記錄關鍵字序列為(60，80，55，40，42，85)，則以第一個關鍵字45為基準而得到的一趟快速排序結果是（ ）。 (A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80 (C) 42，40，55，60，80，85 (D) 42，40，60，85，55，804．（ ）二叉排序樹可以得到一個從小到大的有序序列。 (A) 先序遍歷 (B) 中序遍歷 (C) 后序遍歷 (D) 層次遍歷5．設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結點的左孩子結點的編號為（ ）。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i16．程序段s=i=0；do {i=i+1； s=s+i；}while(i=n)；的時間復雜度為（ ）。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)7．設帶有頭結點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（ ）。 (A) head==0 (B) headnext==0 (C) headnext==head (D) head!=08．設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有（ ）。 (A) 20 (B) 256 (C) 512 (D) 10249．設一組初始記錄關鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關鍵字90需要比較的關鍵字個數為（ ）。 (A) 1 (B) 2 (C) 3 (D) 4，則刪除棧頂元素的操作序列為（ ）。 (A) top=top+1。 (B) top=top1。 (C) topnext=top。 (D) top=topnext。二、判斷題數據的最小單位是數據項。………………………….( √)多重表文件中主索引為非稠密索引，次索引為稠密索引?！?( √ )通常數據結構在計算機中有四種不同的表示方法分為順序存儲結構、鏈式存儲結構、索引存儲、文件存儲。……….…….( )算法具有輸入、輸出、可行性、穩(wěn)定性、有窮性五個特性。……………….( )數據的基本單位是數據項。………………………….( )算法的復雜度分為時間復雜度和效率復雜度?！?( )性質相同的數據元素的集合成為數據對象?！?( √ )所有結點按1對1的鄰接關系構成的整體就是集合結構。……….( )散列文件不能順序存取、只能按關鍵字隨機存取?！?( √ )數據的基本單位是數據元素?！?( √ )11．不論是入隊列操作還是入棧操作，在順序存儲結構上都需要考慮“溢出”情況。（√ ）12．當向二叉排序樹中插入一個結點，則該結點一定成為葉子結點。（√ ）13．由樹轉化成二叉樹，該二叉樹的右子樹不一定為空。（ ）14．線性表中的所有元素都有一個前驅元素和后繼元素。（ ）。（ ）。（ ）。（?。?8. 由樹轉化成二叉樹，該二叉樹的右子樹不一定為空。（ ）。（√?。?或記錄)構成的集合(√)三、填空題1. 設指針變量p指向雙向鏈表中的結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為_________=p；sright=pright；__________=s； prightleft=s；（設結點中的兩個指針域分別為left和right）。2. 設完全有向圖中有n個頂點，則該完全有向圖中共有________條有向條；設完全無向圖中有n個頂點，則該完全無向圖中共有________條無向邊。3. 設關鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個元素開始進
環(huán)評公示相關推薦
鄂ICP備17016276號-1