問答題

閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對應(yīng)欄內(nèi)。
說明：堆數(shù)據(jù)結(jié)構(gòu)定義如下。對于n個元素的關(guān)鍵字序列（a1，a2，...，an），當(dāng)且僅當(dāng)滿足下列關(guān)系時稱其為堆：在一個堆中，若堆頂元素為最大元素，則稱為大頂堆；若堆頂元素為最小元素，則稱為小頂堆。堆常用完全二叉樹表示，圖8.11是一個大頂堆的例子。堆數(shù)據(jù)結(jié)構(gòu)常用于優(yōu)先隊列中，以維護(hù)由一組元素構(gòu)成的集合。對應(yīng)于兩類堆結(jié)構(gòu)，優(yōu)先隊列也有最大優(yōu)先隊列和最小優(yōu)先隊列，其中最大優(yōu)先隊列采用大頂堆，最小優(yōu)先隊列采用小項堆。以下考慮最大優(yōu)先隊列。假設(shè)現(xiàn)已建好大頂堆A，且已經(jīng)實現(xiàn)了調(diào)整堆的函數(shù)heapify（A，n，index）。下面將C代碼中需要完善的3個函數(shù)說明如下。
（1）heapMaximum（A）：返回大頂堆A中的最大元素。
（2）heapExtractMax（A）：去掉并返回大頂堆A的最大元素，將最后一個元素"提前"到堆頂位置，并將剩余元素調(diào)整成大頂堆。（
3）maxHeapInsert（A，key）：把元素key插入到大頂堆A的最后位置，再將A調(diào)整成大頂堆。優(yōu)先隊列采用順序存儲方式，其存儲結(jié)構(gòu)定義如下：C代碼：

問題1：根據(jù)以上說明和C代碼，填充C代碼中的空（1）～（5）。問題2：根據(jù)以上C代碼，函數(shù)heapMaximum，heapExtractMax和maxHeapInsert的時間復(fù)雜度的緊致上界分別為（6）、（7）和（8）（用O符號表示）。問題3：若將元素10插入到堆A=（15，13，9，5，12，8，7，4，0，6，2，1）中，調(diào)用maxHeapInsert函數(shù)進(jìn)行操作，則新插入的元素在堆A中第（9）個位置（從1開始）。

你可能感興趣的試題

4.單項選擇題對于線性表（由n個同類元素構(gòu)成的線性序列），采用單向循環(huán)鏈表存儲的特定之一是（）

A.從表中任意節(jié)點出發(fā)都能遍歷整個鏈表
B.對表中的任意節(jié)點可以進(jìn)行隨機(jī)訪問
C.對于表中的任意一個節(jié)點，訪問其直接前趨和直接后繼節(jié)點所用時間相同
D.第一個節(jié)點必須是頭節(jié)點

最新試題

無向圖中一個頂點的度是指圖中與該頂點相鄰接的頂點數(shù)。若無向圖G中的頂點數(shù)為n，邊數(shù)為e，則所有頂點的度數(shù)之和為（）

題型：單項選擇題

（）是由權(quán)值集合{8，5，6，2}構(gòu)造的哈夫曼樹（最優(yōu)二叉樹）。

題型：單項選擇題

在KMP模式匹配算法中，需要求解模式串p的next函數(shù)值，其定義如下（其中，j為模式串字符的序號）。對于模式串"abaabaca"，其next函數(shù)值序列為（）

題型：單項選擇題

問題1：根據(jù)以上說明和C代碼，填充C代碼中的空（1）～（5）。問題2：根據(jù)以上C代碼，函數(shù)heapMaximum，heapExtractMax和maxHeapInsert的時間復(fù)雜度的緊致上界分別為（6）、（7）和（8）（用O符號表示）。問題3：若將元素10插入到堆A=（15，13，9，5，12，8，7，4，0，6，2，1）中，調(diào)用maxHeapInsert函數(shù)進(jìn)行操作，則新插入的元素在堆A中第（9）個位置（從1開始）。

題型：問答題

一棵滿二叉樹，其每一層節(jié)點個數(shù)都達(dá)到最大值，對其中的節(jié)點從1開始順序編號，即根節(jié)點編號為1，其左、右孩子節(jié)點編號分別為2和3，再下一層從左到右的編號為4、5、6、7，依次類推，每一層都從左到右依次編號，直到最后的葉子節(jié)點層為止，則用（）可判定編號為m和n的兩個節(jié)點是否在同一層。

題型：單項選擇題

對于線性表（由n個同類元素構(gòu)成的線性序列），采用單向循環(huán)鏈表存儲的特定之一是（）

題型：單項選擇題