數(shù)據(jù)結構(本科)形成性考核冊答案

1、1作業(yè)1一、單項選擇題1C2D3B4C5D6C7B8C9A10B11C12D13C14A15B16C17C18B19B20D二、填空題1ni12ni3集合線性結構樹形結構圖狀結構4物理結構存儲結構5線性結構非線性結構6有窮性確定性可形性有零個或多個輸入有零個或多個輸出7圖狀結構8樹形結構9線性結構10n1O(n)11snext=pnext12head13qnext=pnext14pnext=head15單鏈表16順序存儲鏈式存儲17存儲

2、結構18兩個直接后繼直接前驅(qū)尾結點頭結點19頭結點的指針指向第一個結點的指針20鏈式鏈表三、問答題1簡述數(shù)據(jù)的邏輯結構和存儲結構的區(qū)別與聯(lián)系，它們?nèi)绾斡绊懰惴ǖ脑O計與實現(xiàn)？答：若用結點表示某個數(shù)據(jù)元素，則結點與結點之間的邏輯關系就稱為數(shù)據(jù)的邏輯結構。數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結構?？梢姡瑪?shù)據(jù)的邏輯結構是反映數(shù)據(jù)之間的固有關系，而數(shù)據(jù)的存儲結構是數(shù)據(jù)在計算機中的存儲表示。盡管因采用的存儲結構不同，邏輯上相鄰的結點，其物理地址未

3、必相同，但可通過結點的內(nèi)部信息，找到其相鄰的結點，從而保留了邏輯結構的特點。采用的存儲結構不同，對數(shù)據(jù)的操作在靈活性，算法復雜度等方面差別較大。2解釋順序存儲結構和鏈式存儲結構的特點，并比較順序存儲結構和鏈式存儲結構的優(yōu)缺點。答：順序結構存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結構和存儲結構是統(tǒng)一的，，要求內(nèi)存中存儲單元的地址必須是連續(xù)的。優(yōu)點：一般情況下，存儲密度大，存儲空間利用率高。缺點：（1）在做插入和刪除操作時，需移動大量元

4、素；（2）由于難以估計，必須預先分配較大的空間，往往使存儲空間不能得到充分利用；（3）表的容量難以擴充。鏈式結構存儲時，相鄰數(shù)據(jù)元素可隨意存放，所占空間分為兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針。優(yōu)點：插入和刪除元素時很方便，使用靈活。缺點：存儲密度小，存儲空間利用率低。34、假上溢5、隊列是否已滿sq==MaxSize尾指針的值尾指針指向的數(shù)據(jù)單元隊列是否為空sq==sqfront隊頭指針加1返回front所指位置

5、的元素。6、bceda7、終止條件遞歸條件8、LUrear==Lufront9、？？abcfdc10、snext=h11、h=hnext12、rnext=s13、f=fnext14、字符15、順序存儲鏈接存儲16、0117、特殊稀疏18、()(())219、（（def））20、兩串的長度相等，且對應位置上的字符相同。21、i(i1)2j22、行號列號元素值三、簡答1、一般線性表使用數(shù)組來表示的，線性表一般有插入、刪除、讀取等對于任意元素

6、的操作。而棧只是一種特殊的線性表，棧只能在線性表的一端插入（稱為入棧push）或者讀取棧頂元素或者稱為“彈出、出?！?pop)。棧在數(shù)組的基礎上可以用一個指向棧頂?shù)臉俗R符來表示，如a表示棧，則a[top]就表示棧頂元素。2、隊列是一種運算受限的線性表它的運算限制與棧不同是兩頭都有限制插入只能在表的一端進行(只進不出)而刪除只能在表的另一端進行(只出不進)。而一般線性表是用數(shù)組來表示的，線性表一般有插入、刪除、讀取等對于任意元素的操作。3

7、、如果你的棧有頭結點且頭結點不存儲有效數(shù)據(jù)，且sq指向棧頂?shù)挠行?shù)據(jù)，那么sqnext==NULL表示?？?。如果你的棧有頭結點且頭結點存儲有效數(shù)據(jù)，且sq指向棧頂?shù)挠行?shù)據(jù)，那么sq==NULL表示?？铡?、(1)CBAABCBACBCAACB可根據(jù)棧的特點“后進先出“來的出結果不可能的是：CAB(2)可能的輸出序列：ABCDABDCACBDACDBADCBBACDBADCBCADBCDABDCACBADCBDACDBADCBA，共14

8、種不可能的輸出序列：ADBCBDACCDABCABDCADBDCABDABCDACBDBCADBAC共10種。5、SXSSXSXX6、以元素C開頭的有：CBADECBAEDCBDAECBDEACDBAECDBEACDEBACEDBA以元素D開頭的有：DCBAEDCEBADCBEADECBA7、第一個有問題3x2x1x5ABCDEFG8、一般線性表使用數(shù)組來表示的，線性表一般有插入、刪除、讀取等對于任意元素的操作。廣義表是線性表的推廣也稱