數(shù)據(jù)結(jié)構(gòu)第3版習(xí)題答案

1、十二五普通高等教育國(guó)家級(jí)本科規(guī)劃教材第1章緒論高等學(xué)校精品資源共享課程1.1什么是數(shù)據(jù)結(jié)構(gòu)？【答】：數(shù)據(jù)結(jié)構(gòu)是指按一定的邏輯結(jié)構(gòu)組成的一批數(shù)據(jù)，使用某種存儲(chǔ)結(jié)構(gòu)將這批數(shù)據(jù)存儲(chǔ)于計(jì)算機(jī)中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算集合。1.2數(shù)據(jù)結(jié)構(gòu)涉及哪幾個(gè)方面？【答】：數(shù)據(jù)結(jié)構(gòu)涉及三個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算集合。1.3兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)都相同，但是它們的運(yùn)算集合中有一個(gè)運(yùn)算的定義不一樣，它們是否可以認(rèn)

2、作是同一個(gè)數(shù)據(jù)結(jié)構(gòu)？為什么？【答】：不能，運(yùn)算集合是數(shù)據(jù)結(jié)構(gòu)的重要組成部分，不同的運(yùn)算集合所確定的數(shù)據(jù)結(jié)構(gòu)是不一樣的，例如，棧與隊(duì)列它們的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)可以相同，但由于它們的運(yùn)算集合不一樣，所以它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。1.4線性結(jié)構(gòu)的特點(diǎn)是什么？非線性結(jié)構(gòu)的特點(diǎn)是什么？【答】：線性結(jié)構(gòu)元素之間的關(guān)系是一對(duì)一的，在線性結(jié)構(gòu)中只有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，其他的每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)和一個(gè)后繼結(jié)點(diǎn)。而非線性結(jié)構(gòu)則沒(méi)有這個(gè)特點(diǎn)，元

3、素之間的關(guān)系可以是一對(duì)多的或多對(duì)多的。1.5數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式有哪幾種？【答】：數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、散列存儲(chǔ)和索引存儲(chǔ)等四種方式。1.6算法有哪些特點(diǎn)？它和程序的主要區(qū)別是什么？【答】：算法具有（1）有窮性（2）確定性（3）0個(gè)或多個(gè)輸入（4）1個(gè)或多個(gè)輸出（5）可行性等特征。程序是算法的一種描述方式，通過(guò)程序可以在計(jì)算機(jī)上實(shí)現(xiàn)算法。1.7抽象數(shù)據(jù)類(lèi)型的是什么？它有什么特點(diǎn)？【答】：抽象數(shù)據(jù)類(lèi)型是數(shù)據(jù)類(lèi)型的進(jìn)一步抽象

4、，是大家熟知的基本數(shù)據(jù)類(lèi)型的延伸和發(fā)展。抽象數(shù)據(jù)類(lèi)型是與表示無(wú)關(guān)的數(shù)據(jù)類(lèi)型，是一個(gè)數(shù)據(jù)模型及定義在該模型上的一組運(yùn)算。對(duì)一個(gè)抽象數(shù)據(jù)類(lèi)型進(jìn)行定義時(shí)，必須給出它的名字及各運(yùn)算的運(yùn)算符名，即函數(shù)名，并且規(guī)定這些函數(shù)的參數(shù)性質(zhì)。一旦定義了一個(gè)抽象數(shù)據(jù)類(lèi)型及具體實(shí)現(xiàn)，程序設(shè)計(jì)中就可以像使用基本數(shù)據(jù)類(lèi)型那樣，十分方便地使用抽象數(shù)據(jù)類(lèi)型。抽象數(shù)據(jù)類(lèi)型的設(shè)計(jì)者根據(jù)這些描述給出操作的具體實(shí)現(xiàn)，抽象數(shù)據(jù)類(lèi)型的使用者依據(jù)這些描述使用抽象數(shù)據(jù)類(lèi)型。1.8算法

5、的時(shí)間復(fù)雜度指的是什么？如何表示？【答】：算法執(zhí)行時(shí)間的度量不是采用算法執(zhí)行的絕對(duì)時(shí)間來(lái)計(jì)算的，因?yàn)橐粋€(gè)算法在不同的機(jī)器上執(zhí)行所花的時(shí)間不一樣，在不同時(shí)刻也會(huì)由于計(jì)算機(jī)資源占用情況的不同，使得算法在同一臺(tái)計(jì)算機(jī)上執(zhí)行的時(shí)間也不一樣，另外，算法執(zhí)行的時(shí)間還與輸入數(shù)據(jù)的狀態(tài)有關(guān)，所以對(duì)于算法的時(shí)間復(fù)雜性，采用算法執(zhí)行過(guò)程中其基本操作的執(zhí)行次數(shù)，稱為計(jì)算量來(lái)度量。算法中基本操作的執(zhí)行次數(shù)一般是與問(wèn)題規(guī)模有關(guān)的，對(duì)于結(jié)點(diǎn)個(gè)數(shù)為n的數(shù)據(jù)處理問(wèn)題，

6、用T(n)表示算法基本操作的執(zhí)行次數(shù)。為了評(píng)價(jià)算法的執(zhí)行效率，通常采用大寫(xiě)O符號(hào)表示算法的時(shí)間復(fù)雜度，大寫(xiě)O符號(hào)給出了函數(shù)f的一個(gè)上限。其它義如下：3十二五普通高等教育國(guó)家級(jí)本科規(guī)劃教材高等學(xué)校精品資源共享課程第2章線性表及其順序存儲(chǔ)2.1選擇題（1）表長(zhǎng)為n的順序存儲(chǔ)的線性表，當(dāng)在任何位置上插入或刪除一個(gè)元素的概率相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為（為（A）。E），刪除一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)A（n?1）2En2BnF

7、(n1)2Cn1G(n?2)2Dn?1（2）設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的序列為e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該為（C）。A6B4C3D2（3）設(shè)棧的輸入序列為1、2、3…n，若輸出序列的第一個(gè)元素為n，則第i個(gè)輸出的元素為（B）。A不確定Bn?i1CiDn?i（4）在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（1=i=n）

8、時(shí)，需向前移動(dòng)（A）個(gè)元素。An?iBn?i1Cn?i?1Di（5）若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，在第i個(gè)位置上插入一個(gè)新元素的時(shí)間復(fù)雜度為（A）。AO(n)BO(1)CO(n2)DO(n3)（6）表達(dá)式a(bc)?d的后綴表達(dá)式是（B）。Aabcd?Babcd?Cabcd?D?abcd（7）隊(duì)列是一種特殊的線性表，其特殊性在于（C）。A插入和刪除在表的不同位置執(zhí)行B插入和刪除在表的兩端位置執(zhí)行C插入和刪除分別在表的兩端執(zhí)行D

9、插入和刪除都在表的某一端執(zhí)行（8）棧是一種特殊的線性表，具有（B）性質(zhì)。A先進(jìn)先出B先進(jìn)后出C后進(jìn)后出D順序進(jìn)出（9）順序循環(huán)隊(duì)列中（數(shù)組的大小為n），隊(duì)頭指示front指向隊(duì)列的第1個(gè)元素，隊(duì)尾指示rear指向隊(duì)列最后元素的后1個(gè)位置，則循環(huán)隊(duì)列中存放了n?1個(gè)元素，即循環(huán)隊(duì)列滿的條件為（B）。A(rear1)%n=front?1C(rear)%n=frontB(rear1)%n=frontDrear1=front（10）順序循環(huán)隊(duì)列