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