2024年數(shù)據(jù)結(jié)構(gòu)期中題庫及答案

壹、判斷題:

1、線性表的邏輯次序與物理次序^是壹致的。（）

2、線性表的次序存儲表達(dá)優(yōu)于鏈?zhǔn)酱鎯Ρ磉_(dá)。（）

3、線性表若采用鏈?zhǔn)酱鎯Ρ磉_(dá)畤所有結(jié)鉆之間的存儲庠元地址可持續(xù)可不持續(xù)。（）

4、二維數(shù)組是其數(shù)組元素卷線性表的線性表。（）

5、每種數(shù)據(jù)構(gòu)造都應(yīng)具有三種基本運算：插入、刪除和搜索。（）

6、數(shù)據(jù)構(gòu)造概念包括數(shù)據(jù)之間的邏相構(gòu)造，數(shù)據(jù)在計算機中的存儲方式和數(shù)據(jù)的運算三值I

方面。（）

7、線性表中的每他結(jié)粘最多只有壹種前驅(qū)和壹種彳灸繼。（）

8、線性的數(shù)據(jù)構(gòu)造可以次序存儲，也可以鏈接存儲。非線性的數(shù)據(jù)構(gòu)造只能鏈接存儲。（）

9、棧和隊列邏輯上都是線性表。（）

10、單鏈表優(yōu)任何壹種皓鉆出發(fā)，都能訪冏到所有盆?,粘（）

11、刪除二義排序樹中豆種結(jié)黠，再重新插入上去，竟定能得到本來的二義排序樹。（）

12、迅速排序是排序算法中最快的壹種。（）

13、多維數(shù)組是向量的推廣。（）

14、壹般樹和二叉樹的結(jié)黠數(shù)目都可認(rèn)卷0。（）

15、直接選擇排序是壹種不穩(wěn)定的排序措施。（）

16、98、封壹種堆按層次遍歷，不壹定能得到壹種有序序列。（）

17、在只有度卷0和度的結(jié)黠的k叉樹中，設(shè)度卷0的^黠有n0f［札度的^黠有

nk他I,貝I］有nO=nk+10（）

18、折半搜索只合用與有序表，包括有序的次序表和有序的鏈表。（）

19、堆棧在數(shù)據(jù)中的存儲原則是先迤先出。（）

20、隊列在數(shù)據(jù)中的存儲原則是彳友迤先出。（）

21、用相鄰矩陣表達(dá)圖所用的存儲空間大小與圖的邊數(shù)成正比。（）

22、哈夫曼樹壹定是滿二叉樹。（）

23、程序是用計算機^言表述的算法。（）

24、線性表的次序存儲構(gòu)造是通謾數(shù)據(jù)元素的存儲地址直接反應(yīng)數(shù)據(jù)元素的邏輯關(guān)系。（）

25、用壹組地址持續(xù)的存儲罩元寄存的元素壹定構(gòu)成線性表。（）

26、堆棧、隊列和數(shù)組的邏輯構(gòu)造都是線性表構(gòu)造。（）

27、？合定壹組權(quán)值，可以唯壹構(gòu)造出壹棵哈夫曼樹。（）

28、只有在初始數(shù)據(jù)懸逆序畤，冒泡排序所執(zhí)行的比較次數(shù)最多。（）

29、希爾排序在較率上較直接接入排序有較大的改善。不謾不穩(wěn)定的。（）

30、在平均狀況下，迅速排序法最快，堆積排序法最節(jié)省空間。（）

31、迅速排序法是宜種穩(wěn)定性排序法。（）

32、算法壹定要有輸入和輸出。（）

33、算法分析的目的意在分析算法的效率以求改善算法,（）

34、非空線性表中任意壹種數(shù)據(jù)元素均有且僅有壹種直接彳爰繼元素。（）

35、數(shù)據(jù)的存儲構(gòu)造不僅有次序存儲構(gòu)造和鏈?zhǔn)酱鎯?gòu)迨，尚有索引構(gòu)造與散列構(gòu)造）

36、若頻繁地封線性表暹行插入和刪除操作，該線性表采用次序存儲構(gòu)造更合適。（）

37、若線性表采用次序存儲構(gòu)造，每他數(shù)據(jù)元素占用4佃存儲軍元，第12他數(shù)據(jù)元素的存

儲地址卷144,則第1他數(shù)據(jù)元素的存儲地址是101。（）

38、若晨度懸n的線性表采用次序存儲構(gòu)造，刪除表的第if0元素之前需要移勤表中n-i+1

但I(xiàn)元素。（）

39、符號p->next出目前體現(xiàn)式中表達(dá)p所指的那他結(jié)鉆的內(nèi)容。（）

40、要將指針p移到它所指的結(jié)黠的下壹種結(jié)黠是執(zhí)行^句p-p,next。（）

41、若某堆棧的輸入序列卷1,2,3,4,則4,3,1,2不也言午是堆棧的輸出序列之壹。（）

42、線性鏈表中各他I鏈結(jié)玷之間的地址不壹定要持續(xù)。（）

43、程序就是算法，但算法不宜定是程序。（）

44、線性表只能采用次序存儲構(gòu)造或者鏈?zhǔn)酱鎯?gòu)造。（）

45、線性表的鏈?zhǔn)酱鎯?gòu)造是通謾指針來間接反應(yīng)數(shù)據(jù)元素之間邏輯關(guān)系的。（）

46、除插入和刪除操作外，數(shù)組的重要操作尚有存取、修改、檢索和排序等。（）

47、稀疏矩陣中0元素的分布有規(guī)律，因此可以采用三元組措施逛行壓縮存儲。（）

48、不管堆棧采用何種存儲構(gòu)造，只要堆棧不空，可以任意刪除壹種元素。（）

49、確定串T在串S中初次出現(xiàn)的位置的操作稱■^串的模式匹配。（）

50、深度卷h的非空二叉樹的第i層最多有2i-1他皓黠。（）

51、滿二義樹也是完全二義樹。（）

52、已知壹棵二叉樹的前序序列和彳爰序序列可以唯壹地陶造出該二叉樹。（）

53、非空二叉排序樹的任意壹棵子樹也是二叉排序樹。（）

54、封壹棵二又排序樹誕行前序遍歷壹定可以得到壹種按值有序的序列。（）

55、壹種廣義表的深度是指該廣義表展^彳爰所含括號的層數(shù)。（）

56、散列表的查找效率重要取決于所選擇的散列函數(shù)與處理沖突的措施。（）

57、序列初始懸逆序畤，冒泡排序法所逛行的元素之間的比較次數(shù)最多。（）

58、已知指針P指向鍵表L中的某結(jié)黠，執(zhí)行^句P=P->next不曾刪除該鏈表中的^黠。

()

59、在鏈隊列中，雖然不設(shè)置尾指針也能暹行入隊操作,（）

60、假如壹種串中的所有字符均在另壹串中出現(xiàn)，則^前者是彳合者的子串。（）

61、設(shè)與壹棵樹T所封應(yīng)的二叉樹卷BT,則與T中的葉子結(jié)黠所封應(yīng)的BT中的結(jié)黠也宣

定是葉子結(jié)鉆。（）

62、若圖G的最小生成樹不唯宜，則G的邊數(shù)壹定多于n-1,并且權(quán)值最小的邊有多條（其

中n^G的頂鉆數(shù)）。（）

63、幺合出不壹樣的輸入序列建造二叉排序樹，壹定得到不壹樣的二叉排序樹。（）

64、由于希爾排序的最終壹趟與直接插入排序遇程相似，因此前者壹定比彳費者花費的侍間

多。（）

65、程序越短，程序運行的畤間就越少。（）

66、采用循環(huán)鏈表作卷存儲構(gòu)造的隊列就是循環(huán)隊列。（）

67、堆棧是壹種插入和刪除操作在表的壹端暹行的線性表。（）

68、壹種任意串是其自身的子串。（）

69、哈夫曼樹壹定是完全二叉樹。（）

70、帶權(quán)連通圖中某壹頂黠到圖中另壹定黠的最短途徑不壹定唯壹。（）

71、折半查找措施可以用于按值有序的線性鏈表的查找,（）

72、稀疏矩陣壓縮存儲彳急必畬失效掉隨機存取功能。（）

73、由壹棵二叉樹的前序序列和彳令序序列可以唯壹確定它。（）

74、在n他結(jié)鉆的元向圖中，若邊數(shù)在于n-1,則該圖必是連通圖。（）

75、在完全二叉樹中,若某結(jié)黠元左孩子,則它必是葉結(jié)熟。（）

76、若壹種有向圖的鄰接矩陣中，封角線如卜.元素均卷0,則該圖的拓?fù)溆行蛐蛄斜厝淮嬖凇?/p>

（）

77、樹的帶權(quán)途徑晨度最小的二叉樹中必然沒有度懸1的結(jié)黠。（）

78、二叉樹可以用00度W2的有序樹來表達(dá)。（）

79、壹組權(quán)值，可以唯壹構(gòu)造出壹棵哈夫曼樹。（）

80、101,88,46,70,34,39,45,58,66,10）是堆；（）

81、將宜棵樹轉(zhuǎn)換成二叉樹彳為，根結(jié)黠沒有左子樹；（）

82、用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的彳爰序遍歷；（）

83、在非空線性鏈表中由p所指的結(jié)黠背面插入壹種由q所指的結(jié)黠的遇程是依次執(zhí)行^

句：q->next=p->next;p->next=qo（）

84、非空雙向循環(huán)鏈表中由q所指的攵宿.粘背面插入壹種由p指的結(jié)鉆的勃作依次檢：

p->prior=q,p->next=q->next,q->next=p,q->prior->next*-po（）

85、刪除非空鏈?zhǔn)酱嫘艠?gòu)造的堆棧（設(shè)棧頂指針懸top）的壹種元素的遇程是依次執(zhí)

行:p=top,top=p->next,free（p）。（）

86、哈希的查找輾需暹行關(guān)鍵字的比較。（）

87、壹種好的哈希函數(shù)應(yīng)使函數(shù)值均勻的分布在存儲空間的有效地址范圍內(nèi)，以盡量減少

沖突。（）

88、排序是計算機程序設(shè)計中的壹種重要操作，它的功能是將壹種數(shù)據(jù)元素（或記錄i的

任意序列，重新排列成壹種按關(guān)鍵字有序的序列。（）

89、隊列是壹種可以在表^和表尾都能暹行插入和刪除操作的線性表。（）

90、在索引次序表上實現(xiàn)分塊查找，在等概率查找狀況下，其平均查找是度不與表的估I數(shù)

有關(guān)，而與每壹塊中的元素他數(shù)有關(guān)。（）

91、封于有向圖，頂黠的度分懸入度和出度，入度是以該頂黠懸終黠的入邊數(shù)目；出度是

以該頂黠卷起黠的出邊數(shù)目，該頂黠的度等于其入度和出度之和。（）

92、瓢向圖的鄰接矩陣是封稱的有向圖的鄰接矩陣是不封稱的。（）

93.具有nf0頂黠的連通圖的生成樹具有n-1條邊（）

二、填空題：

1、《數(shù)據(jù)構(gòu)造》^程討論的重要內(nèi)容是數(shù)據(jù)的邏輯構(gòu)造、存儲構(gòu)造和O

2、數(shù)據(jù)構(gòu)造算法中，壹般用畤間復(fù)雜度和兩種措施衡量其效率。

3、壹種算法壹該具有和道五種特性。

4、若頻繁地封線性表迤行插入與刪除操作，該線性表應(yīng)采用存儲構(gòu)造。

5、在非空線性表中除第壹種元素外，集合中每儕I數(shù)據(jù)元素只有壹種;除最終壹種

元素之外，集合中每低I數(shù)據(jù)元素均只有壹種，

6、線性表中的每值I結(jié)黠最多有前驅(qū)和彳灸繼。

7、鏈表優(yōu)任何壹種結(jié)鉆出發(fā)，都能訪冏到所有結(jié)黠。

8、鏈?zhǔn)酱鎯?gòu)造中的皓黠包括域，域。

9、在雙向鏈表中，每他I備辭占具有兩他指針域，壹種指向^黠，另壹種指向

10、某帶^^黠的罩鏈表的^指針head,鑒定該軍鏈表非空的條件o

11、在雙向鏈表中，每彳固結(jié)黠具有兩值I指針域，壹種指向蒯i,另壹種指向

結(jié)黠。

12、已知指針p指向罩鏈表中某他I盆沒，則者吾句p->next=p->next->next的作用—刪除p的

彳灸繼結(jié)黠_。

13、已知在東吉黠倜數(shù)不小于1的罩鏈表中，指針p指向某便1結(jié)黠，則下列程序段皓束詩，

指針q指向*p的______________幺吉貼「

q=p;

while(q->next!=p)

q=q->next;

14、若要在軍鏈表令吉黠沖彳令插入壹皓黠*S,執(zhí)行的^句o

15、線性表的鏈?zhǔn)酱鎯?gòu)造地址空間可以,而向量存儲必須是地址空間

O

16、棧構(gòu)造容^選行刪除操作的壹端懸。

17、在棧的次序?qū)嵲校瑮ｍ斨羔榣op,棧卷空條件°

18、封于甲鏈表形式的隊列，其空隊列的F指針和R指針都等于0

19、若數(shù)組s[0..n-1俱兩倜棧s1和S2的共用存儲空間,僅常s[0..n-1]全滿畤，各棧才不能

誕行棧操作，則卷道兩(I同棧分派空間的最佳方案是：S1和S2的棧頂指針的初值分別檢

__________________________O

20、容^在線性表的壹端插入,另壹端迤行刪除操作的線性表稱卷。插入的壹端卷

，刪除的壹端四。

21、設(shè)數(shù)組A[m俱循環(huán)隊列Q的存儲空間，font指針，rear卷尾指針,鑒定Q卷空隊

列的條件C

22、封于次序存儲的隊列，存儲空間大小卷n,指針卷F,尾指針若在邏輯上看壹

種環(huán)，則隊列中元素的4司數(shù)卷。

23、已知循環(huán)隊列的存儲空間卷數(shù)組data[21],且^指針和尾指針分別懸8和3,則該隊列

的目前晨度o

24、壹種串的任意倜持續(xù)的字符構(gòu)成的子序列稱卷該串的，包括該子串的串稱卷

25、求串T在主串S中初次出現(xiàn)的位置的操作是。

26、在初始懸空的隊列中插入元素A,B,C,D彳爰來，緊接著作了兩次刪除操作，此畤的隊尾

元素是O

27、在是度四n的循環(huán)隊列中，刪除其節(jié)黠卷x的畤間復(fù)雜度卷。

28、已知廣義表L懸空，其深度卷o

29、已知壹次序存儲的線性表，每值I結(jié)黠占用k(0單元，若第壹種結(jié)粘的地址卷DAL則

第i他系吉黠的地址卷o

30、設(shè)壹行優(yōu)先次序存儲的數(shù)組A[5][6],A[0H(”的地址卷11。。，且每他I元素占2他存儲覃

元，則A⑵⑶的地址卷°

31、設(shè)有二維數(shù)組A[9][19],其每低I元素占兩f0字節(jié)，第壹種元素的存儲地址卷100,若按

行優(yōu)先次序存儲，則元素A[6,6]的存儲地址卷,按列優(yōu)次序存儲，元素

A[6,6]的存儲地址卷。

32、在謹(jǐn)行直接插入排序畤,其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列關(guān)；而在迤行直

接選擇排序畤，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列關(guān)。

33、假設(shè)以行卷優(yōu)先存儲的三維數(shù)組A[5]⑹⑺,A⑼⑼⑼的地址^1100,每他元素占兩

低I存儲罩元，則A[4][3H2]的地址卷。

34、設(shè)二維數(shù)組A[m][n]按列優(yōu)先存儲，每彳固元素占I他存儲單元，元素A00的存儲地址

loc(AOO),則Aij的存儲地址loc(Aij)=o

35、稀硫矩陣壹般采用措施迤行壓縮存儲。

36、稀疏矩陣可用暹行壓縮存儲，存儲疇需存儲非零元的、、

37、若矩陣中所有非零元素都集中在以主封角線卷中心的帶狀區(qū)域中，區(qū)域外的值全^0,

則稱卷o

38、若壹種n階矩陣A中的元素滿足：Aij=Aji(0v=l,jv=n-1)則稱A矩陣;

若主封角線上方(或下方)的所有元素均卷零畤，稱該矩陣卷。

39、封于上三角形和下三角形矩陣，分別以按行存儲和按列存儲原則暹行壓縮存儲到數(shù)組

M[k]中，若矩陣中非0元素懸Aij,則k封應(yīng)懸和o

40、設(shè)有壹上三角形矩陣A[5H5]按行壓縮存儲到數(shù)組B中，B[0]的地址卷l(X),每倜元素

占2他I罩元，則A[3][2]地址懸。

41、廣義表(A,(a,b),d,e,i(i,j),k))，則廣義表的是度卷,深度懸。

42、已知廣義表A=((a,b,c),(d,e,f))Mh^￡head(head(tail(A))))=。

43、已知廣義表Is=(a,(b.c,d),e),運用head和tail函數(shù)取出Is中的原子b的運算是。

44、在樹構(gòu)造裹，有且僅有壹種結(jié)粘沒有前驅(qū),稱卷根。非根結(jié)粘有且僅有壹種,

且存在壹條優(yōu)根到該結(jié)鉆的o

45、度數(shù)卷0的結(jié)黠，即沒有子樹的令吉黠叫作結(jié)黠或結(jié)黠。同壹種

結(jié)黠的兒子^黠之間互稱卷____________結(jié)黠。

46、假定壹棵樹的廣義表卷A(B(e),C(F(h,i,j),g),D),則該樹的度卷，樹的深度

,終端結(jié)鉆潟,單分支結(jié)鉆潟，雙分支粘值1數(shù)卷，二分支

結(jié)鉆卷,C結(jié)粘的雙親結(jié)黠是,孩子結(jié)貼是。

48、完全二叉樹、滿二叉樹、線索二叉樹和二叉排序樹it四假I名前J術(shù)^中，與數(shù)據(jù)的存儲

構(gòu)造有關(guān)系的是o

47、有三他女吉黠的二叉樹，最多有種形狀。

48、每壹趟排序畤優(yōu)排好序的元素中挑出壹種值最小的元素與道些未排小序的元素的第壹

種元素互換位置，適種排序措施成卷排序法。

49、高度懸k的二叉樹具有的結(jié)黠數(shù)目，至少卷，最多卷。

50、封任何壹棵二叉樹，若nO,nl,n2分別是度卷0,1,2的結(jié)黠的(I司數(shù)，則n0=?

51、在含100f0/吉黠的完全二叉樹，葉子^黠的他數(shù)卷o

52、將壹種數(shù)據(jù)元素(或記錄)的任意序列，重新排列成壹種按關(guān)鍵字有序的序列叫。

53、若壹棵滿二叉樹具有121他I怨｛黠，則該樹的深度卷。

54、壹種具有767彳固結(jié)鉆的完全二叉樹，其葉子結(jié)粘f0數(shù)卷。

55、深度懸90的滿二叉樹，第II層有倜結(jié)貼,

56、有100(0令吉黠的完全二叉樹，深度卷o

57、設(shè)壹棵二叉樹中度卷2的東吉黠10(0,則該樹的葉子他數(shù)懸。

58、若待散列的序列凝18,25,63,50,42,32,9),散列函數(shù)卷H(key尸keyMOD9,與18發(fā)生沖

突的元素有ftlo

59,具有3(02度結(jié)黠和4(0葉幺吉黠的二叉樹可含1度結(jié)黠v

60、壹棵具有5層滿二叉樹中節(jié)鉆冬得數(shù)卷。

61、壹棵具有16彳固皓黠的完全二叉樹，封他按層編號，封于編號卷7的結(jié)黠，他的雙親結(jié)

黠及左右結(jié)黠編號卷、、。

62、深度卷k(設(shè)根的層數(shù)卷1)的完全二叉樹至少有保你鉆,至多有(I腌鉆。

63.若要封某二叉排序樹迤行遍歷，保證輸出所有結(jié)黠的值序列按增序排列，應(yīng)封該二叉

排序樹采用遍歷法。

64、在序歹1(25811,15,16,22,24,27,35,50)中采用折半查找(二分查找)措施查找元索24,需要

謹(jǐn)行次元素之間的比較。

65、設(shè)有1(H固值，構(gòu)成哈夫曼樹，則該哈夫曼樹共有(0令吉粘。

66、優(yōu)樹中壹種余吉砧到另壹種去吉貼之間的分支構(gòu)成追兩倜條吉砧之間的..

67、關(guān)鍵字自身作卷哈希函數(shù)，即H(k)=k,也可自身加上壹種常數(shù)作懸哈希函數(shù)，即

H(k)=k+C適種構(gòu)造哈希函數(shù)的方式叫o

68、封于壹種圖G,若邊集合E(G)卷輾向邊的集合，則稱該圖卷。

69、封于壹種圖G,若邊集合E(G)卷有向邊的集合，則稱該圖卷。

70、封于有向圖，頂黠的度分慮入度和出度，以該頂粘卷終黠的邊數(shù)目叫；以該

頂黠卷起黠的邊數(shù)目叫。

71、壹種輾向圖采用鄰接矩陣存儲措施，其鄰接矩陣壹定是壹種o

72、有壹種n(0頂粘的有向完全圖的弧數(shù)。

73、在艇向圖中，若優(yōu)頂玷A到頂貼R存在.則稱A與R之間是連通的.

74、在壹種輾向圖中，所有頂黠的度數(shù)之和等于所有邊數(shù)的倍。

75、壹種連通圖的生成樹是該圖的連通子圖。若造倜連通圖有n倜頂黠，則

它的生成樹有條邊。

76、輾向圖的鄰接矩陣是壹種—矩陣。

77、假如優(yōu)壹融向圖的任意頂黠出發(fā)迤行壹次深度優(yōu)先搜索即可訪冏所有頂鉆，則該圖壹

定是o

78、若采用鄰接表的存儲構(gòu)造，則圖的廣度優(yōu)先搜索類似于二叉樹的遍歷。

79、若圖的鄰接矩陣是孝寸稱矩陣，則該圖壹定是。

80、優(yōu)如圖所示的臨接矩陣可以看出，該圖共有他頂黠。假如是有向圖，該圖共有

條??；假如是輾向圖，則共有條邊。

81、假如優(yōu)壹種頂黠出發(fā)又回到該頂粘，則此途徑叫做。

82、壹種具有10n頂黠的輾向圖中，要連通所有頂粘至少需要條邊。

83、條合定序列{100.86,48,73,35,39,42,57,66,21},按堆構(gòu)造的定義,則它壹定

堆。

84、優(yōu)未排序序列中選擇壹種元素，該元素將目前參與徘序的那些元素提成前彳麥兩彳固部分，

前壹部分中所有元素都不不小于等于所選元素，彳灸壹部分中所有元素都不小于或等于所選元

素，而此疇所選元素處在排序的最終位置。道種排序法稱卷排序法。

85、折半搜索只合用于o

86、結(jié)站關(guān)鍵宇粒換卷該結(jié)站存儲^元地址的函數(shù)H稱卷或叫

—O

87、在索引查找中，首先查找,然彳菱查找封應(yīng)的，整他索引查找的平

均查找房度等于查找索引表的平均畏度與查找封應(yīng)了?表的平均查找是度的o

三、選擇題：

（）1.數(shù)據(jù)構(gòu)造壹般是研究數(shù)據(jù)的及它（T1之間的聯(lián)絡(luò)。

A存儲和邏輯構(gòu)造B存儲和抽象

C理想和抽象D理想與邏輯

（）2.在堆枝中存取數(shù)據(jù)的原則是。

A先選先出B彳愛迎先出

C先暹彳奏出D隨意迤出

（）3.將壹棵有100他結(jié)黠的完全二叉樹優(yōu)上到下，於左到右依次封結(jié)黠迤行編號，根結(jié)

黠的編號懸1，則編號卷49的結(jié)黠的左孩子的編號懸。

A.98B.99

C.50D./18

（）4.封于如圖所示二叉樹采用中根遍歷，封的的遍歷序列應(yīng)卷（）

A.ABCDEFE.ABECDF

C.CDFBEAD.CBDAEF

（）5.設(shè)有1000司元素，用折半查找法暹行查找畤，最大比較次數(shù)是。

A.25B.50

C.10D.7

（）6.迅速排序在狀況下最易發(fā)揮其房處。

A.被排序數(shù)據(jù)中具有多種相似排序碼B.被排序數(shù)據(jù)已基本有序

C.被排序數(shù)據(jù)完全焦序D.被排序數(shù)據(jù)中最大值和最小值相差懸殊

（）7.由兩他棧共享壹種向量空間的好處是o

A激少存取畤間，減少下溢發(fā)生的機率B節(jié)省存儲空間,減少上溢發(fā)生的機率

C減少存取畤間，減少上溢發(fā)生的機率D節(jié)省存儲空間，減少下溢發(fā)生的機率

（）8.某二叉樹的前序和彳發(fā)序序列恰好相反，則該二叉樹壹定是的二叉樹

A空或者只有壹種結(jié)黠B高度等于其備吉黠數(shù)

C任壹皓鉆瓢左孩子D任壹皓粘輾右孩子

()9.設(shè)散列表房m=14,散列函數(shù)H(K)=K%11,己知表中已^有4佰I結(jié)黠:

r(15)=4;r(38)=5;r(61)=6;r(84)=7,其他地址卷空,如用二次探測再散列處理沖突,關(guān)鍵字

A49的留吉黠地址是o

A8B3

C5D9

()10.在具有nf0項黠有e條邊的輾向圖的鄰接矩陣中，零元素的他I數(shù)懸o

A.eB.2e

C.n2-eD.n2-2e

()11.圖的深度優(yōu)先遍歷類似于二叉樹的o

A.先序遍歷B.中序遍歷

C.彳爰序遍歷D.層次遍歷

()12.設(shè)艮度的鏈隊列用罩循環(huán)鏈表表達(dá)，若只設(shè)指針，則入隊操作的畤間復(fù)雜

度卷O

A.0(1)B.O(log2n)

C.O(n)D.O(n2)

()13.堆的形狀是壹根。

A.二叉排序樹B.滿二叉樹

C.完全二叉樹D.平衡二叉樹

()14.壹種輾向連連通圖的生成樹是具有該連通圖的所有項黠的o

A.極小連通子圖B.極小子圖

C.極大連通子圖D.極大子圖

()15.壹種序列中有10000供I元素，若只想得到其中前10他最小元素，最佳采用

措施

A.迅速排序B.堆排序

C.插入排序D.二路歸并排序

()16.設(shè)甲鏈表中幺吉黠的構(gòu)造懸

typedefstructnode{file:〃鏈表余吉黠定義

ElemTypedata；file:〃數(shù)據(jù)

structnode*Link；file:〃樂吉黠彳為繼指針

}ListNode：

已知指針p所指^黠不是尾結(jié)黠，若在*p之彳菱插入結(jié)鉆*s,則應(yīng)執(zhí)行下列哪壹種操作

O

A.s->link=p；p->link=s：B.s->link=p->link：p->link=s；

C.s->link=p->link；p=s：D.p->link=s：s->link=p；

()17.設(shè)單鏈表中結(jié)黠的構(gòu)造懸

typedefstructnode

{file:〃鏈表結(jié)黠定義

ElemTypedata；file:〃數(shù)據(jù)

structnode*Link；file:〃結(jié)玷彳爰繼指針

}ListNode：

非空的循環(huán)罩鏈表first的尾結(jié)鉆(由p所指向)滿足：

A.p->link==NULL；B,p==NULL：

C.p->link==first；D.p==first；

()18.計算機識別、存儲和加工處理的封象被統(tǒng)稱卷

A.數(shù)據(jù)B.數(shù)據(jù)元素

C.數(shù)據(jù)構(gòu)造D.數(shù)據(jù)類型

()19.在具有n他結(jié)黠的有序罩鏈表中插入壹種新結(jié)黠并使鏈表仍然有序的畤間復(fù)雜度

是_________

A.0(1)B.O(n)

C.O(nlogn)D.O(n2)

()20.隊和棧的重要區(qū)別是

A.邏輯構(gòu)造不壹樣B.存儲構(gòu)造不壹樣

C.所包括的運算(0數(shù)不壹樣D.限定插入和刪除的位置不壹樣

()21.鏈棧與次序棧相比，比較明顯的是處是

A.插入操作愈加以便B.刪除操作愈加以便

C.不曾出現(xiàn)下溢的狀況D.不畬出現(xiàn)上溢的狀況

()22.在目的串邛)尸xwxxyxy”中，封模式串pQ..m-1尸'xy"謔行子串定位操作

的成果________

A.OB.2

C.3D.5

()23.已知廣義表的表^^A,表尾卷(BC),則此廣義表懸

A.(A,(B,C))B.(A,B,C)

C.(ABC)D.((A,B,Ci)

()24.二維數(shù)組A按行次序存儲，其中每值I元素占1f0存儲罩元。若A⑴⑴的存儲地

址懸420,A[3][3]的存儲地址懸446,則A[5][5]的存儲地址卷

A.470B.471

C.472D.473

()25.二叉樹中第5層上的結(jié)黠他數(shù)最多卷

A.8B.15

C.16D.32

()26.假如某圖的鄰接矩陣是封角線元素均懸零的上三角矩陣，則此圖是

A.有向完全圖B.連通圖

C.強連通圖D.有向輾環(huán)圖

()27.封n他關(guān)鍵字的序列迤行迅速排序，平均狀況下的空間復(fù):雜度卷

A.0(1)B.O(logn)

C.O(n)D.O(nlogn)

()28.封于哈希函數(shù)H(key)=key%13,被稱卷同義罰的關(guān)鍵字是

A.35和41B.23和39

C.15和44D.25和51

()29.由權(quán)值分別卷3,8,625的葉子^粘生成壹棵哈夫曼樹，它的帶權(quán)途徑晨度卷

O

A、24B、48

C、72D、53

()30.卦包括Nf0元素的散列表選行檢索，平均檢索是度

A、o(log2N)B、o(N)

C、不直接依賴于ND、上述三者都不是

()31.向堆中插入壹種元素的畤間復(fù)雜度卷。

A、O(log2n)B、。⑻

C、0(1)D、O(nlog2n)

()32.下面有關(guān)圖的存儲的論述中，哪壹種是封的的。

A.用相鄰矩陣法存儲圖，占用的存儲空間數(shù)只與圖中結(jié),鉆他數(shù)有關(guān)，而與邊數(shù)舞關(guān)

B.用相鄰矩陣法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān),而與結(jié)鉆倜數(shù)輾關(guān)

C.用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)黠彳因數(shù)有關(guān)，而與邊數(shù)輾關(guān)

D.用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)，而與幺寺黠僧1數(shù)輾關(guān)

()33.輸入序列卷(A,B,C,D),不也^得到的輸出序列是.

A.(A.B,C,D)B.(D,C,B,A)

C.(A,C,D,B)D/C,A,B,D)

()34.在晨度卷n的次序存儲的線性表中，刪除第i低元素(1<i<n)畤，需要優(yōu)前向彳麥

依次前移佰I元素。

A、n-iB、n-i+1

C、n-i-1D、i

()35.設(shè)壹種廣義表中^黠的f0數(shù)卷n,則求廣義表深度算法的疇間復(fù)雜度,

A、0(1)B、0(n)

C、0(n2)D、O(log2n)

()36.假定壹種次序隊列的隊首和隊尾指針分別卷f和r,則判斷隊空的條件卷一。

A、f+1==rB、r+1==f

C>f==0D、f==r

()37.優(yōu)堆中刪除壹種元素的畤間復(fù)雜認(rèn)卷o

A,0(1)B、0(log2n)

C、0(n)D、O(nlog2n)

()38.若需要運用形參直接訪冏實參，則應(yīng)把形參變量闡明卷參數(shù)。

A.指針B.引用

C.值D.變量

()39.在壹種里鏈表HL中，若要在指針q所指結(jié)粘的背面插入壹種由指針p所指向

的結(jié)黠，則執(zhí)行o

A.q<>next=p^>next：p壹〉next=q：C.q^>next=p^>next：p<>next=q：

B.p壹Anext=q壹〉next：q=p；D.p<>next=q壹〉next；q壹〉next=p；

()40.在壹種次序隊列中，隊首指針指向隊首元素的位置。

A.前壹種B.彳費壹種

C.目前D.最終壹種

()41.向二叉搜索樹中插入壹種元素畤，其畤間復(fù)雜度大體力。

AO(1)BO(1og2n)

CO(n)DO(nlog2n)

()42.算法指的是

A.計算機程序B.處理^題的計算措施

C.排序算法D.處理冏題的有限運算序列

()43.線性表采用鏈?zhǔn)酱鎯Ξ?，結(jié)鉆的存儲地址_________

A.必須是不持續(xù)的B.持續(xù)與否均可

C.必須是持續(xù)的D.和^^粘的存儲地址相持續(xù)

()44.將是充懸n的^鏈表鏈接在是度懸m的單鏈表之彳菱的算法的畤間復(fù)雜度懸

A.0(1)B.O(n)

C.O(m)D.O(m+n)

()45.由兩倜棧共享壹種向量空間的好處是：

A.減少存取畤間，減少卜溢發(fā)生的機率B.節(jié)省存儲空間，減少上溢發(fā)生的機率

C.減少存取畤間，減少上溢發(fā)生的機率D.節(jié)省存儲空間，減少下溢發(fā)生的機率

()46.設(shè)數(shù)組DAtA[m]作卷循環(huán)隊列SQ的存儲空間，front闔隊^指針，reAr卷隊尾指

針，則執(zhí)行出隊操作彳灸其^指針front值卷

A.front=front+1B.front=(front+1)%(m-1)

C.front=(front-1)%mD.front=(front+1)%m

()47.如下陳Bft中封的的是

A.串是壹種特殊的線性表B.串的是度必須不小于零

C.串中元素只能是字母D.空串就是空白串

()48.若目的串的是充卷n,模式串的晨度卷[n/3],則執(zhí)行模式匹配算法疇，在最壤狀況

下的疇間復(fù)雜度是

A.0(1)B.O(n)

C.O(n2)D.O(n3)

()49.壹種非空廣義表的表^

A.不也^是子表B.只能是子表

C.只能是原子D.可以是子表或原子

()50.優(yōu)堆中刪除壹種元素的畤間狂雜度卷o

A、0(1)B、O(n)

C、O(log2n)D、O(nlog2n)

()51.壹棵度卷3的樹中，度卷3的^粘他I數(shù)卷2,度卷2的結(jié)玷他數(shù)卷1,則度懸0

的結(jié)黠(@數(shù)懸

A.4B.5

C.6D.7

()52.優(yōu)二叉搜索樹中查找壹種元素畤，其畤間復(fù)雜度大體卷。

A、O(n)B、0(1)

C、O(log2n)D、O(n2)

()53.根據(jù)n他元素建立壹棵二叉搜索樹畤，其疇間復(fù)雜度大體卷o

A、0⑻B、O(log2n)

C、O(n2)D,O(nlog2n)

()54.用某種排序措施封關(guān)鍵字序列(25,84,21,47,15,27,68,35,20)暹行

排序畤，序列的變化狀況是如下：

20,15,21,25,47,27,68,35,84

15,20,21,25,35,27,47,68,84

15,20,21,25,27,35,47,68,84

則所采用的排序措施是

A.選擇排序B.希爾排序

C.歸并排序D.迅速排序

()55.適于封勛態(tài)查找表選行高效率查找的組織構(gòu)造是

A.有序表B.分塊有序表

C.二叉排序樹D.線性鏈表

()56.若需要運用形參直接訪冏實參，則應(yīng)把形參變量闡明卷參數(shù)。

A指針B引用

C值D常量

()57.鏈?zhǔn)綏Ｅc次序棧相比，壹種比較明顯的是處是。

A.插入操作愈加以便B.壹般不曾出現(xiàn)棧滿的狀況

C.不曾出琨棧空的狀況D,刪除操作愈加以便

()58.設(shè)軍鏈表中結(jié)黠的構(gòu)造卷(data,link).已知指針q所指結(jié)貼是指針p所指結(jié)粘

的直接前驅(qū)，若在*q與*p之間插入結(jié)粘*s,則應(yīng)執(zhí)行下列哪壹種操作

A.s->link=p->link;p->link=s;B.p->link=s;s->link=q;

C.p->link=s->link;s->link=p;D.q->link=s;s->link=p;

()59.若讓元素1,2,3依次暹棧，則出棧次序不也言午出現(xiàn)種狀況。

A.3,2,1B.2,1,3

C.3,1,2D.1,3,2

()60.線性鏈表不具有的特貼是。

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

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

()61.在稀疏矩陣的拾字鏈接存儲中，每低I列軍鏈表中的結(jié)黠都具有相似的。

A.行號B.列號

C.元素值D.地址

()62.假定壹種次序隊列的隊首和隊尾指針分別卷front和rear,寄存該隊列的數(shù)組晨度

卷N,則判斷隊空的條件懸。

A.(front+1)%N==rearC.front==0

B.(rear+1)%N==frontD.front==rear

()63.棧的插入和刪除操作在______迤行.

(A).棧頂(B).棧底

(C).任意位置(D).指定位置

()64.在壹種次序循環(huán)隊列中，隊首指針指向隊首元素的位置。

A.彳爰兩fl司B.彳菱壹種

C.目前D.前壹種

()65.下面算法的畤間復(fù)雜度卷一。

intf(intn){

if(n==0)return1；

elsereturnn*f(n-1)；}

A.0(1)B.0(n)

C.0(n2)D.0(n!)

()66.數(shù)據(jù)構(gòu)造是壹門研究非數(shù)值計算的程序設(shè)計冏題中計算機的(①)以及它fll

之間的(②)和運算的摯科

①A、操作封象B、計算措施C、邏輯存儲D、數(shù)據(jù)映象

②A、構(gòu)造B、關(guān)系C、運算D、算法

()67.數(shù)據(jù)構(gòu)造被形式地定義懸(K,R),其中長是(①)的有限集合,R是K上(②)

的有限集合

①A、算法B、數(shù)據(jù)元素C、數(shù)據(jù)操作D、邏輯結(jié)韻

②A、操作B、映象C、存儲D、關(guān)系

（）68.在數(shù)據(jù)構(gòu)造中，優(yōu)邏輯上可以把數(shù)據(jù)構(gòu)造分卷

A、勤態(tài)構(gòu)造和靜態(tài)構(gòu)造B、緊湊構(gòu)造和非緊湊構(gòu)造

C、線性構(gòu)造和非線性構(gòu)造D、內(nèi)部構(gòu)造和外部構(gòu)造

（）69.線性表的次序存儲構(gòu)造是壹種的存儲構(gòu)造，線性表的鏈?zhǔn)酱鎯?gòu)造是

壹種的存儲構(gòu)造

A、隨機存取B、次序存取

C、索引存取D、HASH存取

（）70.算法分析的目的是（①），算法分析的兩他重要方面是（②）

①A、找出數(shù)據(jù)構(gòu)造的合理性C、分析算法的效率以求改善

B、研究算法中的輸入和輸出的關(guān)系D、分析算法的易懂性和文檔性

②A、空間復(fù)雜性和疇間復(fù)雜性C、可^性和文檔性

B、封的性和簡要性D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

（）71.計算機算法指的是（①），它必具有輸入、輸出和（②）等五值I特性

①A、計算措施B、排序措施

C、處理萊壹冏題的有限運算序列D、調(diào)度措施

②A、可執(zhí)行性、可移植性和可擴充性C、確定性、有窮性和穩(wěn)定性

B、可執(zhí)行性、確定性和有窮性D、易謾性、穩(wěn)定性和安全性

（）72.線性表若采用鏈表存儲構(gòu)造畤，規(guī)定內(nèi)存中可用存儲單元的地址

A、必須是持續(xù)的B、部分地址必須是持續(xù)的

C、壹定是不持續(xù)的D、持續(xù)不持續(xù)都可以

()73.在如下的論述中，卦的的是

A、線性表的線性存儲構(gòu)造優(yōu)于鏈表存儲構(gòu)造C、棧的操作方式是先選先出

B、二維數(shù)組是它的每彳固數(shù)據(jù)元素卷壹種線性表的線性表D、隊列的操作方式是先暹彳登出

()74.宜種數(shù)組元素A[i]與的表達(dá)等價。

A、*(A+i)B、A+i

C、*A+iD、&A+i

()75.封于兩倜函數(shù)，若函數(shù)名相似，但只是不壹樣則不是重載函數(shù)。

A、參數(shù)類型B、參數(shù)低數(shù)

C、函數(shù)類型D、函數(shù)變量

()76.若需要運用形參直接訪冏實參，則應(yīng)把形參變量闡明卷參數(shù)

A、指針B、引用

C、值D、困數(shù)

()77.下面程序段的畤間復(fù):雜度卷。

for(inti=0;i<m;i++)

for(intj=0;j<n;j++)

A[i]ffl=i*j；

A、0(m2)B、0(n2)

C、O(m*n)D、O(m+n)

()78.執(zhí)行下面程序段疇，執(zhí)行句的次數(shù)卷o

for(inti=1;iv=n;i++)

for(intj=1;j<=i;j++)

S；

A、n2B、n2/2

C、n(n+1)D、n(n+1)/2

()79.下面算法的疇間復(fù)雜度卷o

intf(unsignedintn){

if(n==0||n==1)return1;elsereturnn*f(n-1);

)

A、0(1)B、0(n)

C、0(n2)D、Oin!)

()80.在壹種艮度卷n的次序存儲線性表中，向第ifl同元素(1W區(qū)n+1)之前插入壹種新元

素畤，需要優(yōu)彳灸向前依次接移他I元素。

A、n-iB、n-i+1

C、n-i-1D、i

()81.在壹種畏度卷n的次序存儲線性表中，刪除第“固元素(七區(qū)n+1)畤，需要優(yōu)前向

彳為依次前移值I元素。

A、n-iB、n-i+1

C、n-i-1D、i

()82.在壹種是度卷n的線性表中次序行找值的元素畤，查找疇的平均查找信:度(即

x同元素的平均比較次數(shù)，假定查找每倜元素的概率都相等)。

A、nB、n/2

C、(n+1)/2D、(n-1)/2

()83.在壹種單鏈表HL中，若要向表^插入壹種由指針p指向的結(jié)粘，則執(zhí)行。

A、HL=p;p->next=HL;C^p->next=HL;p=HL;

B、p->next=HL;HL=p;D>p->next=HL->next;HL->next=p;

()84.在壹種罩鏈表HL中，若要在指針q所指的結(jié)粘的背面插入壹種由指針p所指的

結(jié)黠，則執(zhí)行。

A、q->next=p->next;p->next=q;C、q->next=p->next;p->next=q;

B、p->next=q->next;q=p;D、p->next=q->next;q->next=p;

()85.在壹種里鏈表HL中，若要刪除由指針q所指向結(jié)黠的彳爰繼結(jié)黠，則執(zhí)行。

A、p=q->next;p->next=q->next;p=q->next;q->next=p->next;

B、p=q->next;q->nex1=p;D、q->next=q->next->next;q->next=q;

()86.在稀疏矩陣的帶行指針向量的鏈接存儲中，每值I行里鏈表中的^黠都具有相似的

A、行號B、列號

C、元素值D、地址

()87.設(shè)壹種廣義表中結(jié)鉆的值I數(shù)卷n,則求廣義表深度算法的畤間復(fù)雜度卷。

A、0(1)B、0(n)

C、0(n2)D、O(log2n)

()88.棧的插入與刪除操作在迤行。

A、棧頂B、棧底

C、任意位置D、指定位置

()89.常運用大小卷N的壹維數(shù)組次序存儲壹種棧侍，假定用top==N表達(dá)?？?，則向

追彳固棧插入壹種元素疇，首先應(yīng)執(zhí)行句修改top指針。

A、top++B,top-

C^top=0D、top

()90.若讓元素1,2,3依次選棧，則出棧次序不也^出現(xiàn)種狀況。

A、3,2,1