數據結構課程學位考試試題(參考答案在題后)

判斷題：判斷下列各小題敘述的正誤。對，在題號后的括號內填入”；錯，在題號后填入“X”。

I、數據的最小單位是數據項。.....................(V)

2、多重表文件中主索引為非稠密索引，次索引為稠密索弓I。......(V)

3、通常數據結構在計算機中有四種不同的表示方法分為順序存儲結構、鏈式存儲結構、索引存儲、文件存

儲。......…….(X)

4、算法具有輸入、輸出、可行性、穩定性、有窮性五個特性。............(X)

5、數據的基本單位是數據項。.....................(X)

6、算法的復雜度分為時間復雜度和效率復雜度。.........(X)

7、性質相同的數據元素的集合成為數據對象。..........(J)

8、所有結點按1對1的鄰接關系構成的整體就是集合結構。......(X)

9、散列文件不能順序存取、只能按關鍵字隨機存取。...........(V)

10、數據的基本單位是數據元素。.....................(V)

11、B+樹中的K個孩子的結點必有K個關鍵字。........(V)

12、B+樹中的K個孩子的結點必有K個關鍵字。......…….(V)

13、倒排表的索引項中沒有頭指針和鏈表長度項。........(V)

14、磁帶是順序存取的外存儲設備。...............................(X)

15、索引文件只能是磁盤文件。........................(J)

16、順序文件只適宜于順序存取。............................(X)

17、磁帶是順序存取的外存儲設備。.....................…….(X)

18、線性的數據結構可以順序存儲，也可以鏈接存儲。...........(V)

19、倒排表的索引項中沒有頭指針和鏈表長度項。...............(V)

20、散列文件不能順序存取、只能按關鍵字隨機存取。….…….(V)

21、棧和隊列都是順序存取的的線性表，但它們對存取位置的限制不同。(J)

22、循環鏈表從任何一個結點出發，都能訪問到所有結點......(V)

23、單鏈表從任何一個結點出發，都能訪問到所有結點。…….(X)

24、線性表采用順序存儲表示時，必須占用一片連續的存儲單元。(J)

25、循環鏈表從任何一個結點出發，都能訪問到所有結點。…….(V)

26、設串S的長度為n,則S的子串個數為n(n+l)/2.....(X)

27、線性表采用鏈接存儲表示時，必須占用一片連續的存儲單元。.(X)

28、鏈接表上做刪除和插入運算時的平均時間復雜度都是0(n)….(X)

29、線性表中的每個結點最多只有一個前驅和一個后繼。............(V)

30、順序表上做刪除和插入運算時的平均時間復雜度都是0(n).(J)

31、具有n個結點的完全二叉樹的高度為1210g2"」+1..........(X)

32、在只有度為0和度為2的結點的二叉樹中，設度為0的結點有nO個，度為2的結點有n2個，則有

n0=n2+l..........(V)

33、循環隊列判斷隊列為滿的條件是sq->front+l==sq->rear。...(X)

34、數組是?種復雜的數據結構，數組元素之間的關系既不是線性的也不是樹形的。......(V)

35、若二叉樹中各結點的值均不相同，則由二叉樹的前序序列和中序序列，或由其后序序列和中序序列均

能惟一地確定一棵二叉樹。一一(V)

36、有n個結點的不同的二叉樹有n!棵。...........................(X)

37、一般樹和二叉樹的結點數目都可以為0。.................（V）

38、循環隊列判斷隊列為空的條件是sq->front==sq->rear。...（J）

39、設有一順序棧S,元素Si,S2,S3,Sa,S5,S6依次進棧,如果6個元素出線的順序是S2,S3,S“S6,S3,Si,則

棧的容量至少應該是3。.（J）

40、在只有度為0和度為k的結點的k叉樹中，設度為0的結點有n0個，

度為k的結點有nk個,則有nO=nk+l............（X）

41、一個連通圖的生成樹，是含該連通圖的全部頂點的一個極小連通子圖.（V）

42、在二叉樹的第i層上至多有2"個結點......（J）

43、先根遍歷樹和先根遍歷與該樹對應的二叉樹，其結果不一樣。.一（X）

44、由樹轉化成二叉樹，其根的右子女指針總是空的......（J）

45、網絡的最小代價生成樹是唯一的............................（X）

46、深度優先搜索遍歷類似于樹的先根遍歷，它所用到的數據結構是隊列。（X）

47、在一棵二叉樹中，假定卷個結點只有左子女，沒有右子女，對它分別進行中

序遍歷和后序遍歷，則具有相同的結果。......（J）

48、對于一棵具有n個結點，其高度為h的二叉樹，進行任一種次序遍歷的時間復雜度為O

（n）?..............（7）

49、圖的深度優先搜索類似于樹的先根次序遍歷........（V）

50、在無向圖中定義頂點V,與匕之間的路徑為從V］到達V」的一個頂點序列（J）

51、設無向連通圖的頂點個數為n,則該圖最多有n（n-l）/2條邊….（V）

52、圖的廣度優先遍歷是樹的按中根遍歷推廣。.....（X）

53、設圖G=（V,E）,V={1,2,3,4},E={〈1,2>,<1,3>,〈2,4〉，〈3,4>},從頂點1出

發，對圖G進行廣度優先搜索的序列有2種...（J）

54、用鄰接表作為有向圖G的存儲結構。設有n個頂點、e條弧，則拓撲排序的時間復雜度為

O（n*e）........（X）

55、查找表是由同一類型的數據元素（或記錄）構成的集合（J）

56、存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數有關，而且與圖的邊數也有

關..............................................（J）

57、圖的深度和廣度遍歷兩種操作的時間復雜度都為O（n*e）。......（X,）

58、只有無向圖，頂點數n、邊數e和度數之間有如下關系：e=.碰必）

59、裝教因子是散列表的一個重要參數，它反映了散列表的裝滿程度。（7）1

60、閉散列法通常比開散列法時間效率更高。（X）

61、進行折半搜索的表必須是順序存儲的有序表。（V）

62、索引順序查找的過程也是一個“縮小區間”的查找過程（J）

63、設有100個數據元素，采用折半搜索時，最大比較次數為7.（X）

64、在順序表中進行順序搜索時，若各元素的搜索概率不等，則各元素應按照搜索概率的降序排列存放，

則可得到最小的平均搜索長度。…….（X）

65、在二叉搜索樹中，若各結點的搜索概率不等，使得搜索概率越小的結點離樹

根越近，則得到的是最優二叉搜索樹。.....（J）

66、閉散列法通常比開散列法時間效率更高。（X）

67、折半搜索只適用與有序表，包括有序的順序表和有序的鏈表。（J）

68、起泡選擇排序是一種不穩定的排序方法。（X）

69、折半搜索只適用與有序表，包括有序的順序表和有序的鏈表。......（X）

70、除留余法選擇一個適當的正整數P,以p除健值以所得的余數作為散列地址。（V）

71、選擇排序是一種不穩定的排序方法。（J）

72、直接選擇排序是不穩定的，其時間復雜性為）0（1）。......（X）

73、快速排序是一種不穩定的排序方法。(J)

74、對于有n個對象的待排序序列進行歸并排序，所需平均時間為0(nlog2n)。(V)

75、直接選擇排序是一種不穩定的排序方法。......................(V)

76、直接插入排序是一種穩定的排序方法。(J)

77、歸并排序是一種不穩定的排序方法。(X)

78、選擇排序是一種不穩定的排序方法。(J)

79、歸并排序是一種不穩定的排序方法。(X)

80、堆排序是一種不穩定的排序方法。(J)

二、單選題：從選擇的答案中選出正確的答案，將其字母編號填入下列敘述中的括號內。

1、以下說法錯誤的是(B)

A.數據的物理結構是指數據在計算機內實際的存儲形式

B.算法和程序沒有區別，所以在數據結構中二者是通用的

C.對鏈表進行插人和刪除操作時.，不必移動結點

D.雙鏈表中至多只有一個結點的后繼指針為空

2、下列有關散列文件的說法中不正確的是(C)

A.散列文件具有隨機存放的優點B.散列文件只能按關鍵字存取

C.散列文件需要索引區D.散列文件的記錄不需要進行排序

3、有一個算法由3個部分的代碼嵌套連接組成，每部分的時間復雜度分別為0(1)、0(n2)、0(n3),

該算法的時間復雜度為(D)

A.0(1)+(n2)+(n3)B.0(n2)

C.(n3)D.(n5)

4、下列有關散列文件的說法中不正確的是(C)

A.散列文件具有隨機存放的優點B.散列文件只能按關鍵字存取

C.散列文件需要索引區D.散列文件的記錄不需要進行排序

5、設單鏈表中結點的結構為(data,next)0已知指針q所指結點是指針p所指結事業的直接前驅，若在

*q與*P之間插入結點*s,則應執行下列哪一個操作？(B)。

A.s->next=p->next;p->next=sB.q->next=s;s->next=p

C.p->next=s->next;s->next=pD.p->next=s;s->next=q

6、對順序表上的插入、刪除算法的時間復雜性分析來說，通常以(B)為標準操作

A.條件判斷B.結點移動

C.算術表達式D.賦值語句

7、在循環鏈表中，將頭指針改設為尾指針(rear)后，其頭結點和尾結點的存儲位置分別是(B)

A.real和rear->next->next

B.rear->next和real

C.rear->next->next和rear

D.rear和rear->next

8、有一個算法由3個部分的線性代碼連接組成，每部分的時間復雜度分別為0(1)、0(力)、0(n3),

該算法的時間復雜度為(C)

A.0(1)+(n2)+(n3)B.0(n2)

C.(n3)D.(n5)

9、以下說法錯誤的是(A)

A.對循環鏈表來說，從表中任一結點出發都能通過前后操作而掃描整個循環鏈表

B.對單鏈表來說，只有從頭結點開始才能掃描表中全部結點

C.雙鏈表的特點是找結點的前趨和后繼都很容易

D.對雙鏈表來說，結點*P的存儲位置既存放在其前趨結點的后繼指針域中，也存放在它的后繼結點的前趨

指針域中。

10、在串的基本運算中，屬于加工型運算的有(D)

A.EQAL(S,T)B.LENGTH(S)

C.CONCAT(S,T)D.REPLACE(S,T,R)

Ik線性鏈表不具有的特點是(A)。

A.隨機訪問B.不必事先估計所需存儲空間大小

C.插入與刪除時不必移動元素D.所需空間與線性表長度成正比

12、以下說法正確的是(C)

A.在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯系，因為可以從頭結點進行查找任何一個

元素

B.在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結構

C.順序存儲結構屬于靜態結構，鏈式結構屬于動態結構

D.順序存儲方式只能用于存儲線性結構

13、線性表是一個具有n個(C)的有限序列。

A.表元素B.字符C.數據元素D.數據項

14、對于順序表，以下說法錯誤的是(A)

A.順序表是用一維數組實現的線性表，數組的下標可以看成是元素的絕對地址

B.順序表的所有存儲結點按相應數據元素間的邏輯關系決定的次序依次排列

C.順序表的特點是:邏輯結構中相鄰的結點在存儲結構中仍相鄰

D.順序表的特點是:邏輯上相鄰的元素，存儲在物理位置也相鄰的單元中

15、一個長度為n的順序表的表尾插入一個新元素的漸進時間復雜度為(C)。

A.O(n)B.O(n/2)C.0(1)D.0(n2)

16、單鏈表的一個存儲結點包含(D)

A.數據域或指針域B.指針域或鏈域

C.指針域和鏈域D.數據域和鏈域

17、在串的基本運算中，屬于引用型運算的行(B)

A.ASSIGN(S,T)B.INSERT(SI,i,S2)

C.DELETE(S,i,j)D.SUBSTR(S,i,j)

18、一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為(A)。

A.0(n)B.0(n/2)C.0(1)D.0(n2)

19、向順序棧中壓入新元素時，應當(A)o

A.先移動棧頂指針，再存入元素

B.先存入元素，再移動棧頂指針

C.先后次序無關緊要

D.同時進行

20、順序隊列的人隊操作應為(A)

A.sq.rear=sq.rear+1;sq.data[sq.rear]=x

B.sq.data[sq.rear]=x;sq.rear=sq.rear+1

C.sq.rear=(sq.rear+1)%maxsize;sq.data[sq.rear]=x

D.sq.data[sqrear|=x;sq.rear=(sq.rear+1)%maxsize

21、頭結點的單鏈表first為空的判定條件是：(B)

A.first=NULL;B.first->next==NULL;

C.first->next==first;D.first!=NULL;

22、如果以鏈表作為棧的存儲結構，則入棧操作時(A)

A、必須判別棧是否滿B、必須判別棧元素的類型

C、必須判別棧是否空D、對棧不作任何判別

23、設有一個nxn的對稱矩陣A,將其下三角部分按行存放在一個一維數組B中，A[0][0]存放于B[0]中，

那么第i行的對角元素存放于8中（A）處。

A.（i+3）*i/2B.（i+l）*i/2

C.（2n-i+l）*i/2D.（2n-iT）*i/2

24、一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是（A）

A.dceabB.decba

C.edcbaD.abcde

25、假定一個鏈式隊列的隊頭和隊尾指針分別為front和rear,則判斷隊空的條件為（A）。

A.front==rearB.front!=NULL

C.rear!=NULLD.front=NULL

26、當利用大小為n的數組順序存儲一個隊列時，該隊列的最大長度為（B）。

A.n-2B.n-1C.nD.n+1

27、循環鏈表主要優點是（D）

A.不再需要頭指針了

B.已知某個結點的位置后，能夠容易找到它的直接前趨

C.在進行插入、刪除運算時:能更好地保證鏈表不斷開

D.從表中任一結點出發都能掃描到整個鏈表

28、稀疏矩陣一般采用（C）方法壓縮存儲。

A.三維數組B.單鏈表C.三元組表D.散列表

29、鏈式棧與順序棧相比，一個比較明顯的優點是（B）

A插入操作更加方便B通常不會出現棧滿的情況

C不會出現棧空的情況D刪除操作更加方便

30、設有一順序棧S,元素Si,S2,S3,S”S5,S6依次進棧，如果6個元素出線的順序是S2,S3,S“S6,S5,S1,則棧

的容量至少應該是（B）

A.2B.3C.5D.6

31、設有50行60列的二維數組A[50][60],其元素長度為4字節，按行優先順序存儲，基地址為200,則

元素A[18][25]的存儲地址為（A）。

A.3700B.4376

C.3900D.4620

32、設C語言數組DATA[m+l]作為循環隊列SQ的存儲空間，front為對頭指針rear為對尾指針，則執行出

隊操作的語句為（D）

A.front=front+lB.front=（front+1）%m

C.rear=（rear+l）%mD..front=（front+l）%（m+l）

33、循環隊列的隊滿條件為（C）

A.（sq.rear+1）%mazsize=（sq.front+1）%maxsize;

B.（sq.rear+1%maxsize==sq.front+1

C.sq.（rear+1）%maxsize=sq.front

D.sq.rear==sq.front

34、在一棵二叉樹的二叉鏈表中，空指針域數等于非空指針域數加（A）。

A.2B.1C.0D.-1

35、具有65個結點的完全二叉樹的高度為（B）。（根的層次號為0）

A.8B.7C.6D.5

36、對某二叉樹進行前序遍歷的結果為ABDEFC,中序遍歷的結果為DBFEAC,則后序遍歷的結果為（B）

A.DBFEACB.DFEBCA

C.BDFECAD.BDEFAC

37、循環隊列的出隊操作為（A）

A.sq.front=（sq.ftont+1）%maxsize

B.sq.front=sq.front+1

C.sq.rear=（sq.rear+）%maxsize

D.sq.rear=sq.rear+1

38、設F是個森林,B是由F轉換得到的二叉樹,F中有n個非葉結點，則B中右指針域為空的結點有（C）

個。

A.n-1B.nC.n+1D.n+2

39、設二叉樹結點的先根序列、中根序列和后根序列中，所有葉子結點的先后順序（B）

A.都不相同B.完全相同

C.先序和中序相同，而與后序不同D.中序和后序相同，而與先序不同

40、對于順序存儲的隊列,存儲空間大小為n,頭指針為F,尾指針為R。若在邏輯上看一個環，則隊列中

元素的個數為（B）

A.R-FB.(n+R-F)modn

C.（R-F+l）modnD.n+R-F

41、以下說法錯誤的是(A)

A.樹形結構的特點是一個結點可以有多個直接前趨

B.線性結構中的一個結點至多只有一個直接后繼

C.樹形結構可以表達（組織）更復雜的數據

D.樹（及一切樹形結構）是一種“分支層次”結構

42、以下說法錯誤的是（B）。

A.二叉樹可以是空集

B.二叉樹的任一結點都有兩棵子樹

C.二叉樹與樹具有相同的樹形結構

D.二叉樹中任一結點的兩棵子樹有次序之分

43、在一棵具有n個結點的二叉樹中，所有結點的空子樹個數等于（C）

A.nB.n-1C.n+1D.2*n

44、下列說法中正確的是（A

A.一棵二叉樹的度可以小于2B.二叉樹中任何一個結點的度都為2

C.二叉樹的度為2D.任何一棵二叉樹中至少有一個結點的度為2

45、在一棵具有5層的滿二叉樹中結點數為（A)

A31B32C33D16

46、一個二叉樹按順序方式存儲在一個維數組中,如圖

01234567891011121314

ABCDEFGHI,1

則結點E在二叉樹的第（C）層。

A.1B.2C.3D.4

47、在圖的鄰接表存儲結構上執行廣度優先搜索遍歷類似于二叉樹上的（D）

A.先根遍歷B.中根遍歷C.后根遍歷D.按層次遍歷

48、任何一棵二叉樹的葉結點在其先根、中根、后跟遍歷序列中的相對位置（C）

A.肯定發生變化B.有時發生變化

C.肯定不發生變化D.無法確定

49、在棵高度為h（假定樹根結點的層號為0）的完全二叉樹中，所含結點個數不小于（B）。

A.2hHB.2卜’C.2-1D.2b

50、樹若用雙親鏈表表示，則(A)

A.可容易地實現求雙親及子孫的運算

B.求雙親及子孫的運算均較困難

C.可容易地實現求雙親運算，但求子孫運算較困難

D.可容易地實現求子孫運算，但求雙親運算較困難

51、任何一個帶權的無向連通圖的最小生成樹(B)

A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在

52、設有向圖有n個頂點和e條邊，采用領接表作為其存儲表示，在進行拓撲排序時，總的計算時間為

(B

A.0(nlog2e)B.0(n+e)

C.0(ne)D.0(n2)

53、以下說法正確的是(A)

A.連通圖的生成樹，是該連通圖的一個極小連通子圖。

B.無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣一定是不對稱的。

C.任何一個有向圖，其全部頂點可以排成個拓撲序列。

D.有回路的圖不能進行拓撲排序。

54、以下說法錯誤的是(D)

A.一般在哈夫曼樹中，權值越大的葉子離根結點越近

B.哈夫曼樹中沒有度數為1的分支結點

C.若初始森林中共有n裸二叉樹，最終求得的哈夫曼樹共有2n-l個結點

D.若初始森林中共有n裸二叉樹，進行2n-l次合并后才能剩下一棵最終的哈夫曼樹

55、如果從無向圖的任一頂點出發進行一次深度優先搜索即可訪問所有頂點，則

該圖一定是(B)

A.完全圖B.連通圖C.有回路D.一棵樹

56、將一棵有50個結點的完全二叉樹按層編號，則對編號為25的結點x,該結點(B)

A.無左、右孩子B.有左孩子，無右孩子

C.有右孩子，無左孩子D.有左、右孩子

57、深度為6的二叉樹最多有(B)個結點

A.64B.63C.32D.31

58、一個有序順表有255個對象，采用順序搜索法查表，搜索長度為(A)。

A、128B、127C、126D、255

59、在有向圖中每個頂點的度等于該頂點的(C)。

A.入度B.出度

C.入度與出度之和D.入度與出度之差

60、具有n個頂點的有向無環圖最多可包含(D)條有向邊。

A.n-1B.nC.n(n-l)/2D.n(n-l)

61、用鄰接表作為有向圖G的存儲結構。設有n個頂點、e條弧，則拓撲排序的時間復雜度為(B)

A.O(n)B.O(n+e)C.0(e)D.O(n*e)

62、一個有序順表有255個對象，采用順序搜索法查表，搜索長度為(A)。

A、128B、127C、126D、255

63、在有向圖中，所有頂點的入度之和是所有頂點出度之和的(B)倍。

A.0.5B.1C.2D.4

64、以下說法錯誤的是(B)

A.用相鄰矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結點個數

有關，而與圖的邊數無關。

B.鄰接表法只能用于有向圖的存儲，而相鄰矩陣法對于有向圖利無向圖的存儲都適用。

C.存儲無向圖的相鄰矩陣是對稱的，因此只要存儲相鄰矩陣的下（或上）三角部分就可以了

D.用相鄰矩陣A表示圖，判定任意兩個結點Vi和Vj之間是否有長度為m的路徑相連，則只要檢查A

的第i行第j列的元素是否為0即可。

65、在圖的鄰接表存儲結構上執行深度優先搜索遍歷類似于二叉樹上的（A）

A.先根遍歷B.中根遍歷C.后根遍歷D按層次遍歷

66、在一個無向圖中，所有頂點的度數之和等于所有邊數的（B）倍。

A.3B.2C.1D.1/2

67、在無向圖中，所有頂點的度數之和是所有邊數的（C）倍。

A.0.5B.1C.2D.4

68、設有6個結點的無向圖,該圖至少應有（B）條邊能確保是一個連通圖。

A.5B.6C.7D.8

69、以下說法正確的是（D）

A.連通分量是無向圖中的極小連通子圖。

B.強連通分量是有向圖中的極大強連通子圖。

C.在一個有向圖的拓撲序列中，若頂點a在頂點b之前，則圖中必有一條弧〈a,b＞。

D.對有向圖G如果從任意頂點出發進行一次深度優先或廣度優先搜索能訪問到每個頂點，則該圖一定是

完全圖。

70、對有14個數據元素的有序表R[14]進行折半搜索，搜索到R[3]的關鍵碼等于給定值，此時元素比較順

序依次為（C

A.R[0],R[l],R[2],R[3]B.R[0],R[13],R[2],R[3]

C.R[6],R[2],R[4],R[3]D.R[6],R[4],R[2],R[3]

71、設有序表的關鍵字序列為｛1,4,6,10,18,35,42,53,67,71,78,84,92,99),當用二分查找

法查找健值為99的結點時，經（C)次比較后查找成功。

A.2B.3C.4C.12

72、設有100個數據元素，采用折半搜索時，最大比較次數為(B)

A6B7C8D10

73、對長度為n的有序單鏈表，若搜索每個元素的概率相等,則順序搜索到表中任一元素的平均搜索長度

為(B)

A.n/2B.(n+l)/2C.(n-1)/2D.n/4

74、對采用二分查找法進行查找運算的查找表，要求按（C）方式進行存儲。

A順序存儲B鏈式存儲

C順序存儲旦結點按關鍵字有序D鏈式存儲且結點按關鍵字有序

75、二分查找法適用于存儲結構為（A）的，且按關鍵字排序的線性表

A.順序存儲B.鏈接存儲C.順序存儲或鏈接存儲D.索引存儲

76、在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為（B）

A.O(n)B.O(n/2)C.0(1)D.O(n2)

77、在對查找表的查找過程中,若被查找的數據元素不存在，則把該數據元素插入到集合中。這種方式主

要適合于（C）

A.靜態查找表B.動態查找表

C.靜態查找表與動態查找表D.兩種表都不適合

78、在一個長度為n的順序表的表尾插入一個新元素的漸進時間復雜度為（B）

A.0(n)B.0(1)C.0(n2)D.0(log2n)

79、設有序表的關鍵字序列為｛1,4,6,10,18,35,42,53,67,71,78,84,92,99｝,當用二分查找

法查找健值為84的結點時?，經（C）次比較后查找成功。

A2B3C4D12

80、靜態查找表與動態查找表兩者的根本差別在于（C）

A邏輯結構不同B存儲實現不同

C施加的操作不同D數據元素的類型不同

81、以下時間復雜性不是0(r?)的排序方法是(B)

A.直接插入排序B.二路歸并排序C.冒泡排序1).直接選擇排序

82、一個對象序列的排序碼為{46,79,56,38,40,84},采用快速排序以位于最左位置的對象為基準而

得到的第一次劃分結果為(C)。

A.{38,46,79,56,40,84}B.{38,79,56,46,40,84)

C.{40,38,46,56,79,84}D.{38,46,56,79,40,84)

83、用順序查找法對具有n個結點的線性表查找的時間復雜性量級為(C)

2

A.O(n)B.O(nlog2n)C.O(n)DO(log2n)

84、用某種排序方法對序列(25,84,21,47,15,27,68,35,20)進行排序,記錄序列的變化情況如

下：

258421471527683520

152021254727683584

152021253527476884

152021252735476884

則采取的排序方法是(C)

A.直接選擇排序B.冒泡排序C.快速排序D.二路歸并排序

85、一個對象序列的排序碼為(46,79,56,38,40,84},采用快速排序以位于最左位置的對象為基準而

得到的第一次劃分結果為(C

A.{38,46,79,56,40,84}B.{38,79,56,46,40,84}

C.{40,38,46,56,79,84)1).{38,46,56,79,40,84}

86、順序查找法適合于(D)存儲結構的查找表。

A.壓縮B.散列C.索引D.順序或鏈式

87、以下說法錯誤的是(C)

A.直接插入排序的空間復雜度為0(1)。

B.快速排序附加存儲開銷為0(log2n)。

C.堆排序的空間復雜度為0(n)。

D.二路歸并排序的空間復雜度為O(n),需要附加兩倍的存儲開銷。

88、對于大文件的排序要研究在外設上的排序技術，即(C)

A.快速排序法B.內排序法C.外排序法D.交叉排序法

89、對■于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為(C)

的值除以9。

A.20B.18C.25D.22

90、具有24個記錄的序列，采用冒泡排序至少的比較次數是(B)

A.1B.23C.24D.529

91、當初始序列己按健值有序時，用直接插入算法進行排序，需要比較的次數為(A)

A.n-IB.log2nC.210g2nD.n2

92、排序的目的是為了以后對已排序的數據元數進行(D)操作。

A.打印輸出B.分類C.合并D.查找

93、以下穩定的排序方法是(B)

A.快速排序B.冒泡排序C.直接選擇排序D.堆排序

94、(B)方法是從未排序序列中依次取出元素與已排序序列中的元素作比較，將其放入已排序序列的正

確位置上。

A.歸并排序B.插入排序C.快速排序D.選擇排序

95、在文件局部有序或文件長度較小的情況下，最佳的排序方法是（A）

A.直接插入排序B.冒泡排序C.直接選擇排序D.歸并排序

96、如果只想得到1024個元素組成的序列中的前5個最小元素，那么用（C）方法最快。

A.起泡排序B.快速排序C.堆排序D.直接選擇排序

97、對--個由n個整數組成的序列，借助排序過程找出其中的最大值，希望比較次數和移動次數最少，應

選用（C）方法。

A.歸并排序B.直接插入排序

C.直接選擇排序D.快速排序

98、對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，

直到子序列為空或只剩一個元素為止。這樣的排序方法是（C）

A直接選擇排序B直接插入排序C快速排序D起泡排序

99、以下不穩定的排序方法是（C）

A.直接插入排序B.冒泡排序C.直接選擇排序D.二路歸并排

100、在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為（B）

A.O（n）B.O（n/2）C.0（1）D.O（n2）

三、填空題

1、有一個算法由3個部分的線性代碼連接組成，每部分的時間復雜度分別為0（n）、0（崔）、0（n4）,

該算法的時間復雜度為（0（襁））。

2、數據的基本單位是（數據元素）。

3、計算機中的算法指的是解決某一問題的有限運算序列，它必須具備輸入、輸出、可行性、（確定性）和（有

窮性）等5個特征

4、所有結點按1對1的鄰接關系構成的整體就是（線性）結構

5、數據元素之間的關聯方式或稱“鄰接關系”稱為（邏輯）關系。

6、有一個算法由3個部分的代碼嵌套連接組成，每部分的時間復雜度分別為0（n）、0（n2）、0（n4）,

該算法的時間復雜度為（0（n7））。

7、數據元素之間邏輯關系的整體稱為（邏輯結構）。

8、對一個算法要作出全面的分析可分成兩用人才個階段進行，即事先分析和（事后測試）。

9、算法的復雜度分為（時間復雜度）和（空間復雜度）兩種。

10、數據在計算機中的存儲表示（機內表示）稱為數據的（存儲結構）。

11、文件的檢索有順序存取、直接存取和（按關鍵字存取）三種方式。

12、文件的檢索有順序存取、直接存取和（按關鍵字存取）三種方式。

13、在順序表中插入或刪除一個元素，需要平均移動（（n+l）/2）元素，具體移動的元素個數與（）有

關。

14、VSAM文件結構由三部分組成：索引集、（順序集）和數據集。

15、ISAM文件是由多級主索引、柱面索引、磁道索弓I和（主文件索弓I）組成。

16、已知:sl="I'mateacher",s2="teacher",s3="student",則REPLACE（si,s2,s3）

等于（I'mateacher）?

17、如果文件中的每個記錄都有一個索引項，則這樣的索引稱為（稠密索引）。

18、如果文件中多個記錄只有一個索引項，則這樣的索引稱為（非稠密索引）。

19、在雙鏈表中，每個結點有兩個指針域，一個指向（前驅），另一個指向（后繼）。

20、當且僅當兩個串的（長度）相等并且各個對應位置上的字符都相同時，這兩個串相等。一個串中任意個

連續字符組成的序列稱為該串的（子串）串。

21、VSAM文件結構由三部分組成：索引集、（順序集）和數據集。

22、串的順序存儲有兩種方法：一種是每個單元只存一個字符，稱為（非緊縮格式）格式，另一種是每個單

元存放多個字符，稱為（緊縮格式）格式。

23、線性表的常見鏈式存儲結構有單鏈表、（雙向鏈表）和（循環鏈表）。

24、線性表典型的基本運算包括初始化、（插入）、（刪除）、查找定位、求長度、存取等六種。

25、已知：sl=〃I'mateacher",s2="teacher",s3="student",則SUBSTR（si,7,7）等于（student）（.

26、已知:mateacher",s2="teacher",s3="student",則DELETE（si,4,10）

等于（I,m）。

27、已知：mateacher",s2="teacher",s3="student",則EQUAL（sl,s2）等于（0）。

28、順序表中邏輯上相鄰的元素的物理位置（必須）緊鄰。單鏈表中邏輯上相鄰的元素的物理位置（不需要）

緊鄰。

29、四維數組是一種非線性結構，其中的每一個數組元素最多有（4）個直

接前驅（或直接后繼）

30、一般地，棧和線性表類似有兩種實現方法，即（順序）實現和（鏈接）實現。

31、含零個字符的串稱為（空串）串，用（中）表示。

32、棧是一種限定在表的一端進行插入和刪除的線性表，又被稱為（后進先出）線性表。

33、在棧的順序實現中，設棧頂指針為top,棧空的條件為（top=0）。

34、若已知一個棧的入棧序列是1,2,3,4,…，n,其輸出序列是Pl,P2,P3,Pn,若Pl=n,則

Pi為（n-i+1）.

35、對于順序存儲的棧，因為棧的空間是有限的，在進行（后進）運算時，可能發生棧的上溢，在進行（先出）

運算時，可能發生棧的下溢。

36、（棧）可以作為實現遞歸函數調用的一種數據結構。

37、對任何二叉樹，若度為2的節點數為n2,則葉子數n0=（n2+l）。

38、隊列中允許進行刪除的一端稱為（對頭）。

39、一般地，一個n維數組可視為其數據元素為（n）維數組的線性表?數組通常只有（刪除）和（插入）兩種

基本運算。

40、二叉樹有不同的鏈式存儲結構，其中最常用的是（二叉鏈表）與（三叉鏈表）。

41、以下運算實現在順序棧上的進棧，請在（）處用適當的語句予以填充。

IntPush（SqStackTp*sq,DataTypex）

{if（sp->top==sqstack_maxsizeT}{error（"棧滿"）;return（0）;}

else{（sq->top++）:

（sq->data[sq->top]）=x;

return（1）;}

）

42、深度為90的滿二叉樹上，第11層有（2與個結點。

43、已知一棵度為3的樹有2個度為1的結點，3個度過為2的結點，1個度為3的結點，則該樹中有（6）

個葉子結點。

44、深度優先搜索遍歷類似于樹的（先根）遍歷，它所用到的數據結構是（棧）。

45、具有n個結點的完全二叉樹的深度為（[log2n]+l）。

46、（樹）中結點的最大度數允許大于2,而（二叉樹）中結點的最大度數不允許大于2

47、一棵樹按照左子女-右兄弟表示法轉換成對應的二叉樹，則該二叉樹中樹根結點肯定沒有（右）子女。

48、深度為k（k>=l）的二叉樹至多有（2-1）個結點。

49、有m個葉子結點的哈夫曼樹，其結點總數為（2m-1）。

50、在一棵樹中，（根）結點沒有前驅結點。

51、對無向圖，其鄰接矩陣是一個關于（對角線）對稱的矩陣。

52、n（n>0）個頂點的有向連通圖最多有（n（n-l））條邊，最少有（n-1）條邊

53、設無向連通圖G的頂點數為n,則G最少有（n-1）條邊。

54、遍歷圖的基本方法有（深度）優先搜索和（廣度）優先搜索兩種。

55、在集合這種邏輯結構中，任何結點之間都不存在（邏輯）關系，這是集合這種邏輯結構的基本特點。

56、一個有向圖G中若有弧,<Vi,Vj>、<Vj,Vk>和<Vi,VQ,則在圖G的拓撲序列中，頂點Vi、Vj和Vk的相對

位置為（省略）。

57、廣度優先搜索遍歷類似于樹的（層次）遍歷，它所用到的數據結構是（隊列）。

58、由（樹）轉換成二叉樹時，其根結點的右子樹總是空的。

59、設圖G=（V,E）,V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4?,從頂點1出發，對圖G進行廣度優先搜

索的序列有種（2）。

60、任何連通圖的連通分量只有一個，即（本身）。

61、向一棵二叉搜索樹中插入一個元素時，若元素的值小于根結點的值，則應把它插入到根結點的（左子樹）

上。

62、對有序表（25,30,32,38,47,54,62,68,90,95）用二分查找法查找32,則所需的比較次數為（3）。

63、靜態查找表包括（建表）、（查找）、（讀元素）三種基本運算。

64、動態查找表包括建表、查找、讀元素、（插入）、（刪除）五種基本運算。

65、根據一組記錄（56,42,50,64,48）依次插入結點生成一棵AVL樹（高度平衡的二叉搜索樹）時，

當插入到值為（50）的結點時需要進行旋轉調整。

66、平衡二叉排序樹上任一結點的平衡因子只可能是（0）、（1）或（-1）。

67、在二叉排序樹上插入新結點時，不必移動其它結點，僅需使某結點的指針域由（空）變為（指向該結點）即

可。

68、在一棵AVL樹（高度平衡的二叉搜索樹）中，每個結點的左子樹高度與右子樹高度之差的絕對值不超

過（1）?

69、在具有24個元素的有序表上進行二分查找，則比較一次查找成功的結點數為（1）。

70、快速排序是不穩定的，其時間復雜性為（O（nlog2n））

71、直接選擇排序是不穩定的，其時間復雜性為（0（n2））。

72、按排序過程中依據的不同原則對內部排序方法進行分類，主要有：插入排序、（選擇排序）、（交換排序）、

歸并排序等四類

73、歸并排序的空間復雜度為（0（1））。

74、二叉排序樹是一種特殊的、增加了限制條件的二叉樹，其限制條件是任一結點的鍵值（大