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