數(shù)據(jù)結(jié)構(gòu)章節(jié)練習(xí)題及答案3

1、第3章棧和隊(duì)列.具有什么特征的數(shù)據(jù)結(jié)構(gòu)被稱為棧和隊(duì)列？先進(jìn)后出、棧頂、棧底、先進(jìn)先出、隊(duì)頭、隊(duì)尾的概念是什么?棧：一種插入和刪除都只能在表的同一端進(jìn)行的線性表。隊(duì)列：一種只允許在表的一端進(jìn)行插入操作，而在表的另一端進(jìn) 行刪除操作的線性表。先進(jìn)后出：元素是以生，e2,聲順序進(jìn)入數(shù)據(jù)結(jié)構(gòu)，以相反 的順序即en.i, ei離開數(shù)據(jù)結(jié)構(gòu)。棧頂：允許進(jìn)行插入和刪除操作的一端。棧底：棧中與棧頂相對的另一端。先進(jìn)先出：元素是以白，e2,品順序進(jìn)入數(shù)據(jù)結(jié)構(gòu)，以相同 的順序即ei, e2,eno離開數(shù)據(jù)結(jié)構(gòu)。隊(duì)頭：允許刪除操作的一端。隊(duì)尾：允許插入操作的一端。.簡述在順序棧的棧頂插入一個(gè)元素的操作過程。在插入元

2、素之前，首先要判斷棧是否為滿，如果棧滿，返回“沾 滿無法插入”等錯(cuò)誤提示信息；否那么讓top指針（指向當(dāng)前順序棧的 棧頂）向后移動(dòng)一個(gè)元素空間（元素大小），將要插入的元素放入top 指針指向的內(nèi)存單元中。. 一個(gè)棧的輸入序列為1、2、3,試給出全部可能的出棧序列?？煞譃槿N情況：當(dāng)只有一個(gè)存儲空間時(shí)，只有一種出棧序列：1、2、3.、當(dāng)有兩個(gè)存儲空間時(shí)，有：1、2、3,2、1、3,2、3、1等3種出棧序列、當(dāng)存儲空間大于等于三個(gè)時(shí)，有：1、2、3,2、1、3,2、3、1,3、2、1等4種出棧序列。.循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？在循環(huán)隊(duì)列中，僅依據(jù)頭尾指針相 等，無法判斷隊(duì)列是“空”還是“滿”。要解決這

3、個(gè)問題，常用的兩種方 法是什么？循環(huán)隊(duì)列的優(yōu)點(diǎn)有兩點(diǎn)：一是可以防止發(fā)生順序隊(duì)列的“假上溢” 現(xiàn)象；二是充分利用隊(duì)列的存儲空間。兩種判斷隊(duì)列是“空”還是“滿”的方法：一是約定少用一個(gè)元素空 間；二是使用計(jì)數(shù)器size記錄當(dāng)前隊(duì)列的實(shí)際長度。.簡述在鏈接棧中插入一個(gè)元素的操作過程。鏈接棧的插入操作，先將待進(jìn)棧結(jié)點(diǎn)的指針域指向原來的棧頂結(jié) 點(diǎn)，然后將棧頂指針top修改指向該結(jié)點(diǎn)，使進(jìn)棧元素結(jié)點(diǎn)成為新的 棧頂結(jié)點(diǎn)。6,請列舉出一些可以用棧和隊(duì)列表示的實(shí)際問題。所有“后進(jìn)先出”(LIFO, Last In First Out)的實(shí)際問題都可以用棧 表示。棧的應(yīng)用主要有：數(shù)制的轉(zhuǎn)換、括號的匹配檢查、行編輯處理、 表達(dá)式求解、走迷宮以及高級語言中函數(shù)的嵌套調(diào)用和遞歸的實(shí)現(xiàn)所有“先進(jìn)先出”(FIFO, First In First Out)的實(shí)際問題都可以用隊(duì) 列表示。如日常中的排隊(duì)問題，隊(duì)列的應(yīng)用主要有：操作系統(tǒng)中各種 資源請