2019國(guó)開(kāi)電大《程序設(shè)計(jì)基礎(chǔ)》形考任務(wù)3答案[共5頁(yè)]

1、程序設(shè)計(jì)基礎(chǔ)形考任務(wù)3：1數(shù)據(jù)結(jié)構(gòu)研究主要包括三個(gè)方面的內(nèi)容，分別是：數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，以及定義在這上面的數(shù)據(jù)的運(yùn)算。2當(dāng)向一個(gè)順序表插入一個(gè)元素時(shí)，從插入位置開(kāi)始后的所有元素均需向后移動(dòng)一個(gè)位置，移動(dòng)過(guò)程是從后向前依次移動(dòng)每一個(gè)元素。3要從一個(gè)順序表刪除一個(gè)元素時(shí)，被刪除之后的所有元素均需向前移動(dòng)一個(gè)位置，移動(dòng)過(guò)程是從前向后依次移動(dòng)每一個(gè)元素。4線性表、棧和隊(duì)列都是線性結(jié)構(gòu)，可以在線性表的任意位置插入和刪除元素，而棧只能在棧頂插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾插入元素，在隊(duì)頭刪除元素。5如果要在鏈表中刪除一個(gè)元素，則只要將要?jiǎng)h除的元素的前一個(gè)元素的指針調(diào)整為指向要?jiǎng)h除的元素的下

2、一個(gè)元素。6為了解決假溢出，通常采用循環(huán)隊(duì)列的方法，即把隊(duì)列的存儲(chǔ)空間設(shè)想成一個(gè)頭尾相接的環(huán)狀結(jié)構(gòu)。7二叉樹(shù)的第 i 層上至多有2i-1(i1)個(gè)結(jié)點(diǎn)。8在任意二叉樹(shù)中，若有n0個(gè)葉子結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，則必有：n0=n2+19深度為h且含有2h -1個(gè)結(jié)點(diǎn)的二叉樹(shù)為 滿 二叉樹(shù)。10深度為5的二叉樹(shù)中至多含有 31 點(diǎn)。二、選擇題（每題6分，合計(jì)60分）2數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)分為兩種，它們是_。選擇一項(xiàng)：A. 數(shù)組存儲(chǔ)和指針存儲(chǔ)B. 順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)C. 線性存儲(chǔ)和樹(shù)型存儲(chǔ)D. 線性存儲(chǔ)和數(shù)組存儲(chǔ)3如果在內(nèi)存中采用鏈?zhǔn)奖４婢€性表，則元素之間的邏輯關(guān)系通過(guò)_。選擇一項(xiàng)：A. 保存在元素中的指

3、針表示先后次序B. 元素本身的關(guān)鍵字來(lái)表示邏輯次序C. 元素在內(nèi)存中的相對(duì)位置表示邏輯次序D. 設(shè)立單獨(dú)的區(qū)域存儲(chǔ)元素之間的邏輯次序4進(jìn)行順序查找的條件是_。選擇一項(xiàng)：A. 數(shù)據(jù)有序且采用鏈?zhǔn)酱鎯?chǔ)方式B. 數(shù)據(jù)不需要有序，但需要順序存儲(chǔ)C. 數(shù)據(jù)有序且采用順序存儲(chǔ)方式D. 數(shù)據(jù)不需要有序，也不限制存儲(chǔ)方式5隊(duì)列的最主要特點(diǎn)是_。選擇一項(xiàng)：A. 先進(jìn)后出B. 兩端進(jìn)出C. 先進(jìn)先出D. 一端進(jìn)一端出6如果在具有層次結(jié)構(gòu)的一組元素中，存在著一對(duì)一的關(guān)系，我們可以認(rèn)為這樣的數(shù)據(jù)的邏輯類型就是_。選擇一項(xiàng)：A. 樹(shù)型結(jié)構(gòu)B. 線性結(jié)構(gòu)C. 集合D. 圖型結(jié)構(gòu)7在任意二叉樹(shù)中，如有N個(gè)葉子結(jié)點(diǎn)，M個(gè)度為

4、 _ 的節(jié)點(diǎn)，則必有_。選擇一項(xiàng)：A. 2 N=M+1B. 1 N=M+2C. 2 N=M+28若按照一定的順序依次訪問(wèn)樹(shù)中的每一個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)只被訪問(wèn)一次，則稱這樣的操作為_(kāi)。選擇一項(xiàng)：A. 查找B. 建立C. 遍歷D. 排序9對(duì)如圖所示的二叉樹(shù)進(jìn)行先序遍歷的頂點(diǎn)序列是_，后序遍歷時(shí)得到的頂點(diǎn)序列是_。選擇一項(xiàng)：A. DEBAC ABDECB. EDBCA DEBACC. ABDEC EDBCA10設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳，B，C，D，E，下列是不可能的出棧序列。選擇一項(xiàng)：A. B，C，D，E，AB. E，A，B，C，DC. E，D，C，B，AD. A，B，C，D，E11已知一個(gè)圖如下所示，則從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索遍歷可以得到的一種頂點(diǎn)序列為