數(shù)據(jù)結(jié)構(gòu) (1)試題及答案

1、數(shù)據(jù)結(jié)構(gòu)一、填空題1. 數(shù)據(jù)的物理結(jié)構(gòu)包括_的表示和存儲和_的表示和存儲。 填空題空1答案：順序空2答案：鏈?zhǔn)?. 對于給定的n個元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有_、_、_、_四種。 填空題空1答案：集合結(jié)構(gòu)空2答案：線性結(jié)構(gòu)空3答案：樹形結(jié)構(gòu)空4答案：圖狀結(jié)構(gòu)3. 一個算法具有5個特性：_、_、_，有零個或多個輸入、有一個或多個輸出。 填空題空1答案：有窮性空2答案：確定性空3答案：可行性4. 抽象數(shù)據(jù)類型被形式地定義為（D，S，P），其中D是_的有限集合，S是D上的_有限集合， P是對D的_集合。 填空題空1答案：數(shù)據(jù)元素空2答案：關(guān)系空3答案：基本操作5. 數(shù)據(jù)結(jié)構(gòu)主要包括數(shù)據(jù)的_、數(shù)據(jù)的_

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

3、以最快的速度存取線性表中的元素，則最好采用_存儲結(jié)構(gòu)。 填空題空1答案：鏈?zhǔn)娇?答案：順序11. 在帶頭結(jié)點(diǎn)的非空單鏈表中，頭結(jié)點(diǎn)的存儲位置由_指示，首元素結(jié)點(diǎn)的存儲位置由_指示，除首元素結(jié)點(diǎn)外，其它任一元素結(jié)點(diǎn)的存儲位置由_指示。 填空題空1答案：頭指針head空2答案：head.next空3答案：直接前驅(qū)12. 在具有n個單元的循環(huán)隊列中，隊滿時共有_個元素。 填空題空1答案：n-113. 具有10個頂點(diǎn)的無向圖，邊的總數(shù)最多為_。提示：n*(n-1)/2 填空題空1答案：45答案解析：n*n-1/214. G是一個非連通無向圖，共有28條邊，則該圖至少有_。 填空題空1答案：915. 在

4、有n個頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需要_條弧。 填空題空1答案：n16. 在有向圖的鄰接矩陣表示中，計算第I個頂點(diǎn)入度的方法是_。 填空題空1答案：第二列非零元素個數(shù)17. 已知一無向圖G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a開始遍歷圖，得到的序列為abecd，則采用的是_遍歷方法。 填空題空1答案：深度優(yōu)先18. 一個無向圖G（V，E），其中V=1,2,3,4,5,6,7，E=（1,2）,(1,3）,（2,4）,（2,5）,（3,6）,（3,7）,（6,7）,（5,1）,對該

5、圖從頂點(diǎn)3開始進(jìn)行遍歷，去掉遍歷中未走過的邊，得一生成樹G(V，E）,E（G）=（1,3）,（3,6）,（3,7）,（1,2）,（1,5）,（2,4），則采用的遍歷方法是_。 填空題空1答案：廣度優(yōu)先遍歷算法19. 求圖的最小生成樹有兩種算法，_算法適合于求稀疏圖的最小生成樹。 填空題空1答案：克魯斯卡爾20. 有一個用于n個頂點(diǎn)連通帶權(quán)無向圖的算法描述如下：（1）設(shè)集合T1與T2，初始均為空；（2）在連通圖上任選一點(diǎn)加入T1；（3）以下步驟重復(fù)n-1次：a.在i屬于T1，j不屬于T1的邊中選最小權(quán)的邊；b.該邊加入T2。上述算法完成后，T2中共有_條邊，該算法稱_算法，T2中的邊構(gòu)成圖的_。

6、 填空題空1答案：n-1空2答案：普里姆空3答案：最小生成樹21. 已知L見帶頭結(jié)點(diǎn)的單鏈表，且p結(jié)點(diǎn)既不是首元素結(jié)點(diǎn)，也不是尾元素結(jié)點(diǎn)。按要求從下列語句中選擇合適的語句序列。a.在p結(jié)點(diǎn)后插入s結(jié)點(diǎn)的語句序列是：_、_b.在p結(jié)點(diǎn)前插入s結(jié)點(diǎn)的語句序列是：_、_、_、_、_、_c.在表首插入s結(jié)點(diǎn)的序列語句是：_、_d.在表尾插入s結(jié)點(diǎn)的語句序列是：_、_、_供選擇的語句有：（1）p.next=s; （2）p.next=p.next.next;（3）p.next=s.next; （4）s.next=p.next;（5）s.next=L.next; （6）s.next=p;（7）s.next=

7、null; （8）q=p;（9）while(p.next!=q) p=p.next;（10）while(p.next!=null) p=p.next;（11）p=q; （12）p=L;（13）L.next=s; （14）L=p; 填空題空1答案：4空2答案：1空3答案：12空4答案：8空5答案：9空6答案：6空7答案：11空8答案：1空9答案：5空10答案：13空11答案：10空12答案：7空13答案：122. 已知一棵樹邊的集合為，請畫出這棵樹，并回答下列問題：（1）哪個是根結(jié)點(diǎn)？_（2）哪些是葉子結(jié)點(diǎn)？_、_、_、_、_、_、_（3）哪個是結(jié)點(diǎn)g的雙親？_（4）哪些是結(jié)點(diǎn)g的祖先？_、_（

8、5）哪些是結(jié)點(diǎn)g的孩子？_、_（6）哪些是結(jié)點(diǎn)e的孩子？_（7）哪些是結(jié)點(diǎn)e的兄弟？_哪些是結(jié)點(diǎn)f的兄弟？_、_（8）結(jié)點(diǎn)b和n的層次號分別是什么？_、_（9）樹的深度是多少？_（10）以結(jié)點(diǎn)c為根的子樹深度是多少？_ 填空題空1答案：a空2答案：d空3答案：m空4答案：n空5答案：f空6答案：j空7答案：k空8答案：l空9答案：c空10答案：a空11答案：c空12答案：j空13答案：k空14答案：i空15答案：d空16答案：g空17答案：h空18答案：2空19答案：5空20答案：5空21答案：3二、選擇題23. 線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（ ）。 單選題一對多關(guān)系多對多關(guān)系多對一關(guān)系一對

9、一關(guān)系(正確答案)24. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的（ ）結(jié)構(gòu)。 單選題存儲物理邏輯(正確答案)物理和存儲25. 算法分析的目的是（ ）。 單選題找出數(shù)據(jù)結(jié)構(gòu)的合理性分析算法的效率以求改進(jìn)(正確答案)研究算法中的輸入和輸出的關(guān)系分析算法的易懂性和文檔性26. 算法分析的兩個主要方面是（ ）。 單選題空間復(fù)雜性和時間復(fù)雜性(正確答案)正確性和簡明性可讀性和文檔性數(shù)據(jù)復(fù)雜性和程序復(fù)雜性27. 計算機(jī)算法指的是（ ）。 單選題計算方法排序方法解決問題的有限運(yùn)算序列(正確答案)調(diào)度方法28. 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）。 單選題線性結(jié)構(gòu)和非線性結(jié)構(gòu)(正確答案)緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

10、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)29. 線性表是（ ）。 單選題一個有限序列，可以為空(正確答案)一個有限序列，不能為空一個無限序列，可以為空一個無限序列，不能為空30. 帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件是（ ）。 單選題head=nullhead .next=null(正確答案)head .next=Lhead!=null31. 在表長為n的單鏈表中，算法時間復(fù)雜度為O(n)的操作為（ ）。 單選題刪除p結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)在p結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)刪除表中第一個結(jié)點(diǎn)查找單鏈表中第i個結(jié)點(diǎn)(正確答案)32. 在表長為n的順序表中，算法時間復(fù)雜度為O(1)的操作為（ ）。 單選題在第i個元素前

11、插入一個元素刪除第i個元素在表尾插入一個元素(正確答案)查找其值與給定值相等的一個元素33. 設(shè)單鏈表中指針p指向結(jié)點(diǎn)ai，若要刪除ai之后的結(jié)點(diǎn)，則需修改指針的操作為（ ）。 單選題p=p.nextp.next=p.next.next(正確答案)p=p.next.nextnext=p34. 一個棧的入棧序列a，b，c，d，e，則棧的不可能的輸出序列是（ ）。 單選題edcbadecbadceab(正確答案)abcde35. 若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1.m，topi代表第i 個棧( i =1,2)棧頂，棧1 的底在v1，棧2 的底在Vm，則棧滿的條件是（ ）。 單選題top2

12、-top1|=0top1+1=top2(正確答案)top1+top2=mtop1=top236. 若已知一個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為（ ）。 單選題in=in-i+1(正確答案)不確定37. 棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是（ ）。 單選題順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)(正確答案)散列方式和索引方式鏈表存儲結(jié)構(gòu)和數(shù)組線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)38. 判定一個棧ST（最多元素為m0）為空的條件是（ ）。 單選題ST.top != -1ST.top = = -1(正確答案)ST.top != m0-1ST.top = = m0-139. 判

13、定一個棧ST（最多元素為m0）為棧滿的條件是（ ）。 單選題ST.top != -1ST.top = = -1ST.top != m0-1ST.top = = m0-1(正確答案)40. 棧的特點(diǎn)是_，隊列的特點(diǎn)是_。（此處空位填寫A或B）A. 先進(jìn)先出 B.先進(jìn)后出 填空題空1答案：B空2答案：A41. 一個隊列的入列序列是1，2，3，4，則隊列的輸出序列是（ ）。 單選題4，3，2，11，2，3，4(正確答案)1，4，3，23，2，4，142. 判定一個循環(huán)隊列QU（最多元素為m0）為空的條件是（ ）。 單選題front= =rear(正確答案)front！=rearfront= =（re

14、ar+1）%m0front！=（rear+1）%m043. 判定一個循環(huán)隊列QU（最多元素為m0）為滿隊列的條件是（ ）。 單選題front= =rearfront！=rearfront= =（rear+1）%m0(正確答案)front！=（rear+1）%m044. 循環(huán)隊列用數(shù)組A0，m-1存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊列中的元素個數(shù)是（ ）。 單選題(rear-front+m)%m(正確答案)rear-front+1rear-front-1rear-front45. 棧和隊列的共同點(diǎn)是（ ）。 單選題都是先進(jìn)后出都是先進(jìn)先出只允許在端點(diǎn)處插入和刪除元素(正確答案)沒有共同點(diǎn)46. 在一棵度為3的樹中，度為3的結(jié)點(diǎn)數(shù)為2個，度為2的結(jié)點(diǎn)數(shù)為1個，度為1的結(jié)點(diǎn)數(shù)為2個，則度為0的結(jié)點(diǎn)數(shù)為（ ）個。 單選題456(正確答案)747. 假設(shè)在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個，則葉子結(jié)點(diǎn)數(shù)為（ ）個。 單選題1516(正確答案)174748. 假定一