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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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