單項選擇題

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

A.01111111
B.01122341
C.01234567
D.01122334


你可能感興趣的試題

5.問答題

閱讀下列說明和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)先隊列中,以維護由一組元素構(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ù)進行操作,則新插入的元素在堆A中第(9)個位置(從1開始)。
6.單項選擇題對于線性表(由n個同類元素構(gòu)成的線性序列),采用單向循環(huán)鏈表存儲的特定之一是()

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

最新試題

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

題型:單項選擇題

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

題型:單項選擇題

無向圖中一個頂點的度是指圖中與該頂點相鄰接的頂點數(shù)。若無向圖G中的頂點數(shù)為n,邊數(shù)為e,則所有頂點的度數(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ù)進行操作,則新插入的元素在堆A中第(9)個位置(從1開始)。

題型:問答題

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

題型:單項選擇題

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

題型:單項選擇題