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

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

)2、線性表的順序存儲表達優(yōu)于鏈式存儲表達。(

)3、線性表若采用鏈式存儲表達時所有結(jié)點之間的存儲單元地址可連續(xù)可不連續(xù)。(

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

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

)6、數(shù)據(jù)結(jié)構(gòu)概念涉及數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計算機中的存儲方式和數(shù)據(jù)的運算三個方面。(

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

）

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

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

）

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

（

）11、刪除二叉排序樹中一個結(jié)點，再重新插入上去，一定能得到本來的二叉排序樹。（

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

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

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

（

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

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

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

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

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

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

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

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

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

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

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

）26、堆棧、隊列和數(shù)組的邏輯結(jié)構(gòu)都是線性表結(jié)構(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ù)的存儲結(jié)構(gòu)不僅有順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，尚有索引結(jié)構(gòu)與散列結(jié)構(gòu)。（

）36、若頻繁地對線性表進行插入和刪除操作，該線性表采用順序存儲結(jié)構(gòu)更合適。（

）37、若線性表采用順序存儲結(jié)構(gòu)，每個數(shù)據(jù)元素占用4個存儲單元，第12個數(shù)據(jù)元素的存儲地址為144，則第1個數(shù)據(jù)元素的存儲地址是101。（

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

）39、符號p->next出現(xiàn)在表達式中表達p所指的那個結(jié)點的內(nèi)容。（

）40、要將指針p移到它所指的結(jié)點的下一個結(jié)點是執(zhí)行語句p←p->next。（

）41、若某堆棧的輸入序列為1,2,3,4，則4,3,1,2不也許是堆棧的輸出序列之一。（

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

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

）44、線性表只能采用順序存儲結(jié)構(gòu)或者鏈式存儲結(jié)構(gòu)。（

）45、線性表的鏈式存儲結(jié)構(gòu)是通過指針來間接反映數(shù)據(jù)元素之間邏輯關(guān)系的。（

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

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

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

）49、擬定串Ｔ在串Ｓ中初次出現(xiàn)的位置的操作稱為串的模式匹配。（

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

個結(jié)點。（

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

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

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

）54、對一棵二叉排序樹進行前序遍歷一定可以得到一個按值有序的序列。（

）55、一個廣義表的深度是指該廣義表展開后所含括號的層數(shù)。（

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

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

）58、已知指針P指向鍵表L中的某結(jié)點，執(zhí)行語句P=P-〉next不會刪除該鏈表中的結(jié)點。（

）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)鏈表作為存儲結(jié)構(gòu)的隊列就是循環(huán)隊列。（

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

）68、一個任意串是其自身的子串。（

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

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

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

）72、稀疏矩陣壓縮存儲后,必會失效掉隨機存取功能。（

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

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

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

）76、若一個有向圖的鄰接矩陣中,對角線以下元素均為0,則該圖的拓撲有序序列必然存在。（

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

）78、二叉樹可以用0≤度≤2的有序樹來表達。（

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

)

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

）81、將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點沒有左子樹；（

）82、用樹的前序遍歷和中序遍歷可以導出樹的后序遍歷；（

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

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

p->next=q->next,q->next=p,q->prior->next←p。（

）85、刪除非空鏈式存儲結(jié)構(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ù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列。（

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

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

）91、對于有向圖，頂點的度分為入度和出度，入度是以該頂點為終點的入邊數(shù)目；出度是以該頂點為起點的出邊數(shù)目，該頂點的度等于其入度和出度之和。（

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

）93、具有n個頂點的連通圖的生成樹具有n-1條邊（

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

的后繼結(jié)點_。13、已知在結(jié)點個數(shù)大于1的單鏈表中，指針p指向某個結(jié)點，則下列程序段結(jié)束時，指針q指向*p的_____________結(jié)點。q=p;while(q->next!=p)

q=q->next;14、若要在單鏈表結(jié)點*P后插入一結(jié)點*S，執(zhí)行的語句_______________。15、線性表的鏈式存儲結(jié)構(gòu)地址空間可以_________，而向量存儲必須是地址空間___________。16、棧結(jié)構(gòu)允許進行刪除操作的一端為_____________。17、在棧的順序?qū)崿F(xiàn)中，棧頂指針top，棧為空條件______________。18、對于單鏈表形式的隊列，其空隊列的F指針和R指針都等于__________________。19、若數(shù)組s[0..n-1]為兩個棧s1和s2的共用存儲空間，僅當s[0..n-1]全滿時，各棧才不能進行棧操作，則為這兩個棧分派空間的最佳方案是：s1和s2的棧頂指針的初值分別為_________。20、允許在線性表的一端插入,另一端進行刪除操作的線性表稱為_______。插入的一端為______,刪除的一端為______。21、設(shè)數(shù)組A[m]為循環(huán)隊列Q的存儲空間，font為頭指針，rear為尾指針，鑒定Q為空隊列的條件____________________。22、對于順序存儲的隊列，存儲空間大小為n，頭指針為F，尾指針為R。若在邏輯上看一個環(huán)，則隊列中元素的個數(shù)為___________。23、已知循環(huán)隊列的存儲空間為數(shù)組data[21]，且頭指針和尾指針分別為8和3，則該隊列的當前長度__________。24、一個串的任意個連續(xù)的字符組成的子序列稱為該串的________，包含該子串的串稱為________。25、求串T在主串S中初次出現(xiàn)的位置的操作是________________。26、在初始為空的隊列中插入元素A,B,C,D以后，緊接著作了兩次刪除操作，此時的隊尾元素是__________。27、在長度為n的循環(huán)隊列中，刪除其節(jié)點為x的時間復雜度為_______________。28、已知廣義表L為空，其深度為___________。29、已知一順序存儲的線性表，每個結(jié)點占用k個單元，若第一個結(jié)點的地址為DA1，則第i個結(jié)點的地址為______________。30、設(shè)一行優(yōu)先順序存儲的數(shù)組A[5][6]，A[0][0]的地址為1100，且每個元素占2個存儲單元，則A[2][3]的地址為_____________。31、設(shè)有二維數(shù)組A[9][19]，其每個元素占兩個字節(jié)，第一個元素的存儲地址為100，若按行優(yōu)先順序存儲，則元素A[6,6]的存儲地址為______________，按列優(yōu)順序存儲，元素A[6,6]的存儲地址為______________。32、在進行直接插入排序時,

其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列________關(guān)；而在進行直接選擇排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列__________關(guān)。33、假設(shè)以行為優(yōu)先存儲的三維數(shù)組A[5][6][7]，A[0][0][0]的地址為1100，每個元素占兩個存儲單元，則A[4][3][2]的地址為_______。34、設(shè)二維數(shù)組A[m][n]按列優(yōu)先存儲，每個元素占1個存儲單元，元素A00的存儲地址loc(A00)，則Aij的存儲地址loc(Aij)=____________________。35、稀疏矩陣一般采用__________方法進行壓縮存儲。36、稀疏矩陣可用_________進行壓縮存儲，存儲時需存儲非零元的________、________、________。37、若矩陣中所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱為__________。38、若一個n

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

(0<=I

,j<=n-1)則稱A為____________矩陣；若主對角線上方(或下方)的所有元素均為零時，稱該矩陣為______________。39、對于上三角形和下三角形矩陣，分別以按行存儲和按列存儲原則進行壓縮存儲到數(shù)組M[k]中，若矩陣中非0元素為Aij，則k相應(yīng)為________和__________。40、設(shè)有一上三角形矩陣A[5][5]按行壓縮存儲到數(shù)組B中，B[0]的地址為100，每個元素占2個單元，則A[3][2]地址為____________。41、廣義表（A,(a,b),d,e,((i,j),k)）,則廣義表的長度為___________，深度為___________。42、已知廣義表A=((a,b,c),(d,e,f)),則運算head(head

(tail（A）)))=___

________。43、已知廣義表ls

=(a,(b,c,d),e),運用head和tail函數(shù)取出ls中的原子b的運算是_____。44、在樹結(jié)構(gòu)里，有且僅有一個結(jié)點沒有前驅(qū)，稱為根。非根結(jié)點有且僅有一個___________,且存在一條從根到該結(jié)點的_______________。45、度數(shù)為0的結(jié)點，即沒有子樹的結(jié)點叫作__________結(jié)點或_________結(jié)點。同一個結(jié)點的兒子結(jié)點之間互稱為___________結(jié)點。

46、假定一棵樹的廣義表為A(B(e),C(F(h,i,j),g),D),則該樹的度為___________，樹的深度為_________，終端結(jié)點為______，單分支結(jié)點為，雙分支結(jié)點個數(shù)為

_______，三分支結(jié)點為_______，C結(jié)點的雙親結(jié)點是______，孩子結(jié)點是______。48、完全二叉樹、滿二叉樹、線索二叉樹和二叉排序樹這四個名詞術(shù)語中，與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān)系的是_____________。47、有三個結(jié)點的二叉樹，最多有________種形狀。48、每一趟排序時從排好序的元素中挑出一個值最小的元素與這些未排小序的元素的第一個元素互換位置，這種排序方法成為_____________排序法。49、高度為k的二叉樹具有的結(jié)點數(shù)目，最少為_____,最多為_____。50、對任何一棵二叉樹，若n0，n1，n2分別是度為0，1，2的結(jié)點的個數(shù)，則n0=_______。51、在含100個結(jié)點的完全二叉樹，葉子結(jié)點的個數(shù)為_______。52、將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列叫_____。53、若一棵滿二叉樹具有121個結(jié)點，則該樹的深度為_________。54、一個具有767個結(jié)點的完全二叉樹，其葉子結(jié)點個數(shù)為________。55、深度為90的滿二叉樹，第11層有________個結(jié)點。56、有100個結(jié)點的完全二叉樹，深度為________。57、設(shè)一棵二叉樹中度為2的結(jié)點10個，則該樹的葉子個數(shù)為________。58、若待散列的序列為(18,25,63,50,42,32,9)，散列函數(shù)為H(key)=key

MOD

9，與18發(fā)生沖突的元素有_____________個。59、具有3個2度結(jié)點和4個葉結(jié)點的二叉樹可含__________個1度結(jié)點。60、一棵具有５層滿二叉樹中節(jié)點總數(shù)為___________。61、一棵具有16個結(jié)點的完全二叉樹，對他按層編號，對于編號為7的結(jié)點，他的雙親結(jié)點及左右結(jié)點編號為______、______、_______。62、深度為k(設(shè)根的層數(shù)為1)的完全二叉樹至少有_______個結(jié)點,

至多有_______個結(jié)點。63、若要對某二叉排序樹進行遍歷，保證輸出所有結(jié)點的值序列按增序排列，應(yīng)對該二叉排序樹采用________遍歷法。64、在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24，需要進行______________次元素之間的比較。65、設(shè)有10個值，構(gòu)成哈夫曼樹，則該哈夫曼樹共有______個結(jié)點。66、從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的____________。67、關(guān)鍵字自身作為哈希函數(shù)，即H（k）=k，也可自身加上一個常數(shù)作為哈希函數(shù)，即H(k)=k+C這種構(gòu)造哈希函數(shù)的方式叫____________。68、對于一個圖G，若邊集合E（G）為無向邊的集合，則稱該圖為____________。69、對于一個圖G，若邊集合E（G）為有向邊的集合，則稱該圖為____________。70、對于有向圖，頂點的度分為入度和出度，以該頂點為終點的邊數(shù)目叫________；以該頂點為起點的邊數(shù)目叫_________。71、一個無向圖采用鄰接矩陣存儲方法，其鄰接矩陣一定是一個______________。72、有一個n個頂點的有向完全圖的弧數(shù)_____________。73、在無向圖中，若從頂點A到頂點B存在_________，則稱A與B之間是連通的。74、在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的___________倍。75、一個連通圖的生成樹是該圖的____________連通子圖。若這個連通圖有n個頂點,

則它的生成樹有__________條邊。76、無向圖的鄰接矩陣是一個_____________矩陣。77、假如從一無向圖的任意頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是_____

_______。78、若采用鄰接表的存儲結(jié)構(gòu)，則圖的廣度優(yōu)先搜索類似于二叉樹的____________遍歷。79、若圖的鄰接矩陣是對稱矩陣，則該圖一定是________________。80、從如圖所示的臨接矩陣可以看出，該圖共有______個頂點。假如是有向圖，該圖共有______條??；假如是無向圖，則共有________條邊。81、假如從一個頂點出發(fā)又回到該頂點，則此途徑叫做___________。82、一個具有個n頂點的無向圖中，要連通所有頂點至少需要________條邊。83、給定序列{100,

86,

48,

73,

35,

39,

42,

57,

66,

21},

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

則它一定_________堆。84、從未排序序列中選擇一個元素，該元素將當前參與排序的那些元素提成前后兩個部分，前一部分中所有元素都小于等于所選元素，后一部分中所有元素都大于或等于所選元素，而此時所選元素處在排序的最終位置。這種排序法稱為_____________排序法。85、折半搜索只適合用于___________________。86、結(jié)點關(guān)鍵字轉(zhuǎn)換為該結(jié)點存儲單元地址的函數(shù)H稱為_____________或叫__________。87、在索引查找中，一方面查找________，然后查找相應(yīng)的_________，整個索引查找的平均查找長度等于查找索引表的平均長度與查找相應(yīng)子表的平均查找長度的_______。三、選擇題：（

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

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

B存儲和抽象

C抱負和抽象

D抱負與邏輯（

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

。A先進先出

B后進先出

C先進后出

D隨意進出（

）3.將一棵有100個結(jié)點的完全二叉樹從上到下，從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號為49的結(jié)點的左孩子的編號為______。A.98

B.99

C.50

D.48(

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

)A.ABCDEF

B.ABECDFC.CDFBEA

D.CBDAEF（

）5.設(shè)有100個元素，用折半查找法進行查找時，最大比較次數(shù)是_____

。A.25

B.50

C.10

D.7（

）6.快速排序在_____情況下最易發(fā)揮其長處。A.被排序數(shù)據(jù)中具有多個相同排序碼

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

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

）7.由兩個棧共享一個向量空間的好處是______。

A減少存取時間,減少下溢發(fā)生的機率

B節(jié)省存儲空間,減少上溢發(fā)生的機率C減少存取時間,減少上溢發(fā)生的機率

D節(jié)省存儲空間,減少下溢發(fā)生的機率（

）8.某二叉樹的前序和后序序列正好相反，則該二叉樹一定是_____的二叉樹A空或者只有一個結(jié)點

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

D任一結(jié)點無右孩子（

）9.設(shè)散列表長m=14,散列函數(shù)H（K）=K％11，已知表中已有4個結(jié)點：r(15)=4;

r(38)=5;

r(61)=6;r(84)=7，其他地址為空，如用二次探測再散列解決沖突，關(guān)鍵字為49的結(jié)點地址是________。A8

B3

C5

D9（

）10.在具有n個項點有e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為________。A.e

B.2e

C.n2-e

D.n2-2e（

）11.圖的深度優(yōu)先遍歷類似于二叉樹的_______。A.先序遍歷

B.中序遍歷

C.后序遍歷

D.層次遍歷（

）12.設(shè)長度為n的鏈隊列用單循環(huán)鏈表表達，若只設(shè)頭指針，則入隊操作的時間復雜度為_______。A.

O(1)

B.

O(log2n)

C.

O(n)

D.

O(n2)（

）13.堆的形狀是一棵_______。A.二叉排序樹

B.滿二叉樹

C.完全二叉樹

D.平衡二叉樹（

）14.一個無向連連通圖的生成樹是具有該連通圖的所有項點的_______。A.極小連通子圖

B.極小子圖

C.極大連通子圖

D.極大子圖（

）15.一個序列中有10000個元素，若只想得到其中前10個最小元素，最佳采用_______方法A.快速排序

B.堆排序

C.插入排序

D.二路歸并排序（

）16.設(shè)單鏈表中結(jié)點的結(jié)構(gòu)為typedef

struct

node

{

file://鏈表結(jié)點定義ElemType

data；

file://數(shù)據(jù)struct

node

*

Link；

file://結(jié)點后繼指針}

ListNode；已知指針p所指結(jié)點不是尾結(jié)點，若在*p之后插入結(jié)點*s，則應(yīng)執(zhí)行下列哪一個操作______。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é)點的結(jié)構(gòu)為typedef

struct

node

{

file://鏈表結(jié)點定義ElemType

data；

file://數(shù)據(jù)struct

node

*

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ù)結(jié)構(gòu)

D.數(shù)據(jù)類型（

）19.在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并使鏈表仍然有序的時間復雜度是________A．O（1）

B.O（n）

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

）20．隊和棧的重要區(qū)別是________A.邏輯結(jié)構(gòu)不同

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

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

）21．鏈棧與順序棧相比，比較明顯的優(yōu)點是________A.插入操作更加方便

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

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

）22．在目的串T[0…n-1]=”xwxxyxy”中，對模式串p[0…m-1]=”xy”進行子串定位操作的結(jié)果_______A.0

B.2C.3

D.5（

）23．已知廣義表的表頭為A，表尾為(B,C)，則此廣義表為________A.（A,(B,C)）

B.（A,B,C）C.(A,B,C)

D.((

A,B,C))（

）24．二維數(shù)組A按行順序存儲，其中每個元素占1個存儲單元。若A[1][1]的存儲地址為420，A[3][3]的存儲地址為446，則A[5][5]的存儲地址為_______A.470

B.471C.472

D.473（

）25．二叉樹中第5層上的結(jié)點個數(shù)最多為________A.8

B.15C.16

D.32（

）26．假如某圖的鄰接矩陣是對角線元素均為零的上三角矩陣，則此圖是_______A.有向完全圖

B.連通圖C.強連通圖D.有向無環(huán)圖（

）27．對n個關(guān)鍵字的序列進行快速排序，平均情況下的空間復雜度為_______A.O（1）

B.O（logn）C.O（n）

D.O（nlogn）（

）28．對于哈希函數(shù)H(key)=key%13，被稱為同義詞的關(guān)鍵字是_______A．35和41

B.23和39C.15和44

D.25和51（

）29.

由權(quán)值分別為3,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)途徑長度為________。A、

24

B、

48

C、

72

D、

53（

）30．對包含N個元素的散列表進行檢索，平均檢索長度

________A、為

o(log2N)

B、為o(N)

C、不直接依賴于N

D、上述三者都不是（

）31.

向堆中插入一個元素的時間復雜度為________。A、

O(log2n)

B、

O(n)

C、

O(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)，而與結(jié)點個數(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）時，需要從前向后依次前移____個元素。A、n-i

B、n-i+1

C、n-i-1

D、i（

）35.設(shè)一個廣義表中結(jié)點的個數(shù)為n，則求廣義表深度算法的時間復雜度為____。A、O(1)

B、O(n)

C、O(n2)

D、O(log

2

n)（

）36.假定一個順序隊列的隊首和隊尾指針分別為f和r，則判斷隊空的條件為

____。A、f+1==r

B、r+1==f

C、f==0

D、f==r（

）37.從堆中刪除一個元素的時間復雜認為____。A、O(1)

B、O(log

2

n)

C、O(n)

D、O(nlog

2

n)（

）38．若需要運用形參直接訪問實參，則應(yīng)把形參變量說明為____參數(shù)。A.指針

B.引用

C.值

D.變量（

）39．在一個單鏈表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；（

）40．在一個順序隊列中，隊首指針指向隊首元素的____位置。A.前一個

B.后一個

C.當前

D.最后一個（

）41．向二叉搜索樹中插入一個元素時，其時間復雜度大體力____。A

O（1）

B

O（1og2n）C

O（n）

D

O（nlog2n）（

）42.算法指的是________A.計算機程序

B.解決問題的計算方法C.排序算法D.解決問題的有限運算序列（

）43.線性表采用鏈式存儲時，結(jié)點的存儲地址________A.必須是不連續(xù)的

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

）44.將長充為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為________A.O（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+1

B.

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

front=(front-1)%m

D.

front=(front+1)%m（

）47.如下陳述中對的的是________A.

串是一種特殊的線性表

B.

串的長度必須大于零C.

串中元素只能是字母

D.

空串就是空白串（

）48.若目的串的長充為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時，在最壞情況下的時間復雜度是________A.O（1）

B.O（n）C.O（n2）

D.O（n3）（

）49.一個非空廣義表的表頭________A.不也許是子表B.只能是子表C.只能是原子

D.可以是子表或原子（

）50.

從堆中刪除一個元素的時間復雜度為________。A、

O(1)

B、

O(n)

C、

O(log2n)

D、

O(nlog2n)（

）51.一棵度為3的樹中，度為3的結(jié)點個數(shù)為2，度為2的結(jié)點個數(shù)為1，則度為0的結(jié)點個數(shù)為________A.4

B.5C.6

D.7（

）52.

從二叉搜索樹中查找一個元素時，其時間復雜度大體為________。A、

O(n)

B、

O(1)

C、

O(log2n)

D、

O(n2)（

）53.

根據(jù)n個元素建立一棵二叉搜索樹時，其時間復雜度大體為________。A、

O(n)

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)查找表進行高效率查找的組織結(jié)構(gòu)是________A.有序表

B.分塊有序表C.二叉排序樹

D.線性鏈表（

）56.

若需要運用形參直接訪問實參，則應(yīng)把形參變量說明為________參數(shù)。

A

指針

B

引用

C

值

D

常量

（

）57.鏈式棧與順序棧相比，一個比較明顯的優(yōu)點是________。

A.

插入操作更加方便

B.

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

C.

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

D.

刪除操作更加方便

（

）58.設(shè)單鏈表中結(jié)點的結(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,

1

B.

2,

1,

3

C.

3,

1,

2

D.

1,

3,

2

（

）60.線性鏈表不具有的特點是________。

A.

隨機訪問

B.

不必事先估計所需存儲空間大小

C.

插入與刪除時不必移動元素

D.

所需空間與線性表長度成正比

（

）61．在稀疏矩陣的十字鏈接存儲中，每個列單鏈表中的結(jié)點都具有相同的_____。

Ａ．行號

Ｂ．列號

Ｃ．元素值

Ｄ．地址

（

）62.假定一個順序隊列的隊首和隊尾指針分別為front和rear，存放該隊列的數(shù)組長度為N，則判斷隊空的條件為________。

A．（front+1）%

N

==

rear

C．

front

==

0B．（rear+1）%

N

==

front

D．

front

==

rear（

）63．棧的插入和刪除操作在＿＿＿進行．

(Ａ)．棧頂

(Ｂ)．棧底(Ｃ)．任意位置

(Ｄ).指定位置

（

）64.

在一個順序循環(huán)隊列中，隊首指針指向隊首元素的________位置。

A.

后兩個

B.

后一個C.

當前

D.前一個

（

）65．下面算法的時間復雜度為＿＿。

int

f（int

n）{

if

（n＝＝0）return

1；

else

return

n＊f（n-1）；}

A．O(1)

B．O(n)

C．O(n2)

D．O(n!)（

）66.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的（①）以及它們之間的（②）和運算的學科

①Ａ、操作對象Ｂ、計算方法Ｃ、邏輯存儲Ｄ、數(shù)據(jù)映象②Ａ、結(jié)構(gòu)Ｂ、關(guān)系Ｃ、運算Ｄ、算法（

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

）68.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為________Ａ、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)Ｂ、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)Ｃ、線性結(jié)構(gòu)和非線性結(jié)構(gòu)Ｄ、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)（

）69.線性表的順序存儲結(jié)構(gòu)是一種_________的存儲結(jié)構(gòu)，線性表的鏈式存儲結(jié)構(gòu)是一種________的存儲結(jié)構(gòu)Ａ、隨機存取

Ｂ、順序存?。谩⑺饕嫒?/p>

Ｄ、HASH存?。?/p>

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

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

Ｃ、可讀性和文檔性Ｂ、對的性和簡明性

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

）71.計算機算法指的是（①），它必具有輸入、輸出和（②）等五個特性①Ａ、計算方法Ｂ、排序方法Ｃ、解決萊一問題的有限運算序列Ｄ、調(diào)度方法②Ａ、可執(zhí)行性、可移植性和可擴充性

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

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

）72.線性表若采用鏈表存儲結(jié)構(gòu)時，規(guī)定內(nèi)存中可用存儲單元的地址________Ａ、必須是連續(xù)的Ｂ、部分地址必須是連續(xù)的Ｃ、一定是不連續(xù)的Ｄ、連續(xù)不連續(xù)都可以（

）73.在以下的敘述中，對的的是__________Ａ、線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)

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

）74.

一個數(shù)組元素A[i]與________的表達等價。A、

*(A+i)

B、

A+i

C、

*A+i

D、

&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.下面程序段的時間復雜度為____________。

for(int

i=0;

i<m;

i++)

for(int

j=0;

j<n;

j++)

A[i][j]=i*j;A、

O(m2)

B、

O(n2)

C、

O(m*n)

D、

O(m+n)（

）78.

執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為____________。

for(int

i=1;

i<=n;

i++)

for(int

j=1;

j<=i;

j++)

S;A、

n2

B、

n2/2

C、

n(n+1)

D、

n(n+1)/2（

）79.

下面算法的時間復雜度為____________。

int

f(

unsigned

int

n

)

{

if

(

n==0

||

n==1

)

return

1;

else

return

n*f(n-1);

}A、

O(1)

B、

O(n)

C、

O(n2)

D、

O(n!)（

）80．在一個長度為n的順序存儲線性表中，向第i個元素(1≤i≤n+1)之前插入一個新元素時，需要從后向前依次后移

個元素。A、n-i

B、n-i+1

C、n-i-1

D、i（

）81．在一個長度為n的順序存儲線性表中，刪除第i個元素(1≤i≤n+1)時，需要從前向后依次前移_____個元素。A、n-i

B、n-i+1

C、n-i-1

D、i（

）82.在一個長度為n的線性表中順序查找值為x的元素時，查找時的平均查找長度（即x同元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為_____。A、n

B、n/2

C、(n+1)/2

D、(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;

C、p

=

q->next

;

q->next

=

p->next;B、p

=

q->next

;

q->next

=

p;

D、q->next

=

q->next->next;

q->next

=

q;（

）86.

在稀疏矩陣的帶行指針向量的鏈接存儲中，每個行單鏈表中的結(jié)點都具有相同的________。A、

行號

B、

列號

C、

元素值

D、

地址（

）87.

設(shè)一個廣義表中結(jié)點的個數(shù)為n，則求廣義表深度算法的時間復雜度為_______。A、

O(1)

B、

O(n)

C、

O(n2)

D、

O(log2n)（

）88．棧的插入與刪除操作在_____進行。A、棧頂

B、棧底

C、任意位置

D、指定位置（

）89．當運用大小為N的一維數(shù)組順序存儲一個棧時，假定用top==N表達?？眨瑒t向這個棧插入一個元素時，一方面應(yīng)執(zhí)行_____語句修改top指針。A、top++

B、top--

C、top=0

D、top（

）90．若讓元素1，2，3依次進棧，則出棧順序不也許出現(xiàn)_____種情況。A、3，2，1

B、2，1，3

C、3，1，2

D、1，3，2（

）91．在一個循環(huán)順序隊列中，隊首指針指向隊首元素的_____位置。A、前一個

B、后一個

C、當前

D、后面（

）92．當運用大小為N的一維數(shù)組順序存儲一個循環(huán)隊列時，該隊列的最大長度為_____。A、N-2

B、N-1

C、N

D、N+1（

）93．從一個循環(huán)順序隊列刪除元素時，一方面需要_____。A、前移一位隊首指針

B、后移一位隊首指針C、取出隊首指針所指位置上的元素

D、取出隊尾指針所指位置上的元素（

）94．假定一個循環(huán)順序隊列的隊首和隊尾指針分別為f和r，則判斷隊空的條件是_____。A、f+1==r

B、r+1==f

C、f==0

D、f==r（

）95．假定一個鏈隊的隊首和隊尾指針分別為front和rear，則判斷隊空的條件是_____。A、front==rear

B、front!=NULL

C、rear!=NULL

D、front==NULL四、應(yīng)用題：1、棧和隊列都是特殊線性表，其特殊性是什么？2、設(shè)有一順序隊列sq，容量為5，初始狀態(tài)sq.front=sq.rear=0，劃出作完下列操作的隊列及其頭尾指針變化狀態(tài)，若不能入隊，簡述理由后停止。1）d,e,b

入隊。2）d,e

出隊。3）

i,j

入隊。4）b

出隊。

5）n,o,p

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

s2,

s3,

s4,

s5,

s6依次進棧，假如6個元素的出棧順序為s2,

s3,

s4,

s6,

s5,

s1，則順序棧的容量至少應(yīng)為多少？4、將兩個棧存入數(shù)組V[1..m]中應(yīng)如何安排最佳?這時?？?、棧滿的條件是什么?5、已知稀疏矩陣如下：請寫出該稀疏矩陣三元組表達。6、廣義表A=（a,b,(c,d),(e,(f,g))）,求其長度，及深度。7、請畫出下面廣義表相應(yīng)的加入表頭結(jié)點的單鏈表表達，D(A(x,y,L(a,b))，B(z,A(x,y,L(a,b))))。8、一棵具有n個結(jié)點的抱負平衡二叉樹（即除離根最遠的最底層外其他各層都是滿的，最底層有若干結(jié)點）有多少層？若設(shè)根結(jié)點在第0層，則樹的高度h如何用n來表達（注意n也許為0）？9、設(shè)二叉樹后根遍歷為BAC，畫出所有也許的二叉樹。10、假設(shè)一棵二叉樹的層序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,請畫出該樹。11、有一個完全二叉樹按層次順序存放在一維數(shù)組中，如下所示：

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

18、有n個頂點的有向連通圖最多有多少條邊?最少有多少條邊？19、下圖中給出由7個頂點組成的無向圖。從頂點1出發(fā)，對它進行深度優(yōu)先遍歷得到的頂點序列是：進行廣度優(yōu)先遍歷得到的頂點序列是：20、什么是連通圖的生成樹？21、什么是哈夫曼（Huffman）樹？22、已知結(jié)點a,b,c,d及其權(quán)值寫出哈夫曼樹的構(gòu)造過程。

a

b

c

d

7

5

2

423、已知圖G={V

,

E}

V={

a,

b,

c,

d,

e

}

E={(a,

b),(b,

d),(c,

d),(d,

e),(e,

a),(a,

c)}畫出圖G，畫出圖G的鄰接表。24、考慮下圖：1）從頂點A出發(fā)，求它的深度優(yōu)先生成樹。2）從頂點E出發(fā)，求它的廣度優(yōu)先生成樹。3）根據(jù)普里姆（Prim）算法，求它的最小生成樹。

25、設(shè)有關(guān)鍵碼序列（Q，H，C，Y，Q，A，M，S，R，D，F(xiàn)，X），要按照關(guān)鍵碼值遞增的順序進行排序。若采用初始步長為4的Shell排序法，則一趟掃描的結(jié)果是：若采用以第一個元素為分界元素的快速排序法，則一趟掃描的結(jié)果是：26、一個對象序列的排序碼為{46，79，56，38，40，84}，采用快速排序以位于最左位置的對象為基準而得到的第一次劃分結(jié)果為：27、用二分法對一個長度為10的有序表進行查找，填寫查找每個元素需要的比較次數(shù)。

下標：

0

1

2

3

4

5

6

7

8

9

比較次數(shù)：28、若對序列(49,38,27,13,97,76,50,65)采用泡排序法(按照值的大小從小到大)進行排序，請分別在下表中寫出每一趟排序的結(jié)果。原始序列

49

38

27

13

97

76

50

65第1趟的結(jié)果第2趟的結(jié)果第3趟的結(jié)果第4趟的結(jié)果29、給出一組關(guān)鍵字：29，18，25，47，58，12，51，10，分別寫出按下列各種排序方法進行排序時的變化過程：1）歸并排序

每歸并一次書寫一個順序。2）快速排序

每劃分一次書寫一個順序。3）堆排序

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

9，并且采用鏈地址方法解決沖突，請畫出元素7,4,5,3,6,2,8,9,1依次插入該雜湊表以后，該雜湊表的狀態(tài)。32、已知二叉樹采用二叉鏈表存儲結(jié)構(gòu)，鏈結(jié)點的構(gòu)造為lchild

|

data

|

rchild

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

[1:M]，棧頂指針為top，請在算法的空缺處填入適當內(nèi)容，使之能正常工作。33、設(shè)有一個順序棧S，元素s1,

s2,

s3,

s4,

s5,

s6依次進棧，假如6個元素的出棧順序為s2,

s3,

s4,

s6,

s5,

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

{

55,

31,

11,

37,

46,

73,

63,

02,

07}

,

(1)

從空樹開始構(gòu)造平衡二叉搜索樹,

畫出每加入一個新結(jié)點時二叉樹的形態(tài)。若發(fā)生不平衡,

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

(2)

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

{

55,

31,

11,

37,

46,

73,

63,

02,

07

}請計算在二分法查找、二叉排序樹兩種的情況下等概率下查找成功的平均查找長度。36、

廣義表A=（a,b,(c,d),(e,(f,g))）,計算下面式子的值Head(Tail(Head(Tail(Tail(A)))))37、

下圖是用鄰接表存儲的圖，畫出此圖，并寫出從C點開始按深度優(yōu)先、廣度優(yōu)先遍歷該圖的結(jié)果。38、

用序列（46，88，45，39，70，58，101，10，66，34）建立一個排序二叉樹，畫出該樹，并求在等概率情況下查找成功的平均查找長度。39、

判斷下列序列是否為堆，假如不是請調(diào)整為堆，假如是請判斷是什么類型的堆（101，88，46，70，34，39，45，58，66，10）40、

假設(shè)一棵二叉樹的層序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,請畫出該樹。41、

找出所有滿足下列條件的二叉樹a)

它們在先序遍歷和中序遍歷時,得到的結(jié)點訪問序列相同；b)

它們在后序遍歷和中序遍歷時,得到的結(jié)點訪問序列相同；c)

它們在先序遍歷和后序遍歷時,得到的結(jié)點訪問序列相同。42、

已知L是無表頭結(jié)點的單鏈表,其中P結(jié)點既不是首元結(jié)點,也不是尾元結(jié)點。a)在P結(jié)點后插入S結(jié)點的語句序列是______b)在P結(jié)點前插入S結(jié)點的語句序列是______c)在表首插入S結(jié)點的語句序列是______d)在表尾插入S結(jié)點的語句序列是______(1)

P->next=S;(2)

P->next=P->next->.next;(3)

P->next=S->next;(4)

S->next=P->next;(5)

S->next=L;(6)

S->next=NIL;(7)

Q=P;(8)

WHILE

P->next<>Q

P=P->next;(9)

WHILE

P->next!=NULL

P=P->next;(10)

P=Q;(11)

P=L;(12)

L=S;(13)

L=P;43、

已知樹T的先序遍歷序列為ABCDEFGHIJKL，后序遍歷序列為CBEFDJIKLHGA，請畫出樹T。44、

對關(guān)鍵字序列（72，87，61，23，94，16，5，58）進行堆排序、快速排序、直接選擇排序，使之關(guān)鍵字遞增有序，請寫出每個排序的前三趟結(jié)果。45、

請畫出廣義表D的圖形表達D=(D,(a,b),((a,b),c),(

))46、

若一二叉樹有2度結(jié)點100個，則其葉結(jié)點有多少個？該二叉樹可以有多少個1度頂點？47、

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

p

，能否將

p

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

?

請對每一種鏈表作出判斷，若可以，寫出程序段；否則說明理由。單鏈表和單循環(huán)鏈表的結(jié)點結(jié)構(gòu)為date

next

雙向鏈表的結(jié)點結(jié)構(gòu)為prior

date

next

(1)

單鏈表

(2)

單循環(huán)鏈表

(3)

雙向鏈表

47、已知散列函數(shù)為H(key)=key%7，散列表長度為7(散列地址空間為0..6)，待散列序列為：(25，48，32，50，68)。規(guī)定：(1)根據(jù)以上條件構(gòu)造一散列表，并用線性探測法解決有關(guān)地址沖突；

(2)若要用該散列表查找元素68，給出所需的比較次數(shù)。48、已知一組鍵值序列為(38，64，73，52，40，37，56，43)，試采用快速排序法對該組序列作升序排序，并給出每一趟的排序結(jié)果。49、已知某二叉樹的順序存儲結(jié)構(gòu)如圖所示，試畫出該二叉樹。

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

55,

31,

11,

37,

46,

73,

63,

02,

07

}

(1)從空樹開始構(gòu)造平衡二叉搜索樹,

畫出每加入一個新結(jié)點時二叉樹

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

HEAD(p,h,w);2)

TAIL

(b,k,p,h);3)

HEAD

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

TAIL

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

HEAD（TAIL（（(a,b),(c,d)）））6)

TAIL（HEAD((a,b),(c,d))）52、畫出下列廣義表的圖形表達：1)

D（A（）），B（e），C（a,L(b,c,d)）2)

J1(J2,(J1,a,J3(J1)),J3(J1))53、完畢下列規(guī)定：1）

請畫出下列廣義表的存儲結(jié)構(gòu)（(((a),b)),(((),(d)),(e,f))）2）請寫出下面鏈表表達的廣義表54、一棵二叉樹如圖：1)

寫出對此樹進行中序、先序、后續(xù)遍歷時得到的結(jié)點序列。2)

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

*

key

%

11,并采用開放定址法解決沖突，隨機探測再散列的下一地址公式為：

d1=H

(key

)

di=(

di-1

+7

*

key

)

%

11

（I=2,3…..）試在0到10的散列地址空間中對關(guān)鍵字序列（22，41，53，46，30，13，01，67）畫出Hash表達意圖，并求在等概率情況下查找成功的平均查找長度。60、什么是內(nèi)部排序？什么是排序方法的穩(wěn)定性？說出你所學過的三個穩(wěn)定算法，一個不穩(wěn)定算法。61、何為隊列上溢？一般用什么方法解決，簡述之。62、載入下圖所示的有權(quán)圖G，回答下列問題：1）

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

給出圖的拓撲序列；3）

給出從結(jié)點v1到結(jié)點v8的最短途徑和關(guān)鍵途徑。63、對于下圖，請給出1）

相應(yīng)的鄰接矩陣，并給出A,B,C三個頂點的入度和出度；2）

鄰接表表達和逆鄰接表表達；3）

求其連同分量；64、對于下圖的樹，分別用孩子鏈表和孩子兄弟鏈表法畫出存儲結(jié)構(gòu)。65、對于下圖的樹，請分別用中序、先序的方法寫出其遍歷結(jié)果。

66、已知一個表{jan,feb,mar,apr,may,june,july,aug,sep}1)

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

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

68、設(shè)有一組關(guān)鍵字（17，13，153，29，35，21）需插入到表長為12的表中，請回答下列問題：1）

自己設(shè)計一個合理的散列函數(shù)2）

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

50，83，10請畫出插入個結(jié)點后樹的情況：71、令s=’aaab’,t=’abcaaa’,u=’abcaabbabcabaacbacbaaa’,分別求出他們的next值。72、請畫出下列二叉樹的中序線索化前趨鏈樹，后序線索化后繼鏈樹。73、將下列結(jié)點按輸入順序構(gòu)造一棵二叉平衡樹。{As74、試在如圖所示線索化的二叉樹中，查找指定結(jié)點E的后繼結(jié)點、C的前驅(qū)結(jié)點，并說明找到結(jié)果的因素。75、什么是數(shù)據(jù)結(jié)構(gòu)？76、試比較線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺陷。77、堆棧和隊列都是特殊線性表，其特殊性是什么？78、將兩個棧存入數(shù)組V[1..m]中應(yīng)如何安排最佳?這時?？諚M的條件是什么?79、內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m），提供應(yīng)兩個棧S1和S2使用，如何分派這部分存儲空間，使得對任一個棧，僅當這部分空間全滿時才發(fā)生上溢。80、給出數(shù)組

int

A[3…8，2…6]；當它在內(nèi)存中按行存放和按列存放時，分別寫出數(shù)組元素A[i,j]的地址計算公式（設(shè)每個元素占兩個存儲單元）。81、若一二叉樹有2度結(jié)點100個，則其葉結(jié)點有多少個？該二叉樹可以有多少個1度頂點？82、如圖所示的二叉樹完畢中序遍歷、后續(xù)遍歷、先序遍歷，并畫出后續(xù)線索化的二叉樹。83、將下圖轉(zhuǎn)換為二叉樹，對轉(zhuǎn)換后的二叉樹進行先根、中根、后根遍歷。84、有一組數(shù)值14、21、32、15、28，畫出哈夫曼樹的生成過程及最后結(jié)果。85、有n個頂點的有向連通圖最多有多少條邊?最少有多少條邊？86、什么是哈夫曼（Huffman）樹？87、已知圖G={V

,

E}

V={

a,

b,

c,

d,

e

}

E={(a,

b),(b,

d),(c,

d),(d,

e),(e,

a),(a,

c)}畫出圖G，畫出圖G的鄰接表。88、設(shè)一個有向圖為G=(V,E),其中V={v1,v2,v3,v4}，E={<v2,v1>,<v2,v3>,<v4,v1>,<v1,v4>,

<v4,v2>},畫出該有向圖，并求出每個結(jié)點的入度和出度，畫出相應(yīng)的鄰接矩陣、鄰接表和逆鄰接表。89、請給出下圖的鄰接矩陣和鄰接表。90、請畫出下圖中的極大連通子圖。91、對于如下圖請畫出其用prim和kruskal兩種不同算法生成最小生成樹的各條邊的并入順序。畫出最小生成樹。并寫出廣度優(yōu)先和深度優(yōu)先的結(jié)點遍歷順序。92、什么是靜態(tài)查找，什么時動態(tài)查找，什么叫平均查找長度。93、用序列（46，88，45，39，70，58，101，10，66，34）建立一個二叉排序樹，畫出該樹，并求在等概率情況下查找成功的平均查找長度。94、已知一個線性表（38，25，74，63，52，48），假定采用h(k)=k%7計算散列地址進行散列存儲，若引用線性探測的開放地址法解決沖突，則在該散列表上進行檢索的平均檢索長度為多少，若運用連地址法解決沖突，則在該散列表上進行檢索的平均查找長度為多少？設(shè)地址空間為9。請畫出算列表。96、已知長度為12的表：（Jan

,

Fed

,

Mar

,

Apr

,

May

,

Jun

,

Aug

,

Sep

,

Oct

,

Nov

,

Dec）按表中元素的順序，依次插入一棵初始為