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