單項選擇題

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

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


你可能感興趣的試題

1.問答題

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

問題1：根據以上說明和C代碼，填充C代碼中的空（1）～（5）。問題2：根據以上C代碼，函數heapMaximum，heapExtractMax和maxHeapInsert的時間復雜度的緊致上界分別為（6）、（7）和（8）（用O符號表示）。問題3：若將元素10插入到堆A=（15，13，9，5，12，8，7，4，0，6，2，1）中，調用maxHeapInsert函數進行操作，則新插入的元素在堆A中第（9）個位置（從1開始）。
6.單項選擇題對于線性表（由n個同類元素構成的線性序列），采用單向循環(huán)鏈表存儲的特定之一是（）

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

最新試題

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

題型：單項選擇題

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

題型：單項選擇題

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

題型：單項選擇題

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

題型：單項選擇題

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

題型：單項選擇題

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

題型：問答題