【正文】 B）棧C）隊(duì)列 D）樹3下面程序段的時(shí)間復(fù)雜度是( A )。 for( i =0。 i++) for(j=0。j++) s +=B[i][j]。 A） O(n2) B） O(n)C） O(m*n) D）O(1) 3二叉樹第i(i≥1)層上至多有（ C ）結(jié)點(diǎn)。A）pnext=pnextnext B）p=pnextC）p=pnexenext D）pnext=p4設(shè)一數(shù)列的順序?yàn)?，2，3，4，5，6，通過(guò)棧結(jié)構(gòu)不可能排成的順序數(shù)列為（ B ）。 A）9 B）11 C）15 D）不能確定4對(duì)待排序的元素序列進(jìn)行劃分，將其分為左、右兩個(gè)子序列，再對(duì)兩個(gè)子序列施加同樣的排序操作，直到子序列為空或只剩一個(gè)元素為止。A）直接選擇排序 B）直接插入排序 C）快速排序 D）起泡排序4設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè)元素，其存儲(chǔ)地址為1，每元素占1個(gè)地址空間，則a85的地址為（ B ）。A）3 B）4 C）5 D）14線索二叉樹中某結(jié)點(diǎn)D，沒(méi)有左孩子的條件是（ B ）。A）LIFO B）FIFOC）FCFS D）HPF4與無(wú)向圖相關(guān)的術(shù)語(yǔ)有（ C ）。A）不唯一 B）權(quán)的總和唯一C）不含回路 D）有n條邊50、若采用鄰接矩陣法存儲(chǔ)一個(gè)n個(gè)頂點(diǎn)的無(wú)向圖，則該鄰接矩陣是一個(gè)（ D ）。A）必須是連續(xù)的 B）連續(xù)不連續(xù)都可以C）部分地址必須是連續(xù) D）必須是不連續(xù)的5倘若在對(duì)串的插入、刪除運(yùn)算中，期望運(yùn)算速度最快，則應(yīng)采用（ B ）。 A）front==rear+1 B）rear==front+1 C）front==rear D）front==0 二、判斷題（對(duì)的打√，錯(cuò)的打 ╳）算法和程序都應(yīng)具有下面一些特征：有輸入，有輸出，確定性，有窮性，有效性。（ 1 ）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)。（ 1 ）數(shù)據(jù)的邏輯結(jié)構(gòu)反映了數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式。（ 1 ）在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為：(rear+l)％n=front。（ 0 ）在鐵路的列車調(diào)度中，假設(shè)兩側(cè)鐵道均為單向行駛道，如果進(jìn)站的列車序列為123456，則一定能得到435612和135426的出站序列。（ 0 ）1數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系，即不是線性的也不是樹形的。（ 0 ）1設(shè)散列表長(zhǎng)度為m，散列函數(shù)為H（key）=key% p，為了減少發(fā)生沖突的可能性，p應(yīng)取小于m的最大奇數(shù)。（ 1 ）1引入線索二叉樹的目的是為了能在二叉樹中方便的進(jìn)行插入與刪除。（ 0 ）1在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(0163。n)時(shí)，需向前移動(dòng)ni個(gè)元素。=（ 0 ）在鐵路的列車調(diào)度中，假設(shè)兩側(cè)鐵道均為單向行駛道，如果進(jìn)站的列車序列為123456，則只能得到654321的出站序列。（ 0 ）2廣義表((a,b),a,b)的表頭和表尾是相等的。（ 1 ）2插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也會(huì)經(jīng)常使用。（ 1 ）2一個(gè)帶權(quán)無(wú)向連通圖的最小生成樹有一棵或多棵。（ 1 ）2樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加1。（ 1 ）三、填空題。有向圖的邊稱為 弧 ，邊的始點(diǎn)稱為 弧尾 ，邊的終點(diǎn)稱為 弧頭 。若一個(gè)算法中的語(yǔ)句頻度之和為T（n）=3n+nlog2n+n2，則算法的時(shí)間復(fù)雜度為 O(T（n）)___ 。 i=n。 for (j=1。 j++) sum+=j。從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，平均比較次數(shù)為：____(n+1)/2____。對(duì)于一個(gè)以順序?qū)崿F(xiàn)的循環(huán)隊(duì)列Q[0..m1]，隊(duì)頭、隊(duì)尾指針?lè)謩e為f,r，其判空的條件是 f=r ，判滿的條件是 (r+1)%m=f 。設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開(kāi)始順序編號(hào)，則第i個(gè)結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的編號(hào)為_(kāi)____2n+1__。1在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有__n(n1)/2__條邊。1設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長(zhǎng)度之和為_(kāi)___45____1設(shè)有向圖G中有向邊的集合E={1，2，1，3，2，4，3，2，3，4，4，5}，則該圖的拓?fù)湫蛄袨開(kāi)____13245____。1設(shè)有一個(gè)順序循環(huán)隊(duì)列中有M個(gè)存儲(chǔ)單元，則該循環(huán)隊(duì)列中最多能夠存儲(chǔ)______M1_____個(gè)隊(duì)列元素。 InQueue(Q,a)。 DeQueue(Q, x)。 后x值是_______b_____。設(shè)一棵完全二叉樹中有300個(gè)結(jié)點(diǎn)，則該二叉樹的深度為_(kāi)___9____。2一棵深度為 10 的完全二叉樹的結(jié)點(diǎn)總數(shù)的最小值為_(kāi)_2^91__，最大值為_(kāi)___2^101______。2遞歸算法必須依賴 堆棧 的處理來(lái)實(shí)現(xiàn)。2設(shè)有向圖G中有向邊的集合E={1，2，2，3，1，4，4，2，4，3}，則該圖的拓?fù)湫蛄袨開(kāi)_____1423___。2假設(shè)用front表示隊(duì)頭元素在一維數(shù)組中的前一位置，rear表示對(duì)尾元素在一維數(shù)組中的位置，則隊(duì)列為空的條件是__front==rear____。已知二維數(shù)組A[6][10]，每個(gè)數(shù)組元素占4個(gè)存儲(chǔ)單元，若按行優(yōu)先順序存放數(shù)組元素a[3][5]的存儲(chǔ)地址是1000，則a[0][0]的存儲(chǔ)地址是______860___。3對(duì)于棧只能在___棧頂___插入和刪除元素。3指向前趨節(jié)點(diǎn)和后繼節(jié)點(diǎn)的指針?lè)Q為線索，加了線索的二叉樹稱為_(kāi)__線索二叉樹___。3為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問(wèn)題是____構(gòu)造一個(gè)好的hash函數(shù)_____和___確定解決沖突的方法____。單鏈表中邏輯上相鄰的元素的物理位置 不 相鄰。四、簡(jiǎn)答題。數(shù)據(jù)：指所有能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)集合。數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的集合。存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（也稱映像）叫做物理結(jié)構(gòu)。簡(jiǎn)述棧和線性表的差別。抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但含義比一般數(shù)據(jù)類型更廣、更抽象。抽象數(shù)據(jù)類型通常由編程者定義，包括定義它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進(jìn)行的操作。（1） 哪個(gè)是根結(jié)點(diǎn)？ a（2） 哪些是葉結(jié)點(diǎn)？ d m n j k f l（3） 哪個(gè)是g的雙親？ c（4） 哪些是g的祖先？ a b c（5） 哪些是g的孩子？ j k（6） 哪些是e的子孫？ i m n（7） 哪些是e的兄弟？哪些是f的兄弟？ dgfh degh（8） 結(jié)點(diǎn)b和n的層次各是多少？ 2 5（9） 樹的深度是多少？ 5（10） 以結(jié)點(diǎn)c為根的子樹的深度是多少？ 2（11） 樹的度是多少？ 3何謂隊(duì)列的“假溢出”現(xiàn)象，如何解決？假溢出是是隊(duì)列在一端進(jìn)入插入，TOP值就會(huì)增加，在另一端刪除，當(dāng)判斷TOP==MAX1是，就會(huì)說(shuō)明已經(jīng)隊(duì)滿，但實(shí)際在隊(duì)列的另一端還是有存儲(chǔ)空間的，這就是“假溢出”。TOP=（TOP+1）MOD （MAX1）。abdce先序：abdce中序：bdaec后序：dbeca對(duì)于下圖，試給出：（1）每個(gè)頂點(diǎn)的入度，出度。（3）強(qiáng)連通分量。【14】,74,16,53,46,26,40,38,86,65,27,34【14,16】,74,53,46,26,40,38,86,65,27,34【14,16,26】,53,46,74,40,38,86,65,27,34【14,16,26,27】,46,74,40,38,86,65,53,34【14,16,26,27,34】,74,40,38,86,65,53,46【14,16,26,27,34,38】,40,74,86,65,53,46【14,16,26,27,34,38,40】,74,86,65,53,46【14,16,26,27,34,38,40,46】,86,65,53,74【14,16,26,27,34,38,40,46,53】,65,86,74【14,16,26,27,34,38,40,46,53,65】,86,74【14,16,26,27,34,38,40,46,53,65,74】,86【14,16,26,27,34,38,40,46,53,65,74,86】1設(shè)二叉樹的順序存儲(chǔ)結(jié)構(gòu)如下：1 2 3 4 5 6 7 8 9 10 11