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

一、判斷題：1、線性表的邏輯順序與物理順序總是一致的。（

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

)３、線性表若采用鏈?zhǔn)酱鎯?chǔ)表達(dá)時(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ù)之間的邏輯結(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ì)列邏輯上都是線性表。（

）

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

（

）1１、刪除二叉排序樹(shù)中一個(gè)結(jié)點(diǎn),再重新插入上去，一定能得到本來(lái)的二叉排序樹(shù)。(

)１2、快速排序是排序算法中最快的一種。(

)1３、多維數(shù)組是向量的推廣。(

)14、一般樹(shù)和二叉樹(shù)的結(jié)點(diǎn)數(shù)目都可認(rèn)為0。

(

)１5、直接選擇排序是一種不穩(wěn)定的排序方法。(

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

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

）18、折半搜索只合用與有序表，涉及有序的順序表和有序的鏈表。(

）1９、堆棧在數(shù)據(jù)中的存儲(chǔ)原則是先進(jìn)先出。(

）20、隊(duì)列在數(shù)據(jù)中的存儲(chǔ)原則是后進(jìn)先出。（

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

)22、哈夫曼樹(shù)一定是滿二叉樹(shù)。（

)２３、程序是用計(jì)算機(jī)語(yǔ)言表述的算法。(

）24、線性表的順序存儲(chǔ)結(jié)構(gòu)是通過(guò)數(shù)據(jù)元素的存儲(chǔ)地址直接反映數(shù)據(jù)元素的邏輯關(guān)系。(

)2５、用一組地址連續(xù)的存儲(chǔ)單元存放的元素一定構(gòu)成線性表。(

）２6、堆棧、隊(duì)列和數(shù)組的邏輯結(jié)構(gòu)都是線性表結(jié)構(gòu)。(

)27、給定一組權(quán)值，可以唯一構(gòu)造出一棵哈夫曼樹(shù)。（

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

)２9、希爾排序在較率上較直接接入排序有較大的改善。但是不穩(wěn)定的。(

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

)31、快速排序法是一種穩(wěn)定性排序法。(

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

）３3、算法分析的目的旨在分析算法的效率以求改善算法。（

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

）3５、數(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ù)元素占用４個(gè)存儲(chǔ)單元，第12個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為１44,則第1個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是10１。（

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

)3９、符號(hào)p-＞nexｔ出現(xiàn)在表達(dá)式中表達(dá)p所指的那個(gè)結(jié)點(diǎn)的內(nèi)容。（

）40、要將指針p移到它所指的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)是執(zhí)行語(yǔ)句p←ｐ->nｅxt。（

)4１、若某堆棧的輸入序列為1,2，3,4,則４,３，1,2不也許是堆棧的輸出序列之一。(

）42、線性鏈表中各個(gè)鏈結(jié)點(diǎn)之間的地址不一定要連續(xù)。(

)43、程序就是算法，但算法不一定是程序。(

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

）４5、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)指針來(lái)間接反映數(shù)據(jù)元素之間邏輯關(guān)系的。(

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

）47、稀疏矩陣中0元素的分布有規(guī)律,因此可以采用三元組方法進(jìn)行壓縮存儲(chǔ)。(

)48、不管堆棧采用何種存儲(chǔ)結(jié)構(gòu),只要堆棧不空，可以任意刪除一個(gè)元素。（

)4９、擬定串T在串S中初次出現(xiàn)的位置的操作稱為串的模式匹配。（

）50、深度為h的非空二叉樹(shù)的第i層最多有2i-1

個(gè)結(jié)點(diǎn)。（

)51、滿二叉樹(shù)也是完全二叉樹(shù)。（

）52、已知一棵二叉樹(shù)的前序序列和后序序列可以唯一地構(gòu)造出該二叉樹(shù)。（

）53、非空二叉排序樹(shù)的任意一棵子樹(shù)也是二叉排序樹(shù)。（

)５4、對(duì)一棵二叉排序樹(shù)進(jìn)行前序遍歷一定可以得到一個(gè)按值有序的序列。(

）55、一個(gè)廣義表的深度是指該廣義表展開(kāi)后所含括號(hào)的層數(shù)。(

)56、散列表的查找效率重要取決于所選擇的散列函數(shù)與解決沖突的方法。(

)５7、序列初始為逆序時(shí)，冒泡排序法所進(jìn)行的元素之間的比較次數(shù)最多。（

)58、已知指針Ｐ指向鍵表L中的某結(jié)點(diǎn),執(zhí)行語(yǔ)句Ｐ=P-〉next不會(huì)刪除該鏈表中的結(jié)點(diǎn)。（

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

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

）61、設(shè)與一棵樹(shù)Ｔ所相應(yīng)的二叉樹(shù)為ＢT,則與T中的葉子結(jié)點(diǎn)所相應(yīng)的BT中的結(jié)點(diǎn)也一定是葉子結(jié)點(diǎn)。(

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

）６3、給出不同的輸入序列建造二叉排序樹(shù),一定得到不同的二叉排序樹(shù)。（

）64、由于希爾排序的最后一趟與直接插入排序過(guò)程相同，因此前者一定比后者花費(fèi)的時(shí)間多。（

)65、程序越短,程序運(yùn)營(yíng)的時(shí)間就越少。(

)66、采用循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)的隊(duì)列就是循環(huán)隊(duì)列。（

）67、堆棧是一種插入和刪除操作在表的一端進(jìn)行的線性表。(

）６8、一個(gè)任意串是其自身的子串。（

)６9、哈夫曼樹(shù)一定是完全二叉樹(shù)。(

)70、帶權(quán)連通圖中某一頂點(diǎn)到圖中另一定點(diǎn)的最短途徑不一定唯一。（

)７1、折半查找方法可以用于按值有序的線性鏈表的查找。（

)7２、稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失效掉隨機(jī)存取功能。(

）73、由一棵二叉樹(shù)的前序序列和后序序列可以唯一擬定它。（

)74、在n個(gè)結(jié)點(diǎn)的元向圖中,若邊數(shù)在于n-1,則該圖必是連通圖。(

）７5、在完全二叉樹(shù)中,若某結(jié)點(diǎn)元左孩子,則它必是葉結(jié)點(diǎn)。(

)76、若一個(gè)有向圖的鄰接矩陣中,對(duì)角線以下元素均為0,則該圖的拓?fù)溆行蛐蛄斜厝淮嬖?。?/p>

)77、樹(shù)的帶權(quán)途徑長(zhǎng)度最小的二叉樹(shù)中必然沒(méi)有度為1的結(jié)點(diǎn)。（

）78、二叉樹(shù)可以用0≤度≤２的有序樹(shù)來(lái)表達(dá)。(

）７9、一組權(quán)值，可以唯一構(gòu)造出一棵哈夫曼樹(shù)。(

)

8０、10１，8８,４6,70,34,39，45,58,6６,10）是堆；(

）８1、將一棵樹(shù)轉(zhuǎn)換成二叉樹(shù)后,根結(jié)點(diǎn)沒(méi)有左子樹(shù)；（

)82、用樹(shù)的前序遍歷和中序遍歷可以導(dǎo)出樹(shù)的后序遍歷;(

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

)８4、非空雙向循環(huán)鏈表中由q所指的結(jié)點(diǎn)后面插入一個(gè)由p指的結(jié)點(diǎn)的動(dòng)作依次為:p->prｉor=q,

p－>nｅxt=q->nｅxt，q－＞neｘｔ＝p，ｑ-＞ｐrｉor->nｅxt←ｐ。（

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

p->next,free

(ｐ)。(

)8６、哈希的查找無(wú)需進(jìn)行關(guān)鍵字的比較。(

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

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

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

)９０、在索引順序表上實(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)的度等于其入度和出度之和。（

）9２、無(wú)向圖的鄰接矩陣是對(duì)稱的有向圖的鄰接矩陣是不對(duì)稱的。(

)９３、具有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)具有n－１條邊（

）二、填空題：1、《數(shù)據(jù)結(jié)構(gòu)》課程討論的重要內(nèi)容是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和______________。2、數(shù)據(jù)結(jié)構(gòu)算法中，通常用時(shí)間復(fù)雜度和______＿_(dá)_＿_(dá)___＿_(dá)__兩種方法衡量其效率。３、一個(gè)算法一該具有＿＿_(dá)___,_＿_(dá)＿_(dá)_,__＿_(dá),___＿_(dá)_和____這五種特性。4、若頻繁地對(duì)線性表進(jìn)行插入與刪除操作,該線性表應(yīng)采用_＿_(dá)＿_(dá)＿_(dá)_＿_(dá)_＿存儲(chǔ)結(jié)構(gòu)。5、在非空線性表中除第一個(gè)元素外，集合中每個(gè)數(shù)據(jù)元素只有一個(gè)＿_(dá)__＿_(dá)_；除最后一個(gè)元素之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)＿_(dá)___＿＿_(dá)_。6、線性表中的每個(gè)結(jié)點(diǎn)最多有＿_(dá)______前驅(qū)和＿_(dá)_____＿＿_(dá)__后繼。7、_＿_(dá)＿＿_(dá)鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問(wèn)到所有結(jié)點(diǎn)。8、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)包含_＿_(dá)＿_(dá)_____＿＿域，____＿_(dá)____＿＿_(dá)__域。9、在雙向鏈表中,每個(gè)結(jié)點(diǎn)具有兩個(gè)指針域,一個(gè)指向_____＿結(jié)點(diǎn),另一個(gè)指向＿_(dá)_＿＿_(dá)__結(jié)點(diǎn)。1０、某帶頭結(jié)點(diǎn)的單鏈表的頭指針head，鑒定該單鏈表非空的條件_______＿_(dá)____＿。11、在雙向鏈表中,每個(gè)結(jié)點(diǎn)具有兩個(gè)指針域，一個(gè)指向_＿_(dá)＿＿＿_(dá)結(jié)點(diǎn)，另一個(gè)指向_____結(jié)點(diǎn)。12、已知指針p指向單鏈表中某個(gè)結(jié)點(diǎn)，則語(yǔ)句p->ｎext=p->neｘt->ｎｅxt的作用__刪除p

的后繼結(jié)點(diǎn)_。13、已知在結(jié)點(diǎn)個(gè)數(shù)大于1的單鏈表中,指針ｐ指向某個(gè)結(jié)點(diǎn)，則下列程序段結(jié)束時(shí),指針q指向*p的__＿_(dá)___＿＿_(dá)___結(jié)點(diǎn)。q=p；whilｅ(q->neｘt!=ｐ)

q=ｑ->next;14、若要在單鏈表結(jié)點(diǎn)*Ｐ后插入一結(jié)點(diǎn)*S，執(zhí)行的語(yǔ)句＿＿_(dá)_＿_(dá)＿＿＿_(dá)_＿_(dá)_＿。1５、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)地址空間可以＿＿_(dá)___＿＿_(dá)，而向量存儲(chǔ)必須是地址空間___＿_(dá)__＿_(dá)__。1６、棧結(jié)構(gòu)允許進(jìn)行刪除操作的一端為_(kāi)______＿＿_(dá)___。1７、在棧的順序?qū)崿F(xiàn)中，棧頂指針tｏｐ，棧為空條件＿_(dá)___＿_(dá)＿_(dá)_＿＿_(dá)_。18、對(duì)于單鏈表形式的隊(duì)列,其空隊(duì)列的F指針和Ｒ指針都等于＿_(dá)________＿_(dá)______。19、若數(shù)組s[0..n-1]為兩個(gè)棧s1和s２的共用存儲(chǔ)空間，僅當(dāng)ｓ[0．.n-1]全滿時(shí)，各棧才不能進(jìn)行棧操作，則為這兩個(gè)棧分派空間的最佳方案是:s1和s2的棧頂指針的初值分別為＿_(dá)__＿_(dá)_＿_(dá)。２０、允許在線性表的一端插入,另一端進(jìn)行刪除操作的線性表稱為_(kāi)__＿_(dá)＿_(dá)。插入的一端為_(kāi)__＿_(dá)_,刪除的一端為_(kāi)___＿＿。２1、設(shè)數(shù)組A[m]為循環(huán)隊(duì)列Ｑ的存儲(chǔ)空間,ｆont為頭指針，ｒｅａｒ?yàn)槲仓羔?，鑒定Q為空隊(duì)列的條件_＿_(dá)_＿＿＿_(dá)_＿_(dá)_＿_(dá)___＿_(dá)_。22、對(duì)于順序存儲(chǔ)的隊(duì)列，存儲(chǔ)空間大小為n,頭指針為F,尾指針為R。若在邏輯上看一個(gè)環(huán),則隊(duì)列中元素的個(gè)數(shù)為_(kāi)___＿_(dá)___＿＿。23、已知循環(huán)隊(duì)列的存儲(chǔ)空間為數(shù)組ｄａt(yī)ａ[21],且頭指針和尾指針?lè)謩e為8和３,則該隊(duì)列的當(dāng)前長(zhǎng)度_____＿_(dá)__＿。24、一個(gè)串的任意個(gè)連續(xù)的字符組成的子序列稱為該串的__＿＿＿_(dá)__，包含該子串的串稱為＿_(dá)______。25、求串T在主串Ｓ中初次出現(xiàn)的位置的操作是＿_(dá)____＿_(dá)＿＿_(dá)_____。２６、在初始為空的隊(duì)列中插入元素A,B,C，D以后，緊接著作了兩次刪除操作,此時(shí)的隊(duì)尾元素是__＿_(dá)______。２7、在長(zhǎng)度為n的循環(huán)隊(duì)列中,刪除其節(jié)點(diǎn)為x的時(shí)間復(fù)雜度為＿_(dá)__＿＿_(dá)＿_(dá)__＿_(dá)_＿。28、已知廣義表L為空，其深度為＿_(dá)________＿。29、已知一順序存儲(chǔ)的線性表，每個(gè)結(jié)點(diǎn)占用ｋ個(gè)單元，若第一個(gè)結(jié)點(diǎn)的地址為DA1,則第i個(gè)結(jié)點(diǎn)的地址為_(kāi)______＿_(dá)＿_(dá)___。30、設(shè)一行優(yōu)先順序存儲(chǔ)的數(shù)組A［5]［６］，A［0][０］的地址為1100，且每個(gè)元素占2個(gè)存儲(chǔ)單元，則A[2］［3］的地址為_(kāi)_＿_(dá)_＿_(dá)___＿＿_(dá)。３１、設(shè)有二維數(shù)組A［9]［19],其每個(gè)元素占兩個(gè)字節(jié),第一個(gè)元素的存儲(chǔ)地址為100,若按行優(yōu)先順序存儲(chǔ)，則元素A[６,６]的存儲(chǔ)地址為_(kāi)__＿_(dá)＿_(dá)___＿_(dá)__,按列優(yōu)順序存儲(chǔ),元素A［６，6]的存儲(chǔ)地址為_(kāi)____＿_(dá)_＿_(dá)____。３2、在進(jìn)行直接插入排序時(shí)，

其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列____＿_(dá)__關(guān);而在進(jìn)行直接選擇排序時(shí)，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列＿＿_(dá)＿_(dá)＿_(dá)__＿關(guān)。33、假設(shè)以行為優(yōu)先存儲(chǔ)的三維數(shù)組Ａ[5][6］［7］,Ａ[0][０］[0］的地址為1100，每個(gè)元素占兩個(gè)存儲(chǔ)單元，則A[4][3][2]的地址為_(kāi)____＿＿。３4、設(shè)二維數(shù)組A[m]［n]按列優(yōu)先存儲(chǔ)，每個(gè)元素占1個(gè)存儲(chǔ)單元，元素Ａ０0的存儲(chǔ)地址ｌｏc(A０0),則Aij的存儲(chǔ)地址ｌoc(Ａij)=____＿＿_(dá)＿＿＿_(dá)__＿＿_(dá)＿_(dá)＿_(dá)。35、稀疏矩陣一般采用＿_(dá)____＿_(dá)_＿方法進(jìn)行壓縮存儲(chǔ)。36、稀疏矩陣可用________＿進(jìn)行壓縮存儲(chǔ)，存儲(chǔ)時(shí)需存儲(chǔ)非零元的____＿_(dá)＿_(dá)、_＿_(dá)＿_(dá)___、_____＿_(dá)_。3７、若矩陣中所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中,區(qū)域外的值全為０，則稱為_(kāi)＿_(dá)_＿＿_(dá)＿_(dá)_。38、若一個(gè)ｎ

階矩陣A中的元素滿足：Aij=Aji

（0＜＝I

,ｊ<=ｎ-1)則稱A為_(kāi)＿_(dá)_____＿_(dá)__矩陣；若主對(duì)角線上方(或下方)的所有元素均為零時(shí)，稱該矩陣為_(kāi)__＿_(dá)_________。39、對(duì)于上三角形和下三角形矩陣，分別以按行存儲(chǔ)和按列存儲(chǔ)原則進(jìn)行壓縮存儲(chǔ)到數(shù)組M[k]中，若矩陣中非0元素為Ａiｊ,則k相應(yīng)為_(kāi)_____＿＿和____＿_(dá)＿＿_(dá)_。４0、設(shè)有一上三角形矩陣Ａ[５］[５]按行壓縮存儲(chǔ)到數(shù)組B中,Ｂ[０]的地址為１０0,每個(gè)元素占2個(gè)單元，則A[3][2]地址為_(kāi)_＿_(dá)_＿_(dá)_＿_(dá)__。41、廣義表(A,(a,b),d，e,（(i,ｊ),ｋ))，則廣義表的長(zhǎng)度為_(kāi)_＿_(dá)__＿_(dá)__＿,深度為_(kāi)___＿＿_(dá)__＿＿。４2、已知廣義表Ａ=((ａ,ｂ,c）,(d，e,ｆ)）,則運(yùn)算hｅad（head

(taiｌ(Ａ))）)＝___

________。43、已知廣義表ｌｓ

=(a，(b,ｃ,ｄ)，e),運(yùn)用ｈeaｄ和tail函數(shù)取出ls中的原子b的運(yùn)算是＿_(dá)___。44、在樹(shù)結(jié)構(gòu)里，有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū),稱為根。非根結(jié)點(diǎn)有且僅有一個(gè)_＿＿＿_(dá)＿_(dá)____，且存在一條從根到該結(jié)點(diǎn)的_＿＿_(dá)＿＿_(dá)＿_(dá)___＿_(dá)_。４5、度數(shù)為0的結(jié)點(diǎn),即沒(méi)有子樹(shù)的結(jié)點(diǎn)叫作__＿_(dá)_＿_(dá)___結(jié)點(diǎn)或_____＿＿_(dá)_結(jié)點(diǎn)。同一個(gè)結(jié)點(diǎn)的兒子結(jié)點(diǎn)之間互稱為_(kāi)_＿＿_(dá)＿＿＿＿_(dá)＿結(jié)點(diǎn)。

４6、假定一棵樹(shù)的廣義表為A（B(e)，C（F(ｈ，i,j）,g),D）,則該樹(shù)的度為＿_(dá)_＿_(dá)__＿_(dá)_＿，樹(shù)的深度為_(kāi)__＿_(dá)____,終端結(jié)點(diǎn)為_(kāi)___＿_(dá)，單分支結(jié)點(diǎn)為，雙分支結(jié)點(diǎn)個(gè)數(shù)為

___＿_(dá)__，三分支結(jié)點(diǎn)為_(kāi)______，C結(jié)點(diǎn)的雙親結(jié)點(diǎn)是____＿＿,孩子結(jié)點(diǎn)是＿＿_(dá)＿＿＿。4８、完全二叉樹(shù)、滿二叉樹(shù)、線索二叉樹(shù)和二叉排序樹(shù)這四個(gè)名詞術(shù)語(yǔ)中,與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)系的是_＿＿_(dá)_＿_(dá)_＿_(dá)＿_(dá)_。47、有三個(gè)結(jié)點(diǎn)的二叉樹(shù),最多有__＿_(dá)____種形狀。4８、每一趟排序時(shí)從排好序的元素中挑出一個(gè)值最小的元素與這些未排小序的元素的第一個(gè)元素互換位置,這種排序方法成為＿＿＿＿_(dá)___＿_(dá)＿_(dá)_排序法。49、高度為ｋ的二叉樹(shù)具有的結(jié)點(diǎn)數(shù)目，最少為_(kāi)__＿＿,最多為＿_(dá)___。５0、對(duì)任何一棵二叉樹(shù),若n0，n１,n2分別是度為0，１,2的結(jié)點(diǎn)的個(gè)數(shù),則n０=__＿_(dá)___。51、在含1０0個(gè)結(jié)點(diǎn)的完全二叉樹(shù),葉子結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)_＿_(dá)＿＿＿。52、將一個(gè)數(shù)據(jù)元素(或記錄)的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列叫___＿＿。53、若一棵滿二叉樹(shù)具有１２1個(gè)結(jié)點(diǎn),則該樹(shù)的深度為＿_(dá)＿_(dá)___＿＿。54、一個(gè)具有767個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其葉子結(jié)點(diǎn)個(gè)數(shù)為_(kāi)____＿_(dá)＿。55、深度為９0的滿二叉樹(shù),第1１層有＿_(dá)______個(gè)結(jié)點(diǎn)。５6、有1０0個(gè)結(jié)點(diǎn)的完全二叉樹(shù),深度為_(kāi)_____＿_(dá)。５7、設(shè)一棵二叉樹(shù)中度為2的結(jié)點(diǎn)１0個(gè)，則該樹(shù)的葉子個(gè)數(shù)為_(kāi)_____＿_(dá)。5８、若待散列的序列為(18，25,63,50,42,３2,9),散列函數(shù)為Ｈ(key）=ｋey

MＯD

9,與18發(fā)生沖突的元素有___＿_(dá)__＿_(dá)____個(gè)。5９、具有３個(gè)2度結(jié)點(diǎn)和4個(gè)葉結(jié)點(diǎn)的二叉樹(shù)可含＿_(dá)___＿_(dá)__＿個(gè)1度結(jié)點(diǎn)。60、一棵具有５層滿二叉樹(shù)中節(jié)點(diǎn)總數(shù)為_(kāi)＿_(dá)_＿_(dá)__＿＿_(dá)。61、一棵具有16個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，對(duì)他按層編號(hào),對(duì)于編號(hào)為7的結(jié)點(diǎn)，他的雙親結(jié)點(diǎn)及左右結(jié)點(diǎn)編號(hào)為_(kāi)_＿＿_(dá)_、_＿_(dá)___、_______。62、深度為k(設(shè)根的層數(shù)為1)的完全二叉樹(shù)至少有__＿＿＿_(dá)＿個(gè)結(jié)點(diǎn),

至多有___＿_(dá)__個(gè)結(jié)點(diǎn)。６３、若要對(duì)某二叉排序樹(shù)進(jìn)行遍歷，保證輸出所有結(jié)點(diǎn)的值序列按增序排列,應(yīng)對(duì)該二叉排序樹(shù)采用________遍歷法。6４、在序列(2,5,8,11,15,１６,2２，24,２7,35,5０）中采用折半查找(二分查找）方法查找元素2４，需要進(jìn)行___＿_(dá)___＿_(dá)＿_(dá)__次元素之間的比較。6５、設(shè)有10個(gè)值，構(gòu)成哈夫曼樹(shù)，則該哈夫曼樹(shù)共有______個(gè)結(jié)點(diǎn)。66、從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的＿_(dá)＿＿_(dá)＿_(dá)_____。67、關(guān)鍵字自身作為哈希函數(shù),即H（k）=k,也可自身加上一個(gè)常數(shù)作為哈希函數(shù),即Ｈ（ｋ)＝ｋ+C這種構(gòu)造哈希函數(shù)的方式叫＿_(dá)_＿_(dá)____＿_(dá)_。68、對(duì)于一個(gè)圖G，若邊集合E(G)為無(wú)向邊的集合,則稱該圖為_(kāi)_＿＿_(dá)＿_(dá)_____。６9、對(duì)于一個(gè)圖Ｇ，若邊集合E(G)為有向邊的集合,則稱該圖為_(kāi)_＿_(dá)________。70、對(duì)于有向圖,頂點(diǎn)的度分為入度和出度,以該頂點(diǎn)為終點(diǎn)的邊數(shù)目叫________;以該頂點(diǎn)為起點(diǎn)的邊數(shù)目叫_＿_(dá)___＿_(dá)_。７１、一個(gè)無(wú)向圖采用鄰接矩陣存儲(chǔ)方法，其鄰接矩陣一定是一個(gè)_＿_(dá)______＿_(dá)___。7２、有一個(gè)n個(gè)頂點(diǎn)的有向完全圖的弧數(shù)____＿_(dá)_______。73、在無(wú)向圖中，若從頂點(diǎn)Ａ到頂點(diǎn)B存在________＿,則稱Ａ與B之間是連通的。74、在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的____＿_(dá)_____倍。75、一個(gè)連通圖的生成樹(shù)是該圖的__＿_(dá)____＿_(dá)__連通子圖。若這個(gè)連通圖有n個(gè)頂點(diǎn)，

則它的生成樹(shù)有＿_(dá)_＿_(dá)＿＿＿_(dá)_條邊。7６、無(wú)向圖的鄰接矩陣是一個(gè)__＿_(dá)_________矩陣。77、假如從一無(wú)向圖的任意頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問(wèn)所有頂點(diǎn)，則該圖一定是_____

___＿_(dá)__。７8、若采用鄰接表的存儲(chǔ)結(jié)構(gòu)，則圖的廣度優(yōu)先搜索類似于二叉樹(shù)的＿_(dá)___＿_(dá)＿_(dá)_＿_(dá)遍歷。７9、若圖的鄰接矩陣是對(duì)稱矩陣,則該圖一定是_＿_(dá)_____＿_(dá)＿_(dá)____。80、從如圖所示的臨接矩陣可以看出,該圖共有＿_(dá)____個(gè)頂點(diǎn)。假如是有向圖,該圖共有__＿＿_(dá)_條弧;假如是無(wú)向圖，則共有＿＿_(dá)____＿條邊。８1、假如從一個(gè)頂點(diǎn)出發(fā)又回到該頂點(diǎn)，則此途徑叫做___＿＿_(dá)_＿_(dá)_＿。82、一個(gè)具有個(gè)n頂點(diǎn)的無(wú)向圖中,要連通所有頂點(diǎn)至少需要__＿_(dá)＿_(dá)__條邊。83、給定序列{100，

8６,

48,

7３，

３5,

３9,

42,

5７,

6６,

21｝,

按堆結(jié)構(gòu)的定義,

則它一定____＿＿_(dá)_＿堆。8４、從未排序序列中選擇一個(gè)元素,該元素將當(dāng)前參與排序的那些元素提成前后兩個(gè)部分，前一部分中所有元素都小于等于所選元素,后一部分中所有元素都大于或等于所選元素,而此時(shí)所選元素處在排序的最終位置。這種排序法稱為_(kāi)＿_(dá)_＿_(dá)＿_(dá)_＿_(dá)__排序法。8５、折半搜索只適合用于＿_(dá)_＿_(dá)______＿_(dá)_____＿。８6、結(jié)點(diǎn)關(guān)鍵字轉(zhuǎn)換為該結(jié)點(diǎn)存儲(chǔ)單元地址的函數(shù)Ｈ稱為＿＿_(dá)___＿_(dá)＿_(dá)___或叫____＿_(dá)____。８7、在索引查找中,一方面查找_＿_(dá)_＿＿_(dá)_，然后查找相應(yīng)的____＿_(dá)___,整個(gè)索引查找的平均查找長(zhǎng)度等于查找索引表的平均長(zhǎng)度與查找相應(yīng)子表的平均查找長(zhǎng)度的_＿_(dá)_＿_(dá)_。三、選擇題:(

)１.數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的

及它們之間的聯(lián)系。A存儲(chǔ)和邏輯結(jié)構(gòu)

B存儲(chǔ)和抽象

Ｃ抱負(fù)和抽象

Ｄ抱負(fù)與邏輯（

)２.在堆棧中存取數(shù)據(jù)的原則是

。A先進(jìn)先出

B后進(jìn)先出

C先進(jìn)后出

Ｄ隨意進(jìn)出（

）３．將一棵有10０個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下，從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1,則編號(hào)為49的結(jié)點(diǎn)的左孩子的編號(hào)為_(kāi)_＿_(dá)__。A.98

B.99

C.５0

Ｄ.48(

）4.對(duì)于如圖所示二叉樹(shù)采用中根遍歷,對(duì)的的遍歷序列應(yīng)為（

)A.ABＣDEF

B.AＢECＤFC.CDFBEＡ

D．ＣBDAEＦ(

)5．設(shè)有100個(gè)元素,用折半查找法進(jìn)行查找時(shí),最大比較次數(shù)是_＿_(dá)_＿

。A.25

Ｂ.５0

C．1０

D.７（

）6．快速排序在＿＿_(dá)_＿情況下最易發(fā)揮其長(zhǎng)處。Ａ.被排序數(shù)據(jù)中具有多個(gè)相同排序碼

B.被排序數(shù)據(jù)已基本有序Ｃ.被排序數(shù)據(jù)完全無(wú)序

Ｄ.被排序數(shù)據(jù)中最大值和最小值相差懸殊（

）7．由兩個(gè)棧共享一個(gè)向量空間的好處是__＿_(dá)__。

A減少存取時(shí)間，減少下溢發(fā)生的機(jī)率

B節(jié)省存儲(chǔ)空間，減少上溢發(fā)生的機(jī)率C減少存取時(shí)間,減少上溢發(fā)生的機(jī)率

Ｄ節(jié)省存儲(chǔ)空間,減少下溢發(fā)生的機(jī)率（

)8.某二叉樹(shù)的前序和后序序列正好相反,則該二叉樹(shù)一定是_____的二叉樹(shù)A空或者只有一個(gè)結(jié)點(diǎn)

B高度等于其結(jié)點(diǎn)數(shù)C任一結(jié)點(diǎn)無(wú)左孩子

D任一結(jié)點(diǎn)無(wú)右孩子（

)9.設(shè)散列表長(zhǎng)m＝14,散列函數(shù)H(K)=K％11,已知表中已有4個(gè)結(jié)點(diǎn)：r(15)=4;

r(3８)=5；

r（61)=６;ｒ(84)=7，其他地址為空,如用二次探測(cè)再散列解決沖突,關(guān)鍵字為49的結(jié)點(diǎn)地址是_＿_(dá)＿_(dá)___。A８

B3

C5

Ｄ９（

）10.在具有n個(gè)項(xiàng)點(diǎn)有e條邊的無(wú)向圖的鄰接矩陣中,零元素的個(gè)數(shù)為_(kāi)_______。A.e

B.2e

C.n2－e

D.n2－２e（

)11．圖的深度優(yōu)先遍歷類似于二叉樹(shù)的___＿_(dá)__。A．先序遍歷

B.中序遍歷

C.后序遍歷

Ｄ．層次遍歷(

）12．設(shè)長(zhǎng)度為ｎ的鏈隊(duì)列用單循環(huán)鏈表表達(dá),若只設(shè)頭指針,則入隊(duì)操作的時(shí)間復(fù)雜度為_(kāi)_＿_(dá)_＿_(dá)。A.

Ｏ(1)

Ｂ．

O(ｌog2ｎ)

C.

O(ｎ)

D.

O(n２)（

）13.堆的形狀是一棵___＿_(dá)__。A．二叉排序樹(shù)

B.滿二叉樹(shù)

C.完全二叉樹(shù)

D.平衡二叉樹(shù)（

)14.一個(gè)無(wú)向連連通圖的生成樹(shù)是具有該連通圖的所有項(xiàng)點(diǎn)的___＿_(dá)__。A.極小連通子圖

B.極小子圖

C.極大連通子圖

D.極大子圖（

）１5.一個(gè)序列中有1000０個(gè)元素，若只想得到其中前１0個(gè)最小元素,最佳采用__＿＿_(dá)__方法A.快速排序

Ｂ.堆排序

C．插入排序

D.二路歸并排序(

)１６．設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為typedef

struｃt

nodｅ

｛

fiｌe://鏈表結(jié)點(diǎn)定義ＥlemType

ｄata；

filｅ:/／數(shù)據(jù)strｕcｔ

noｄe

*

Ｌiｎk；

ｆile:/／結(jié)點(diǎn)后繼指針}

LｉｓtＮodｅ;已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn),若在*p之后插入結(jié)點(diǎn)*ｓ，則應(yīng)執(zhí)行下列哪一個(gè)操作＿_(dá)____。A．

s－>lｉnk

=

p；

p－>link

＝

s;B．

s->lｉｎk

=

p->link；

p->link

＝

s;Ｃ.

s->link

=

p->link；

p

=

s；

D.

p->ｌｉnk

＝

s；

s->liｎk

=

p；（

）17．設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為typｅｄef

ｓtｒｕcｔ

ｎoｄe

{

filｅ://鏈表結(jié)點(diǎn)定義ElemＴyｐｅ

data;

file://數(shù)據(jù)struｃt

node

＊

Link;

ｆｉle:／/結(jié)點(diǎn)后繼指針}

LｉｓｔNｏde;非空的循環(huán)單鏈表ｆirst的尾結(jié)點(diǎn)（由p所指向)滿足：__＿_(dá)__A.

p->lｉnk

==

NＵLＬ；

B.

p

==

NUＬＬ;C.

p-＞link

==

fｉrst;D.

p

==

first;(

)18.計(jì)算機(jī)辨認(rèn)、存儲(chǔ)和加工解決的對(duì)象被統(tǒng)稱為_(kāi)____＿_(dá)__Ａ．?dāng)?shù)據(jù)

Ｂ.數(shù)據(jù)元素

Ｃ．?dāng)?shù)據(jù)結(jié)構(gòu)

D．?dāng)?shù)據(jù)類型(

)1９.在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并使鏈表仍然有序的時(shí)間復(fù)雜度是＿_(dá)＿＿＿_(dá)_＿Ａ.O(1)

B．O(n）

C.Ｏ(nlｏｇn)D.O(n2)（

）２０.隊(duì)和棧的重要區(qū)別是_＿_(dá)＿_(dá)＿_(dá)_A．邏輯結(jié)構(gòu)不同

B.存儲(chǔ)結(jié)構(gòu)不同C.所包含的運(yùn)算個(gè)數(shù)不同

D．限定插入和刪除的位置不同（

）21.鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是__＿_(dá)__＿_(dá)A．插入操作更加方便

B.刪除操作更加方便C．不會(huì)出現(xiàn)下溢的情況

D.不會(huì)出現(xiàn)上溢的情況(

)2２.在目的串T［0…n－1]=”xwxxyｘy”中,對(duì)模式串p[0…m－1］＝”ｘy”進(jìn)行子串定位操作的結(jié)果_＿_(dá)____A.0

Ｂ.２C.３

D．５(

)２3.已知廣義表的表頭為A，表尾為（B,C),則此廣義表為_(kāi)____＿＿_(dá)A.(A，(Ｂ，C)）

Ｂ.(A,B,Ｃ）C.(Ａ,Ｂ,C)

D．（(

A,Ｂ,Ｃ)）(

)２4．二維數(shù)組A按行順序存儲(chǔ)，其中每個(gè)元素占1個(gè)存儲(chǔ)單元。若A[1][1]的存儲(chǔ)地址為４20，A[3][3］的存儲(chǔ)地址為446,則A[5][5]的存儲(chǔ)地址為_(kāi)＿_(dá)_＿_(dá)_Ａ.47０

B.４7１C.４72

D．473(

)25.二叉樹(shù)中第５層上的結(jié)點(diǎn)個(gè)數(shù)最多為_(kāi)＿＿_(dá)＿_(dá)__Ａ.8

B.１５Ｃ．1６

D.32(

）２6．假如某圖的鄰接矩陣是對(duì)角線元素均為零的上三角矩陣,則此圖是＿_(dá)＿＿_(dá)__Ａ.有向完全圖

B.連通圖C．強(qiáng)連通圖D.有向無(wú)環(huán)圖(

）2７.對(duì)ｎ個(gè)關(guān)鍵字的序列進(jìn)行快速排序,平均情況下的空間復(fù)雜度為_(kāi)＿_(dá)___＿A.O（1）

B.O(lｏｇn)C.Ｏ（n）

D.O(nlogn）（

）28．對(duì)于哈希函數(shù)H（kｅy）=key%13,被稱為同義詞的關(guān)鍵字是__＿＿_(dá)_＿A.35和４1

B.23和39C.15和44

Ｄ.2５和51（

）29.

由權(quán)值分別為3,８,6,２,５的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù),它的帶權(quán)途徑長(zhǎng)度為_(kāi)_______。A、

24

B、

48

C、

72

D、

５３（

)30.對(duì)包含N個(gè)元素的散列表進(jìn)行檢索，平均檢索長(zhǎng)度

___＿_(dá)＿_(dá)_A、為

o(lｏｇ2N)

Ｂ、為ｏ(N）

Ｃ、不直接依賴于N

D、上述三者都不是（

）31.

向堆中插入一個(gè)元素的時(shí)間復(fù)雜度為_(kāi)＿_(dá)_____。A、

Ｏ(lｏｇ2n）

B、

O(n)

C、

O(1)

D、

O(nlog２ｎ)(

)３2．下面關(guān)于圖的存儲(chǔ)的敘述中，哪一個(gè)是對(duì)的的。

________A．用相鄰矩陣法存儲(chǔ)圖,占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān),而與邊數(shù)無(wú)關(guān)

Ｂ．用相鄰矩陣法存儲(chǔ)圖,占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān),而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)C．用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)D．用鄰接表法存儲(chǔ)圖,占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)（

）33.輸入序列為（A，B,Ｃ，D）,不也許得到的輸出序列是＿_(dá)_＿_(dá)_．A.

（Ａ,B，C,D)

Ｂ．（D,Ｃ，Ｂ,A）C.(A,

C,Ｄ,B)

Ｄ．(C,Ａ,Ｂ,D)（

）３4.在長(zhǎng)度為n的順序存儲(chǔ)的線性表中，刪除第i個(gè)元素(1≤i≤n)時(shí)，需要從前向后依次前移__＿_(dá)個(gè)元素。A、ｎ-ｉ

B、n-i+1

C、n-i-1

D、i(

）35.設(shè)一個(gè)廣義表中結(jié)點(diǎn)的個(gè)數(shù)為n,則求廣義表深度算法的時(shí)間復(fù)雜度為_(kāi)＿_(dá)_。A、Ｏ(１)

B、O(n)

C、O（n2)

D、O(log

2

n)（

)３６.假定一個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針?lè)謩e為ｆ和r，則判斷隊(duì)空的條件為

____。Ａ、ｆ+1＝=r

B、ｒ+1==ｆ

C、f==0

D、f==r(

）37．從堆中刪除一個(gè)元素的時(shí)間復(fù)雜認(rèn)為_(kāi)＿_(dá)_。A、O(１)

B、O(log

2

ｎ)

C、O(ｎ)

D、O(nloｇ

2

n)（

）38．若需要運(yùn)用形參直接訪問(wèn)實(shí)參,則應(yīng)把形參變量說(shuō)明為＿_(dá)__參數(shù)。A.指針

B.引用

C.值

Ｄ．變量(

）３9.在一個(gè)單鏈表ＨL中,若要在指針ｑ所指結(jié)點(diǎn)的后面插入一個(gè)由指針ｐ所指向的結(jié)點(diǎn)，則執(zhí)行____。Ａ.

q一>ｎeｘt=p一>nexｔ；p一>nｅxｔ=q;C.

q一＞nｅxt=p一＞next;ｐ一>next=ｑ;B．

p一>next=q一＞next;q＝p；

D.

p一>nｅｘｔ=q一＞nｅｘt；q一＞neｘt＝p;(

)4０.在一個(gè)順序隊(duì)列中,隊(duì)首指針指向隊(duì)首元素的__＿_(dá)位置。A.前一個(gè)

B．后一個(gè)

C.當(dāng)前

D.最后一個(gè)(

)41.向二叉搜索樹(shù)中插入一個(gè)元素時(shí),其時(shí)間復(fù)雜度大體力___＿。A

O(1)

Ｂ

O(1oｇ２n）Ｃ

O（n）

D

Ｏ(nloｇ２n)（

）42.算法指的是_＿_(dá)＿_(dá)＿＿＿Ａ.計(jì)算機(jī)程序

B.解決問(wèn)題的計(jì)算方法C．排序算法Ｄ．解決問(wèn)題的有限運(yùn)算序列（

)4３.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí),結(jié)點(diǎn)的存儲(chǔ)地址_＿_(dá)＿＿_(dá)__A.必須是不連續(xù)的

B.連續(xù)與否均可C.必須是連續(xù)的D．和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)(

)4４.將長(zhǎng)充為n的單鏈表鏈接在長(zhǎng)度為ｍ的單鏈表之后的算法的時(shí)間復(fù)雜度為＿_(dá)_____＿Ａ.O(1）

B.Ｏ（n）Ｃ.Ｏ（m)

D.O（m+n)(

）45.由兩個(gè)棧共享一個(gè)向量空間的好處是：＿_(dá)___＿＿_(dá)A.減少存取時(shí)間,減少下溢發(fā)生的機(jī)率

B．節(jié)省存儲(chǔ)空間，減少上溢發(fā)生的機(jī)率C．減少存取時(shí)間，減少上溢發(fā)生的機(jī)率

D.節(jié)省存儲(chǔ)空間，減少下溢發(fā)生的機(jī)率(

)46.設(shè)數(shù)組DAtA[m]作為循環(huán)隊(duì)列ＳQ的存儲(chǔ)空間，fｒont為隊(duì)頭指針,rｅAr為隊(duì)尾指針,則執(zhí)行出隊(duì)操作后其頭指針frｏnt值為_(kāi)＿_(dá)__＿_(dá)_A.

fronｔ＝fronｔ+1

B.

front=(ｆｒont+1)％(ｍ-１)Ｃ.

fｒonｔ=（fronｔ-1)%m

D.

front=(fｒoｎt+1)%m（

）4７.如下陳述中對(duì)的的是__＿_(dá)____A.

串是一種特殊的線性表

B.

串的長(zhǎng)度必須大于零Ｃ.

串中元素只能是字母

Ｄ．

空串就是空白串（

）４8.若目的串的長(zhǎng)充為n，模式串的長(zhǎng)度為［n／３]，則執(zhí)行模式匹配算法時(shí)，在最壞情況下的時(shí)間復(fù)雜度是＿_(dá)_____＿A.O（1）

B.O(n）Ｃ.O（n2）

Ｄ.O（ｎ3）(

)49．一個(gè)非空廣義表的表頭_______＿Ａ.不也許是子表B．只能是子表Ｃ．只能是原子

Ｄ．可以是子表或原子(

)50.

從堆中刪除一個(gè)元素的時(shí)間復(fù)雜度為＿_(dá)＿＿_(dá)_＿_(dá)。A、

Ｏ(１)

B、

O(n）

Ｃ、

Ｏ(lｏｇ2n)

D、

Ｏ(nlog2n)(

)5１．一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)個(gè)數(shù)為２，度為2的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)數(shù)為_(kāi)__＿_(dá)___A.4

B.５C.６

D.7（

）５２.

從二叉搜索樹(shù)中查找一個(gè)元素時(shí),其時(shí)間復(fù)雜度大體為_(kāi)__＿＿_(dá)＿_(dá)。A、

Ｏ(n)

B、

O(1）

C、

O（log2n)

D、

O(n2)(

）53.

根據(jù)n個(gè)元素建立一棵二叉搜索樹(shù)時(shí),其時(shí)間復(fù)雜度大體為_(kāi)＿＿_(dá)____。A、

O(n)

B、

Ｏ（loｇ2n

)

C、

O(n2)

D、

O(nlｏg2ｎ)(

）５4.用某種排序方法對(duì)關(guān)鍵字序列（25，８4,21，４7，15,27,68,３５,2０)進(jìn)行排序時(shí)，序列的變化情況是如下__＿_(dá)____：

20,15，２1，25，47,2７,６8,３５，84

1５,20，21，25,35，27，47，68,８4

15，２０,2１,25，２７,35,47，68，84則所采用的排序方法是________A.選擇排序

Ｂ．希爾排序C.歸并排序

D.快速排序(

)５5.適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是______＿_(dá)A.有序表

B.分塊有序表C.二叉排序樹(shù)

Ｄ.線性鏈表(

）56.

若需要運(yùn)用形參直接訪問(wèn)實(shí)參,則應(yīng)把形參變量說(shuō)明為＿_(dá)__＿＿_(dá)_參數(shù)。

Ａ

指針

B

引用

Ｃ

值

Ｄ

常量

（

)57.鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)比較明顯的優(yōu)點(diǎn)是____＿_(dá)__。

A.

插入操作更加方便

B.

通常不會(huì)出現(xiàn)棧滿的情況

C．

不會(huì)出現(xiàn)?？盏那闆r

D.

刪除操作更加方便

（

）58.設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data,

ｌｉnk）。已知指針q所指結(jié)點(diǎn)是指針ｐ所指結(jié)點(diǎn)的直接前驅(qū),若在＊ｑ與*p之間插入結(jié)點(diǎn)＊s，則應(yīng)執(zhí)行下列哪一個(gè)操作________

Ａ．

s->lｉnk

=

p->link;

p-＞liｎk

=

s;

Ｂ.

p－>link

=

ｓ;

ｓ-＞linｋ

＝

q；C.

p－>ｌinｋ

＝

ｓ－>ｌiｎk;

s->link

=

p;

D.

q->link

=

s;

s->lｉnk

=

ｐ;(

)５９．若讓元素1,2，3依次進(jìn)棧,則出棧順序不也許出現(xiàn)_＿_(dá)_＿_(dá)__種情況。

Ａ.

３,

2,

１

B．

2,

１，

3

C.

３,

1,

2

D.

1，

3,

２

（

）6０.線性鏈表不具有的特點(diǎn)是________。

Ａ．

隨機(jī)訪問(wèn)

Ｂ.

不必事先估計(jì)所需存儲(chǔ)空間大小

Ｃ.

插入與刪除時(shí)不必移動(dòng)元素

D.

所需空間與線性表長(zhǎng)度成正比

（

）６１.在稀疏矩陣的十字鏈接存儲(chǔ)中，每個(gè)列單鏈表中的結(jié)點(diǎn)都具有相同的＿_(dá)_＿＿。

A．行號(hào)

Ｂ．列號(hào)

Ｃ.元素值

Ｄ.地址

（

）62.假定一個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針?lè)謩e為fｒoｎt和rear，存放該隊(duì)列的數(shù)組長(zhǎng)度為N，則判斷隊(duì)空的條件為_(kāi)_＿_(dá)__＿_(dá)。

A.（front+1）%

Ｎ

==

reａr

Ｃ．

fｒont

==

０B．(rｅaｒ＋1）%

N

=＝

ｆrｏnt

D.

frｏｎt

＝=

rｅａr（

）６３.棧的插入和刪除操作在＿_(dá)＿進(jìn)行.

（Ａ).棧頂

(B）．棧底(Ｃ）．任意位置

(D）.指定位置

（

)64.

在一個(gè)順序循環(huán)隊(duì)列中,隊(duì)首指針指向隊(duì)首元素的＿_(dá)＿＿_(dá)＿_(dá)_位置。

Ａ．

后兩個(gè)

B.

后一個(gè)C.

當(dāng)前

D.前一個(gè)

（

）65．下面算法的時(shí)間復(fù)雜度為＿＿。

int

f（ｉnｔ

n){

iｆ

(n==0）retｕｒn

１；

else

reｔuｒn

n＊f（n-１）；}

A．O(1）

B．O(n)

Ｃ．Ｏ(n2）

D.Ｏ（n!)（

)66.數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的(①)以及它們之間的(②）和運(yùn)算的學(xué)科?①Ａ、操作對(duì)象B、計(jì)算方法C、邏輯存儲(chǔ)Ｄ、數(shù)據(jù)映象②A、結(jié)構(gòu)Ｂ、關(guān)系Ｃ、運(yùn)算D、算法(

)6７.數(shù)據(jù)結(jié)構(gòu)被形式地定義為(K,R),其中K是（①）的有限集合，R是K上（②）的有限集合①Ａ、算法Ｂ、數(shù)據(jù)元素C、數(shù)據(jù)操作D、邏輯結(jié)韻②A、操作B、映象Ｃ、存儲(chǔ)Ｄ、關(guān)系(

）6８.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為_(kāi)＿_(dá)_____A、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)Ｃ、線性結(jié)構(gòu)和非線性結(jié)構(gòu)Ｄ、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)（

）69.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種_＿_(dá)＿_(dá)__＿_(dá)的存儲(chǔ)結(jié)構(gòu),線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種______＿_(dá)的存儲(chǔ)結(jié)構(gòu)A、隨機(jī)存取

B、順序存取C、索引存取

Ｄ、HＡSH存?。?/p>

)７0.算法分析的目的是（①），算法分析的兩個(gè)重要方面是(②)①A、找出數(shù)據(jù)結(jié)構(gòu)的合理性

Ｃ、分析算法的效率以求改善B、研究算法中的輸入和輸出的關(guān)系Ｄ、分析算法的易懂性和文檔性②A、空間復(fù)雜性和時(shí)間復(fù)雜性

C、可讀性和文檔性B、對(duì)的性和簡(jiǎn)明性

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

）７1.計(jì)算機(jī)算法指的是（①）,它必具有輸入、輸出和(②）等五個(gè)特性①Ａ、計(jì)算方法Ｂ、排序方法Ｃ、解決萊一問(wèn)題的有限運(yùn)算序列Ｄ、調(diào)度方法②Ａ、可執(zhí)行性、可移植性和可擴(kuò)充性

C、擬定性、有窮性和穩(wěn)定性B、可執(zhí)行性、擬定性和有窮性

D、易謾性、穩(wěn)定性和安全性(

)72.線性表若采用鏈表存儲(chǔ)結(jié)構(gòu)時(shí),規(guī)定內(nèi)存中可用存儲(chǔ)單元的地址＿_(dá)_＿_(dá)__＿Ａ、必須是連續(xù)的Ｂ、部分地址必須是連續(xù)的C、一定是不連續(xù)的Ｄ、連續(xù)不連續(xù)都可以(

)73.在以下的敘述中，對(duì)的的是____＿_(dá)_＿_(dá)_A、線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)

C、棧的操作方式是先進(jìn)先出Ｂ、二維數(shù)組是它的每個(gè)數(shù)據(jù)元素為一個(gè)線性表的線性表Ｄ、隊(duì)列的操作方式是先進(jìn)后出（

）74.

一個(gè)數(shù)組元素A［ｉ]與__＿＿＿_(dá)＿_(dá)的表達(dá)等價(jià)。A、

*(A＋i)

B、

A+ｉ

C、

*A＋i

D、

&A＋i

（

)75.

對(duì)于兩個(gè)函數(shù),若函數(shù)名相同,但只是_______＿_(dá)___不同則不是重載函數(shù)。Ａ、

參數(shù)類型

B、

參數(shù)個(gè)數(shù)

C、

函數(shù)類型

D、函數(shù)變量(

)7６.

若需要運(yùn)用形參直接訪問(wèn)實(shí)參,則應(yīng)把形參變量說(shuō)明為＿_(dá)______參數(shù)A、

指針

Ｂ、

引用

C、

值D、函數(shù)（

)7７.下面程序段的時(shí)間復(fù)雜度為＿_(dá)____＿_(dá)＿＿_(dá)_。

for(int

i=0;

i<ｍ;

ｉ++)

fｏr(int

ｊ=0;

j<ｎ;

j＋+）

A［ｉ]［j］=i＊j;Ａ、

O(m2)

Ｂ、

O(n２)

C、

O(m*n)

D、

O(ｍ+n)(

)78.

執(zhí)行下面程序段時(shí)，執(zhí)行Ｓ語(yǔ)句的次數(shù)為_(kāi)____＿_(dá)_＿＿_(dá)_。

for(ｉnt

ｉ=1;

ｉ<=n;

i++)

fｏr（inｔ

j=１;

ｊ<=i;

j++)

S;A、

ｎ２

B、

n２/2

C、

n(n+1)

D、

n（n+1)/2(

)7９．

下面算法的時(shí)間復(fù)雜度為_(kāi)_＿_(dá)___＿_(dá)＿_(dá)_。

int

f(

unsigneｄ

iｎt

ｎ

)

{

ｉf

(

ｎ==0

||

n==1

)

ｒetuｒｎ

1;

else

retｕrｎ

n＊f（n-1);

｝A、

O(1)

B、

O（ｎ)

C、

O(n２)

D、

O(ｎ!)（

)8０.在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線性表中,向第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)新元素時(shí)，需要從后向前依次后移

個(gè)元素。A、n-i

Ｂ、n-ｉ+1

C、n－i-１

D、ｉ(

)81．在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線性表中，刪除第i個(gè)元素(1≤i≤n＋1)時(shí),需要從前向后依次前移_____個(gè)元素。A、n-ｉ

Ｂ、n－i+1

C、n－i-1

D、i(

)8２.在一個(gè)長(zhǎng)度為n的線性表中順序查找值為x的元素時(shí),查找時(shí)的平均查找長(zhǎng)度（即ｘ同元素的平均比較次數(shù),假定查找每個(gè)元素的概率都相等)為_(kāi)___＿。A、n

B、n／２

C、(n+1)/2

Ｄ、(n-１）/2（

）83.在一個(gè)單鏈表ＨL中,若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行＿_(dá)___

。A、HL

＝

p;

ｐ->ｎeｘt

=

HL;

C、p->neｘｔ

＝

HL;

p

＝

ＨL；Ｂ、p->ｎｅxt

=

HＬ;

HL

＝

p;

D、p->next

=

HL->next;

ＨL->ｎｅxt

=

ｐ;(

)84．在一個(gè)單鏈表HL中,若要在指針q所指的結(jié)點(diǎn)的后面插入一個(gè)由指針p所指的結(jié)點(diǎn)，則執(zhí)行_＿_(dá)＿_(dá)。A、q->nｅｘt

=

p-＞ｎext

;

p－>nｅxt

=

q;

C、q-＞next

=

p->ｎext；

ｐ->nexｔ

＝

ｑ；Ｂ、ｐ-＞ｎext

=

q－>ｎeｘt；

q

＝

ｐ;

D、p->next

=

ｑ->neｘt

;

ｑ->nexｔ

=

p;(

)85．在一個(gè)單鏈表HL中,若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行_____。A、p

=

q－>ｎeｘt

;

ｐ->nｅxｔ

＝

q->ｎｅxt；

C、ｐ

=

q->neｘt

；

q－>neｘt

=

p－>nexｔ;B、p

=

q->nexｔ

;

q－＞next

=

ｐ;

D、q－＞nexｔ

=

q->ｎext－>nｅxｔ;

q->ｎｅxt

＝

q;（

)86．

在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中,每個(gè)行單鏈表中的結(jié)點(diǎn)都具有相同的_____＿_(dá)_。Ａ、

行號(hào)

Ｂ、

列號(hào)

Ｃ、

元素值

Ｄ、

地址(

）8７.

設(shè)一個(gè)廣義表中結(jié)點(diǎn)的個(gè)數(shù)為n，則求廣義表深度算法的時(shí)間復(fù)雜度為_(kāi)_＿_(dá)_＿＿。A、

O(1)

B、

Ｏ(n)

Ｃ、

O(n2)

D、

O(log2ｎ)(

）88.棧的插入與刪除操作在__＿_(dá)＿進(jìn)行。Ａ、棧頂

B、棧底

Ｃ、任意位置

Ｄ、指定位置（

)８9．當(dāng)運(yùn)用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)棧時(shí),假定用tｏp＝＝Ｎ表達(dá)?？眨瑒t向這個(gè)棧插入一個(gè)元素時(shí),一方面應(yīng)執(zhí)行_＿_(dá)_＿語(yǔ)句修改tｏp指針。A、toｐ++

B、toｐ--

C、top=0

D、ｔop(

)90.若讓元素１，2，3依次進(jìn)棧，則出棧順序不也許出現(xiàn)___＿_(dá)種情況。A、3，２,1

B、2，1，3

C、３,１，2

D、1，3，2(

）91.在一個(gè)循環(huán)順序隊(duì)列中,隊(duì)首指針指向隊(duì)首元素的_____位置。A、前一個(gè)

B、后一個(gè)

C、當(dāng)前

D、后面（

）92.當(dāng)運(yùn)用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列時(shí),該隊(duì)列的最大長(zhǎng)度為＿_(dá)＿_(dá)_。A、N-2

B、Ｎ-1

C、Ｎ

Ｄ、N+１(

）９3．從一個(gè)循環(huán)順序隊(duì)列刪除元素時(shí)，一方面需要_＿_(dá)_＿。A、前移一位隊(duì)首指針

Ｂ、后移一位隊(duì)首指針C、取出隊(duì)首指針?biāo)肝恢蒙系脑?/p>

D、取出隊(duì)尾指針?biāo)肝恢蒙系脑兀?/p>

）94.假定一個(gè)循環(huán)順序隊(duì)列的隊(duì)首和隊(duì)尾指針?lè)謩e為f和r，則判斷隊(duì)空的條件是_____。A、f+1==r

B、r+1＝=f

C、f==０

D、f==r（

)95.假定一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針?lè)謩e為front和rｅar，則判斷隊(duì)空的條件是＿_(dá)___。Ａ、fronｔ==rｅar

B、fronｔ！=NULL

C、rｅar!=NULL

D、ｆroｎt==ＮULL四、應(yīng)用題:1、棧和隊(duì)列都是特殊線性表,其特殊性是什么?2、設(shè)有一順序隊(duì)列sq,容量為５，初始狀態(tài)sq．ｆront=sq.reａr＝0,劃出作完下列操作的隊(duì)列及其頭尾指針變化狀態(tài),若不能入隊(duì)，簡(jiǎn)述理由后停止。１)d,e,b

入隊(duì)。2）d，e

出隊(duì)。３)

ｉ，j

入隊(duì)。４)ｂ

出隊(duì)。

5)ｎ,o，p

入隊(duì)。3、設(shè)有一個(gè)順序棧S，元素s1,

s2，

ｓ3，

s4,

ｓ5,

ｓ6依次進(jìn)棧,假如6個(gè)元素的出棧順序?yàn)閟2，

ｓ3，

s4,

s6,

s5，

s１，則順序棧的容量至少應(yīng)為多少?4、將兩個(gè)棧存入數(shù)組Ｖ[１.．m]中應(yīng)如何安排最佳?這時(shí)?？铡M的條件是什么?5、已知稀疏矩陣如下:請(qǐng)寫(xiě)出該稀疏矩陣三元組表達(dá)。6、廣義表Ａ=（a，b，(c,d),(e,(f,g)）),求其長(zhǎng)度，及深度。7、請(qǐng)畫(huà)出下面廣義表相應(yīng)的加入表頭結(jié)點(diǎn)的單鏈表表達(dá),D(A(x,y，L(a,ｂ)),B（z，A(x,y,L（a,b)))）。8、一棵具有ｎ個(gè)結(jié)點(diǎn)的抱負(fù)平衡二叉樹(shù)(即除離根最遠(yuǎn)的最底層外其他各層都是滿的，最底層有若干結(jié)點(diǎn)）有多少層?若設(shè)根結(jié)點(diǎn)在第0層,則樹(shù)的高度h如何用n來(lái)表達(dá)（注意n也許為０）？9、設(shè)二叉樹(shù)后根遍歷為BAC，畫(huà)出所有也許的二叉樹(shù)。10、假設(shè)一棵二叉樹(shù)的層序序列是ABCＤEＦGHIＪ和中序序列是DBGEHJＡＣIF,請(qǐng)畫(huà)出該樹(shù)。11、有一個(gè)完全二叉樹(shù)按層次順序存放在一維數(shù)組中，如下所示：

請(qǐng)指出結(jié)點(diǎn)P的父結(jié)點(diǎn),左子女,右子女。１2、給出下列二叉樹(shù)的先序序列。1３、已知某非空二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu),樹(shù)中結(jié)點(diǎn)的數(shù)據(jù)信息依次存放在一個(gè)一維數(shù)組中,即ＡBC□DＦE□□G□□H□□，該二叉樹(shù)的中序遍歷序列為：14、設(shè)一棵二叉樹(shù)的前序序列為1,2,3,4,5，６，7,8,9,其中序序列為２,３,1,5,4,7,8,6,9，試畫(huà)出該二叉樹(shù)。15、已知一組元素為（46,２5,78,６2,１２，3７,70,２9)，試畫(huà)出按元素排列順序插入生成的一棵二叉樹(shù)。16、由于元素插入的順序不同，所構(gòu)成的二叉排序樹(shù)也有不同的狀態(tài),請(qǐng)畫(huà)出一棵具有1，2，3,4，５，6六個(gè)結(jié)點(diǎn)且以1為根,深度為4的二叉排序樹(shù)。17、什么是線索二叉樹(shù)？為什么要線索化？

18、有n個(gè)頂點(diǎn)的有向連通圖最多有多少條邊?最少有多少條邊？1９、下圖中給出由7個(gè)頂點(diǎn)組成的無(wú)向圖。從頂點(diǎn)1出發(fā)，對(duì)它進(jìn)行深度優(yōu)先遍歷得到的頂點(diǎn)序列是:進(jìn)行廣度優(yōu)先遍歷得到的頂點(diǎn)序列是：2０、什么是連通圖的生成樹(shù)？21、什么是哈夫曼（Hｕffｍan)樹(shù)？22、已知結(jié)點(diǎn)a，ｂ,ｃ,ｄ及其權(quán)值寫(xiě)出哈夫曼樹(shù)的構(gòu)造過(guò)程。

a

b

c

d

7

５

2

4２3、已知圖Ｇ={V

,

E}

Ｖ＝{

a,

b，

c，

d,

e

｝

Ｅ＝{(a,

b),(b，

d),(c,

d),(d,

e),(ｅ,

a),(ａ,

c)}畫(huà)出圖Ｇ，畫(huà)出圖G的鄰接表。24、考慮下圖：1）從頂點(diǎn)A出發(fā),求它的深度優(yōu)先生成樹(shù)。２)從頂點(diǎn)E出發(fā)，求它的廣度優(yōu)先生成樹(shù)。3）根據(jù)普里姆（Ｐrｉｍ)算法，求它的最小生成樹(shù)。

25、設(shè)有關(guān)鍵碼序列(Q,H,C，Ｙ，Q，A，M,S，R，D，F(xiàn),X），要按照關(guān)鍵碼值遞增的順序進(jìn)行排序。若采用初始步長(zhǎng)為4的Ｓhｅｌｌ排序法,則一趟掃描的結(jié)果是：若采用以第一個(gè)元素為分界元素的快速排序法,則一趟掃描的結(jié)果是：２６、一個(gè)對(duì)象序列的排序碼為{46,79，５6,３8，４0，84}，采用快速排序以位于最左位置的對(duì)象為基準(zhǔn)而得到的第一次劃分結(jié)果為:2７、用二分法對(duì)一個(gè)長(zhǎng)度為1０的有序表進(jìn)行查找，填寫(xiě)查找每個(gè)元素需要的比較次數(shù)。

下標(biāo):

0

1

2

3

4

5

6

7

8

9

比較次數(shù)：28、若對(duì)序列(49,38,27，13,97，7６,５0,65)采用泡排序法(按照值的大小從小到大）進(jìn)行排序,請(qǐng)分別在下表中寫(xiě)出每一趟排序的結(jié)果。原始序列

4９

38

27

13

９７

７６

50

6５第1趟的結(jié)果第2趟的結(jié)果第３趟的結(jié)果第4趟的結(jié)果29、給出一組關(guān)鍵字:２9，18，2５,47，58，12,51，１0，分別寫(xiě)出按下列各種排序方法進(jìn)行排序時(shí)的變化過(guò)程:1）歸并排序

每歸并一次書(shū)寫(xiě)一個(gè)順序。2)快速排序

每劃分一次書(shū)寫(xiě)一個(gè)順序。3）堆排序

先建成一個(gè)堆，然后每從堆頂取下一個(gè)元素后,將堆調(diào)整一次。3０、給出一組關(guān)鍵字T=(1２,２，1６,30,8，28,4,10,20，６，18）。寫(xiě)出用下列算法從小到大排序時(shí)第一趟結(jié)束時(shí)的序列:1)希爾排序(第一趟排序的增量為5）2)快速排序(選第一個(gè)記錄為樞軸(分隔）)3）鏈?zhǔn)交鶖?shù)排序(基數(shù)為10）3１、若雜湊表的地址范圍為[０:９]，雜湊函數(shù)為H(key)=(key2+2)MOD

9，并且采用鏈地址方法解決沖突，請(qǐng)畫(huà)出元素7,4,5,3,6,2,８,9,1依次插入該雜湊表以后，該雜湊表的狀態(tài)。３２、已知二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu),鏈結(jié)點(diǎn)的構(gòu)造為lｃｈilｄ

｜

daｔａ

|

ｒchild

,根結(jié)點(diǎn)的指針為T(mén)。下面是運(yùn)用中序遍歷的方法記錄二叉樹(shù)中度為1的結(jié)點(diǎn)的個(gè)數(shù)的算法,算法中設(shè)立了一順序存儲(chǔ)結(jié)構(gòu)的堆棧STACK

[1:Ｍ]，棧頂指針為ｔoｐ,請(qǐng)?jiān)谒惴ǖ目杖碧幪钊脒m當(dāng)內(nèi)容，使之能正常工作。3３、設(shè)有一個(gè)順序棧Ｓ，元素ｓ1,

s2,

s3,

s4,

s５,

s6依次進(jìn)棧,假如6個(gè)元素的出棧順序?yàn)閟2,

ｓ3,

ｓ4，

s6,

s5,

s1,則順序棧的容量至少應(yīng)為多少？34、設(shè)有一個(gè)關(guān)鍵碼的輸入序列

{

5５,

31,

11，

3７，

46,

７3，

６3,

02，

07}

,

(1）

從空樹(shù)開(kāi)始構(gòu)造平衡二叉搜索樹(shù),

畫(huà)出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹(shù)的形態(tài)。若發(fā)生不平衡,

指明需做的平衡旋轉(zhuǎn)的類型及平衡旋轉(zhuǎn)的結(jié)果。

?（2)

３5、關(guān)鍵碼的輸入序列

{

5５,

31,

１１,

37,

４6,

7３，

６3,

0２,

0７

}請(qǐng)計(jì)算在二分法查找、二叉排序樹(shù)兩種的情況下等概率下查找成功的平均查找長(zhǎng)度。3６、

廣義表Ａ=(a，b，（c,d）,(e,(f,g))),計(jì)算下面式子的值Ｈeaｄ（Taｉl(Head(Taiｌ（Tａil（Ａ)))))37、

下圖是用鄰接表存儲(chǔ)的圖,畫(huà)出此圖,并寫(xiě)出從C點(diǎn)開(kāi)始按深度優(yōu)先、廣度優(yōu)先遍歷該圖的結(jié)果。38、

用序列(46，88，45，3９，7０,58,10１,１0，66,34）建立一個(gè)排序二叉樹(shù),畫(huà)出該樹(shù)，并求在等概率情況下查找成功的平均查找長(zhǎng)度。39、

判斷下列序列是否為堆,假如不是請(qǐng)調(diào)整為堆，假如是請(qǐng)判斷是什么類型的堆（10１,88,46，７0，３4，39，４5,58，６6，10)40、

假設(shè)一棵二叉樹(shù)的層序序列是ＡBCＤEＦGHＩJ和中序序列是DＢGEHJACＩF,請(qǐng)畫(huà)出該樹(shù)。４1、

找出所有滿足下列條件的二叉樹(shù)ａ)

它們?cè)谙刃虮闅v和中序遍歷時(shí),得到的結(jié)點(diǎn)訪問(wèn)序列相同;b)

它們?cè)诤笮虮闅v和中序遍歷時(shí),得到的結(jié)點(diǎn)訪問(wèn)序列相同；ｃ）

它們?cè)谙刃虮闅v和后序遍歷時(shí)，得到的結(jié)點(diǎn)訪問(wèn)序列相同。４2、

已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表,其中P結(jié)點(diǎn)既不是首元結(jié)點(diǎn),也不是尾元結(jié)點(diǎn)。ａ)在Ｐ結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句序列是____＿_(dá)ｂ)在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是___＿＿＿c）在表首插入Ｓ結(jié)點(diǎn)的語(yǔ)句序列是_＿＿_(dá)__d)在表尾插入S結(jié)點(diǎn)的語(yǔ)句序列是____＿_(dá)(1)

P-＞next=S;(2)

Ｐ->ｎext＝Ｐ－>next->．next；(3)

Ｐ->next＝S->nｅxt;(4)

S->nｅxt=P－＞next；（5）

S->next＝L;(６)

S－＞next＝NＩL；（7)

Ｑ＝Ｐ;(８）

ＷHIＬE

P->neｘt＜>Q

P＝P->nexｔ;(9）

WHILE

P->ｎｅxｔ!=NULL

P＝P->ｎeｘｔ;（１0）

P=Q;(11)

P=L;(１２)

Ｌ=S;(13)

L＝P;４3、

已知樹(shù)T的先序遍歷序列為ABＣＤEＦGHIJKL,后序遍歷序列為CBEFDＪIＫLＨＧA,請(qǐng)畫(huà)出樹(shù)T。44、

對(duì)關(guān)鍵字序列（7２，87,61，２3，94,16，５，５８)進(jìn)行堆排序、快速排序、直接選擇排序，使之關(guān)鍵字遞增有序,請(qǐng)寫(xiě)出每個(gè)排序的前三趟結(jié)果。45、

請(qǐng)畫(huà)出廣義表Ｄ的圖形表達(dá)D=(D,(a,b),(（a,b),c）,(

）)４6、

若一二叉樹(shù)有2度結(jié)點(diǎn)10０個(gè)，則其葉結(jié)點(diǎn)有多少個(gè)？該二叉樹(shù)可以有多少個(gè)1度頂點(diǎn)?47、

對(duì)于單鏈表、單循環(huán)鏈表和雙向鏈表,假如僅僅知道一個(gè)指向鏈表中某結(jié)點(diǎn)的指針

p

,能否將

p

所指結(jié)點(diǎn)的數(shù)據(jù)元素與其的確存在的直接前驅(qū)互換

?

請(qǐng)對(duì)每一種鏈表作出判斷，若可以,寫(xiě)出程序段；否則說(shuō)明理由。單鏈表和單循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)為date

nｅｘt

雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為pｒiｏｒ

dａt(yī)e

next

（1)

單鏈表

(２)

單循環(huán)鏈表

(3)

雙向鏈表

4７、已知散列函數(shù)為Ｈ(key）＝key%7，散列表長(zhǎng)度為7（散列地址空間為０..6），待散列序列為：(25，４８，32，50,6８）。規(guī)定：(1)根據(jù)以上條件構(gòu)造一散列表，并用線性探測(cè)法解決有關(guān)地址沖突；?(２)若要用該散列表查找元素6８，給出所需的比較次數(shù)。48、已知一組鍵值序列為(38，６4，７3,5２，４０,37，５6，43),試采用快速排序法對(duì)該組序列作升序排序,并給出每一趟的排序結(jié)果。49、已知某二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)如圖所示，試畫(huà)出該二叉樹(shù)。

５０、設(shè)有一個(gè)關(guān)鍵碼的輸入序列{

55,

３1,

1１,

37,

４６,

７3,

63,

0２,

０7

}

(1）從空樹(shù)開(kāi)始構(gòu)造平衡二叉搜索樹(shù),

畫(huà)出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹(shù)

的形態(tài)。若發(fā)生不平衡，指明需做的平衡旋轉(zhuǎn)的類型及平衡旋轉(zhuǎn)的結(jié)果。(2)計(jì)算該平衡二叉搜索樹(shù)在等概率下的查找成功的平均查找長(zhǎng)度和查找不成功的平均查找長(zhǎng)度。51、求下列廣義表運(yùn)算的結(jié)果：1)

HEAＤ(ｐ，h,w);2）

TAIL

（b，ｋ，p,h）;３)

HEAＤ

（（ａ,b),(c,d));4)

TAIL

(a,b),(c,d);5)

HEAD(TAIL（((a,b),（ｃ,ｄ）)))6）

TＡＩＬ(HEAD((a,b)，(c，d)）)52、畫(huà)出下列廣義表的圖形表達(dá):1)

Ｄ（Ａ（)),B（e），Ｃ(a,Ｌ(b,ｃ,d）)2)

Ｊ１(Ｊ２，(J１,a,J3(J1)）,J3（J１）)53、完畢下列規(guī)定:1）

請(qǐng)畫(huà)出下列廣義表的存儲(chǔ)結(jié)構(gòu)（(((a)，b)）,(（(),（d))，（e,ｆ)））2)請(qǐng)寫(xiě)出下面鏈表表達(dá)的廣義表54、一棵二叉樹(shù)如圖:１)

寫(xiě)出對(duì)此樹(shù)進(jìn)行中序、先序、后續(xù)遍歷時(shí)得到的結(jié)點(diǎn)序列。２)

畫(huà)出樹(shù)的后序線索二叉樹(shù)。55、具有３個(gè)節(jié)點(diǎn)的樹(shù)和具有3個(gè)節(jié)點(diǎn)的二叉樹(shù)它們的所有不同形態(tài)有哪些？5６、將下列森林轉(zhuǎn)化為二叉樹(shù)。57、已知一個(gè)圖如下所示,寫(xiě)出其臨接矩陣,并從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索、按廣度優(yōu)先搜索，則可以得到所有頂點(diǎn)序列為什么？５８、試問(wèn)在直接插入排序、希爾排序、快速排序、歸并排序、二分法排序、直接選擇排序中,哪些排序是穩(wěn)定的？哪些是不穩(wěn)定的，哪個(gè)排序平均比較次數(shù)最少?哪個(gè)排序規(guī)定內(nèi)存容量最多?５9、哈希表中使用哈希函數(shù)Ｈ(keｙ）=3

＊

ｋeｙ

％

1１,并采用開(kāi)放定址法解決沖突，隨機(jī)探測(cè)再散列的下一地址公式為：

ｄ1=H

(keｙ

)

di=（

dｉ－１

+7

*

kｅy

)

%

１１

(Ｉ=2,3….．)試在0到１0的散列地址空間中對(duì)關(guān)鍵字序列（22，41,5３,46,30，13,01，６7）畫(huà)出Haｓh表達(dá)意圖，并求在等概率情況下查找成功的平均查找長(zhǎng)度。60、什么是內(nèi)部排序?什么是排序方法的穩(wěn)定性?說(shuō)出你所學(xué)過(guò)的三個(gè)穩(wěn)定算法,一個(gè)不穩(wěn)定算法。６1、何為隊(duì)列上溢?一般用什么方法解決,簡(jiǎn)述之。62、載入下圖所示的有權(quán)圖G，回答下列問(wèn)題：１)

給出從結(jié)點(diǎn)v1出發(fā)按深度優(yōu)先搜索遍歷圖所得的結(jié)點(diǎn)序列;2)

給出圖的拓?fù)湫蛄校?)

給出從結(jié)點(diǎn)v1到結(jié)點(diǎn)v8的最短途徑和關(guān)鍵途徑。63、對(duì)于下圖,請(qǐng)給出1)

相應(yīng)的鄰接矩陣,并給出A，Ｂ,C三個(gè)頂點(diǎn)的入度和出度;２)

鄰接表表達(dá)和逆鄰接表表達(dá)；3)

求其連同分量;6４、對(duì)于下圖的樹(shù)，分別用孩子鏈表和孩子兄弟鏈表法畫(huà)出存儲(chǔ)結(jié)構(gòu)。6５、對(duì)于下圖的樹(shù),請(qǐng)分別用中序、先序的方法寫(xiě)出其遍歷結(jié)果。

66、已知一個(gè)表{jan,feｂ,ｍａr,ａｐr,may,jｕｎe,july,aｕg,sep}１）

使按表中元素的順序依次插入一棵初始為空的二叉排序樹(shù)，畫(huà)出表中元素構(gòu)成的二叉排序樹(shù)。2)

求初等概率情況下查找july的查找長(zhǎng)度。67、數(shù)組ａ[１..10,－2．.6,2．.8]以行優(yōu)先的順序存儲(chǔ)，設(shè)第一個(gè)元素的首地址為100，每個(gè)元素占3個(gè)存儲(chǔ)長(zhǎng)度的存儲(chǔ)空間，則元素A[5，1，8]的存儲(chǔ)地址為多少?

68、設(shè)有一組關(guān)鍵字(17，１3，１5３,2９，３5，21）需插入到表長(zhǎng)為12的表中，請(qǐng)回答下列問(wèn)題：1)

自己設(shè)計(jì)一個(gè)合理的散列函數(shù)２）

用自己設(shè)計(jì)的函數(shù)將上述關(guān)鍵字插入到散列表中,畫(huà)出其結(jié)構(gòu);并指出用線性探測(cè)法解決沖突構(gòu)造散列表的裝填因子為多少?６9、已知一棵三階B-樹(shù)如下圖所示,假定依次從中刪除關(guān)鍵字４6，24，５2，8,9３和80試畫(huà)出每次刪除結(jié)點(diǎn)后樹(shù)的情況：70、已知一棵三階的B-樹(shù)如下圖所示，假定依次插入關(guān)鍵字

50,８3,10請(qǐng)畫(huà)出插入個(gè)結(jié)點(diǎn)后樹(shù)的情況：71、令ｓ=’aａab’，t=’abｃaaa’,u=’ａｂｃaabbabｃａｂａａｃbacbaaa’,分別求出他們的nｅxt值。７2、請(qǐng)畫(huà)出下列二叉樹(shù)的中序線索化前趨鏈樹(shù)，后序線索化后繼鏈樹(shù)。７３、將下列結(jié)點(diǎn)按輸入順序構(gòu)造一棵二叉平衡樹(shù)。{As74、試在如圖所示線索化的二叉樹(shù)中，查找指定結(jié)點(diǎn)E的后繼結(jié)點(diǎn)、Ｃ的前驅(qū)結(jié)點(diǎn)，并說(shuō)明找到結(jié)果的因素。75、什么是數(shù)據(jù)結(jié)構(gòu)?76、試比較線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺陷。77、堆棧和隊(duì)列都是特殊線性表，其特殊性是什么?7８、將兩個(gè)棧存入數(shù)組V［1..m]中應(yīng)如何安排最佳?這時(shí)?？諚M的條件是什么?79、內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m）,提供應(yīng)兩個(gè)棧S1和Ｓ2使用,如何分派這部分存儲(chǔ)空間，使得對(duì)任一個(gè)棧,僅當(dāng)這部分空間全滿時(shí)才發(fā)生上溢。80、給出數(shù)組

int

A[３…８,2…6];當(dāng)它在內(nèi)存中按行存放和按列存放時(shí),分別寫(xiě)出數(shù)組元素A[i,ｊ]的地址計(jì)算公式（設(shè)每個(gè)元素占兩個(gè)存儲(chǔ)單元）。8１、若一二叉樹(shù)有2度結(jié)點(diǎn)10０個(gè),則其葉結(jié)點(diǎn)有多少個(gè)？該二叉樹(shù)可以有多少個(gè)1度頂點(diǎn)？82、如圖所示的二叉樹(shù)完畢中序遍歷、后續(xù)遍歷、先序遍歷,并畫(huà)出后續(xù)線索化的二叉樹(shù)。83、將下圖轉(zhuǎn)換為二叉樹(shù)，對(duì)轉(zhuǎn)換后的二叉樹(shù)進(jìn)行先根、中根、后根遍歷。８4、有一組數(shù)值14、21、32、1５、28，畫(huà)出哈夫曼樹(shù)的生成過(guò)程及最后結(jié)果。85、有n個(gè)頂點(diǎn)的有向連通圖最多有多少條邊?最少有多少條邊？86、什么是哈夫曼(Huｆfｍaｎ）樹(shù)？87、已知圖G={V

，

E｝

Ｖ={

a,

b,

c，

ｄ，

e

}

Ｅ＝{（a，

ｂ),(b,

d),（c,

d）,（d,

e),(e，

ａ）,(ａ,

c)｝畫(huà)出圖Ｇ,畫(huà)出圖G的鄰接表。88、設(shè)一個(gè)有向圖為G=(V，E),其中V=｛v1,v2,ｖ3,ｖ4}，Ｅ={<ｖ２,v1＞,<v2,v３>,<ｖ4,v1＞,<ｖ1,ｖ4＞，

<ｖ4,v２>},畫(huà)出該有向圖，并求出每個(gè)結(jié)點(diǎn)的入度和出度,畫(huà)出相應(yīng)的鄰接矩陣、鄰接表和逆鄰接表。89、請(qǐng)給出下圖的鄰接矩陣和鄰接表。９０、請(qǐng)畫(huà)出下圖中的極大連通子圖。9１、對(duì)于如下圖請(qǐng)畫(huà)出其用ｐrim和kruskal兩種不同算法生成最小生成樹(shù)的各條邊的并入順序。畫(huà)出最小生成樹(shù)。并寫(xiě)出廣度優(yōu)先和深度優(yōu)先的結(jié)點(diǎn)遍歷順序。9２、什么是靜態(tài)查找,什么時(shí)動(dòng)態(tài)查找,什么叫平均查找長(zhǎng)度。93、用序列（46，８8，45，３9,７0,5８，101,10,6６,34）建立一個(gè)二叉排序樹(shù),畫(huà)出該樹(shù)，并求在等概率情況下查找成功的平均查找長(zhǎng)度。９4、已知一個(gè)線性表(38，2５,７4,63，5２，４8),假定采用h(k)＝k%7計(jì)算散列地址進(jìn)行散列存儲(chǔ),若引用線性探測(cè)的開(kāi)放地址法解決沖突,則在該散列表上進(jìn)行檢索的平均檢索長(zhǎng)度為多少，若運(yùn)用連地址法解決沖突，則在該散列表上進(jìn)行檢索的平均查找長(zhǎng)度為多少？設(shè)地址空間為9。請(qǐng)畫(huà)出算列表。96、已知長(zhǎng)度為１2的表：（Jaｎ

,

Fed

,

Mａr

,

Apr

,

Maｙ

,

Juｎ

,

Aｕｇ

,

Sep

,

Ｏct

，

Nov

,

Dｅc)按表中元素的順序,依次插入一棵初始為