西南交大數(shù)據(jù)結(jié)構(gòu)主觀題作業(yè)(編輯修改稿)
2025-04-21 07:41 本頁面
【文章內(nèi)容簡(jiǎn)介】 入序列是12345，則棧的輸出序列43512是參考答案：錯(cuò)誤的64.設(shè)棧采取順序存儲(chǔ)結(jié)構(gòu)，棧中已有i1個(gè)元素，則第i個(gè)元素進(jìn)棧操作的算法時(shí)間復(fù)雜度是參考答案：O（1）65.棧的特點(diǎn)是【① 】，隊(duì)列的特點(diǎn)是【② 】；棧和隊(duì)列都是【③ 】若入棧序列是1，2，3，4 ，則【④ 】是不可能的出棧序列；若進(jìn)隊(duì)列的序列是1，2，3，4，則【⑤ 】是可能的出隊(duì)序列。參考答案：①后進(jìn)先出②先進(jìn)先出③限制存取點(diǎn)的線性結(jié)構(gòu)④3,2,1,4⑤1,2,3,466.若用不帶頭結(jié)點(diǎn)的單鏈表表示棧，則創(chuàng)建一個(gè)空棧要執(zhí)行的操作是參考答案：top=NULL67.從循環(huán)隊(duì)列中刪除一個(gè)元素的操作是參考答案：=(+1)%QSize68.從循環(huán)隊(duì)列中插入一個(gè)元素的操作是參考答案： =(+1)%QSize69.判斷鏈隊(duì)列中只有一個(gè)結(jié)點(diǎn)的條件是參考答案：next==70.如果棧的最大長(zhǎng)度難以估計(jì)，最好使用參考答案：鏈棧71.為什么說棧是一種后進(jìn)先出表？參考答案：因?yàn)闂Ｊ窍薅ㄔ诒淼囊欢诉M(jìn)行插入和刪除操作，所以后入棧的數(shù)據(jù)元素總是先出棧，所以說棧是一種后進(jìn)先出表。72.對(duì)于一個(gè)棧，其輸入序列是A,B,C,試給出全部可能的輸出序列。參考答案：可能的出棧序列是：ABC、ACB、BAC、BCA、CBA。73.何謂隊(duì)列上溢？何為假溢出現(xiàn)象？有哪些解決假溢出問題的方法，并分別闡述其工作原理。參考答案：隊(duì)列上溢指在隊(duì)列的順序存儲(chǔ)分配中，按照隊(duì)列的操作規(guī)則，需要進(jìn)隊(duì)的元素因找不到合適的存儲(chǔ)單元而無法進(jìn)入隊(duì)列。假溢出指在隊(duì)列的順序存儲(chǔ)分配中，分配給隊(duì)列的存儲(chǔ)空間有存儲(chǔ)單元未被占用，但按照操作規(guī)則而使進(jìn)隊(duì)的數(shù)據(jù)元素?zé)o法進(jìn)隊(duì)的現(xiàn)象。解決假溢出問題的方法是在隊(duì)列的順序存儲(chǔ)分配中，分配給隊(duì)列的存儲(chǔ)空間可以循環(huán)使用，其進(jìn)本原理是用表示隊(duì)頭和隊(duì)尾指針與分配給隊(duì)列的存儲(chǔ)空間長(zhǎng)度進(jìn)行取模運(yùn)算。即：入隊(duì)操作：=(+1)%MSize出隊(duì)操作：=(+1)%MSize74.隊(duì)列可以用單循環(huán)鏈表來實(shí)現(xiàn)，故可以只設(shè)一個(gè)頭指針或只設(shè)一個(gè)尾指針，請(qǐng)分析用哪種方案最合適。參考答案：使用循環(huán)鏈表來表示隊(duì)列，設(shè)置尾指針比較合適，因?yàn)槿腙?duì)操作可以直接在尾結(jié)點(diǎn)后進(jìn)行插入操作，出隊(duì)操作時(shí)可以根據(jù)尾指針很容易找到鏈表的頭結(jié)點(diǎn)，入隊(duì)出隊(duì)操作的算法時(shí)間復(fù)雜度均為O(1)。若只設(shè)頭指針，則出隊(duì)操作的算法時(shí)間復(fù)雜度為O(1)，入隊(duì)操作的算法時(shí)間復(fù)雜度為O(n)。75.深度為k的完全二叉樹至少有個(gè)結(jié)點(diǎn)，至多有個(gè)結(jié)點(diǎn)。參考答案：2K1 ,2K176.在一棵二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則有n0=參考答案：n2+177.一棵二叉樹第i層最多有個(gè)結(jié)點(diǎn)，一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹共有個(gè)結(jié)點(diǎn)，共有個(gè)葉結(jié)點(diǎn)。參考答案：2i1 ,2K1 ,2K178.根據(jù)二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹共有 種不同形態(tài)，它們分別是參考答案：5 ,79.有一棵如下圖所示的樹，回答下列問題：①這棵樹的根結(jié)點(diǎn)是②這棵樹的葉子結(jié)點(diǎn)是③結(jié)點(diǎn)c的度為④這棵樹的深度是⑤結(jié)點(diǎn)c的孩子結(jié)點(diǎn)是⑥結(jié)點(diǎn)c的雙親結(jié)點(diǎn)是⑦這棵樹的度是參考答案：
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1