問(wèn)答題

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

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

你可能感興趣的試題

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

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

最新試題

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

題型：?jiǎn)雾?xiàng)選擇題

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

題型：?jiǎn)柎痤}

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

題型：?jiǎn)雾?xiàng)選擇題

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

題型：?jiǎn)雾?xiàng)選擇題

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

題型：?jiǎn)雾?xiàng)選擇題

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

題型：?jiǎn)雾?xiàng)選擇題