大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》各章節(jié)測(cè)試題與答案

《數(shù)據(jù)結(jié)構(gòu)與算法》的答案

第I章

第2章

第3章

第4章

第5章

第6章

第7章

問(wèn)題：1.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成()。

答案：線性結(jié)構(gòu)和非線性結(jié)構(gòu)

問(wèn)題：2.在數(shù)據(jù)結(jié)構(gòu)中,從存儲(chǔ)結(jié)構(gòu)上可以將之分為()。

答案：順序存儲(chǔ)和非順序存儲(chǔ)

問(wèn)題：3.某算法的時(shí)間復(fù)雜度是0(M2),表明該算法的(??)。

答案：執(zhí)行時(shí)間與M2成正比

問(wèn)題：4.在下面的程序段中,x=x+l;的語(yǔ)句頻度為()。for(i=l;i<=n;i++)

for(j=l;j<=n;j++)x=x+l;

答案：0(nA2)

問(wèn)題：5.以下數(shù)據(jù)結(jié)構(gòu)中,()是非線性數(shù)據(jù)結(jié)構(gòu)。

答案：樹

問(wèn)題：6.順序存儲(chǔ)，存儲(chǔ)單元的地址()。

答案：一定連續(xù)

問(wèn)題：7.評(píng)價(jià)一個(gè)算法性能好壞的重要標(biāo)準(zhǔn)是（）。

答案：算法的時(shí)間和空間復(fù)雜度

問(wèn)題：8.若需要利用形式參數(shù)直接訪問(wèn)修改實(shí)參值，則應(yīng)將形參說(shuō)明為（）參

數(shù)。

答案：指針

問(wèn)題：9.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。

答案：錯(cuò)誤

問(wèn)題：10.數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是算法的時(shí)間復(fù)雜度和空

間復(fù)雜度。

答案：正確

第8章

第9章

第10章

第11章

第12章

第13章

第14章

問(wèn)題：1.下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)（）。

答案：存儲(chǔ)密度大

問(wèn)題：2.若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)

行插入和刪除運(yùn)算，則利用()存儲(chǔ)方式最節(jié)省時(shí)間。

答案：順序表?？

問(wèn)題：3.設(shè)某順序表中第一個(gè)元素的地址是se(下標(biāo)從1開始)，每個(gè)結(jié)點(diǎn)占

m個(gè)單元，則第i個(gè)結(jié)點(diǎn)的地址為()。

答案:se+(i-l)xm

問(wèn)題：4.某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和

刪除第一個(gè)元素,則采用0存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

答案：僅有尾指針的單循環(huán)鏈表

問(wèn)題：5.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)

新元素的算法的時(shí)間復(fù)雜度為()。

答案：O(n)??

問(wèn)題：6.在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是

()。

答案：s->next=p->next;p->next=s;

問(wèn)題：7.對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的

條件是()。????????

答案：head-next==NULL;

問(wèn)題：8.靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移

動(dòng)。

答案：正確

問(wèn)題：9.順序表適宜于順序存取，而鏈表適宜于隨機(jī)存取。

答案：錯(cuò)誤

問(wèn)題：10.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上

并不一定相鄰。

答案：正確

第15章

第16章

第17章

第18章

第19章

第20章

第21章

第22章

第23章

問(wèn)題：1.棧和隊(duì)列都是（）。

答案：限制存取點(diǎn)的線性結(jié)構(gòu)?？

問(wèn)題：2.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el,e2,e3,e4,e5和e6依次通

過(guò)棧S,一個(gè)元素出棧后隨即進(jìn)入隊(duì)列Q,若6個(gè)元素出隊(duì)的序列是

e2,e4,e3,e6,e5,el,則棧S的容量至少應(yīng)該是（）。

答案：3

問(wèn)題：3.設(shè)計(jì)一個(gè)判別表達(dá)式中括號(hào)是否匹配出現(xiàn)的算法，采用（）的數(shù)據(jù)結(jié)

構(gòu)最佳。

答案：棧？？

問(wèn)題：4.表達(dá)式a*（b+c）-d的后綴表達(dá)式是（）。

答案：abc+*d-??

問(wèn)題：5.遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址需要用一種（）的數(shù)據(jù)

結(jié)構(gòu)。

答案?^9999999999

問(wèn)題：6.最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針為rear,隊(duì)頭指針為front,則隊(duì)

空的條件是（）。

答案：rear==front????????

問(wèn)題：7.用帶頭結(jié)點(diǎn)的單鏈表表示隊(duì)長(zhǎng)大于1的隊(duì)列時(shí)，其隊(duì)頭指針指向隊(duì)

頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)（）。

答案：僅修改隊(duì)頭指針

問(wèn)題：8.對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新

結(jié)點(diǎn)的時(shí)間復(fù)雜度和在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度

分別為（）。

答案:O（l）,O（n）??

問(wèn)題：9.兩順序棧共享空間，也存在空間溢出問(wèn)題。

答案：正確

問(wèn)題：10.在對(duì)不帶頭結(jié)點(diǎn)的鏈隊(duì)列作出隊(duì)操作時(shí)，不會(huì)改變頭指針的值。

答案：錯(cuò)誤

第24章

第25章

第26章

第27章

第28章

第29章

第3（）章

問(wèn)題：1.串是一種特殊的線性表，其特殊性體現(xiàn)在（）。

答案：數(shù)據(jù)元素是字符

問(wèn)題：2.若串S=，software：其前綴真子串的數(shù)目是（）。

答案：7

問(wèn)題：3.設(shè)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位

置的算法稱為（）。

答案：串的模式匹配?？

問(wèn)題：4.已知串S='aaab'其next函數(shù)值為（）。

答案：0123

問(wèn)題：5.函數(shù)strcmp（'stcabuc','stbabuc'）的返回值是（）。

答案：1

問(wèn)題：6.KMP算法的特點(diǎn)是在模式匹配時(shí)指示主串的指針不會(huì)回溯。

答案：正確

問(wèn)題：7.模式串？?P=，abaabcac，的next函數(shù)值序列為01122312。

答案：正確

問(wèn)題：8.串的存儲(chǔ)結(jié)構(gòu)有順序串、堆串和塊鏈串三種。

答案：正確

問(wèn)題：9.子串的定位運(yùn)算稱為串的模式匹配。

答案：正確

問(wèn)題：10.串，student，和'Student'相等。

答案：錯(cuò)誤

第31章

第32章

第33章

第34章

第35章

問(wèn)題：1.假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array口…100,1…10()],設(shè)每個(gè)

數(shù)組元素占2個(gè)存儲(chǔ)單元，基地址為1(),則LOC[5,5]=()。

答案：818

問(wèn)題：2.若對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包

括主對(duì)角線上所有元素)依次存放于一維數(shù)組B[1…(n(n+l))⑵中，則在B中

確定aij(i<j)的位置k的計(jì)算公式為()。

答案：i(i-l)/2+j

問(wèn)題:3.設(shè)廣義表L=((a,b,c)),則L的長(zhǎng)度和深度分別為()。

答案：1和2

問(wèn)題：4.在稀疏矩陣的三元組順序表中，每個(gè)三元組表示()。

答案：矩陣中非零元素的行號(hào)、列號(hào)和數(shù)據(jù)值

問(wèn)題：5.多維數(shù)組可以看作是一種特殊的線性表。

答案：正確

問(wèn)題：6.一個(gè)稀疏矩陣A[m,n]采用三元組順序表形式表示，若把三元組中

有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把m和n的值互換，則就完成了A[m,n]的

轉(zhuǎn)置運(yùn)算。？？

答案：錯(cuò)誤

問(wèn)題：7.廣義表B=(a,B)=(a,(a,(a,...,??)))的長(zhǎng)度為無(wú)窮大。

答案：正確

問(wèn)題：8.一個(gè)廣義表可以為其它廣義表所共享。

答案：正確

問(wèn)題：9.稀疏矩陣中非零元素的個(gè)數(shù)遠(yuǎn)小于矩陣中元素的總數(shù)。

答案：正確

問(wèn)題：10.tail(head(((a,b,c,d,e))))=(a,b,c,d,e)?

答案：錯(cuò)誤

第36章

第37章

第38章

第39章

第4()章

第41章

第42章

第43章

第44章

第45章

第46章

第47章

第48章

第49章

第50章

第51章

問(wèn)題：1.樹最適合用來(lái)表示的結(jié)構(gòu)是（??）。

答案：元素間具有分支及層次關(guān)系的結(jié)構(gòu)

問(wèn)題：2.任意一棵二叉樹的葉子結(jié)點(diǎn)在其先序、中序、后序序列中的相對(duì)

位置（）。

答案：肯定不發(fā)生變化

問(wèn)題：3.判斷線索二叉樹中某結(jié)點(diǎn)P有左孩子的條件是（）。

答案：p->LTag==0

問(wèn)題：4.設(shè)森林T中有4棵樹，其結(jié)點(diǎn)個(gè)數(shù)分別為nl,n2,n3,n4,那么當(dāng)森林

T轉(zhuǎn)換成一棵二叉樹后，則根結(jié)點(diǎn)的右子樹上有（??）個(gè)結(jié)點(diǎn)。

答案：n2+n3+n4

問(wèn)題：5.以數(shù)據(jù)集｛4,5,6,7,10,12,18｝為葉結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹，其帶

權(quán)路徑長(zhǎng)度為（）。

答案：165

問(wèn)題：6.以下屬于前綴編碼的是（）。

答案：{0,1101,1110,1100,1111}

問(wèn)題：7.一棵具有N個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表進(jìn)行存儲(chǔ),其中空指針域

有（？?）個(gè)。

答案：N+1

問(wèn)題：8.已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn),3個(gè)度為2的結(jié)點(diǎn),4個(gè)

度為3的結(jié)點(diǎn)，則該樹中有（）個(gè)葉子結(jié)點(diǎn)。

答案：12

問(wèn)題：9.滿二叉樹一定完全是二叉樹。

答案：正確

問(wèn)題：10.二叉樹的遍歷結(jié)果不是唯一的。

答案：正確

第52章

第53章

第54章

第55章

第56章

第57章

第58章

第59章

第60章

第61章

第62章

第63章

第64章

第65章

第66章

問(wèn)題：1.一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖最多有（）邊。

答案：n（n-l）/2??

問(wèn)題：2.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則占

用的存儲(chǔ)空間為（??）?

答案:n+2e

問(wèn)題：3.如果含有n個(gè)頂點(diǎn)的圖形成一個(gè)環(huán)，則它有（？?）棵生成樹。

答案：n

問(wèn)題：4.任何一個(gè)無(wú)向連通網(wǎng)的最小生成樹（）。

答案：有一棵或多棵

問(wèn)題：5.判斷一個(gè)有向圖是否存在回路,可以用（）。

答案：深度優(yōu)先遍歷算法

問(wèn)題：6.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（？?）。

答案：從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑

問(wèn)題：7.深度優(yōu)先遍歷類似于二叉樹的（）。

答案：先序遍歷?？

問(wèn)題：8.廣度優(yōu)先遍歷類似于二叉樹的（）。

答案：層次遍歷

問(wèn)題：9.迪杰斯特拉算法求最短路徑時(shí)，是按照路徑長(zhǎng)度遞增的順序求解

的。

答案：正確

問(wèn)題：10.任何一個(gè)有向圖都一定存在拓?fù)湫蛄小?/p>

答案：錯(cuò)誤

第67章

第68章

第69章

第70章

第71章

第72章

第73章

第74章

第75章

問(wèn)題：1.具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度（）。

答案：'37/12

問(wèn)題：2.如果要求用線性表既能較快地查找，又能適應(yīng)動(dòng)態(tài)變化的要求，則

可采用（？?）查找方法。

答案：分塊查找

問(wèn)題：3.已知一如下10個(gè)記錄的表，其關(guān)鍵字序列為

（2,15,19,25,30,34,44,55,58,8（））,用折半查找法查找關(guān)鍵字為55的記錄，比較

次數(shù)是（）。

答案：2次

問(wèn)題：4.如果按關(guān)鍵碼值遞增的順序依次將99個(gè)關(guān)鍵碼值插入到二叉排

序樹中，則對(duì)這樣的二叉排序樹檢索時(shí),在等概率情況下查找成功時(shí)的平均

查找長(zhǎng)度ASL為（）。??????

答案：5（）

問(wèn)題：5.對(duì)包含n個(gè)元素的散列表進(jìn)行查找，平均查找長(zhǎng)度為（）。

答案：不直接依賴于n

問(wèn)題：6.衡量查找算法效率的主要標(biāo)準(zhǔn)是（）。

答案：平均查找長(zhǎng)度

問(wèn)題：7.Hash表的平均查找長(zhǎng)度與處理沖突的方法無(wú)關(guān)。

答案：錯(cuò)誤

問(wèn)題：8.在二叉樹排序樹中插入一個(gè)新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面。

答案：正確

問(wèn)題：9.哈希表是一種將關(guān)鍵字轉(zhuǎn)換為存儲(chǔ)地址的存儲(chǔ)方法。

答案：正確

問(wèn)題：10.在二叉排序樹上刪除一個(gè)結(jié)點(diǎn)時(shí)，不必移動(dòng)其它結(jié)點(diǎn)，只要將該結(jié)

點(diǎn)的父結(jié)點(diǎn)的相應(yīng)的指針域置空即可。

答案：錯(cuò)誤

第76章

第77章

第78章

第79章

第80章

第81章

第82章

第83章

第84章

第85章

第86章

問(wèn)題：1.有一組數(shù)據(jù)(15,9,7,8,20,-1,7,4),用堆排序的篩選方法建立的初始

小根堆為()。

答案：-1,4,7,8,20,15,7,9

問(wèn)題：2.一組記錄的關(guān)鍵字為(46,79,56,38,4(),84),則利用快速排序的方法,

以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為()。

答案：(40,38,46,56,79,84)

問(wèn)題：3.對(duì)下列整數(shù)序列使用基數(shù)排序,一趟分配收集之后的結(jié)果是()。

(179,208,93,306,55,859,984,9,271,33)

答案：{271,93,33,984,55,306,208,179,859