數(shù)據(jù)結(jié)構(gòu)填空

1、精選優(yōu)質(zhì)文檔-傾情為你奉上16.數(shù)據(jù)結(jié)構(gòu)由數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的_運(yùn)算_三部分組成。17.在單鏈表中某結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)，需要修改_2_個(gè)結(jié)點(diǎn)指針域的值。18.設(shè)棧S的初始狀態(tài)為空，若元素a、b、c、d、e、f依次進(jìn)棧，得到的出棧序列是b、d、c、f、e、a，則棧S的容量至少是_3_。19.長(zhǎng)度為零的串稱為_空串_。20.廣義表G=(a,b，(c，d，(e，f)，G)的長(zhǎng)度為_4_。21.一棵樹T采用孩子兄弟鏈表存儲(chǔ)，如果樹T中某個(gè)結(jié)點(diǎn)為葉子結(jié)點(diǎn)，則該結(jié)點(diǎn)在二叉鏈表中所對(duì)應(yīng)的結(jié)點(diǎn)一定是_左右指針域均為空_。22.一個(gè)有n個(gè)頂點(diǎn)的無向連通圖，最少有_n-1_條邊。23.當(dāng)待排關(guān)鍵字序

2、列基本有序時(shí)，快速排序、簡(jiǎn)單選擇排序和直接插入排序三種排序方法中，運(yùn)行效率最高的是_直接插入排序_。24.在一棵深度為h的具有n個(gè)結(jié)點(diǎn)的二叉排序樹中，查找任一結(jié)點(diǎn)的最多比較次數(shù)是_h_。25.不定長(zhǎng)文件指的是文件的_記錄含有的信息長(zhǎng)度_大小不固定。16.下面程序段的時(shí)間復(fù)雜度為_O(n)_。sum=1；for（i=0；sum<n;i+）sum+=1；17.已知鏈表結(jié)點(diǎn)定義如下：typedef struct nodechar data16；struct node *next; LinkStrNode；如果每個(gè)字符占1個(gè)字節(jié)，指針占4個(gè)字節(jié)，則該鏈表的存儲(chǔ)密度是_4/5_。18.使用一個(gè)10

3、0個(gè)元素的數(shù)組存儲(chǔ)循環(huán)隊(duì)列，如果采取少用一個(gè)元素空間的方法來區(qū)別循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿，約定隊(duì)頭指針front等于隊(duì)尾指針rear時(shí)表示隊(duì)空。若為front=8，rear=7，則隊(duì)列中的元素個(gè)數(shù)為_99_。19.3個(gè)結(jié)點(diǎn)可以組成_5_種不同樹型的二叉樹。20.用5個(gè)權(quán)值3, 2，4，5，1構(gòu)造的哈夫曼(Huffman)樹的帶權(quán)路徑長(zhǎng)度是_33_。21.若無向圖G中有n個(gè)頂點(diǎn)m條邊，采用鄰接矩陣存儲(chǔ)，則該矩陣中非0元素的個(gè)數(shù)為_2m_。22.影響排序效率的兩個(gè)因素是關(guān)鍵字的_比較_次數(shù)和記錄的移動(dòng)次數(shù)。23.對(duì)任一m階的B樹，每個(gè)結(jié)點(diǎn)中最多包含_m-1_個(gè)關(guān)鍵字。24.若兩個(gè)關(guān)鍵字通過散列函數(shù)映射

4、到同一個(gè)散列地址，這種現(xiàn)象稱為_沖突_。25.如果要為文件中的每個(gè)記錄建立一個(gè)索引項(xiàng)，則這樣建立的索引表稱_稠密索引_。16數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示稱為_數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)_。17長(zhǎng)度為n的線性表采用單鏈表結(jié)構(gòu)存儲(chǔ)時(shí)，在等概率情況下查找第i個(gè)元素的時(shí)間復(fù)雜度是_O（n）_。18下面是在順序棧上實(shí)現(xiàn)的一個(gè)?；静僮?，該操作的功能是_取棧頂元素_。 typedef struct DataType data100； int top； SeqStack； DataType f18(SeqStack*S) if(StackEmpty(S) Error(”Stack is empty”)； re

5、turn S->dataS->top； 19在串匹配中，一般將主串稱為目標(biāo)串，將子串稱為_模式串_。20已知廣義表C=(a(b，c)，d)，則：tail(head(tail(C)= _（c）_。21用6個(gè)權(quán)值分別為6、13、18、30、7和16的結(jié)點(diǎn)構(gòu)造一棵哈夫曼(Huffman)樹，該樹的帶權(quán)路徑長(zhǎng)度為_219_。 22已知有向圖如下所示，其中頂點(diǎn)A到頂點(diǎn)C的最短路徑長(zhǎng)度是_35_。23對(duì)序列55，46，13，05，94，17，42進(jìn)行基數(shù)排序，第一趟排序后的結(jié)果是_42,13,94,55,05,46,17_。24高度為3的3階B-樹最少的關(guān)鍵字總數(shù)是_7_。25VSAM通常作為

6、大型索引順序文件的標(biāo)準(zhǔn)組織，其動(dòng)態(tài)索引結(jié)構(gòu)采用的是_B+樹_。16數(shù)據(jù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是借助_指針_表示數(shù)據(jù)元素之間的邏輯關(guān)系。17如果需要對(duì)線性表頻繁進(jìn)行_插入_或_刪除_操作，則不宜采用順序存儲(chǔ)結(jié)構(gòu)。18如圖所示，可以利用一個(gè)向量空間同時(shí)實(shí)現(xiàn)兩個(gè)類型相同的棧。其中棧1為空的條件是top1=0，棧2為空的條件是top2=n-1，則“棧滿”的判定條件是_top2+1=top1_。19靜態(tài)存儲(chǔ)分配的順序串在進(jìn)行插入、置換和_鏈接_等操作時(shí)可能發(fā)生越界。20廣義表L=（a，（b，( )）的深度為_3_。21任意一棵完全二叉樹中，度為1的結(jié)點(diǎn)數(shù)最多為_1_。22求最小生成樹的克魯斯卡爾(Krus

7、kal)算法耗用的時(shí)間與圖中_邊_的數(shù)目正相關(guān)。23在5階B-樹中，每個(gè)結(jié)點(diǎn)至多含4個(gè)關(guān)鍵字，除根結(jié)點(diǎn)之外，其他結(jié)點(diǎn)至少含_2_個(gè)關(guān)鍵字。24若序列中關(guān)鍵字相同的記錄在排序前后的相對(duì)次序不變，則稱該排序算法是_穩(wěn)定_的。25常用的索引順序文件是_ISAM_文件和_VSAM_文件。16.估算算法時(shí)間復(fù)雜度時(shí)考慮的問題規(guī)模通常是指算法求解問題的_規(guī)模函數(shù)_。17.在雙向循環(huán)鏈表中插入一個(gè)新的結(jié)點(diǎn)時(shí)，應(yīng)修改_4_個(gè)指針域的值。18.若進(jìn)棧序列為a，b，c，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)_5_個(gè)不同的出棧序列。19.鏈串的結(jié)點(diǎn)大小定義為結(jié)點(diǎn)的_數(shù)據(jù)域_中存放的字符個(gè)數(shù)。20.廣義表(a，(d，(

8、c)的深度為_3_。21.在含有3個(gè)結(jié)點(diǎn)a，b，c的二叉樹中，前序序列為abc且后序序列為cba的二叉樹有_4_棵。22.若用鄰接矩陣表示有向圖，則頂點(diǎn)i的入度等于矩陣中_第i列的非零個(gè)數(shù)_。23.對(duì)關(guān)鍵字序列(15，18，11，13，19，16，12，17，10，8)進(jìn)行增量為5的一趟希爾排序的結(jié)果為_15,12,11,10,8,16,18,17,13,19_。24.索引順序查找的索引表由各分塊中的最大關(guān)鍵字及各分塊的_起始地址_構(gòu)成。25.VSAM文件的實(shí)現(xiàn)依賴于操作系統(tǒng)中的_虛擬_存取方法的功能。16.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是其邏輯結(jié)構(gòu)_映像_。17.輸入線性表的n個(gè)元素建立帶頭結(jié)點(diǎn)的單鏈表，其

9、時(shí)間復(fù)雜度為_O（n）_。18.假設(shè)循環(huán)隊(duì)列的元素存儲(chǔ)空間大小為m，隊(duì)頭指針f指向隊(duì)頭元素，隊(duì)尾指針r指向隊(duì)尾元素的下一個(gè)位置，則在少用一個(gè)元素空間的前提下，表示“隊(duì)滿”的條件是_（rear+1）%m=f_。19.給定串的聯(lián)接操作函數(shù)：char *strcat(char *to, char *from);/將串from聯(lián)接到串to的末尾，并返回聯(lián)接后的串 若字符串s1=point,s2=of,則strcat(s1,strcat)(s2,s1)的操作結(jié)果是_pointofpoint_。20.假設(shè)二維數(shù)組A810按行優(yōu)先順序存儲(chǔ),若每個(gè)元素占2個(gè)存儲(chǔ)單元,元素A00的存儲(chǔ) 地址為100,則元素A45的存儲(chǔ)地址為_190_。21.假設(shè)一棵完全二叉樹含1000個(gè)結(jié)點(diǎn),則其中度為2的結(jié)點(diǎn)數(shù)為_499_。22.已知一個(gè)有向網(wǎng)如圖所示,從頂點(diǎn)1到頂點(diǎn)4的最短路徑長(zhǎng)度為_55_。23.在快速排序、