【文章內(nèi)容簡(jiǎn)介】 R)，D={1，2，3，4，5，6，7，8，9}，R={r}，r={1，2，1，3，1，4，2，5，2，6，3，7，3，8，3，9}，則該數(shù)據(jù)結(jié)構(gòu)是____樹(shù)形___結(jié)構(gòu)。從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，平均比較次數(shù)為：____(n+1)/2____。在中序線索二叉樹(shù)中，左線索指向 前驅(qū)或左孩子 。對(duì)于一個(gè)以順序?qū)崿F(xiàn)的循環(huán)隊(duì)列Q[0..m1]，隊(duì)頭、隊(duì)尾指針?lè)謩e為f,r，其判空的條件是 f=r ，判滿的條件是 (r+1)%m=f 。若已知一個(gè)棧的進(jìn)棧序列是1，2，3，… ，n，其輸出序列為p1，p2，p3， …，pn，若p1=n，則pi為_(kāi)__ni+1____。設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按照從自上到下、從左到右從1開(kāi)始順序編號(hào)，則第i個(gè)結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的編號(hào)為_(kāi)____2n+1__。1在一棵二叉樹(shù)中，如果度為2的結(jié)點(diǎn)有25個(gè)，則該樹(shù)的葉子結(jié)點(diǎn)一定有____26____個(gè)。1在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有__n(n1)/2__條邊。1線性結(jié)構(gòu)的邏輯特征是 除頭結(jié)點(diǎn)和尾節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)僅有一個(gè)前驅(qū)和一個(gè)后繼結(jié)點(diǎn) 。1設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹(shù)中帶權(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一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則出隊(duì)序列為：__________1234____。1設(shè)有一個(gè)順序循環(huán)隊(duì)列中有M個(gè)存儲(chǔ)單元，則該循環(huán)隊(duì)列中最多能夠存儲(chǔ)______M1_____個(gè)隊(duì)列元素。1隊(duì)列Q，經(jīng)過(guò)下列運(yùn)算：InitQueue(Q)(初始化隊(duì)列)。 InQueue(Q,a)。 InQueue(Q,b)。 DeQueue(Q, x)。 DeQueue(Q, x)。 后x值是_______b_____。1數(shù)據(jù)結(jié)構(gòu)包括了 數(shù)據(jù)的邏輯結(jié)構(gòu) 、 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 、 數(shù)據(jù)的運(yùn)算 三個(gè)方面的內(nèi)容。設(shè)一棵完全二叉樹(shù)中有300個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的深度為_(kāi)___9____。2在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有____n*(n1)__條邊。2一棵深度為 10 的完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)的最小值為_(kāi)_2^91__，最大值為_(kāi)___2^101______。2有一個(gè)有序表{3，7，8，15，18，22，34， 67，75， 84，92，100},當(dāng)用二分查找法查找鍵值為92的結(jié)點(diǎn)時(shí)，經(jīng)____3__次比較后查找成功。2遞歸算法必須依賴 堆棧 的處理來(lái)實(shí)現(xiàn)。2隊(duì)列的運(yùn)算特點(diǎn)是 先進(jìn)先出 ，棧的運(yùn)算特點(diǎn)是 先進(jìn)后出 。2設(shè)有向圖G中有向邊的集合E={1，2，2，3，1，4，4，2，4，3}，則該圖的拓?fù)湫蛄袨開(kāi)_____1423___。2在一個(gè)長(zhǎng)度為n的順序表L中，刪除下標(biāo)為i的結(jié)點(diǎn)，需要移動(dòng)的結(jié)點(diǎn)數(shù)為_(kāi)___ni1__。2假設(shè)用front表示隊(duì)頭元素在一維數(shù)組中的前一位置，rear表示對(duì)尾元素在一維數(shù)組中的位置，則隊(duì)列為空的條件是__front==rear____。2一棵含7個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi)__3____。已知二維數(shù)組A[6][10]，每個(gè)數(shù)組元素占4個(gè)存儲(chǔ)單元，若按行優(yōu)先順序存放數(shù)組元素a[3][5]的存儲(chǔ)地址是1000，則a[0][0]的存儲(chǔ)地址是______860___。3含n個(gè)頂點(diǎn)的無(wú)向連通圖中至少含有____n1__條邊。3對(duì)于棧只能在___棧頂___插入和刪除元素。3樹(shù)是n個(gè)節(jié)點(diǎn)的有限集合，其中有且僅有一個(gè)___根__節(jié)點(diǎn)沒(méi)有前趨節(jié)點(diǎn)，而包含度為0的節(jié)點(diǎn)稱為_(kāi)__n+1/2__節(jié)點(diǎn)。3指向前趨節(jié)點(diǎn)和后繼節(jié)點(diǎn)的指針?lè)Q為線索，加了線索的二叉樹(shù)稱為_(kāi)__線索二叉樹(shù)___。3常用的圖的遍歷方法有兩種；深度優(yōu)先搜索和____廣度優(yōu)先搜索_____。3為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問(wèn)題是____構(gòu)造一個(gè)好的hash函數(shù)_____和___確定解決沖突的方法____。3順序表中邏輯上相鄰的元素的物理位置 相鄰 。單鏈表中邏輯上相鄰的元素的物理位置 不 相鄰。3在一個(gè)長(zhǎng)度為n的數(shù)組的第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng) ni 個(gè)元素。四、簡(jiǎn)答題。已知兩個(gè)一元多項(xiàng)式A(x)和B(x)如下：A(x) = 3 + 5x + 7x5 + 9x15 B(x) = 4x – 7x5+ 21x7要求給出圖形示意表示：（1）采用單鏈表表示一元多項(xiàng)式A(x)和B(x)（2）給出求和A(x)+B(x)多項(xiàng)式的單鏈表（要求給出結(jié)點(diǎn)指針變化過(guò)程）簡(jiǎn)述下列術(shù)語(yǔ)：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)：指所有能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)集合。數(shù)據(jù)元素：數(shù)據(jù)集合中的一個(gè)實(shí)體，是計(jì)算機(jī)程序中加工處理的基本單位。數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的集合。即包括數(shù)據(jù)元素的集合和數(shù)據(jù)元素之間的關(guān)系的集合。存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（也稱映像）叫做物理結(jié)構(gòu)。又稱為存儲(chǔ)結(jié)構(gòu)。簡(jiǎn)述棧和線性表的差別。試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語(yǔ)言中數(shù)據(jù)類型概念的區(qū)別。抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但含義比一般數(shù)據(jù)類型更廣、更抽象。一般數(shù)據(jù)類型由具體語(yǔ)言系統(tǒng)內(nèi)部定義，直接提供給編程者定義用戶數(shù)據(jù)，因此稱它們?yōu)轭A(yù)定義數(shù)據(jù)類型。抽象數(shù)據(jù)類型通常由編程者定義，包括定義它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進(jìn)行的操作。已知一棵樹(shù)邊的集合為{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用樹(shù)形表示法畫(huà)出此樹(shù)，并回答下列問(wè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） 樹(shù)的深度是多少？ 5（10） 以結(jié)點(diǎn)c為根的子樹(shù)的深度是多少？ 2（11） 樹(shù)的度是多少？ 3何謂隊(duì)列的“假溢出”現(xiàn)象，如何解決？假溢出是是隊(duì)列在一端進(jìn)入插入，TOP值就會(huì)增加，在另一端刪除，當(dāng)判斷TOP==MAX1是，就會(huì)說(shuō)明已經(jīng)隊(duì)滿，但實(shí)際在隊(duì)列的另一端還是有存儲(chǔ)空間的，這就是“假溢出”。 解決方法：設(shè)置隊(duì)列為循環(huán)隊(duì)列就可以了。TOP=（TOP+1）MOD （MAX1）。簡(jiǎn)述隊(duì)列和堆棧這兩種數(shù)據(jù)類型的相同點(diǎn)和差異處。abdce先序：abdce中序：bdaec后序：dbeca對(duì)于下圖，試給出：（1）每個(gè)頂點(diǎn)的入度，出度。d(1)+ = 1, d(1) = 2d(2)+ = 2, d(1) = 2d(3)+ = 3, d(3) = 1d(4)+ = 3, d(4) = 0d(5)+ = 2, d(5) = 3d(6)+ = 1, d(6) = 2（2）鄰接矩陣和入邊表圖示。（3）強(qiáng)連通分量。23652 1 4 5 6 2 3鄰接表 入邊表(逆鄰接表)已知一組元素的排序碼為:（46,74,16,53,14,26,40,38,86,65,27,34）寫(xiě)出用直接選擇排序方法進(jìn)行每趟排序的結(jié)果?！?4】,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è)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)如下：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20E AF∧D∧H∧∧C∧∧∧GI∧∧∧∧B（1） 根據(jù)其存儲(chǔ)結(jié)構(gòu)，畫(huà)出該二叉樹(shù)。（2） 寫(xiě)出按前序、中序、后序遍歷該二叉樹(shù)所得的結(jié)點(diǎn)序列。前序：EADCBFHGI中序：ABCDEFGHI后序：BCDAGIHFE（3） 畫(huà)出二叉樹(shù)的后序線索化樹(shù)。1已知某電文中只有ABCDE共5個(gè)字母，權(quán)值