數(shù)據(jù)結(jié)構(gòu)導(dǎo)論填空題目匯總

1、-0116下列程序段的時(shí)間復(fù)雜性量級(jí)是 0(n*i)。for (i=1;in; i+)for (j=1; j top +sq - datasq - top=x19鏈隊(duì)列實(shí)際上是一個(gè)同時(shí)帶有頭指針和尾指針的單鏈表，尾指針指向該單鏈表的 隊(duì)尾結(jié)點(diǎn)。20設(shè)有k個(gè)結(jié)點(diǎn)在用哈夫曼算法構(gòu)造哈夫曼樹(shù)的過(guò)程中若第i次合并時(shí)已找到權(quán)最小的結(jié)點(diǎn) x和權(quán)次小的結(jié)點(diǎn)y用Tx.wt表示結(jié)點(diǎn)x的權(quán)值已知Tx.wt=m, Ty.wt=n則合并成新的二叉 樹(shù)后給新根結(jié)點(diǎn)的權(quán)值賦值的語(yǔ)句為 m+n。21在下列樹(shù)中結(jié)點(diǎn)H的祖先為 F。/磔 01 &22頂點(diǎn)數(shù)為n、邊數(shù)為n(n-1)/2的無(wú)向圖稱為無(wú)向完全圖。任何兩點(diǎn)之間都有的邊

2、的無(wú)向圖稱為無(wú)向完全圖；邊數(shù)(n(n-1)/2)任何兩點(diǎn)之間都有弧的有向圖稱為有向完全圖；弧數(shù)(n*(n-1)23動(dòng)態(tài)查找表在開(kāi)散列表上通常采用線性探測(cè)法和鏈地址法 來(lái)解決沖突問(wèn)題。24對(duì)于有10個(gè)元素的有序表采用二分查找需要比較3次方可找到其對(duì)應(yīng)的鍵值則該元素在 有序表中的位置可能是1,3,6,9。25查找表的邏輯結(jié)構(gòu)與線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)等相比根本區(qū)別在于數(shù)據(jù)元素之間無(wú)邏輯關(guān)系。27在排序方法中依次將每個(gè)記錄插入到一個(gè)有序的子序列中去即在第i(i21)遍整理時(shí)r1,r2,ri-1已經(jīng)是排好順序的子序列取出第i個(gè)元素ri在已排好序的子序列里為ri找到一個(gè) 合適的位置并把它插到該位置上。這種排序

3、方法被稱為直接插入排序 。28快速排序法在待排序數(shù)據(jù)已基本有序 的情況下最不利于發(fā)揮其長(zhǎng)處。2004-10從數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)，數(shù)據(jù)通常可分為三個(gè)層次，即：數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng) 對(duì)順序表執(zhí)行插入操作，其插入算法的平均時(shí)間復(fù)雜性為O(n)。在具有n個(gè)單元、且采用順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 n-1 個(gè)元素。若front和rear分別表示循環(huán)隊(duì)列Q的頭指針和尾指針，m0表示該隊(duì)列的最大容量，則 循環(huán)隊(duì)列為空的條件是 Qfront=Qrear。21.二維數(shù)組A1020采用按行為主序的存儲(chǔ)方式，每個(gè)元素占4個(gè)存儲(chǔ)單元，若A00的存儲(chǔ)地址為300，則A1010的地址為 1056。 樹(shù)的遍歷主要有先根遍

4、歷、后根遍歷和中根遍歷 三種。深度為k的完全二叉樹(shù)至少有 2(k次方)-1 個(gè)結(jié)點(diǎn)。 若圖的鄰接矩陣是一個(gè)對(duì)稱矩陣，則該圖一定是一個(gè) 無(wú)向圖。對(duì)于具有n個(gè)元素的數(shù)據(jù)序列，采用二叉排序樹(shù)查找，其平均查找長(zhǎng)度為log2(n+1)-1。元要完全避免散列所產(chǎn)生的堆積”現(xiàn)象，通常采用公共溢出區(qū) 法。28.在最好的情況下，對(duì)于具有n個(gè)元素的有序序列，若采用冒泡排序，所需的比較次數(shù)為 n-1 次。-01數(shù)據(jù)結(jié)構(gòu)中的算法，通常采用最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度 兩種方法衡量其效率。判斷帶頭結(jié)點(diǎn)head的單鏈表為空的條件是head-next=null。若順序表每個(gè)元素長(zhǎng)度均為5,其中第一個(gè)元素的存儲(chǔ)地址為30,

5、則第6個(gè)元素的儲(chǔ)地址為 55_( 30+5*(6-1)。若front和rear分別表示循環(huán)隊(duì)列Q的頭指針和尾指針，m0表示該隊(duì)列的最大容量，則 判斷循環(huán)隊(duì)列為滿的條件是_(sq.rear+1)%maxsize=sq.front。對(duì)于順序存儲(chǔ)結(jié)構(gòu)的二維數(shù)組，通常采用 行序優(yōu)先存儲(chǔ)和列序優(yōu)先存儲(chǔ) 兩種存放方式存儲(chǔ)數(shù)據(jù)元素。若某二叉樹(shù)的先根遍歷序列為CEDBA，中根遍歷序列為DEBAC，則其后根遍歷序列為 DABEC。具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其深度為log2n+1。 圖主要采用鄰接矩陣和鄰接 兩種存儲(chǔ)結(jié)構(gòu)存放。索引順序查找通常分兩個(gè)階段進(jìn)行，首先采用順序查找法或二分法確定所要查找的塊，然后再用 順

6、序查找 法在塊中找到具體的元素值。二叉排序樹(shù)是一種特殊的有序表，若要保證輸出序列其鍵值完全按遞增排列，則應(yīng)對(duì)二叉排序樹(shù)采用中根遍歷法遍歷。28.在各種內(nèi)部排序中，占用存儲(chǔ)空間較大的排序通常并歸 排序。2005-10 時(shí)間復(fù)雜性描述量級(jí)中，若某算法達(dá)到指數(shù)量級(jí)，則該算法通常是不可計(jì)算 的。對(duì)順序表執(zhí)行刪除操作，其刪除算法的平均時(shí)間復(fù)雜性為(n-1)/2。若head表示循環(huán)鏈表的頭指針，t表示尾結(jié)點(diǎn)，則頭指針head與尾結(jié)點(diǎn)t之間的關(guān)系可表示為 t-next=head。 我們通常把隊(duì)列中允許刪除的一端稱為隊(duì)頭。二維數(shù)組A 56采用按列為主序的存儲(chǔ)方式，每個(gè)元素占3個(gè)存儲(chǔ)單元，若 A00的存儲(chǔ)地址是

7、100,則A 43的存儲(chǔ)地址_157。以行為主序存儲(chǔ)Aij的首地址=數(shù)組的在內(nèi)存中的基地址+ i *列數(shù)*每個(gè)元素占單元數(shù)+ j *每 個(gè)元素占單元數(shù)若二維數(shù)組AL1.U1,L2.U2以列為主序存儲(chǔ)，每個(gè)元素占用d個(gè)存儲(chǔ)單元，則元素Ai,j 的存儲(chǔ)位置相對(duì)于數(shù)組空間首地址的偏移量為(J-L2)x(U1-LI+1)+I-L1)xd 樹(shù)在數(shù)據(jù)結(jié)構(gòu)中常采用孩子鏈表表示法、孩子兄弟鏈表和雙親表示法三種存 儲(chǔ)結(jié)構(gòu)表示。若某二叉樹(shù)中度為1的結(jié)點(diǎn)數(shù)為4,度為2的結(jié)點(diǎn)數(shù)為6,則該樹(shù)葉子結(jié)點(diǎn)數(shù)為7。對(duì)于n個(gè)頂點(diǎn)的生成樹(shù)，其邊的個(gè)數(shù)為_(kāi)n-1。對(duì)于具有n個(gè)元素的數(shù)據(jù)序列，若采用二分查找法，當(dāng)n的值較大時(shí)其平均查找

8、長(zhǎng)度為_(kāi)log2 （n+1）-1。解決散列所引起沖突的方案中，建立公共溢出區(qū)法是介于開(kāi)散列表與閉散列表之間的一種方法。28.排序通?？煞譃閮?nèi)部排序和外部排序，其中內(nèi)部排序是指排序的整個(gè)過(guò)程中，數(shù)據(jù)全部 存放在計(jì)算機(jī)的內(nèi)存 中。-01 數(shù)據(jù)表示和 數(shù)據(jù)處理 是程序設(shè)計(jì)者所要考慮的兩項(xiàng)基本任務(wù)。一個(gè)算法通常可從正確性、易讀性、健壯性和時(shí)空性 等四個(gè)方面評(píng)價(jià)、分析。對(duì)長(zhǎng)度為n的順序表執(zhí)行刪除操作，其刪除算法在最壞情況下的時(shí)間復(fù)雜性為0（n）。 我們通常把隊(duì)列中允許插入的一端稱為 隊(duì)尾。二維數(shù)組在機(jī)器級(jí)的具體實(shí)現(xiàn)，通常均采用 順序和二叉鏈表 存儲(chǔ)結(jié)構(gòu)。 深度為k的滿二叉樹(shù)其葉子結(jié)點(diǎn)個(gè)數(shù)共有 2（k次方

9、）-1 個(gè)。二叉樹(shù)通常采用順序儲(chǔ)存結(jié)構(gòu)和鏈?zhǔn)絻?chǔ)存結(jié)構(gòu) 兩種存儲(chǔ)結(jié)構(gòu)表示。若一個(gè)完全無(wú)向圖具有n條邊，則該圖的頂點(diǎn)個(gè)數(shù)為。 查找表的邏輯組織結(jié)構(gòu)實(shí)際上是 集合 結(jié)構(gòu)。對(duì)于具有n個(gè)元素的數(shù)據(jù)序列，采用順序查找法，其平均查找長(zhǎng)度為（n+1）/2。28.對(duì)于具有n個(gè)元素的有序序列，若采用冒泡排序，最多需要進(jìn)行 n-1 趟起泡。200610 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、_線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)等 四類。 通常從正確性、易讀性、健壯性 和時(shí)空性等4個(gè)方面評(píng)價(jià)算法（包括程序）的 質(zhì)量。 順序表的存儲(chǔ)密度為1，而鏈表的存儲(chǔ)密度為小于1。對(duì)于棧只能在棧頂 插入和刪除元素。在循環(huán)隊(duì)列中，存儲(chǔ)空間為

10、0n-1,設(shè)隊(duì)頭指針front指向隊(duì)頭元素前一個(gè)空閑元素，隊(duì)尾指針指向隊(duì)尾元素，那么隊(duì)滿標(biāo)志為front=（rear+1）%n,隊(duì)空標(biāo)志為_(kāi)front= rear三個(gè)結(jié)點(diǎn)可構(gòu)成_5 種不同形態(tài)的二叉樹(shù)。共有5種，如下圖所示 TOC o 1-5 h z 花彌點(diǎn)花擊 HYPERLINK l bookmark70 o Current Document / I * 短k憊fcA:對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為2n個(gè)，其中 n-1 個(gè)用于鏈接孩子結(jié)點(diǎn)。（n+1個(gè)空閑節(jié)點(diǎn)）有向圖G用鄰接矩陣A1n，1-n存儲(chǔ)，其第i列的所有元素之和等于頂點(diǎn)*的度。對(duì)二叉排序樹(shù)

11、進(jìn)行 中序 遍歷，可得到排好序的遞增結(jié)點(diǎn)序列。采用折半查找方法進(jìn)行查找的數(shù)據(jù)序列應(yīng)為有序表 且_順序存儲(chǔ)結(jié)構(gòu)。 在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用插入；若初始數(shù)據(jù)基本反序，則選用選擇?；菊驎r(shí)用插入排序，因?yàn)檫@時(shí)的關(guān)鍵字比較次數(shù)和記錄移動(dòng)次數(shù)都很少基本反序用選擇排序，此時(shí)兩者的關(guān)鍵字比較次數(shù)差不多，選擇排序的記錄移動(dòng) 次數(shù)很少 快速排序最好情況下的時(shí)間復(fù)雜度為_(kāi)O（nlog2n次方），最壞情況下的時(shí)間復(fù)雜度 為_(kāi)O（n2平方）。-01在數(shù)據(jù)結(jié)構(gòu)中，各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任意兩個(gè)結(jié)點(diǎn)可以鄰接的結(jié)構(gòu)稱為圖結(jié)構(gòu)。每個(gè)存儲(chǔ)結(jié)點(diǎn)只含一個(gè)數(shù)據(jù)元素，所有存儲(chǔ)結(jié)點(diǎn)連續(xù)存放。此外增設(shè)一個(gè)索引

12、表，索引 表中的索引指示各存儲(chǔ)結(jié)點(diǎn)的存儲(chǔ)位置或位置區(qū)間端點(diǎn)。按這種方式組織起來(lái)的存儲(chǔ)結(jié) 構(gòu)稱為索引存儲(chǔ)方式。 在順序表上讀表元算法的時(shí)間復(fù)雜度為_(kāi)0（n）。雙鏈表中前驅(qū)指針為prior，后繼指針為next，在指針P所指結(jié)點(diǎn)前插入指針S所指的 結(jié)點(diǎn)，需執(zhí)行下列語(yǔ)句：Sfnext=P;Sfprior=Pfprior;Pfprior=S;設(shè)數(shù)組A 0.80.8的起始元素位置為a,每個(gè)元素占2 L個(gè)存儲(chǔ)單元，按行序?yàn)橹餍虼鎯?chǔ)。若元素Aij的存儲(chǔ)位置為a+66 L，則元素A ji的存儲(chǔ)位置為 _a+114L。有4個(gè)結(jié)點(diǎn)且深度為4的二叉樹(shù)的形態(tài)共有 4種。某二叉樹(shù)的先根遍歷序列為IJKLMNO,中根遍歷序

13、列為JLKINMO,則該二叉樹(shù)中根結(jié)點(diǎn)的右孩子是M。第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路或者環(huán)，除第一個(gè)頂點(diǎn)和最后一個(gè)頂 點(diǎn)外，其余頂點(diǎn)都不重復(fù)的回路，稱為_(kāi)簡(jiǎn)單回路或簡(jiǎn)單環(huán)。 一個(gè)具有10個(gè)頂點(diǎn)的完全無(wú)向圖中有45 條邊。 二分查找的時(shí)間復(fù)雜度為O（log2n次方）。 二路歸并排序算法的時(shí)間復(fù)雜度為_(kāi)O（nlog2n次方）。2007-10設(shè)有指針head指向不帶表頭結(jié)點(diǎn)的單鏈表用next表示結(jié)點(diǎn)的一個(gè)鏈域指針p指向與鏈 表中結(jié)點(diǎn)同類型的一個(gè)新結(jié)點(diǎn)?，F(xiàn)要將指針p指向的結(jié)點(diǎn)插入表中使之成為第一個(gè)結(jié)點(diǎn)則所 需的操作為“pfnext=head”和氣 單鏈表中邏輯上相鄰的兩個(gè)元素在物理位置上 未

14、必 相鄰。在一個(gè)長(zhǎng)度為n的數(shù)組中刪除第i個(gè)元素1itl-r1=s-r1；和s-r1-t1=s-t1;”。 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的目的是節(jié)省儲(chǔ)存空間。在一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找值為m的某結(jié)點(diǎn)，若查找成功，則需平均比較的結(jié)點(diǎn)數(shù)為 n+1/2。深度為15的滿二叉樹(shù)上，第11層有 1024 個(gè)結(jié)點(diǎn)。5.深度為15的滿二叉樹(shù)上，第u層有2山=】024個(gè)結(jié)點(diǎn)。在深度為7的滿二只樹(shù)中，度為2的結(jié)點(diǎn)個(gè)數(shù)為 這里的度為W 的結(jié)點(diǎn)個(gè)數(shù)是什么意思？在深廈為了的而二受肉中，度為2的結(jié)點(diǎn)個(gè)教為.這里的度為上的結(jié)點(diǎn)個(gè)裁旱么意思？片岡美夕數(shù)字201411-29優(yōu)質(zhì)解答度為的W席就是該節(jié)點(diǎn)既有左于廁,又有右于樹(shù)深度為

15、7的向二叉樹(shù)總共的節(jié)點(diǎn)數(shù)為2人了-1 = 1，又因?yàn)槭菨M二叉樹(shù)，所以只有度為2的和度為0的節(jié)點(diǎn)，葉子節(jié)點(diǎn)的數(shù)目為：(7T)=隊(duì)用以有度為2的結(jié)點(diǎn)個(gè)數(shù)為-127-時(shí)=63個(gè).對(duì)一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層編號(hào)，則編號(hào)為49的結(jié)點(diǎn)，它的左孩子的編號(hào)為98。i的左孩子是2i,右孩子是2i+1 .所以49的右孩子編號(hào)為98+1.一個(gè)具有4個(gè)頂點(diǎn)的無(wú)向完全圖有 6 條邊。n(n-1)/2一個(gè)有向圖G中若有孤、和，則在圖G的拓?fù)湫蛄兄?，頂點(diǎn) Vi，V.和 Vk 的相對(duì)位置為 V.,V.,Vk。1 在一棵二叉排序樹(shù)上按 中序 遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。 實(shí)現(xiàn)二分查找的存儲(chǔ)結(jié)構(gòu)僅限于順序存儲(chǔ)結(jié)構(gòu)

16、，且其中元素排列必須是 有序表 的。在插入排序和選擇排序中，若原始記錄已基本有序，則較適合選用 插入排序?qū)個(gè)元素的序列進(jìn)行冒泡排序時(shí)，最多需進(jìn)行n-1 趟。2008-10在任何問(wèn)題中，數(shù)據(jù)元素都不是孤立的，它們之間總存在某種關(guān)系，通常稱這種關(guān)系為 圖狀結(jié)構(gòu)。存儲(chǔ)結(jié)點(diǎn)之間通常有四種基本存儲(chǔ)方式，即順序存儲(chǔ)方式、索引存儲(chǔ)方式、鏈?zhǔn)酱鎯?chǔ)方式 和散列存儲(chǔ)方式。在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素(1ir之前插入一個(gè)元素時(shí)，需向后移動(dòng)n-i+1 個(gè)元素。對(duì)一棵深度為10的滿二叉樹(shù)按層編號(hào)，則編號(hào)為51的結(jié)點(diǎn)，它的雙親結(jié)點(diǎn)編號(hào)為25。用S表示入棧操作，X表示出棧操作，若元素入棧順序?yàn)?234,為了得到13

17、42的出棧順 序，相應(yīng)的S和X操作串為 SXSSXSXX。具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)，其結(jié)點(diǎn)總數(shù)為 2n-1。一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，所有非終端結(jié)點(diǎn)的度均為k，則該樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)為一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，所有非終端結(jié)點(diǎn)的度均為k，則此二叉樹(shù)為K叉樹(shù)，這棵樹(shù)只右度 為K和度為0的結(jié)點(diǎn)，設(shè)度為K的結(jié)點(diǎn)數(shù)為a，度為0的結(jié)點(diǎn)數(shù)為b，則n=a+b。又設(shè)二叉 樹(shù)的所有分支為m,則m=k*a,同樣可以得到n=m+1。綜上可以得到 b=(n-1)*(k-1)/k-1。23.在無(wú)向圖G的鄰接矩陣A中，若A ij等于0，則A ji等于 0。某二叉樹(shù)的后根遍歷序列為abd，中根遍歷序列為adb，則它的先根遍歷序列為

18、dab。先在所有的記錄中選出鍵值最小的記錄，將它與第一個(gè)記錄交換；然后在其余的記錄中 再選出最小的記錄與第二個(gè)記錄交換，依此類推，直至所有記錄排序完成。這種排序方法 稱為直接選擇排序。對(duì)含有n個(gè)結(jié)點(diǎn)e條邊的無(wú)向連通圖，利用prim算法生成最小生成樹(shù)的時(shí)間復(fù)雜度為O(n2 次方)。 對(duì)n個(gè)元素進(jìn)行冒泡排序時(shí)，最少的比較次數(shù)為_(kāi)n-1。200901在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)方式、鏈?zhǔn)酱鎯?chǔ)方式、索引存儲(chǔ)方式和散列存儲(chǔ)方式等四種。作為一個(gè)算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其他參數(shù)，稱為_(kāi)算 TOC o 1-5 h z 法的輸入規(guī)模和問(wèn)題的規(guī)模。在雙鏈表中，存儲(chǔ)一個(gè)結(jié)點(diǎn)有三個(gè)

19、域，一個(gè)是數(shù)據(jù)域，另兩個(gè)是指針域，分別指向直接前驅(qū)和直接后繼。在有n個(gè)元素的鏈隊(duì)列中，入隊(duì)和出隊(duì)操作的時(shí)間復(fù)雜度分別為_(kāi)O(1)和 HYPERLINK l bookmark142 o Current Document _O(n)。在棧結(jié)構(gòu)中，允許插入的一端稱為棧頂；在隊(duì)列結(jié)構(gòu)中，允許插入的一端稱為 隊(duì)尾。在循環(huán)隊(duì)列中，存儲(chǔ)空間為0n-1。設(shè)隊(duì)頭指針front指向隊(duì)頭元素前一個(gè)空閑元素，隊(duì) HYPERLINK l bookmark147 o Current Document 尾指針指向隊(duì)尾元素，那么其隊(duì)空標(biāo)志為rear=front，隊(duì)滿標(biāo)志為 _(rear+1)%maxsize=front。 深

20、度為k的二叉樹(shù)至多有_2k次方-1 個(gè)結(jié)點(diǎn)，最少有 2(k次方-1) 個(gè)結(jié)點(diǎn)。設(shè)有一稠密圖G，則G采用 鄰接矩陣 存儲(chǔ)結(jié)構(gòu)較省空間。設(shè)有一稀疏圖G，則G采用 鄰接表存儲(chǔ)結(jié)構(gòu)較省空間。在一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較(n+1)/2 個(gè)元素結(jié)點(diǎn)。假定對(duì)線性表R059進(jìn)行分塊檢索，共分為10塊，每塊長(zhǎng)度等于6。若檢索索引表 和塊均用順序檢索的方法，則檢索每一個(gè)元素的平均檢索長(zhǎng)度為_(kāi)9。在插入排序、冒泡排序、快速排序、歸并排序等排序算法中，占用輔助空間最多的是 歸并排序。 冒泡排序最好的時(shí)間復(fù)雜度為 O (n) ，平均時(shí)間復(fù)雜度為_(kāi) O (n的平方)，

21、是一種穩(wěn)定的排序算法。-10下列程序段的時(shí)間復(fù)雜度為 O(n) i=0s=0 whilein i+s=s+i數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。線性表中所含結(jié)點(diǎn)的個(gè)數(shù)稱為表長(zhǎng)。向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)新結(jié)點(diǎn)*p時(shí)應(yīng)執(zhí)行top-next_=p 和 top=p操作。20-設(shè)一個(gè)順序棧S元素七七七與%棧的容量至少為 3。依次進(jìn)棧如果6個(gè)元素的退棧順序?yàn)閟 s s s s s則順序2 3 4 6 5 1若滿二叉樹(shù)的結(jié)點(diǎn)數(shù)為n則其高度為【log2(n)】+1。在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中從樹(shù)根起自上而下、從左到右地給所有結(jié)點(diǎn)編號(hào)。若編號(hào)為i的結(jié)點(diǎn)有父結(jié)點(diǎn)那么

22、其父結(jié)點(diǎn)的編號(hào)為i/2。深度為k的二叉樹(shù)結(jié)點(diǎn)數(shù)最多有 2k次方-1 個(gè)。某二叉樹(shù)的后根遍歷為ABKCBPM則該二叉樹(shù)的根為 M 。在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中頂點(diǎn)的度最大可達(dá)n-1。有向圖G的鄰接矩陣為A如果圖中存在弧V V 則Aij的值為1順序查找算法的平均查找長(zhǎng)度為n+1/2 j。 二路歸并排序的平均時(shí)間復(fù)雜度為,丑迎虬。-01下列程序段的時(shí)間復(fù)雜度為 O（n3次方）。for（i=1； i=n； i+）for（j=1； j=n； j+）for（k=1； k=n； k+）s=i+j+k；在數(shù)據(jù)結(jié)構(gòu)中，各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任意兩個(gè)結(jié)點(diǎn)可以鄰接的結(jié)構(gòu)稱為 圖狀結(jié)構(gòu)。在單鏈表中，存儲(chǔ)每個(gè)結(jié)

23、點(diǎn)有兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是指針域，指針域指向該結(jié)點(diǎn)直接后繼 的。在棧結(jié)構(gòu)中，允許插入的一端稱為 棧頂。 從一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（1in）時(shí)，需向前移動(dòng) n-i 個(gè)元素。一個(gè)棧的輸入序列是1，2, 3,，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素為n-i+1。循環(huán)隊(duì)列被定義為結(jié)構(gòu)類型，含有三個(gè)域：data, front和rear，則循環(huán)隊(duì)列sq為空的條 件 是 sq.front=sq.rear。一個(gè)10階對(duì)稱矩陣A，采用行優(yōu)先順序壓縮存儲(chǔ)上三角元素，a00為第一個(gè)元素，其存儲(chǔ)地址為0，每個(gè)元素占有1個(gè)存儲(chǔ)地址空間，則a45的地址為 19。 對(duì)于一棵滿二叉樹(shù)，若有m個(gè)葉

24、子，則樹(shù)中結(jié)點(diǎn)數(shù)為2m-1。含有n個(gè)頂點(diǎn)和n-1條邊的連通圖G采用鄰接表 存儲(chǔ)結(jié)構(gòu)較省空間。 在圖中，第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為 簡(jiǎn)單回路或簡(jiǎn)單環(huán)。動(dòng)態(tài)查找中兩個(gè)元素X，Y存入同一個(gè)散列表時(shí)，X、Y鍵值相同，則這種情況稱為 沖突。 堆排序需 一 個(gè)記錄大小的輔助存儲(chǔ)空間。2010-10下列程序段的時(shí)間復(fù)雜度為_(kāi)O（根號(hào)n）。i=0； s=0；while （snext=top和top=p 操作。 有m個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)所具有的結(jié)點(diǎn)數(shù)為_(kāi)2m-1。在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，從樹(shù)根起，自上而下、自左至右地給所有結(jié)點(diǎn)編號(hào)。設(shè)根結(jié)點(diǎn)編號(hào)為1。若編號(hào)為i的結(jié)點(diǎn)有右孩子，那么其右孩子的編

25、號(hào)為2i+1。在一棵樹(shù)中，根 結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。 一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖的弧數(shù)是_n(n-1)。n個(gè)頂點(diǎn)的無(wú)向圖G用鄰接矩陣Ann存儲(chǔ)，其中第i列的所有元素之和等于頂 點(diǎn)Vi的度。 選擇排序的平均時(shí)間復(fù)雜度為_(kāi)O(n的平方)。-01下列程序段的時(shí)間復(fù)雜度為 O(log2n)。i=1;while (i1)的滿二叉樹(shù)中共有 2n次方-1 個(gè)結(jié)點(diǎn)。在無(wú)向圖中，如果從頂點(diǎn)v到頂點(diǎn)v有路徑，則稱v和v是 連通的。 無(wú)向完全圖G采用鄰接矩陣 存儲(chǔ)結(jié)構(gòu)較省空間。在順序查找、二分查找、索引查找和散列查找四種查找方法中，平均查找長(zhǎng)度與元素個(gè) 數(shù)沒(méi)有關(guān)系的查找方法是 散列查找。 快速排序最好情況下的時(shí)間復(fù)雜

26、度為 O(nlog2n)。2011-10下列程序段的時(shí)間復(fù)雜度為_(kāi)O(n的平方)。for(i=1;i=n;i+)for(j=1;jnext=head。隊(duì)列又稱為先進(jìn)先出 的線性表。順序棧被定義為結(jié)構(gòu)類型，含有兩個(gè)域：data和top，則對(duì)棧*sq進(jìn)行初始化的操作是 _sqtop=0。對(duì)于任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n2=_n0-1。一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，采用二叉鏈表存儲(chǔ)，則二叉鏈表中指向孩子結(jié)點(diǎn)的指針有_n-1個(gè)。 若連通圖G的頂點(diǎn)個(gè)數(shù)為n，則圖G的生成樹(shù)的邊數(shù)為 n-1。一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖的邊數(shù)最多為 n(n-1)/2。 中根遍歷二叉排序樹(shù)所得

27、到的結(jié)點(diǎn)訪問(wèn)序列是鍵值的 遞增 序列。 冒泡排序的平均時(shí)間復(fù)雜度為 O(n2)。 將序列60，20，23，68，94，70，73建成堆，則只需把20與 60 互相交換。201201數(shù)據(jù)的不可分割的最小標(biāo)識(shí)單位是 數(shù)據(jù)項(xiàng)，它通常不具有完整確定的實(shí)際意義， 或不被當(dāng)作一個(gè)整體對(duì)待。運(yùn)算分為加工型運(yùn)算和引用型運(yùn)算，讀取操作是_引用類型 運(yùn)算。帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表L(L為頭指針)中，指針p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是 _p next=L。在雙鏈表中，前趨指針和后繼指針?lè)謩e為prior和next。若使指針p往后移動(dòng)兩個(gè)結(jié)點(diǎn)，則需執(zhí)行語(yǔ)句*p=p-next-next。元素s，s，s，s，s，s依次進(jìn)入順序

28、棧S，如果6個(gè)元素的退棧順序?yàn)?23456&，&，s.，s，則順序棧的容量至少為_(kāi)3_。234651稀疏矩陣一般采用的壓縮存儲(chǔ)方法是_三元組表示法。在一棵樹(shù)中，根結(jié)點(diǎn)沒(méi)有雙親。一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，從樹(shù)根起，自上而下、自左至右給所有結(jié)點(diǎn)編號(hào)。設(shè)根結(jié)點(diǎn)編號(hào)為1，若編號(hào)為i的結(jié)點(diǎn)有父結(jié)點(diǎn)，那么其父結(jié)點(diǎn)的編號(hào)為_(kāi)i/2 (取下整 數(shù))。二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)中判斷指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_(p-lchild=null)&( p-rchild=null)。邊稀疏的無(wú)向圖采用_鄰接表存儲(chǔ)較省空間。 除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同外，其余頂點(diǎn)不重復(fù)的回路，稱為簡(jiǎn)單回路 。二分查找算法的

29、時(shí)間復(fù)雜度是 O(n*log2n)。 要將序列51，18，23，68，94，70，73建成堆，則只需把18與_51 相互交換。201210下面算法程序段的時(shí)間復(fù)雜度為_(kāi)0(n的3次方)。for (i=1; i=n; i+)for (j=1; j=n; j+)for (k=1;knext=_p-next-next。在帶有頭結(jié)點(diǎn)的單鏈表head中首結(jié)點(diǎn)的指針為_(kāi)head-next。在棧結(jié)構(gòu)中允許插入和刪除的一端稱為棧頂。C程序中將對(duì)稱矩陣Ann的下三角元素壓縮存儲(chǔ)到n(n+1)/2個(gè)元素的一維數(shù)組M中設(shè) aiji存放在數(shù)組Mk中則k的值用i,j表示為_(kāi)(i+1)*i/2+j。 具有64個(gè)結(jié)點(diǎn)的完全

30、二叉樹(shù)的深度為 7。某二叉樹(shù)的先序遍歷序列為AJKLMNO中序遍歷序列為JLKANMO則根結(jié)點(diǎn)A的右子樹(shù)中 的結(jié)點(diǎn)個(gè)數(shù)為_(kāi)3_。0 1 三個(gè)頂點(diǎn)vj,v2,v3的圖的鄰接矩陣為1 0 1則該圖中頂點(diǎn)V2的出度為_(kāi)2。0 0 0除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同外其余頂點(diǎn)不重復(fù)的回路稱為_(kāi)簡(jiǎn)單回路或簡(jiǎn)單環(huán)在順序查找、二分查找、散列查找和索引順序查找四種查找方法中平均查找長(zhǎng)度與元素 個(gè)數(shù)沒(méi)有關(guān)系的查找方法是 散列查找。 堆排序算法的時(shí)間復(fù)雜度為_(kāi)O(n*logn2(n)。28.如果要將序列60182869997578建成堆則只需把60與 18 相互交換。2013一01下面算法程序段的時(shí)間復(fù)雜度為0(n

31、2平方)。for(i=1;i=n;i+)for(j=1;jnext=q;p=q: p-next=NULL。向一個(gè)長(zhǎng)度為100的順序表中第貢個(gè)元素之前插入一個(gè)元素時(shí)，需向后移動(dòng)的元素個(gè)數(shù)為 51。一個(gè)帶頭結(jié)點(diǎn)的鏈棧LS,現(xiàn)將一個(gè)新結(jié)點(diǎn)入棧，指向該結(jié)點(diǎn)的指針為？，入棧操作為p-next=LS-next 和ls-next=p。 隊(duì)列操作的原則是-先進(jìn)先出。 含有n個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其最大長(zhǎng)度為n-1。在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)數(shù)為1個(gè)，度為2的結(jié)點(diǎn)數(shù)為2個(gè)，度為1的結(jié)點(diǎn)數(shù)為3個(gè)，則度為0的結(jié)點(diǎn)數(shù)為 6 個(gè)。正確答案：。解析：設(shè)這棵樹(shù)中葉子結(jié)點(diǎn)數(shù)為瑚,度數(shù)為1的結(jié)點(diǎn)數(shù)為nl,度

32、數(shù)為2的結(jié)點(diǎn)數(shù)為德，度教為3的結(jié) 點(diǎn)數(shù)為如總結(jié)點(diǎn)數(shù)為m則2抑設(shè)樹(shù)的總?cè)攵葹閙-由于在樹(shù)中除了根結(jié)點(diǎn)外，其 余每一個(gè)結(jié)點(diǎn)都有唯一的一個(gè)分支進(jìn)入，則樹(shù)的總結(jié)點(diǎn)數(shù)為n=m+l(2)又由于樹(shù)中這m個(gè)進(jìn)入分支分 別由非葉子結(jié)點(diǎn)射出，其中度數(shù)為1的結(jié)點(diǎn)射出1,度數(shù)為N的結(jié)點(diǎn)射出2,度數(shù)為3的結(jié)點(diǎn)射出3。 而且射出分支總數(shù)與總的進(jìn)入分支數(shù)相等，即m=nl+2n2+3n3(3)由式(1).(2).(3)可以得到 nO=n2+2n3+l=1+2X 2+l=6n某二叉樹(shù)的中序遍歷序列為BACDEFGH，后序遍歷序列為BCAEDGHF，則根結(jié)點(diǎn)F的左子樹(shù)上共有5 個(gè)結(jié)點(diǎn)。 設(shè)有向圖G的鄰接矩陣為A,如果0八是圖中的

33、一條弧測(cè)A ij的值為 1。一個(gè)有序表A含有15個(gè)數(shù)據(jù)元素，,且第一個(gè)元素的下標(biāo)為1，按二分查找算法查找元素A 14，所比較的元素下標(biāo)依次是_8,12,14。二分查找算法是從low=1開(kāi)始的。Hgih=有序表長(zhǎng)度1+15/2=8(814),9+15/2=12(12prior=p_t-next=p-nextp-next-prior=tp-next=t。在帶有頭結(jié)點(diǎn)的循環(huán)鏈表中頭指針為head判斷指針p所指結(jié)點(diǎn)為首結(jié)點(diǎn)的條件是p=head-next。19元素的進(jìn)棧次序?yàn)?23.n出棧的第一個(gè)元素是n則第k個(gè)出棧的元素是n-k+1。20在棧結(jié)構(gòu)中允許插入和刪除的一端稱為 棧頂。21 100個(gè)結(jié)點(diǎn)的二叉樹(shù)采用三叉鏈表存儲(chǔ)時(shí)空指針域NULL有 102 個(gè)。100個(gè)結(jié)點(diǎn)的二