閱讀下列說(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)滿足下列關(guān)系時(shí)稱其為堆:在一個(gè)堆中,若堆頂元素為最大元素,則稱為大頂堆;若堆頂元素為最小元素,則稱為小頂堆。堆常用完全二叉樹(shù)表示,圖8.11是一個(gè)大頂堆的例子。堆數(shù)據(jù)結(jié)構(gòu)常用于優(yōu)先隊(duì)列中,以維護(hù)由一組元素構(gòu)成的集合。對(duì)應(yīng)于兩類堆結(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代碼:
您可能感興趣的試卷
你可能感興趣的試題
A.
B.
C.
D.
A.log2m=log2n
B.
C.
D.
A.n×e
B.n+e
C.2n
D.2e
A.從表中任意節(jié)點(diǎn)出發(fā)都能遍歷整個(gè)鏈表
B.對(duì)表中的任意節(jié)點(diǎn)可以進(jìn)行隨機(jī)訪問(wèn)
C.對(duì)于表中的任意一個(gè)節(jié)點(diǎn),訪問(wèn)其直接前趨和直接后繼節(jié)點(diǎn)所用時(shí)間相同
D.第一個(gè)節(jié)點(diǎn)必須是頭節(jié)點(diǎn)
在KMP模式匹配算法中,需要求解模式串p的next函數(shù)值,其定義如下(其中,j為模式串字符的序號(hào))。對(duì)于模式串"abaabaca",其next函數(shù)值序列為()
A.01111111
B.01122341
C.01234567
D.01122334
最新試題
問(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)始)。
一棵滿二叉樹(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,依次類推,每一層都從左到右依次編號(hào),直到最后的葉子節(jié)點(diǎn)層為止,則用()可判定編號(hào)為m和n的兩個(gè)節(jié)點(diǎn)是否在同一層。
對(duì)于線性表(由n個(gè)同類元素構(gòu)成的線性序列),采用單向循環(huán)鏈表存儲(chǔ)的特定之一是()
()是由權(quán)值集合{8,5,6,2}構(gòu)造的哈夫曼樹(shù)(最優(yōu)二叉樹(shù))。
無(wú)向圖中一個(gè)頂點(diǎn)的度是指圖中與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù)。若無(wú)向圖G中的頂點(diǎn)數(shù)為n,邊數(shù)為e,則所有頂點(diǎn)的度數(shù)之和為()
在KMP模式匹配算法中,需要求解模式串p的next函數(shù)值,其定義如下(其中,j為模式串字符的序號(hào))。對(duì)于模式串"abaabaca",其next函數(shù)值序列為()