2023年秋季國家開放大學(xué)-02272-數(shù)據(jù)結(jié)構(gòu)（本）期末考試題帶答案

單選題1、采用順序查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為（）。

正確選項(xiàng)1.(n+1)/2(V)

2、權(quán)值為{1，2，6，8}的四個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹的帶權(quán)路徑長度是（）。

正確選項(xiàng)1.29(V)

3、（）的一個(gè)重要應(yīng)用是解決主機(jī)和打印機(jī)之間速度不匹配的問題。

正確選項(xiàng)1.隊(duì)列(V)

4、（）的一個(gè)重要應(yīng)用是在程序設(shè)計(jì)中實(shí)現(xiàn)遞歸調(diào)用。

正確選項(xiàng)1.棧(V)

5、（）有兩個(gè)指針域，分別指向直接前驅(qū)和直接后繼，可以實(shí)現(xiàn)從前向后和從后向前查找。

正確選項(xiàng)1.雙向循環(huán)鏈表(V)

6、（）不屬于線性表的基本操作。

正確選項(xiàng)1.求子表(V)

7、8.對(duì)于一個(gè)鏈串s，查找第一個(gè)字符值為x的算法的時(shí)間復(fù)雜度為（）

正確選項(xiàng)1.O(n)(V)

8、表達(dá)式a*(b+c)-d的后綴表達(dá)式是（）。

正確選項(xiàng)1.abc+*d-(V)

9、采用折半查找方法查找長度為n的線性表時(shí)，其算法的時(shí)間復(fù)雜度為（）。

正確選項(xiàng)1.O(log2n)(V)

10、串的長度是指（）。

正確選項(xiàng)1.串中所含字符的個(gè)數(shù)(V)

11、串函數(shù)Strcat（a,b）的功能是進(jìn)行串（）。

正確選項(xiàng)1.連接(V)

12、串是（）。

正確選項(xiàng)1.有限個(gè)字符的序列(V)

13、串與普通的線性表相比較，它的特殊性體現(xiàn)在（）。

正確選項(xiàng)1.數(shù)據(jù)元素是一個(gè)字符(V)

14、從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（）。

正確選項(xiàng)1.插入排序(V)

15、帶頭結(jié)點(diǎn)的單向鏈表L為空的判定條件是（）。

正確選項(xiàng)1.L->next==NULL(V)

16、帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L為空表的條件是（）。

正確選項(xiàng)1.L->next==L(V)

17、當(dāng)利用大小為100的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，隊(duì)列的最大長度為（）。

正確選項(xiàng)1.99(V)

18、當(dāng)利用大小為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==-1表示?？?，則入棧應(yīng)該執(zhí)行（）語句修改top指針。

正確選項(xiàng)1.top++(V)

19、當(dāng)利用大小為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？?，則入棧應(yīng)該執(zhí)行（）語句修改top指針。

正確選項(xiàng)1.top--(V)

20、當(dāng)兩個(gè)元素出現(xiàn)逆序的時(shí)候就交換位置，這種排序方法稱為（）。

正確選項(xiàng)1.交換排序(V)

21、隊(duì)列是一種操作受限的線性表，其限制是（）。

正確選項(xiàng)1.僅允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除操作(V)

22、對(duì)二叉排序樹進(jìn)行（）遍歷，可以使遍歷所得到的序列是有序序列。

正確選項(xiàng)1.中序(V)

23、對(duì)具有n個(gè)元素的任意序列采用插入排序法進(jìn)行排序，排序趟數(shù)為（）。

正確選項(xiàng)1.n-1(V)

24、對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（）。

正確選項(xiàng)1.以順序存儲(chǔ)方式，且數(shù)據(jù)元素有序(V)

25、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為（）。

正確選項(xiàng)1.2e(V)

26、對(duì)于一個(gè)線性表，若要求既能進(jìn)行較快地插入和刪除，又要求存儲(chǔ)結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系，則應(yīng)該（）。

正確選項(xiàng)1.以鏈接存儲(chǔ)方式(V)

27、二叉樹的按層遍歷算法需要使用（）

正確選項(xiàng)1.隊(duì)列(V)

28、非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（）（設(shè)頭指針為head，指針p指向尾結(jié)點(diǎn)）。

正確選項(xiàng)1.p->next==head(V)

29、關(guān)于棧和隊(duì)列的說法中，錯(cuò)誤的是（）。

正確選項(xiàng)1.棧是先進(jìn)先出，隊(duì)列是后進(jìn)先出(V)

30、廣義表(f,h,(a,b,d,c),d,e,((i,j),k))的長度是()。

正確選項(xiàng)1.6(V)

31、廣義表（a，a，b，d，e，（（i，j），k））的表頭是（）。

正確選項(xiàng)1.a(V)

32、廣義表（a，d，e，（i，j），k）的表尾是（）。

正確選項(xiàng)1.（d，e，（i，j），k）(V)

33、假定一棵二叉樹中，葉子結(jié)點(diǎn)數(shù)為10，單分支結(jié)點(diǎn)數(shù)為30，則雙分支結(jié)點(diǎn)數(shù)為（）。

正確選項(xiàng)1.9(V)

34、假設(shè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針是F和R，那么隊(duì)空的條件是（）。

正確選項(xiàng)1.R=NULL(V)

35、就排序算法所用的輔助空間而言，堆排序、快速排序、歸并排序的關(guān)系是（）。

正確選項(xiàng)1.堆排序<

快速排序<

歸并排序(V)

36、空串與空格串（）。

正確選項(xiàng)1.不相同(V)

37、利用2、4、5、10這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（）。

正確選項(xiàng)1.38(V)

38、鏈表不具有的特點(diǎn)是（）。

正確選項(xiàng)1.可隨機(jī)訪問任一元素(V)

39、鏈表所具備的特點(diǎn)是（）。

正確選項(xiàng)1.插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn)(V)

40、鏈棧和順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)，即（）。

正確選項(xiàng)1.通常不會(huì)出現(xiàn)棧滿的情況(V)

41、兩個(gè)字符串相等的條件是（）。

正確選項(xiàng)1.兩串的長度相等，并且對(duì)應(yīng)位置上的字符相同(V)

42、兩個(gè)字符串相等的條件是（）。

正確選項(xiàng)1.兩個(gè)串的長度相等且對(duì)應(yīng)位置的字符相同(V)

43、鄰接表是圖的一種（）。

正確選項(xiàng)1.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(V)

44、每個(gè)存儲(chǔ)結(jié)點(diǎn)只存儲(chǔ)一個(gè)數(shù)據(jù)元素，各結(jié)點(diǎn)存儲(chǔ)在連續(xù)的存儲(chǔ)空間，該存儲(chǔ)方式是（）存儲(chǔ)方式。

正確選項(xiàng)1.順序(V)

45、某串的長度小于一個(gè)常數(shù)，則采用（）存儲(chǔ)方式最節(jié)省空間。

正確選項(xiàng)1.順序(V)

46、判斷向上增長型的順序?？盏臈l件是（）。

正確選項(xiàng)1.top=-1(V)

47、判斷一個(gè)順序隊(duì)列sq（最多元素為m）為空的條件是（）。

正確選項(xiàng)1.sq->front==sq->rear(V)

48、任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的（）。

正確選項(xiàng)1.相對(duì)次序不改變(V)

49、如果進(jìn)行串的比較，下列哪個(gè)串最大？（）

正確選項(xiàng)1.“BEIJING”(V)

50、如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)（）。

正確選項(xiàng)1.必須判斷棧是否空(V)

51、如圖所示二叉樹的中序遍歷序列是（）。

正確選項(xiàng)1.dgbaechf(V)

52、若Head為一個(gè)帶表頭結(jié)點(diǎn)的單鏈表的表頭指針，則該表為空表的條件是（）。

正確選項(xiàng)1.Head->next==NULL(V)

53、設(shè)a，b為一棵二叉樹的兩個(gè)結(jié)點(diǎn)，在后續(xù)遍歷中，a在b前的條件是（）。

正確選項(xiàng)1.a在b下方(V)

54、設(shè)頭指針為head的非空的單向鏈表，指針p指向尾結(jié)點(diǎn),則通過以下操作（)可使其成為單向循環(huán)鏈表。

正確選項(xiàng)1.p->next=head;(V)

55、設(shè)有兩個(gè)長度為n的單向鏈表，結(jié)點(diǎn)類型相同，分別是循環(huán)鏈表和非循環(huán)鏈表，則（）。

正確選項(xiàng)1.對(duì)于兩個(gè)鏈表來說，刪除最后一個(gè)結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是O(n)(V)

56、設(shè)有一個(gè)廣義表A(a)，其表尾為（）。

正確選項(xiàng)1.()(V)

57、設(shè)有一個(gè)長度為n的順序表，要?jiǎng)h除第i個(gè)元素,則需移動(dòng)元素的個(gè)數(shù)為（）。

正確選項(xiàng)1.n-i(V)

58、樹的（）沒有前驅(qū)結(jié)點(diǎn)，其他結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)。

正確選項(xiàng)1.根結(jié)點(diǎn)(V)

59、樹形結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系是（）

正確選項(xiàng)1.一對(duì)多(V)

60、樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（）。

正確選項(xiàng)1.-1(V)

61、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（）。

正確選項(xiàng)1.數(shù)據(jù)元素間的關(guān)系的表示(V)

62、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）。

正確選項(xiàng)1.邏輯結(jié)構(gòu)(V)

63、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）。

正確選項(xiàng)1.邏輯結(jié)構(gòu)(V)

64、順序隊(duì)列中，隊(duì)首元素位置為5，則隊(duì)首指針位置為（）。

正確選項(xiàng)1.4(V)

65、通常的使用順序?；蛘哝湕?shí)現(xiàn)遞歸算法，下面哪個(gè)說法正確（）。

正確選項(xiàng)1.順序棧和鏈棧性能基本相同(V)

66、圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。

正確選項(xiàng)1.先序(V)

67、無向圖的鄰接矩陣是一個(gè)（）。

正確選項(xiàng)1.對(duì)稱矩陣(V)

68、稀疏矩陣采用壓縮存儲(chǔ)的目的主要是（）。

正確選項(xiàng)1.減少不必要的存儲(chǔ)空間的開銷(V)

69、下列的敘述中，不屬于算法特性的是（）。

正確選項(xiàng)1.可讀性(V)

70、下列廣義表中的線性表是（）。

正確選項(xiàng)1.E(a,b)(V)

71、下列是”abcd321ABCD”的子串的選項(xiàng)是（）。

正確選項(xiàng)1.”21ABC”(V)

72、下列說法不正確的是（）。

正確選項(xiàng)1.串不是線性結(jié)構(gòu)(V)

73、下面程序段的時(shí)間復(fù)雜度是（）。for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}

正確選項(xiàng)1.O(n3)(V)

74、下面的操作不是?；具\(yùn)算的是（）。

正確選項(xiàng)1.排序操作(V)

75、下面的應(yīng)用中，不符合棧的后進(jìn)先出特點(diǎn)的是（）。

正確選項(xiàng)1.算數(shù)運(yùn)算、邏輯運(yùn)算和關(guān)系運(yùn)算(V)

76、下面關(guān)于串的敘述中，正確的是（）。

正確選項(xiàng)1.模式匹配是串的一種重要運(yùn)算(V)

77、下面關(guān)于棧的基本運(yùn)算算法中，復(fù)雜度最高的是（）。

正確選項(xiàng)1.鏈棧清空運(yùn)算(V)

78、線性結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系是（）

正確選項(xiàng)1.一對(duì)一(V)

79、向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（）。

正確選項(xiàng)1.先移動(dòng)棧頂指針，再存入元素(V)

80、向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素，并保持原來的順序不變，平均要移動(dòng)（）個(gè)元素。

正確選項(xiàng)1.63.5(V)

81、序列狀態(tài)為（）時(shí)，快速排序達(dá)到最好的時(shí)間復(fù)雜度。

正確選項(xiàng)1.序列無序(V)

82、一般情況下，將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)該設(shè)置（）。

正確選項(xiàng)1.棧(V)

83、一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖包含（）條邊。

正確選項(xiàng)1.n（n-1）(V)

84、一棵二叉樹采用鏈?zhǔn)酱鎯?chǔ)，n個(gè)結(jié)點(diǎn)的二叉樹共有（）個(gè)指針域?yàn)榭铡?/p>

正確選項(xiàng)1.n+1(V)

85、一組記錄的關(guān)鍵字序列為（80，57，41，39，46，47），利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（）。

正確選項(xiàng)1.39，46，41，57，80，47(V)

86、依次將每兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序方法稱為（）。

正確選項(xiàng)1.歸并排序(V)

87、已知10個(gè)數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，26，43），對(duì)該數(shù)列從小到大排序，經(jīng)過一趟冒泡排序后的序列為（）。

正確選項(xiàng)1.28，16，34，54，62，73，60，26，43，95(V)

88、已知某二叉樹的后續(xù)遍歷序列是dabec，中序遍歷是debac，則它的先序遍歷序列是（）。

正確選項(xiàng)1.cedba(V)

89、已知一個(gè)有序表為{11,22,33,44,55,66,77,88,99}，則順序查找元素55需要比較（）次。

正確選項(xiàng)1.5(V)

90、以下數(shù)據(jù)結(jié)構(gòu)中（）是線性結(jié)構(gòu)。

正確選項(xiàng)1.棧(V)

91、以下四個(gè)串中最小的是（）。

正確選項(xiàng)1.”ABADF”(V)

92、有關(guān)線性表的正確說法是（）。

正確選項(xiàng)1.除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼(V)

93、有一個(gè)長度為10的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。

正確選項(xiàng)1.29/10(V)

94、有一個(gè)長度為12的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。

正確選項(xiàng)1.37/12(V)

95、與順序表相比，鏈表的優(yōu)勢(shì)是（）。

正確選項(xiàng)1.插入數(shù)據(jù)元素較快(V)

96、在二叉樹的第4層最多含有（）個(gè)結(jié)點(diǎn)。

正確選項(xiàng)1.8(V)

97、在非空雙向循環(huán)鏈表的*p結(jié)點(diǎn)之前插入*q結(jié)點(diǎn)的操作是（）。

正確選項(xiàng)1.q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;(V)

98、在雙向循環(huán)雙鏈表中，刪除*p結(jié)點(diǎn)需要（）。

正確選項(xiàng)1.p->prior->next=p->next;p->next->prior=p->prior;(V)

99、在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊（）。

正確選項(xiàng)1.只有右子樹上的所有結(jié)點(diǎn)(V)

100、在一個(gè)帶頭結(jié)點(diǎn)的單向鏈表中，若要在指針q所指結(jié)點(diǎn)后插入p指針?biāo)附Y(jié)點(diǎn)，則執(zhí)行（）。

正確選項(xiàng)1.p->next=q->next;q->next=p;(V)

101、在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（）倍。

正確選項(xiàng)1.2(V)

102、在一個(gè)長度為n的順序表中為了刪除第5個(gè)元素，由第6個(gè)元素開始從后到前依次移動(dòng)了15個(gè)元素。則原順序表的長度為（）。

正確選項(xiàng)1.20(V)

103、在一棵度具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（）。

正確選項(xiàng)1.31(V)

104、在有向圖的鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（）鄰接點(diǎn)。

正確選項(xiàng)1.出邊(V)

105、在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86時(shí)，經(jīng)（）次比較后查找成功。

正確選項(xiàng)1.4(V)

106、在長度為n（n>1）的（）上，刪除第一個(gè)元素，其算法的時(shí)間復(fù)雜度為O(n)。

正確選項(xiàng)1.只有首結(jié)點(diǎn)指針h的不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表(V)

107、棧的操作特性決定了它是一種（）的線性表。

正確選項(xiàng)1.先進(jìn)后出(V)

108、棧的基本運(yùn)算包括（）

正確選項(xiàng)1.取棧頂元素(V)判斷題1、哈夫曼樹一定是完全二叉樹或滿二叉樹。

正確選項(xiàng)1.×(V)

2、AOV網(wǎng)是一個(gè)帶權(quán)的有向圖。

正確選項(xiàng)1.×(V)

3、按照一定規(guī)則，在二叉排序樹上插入、刪除結(jié)點(diǎn)，仍能保持二叉排序樹的性質(zhì)。

正確選項(xiàng)1.√(V)

4、采用分塊查找時(shí)，數(shù)據(jù)的組織方式是把數(shù)據(jù)分成若干塊，塊內(nèi)數(shù)據(jù)不必有序，但塊間必需有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引表。

正確選項(xiàng)1.√(V)

5、采用分塊查找時(shí)，數(shù)據(jù)的組織方式為把數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最小）的數(shù)據(jù)組成索引表。

正確選項(xiàng)1.×(V)

6、采用順序查找法對(duì)長度為n（n為偶數(shù)）的線性表進(jìn)行查找，采用從前向后的方向查找。在等概率條件下成功查找到前n/2個(gè)元素的平均查找長度為(n+2)/4。

正確選項(xiàng)1.√(V)

7、采用順序查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為n/2。

正確選項(xiàng)1.×(V)

8、串的兩種最基本的存儲(chǔ)方式是順序和鏈接。

正確選項(xiàng)1.√(V)

9、串中的元素只可能是字母。

正確選項(xiàng)1.×(V)

10、串中字符的個(gè)數(shù)稱為串的長度。

正確選項(xiàng)1.√(V)

11、存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。

正確選項(xiàng)1.×(V)

12、待排序的序列為8,3,4,1,2,5,9，采用直接選擇排序算法，當(dāng)進(jìn)行了兩趟選擇后，結(jié)果序列為1,2,8,3,4,5,9。

正確選項(xiàng)1.×(V)

13、遞歸的算法簡(jiǎn)單、易懂、容易編寫，而且執(zhí)行效率也高。

正確選項(xiàng)1.×(V)

14、遞歸算法可讀性差，但是效率高

正確選項(xiàng)1.×(V)

15、遞歸算法執(zhí)行時(shí)，每次遞歸可將原問題的規(guī)模縮小。

正確選項(xiàng)1.√(V)

16、隊(duì)列的特性是先進(jìn)后出。

正確選項(xiàng)1.×(V)

17、對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。

正確選項(xiàng)1.√(V)

18、對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的行號(hào)、列號(hào)和元素值三項(xiàng)信息。

正確選項(xiàng)1.√(V)

19、對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在*p結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是O(n)。

正確選項(xiàng)1.×(V)

20、對(duì)于一個(gè)無向圖，每個(gè)頂點(diǎn)的入度等于出度。

正確選項(xiàng)1.√(V)

21、對(duì)于一棵深度為4的滿三叉樹，其結(jié)點(diǎn)數(shù)為40。

正確選項(xiàng)1.√(V)

22、對(duì)于一棵深度為h，度為3的樹最多有（3h-1）/2個(gè)結(jié)點(diǎn)。

正確選項(xiàng)1.×(V)

23、二叉排序樹中某一結(jié)點(diǎn)的左兒子一定小于樹中任一個(gè)結(jié)點(diǎn)的右兒子。

正確選項(xiàng)1.×(V)

24、二叉樹的遍歷就是按照一定次序訪問樹中所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)的值僅被訪問一次的過程。

正確選項(xiàng)1.√(V)

25、二叉樹的根結(jié)點(diǎn)值大于其左子樹結(jié)點(diǎn)的值，小于右子樹結(jié)點(diǎn)的值，則它是一棵二叉排序樹。

正確選項(xiàng)1.×(V)

26、二叉樹中任一結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值，則它是一棵二叉排序樹。

正確選項(xiàng)1.×(V)

27、二分查找是一種最簡(jiǎn)單的查找方法。

正確選項(xiàng)1.×(V)

28、分塊查找分為兩個(gè)步驟：第一步是要對(duì)索引表進(jìn)行查找；第二步是在塊中查找。這兩步查找都可以采用折半查找或者順序查找方法。

正確選項(xiàng)1.×(V)

29、父親李貴有兩個(gè)兒子李萬勝和李萬利，李萬勝又有三個(gè)兒子李建新、李建中和李建國，這個(gè)家庭可以用樹結(jié)構(gòu)來描述。

正確選項(xiàng)1.√(V)

30、各種鏈表只需定義有兩個(gè)域的結(jié)點(diǎn)。

正確選項(xiàng)1.×(V)

31、根據(jù)圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行某種次序的遍歷，得到的頂點(diǎn)序列是唯一的。

正確選項(xiàng)1.×(V)

32、哈夫曼樹葉結(jié)點(diǎn)數(shù)比非葉結(jié)點(diǎn)數(shù)多1。

正確選項(xiàng)1.√(V)

33、哈夫曼樹只存在著雙支結(jié)點(diǎn)，不存在單支結(jié)點(diǎn)。

正確選項(xiàng)1.√(V)

34、計(jì)算機(jī)所處理的數(shù)據(jù)一般具有某種關(guān)系,這是指數(shù)據(jù)元素與數(shù)據(jù)元素之間存在的某種關(guān)系。

正確選項(xiàng)1.√(V)

35、健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。

正確選項(xiàng)1.√(V)

36、具有10個(gè)結(jié)點(diǎn)的完全二叉樹有5個(gè)葉子。

正確選項(xiàng)1.√(V)

37、具有12個(gè)結(jié)點(diǎn)的完全二叉樹的深度為4。

正確選項(xiàng)1.√(V)

38、具有n個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲(chǔ)，共有n-1個(gè)空鏈域。

正確選項(xiàng)1.×(V)

39、鏈接存儲(chǔ)表示中數(shù)據(jù)元素之間的邏輯關(guān)系是由指針表示的。

正確選項(xiàng)1.√(V)

40、鏈棧通常不會(huì)出現(xiàn)棧滿的狀態(tài)

正確選項(xiàng)1.√(V)

41、兩個(gè)字符串比較時(shí)，較長的串比較短的串大

正確選項(xiàng)1.×(V)

42、鄰接表只能用于存儲(chǔ)有向圖，而鄰接矩陣則可存儲(chǔ)有向圖和無向圖。

正確選項(xiàng)1.×(V)

43、滿二叉樹中沒有度為1的結(jié)點(diǎn)。

正確選項(xiàng)1.√(V)

44、冒泡排序是一種比較簡(jiǎn)單的插入排序方法。

正確選項(xiàng)1.×(V)

45、冒泡排序是一種比較簡(jiǎn)單的交換排序方法。

正確選項(xiàng)1.√(V)

46、如果結(jié)點(diǎn)A有3個(gè)兄弟3個(gè)孩子，而且B是A的雙親，則A的度是3。

正確選項(xiàng)1.×(V)

47、如果一個(gè)葉子結(jié)點(diǎn)是某二叉樹中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，那么它也是該二叉樹的先序遍歷序列的最后一個(gè)結(jié)點(diǎn)。

正確選項(xiàng)1.√(V)

48、若讓元素1,2,3依次進(jìn)棧，則出棧次序1,3,2是不可能出現(xiàn)的情況。

正確選項(xiàng)1.×(V)

49、若讓元素a,b,c依次進(jìn)棧，則出棧次序c,a,b是不可能出現(xiàn)的情況。

正確選項(xiàng)1.√(V)

50、若樹中各結(jié)點(diǎn)的子樹是按照一定的次序從左向右安排的，則稱之為有序樹。

正確選項(xiàng)1.√(V)

51、若一個(gè)強(qiáng)連通圖有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少含有n條有向邊。

正確選項(xiàng)1.√(V)

52、散列技術(shù)中的沖突指的是兩個(gè)元素具有相同的序號(hào)。

正確選項(xiàng)1.×(V)

53、森林是m（m≥0）棵互不相交的樹的集合。

正確選項(xiàng)1.√(V)

54、刪除順序表的最后一個(gè)元素，需要移動(dòng)的元素最多。

正確選項(xiàng)1.×(V)

55、設(shè)廣義表L=（（），（）），則其表頭是（（））。

正確選項(xiàng)1.×(V)

56、設(shè)廣義表L=（（），（）），則其表尾是（）。

正確選項(xiàng)1.×(V)

57、設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為BCDA。

正確選項(xiàng)1.×(V)

58、設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有6條邊才能確保是一個(gè)連通圖。

正確選項(xiàng)1.×(V)

59、設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，指針p指向尾結(jié)點(diǎn)，現(xiàn)要使p指向第一個(gè)結(jié)點(diǎn)，可用語句p=p->next;。

正確選項(xiàng)1.√(V)

60、設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p->next=head。

正確選項(xiàng)1.√(V)

61、設(shè)有一個(gè)單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，指針p指向表中某結(jié)點(diǎn)，若邏輯表達(dá)式p->next==head;的結(jié)果為真，則p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。

正確選項(xiàng)1.√(V)

62、設(shè)有一個(gè)長度為40的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為33。

正確選項(xiàng)1.×(V)

63、深度為k的完全二叉樹至少有2k-1個(gè)結(jié)點(diǎn)。

正確選項(xiàng)1.×(V)

64、使用鄰接矩陣存儲(chǔ)圖的時(shí)候，占用空間大小與圖的結(jié)點(diǎn)個(gè)數(shù)沒有關(guān)系。

正確選項(xiàng)1.×(V)

65、使用三元組表示稀疏矩陣中的非零元素能節(jié)省存儲(chǔ)空間。

正確選項(xiàng)1.√(V)

66、樹的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)。

正確選項(xiàng)1.×(V)

67、樹是一種線性結(jié)構(gòu)。

正確選項(xiàng)1.×(V)

68、樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)。

正確選項(xiàng)1.√(V)

69、樹型結(jié)構(gòu)的元素間存在多對(duì)多的關(guān)系。

正確選項(xiàng)1.×(V)

70、樹最適合表示元素之間具有層次關(guān)系的數(shù)據(jù)。

正確選項(xiàng)1.√(V)

71、數(shù)據(jù)的邏輯結(jié)構(gòu)是與存儲(chǔ)該結(jié)構(gòu)的計(jì)算機(jī)相關(guān)的。

正確選項(xiàng)1.×(V)

72、數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的。

正確選項(xiàng)1.√(V)

73、數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。

正確選項(xiàng)1.√(V)

74、數(shù)據(jù)結(jié)構(gòu)中,元素之間存在多對(duì)多的關(guān)系稱為樹狀結(jié)構(gòu)。

正確選項(xiàng)1.×(V)

75、數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。

正確選項(xiàng)1.√(V)

76、數(shù)組通常具有的操作是順序存取。

正確選項(xiàng)1.×(V)

77、順序查找是一種最簡(jiǎn)單的查找方法。

正確選項(xiàng)1.√(V)

78、順序隊(duì)列的入隊(duì)算法是先檢查隊(duì)列是否為滿，若不滿則將新元素值賦給隊(duì)頭指針?biāo)赶虻臄?shù)據(jù)單元，再將隊(duì)頭指針加1。

正確選項(xiàng)1.×(V)

79、圖的廣度優(yōu)先搜索序列是惟一的。

正確選項(xiàng)1.×(V)

80、圖的連通分量是無向圖的極大連通子圖。

正確選項(xiàng)1.√(V)

81、圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是惟一的。

正確選項(xiàng)1.√(V)

82、圖的最小生成樹只有一棵。

正確選項(xiàng)1.×(V)

83、完全二叉樹中沒有度為1的結(jié)點(diǎn)。

正確選項(xiàng)1.×(V)

84、線性表的順序存儲(chǔ)是利用數(shù)組來實(shí)現(xiàn)的。

正確選項(xiàng)1.√(V)

85、線性表是一個(gè)有限序列，不可以為空。

正確選項(xiàng)1.×(V)

86、線性表用順序方式存儲(chǔ)可以隨機(jī)訪問。

正確選項(xiàng)1.√(V)

87、向一個(gè)長度為n的順序表中的第i個(gè)元素（1≤i≤n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)n-i個(gè)元素。

正確選項(xiàng)1.×(V)

88、序列15,13,16,14,19,17，采用冒泡排序算法(升序)，經(jīng)一趟冒泡后，結(jié)果序列是13,15,14,16,17,19。

正確選項(xiàng)1.√(V)

89、序列3,1,7,18,6,9,13,12經(jīng)一趟歸并排序的結(jié)果為1,3,7,18,6,9,13,12。

正確選項(xiàng)1.×(V)

90、循環(huán)隊(duì)列隊(duì)頭指針在隊(duì)尾指針后一個(gè)位置，隊(duì)列是“滿”狀態(tài)。

正確選項(xiàng)1.√(V)

91、循環(huán)隊(duì)列是將隊(duì)列想象成一個(gè)首尾相接的圓環(huán)。

正確選項(xiàng)1.√(V)

92、要在一個(gè)單向鏈表中刪除p所指向的結(jié)點(diǎn)，已知q指向p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，則可執(zhí)行q->next=p->next。

正確選項(xiàng)1.√(V)

93、一個(gè)廣義表的表頭總是一個(gè)廣義表。

正確選項(xiàng)1.×(V)

94、一個(gè)空格的串的長度是0。

正確選項(xiàng)1.×(V)

95、一個(gè)有向圖的鄰接表和逆鄰接表中的節(jié)點(diǎn)個(gè)數(shù)一定相等。

正確選項(xiàng)1.√(V)

96、一棵二叉樹每一層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹是完全二叉樹。

正確選項(xiàng)1.×(V)

97、已知一棵樹的先序序列和后序序列，一定能構(gòu)造出該樹。

正確選項(xiàng)1.×(V)

98、用鄰接矩陣存儲(chǔ)圖的時(shí)候，占用空間大小不但與圖的結(jié)點(diǎn)個(gè)數(shù)有關(guān)還與圖的邊數(shù)有關(guān)。

正確選項(xiàng)1.×(V)

99、用數(shù)組實(shí)現(xiàn)順序棧，棧底可以是數(shù)組空間的任何一端

正確選項(xiàng)1.√(V)

100、用字符數(shù)組存儲(chǔ)長度為n的字符串，數(shù)組長度至少為n+1。

正確選項(xiàng)1.√(V)

101、由一個(gè)具有n個(gè)頂點(diǎn)的連通圖生成的最小生成樹中，具有n-1條邊。

正確選項(xiàng)1.√(V)

102、在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。

正確選項(xiàng)1.√(V)

103、在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，尾指針后移，當(dāng)刪除一個(gè)元素隊(duì)列時(shí)，頭指針后移。

正確選項(xiàng)1.√(V)

104、在對(duì)10個(gè)記錄的序列(14,30,10,7,22,13,66,85,47,58)進(jìn)行直接插入排序時(shí)，當(dāng)把第6個(gè)記錄13插入到有序表時(shí)，為尋找插入位置，需比較3次。

正確選項(xiàng)1.×(V)

105、在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是哈希表查找。

正確選項(xiàng)1.√(V)

106、在歸并排序中，在第3趟歸并中，是把長度為4的有序表歸并為長度為8的有序表。

正確選項(xiàng)1.√(V)

107、在雙向循環(huán)鏈表上，刪除最后一個(gè)結(jié)點(diǎn)，其算法的時(shí)間復(fù)雜度為0(1)。

正確選項(xiàng)1.√(V)

108、在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過物理存儲(chǔ)位置決定的；在線性表的鏈?zhǔn)酱鎯?chǔ)中，元素之間的邏輯關(guān)系是通過鏈域的指針值決定的。

正確選項(xiàng)1.√(V)

109、在一個(gè)查找表中，能夠唯一地確定一個(gè)記錄的關(guān)鍵字稱為主關(guān)鍵字。

正確選項(xiàng)1.√(V)

110、在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中,隊(duì)頭指針指向隊(duì)頭元素的后一個(gè)位置。

正確選項(xiàng)1.×(V)

111、在有序表A[1…18]中，采用二分查找算法查找元素值等于A[17]的元素，所比較過的元素的下標(biāo)依次是9、14、16、17。

正確選項(xiàng)1.√(V)

112、在有序順序存儲(chǔ)的線性表中查找一個(gè)元素，用折半查找速度一定比順序查找快。

正確選項(xiàng)1.×(V)

113、在長度為n的順序表L中查找指定元素值的元素，其時(shí)間復(fù)雜度為O(n)。

正確選項(xiàng)1.√(V)

114、棧是限定在表的兩端進(jìn)行插入和刪除操作的線性表，又稱為先進(jìn)先出表。

正確選項(xiàng)1.×(V)

115、長度為0的線性表稱為空表。

正確選項(xiàng)1.√(V)

116、折半查找方法運(yùn)用在升序序列比降序序列效率更高，所以降序序列最好先轉(zhuǎn)換為升序序列。

正確選項(xiàng)1.×(V)

117、字符串a(chǎn)1=〝heijing〞,a2=〝hen〞,a3=〝heifang〞,a4=“heni〞，其中最小的是a2。

正確選項(xiàng)1.×(V)

118、字符串屬于線性的數(shù)據(jù)結(jié)構(gòu)

正確選項(xiàng)1.√(V)綜合題1、在下面空格處填寫一條語句，以使下面的順序隊(duì)列入隊(duì)算法完整。voidInQueue(structSeqQueue*sq,intx){if(sq->rear==MaxSize)

{printf(“隊(duì)列已滿！\n”);exit(1);}______________sq->rear++;}

正確選項(xiàng)1.sq->data[sq->rear]=x;(V)

2、設(shè)有數(shù)據(jù)集合{50，39，17，83，91，14，65}，依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹，是如下的（）。

正確選項(xiàng)1.(V)

3、以下為求二叉樹深度的算法，完成程序中空格部分。intBTreeDepth(BTreeNode*BT){

if(BT==NULL)

return0;

else

{intdep1=BTreeDepth(BT->left);/*計(jì)算左子樹的深度*/

intdep2=BTreeDepth(BT->right);/*計(jì)算右子樹的深度*/

if(________)

returndep1+1;

else

returndep2+!;

}}

正確選項(xiàng)1.dep1>dep2(V)

4、設(shè)有一個(gè)頭指針為head的不帶頭結(jié)點(diǎn)單向鏈表中（結(jié)點(diǎn)類型為NODE），p為指向該鏈表中某個(gè)結(jié)點(diǎn)的指針。以下程序段為插入一個(gè)指針為s的結(jié)點(diǎn)，使它成為p結(jié)點(diǎn)的直接前驅(qū)，請(qǐng)把合適選項(xiàng)填寫到空行處。NODE*q;q=head;while(q->next!=p)q=q->next;s->next=p;________;

正確選項(xiàng)1.q->next=s(V)

5、寫出下列程序段執(zhí)行后的結(jié)果SeqQueueQ;

InitQueue(Q);inti,a[4]={5,8,12,15};for(i=0;i<4;i++)InQueue(Q,a[i]);InQueue(Q,OutQueue(Q));InQueue(Q,30);InQueue(Q,OutQueue(Q)+10);while(!QueueEmpty(Q))printf(“%d”,OutQueue(Q));

正確選項(xiàng)1.121553018(V)

6、在下面空格處填寫一條語句，以使下面的出棧算法完整。ElemTypePop(structSeqStack*s,ElemTypex){if(StackEmpty(s))

{printf(“棧下溢錯(cuò)誤！\n”);exit(1);}x=s->data[s->top];

________

returnx;}

正確選項(xiàng)1.s->top--;(V)

7、設(shè)某二叉樹先序遍歷為abdec，中序遍歷為dbeac。該二叉樹的圖形是（）。

正確選項(xiàng)1.(V)

8、二叉排序樹結(jié)點(diǎn)類型定義如下：typedefstructBnode{intkey;structBnode*left;structBnode*right;}Bnode;以下為二叉排序樹的查找算法，完成程序中空格部分。Bnode*BSearch(Bnode*bt,intk){

Bnode*p;

if(bt==NULL)

return(bt);

p=bt;while(________)

{if(kkey)

p=p->left;

else

p=p->right;if(p==NULL)break;

}return(p);}

正確選項(xiàng)1.p->key!=k(V)

9、一組記錄的關(guān)鍵字序列為（6，9，7，4，5，8），利用堆排序（堆頂元素是最小元素）的方法建立初始堆是如下哪個(gè)圖？（）

正確選項(xiàng)1.(V)

10、在下面空格處填寫一條語句，以使下面的循環(huán)隊(duì)列出隊(duì)算法完整。ElemTypeOutQueue(structSeqQueue*sq){if(sq->rear==sq->front)

{printf(“隊(duì)列已空，不能進(jìn)行出隊(duì)操作！\n”);exit(1);}________sq->front=(sq->front+1)%MaxSize;

returnx;}

正確選項(xiàng)1.x=sq->data[sq->front];(V)

11、設(shè)數(shù)據(jù)序列為：{53,30,37,12,45,24,96}，從空二叉樹開始逐個(gè)插入該數(shù)據(jù)序列來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是（）。

正確選項(xiàng)1.37,24,12,30,53,45,96(V)

12、以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。voidPreorder(structBTreeNode*BT){if(BT!=NULL)

{_________________;Preorder(BT-->left);Preorder(BT-->right);}}

正確選項(xiàng)1.printf(“%c”,BT->data)(V)

13、設(shè)查找表為：用折半查找在該查找表成功查找到元素55需要經(jīng)過（）次比較。

正確選項(xiàng)1.2(V)

14、設(shè)線性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head。以下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data，完成程序中空格部分。#defineNULL0voidmain(){NODE*head,*p;p=head;/*p為工作指針*/do{printf(“%d\n”,p->data);p=p->next;}while(________);}

正確選項(xiàng)1.p!=NULL(V)

15、設(shè)關(guān)鍵字序列為：（36，69，46，28，30，74），將此序列用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一趟劃分的結(jié)果為（）。

正確選項(xiàng)1.30，28，36，46，69，74(V)

16、以1，2，3，6，7，8作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹是如下哪個(gè)圖？（）

正確選項(xiàng)1.(V)

17、在下面空格處填寫一條語句，以使下面的串連接算法完整。char*strcat(char*s1,char*s2){char*p=s1;while(*p!='\0')p++;while(*s2!='\0'){*p=*s2;p++;_____}*p='\0';

returns1;}

正確選項(xiàng)1.s2++;(V)

18、以下程序是快速排序的算法，完成程序中空格部分。設(shè)待排序的記錄序列存放在a[start],…a[end]中，按記錄的關(guān)鍵字進(jìn)行快速排序，先進(jìn)行一次劃分，再分別進(jìn)行遞歸調(diào)用。

voidquicksort(NODEa[],intstart,intend){inti,j;NODEmid;if(start>=end)return;i=start;j=end;mid=a[i];while(i<J)a[j].key&&while(imid.key)j--;if(i<J)&&while(i

<j)i++;a[i].key<="mid.key)"/>正確選項(xiàng)1.quicksort(a,start,i-1);(V)

19、在下面空格處填寫一條語句，以使下面的串比較算法完整。intstrcmp(char*s1,char*s2){inti;for(i=0;s1[i]!='\0'&&s2[i]!='\0';i++)if(s1[i]>s2[i])

return1;else

if(s1[i]<S2[I])}

正確選項(xiàng)1.return0;(V)

20、設(shè)查找表為(16,15,20,53,64,7)，用冒泡法對(duì)該表進(jìn)行排序，在排序后的有序表的基礎(chǔ)上進(jìn)行折半查找，在等概率條件下,成功查找的平均查找長度為（）。

正確選項(xiàng)1.14/6(V)

21、一組記錄的關(guān)鍵字序列為（36，69，46，28，30，84），對(duì)該序列進(jìn)行直接選擇排序（每次選擇最小關(guān)鍵字），第二趟排序后的結(jié)果序列為（）。

正確選項(xiàng)1.28，30，46，36，69，84(V)

22、已知某帶權(quán)圖的鄰接矩陣如下所示：從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索序列為（）。

正確選項(xiàng)1.1，2，3，4，5，6(V)

23、在下面空格處填寫一條語句，以使下面的進(jìn)棧算法完整。voidPush(structSeqStack*s,ElemTypex){if(s->top==MaxSize-1)

{printf(“棧滿溢出錯(cuò)誤！\n”);exit(1);}________s->data[s->top]=x;}

正確選項(xiàng)1.s->top++;(V)

24、以下是直接插入排序算法對(duì)存放在a[0],a[1],……,a[n-1]中，長度為n的記錄序列按關(guān)鍵字key由小到大排序，完成程序中空格部分。voiddisort(NODEa[],intn){inti,j;NODEtemp;for(i=1;i<N;I++)

{j(temp="a[i];

j=i-1;

while">=0&&temp.key<A[J].KEY)

{a[j+1]="a[j];

_______;

}">正確選項(xiàng)1.j--(V)

25、在下面空格處填寫一條語句，以使下面的順序隊(duì)列出隊(duì)算法完整。El