數(shù)據(jù)結(jié)構(gòu)綜合題

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)綜合題數(shù)據(jù)結(jié)構(gòu)綜合題

一、判斷題：

1、線性表的規(guī)律順序與物理順序總是一致的。()2、線性表的順序存儲(chǔ)表示優(yōu)于鏈?zhǔn)酱鎯?chǔ)表示。()

3、線性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)所有結(jié)點(diǎn)之間的存儲(chǔ)單元地址可連續(xù)可不連續(xù)。()4、二維數(shù)組是其數(shù)組元素為線性表的線性表。()

5、每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算：插入、刪除和探尋。()

6、數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的規(guī)律結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn)算三個(gè)方面。()

7、線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。（）

8、線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲(chǔ)，也可以鏈接存儲(chǔ)。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲(chǔ)。（）9、棧和隊(duì)列規(guī)律上都是線性表。（）

10、單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)（）

11、刪除二叉排序樹中一個(gè)結(jié)點(diǎn)，再重新插入上去，一定能得到原來的二叉排序樹。（）12、快速排序是排序算法中最快的一種。（）13、多維數(shù)組是向量的推廣。（）

14、一般樹和二叉樹的結(jié)點(diǎn)數(shù)目都可以為0。（）15、直接選擇排序是一種不穩(wěn)定的排序方法。（）

16、98、對(duì)一個(gè)堆按層次遍歷，不一定能得到一個(gè)有序序列。（）

17、在只有度為0和度為k的結(jié)點(diǎn)的k叉樹中，設(shè)度為0的結(jié)點(diǎn)有n0個(gè)，度為k的結(jié)點(diǎn)有nk個(gè)，則有n0=nk+1。（）

18、折半探尋只適用與有序表，包括有序的順序表和有序的鏈表。（）19、堆棧在數(shù)據(jù)中的存儲(chǔ)原則是先進(jìn)先出。（）20、隊(duì)列在數(shù)據(jù)中的存儲(chǔ)原則是后進(jìn)先出。（）

21、用相鄰矩陣表示圖所用的存儲(chǔ)空間大小與圖的邊數(shù)成正比。（）22、哈夫曼樹一定是滿二叉樹。（）23、程序是用計(jì)算機(jī)語言表述的算法。（）

24、線性表的順序存儲(chǔ)結(jié)構(gòu)是通過數(shù)據(jù)元素的存儲(chǔ)地址直接反映數(shù)據(jù)元素的規(guī)律關(guān)系。（）25、用一組地址連續(xù)的存儲(chǔ)單元存放的元素一定構(gòu)成線性表。（）26、堆棧、隊(duì)列和數(shù)組的規(guī)律結(jié)構(gòu)都是線性表結(jié)構(gòu)。（）27、給定一組權(quán)值，可以唯一構(gòu)造出一棵哈夫曼樹。（）

1

28、只有在初始數(shù)據(jù)為逆序時(shí)，冒泡排序所執(zhí)行的比較次數(shù)最多。（）29、希爾排序在較率上較直接接入排序有較大的改進(jìn)。但是不穩(wěn)定的。（）30、在平均狀況下，快速排序法最快，堆積排序法最節(jié)省空間。（）31、快速排序法是一種穩(wěn)定性排序法。（）32、算法一定要有輸入和輸出。（）

33、算法分析的目的旨在分析算法的效率以求改進(jìn)算法。（）

34、非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接后繼元素。（）

35、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)不僅有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，還有索引結(jié)構(gòu)與散列結(jié)構(gòu)。（）36、若頻繁地對(duì)線性表進(jìn)行插入和刪除操作，該線性表采用順序存儲(chǔ)結(jié)構(gòu)更適合。（）37、若線性表采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)數(shù)據(jù)元素占用4個(gè)存儲(chǔ)單元，第12個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為144，則第1個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是101。（）

38、若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，刪除表的第i個(gè)元素之前需要移動(dòng)表中n-i+1個(gè)元素。（）

39、符號(hào)p->next出現(xiàn)在表達(dá)式中表示p所指的那個(gè)結(jié)點(diǎn)的內(nèi)容。（）40、要將指針p移到它所指的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)是執(zhí)行語句p←p->next。（）41、若某堆棧的輸入序列為1,2,3,4，則4,3,1,2不可能是堆棧的輸出序列之一。（）42、線性鏈表中各個(gè)鏈結(jié)點(diǎn)之間的地址不一定要連續(xù)。（）43、程序就是算法，但算法不一定是程序。（）

44、線性表只能采用順序存儲(chǔ)結(jié)構(gòu)或者鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（）

45、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過指針來間接反映數(shù)據(jù)元素之間規(guī)律關(guān)系的。（）46、除插入和刪除操作外，數(shù)組的主要操作還有存取、修改、檢索和排序等。（）47、稀疏矩陣中0元素的分布有規(guī)律，因此可以采用三元組方法進(jìn)行壓縮存儲(chǔ)。（）48、不管堆棧采用何種存儲(chǔ)結(jié)構(gòu)，只要堆棧不空，可以任意刪除一個(gè)元素。（）49、確定串Ｔ在串Ｓ中首次出現(xiàn)的位置的操作稱為串的模式匹配。（）50、深度為h的非空二叉樹的第i層最多有2i-1個(gè)結(jié)點(diǎn)。（）51、滿二叉樹也是完全二叉樹。（）

52、已知一棵二叉樹的前序序列和后序序列可以唯一地構(gòu)造出該二叉樹。（）53、非空二叉排序樹的任意一棵子樹也是二叉排序樹。（）

54、對(duì)一棵二叉排序樹進(jìn)行前序遍歷一定可以得到一個(gè)按值有序的序列。（）55、一個(gè)廣義表的深度是指該廣義表展開后所含括號(hào)的層數(shù)。（）

56、散列表的查找效率主要取決于所選擇的散列函數(shù)與處理沖突的方法。（）57、序列初始為逆序時(shí)，冒泡排序法所進(jìn)行的元素之間的比較次數(shù)最多。（）58、已知指針P指向鍵表L中的某結(jié)點(diǎn)，執(zhí)行語句P=P-〉next不會(huì)刪除該鏈表中的結(jié)點(diǎn)。

2

（）

59、在鏈隊(duì)列中，即使不設(shè)置尾指針也能進(jìn)行入隊(duì)操作。（）

60、假使一個(gè)串中的所有字符均在另一串中出現(xiàn)，則說前者是后者的子串。（）

61、設(shè)與一棵樹T所對(duì)應(yīng)的二叉樹為BT，則與T中的葉子結(jié)點(diǎn)所對(duì)應(yīng)的BT中的結(jié)點(diǎn)也一定是葉子結(jié)點(diǎn)。（）

62、若圖G的最小生成樹不唯一，則G的邊數(shù)一定多于n-1，并且權(quán)值最小的邊有多條（其中n為G的頂點(diǎn)數(shù)）。（）

63、給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。（）

64、由于希爾排序的最終一趟與直接插入排序過程一致，因此前者一定比后者花費(fèi)的時(shí)間多。（）65、程序越短，程序運(yùn)行的時(shí)間就越少。（）

66、采用循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)的隊(duì)列就是循環(huán)隊(duì)列。（）67、堆棧是一種插入和刪除操作在表的一端進(jìn)行的線性表。（）68、一個(gè)任意串是其自身的子串。（）69、哈夫曼樹一定是完全二叉樹。（）

70、帶權(quán)連通圖中某一頂點(diǎn)到圖中另一定點(diǎn)的最短路徑不一定唯一。（）71、折半查找方法可以用于按值有序的線性鏈表的查找。（）72、稀疏矩陣壓縮存儲(chǔ)后,必會(huì)失效掉隨機(jī)存取功能。（）73、由一棵二叉樹的前序序列和后序序列可以唯一確定它。（）74、在n個(gè)結(jié)點(diǎn)的元向圖中,若邊數(shù)在于n-1,則該圖必是連通圖。（）75、在完全二叉樹中,若某結(jié)點(diǎn)元左孩子,則它必是葉結(jié)點(diǎn)。（）

76、若一個(gè)有向圖的鄰接矩陣中,對(duì)角線以下元素均為0,則該圖的拓?fù)溆行蛐蛄斜囟ù嬖凇＃ǎ?7、樹的帶權(quán)路徑長(zhǎng)度最小的二叉樹中必定沒有度為1的結(jié)點(diǎn)。（）78、二叉樹可以用0≤度≤2的有序樹來表示。（）79、一組權(quán)值，可以唯一構(gòu)造出一棵哈夫曼樹。()80、101，88，46，70，34，39，45，58，66，10）是堆；（）81、將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點(diǎn)沒有左子樹；（）82、用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷；（）

83、在非空線性鏈表中由p所指的結(jié)點(diǎn)后面插入一個(gè)由q所指的結(jié)點(diǎn)的過程是依次執(zhí)行語句：q->next=p->next;p->next=q。（）

84、非空雙向循環(huán)鏈表中由q所指的結(jié)點(diǎn)后面插入一個(gè)由p指的結(jié)點(diǎn)的動(dòng)作依次為：p->prior=q,p->next=q->next,q->next=p,q->prior->next←p。（）

85、刪除非空鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的堆棧(設(shè)棧頂指針為top)的一個(gè)元素的過程是依次執(zhí)行:p=top,top=p->next,free(p)。()

3

86、哈希的查找無需進(jìn)行關(guān)鍵字的比較。（）

87、一個(gè)好的哈希函數(shù)應(yīng)使函數(shù)值均勻的分布在存儲(chǔ)空間的有效地址范圍內(nèi)，以盡可能減少?zèng)_突。（）

88、排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。（）

89、隊(duì)列是一種可以在表頭和表尾都能進(jìn)行插入和刪除操作的線性表。（）

90、在索引順序表上實(shí)現(xiàn)分塊查找，在等概率查找狀況下，其平均查找長(zhǎng)度不與表的個(gè)數(shù)有關(guān)，而與每一塊中的元素個(gè)數(shù)有關(guān)。（）

91、對(duì)于有向圖，頂點(diǎn)的度分為入度和出度，入度是以該頂點(diǎn)為終點(diǎn)的入邊數(shù)目；出度是以該頂點(diǎn)為起點(diǎn)的出邊數(shù)目，該頂點(diǎn)的度等于其入度和出度之和。（）92、無向圖的鄰接矩陣是對(duì)稱的有向圖的鄰接矩陣是不對(duì)稱的。（）93、具有n個(gè)頂點(diǎn)的連通圖的生成樹具有n-1條邊（）

二、填空題：

1、《數(shù)據(jù)結(jié)構(gòu)》課程探討的主要內(nèi)容是數(shù)據(jù)的規(guī)律結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和______________。2、數(shù)據(jù)結(jié)構(gòu)算法中，尋常用時(shí)間繁雜度和__________________兩種方法衡量其效率。3、一個(gè)算法一該具有______,______,____,______和____這五種特性。

4、若頻繁地對(duì)線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采用____________存儲(chǔ)結(jié)構(gòu)。

5、在非空線性表中除第一個(gè)元素外，集合中每個(gè)數(shù)據(jù)元素只有一個(gè)_______；除最終一個(gè)元素之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)_________。

6、線性表中的每個(gè)結(jié)點(diǎn)最多有________前驅(qū)和____________后繼。7、______鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)。

8、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)包含____________域，_______________域。

9、在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向______結(jié)點(diǎn)，另一個(gè)指向________結(jié)點(diǎn)。10、某帶頭結(jié)點(diǎn)的單鏈表的頭指針head，判定該單鏈表非空的條件______________。

11、在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向_______結(jié)點(diǎn)，另一個(gè)指向_____結(jié)點(diǎn)。12、已知指針p指向單鏈表中某個(gè)結(jié)點(diǎn)，則語句p->next=p->next->next的作用__刪除p的后繼結(jié)點(diǎn)_。13、已知在結(jié)點(diǎn)個(gè)數(shù)大于1的單鏈表中，指針p指向某個(gè)結(jié)點(diǎn)，則以下程序段終止時(shí)，指針q指向*p的_____________結(jié)點(diǎn)。

q=p;

while(q->next!=p)q=q->next;

14、若要在單鏈表結(jié)點(diǎn)*P后插入一結(jié)點(diǎn)*S，執(zhí)行的語句_______________。

15、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)地址空間可以_________，而向量存儲(chǔ)必需是地址空間___________。16、棧結(jié)構(gòu)允許進(jìn)行刪除操作的一端為_____________。

4

17、在棧的順序?qū)崿F(xiàn)中，棧頂指針top，棧為空條件______________。

18、對(duì)于單鏈表形式的隊(duì)列，其空隊(duì)列的F指針和R指針都等于__________________。

19、若數(shù)組s[0..n-1]為兩個(gè)棧s1和s2的共用存儲(chǔ)空間，僅當(dāng)s[0..n-1]全滿時(shí)，各棧才不能進(jìn)行棧操作，則為這兩個(gè)棧分派空間的最正確方案是：s1和s2的棧頂指針的初值分別為_________。

20、允許在線性表的一端插入,另一端進(jìn)行刪除操作的線性表稱為_______。插入的一端為______,刪除的一端為______。

21、設(shè)數(shù)組A[m]為循環(huán)隊(duì)列Q的存儲(chǔ)空間，font為頭指針，rear為尾指針，判定Q為空隊(duì)列的條件____________________。

22、對(duì)于順序存儲(chǔ)的隊(duì)列，存儲(chǔ)空間大小為n，頭指針為F，尾指針為R。若在規(guī)律上看一個(gè)環(huán)，則隊(duì)列中元素的個(gè)數(shù)為___________。

23、已知循環(huán)隊(duì)列的存儲(chǔ)空間為數(shù)組data[21]，且頭指針和尾指針分別為8和3，則該隊(duì)列的當(dāng)前長(zhǎng)度__________。

24、一個(gè)串的任意個(gè)連續(xù)的字符組成的子序列稱為該串的________，包含該子串的串稱為________。25、求串T在主串S中首次出現(xiàn)的位置的操作是________________。

26、在初始為空的隊(duì)列中插入元素A,B,C,D以后，緊接著作了兩次刪除操作，此時(shí)的隊(duì)尾元素是__________。

27、在長(zhǎng)度為n的循環(huán)隊(duì)列中，刪除其節(jié)點(diǎn)為x的時(shí)間繁雜度為_______________。28、已知廣義表L為空，其深度為___________。

29、已知一順序存儲(chǔ)的線性表，每個(gè)結(jié)點(diǎn)占用k個(gè)單元，若第一個(gè)結(jié)點(diǎn)的地址為DA1，則第i個(gè)結(jié)點(diǎn)的地址為______________。

30、設(shè)一行優(yōu)先順序存儲(chǔ)的數(shù)組A[5][6]