數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)

1、數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)1.一個(gè)棧的入棧序列a，b，c，d，e，則棧的不可能的輸出序列是（）。 單選題 *A. edcbaB. decbaC. dceab(正確答案)D. abcde2.若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1.m，topi代表第i 個(gè)棧( i =1,2)棧頂，棧1 的底在v1，棧2 的底在Vm，則棧滿(mǎn)的條件是（）。 單選題 *A. top2-top1|=0B. top1+1=top2(正確答案)C. top1+top2=mD. top1=top23.若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為（）。 單選題 *A. iB. n=

2、iC. n-i+1(正確答案)D. 不確定4.棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（）。 單選題 *A. 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(正確答案)B. 散列方式和索引方式C. 鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組D. 線(xiàn)性存儲(chǔ)結(jié)構(gòu)和非線(xiàn)性存儲(chǔ)結(jié)構(gòu)5.判定一個(gè)棧ST(最多元素為m0)為空的條件是（）。 單選題 *A. ST.top != -1B. ST.top = = -1(正確答案)C. ST.top != m0-1D. ST.top = = m0-16.判定一個(gè)棧ST(最多元素為m0)為棧滿(mǎn)的條件是（）。 單選題 *A. ST.top != -1B. ST.top = = -1C. ST.top != m0-1D.

3、ST.top = = m0-1(正確答案)7.棧的特點(diǎn)是（），隊(duì)列的特點(diǎn)是（）。 *A. 先進(jìn)先出(正確答案)B.先進(jìn)后出(正確答案)8.一個(gè)隊(duì)列的入列序列是1，2，3，4，則隊(duì)列的輸出序列是（）。 單選題 *A. 4，3，2，1B. 1，2，3，4(正確答案)C. 1，4，3，2D. 3，2，4，19.判定一個(gè)循環(huán)隊(duì)列QU(最多元素為m0)為空的條件是（）。 單選題 *A. front= =rear(正確答案)B. front！=rearC. front= =(rear+1)%m0D. front！=(rear+1)%m010.判定一個(gè)循環(huán)隊(duì)列QU(最多元素為m0)為滿(mǎn)隊(duì)列的條件是（）。 單

4、選題 *A. front= = rearB. front！= rearC. front= =(rear+1)%m0(正確答案)D. front！=(rear+1)%m011.循環(huán)隊(duì)列用數(shù)組A0，m-1存放其元素值，已知其頭尾指針?lè)謩e是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（）。 單選題 *A. (rear-front+m)%m(正確答案)B. rear-front+1C. rear-front-1D. rear-front12.棧和隊(duì)列的共同點(diǎn)是（）。 單選題 *A. 都是先進(jìn)后出B. 都是先進(jìn)先出C. 只允許在端點(diǎn)處插入和刪除元素D. 沒(méi)有共同點(diǎn)(正確答案)13.在一棵度為3的樹(shù)中，

5、度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（）個(gè)。 單選題 *A. 4B. 5C. 6(正確答案)D. 714.假設(shè)在一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為（）個(gè)。 單選題 *A. 15B. 16(正確答案)C. 17D. 4715.假定一棵三叉樹(shù)的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（）。 單選題 *A. 3B. 4C. 5(正確答案)D. 616.在一棵二叉樹(shù)上第4層的結(jié)點(diǎn)數(shù)最多為（）。 單選題 *A. 2B. 4C. 6D. 8(正確答案)17.用順序存儲(chǔ)的方法將完全二叉樹(shù)中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R1.n，結(jié)點(diǎn)Ri若

6、有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn)（）。 單選題 *A. R2i+1B. R2i(正確答案)C. Ri/2D. R2i-118.由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（）。 單選題 *A. 24B. 48C. 72D. 53(正確答案)19.線(xiàn)性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（）。 單選題 *A一對(duì)多關(guān)系B多對(duì)多關(guān)系C多對(duì)一關(guān)系D一對(duì)一關(guān)系(正確答案)20.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。 單選題 *A存儲(chǔ)B物理C邏輯(正確答案)D物理和存儲(chǔ)21.算法分析的目的是（）。 單選題 *A找出數(shù)據(jù)結(jié)構(gòu)的合理性B分析算法的效率以求改進(jìn)(正確答案)C研究

7、算法中的輸入和輸出的關(guān)系D分析算法的易懂性和文檔性22.算法分析的兩個(gè)主要方面是（）。 單選題 *A空間復(fù)雜性和時(shí)間復(fù)雜性(正確答案)B正確性和簡(jiǎn)明性C可讀性和文檔性D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性23.計(jì)算機(jī)算法指的是（）。 單選題 *A計(jì)算方法B排序方法C解決問(wèn)題的有限運(yùn)算序列(正確答案)D調(diào)度方法24.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）。 單選題 *A線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)(正確答案)B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)25.線(xiàn)性表是（）。 單選題 *A一個(gè)有限序列，可以為空(正確答案)B一個(gè)有限序列，不能為空C一個(gè)無(wú)限序列，可以為空D一個(gè)無(wú)限序列，不能為空26.帶頭結(jié)點(diǎn)的單

8、鏈表L為空的判定條件是（）。 單選題 *Ahead=nullBhead .next=null(正確答案)Chead .next=LDhead!=null27.在表長(zhǎng)為n的單鏈表中，算法時(shí)間復(fù)雜度為O(n)的操作為（）。 單選題 *A刪除p結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)B在p結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)C刪除表中第一個(gè)結(jié)點(diǎn)D查找單鏈表中第i個(gè)結(jié)點(diǎn)(正確答案)28.在表長(zhǎng)為n的順序表中，算法時(shí)間復(fù)雜度為O(1)的操作為（）。 單選題 *A在第i個(gè)元素前插入一個(gè)元素B刪除第i個(gè)元素C在表尾插入一個(gè)元素(正確答案)D查找其值與給定值相等的一個(gè)元素29.設(shè)單鏈表中指針p指向結(jié)點(diǎn)ai，若要?jiǎng)h除ai結(jié)點(diǎn)，則需修改指針的操作為（

9、）。 單選題 *Ap=p.nextBp.next=p.next.next(正確答案)Cp=p.next.nextDnext=p單選題1.數(shù)據(jù)的物理結(jié)構(gòu)包括_ 的表示和存儲(chǔ)和 _的表示和存儲(chǔ)。 填空題_(答案：順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu))2.對(duì)于給定的n個(gè)元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有（ ）,( )，( )，( )四種。 填空題_(答案：集合結(jié)構(gòu)、線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖狀結(jié)構(gòu))3.一個(gè)算法具有5個(gè)特性：( )、（ ）、（ ），有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。 填空題_(答案：有窮性、確定性、可行性)4.抽象數(shù)據(jù)類(lèi)型被形式地定義為（ ），其中D是（ ）的有限集合，S是D上的（ ）有限集合， P是對(duì)D的（

10、 ）集合。 填空題_(答案：D,S,P、數(shù)據(jù)元素、關(guān)系、基本操作)5.數(shù)據(jù)結(jié)構(gòu)主要包括數(shù)據(jù)的（ ）、數(shù)據(jù)的（ ）和數(shù)據(jù)的（ ）這三個(gè)方面的內(nèi)容。 填空題_(答案：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、操作)6.一個(gè)算法的效率可分為（ ）效率和（ ）效率。 填空題_(答案：時(shí)間、空間)7.線(xiàn)性表的兩種存儲(chǔ)結(jié)構(gòu)分別為（ ）和（ ）。 填空題_(答案：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))8.順序表中，邏輯上相鄰的元素，其物理位置（ ）相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置（ ）相鄰。 填空題_(答案：不一定、一定)9.若經(jīng)常需要對(duì)線(xiàn)性表進(jìn)行插入和刪除操作，則最好采用（ ）存儲(chǔ)結(jié)構(gòu)，若線(xiàn)性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行