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

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

1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中的操作對象以及它們之間的

（）和運算的學(xué)科。［單選題］*

A、結(jié)構(gòu)

B、關(guān)系（正確答案）

C、運算

D、算法

2.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。［單選題］*

A、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)

D、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

3.線性表的邏輯順序和存儲順序總是一致的，這種說法（）。［單選題］*

A、正確

B、不正確

C、無法確定

D、以上答案都不對

4.算法分析的目的是（）。［單選題］*

A、找出算法的合理性

B、研究算法的輸入與輸出關(guān)系

C、分析算法的有效性以求改進照答案）

D、分析算法的易懂性

5.數(shù)據(jù)結(jié)構(gòu)這門學(xué)科是針對什么問題而產(chǎn)生的？（）［單選題］*

A、針對非數(shù)值計算的程序設(shè)計問題

B、針對數(shù)值計算的程序設(shè)計問題

C、數(shù)值計算與非數(shù)值計算的問題都針對

D、兩者都不針對

6.數(shù)據(jù)結(jié)構(gòu)這門學(xué)科的研究內(nèi)容下面選項最準(zhǔn)確的是（）。［單選題］*

A、研究數(shù)據(jù)對象和數(shù)據(jù)之間的關(guān)系

B、研究數(shù)據(jù)對象

C、研究數(shù)據(jù)對象和數(shù)據(jù)的操作

D、研究數(shù)據(jù)對象、數(shù)據(jù)之間的關(guān)系和操作

7.某班級的學(xué)生成績表中查得張三同學(xué)的各科成績記錄，其中數(shù)據(jù)結(jié)構(gòu)考了90

分，那么下面關(guān)于數(shù)據(jù)對象、數(shù)據(jù)元素、數(shù)據(jù)項描述正確的是（）。［單選題］*

A、某班級的學(xué)生成績表是數(shù)據(jù)元素，90分是數(shù)據(jù)項

B、某班級的學(xué)生成績表是數(shù)據(jù)對象，90分是數(shù)據(jù)元素

C、某班級的學(xué)生成績表是數(shù)據(jù)對象，90分是數(shù)據(jù)項

D、某班級的學(xué)生成績表是數(shù)據(jù)元素，90分是數(shù)據(jù)元素

8.數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址不相同，稱之為（）。

［單選題］*

A、存儲結(jié)構(gòu)

B、邏輯結(jié)構(gòu)

C、鏈?zhǔn)酱鎯Y(jié)構(gòu)

D、順序存儲結(jié)構(gòu)

9.算法分析的主要方法（）。［單選題］*

A、空間復(fù)雜度和時間復(fù)雜度需答案）

B、正確性和簡明性

C、可讀性和文檔性

D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

1（）?計算機內(nèi)部處理的基本單元是（）。［單選題］*

A、數(shù)據(jù)

B、數(shù)據(jù)元素

C、數(shù)據(jù)項

D、數(shù)據(jù)庫

11.關(guān)于線性表的說法不正確的是?（）。［單選題］*

A、存在唯一的一個被稱為“第一個”的數(shù)據(jù)元素（開始結(jié)點）

B、存在唯一的一個被稱為“最后一個”的數(shù)據(jù)元素（終端結(jié)點）

C、除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)

D、除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個后繼

12.關(guān)于順序表的說法不正確的是?（）。［單選題］*

A、邏輯關(guān)系上相鄰的兩個元素在物理存儲位置上也相鄰

B、可以隨機存取表中任一元素，方便快捷

C、在線性表中插入某一元素時，往往需要移動大量元素

D、在線性表中刪除某一元素時，無需移動大量元素確答案?

13.當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作,但要求以最快的速度

存取線性表中的元素時，應(yīng)采用什么存儲結(jié)構(gòu)?（）。［單選題］*

A、順序表（正確答案）

B、單鏈表

C、循環(huán)鏈表

D、雙鏈表

14.在一個長度為n的順序表中第i個元素（l<=i<=n）之前插入一個元素吐需向后移

動多少個元素。（）。［單選題］*

A、n-1

B、n-i

C、n-i+1

D、n-i-1

15.在單鏈表中設(shè)置頭結(jié)點的作用是（）。［單選題］*

A、單鏈表定義而已

B、指定表的起始位置

C、為雙向鏈表做準(zhǔn)備

D、為循環(huán)鏈表做準(zhǔn)備

16.根據(jù)線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點包含的指針數(shù)，將線性鏈表分成（）。［單選

題］*

A、單鏈表與循環(huán)鏈表

B、單鏈表與十字鏈表

C、單鏈表與雙鏈表

D、循環(huán)鏈表與多鏈表

17.鏈接存儲的特點是利用什么來表示數(shù)據(jù)元素之間的邏輯關(guān)系（）。［單選題］*

A、引用二確答案）

B、串聯(lián)

C、掛接

D、指派

18.已知指針p指向單鏈表L中的某結(jié)點，則刪除其后繼結(jié)點的語句是（）。［單選題］

*

A、p=p.next

B、p=null

C、p.next=null

D、p.next=p.next.next（正確答案）

19.在單鏈表L中，指針p所指結(jié)點有后繼結(jié)點的條件是（）。［單選題］*

A、p=p.next

B、p.next!=null正確答案）

C、p.next=null

D、p.next=p.next.next

20.在單鏈表p結(jié)點之后插入s結(jié)點的操作是（）。［單選題］*

A、p.next=s;s.next=p.next;

B、s.next=p.next;p.next=p.next.next;

C、s.next=p.next;p.next=s;

D、s.next=p;p.next=s;

21.設(shè)abcdef以所給的次序進棧，若在進棧操作時,允許退棧操作，則下面得不到的序

列為（）。［單選題］*

A、fedcba

B、bcafed

C、dcefba

D、cabdef三確答案）

22.若已知一個棧的入棧序列是1,2,3,…,n,其輸出序列為pl,p2,p3,...,pN,若pN是n,

則pi是（）。［單選題］*

A、i

B、n-i

C、n-i+1

D、不確定

23.設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。

［單選題］*

A、線性表的順序存儲結(jié)構(gòu)

B、隊列

C、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

D、棧（正確答案）

24.用鏈接方式存儲的隊列，在進行刪除運算時（）。［單選題］*

A、僅修改頭指針

B、僅修改尾指針

C、頭、尾指針都要修改

D、頭、尾指針可能都要修改

25.遞歸過程或函數(shù)調(diào)用時,處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。［單

選題］*

A、隊列

B、多維數(shù)組

C、棧（正確答案）

D、線性表

26.假設(shè)以數(shù)組A［m］存放循環(huán)隊列的元素，其頭尾指針分別為front和rear,則當(dāng)前隊

列中的元素個數(shù)為()。［單選題］*

A、(rear-front+m)%m

B、rear-front+1

C、(front-rear+m)%m

D、(rear-front)%m

27.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列,且當(dāng)前rear和front的值分別為()和3,

當(dāng)從隊列中刪除一個元素,再加入兩個元素后,rear和front的值分別為多少?()［單選

題］*

A、1和5

B、2和4

C、4和2

D、5和1

28.最大容量為n的循環(huán)隊列，隊尾指針是rear,隊頭是front,則隊空的條件是()。［單

選題］*

A、(rear+l)MODn=front

B、rear=front

C、rear+l=front

D、(rear-1)MODn=front

29.棧和隊列的共同點是()。［單選題］*

A、都是先進先出

B、都是先進后出

C、只允許在端點處插入和刪除元素

D、沒有共同點

30.設(shè)棧S和隊列Q的初始狀態(tài)為空，元素el,e2,e3,e4,e5和e6依次通過棧S,一個元

素出棧后即進隊列Q,若6個元素出隊的序列是e2,e4,e3,e6,e5,el貝IJ棧S的容量至少

應(yīng)該是()。［單選題］*

A、6

B、4

C、3，

D、2

31.串是一種特殊的線性表，其特殊性體現(xiàn)在0。［單選題］*

A、可以順序存儲

B、可以用鏈表存儲

C、數(shù)據(jù)元素是一個字符

D、數(shù)據(jù)元素可以是多個字符

32.串是()。［單選題］*

A、少于一個字母的序列

B、任意個字母的序列

C、不少于一個字符的序列

D、有限個字符的序列

33.串的長度是()。［單選題］*

A、串中不同字母的個數(shù)

B、串中不同字符的個數(shù)

C、串中所含字符的個數(shù)，且大于0

D、串中所含字符的個數(shù)

34.設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算0.［單選題］

A、連接

B、模式匹配(正確答案)

C、求子串

D、求串長

35.存取數(shù)組中任一元素的時間都是相等的，這種存取方式為()存取方式。［單選題］*

A、順序

B、隨機(正確答案)

C、線性

D、非線性

36.設(shè)一個一維數(shù)組第一個元素的存儲單元的地址是100,每個元素的長度是6,則它

的第5個元素的地址是()。［單選題］*

A、130

B、105

C、106

D、124(正確答案)

37.設(shè)n階方陣是一個上三角矩陣，則需要存儲的元素個數(shù)是()。［單選題］*

A、n2/2

B、n(n+l)/2正確答案)

C、n

D、n2

38.對一些特殊矩陣采用壓縮存儲的目的主要是為()。［單選題］*

A、表達變得簡單

B、減少不必要的存儲空間的開銷

C、去掉矩陣中的多余元素

D、對矩陣元素的存取變得簡單

39.三元組表不包括()。［單選題］*

A、行數(shù)

B、列數(shù)

C、元素值

D、元素總數(shù)和答案)

40.設(shè)已知一個稀疏矩陣的三元組如下:(1,2,3),(1,6,1),(3,1,5),(3,2,-1),(4,5,4),(5,1,-3),則

其轉(zhuǎn)置矩陣的三元組表中第3個三元組為0。［單選題］*

A、(2,1,3)確答案)

B、(3,1,5)

C、(3,2,-1)

D、(2,3,-1)

41.樹最適合用來表示()。［單選題］*

A、有序數(shù)據(jù)元素

B、無序數(shù)據(jù)元素

C、元素之間具有分支層次關(guān)系的數(shù)據(jù)

D、元素之間無聯(lián)系的數(shù)據(jù)

42.二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以()。［單選題］*

A、它不能用順序存儲結(jié)構(gòu)存儲；

B、它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲；

C、順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲;

D、順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用

43.在下列情況中，可稱為二叉樹的是（）。［單選題］*

A、每個結(jié)點至多有兩棵子樹的樹

B、哈夫曼樹

C、每個結(jié)點有兩棵子樹的有序樹

D、每個結(jié)點只有一棵子樹

44.不含任何結(jié)點的空樹（）。［單選題］*

A、是一棵樹

B、是一棵二叉樹

C、是一棵樹也是一棵二叉樹

D、既不是樹也不是二叉樹

45.把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（）。［單選題］*

A、唯一的（正確答案）

B、有多種

C、有多種，但根結(jié)點都沒有左孩子

D、有多種，但根結(jié)點都沒有右孩子

46.二叉樹的深度為k,則二叉樹最多有（）個結(jié)點。［單選題］*

A、2k

B、2k-1

C、2k-1

D、2k-1

47.在一棵具有5層的滿二叉樹中結(jié)點總數(shù)為（）。［單選題］*

A、31工確答空）

B、32

C、33

D、16

48.將完全二叉樹中所有結(jié)點按層逐個從左到右的順序存放在一維數(shù)組中，

若結(jié)點R［i］有右孩子，則其右孩子是（）。［單選題］*

A、R⑵-1］

B、R［2i+1］

C、R［2il

D、R［2/i］

49.設(shè)a,b為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，a在b前面的條件是（）。

［單選題］*

A、a在b的右方

B、a在b的左方

C、a是b的祖先

D、a是b的子孫

50.若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，

利用（）遍歷方法最合適。［單選題］*

A、前序

B、中序

C、后序

D、按層次

學(xué)生答案:C

51.某二叉樹的中序序列為ABCDEFG,后序序歹IJ為BDCAFGE,則其左子樹中結(jié)

點數(shù)目為（）。［單選題］*

A、3

B、2

C、4

D、5

52.若以｛4,5,6,7,8｝作為權(quán)值構(gòu)造哈夫曼樹，則該樹的帶權(quán)路徑長度為（）。［單選

題］*

A、67

B、68

C、69

D、70

53.按照二叉樹的定義，具有3個結(jié)點的二叉樹有（）種。［單選題］*

A、3

B、4

C、5

D、6

54.將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次對

結(jié)點進行編號，根結(jié)點的編號為1,則編號為49的結(jié)點的左孩子編號為（）。

［單選題］*

A、98（正確答案）

B、99

C、50

D、48

55.對某二叉樹進行先序遍歷的結(jié)果為ABDEFC,中序遍歷的結(jié)果為DBFEAC,則

后序遍歷的結(jié)果是（）。［單選題］*

A、DBFEAC

B、DFEBCA（正確答案）

C、BDFECA

D、BDEFAC

56.設(shè)樹T的度為4,其中度為123,4的結(jié)點個數(shù)分別為4,2,1/，則T中的葉子數(shù)

為（）o［單選題］*

A、5

B、6

C、7

D、8

57.設(shè)森林F對應(yīng)的二叉樹為B,它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)

為n,森林F中第一棵樹的結(jié)點個數(shù)是（）。［單選題］*

A、m-n

B、m-n-1

C、n+1

D、條件不足，無法確定

58.一顆完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）。［單選題】*

A、250

B、500

C、499

D、以上答案都不對

59.一個具有1025個結(jié)點的二叉樹的高h(yuǎn)為（）。［單選題］*

A、11

B、10

C、11至1025之間（正確答案）

D、10至1024之間

60.在下列存儲形式中，哪一個不是樹的存儲形式（）？［單選題］*

A、雙親表示法

B、孩子鏈表表示法

C、孩子兄弟表示法

D、順序存儲表示法

61.在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。［單選題］*

A、1/2

B、1

C、2（正確答案）

D、4

62.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。［單選

題］*

A、1/2

B、1

C、2

D、4

63.一個有n個頂點的無向圖最多有（）條邊。［單選題］*

A、n

B、n（n-l）

C、n（n-l）/2（正確答案）

D、2n

64.有8個結(jié)點的無向連通圖最少有（）條邊。［單選題］*

A、5

B、6

C、7

D、8

65.對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是（）

［單選題］*

A、n

B、（n-l）A2

C、n-1

D、M2E確答案）

66.用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用（）來實現(xiàn)算法的。［單選題］

*

A、棧

B、隊列三確答案）

C、排序

D、查找

67.用鄰接表表示圖進行深度優(yōu)先遍歷時，通常是采用（）來實現(xiàn)算法的。［單選題］

*

A、棧E確答案）

B、隊列

C、排序

D、查找

68.如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，所生

成的圖一定是（）。［單選題］*

A、完全圖

B、連通圖

C、有回路

D、一棵樹（正確答案）

69.帶權(quán)有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中（）。［單選題］*

A、第i行非無窮的元素之和

B、第i列非無窮的元素個數(shù)之和

C、第i行非無窮且非0的元素個數(shù)

D、第i行與第i列非無窮且非0的元素之和

70.采用鄰接表存儲的圖，其深度優(yōu)先遍歷類似于二叉樹的（）o［單選題］*

A、中序遍歷

B、先序遍歷

C、后序遍歷

D、按層次遍歷

71.無向圖的鄰接矩陣是一個（）。［單選題］*

A、對稱矩陣（正確答案）

B、零矩陣

C、上三角矩陣

D、對角矩陣

72.鄰接表是圖的一種（）o［單選題］*

A、順序存儲結(jié)構(gòu)

B、鏈?zhǔn)酱鎯Y(jié)構(gòu)

C、索引存儲結(jié)構(gòu)

D、散列存儲結(jié)構(gòu)

73.在無向圖中定義頂點vi與vj之間的路徑為從vi到vj的一個()。［單選題］*

A、頂點序列(正確答案)

B、邊序列

C、權(quán)值總和

D、邊的條數(shù)

74.在有向圖的逆鄰接表中，每個頂點鄰接表鏈接著該頂點所有()鄰接點。［單

選題］*

A、入邊

B、出邊

C、入邊和出邊

D、不是出邊也不是入邊

75.設(shè)G1=(V1,E1)和G2=(V2,E2)為兩個圖，如果VI屬于V2,E1屬于E2則稱

()o［單選題］*

A、G1是G2的子圖確答案)

B、G2是G1的子圖

C、G1是G2的連通分量

D、G2是G1的連通分量

76.已知一個有向圖的鄰接矩陣表示，要刪除所有從第i個結(jié)點發(fā)出的邊，應(yīng)

()o［單選題］*

A、將鄰接矩陣的第i行刪除

B、將鄰接矩陣的第i行元素全部置為0

C、將鄰接矩陣的第i列