數(shù)據(jù)結(jié)構(gòu)-21學(xué)習(xí)通超星期末考試答案章節(jié)答案2024年

數(shù)據(jù)結(jié)構(gòu)-21學(xué)習(xí)通超星期末考試章節(jié)答案2024年設(shè)有5000個無序的元素,希望用最快速度挑選出其中前10個最大的元素,在以下的排序方法中,采用()方法最好

答案:堆排序在下列算法中,()算法可能出現(xiàn)下列情況:在最后一趟開始之前,所有的元素都不在其最終的位置上。

答案:插入排序在文件“局部有序”或文件長度較小的情況下,最佳內(nèi)部排序方法是()

答案:直接插入排序?qū)τ涗浀年P(guān)鍵碼(50,26,38,80,70,90,8,30,40,20)進(jìn)行排序,各趟排序結(jié)束時的結(jié)果為:50,26,38,80,70,90,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序方法是()

答案:希爾排序一組記錄的關(guān)鍵碼為{46,79,56,38,40,84},則利用快速排序的方法,以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為()

答案:40,38,46,56,79,84下面給出的四種排序法中,()排序是不穩(wěn)定排序法。

答案:堆用某種排序方法對線性表{25,84,21,47,15,27,68,35,20)進(jìn)行排序時,無序序列的變化情況如下:258421471527683520201521254727683584152021253527476884152021252735476884則所采用的排序方法是()

答案:快速排序下面各種排序方法中,最好情況下時間復(fù)雜度為O(n)的是()

答案:直接插入排序從未排序的序列中依次取出一個元素與已排序序列中的元素依次進(jìn)行比較,然后將其放在排序序列的合適位置,該排序方法稱為()排序法。

答案:插入??就平均性能而言，目前最好的內(nèi)排序方法是_______排序。?

答案:快速??下列排序算法中，在每一趟都能選出一個元素放到其最終位置上，并且其時間性能受數(shù)據(jù)初始特性影響的是：_______。??

答案:快速排序??在下面的排序方法中，輔助空間為O（n）的是_______。??

答案:歸并排序??在下列排序算法中,哪一個算法的時間復(fù)雜度與初始排序無關(guān)_______。??

答案:直接選擇排序??下面給出的四種排序方法中，排序過程中的比較次數(shù)與排序方法無關(guān)的是_______。??

答案:選擇排序法??下列排序方法中，哪一個是穩(wěn)定的排序方法？_______。??

答案:二分法插入排序??下列排序算法中，其中_______是穩(wěn)定的。??

答案:歸并排序，冒泡排序??下面給出的四種排序法中_______排序法是不穩(wěn)定性排序法。??

答案:堆積???某內(nèi)排序方法的穩(wěn)定性是指_______。?

答案:以上都不對衡量查找算法效率的主要標(biāo)準(zhǔn)是()。

答案:平均查找長度如果要求一個線性表既能較快地查找,又能適應(yīng)動態(tài)變化的要求,可以采用()查找方法。

答案:分塊若采用鏈地址法構(gòu)造散列表,散列函數(shù)為H(key)=keyMOD17,這些鏈的鏈?zhǔn)字羔槝?gòu)成一個指針數(shù)組,數(shù)組的下標(biāo)范圍為(2)

答案:0至16下面關(guān)于哈希(Hash,雜湊)查找的說法正確的是()

答案:不存在特別好與壞的哈希函數(shù),要視情況而定設(shè)有一組記錄的關(guān)鍵字為{19,14,23,1,68,20,84,27,55,11,10,79},用鏈地址法構(gòu)造散列表,散列函數(shù)為H(key)=keyMOD13,散列地址為1的鏈中有()個記錄。

答案:4要進(jìn)行順序查找,則線性表(1)。

答案:既可以以順序方式存儲,也可以鏈?zhǔn)椒绞酱鎯?當(dāng)在一個有序的順序存儲表上查找一個數(shù)據(jù)時,即可用折半查找,也可用順序查找,但前者比后者的查找速度(

答案:不一定用折半查找表的元素的速度比用順序法()

答案:不能確定有一個有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100},當(dāng)折半查找值為82的結(jié)點時,()次比較后查找成功。

答案:4對線性表進(jìn)行折半查找時,要求線性表必須是()。

答案:以順序方式存儲,且結(jié)點按關(guān)鍵字有序排序查找表是以()為查找結(jié)構(gòu)的。

答案:集合哈希查找中k個關(guān)鍵字具有同一哈希值，若用線性探測法將這k個關(guān)鍵字對應(yīng)的記錄存入哈希表中，至少要進(jìn)行_______次探測。

答案:k(k+1)/2假定有k個關(guān)鍵字互為同義詞，若用線性探測法把這k個關(guān)鍵字存入散列表中，至少要進(jìn)行多少次探測？_______

答案:k（k+1）/2次設(shè)哈希表長為14，哈希函數(shù)是H(key)=key%11,表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個，現(xiàn)要將關(guān)鍵字為49的結(jié)點加到表中，用二次探測再散列法解決沖突，則放入的位置是_______。

答案:9下面關(guān)于哈希(Hash，雜湊)查找的說法正確的是_______。A．B．

C．D．

答案:不存在特別好與壞的哈希函數(shù)，要視情況而定要進(jìn)行順序查找，則線性表___(1)____；要進(jìn)行折半查詢，則線性表___(2)____；若表中元素個數(shù)為n,則順序查找的平均比較次數(shù)為___(3)____；折半查找的平均比較次數(shù)為___(4)____。

(1)(2)：A.必須以順序方式存儲；B.必須以鏈?zhǔn)椒绞酱鎯?；C.既可以以順序方式存儲，也可以鏈?zhǔn)椒绞酱鎯?；D.必須以順序方式存儲，且數(shù)據(jù)已按遞增或遞減順序排好；E.必須以鏈?zhǔn)椒绞酱鎯?，且?shù)據(jù)已按遞增或遞減的次序排好。(3)(4)：A.n

B.n/2C.n*n

D.n*n/2

E.log2nF.nlog2nG.(n+1)/2

H.log2(n+1)

答案:C/D/G/H二叉查找樹的查找效率與二叉樹的___(1)____有關(guān),在___(2)____時其查找效率最低。(1):

A.高度

B.結(jié)點的多少

C.樹型

D.結(jié)點的位置(2):

A.結(jié)點太多B.完全二叉樹

C.呈單枝樹

D.結(jié)點太復(fù)雜。

答案:樹型；呈單枝樹在等概率情況下,線性表的順序查找的平均查找長度ASL為___(1)____,有序表的折半查找的ASL為___(2)____,對靜態(tài)樹表,在最壞情況下,ASL為___(3)____,而當(dāng)它是一棵平衡樹時,ASL為___(4)____,在平衡樹上刪除一個結(jié)點后可以通過旋轉(zhuǎn)使其平衡,在最壞情況下需___(5)____次旋轉(zhuǎn)。供選擇的答案：(1)(2)(3)(4)(5):A.O(1)

B.O(log2n)C.O((log2n)2)D.O(nlog2n)

E.O(n)

答案:E/B/E/B/B下面關(guān)于二分（對半）查找的敘述正確的是_______。

答案:表必須有序，且表只能以順序方式存儲對線性表進(jìn)行二分（對半）查找時，要求線性表必須_______。

答案:以順序方式存儲,且數(shù)據(jù)元素有序一個無向圖有5個頂點、8條邊,則其生成樹將要去掉()條邊。

答案:4無向圖G=(V,E),其中:v={a,b,c,d,e,f,E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},對該圖進(jìn)行深度優(yōu)先遍歷,得到的頂點序列正確的是()。

答案:a,e,d,f,c,b無向圖頂點V的度是關(guān)聯(lián)于該頂點()的數(shù)目。

答案:邊用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時,通常采用()來實現(xiàn)算法。

答案:隊列用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時,通常采用()來實現(xiàn)算法。

答案:棧n個結(jié)點的完全有向圖含有邊的數(shù)目()。

答案:n*(n-1)要連通具有n個頂點的有向圖,至少需要()條邊。

答案:n設(shè)無向圖的頂點個數(shù)為n,則該圖最多有()條邊。

答案:n(n-1)/2圖中有關(guān)路徑的定義是()。

答案:由頂點和相鄰頂點序偶構(gòu)成的邊所形成的序列關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中_____。

答案:從源點到匯點的最長路徑在用鄰接表表示圖時，拓?fù)渑判蛩惴〞r間復(fù)雜度為_____。

答案:O(n＋e)求解最短路徑的Floyd算法的時間復(fù)雜度為_____。

答案:O（n*n*n）當(dāng)各邊上的權(quán)值_____時，BFS算法可用來解決單源最短路徑問題。

答案:均相等n個結(jié)點的完全有向圖含有邊的數(shù)目_____。

答案:n*（n－l）要連通具有n個頂點的有向圖，至少需要_____條邊。

答案:n設(shè)無向圖的頂點個數(shù)為n，則該圖最多有_____條邊。

答案:n(n-1)/21.圖中有關(guān)路徑的定義是_____。

答案:由頂點和相鄰頂點序偶構(gòu)成的邊所形成的序列任何一棵二叉樹的葉子結(jié)點在先序、中序、后序遍歷序列中的相對次序()。

答案:不發(fā)生改變某二又樹的后序遍歷序列為DABEC,中序遍歷序列為DEBAC,則先序遍歷序列為()。

答案:CEDBA具有35個結(jié)點的完全二叉樹的深度為()。

答案:6已知一棵完全二叉樹的結(jié)點總數(shù)為9個,則最后一層的結(jié)點數(shù)為()。

答案:2一個結(jié)點的子結(jié)點個數(shù)為該結(jié)點的_____

。

答案:度若已知一棵二叉樹的前序序列是BEFCGDH,中序序列是FEBGCHD,則它的后序序列必是____。

答案:FEGHDCB用5個權(quán)值{3,2,4,5,1}構(gòu)造的哈夫曼(Huffman)樹的帶權(quán)路徑長度是____

答案:33一棵含有n個結(jié)點的k叉樹,可能達(dá)到的最大深度為____,最小深度為____。

答案:n;2中序遍歷的遞歸算法平均空間復(fù)雜度為____。

答案:O(n設(shè)一棵完全二叉樹有700個結(jié)點,則共有____個葉子結(jié)點。

答案:350一棵具有257個結(jié)點的完全二叉樹,它的深度為____。

答案:9設(shè)一棵完全二叉樹具有1000個結(jié)點,則此完全二叉樹有____個葉子結(jié)點,有____個度為2的結(jié)點,有____個結(jié)點只有非空左子樹,有____個結(jié)點只有非空右子樹。

答案:500;499;1;0一棵深度為6的滿二叉樹有____個分支結(jié)點和____個葉子。

答案:31;32由3個結(jié)點所構(gòu)成的二叉樹有____種形態(tài)。

答案:5在下列存儲形式中，哪一個不是樹的存儲形式？_______。

答案:順序存儲表示法樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的_______。

答案:中序序列在完全二叉樹中,若一個結(jié)點沒有,則它必定是葉結(jié)點。()。

答案:左子結(jié)點把一棵樹轉(zhuǎn)換為二叉樹后,這棵二叉樹的形態(tài)是:()。

答案:唯一的具有n(n>0)個結(jié)點的完全二叉樹的深度為:()。

答案:?log2(n)?+1廣義表A=(a,b,(c,d),(e,(f,g))),則下面式子的值為_______。Head(Tail(Head(Tail(Tail(A)))))

答案:d廣義表(a,b,c,d,e)的表尾是()。

答案:(b,c,d,e)廣義表是線性表的推廣,它們之間的區(qū)別在于()。

答案:能否使用子表若StrIndex(S,T)表示求T在S中的位置的操作,則對于S="BeijingandNanjing”,T="jing",Strlndex(S.T)的結(jié)果為()。

答案:4以下論斷正確的是()。

答案:””是空串,””是空格串字符串‘a(chǎn)babaabab’的nextval為_______。

答案:(0,1,0,1,04,1,0,1)已知串S=‘a(chǎn)aab’,其Next數(shù)組值為_______。

答案:0123下面關(guān)于串的的敘述中，哪一個是不正確的？_______

答案:空串是由空格構(gòu)成的串棧和隊都是()。

答案:限制存取點的線性結(jié)構(gòu)存放循環(huán)隊列元素的數(shù)組data有10個元素,則data數(shù)組的下標(biāo)范圍是()。

答案:0~9同一隊列內(nèi)各元素的類型()。

答案:必須一致對于隊列操作數(shù)據(jù)的原則是()。

答案:先進(jìn)先出設(shè)有一個順序棧S,元素A,B,C,D,E,E,依次進(jìn)棧,如果6個元素出棧的順序是B,D,C,F,E,A,則棧的容量至少應(yīng)是()。

答案:3一個棧的入棧次序ABCDE,則棧的不可能的輸出序列是()。

答案:DCEAB如果以鏈表作為棧的存儲結(jié)構(gòu),則出棧操作時()。

答案:必須判別棧是否空輸入序列為ABC,可以變?yōu)镃BA時,經(jīng)過的棧操作為()。

答案:push,push,push,pop,pop,pop插入和刪除只能在一端進(jìn)行的線性表,稱為()。

答案:棧帶表頭結(jié)點的空循環(huán)雙向鏈表的長度等于____。

答案:0從循環(huán)隊列中刪除一個元素時,其操作是先____,后____。。

答案:移動隊首指針;取出元素向棧中壓入元素的操作是先____,后____。

答案:移動棧頂指針;存入元素在具有n個單元的循環(huán)隊列中,隊滿時共有____,個元素。

答案:n-1在一個循環(huán)隊列中,隊首指針指向隊首元素的____位置。

答案:前1個被限定為只能在表的一端進(jìn)行插入運(yùn)算,在表的另一端進(jìn)行刪除運(yùn)算的線性表是____。

答案:隊列棧是一種特殊的線性表,允許插入和刪除運(yùn)算的一端稱為____、不允許插入和刪除運(yùn)算的一端稱為____。

答案:棧頂;棧底棧和隊列都是____結(jié)構(gòu),對于棧只能在____插入和刪除元素;對于隊列只能在____插入和____刪除元素。

答案:線性;棧頂;隊尾;隊首為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續(xù)的內(nèi)存空間時,應(yīng)將兩棧的棧底分別設(shè)在這片內(nèi)存空間的兩端,這樣,只有當(dāng)時,才產(chǎn)生上溢。()。

答案:兩個棧的棧頂在達(dá)?？臻g的某一位置相遇數(shù)組Q[n]用來表示一個循環(huán)隊列,f為當(dāng)前隊列頭元素的前一位置,r為隊尾元素的位置,假定隊列中元素的個數(shù)小于n,計算隊列中元素的公式為()。

答案:(n+r-f)%n若已知一個棧的入棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pn,若p1=n,則pi為()。

答案:n-i+1循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為_______。

答案:rear=(rear+1)mod(m+1)用鏈接方式存儲的隊列，在進(jìn)行刪除運(yùn)算時_______。

答案:頭、尾指針可能都要修改若一個棧的輸入序列為1,2,3,…,n，輸出序列的第一個元素是i，則第j個輸出元素是_______。

答案:不確定的等概率情況下，在有n個結(jié)點的順序表上做插入結(jié)點運(yùn)算，需平均移動結(jié)點的數(shù)目為（）。

答案:n/2設(shè)p為指向單循環(huán)鏈表上某結(jié)點的指針,則*p的直接前驅(qū)()。

答案:查找時間復(fù)雜度為O(n)在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點,正確的操作是()。

答案:s->next=p->next;p->next=s;鏈表不具備的特點是()。

答案:隨機(jī)訪問在順序表中,只要知道(),就可以求出任意一個結(jié)點的存儲地址。

答案:基地址和結(jié)點大小在有n個結(jié)點的順序表上做插入、刪除結(jié)點運(yùn)算的時間復(fù)雜度為()。

答案:O(n)在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p,需找到它的____,其時間復(fù)雜度為____。

答案:前驅(qū)結(jié)點的地址;O(n在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由____指示。

答案:其直接前驅(qū)結(jié)點的鏈域的值順序表中邏輯上相鄰的元素的物理位置____相鄰。單鏈表中邏輯上相鄰的元素的物理位置____相鄰。

答案:必定;不一定在順序表中訪問任意一結(jié)點的時間復(fù)雜度均為____,因此,順序表也稱為____的數(shù)據(jù)結(jié)構(gòu)。

答案:O(1;隨機(jī)存取向一個長度為n的向量中刪除第i個元素(1≤i≤n)時,需向前移動____個元素。

答案:n-i向一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時,需向后移動____個元素。

答案:n-i+1線性表中結(jié)點的集合是____、的,結(jié)點間的關(guān)系是____的。

答案:有限;一對一在順序表中插入或刪除一個元素,需要平均移動表中____元素,具體移動的元素個數(shù)與____有關(guān)。

答案:一半;表長和該元素在表中的位置鏈表是一種采用存儲結(jié)構(gòu)存儲的線性表()。

答案:鏈?zhǔn)芥溄哟鎯Φ拇鎯Y(jié)構(gòu)所占存儲空間:()。

答案:分兩部分,一部分存放結(jié)點值,另一部分存放表示結(jié)點間關(guān)系的指針線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時,要求內(nèi)存中可用存儲單元的地址:()。

答案:連續(xù)或不連續(xù)都可以數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時,物理地址與邏輯地址相同并且是連續(xù)的,稱之為:()。

答案:順序存儲結(jié)構(gòu)鏈接存儲的存儲結(jié)構(gòu)所占存儲空間_______。

答案:分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為_______。

答案:順序存儲結(jié)構(gòu)線性表的鏈接存儲結(jié)構(gòu)是一種_______的存儲結(jié)構(gòu)。

答案:順序存取設(shè)有以下說明語句，則下面的敘述不正確的是（）。structstu{inta;floatb;}stutype;

答案:stutype是用戶定義的結(jié)構(gòu)體類型名設(shè)int類型變量占用四個字節(jié)，若有定義int

x[10]={0,2,4}；則數(shù)組x在內(nèi)存中所占字節(jié)數(shù)是（）。

答案:40數(shù)組定義為，int

a[11][11]；則數(shù)組a的數(shù)組元素個數(shù)為（）。

答案:121若有說明：int

a[3][4]；則對a數(shù)組元素的正確引用是（）。

答案:a[1+1][0]分析下面程序段的時間復(fù)雜度。i=1;while(i<=n)i=i*3;

答案:O(log3n)分析下面程序段的時間復(fù)雜度。for(i=0;i答案:O(m*n)寫出下列程序段的運(yùn)行結(jié)果。main(){SeqQueueQ;charx,y;X='E';y='C';InitQueue(&Q);EnQueue(&Q,'H');EnQueue(&Q,'R');EnQueue(&Q,y);DeQueue(&Q,&x);EnQueue(&Q,x);DeQueue(&Q,&x);EnQueue(&Q,'A');while(!EmptyQueue(&Q))

{

DeQueue(&Q,&y);

printf("sc",y);

}

printf("gc\n",x);}

答案:CHAR設(shè)循環(huán)隊列的容量為40(序號從0到39),現(xiàn)經(jīng)過一系列的入隊和出隊運(yùn)算后,有①front=11,rear=19;②front=19,rear=11;問在這兩種情況下,循環(huán)隊列中各有元素多少個?

答案:用隊列長度計算公式:(N+r-f)%N①L=(40+19-11)%40=8②L=(40+11-19)%40=32寫出下列程序段的運(yùn)行結(jié)果。main(){SeqStackS;charx,y;InitStack(&S);x='C';y='K';Push(&S,x);Push(&S,'A');Push(&S,y);Pop(&S,&x);Push(&S,'T');Push(&S,x);Pop(&S,&x);Push(&S,'S');while(!EmptyStack(&S)){

Pop(&S,&y);

printf("%c",y);}printf("%c\n",x);}

答案:STACK設(shè)有編號為1,2,3,4的四輛列車,順序進(jìn)入一個棧式結(jié)構(gòu)的車站,具體寫出這四輛列車開出車站的所有可能的順序。

答案:①全進(jìn)之后再出情況,只有1種:4,3,2,1②進(jìn)3個之后再出的情況,有3種,3,4,2,13,2,4,13,2,1,4③進(jìn)2個之后再出的情況,有5種,2,4,3,12,3,4,12,1,3,42,1,4,3④進(jìn)1個之后再出的情況,有5種,1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3分析下面程序段的時間復(fù)雜度。i=1;while(i<=n)

i=i*5;

答案:O(log5n)分析以下程序段的時間復(fù)雜度

i=s=0;

while(s答案:O()分析以下程序段的時間復(fù)雜度for(i=1;i答案:O()順序存儲方式只能用于存儲線性結(jié)構(gòu)。

答案:錯如果一個串中所有的字母均在另一個串中出現(xiàn),則說明前者是后者的子串。

答案:錯在順序存儲結(jié)構(gòu)中,串的插入算法是非常方便的。

答案:錯在隊列中允許刪除的一端稱為隊頭。

答案:對棧一定是順序存儲的線性結(jié)構(gòu)。

答案:錯棧和隊列都是線性結(jié)構(gòu)。

答案:對在C語言中設(shè)順序棧的長度為MAXLEN,則top=MAXLEN時表示隊滿。

答案:錯在鏈隊列上進(jìn)行出隊操作時,會改變front指針的值。

答案:錯設(shè)S=“A:/Mary.doc”，則strlen(s)=____。

答案:11鏈隊列LQ為空時,LQ->front->next=____。

答案:NULL;null;Null/star3/origin/1a07bb6406e5a27be2013ead398fa8fd.png

答案:s->next=p->next;;p->next=s;設(shè)S=“A:/doc/Mary.doc”，則“c”的字符定位的位置為____。

答案:6數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的____結(jié)構(gòu)、數(shù)據(jù)的____結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算三個方面的內(nèi)容。

答案:邏輯;存儲;物理非循環(huán)順序隊列初始化后,front=rear=____。

答案:-1在一個鏈隊列中,若隊首指針與隊尾指針的值相同,則表示該隊列為____。

答案:空在空串和空格串中,長度為0的是____.

答案:空串完成順序表的刪除操作算法。defineMAXLEN100

/*定義常量MAXLEN為100表示存儲空間總量*/typedefintDataType;/*定義DataType為int類型*/typedefstruct{

/*順序表存儲類型*/dataTypedata[MAXLEN];/*存放線性表的數(shù)組*/intLength;

/*Length是順序表的長度*/}seqList;seqListL;

/*定義一個順序表L*/intDelElem(SeqList*L,inti,DataType*x){/*在順序表L中刪除第i位元素函數(shù)*/

......*x=L->data[i-1];

/*用指針變量*x返回刪除的元素值*/for(j=i;jLength;j++)

___________;

/*結(jié)點移動*/_______________;

/*順序表長度減1*/return1;

/*刪除成功，返回*/}

答案:L->data[j-1]=L->data[j];L->Length--設(shè)目標(biāo)T=”abccdcdccbaa”，模式P=“dc”，則第____次匹配成功。

答案:5在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到它的____(前驅(qū)/后繼)結(jié)點的地址，

答案:前驅(qū)向一個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動____個元素。

答案:n-i從一個棧頂指針為top的鏈棧中刪除一個結(jié)點(數(shù)據(jù)域為data,指針域為next)時,用x保存被刪除的結(jié)點,完成刪除操作語句。

x=top->data;

//保存被刪除的結(jié)點___________;

//刪除棧頂結(jié)點/

答案:top=top->next在具有n個單元的循環(huán)隊列中，隊滿時共有_____個元素

答案:n-1一個棧的輸入序列是12345，請列明首出數(shù)字為4的可能的輸出序列4_______、4_______、4_______、4_______。

答案:5321;3521;3251;3215有一個二維數(shù)組A，行下標(biāo)的范圍是0到8，列下標(biāo)的范圍是1到5，每個數(shù)組元素用相鄰的4個字節(jié)存儲。存儲器按字節(jié)編址。假設(shè)存儲數(shù)組元素A[0,1]的第一個字節(jié)的地址是0。存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是_______。若按行存儲，則A[3,5]和A[5,3]的第一個字節(jié)的地址分別是_______和_______。若按列存儲，則A[3,5]和A[5,3]的第一個字節(jié)的地址分別是_______和_______。

答案:176;76;108;156;92廣義表(a,b,c,d,e)的表頭是________,

表尾是____________.

答案:a;(b,c,d,e若SubString(Sub,S,pos,len)表示用Sub返回串S的第pos個字符起長度為len的子串的操作,則對于S="DataStructure",SubString(Sub,S,6,3)的結(jié)果為(

)。

答案:"Str"對于隊列操作數(shù)據(jù)的原則是(

)。

答案:先進(jìn)先出計算機(jī)算法指的是:(

)。

答案:解決問題的有限運(yùn)算序列若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列,且當(dāng)前front和rear的值分別為3和0,當(dāng)從隊列中刪除一個元素,再加入兩個元素后,front和rear的值分別為(

)。

答案:4和2設(shè)鏈棧中結(jié)點的結(jié)構(gòu):data為數(shù)據(jù)域,next為指針域,且top是棧頂指針。若想在鏈棧的棧頂插入一個由指針s所指的結(jié)點,則應(yīng)執(zhí)行下列(

)操作。

答案:s->next=top;top=s;算法分析的目的是:(

)。

答案:分析算法的效率以求改進(jìn)下面不正確的字符串常量是(

)。

答案:'abc'設(shè)串S1="ABCDEFG",S2="PQRST",則ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的結(jié)果串為(

)。

答案:BCDEFEF串是一種特殊的線性表，其特殊性體現(xiàn)在:(

)

答案:數(shù)據(jù)元素是一個字符數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時,物理地址與邏輯地址相同并且是連續(xù)的,稱之為:(

)。

答案:順序存儲結(jié)構(gòu)順序棧存儲空間的實現(xiàn)使用(

)存儲棧元素。

答案:數(shù)組判定一個非循環(huán)順序隊列QU（最多元素為m）為滿隊列的條件是（

）

答案:QU->rear==m－1隊列是限定在(

)進(jìn)行操作的線性表。

答案:端點最大容量為n的循環(huán)隊列,隊尾指針是rear,隊頭是front,則隊滿的條件是(

)。

答案:(rear+1)%n==front以下不能正確進(jìn)行字符串賦初值的語句是(

)。

答案:charstr[5]="good!";設(shè)有一個字符串S="abcde“,問該串的子串總數(shù)為(

)。

答案:16設(shè)有一個字符串S="WelcometoNanjing!",問該串的長度為(

)。

答案:19在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O(1)的操作是:(

)。

答案:訪問第i個結(jié)點(1≤i≤n)和求第i個結(jié)點的直接前驅(qū)(2≤i≤n)判定一個棧ST(最多元素為m0)為空的條件是(

)。

答案:ST->top=0棧和隊都是(

)。

答案:限制存取點的線性結(jié)構(gòu)最大容量為n的循環(huán)隊列,隊尾指針是rear,隊頭是front,則隊空的條件是(

)。

答案:rear==front數(shù)據(jù)結(jié)構(gòu)中,與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的（

）結(jié)構(gòu)。

答案:邏輯4個元素按A,B,C,D順序進(jìn)S棧,執(zhí)行兩次Pop(S,x)運(yùn)算后,x的值是____.

答案:B若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’,執(zhí)行concat(replace(S1,substr(S1,5,length(S3)),S3),substr(S4,index(S2,‘8’),3))其結(jié)果為_______

答案:ABCD;123向一個有30個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（

）個元素。

答案:15chara[10];不能將字符串"abc"存儲在數(shù)組中的是(

)。

答案:a="abc";二叉排序樹的查找效率與二叉樹的(1)有關(guān)。

答案:樹型順序查找法適合于存儲結(jié)構(gòu)為()的線性表。

答案:順序存儲或是鏈?zhǔn)酱鎯σM(jìn)行順序查找,則線性表(

)。

答案:既可以以順序方式存儲,也可以鏈?zhǔn)椒绞酱鎯?二叉查找（排序）樹在___(2)____時其查找效率最低。

答案:呈單枝樹當(dāng)采用分快查找時，數(shù)據(jù)的組織方式為_______。

答案:數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大(或最小)的數(shù)據(jù)組成索引塊下面關(guān)于哈希(Hash，雜湊)查找的說法正確的是_______。

答案:不存在特別好與壞的哈希函數(shù)，要視情況而定二叉查找（排序）樹的查找效率與二叉樹的___(1)____有關(guān),

答案:樹型有序表的折半查找的時間復(fù)雜度為___(2)____,

答案:O(log2

n

)若采用鏈地址法構(gòu)造散列表,散列函數(shù)為H(key)=keyMOD17,則需(1)個鏈表。

答案:17要進(jìn)行折半（二分）查詢,則線性表(

)。

答案:必須以順序方式存儲,且結(jié)點按關(guān)鍵字有序排序(數(shù)據(jù)已按遞增或遞減順序排好);在等概率情況下,線性表的順序查找的時間復(fù)雜度為_______,

答案:O(n)若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為_______。

答案:(n+1)/2若線性表中元素個數(shù)為n,則折半查找的平均比較次數(shù)為_______。

答案:log2

(n+1)對下列四種排序方法，在排序中關(guān)鍵字比較次數(shù)同記錄初始排列無關(guān)的是_______。??

答案:歸并排序;直接選擇??排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是_______排序法。??

答案:快速;冒泡對初始狀態(tài)為遞增序列的表按遞增順序排序，最費(fèi)時間的是_______算法。

答案:快速排序?qū)Τ跏紶顟B(tài)為遞增序列的表按遞增順序排序，最省時間的是_______算法，

答案:插入排序快速排序方法在()情況下最不利于發(fā)揮其長處。

答案:要排序的數(shù)據(jù)已基本有序??下列排序算法中，在待排序數(shù)據(jù)已有序時，花費(fèi)時間反而最多的是_______排序。??

答案:快速??穩(wěn)定的排序方法是_______。??

答案:折半插入排序和起泡排序在順序表的第i個位置前插入一個元素x,其結(jié)點結(jié)構(gòu)包括元素數(shù)組elem、長度變量length;請完成算法.StatusListInsert_sq(SqList&l,inti,elemtypex){if(i<0||i>l.length)return(ERROR);if(l.length==MAXSIZE)return(OVERFLOW);for(j=l.length;j>=i;j--)①;l.elem[j]=x;②;return(OK);}

答案:l.elem[j]=l.elem[j-1];l.length++;寫出下列程序段的輸出結(jié)果（隊列中的元素類型QElemType為char）。voidmain(){QueueQ;InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);}

答案:char數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映像

答案:對廣義表組成的元素可以是不同形式的元素。

答案:對兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機(jī)會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。

答案:對順序表結(jié)構(gòu)適宜于進(jìn)行順序存取,而鏈表適宜于進(jìn)行隨機(jī)存取。

答案:錯有向圖不能進(jìn)行廣度優(yōu)先遍歷。

答案:錯樹結(jié)構(gòu)中的每個結(jié)點最多只有一個直接前驅(qū)。

答案:對線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。

答案:錯隊列是限制在兩端進(jìn)行操作的線性表。

答案:對算法分析的目的是找出數(shù)據(jù)結(jié)構(gòu)的合理性。

答案:錯數(shù)據(jù)的運(yùn)算最常用的有5種,它們分別是____、____、____、____和排序。

答案:插入;刪除;修改;查找廣義表A=(a,b,(c,d),(e,(f,g))),則GetHead(GetTail(GetHead(GetTail(GetTail(A)))))=________.

答案:d在隊列中,允許插入的一端稱為____。

答案:隊尾圖形結(jié)構(gòu)中元素之間存在____關(guān)系。

答案:多對多設(shè)數(shù)組a[1…50，1…80]的基地址為2000，每個元素占2個存儲單元。（1）若以行序為主序順序存儲，則元素a[45][68]的存儲地址為________.（2）若以列序為主序順序存儲，則元素a[45][68]的存儲地址為________.

答案:9336;8890在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到它的____(前驅(qū)/后繼)結(jié)點的地址，其時間復(fù)雜度為O(____)。

答案:前驅(qū);n兩個串相等是指兩個串長度相等,且對應(yīng)位置的____相同.

答案:字符字符串按存儲方式可以分為:順序存儲、鏈接存儲和____.

答案:堆分配存儲算法分析的兩個主要方面是:()。

答案:空間復(fù)雜性和時間復(fù)雜性單鏈表的存儲密度()

答案:小于1;設(shè)鏈棧中結(jié)點的結(jié)構(gòu):data為數(shù)據(jù)域,next為指針域,且top是棧頂指針。若想在鏈棧的棧頂插入一個由指針s所指的結(jié)點,則應(yīng)執(zhí)行下列()操作。

答案:s->next=top;top=s;下面關(guān)于求關(guān)鍵路徑的說法不正確的是_____。

答案:一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與數(shù)據(jù)的基本單位是()。

答案:數(shù)據(jù)元素以下論述正確的是()。

答案:空串是零個字符的串設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作：

答案:模式匹配/download/53fa9d815370cd3da0264065

答案:i(i-1)/2+j不含任何結(jié)點的空樹:()。

答案:是一棵樹也是一棵二叉樹已知廣義表L=((x,y,z)，a，(u，t，w))，從L表中取出原子項t的運(yùn)算是_______。

答案:head(tail(head(tail(tail(L))))要進(jìn)行折半查詢,則線性表(2)。

答案:必須以順序方式存儲,且數(shù)據(jù)已按遞增或遞減順序排好;二叉排序樹在(2)時其查找效率最低。

答案:呈單枝樹若采用鏈地址法構(gòu)造散列表，散列函數(shù)為H（key）=keyMOD17，則需(（1）A)個鏈表。這些鏈的鏈?zhǔn)字羔槝?gòu)成一個指針數(shù)組，數(shù)組的下標(biāo)范圍為_______。

（1）A．17

B.13

C.16

D.任意（2）A．0至17

B.1至17

C.0至16

D.1至16

答案:A/C順序查找法適用于查找順序存儲或鏈?zhǔn)酱鎯Φ木€性表，平均比較次數(shù)為___(1)____,二分法查找只適用于查找順序存儲的有序表，平均比較次數(shù)為___(2)____。在此假定N為線性表中結(jié)點數(shù)，且每次查找都是成功的。

答案:logN;N/2對N個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為_______。

答案:(N+1)/2一個有n個結(jié)點的圖，最少有1個連通分量，最多有(）個連通分量。

答案:n在一個無向圖中,所有頂點的度數(shù)之和等于所有邊數(shù)()倍,在一個有向圖中,所有頂點的入度之和等于所有頂點出度之和的1倍。

答案:2一個n個頂點的連通無向圖,其邊的個數(shù)至少為()。

答案:n-1下列關(guān)于AOE網(wǎng)的敘述中，不正確的是_____。

答案:任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成（1）求從指定源點到其余各頂點的迪杰斯特拉（Dijkstra）最短路徑算法中弧上權(quán)不能為負(fù)的原因是在實際應(yīng)用中無意義；

（2）利用Dijkstra求每一對不同頂點之間的最短路徑的算法時間是O(n3)；（圖用鄰接矩陣表示）

（3）Floyd求每對不同頂點對的算法中允許弧上的權(quán)為負(fù)，但不能有權(quán)和為負(fù)的回路。

上面不正確的是_____。

答案:(1),(2),(3)在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)_____倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的_____倍。

答案:2;1一個n個頂點的連通無向圖，其邊的個數(shù)至少為_____。

答案:n-1A、B為一棵二叉樹上的兩個葉子結(jié)點,在中序遍歷時,A在B前的條件是()。

答案:A在B的左方在一棵度為3的樹中,度為3的結(jié)點數(shù)為2個,度為2的結(jié)點數(shù)為1個,度為1的結(jié)點數(shù)為2個,那么度為0的結(jié)點數(shù)有()個。

答案:6樹最適合用來表示()。

答案:元素之間具有分支層次關(guān)系的數(shù)據(jù)在下列存儲形式中,哪一種不是樹的存儲形式()。

答案:順序存儲表示法在完全二叉樹中,如果一個結(jié)點是葉子結(jié)點,則它沒有()。

答案:左、右孩子結(jié)點設(shè)有一棵二叉樹,其先序遍歷序列是:ABCDEFG,中序遍歷序列是:CBAEDFG,則該二叉樹的后序遍歷序列是()。

答案:CBEGFDA二叉樹的先序遍歷序列為ABC的不同二叉樹有()種形態(tài)。

答案:5在一棵二叉樹上第3層上的結(jié)點數(shù)最多為()。

答案:4假設(shè)在一棵二叉樹中,雙分支結(jié)點數(shù)為15,單分支結(jié)點數(shù)為30個,則葉子結(jié)點數(shù)為()個。

答案:16由樹轉(zhuǎn)換成的二叉樹里,一個結(jié)點N的左子女是N在原樹里對應(yīng)結(jié)點的,()。

答案:最左子結(jié)點由3個結(jié)點可以構(gòu)造出多少種不同的二叉樹？_______。

答案:5由3個結(jié)點可以構(gòu)造出多少種不同的有向樹？_______。

答案:2如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的后序就是T2中結(jié)點的_______。

答案:中序設(shè)F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有_______個。

答案:n+1已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為_______。

答案:CBEFDA一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是_______。

答案:ABCDEFG若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用_______遍歷方法最合適。

答案:后序?qū)Χ鏄涞慕Y(jié)點從1開始進(jìn)行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用_______次序的遍歷實現(xiàn)編號。

答案:后序在下述結(jié)論中，正確的是_______①只有一個結(jié)點的二叉樹的度為0;②二叉樹的度為2;③二叉樹的左右子樹可任意交換;④深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。

答案:①④設(shè)串S1="ABCDEFG",S2="PQRST",則ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的結(jié)果串為()。

答案:BCDEFEFS1="Good",S2="Morming”,執(zhí)行串連接函數(shù)ConcatStr(S1,S2)后的結(jié)果為()。

答案:"GoodMorning"S=”morning”,執(zhí)行求子串函數(shù)SubStr(S,2,2)后的結(jié)果為()。

答案:"or"S1="good",S2="morning",執(zhí)行函數(shù)SubStr(S2,4,LenStr(S1))后的結(jié)果為()。

答案:"ning"若SubString(Sub,S,pos,len)表示用Sub返回串S的第pos個字符起長度為len的子串的操作,則對于S="DataStructure",SubString(Sub,S,6,3)的結(jié)果為()。

答案:"Str"串的模式匹配是指()。

答案:找某子串在主串中第一次出現(xiàn)的第一個字符位置設(shè)有兩個串S1和S2,則StrCompare(S1,S2)運(yùn)算稱做()。

答案:串比較某串的長度小于一個常數(shù),則采用()存儲方式最節(jié)省空間。

答案:順序兩個字符串相等的條件是()。

答案:兩串的長度相等,并且對應(yīng)位置上的字符相同設(shè)有一個字符串S="abcdefgh",問該串的最大子串個數(shù)為()。

答案:37設(shè)有一個字符串S="WelcometoShenyang!",問該串的長度為()。

答案:20若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列,且當(dāng)前front和rear的值分別為3和0,當(dāng)從隊列中刪除一個元素,再加入兩個元素后,front和rear的值分別為()。

答案:4和29.循環(huán)隊列占用的空間()。

答案:必須連續(xù)隊列中的元素個數(shù)是()。

答案:可變的向順序棧中壓入元素時,()。

答案:先移動棧頂指針,后存入元素順序棧存儲空間的實現(xiàn)使用()存儲棧元素。

答案:數(shù)組判定一個隊列QU(最多元素為m0)為滿隊列的條件是()。

答案:QU->rear-QU->front==m0棧中元素的進(jìn)出原則是()。

答案:后進(jìn)先出用單鏈表表示的鏈?zhǔn)疥犃械年狀^在鏈表的_______位置。

答案:鏈頭若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和fr