數(shù)據(jù)結(jié)構(gòu)(本科)形成性考核冊答案

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

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

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

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

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

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

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

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