算法與數(shù)據(jù)結(jié)構(gòu)常見考題筆試題

二、填空題：1、《數(shù)據(jù)結(jié)構(gòu)》課程討論的主要內(nèi)容是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和___運(yùn)算___________。2、數(shù)據(jù)結(jié)構(gòu)算法中，通常用時間復(fù)雜度和____空間復(fù)雜度______________兩種方法衡量其效率。3、一個算法一該具有__有窮性____,__確定性____,__可行性__,___輸入___和_輸出___這五種特性。4、若頻繁地對線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采用_鏈?zhǔn)絖__________存儲結(jié)構(gòu)。5、在非空線性表中除第一個元素外，集合中每個數(shù)據(jù)元素只有一個_直接前驅(qū)______；除最后一個元素之外，集合中每個數(shù)據(jù)元素均只有一個___直接_后繼_____。6、線性表中的每個結(jié)點(diǎn)最多有__一個_直接___前驅(qū)和______一個直接___后繼。7、____循環(huán)__鏈表從任何一個結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)。8、鏈?zhǔn)酱鎯Y(jié)構(gòu)中的結(jié)點(diǎn)包含__指針__________域，________數(shù)據(jù)_______域。9、在雙向鏈表中，每個結(jié)點(diǎn)含有兩個指針域，一個指向___前驅(qū)__結(jié)點(diǎn)，另一個指向__后繼______結(jié)點(diǎn)。10、某帶頭結(jié)點(diǎn)的單鏈表的頭指針head，判定該單鏈表非空的條件__head->next!=NULL____________。11、在雙向鏈表中，每個結(jié)點(diǎn)含有兩個指針域，一個指向前驅(qū)結(jié)點(diǎn)，另一個指向后續(xù)結(jié)點(diǎn)。12、已知指針p指向單鏈表中某個結(jié)點(diǎn)，則語句p->next=p->next->next的作用__刪除p的后繼結(jié)點(diǎn)_。13、已知在結(jié)點(diǎn)個數(shù)大于1的單鏈表中，指針p指向某個結(jié)點(diǎn)，則下列程序段結(jié)束時，指針q指向*p的____后繼_________結(jié)點(diǎn)。q=p;while(q->next!=p)q=q->next;14、若要在單鏈表結(jié)點(diǎn)*P后插入一結(jié)點(diǎn)*S，執(zhí)行的語句_p->next=s->next;p->next=s_____。15、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)地址空間可以_不連續(xù)_，而向量存儲必須是地址空間__連續(xù)____。16、棧結(jié)構(gòu)允許進(jìn)行刪除操作的一端為_棧頂__。17、在棧的順序?qū)崿F(xiàn)中，棧頂指針top，棧為空條件__top=-1____________。18、對于單鏈表形式的隊列，其空隊列的F指針和R指針都等于__頭結(jié)點(diǎn)__________。19、若數(shù)組s[0..n-1]為兩個棧s1和s2的共用存儲空間，僅當(dāng)s[0..n-1]全滿時，各棧才不能進(jìn)行棧操作，則為這兩個棧分配空間的最佳方案是：s1和s2的棧頂指針的初值分別為s[0],s[n-1]__。20、允許在線性表的一端插入,另一端進(jìn)行刪除操作的線性表稱為_隊列______。插入的一端為_對尾_____,刪除的一端為_對頭_____。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，則該隊列的當(dāng)前長度__________。24、一個串的任意個連續(xù)的字符組成的子序列稱為該串的________，包含該子串的串稱為________。25、求串T在主串S中首次出現(xiàn)的位置的操作是________________。26、在初始為空的隊列中插入元素A,B,C,D以后，緊接著作了兩次刪除操作，此時的隊尾元素是__________。27、在長度為n的循環(huán)隊列中，刪除其節(jié)點(diǎn)為x的時間復(fù)雜度為_______________。28、已知廣義表L為空，其深度為___________。29、已知一順序存儲的線性表，每個結(jié)點(diǎn)占用k個單元，若第一個結(jié)點(diǎn)的地址為DA1，則第i個結(jié)點(diǎn)的地址為______________。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、在進(jìn)行直接插入排序時,其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列________關(guān)；而在進(jì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、稀疏矩陣一般采用__________方法進(jìn)行壓縮存儲。36、稀疏矩陣可用_________進(jìn)行壓縮存儲，存儲時需存儲非零元的________、________、________。37、若矩陣中所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱為__________。38、若一個n階矩陣A中的元素滿足：Aij=Aji(0<=I,j<=n-1)則稱A為____________矩陣；若主對角線上方(或下方)的所有元素均為零時，稱該矩陣為______________。39、對于上三角形和下三角形矩陣，分別以按行存儲和按列存儲原則進(jìn)行壓縮存儲到數(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)),則運(yùn)算head(head(tail（A）)))=___________。43、已知廣義表ls=(a,(b,c,d),e),運(yùn)用head和tail函數(shù)取出ls中的原子b的運(yùn)算是_____。44、在樹結(jié)構(gòu)里，有且僅有一個結(jié)點(diǎn)沒有前驅(qū)，稱為根。非根結(jié)點(diǎn)有且僅有一個___________,且存在一條從根到該結(jié)點(diǎn)的_______________。45、度數(shù)為0的結(jié)點(diǎn)，即沒有子樹的結(jié)點(diǎn)叫作__________結(jié)點(diǎn)或_________結(jié)點(diǎn)。同一個結(jié)點(diǎn)的兒子結(jié)點(diǎn)之間互稱為___________結(jié)點(diǎn)。46、假定一棵樹的廣義表為A(B(e),C(F(h,i,j),g),D),則該樹的度為___________，樹的深度為_________，終端結(jié)點(diǎn)為______，單分支結(jié)點(diǎn)為，雙分支結(jié)點(diǎn)個數(shù)為_______，三分支結(jié)點(diǎn)為_______，C結(jié)點(diǎn)的雙親結(jié)點(diǎn)是______，孩子結(jié)點(diǎn)是______。48、完全二叉樹、滿二叉樹、線索二叉樹和二叉排序樹這四個名詞術(shù)語中，與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān)系的是_____________。47、有三個結(jié)點(diǎn)的二叉樹，最多有________種形狀。48、每一趟排序時從排好序的元素中挑出一個值最小的元素與這些未排小序的元素的第一個元素交換位置，這種排序方法成為_____________排序法。49、高度為k的二叉樹具有的結(jié)點(diǎn)數(shù)目，最少為_____,最多為_____。50、對任何一棵二叉樹，若n0，n1，n2分別是度為0，1，2的結(jié)點(diǎn)的個數(shù)，則n0=_______。51、在含100個結(jié)點(diǎn)的完全二叉樹，葉子結(jié)點(diǎn)的個數(shù)為_______。52、將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列叫_____。53、若一棵滿二叉樹含有121個結(jié)點(diǎn)，則該樹的深度為_________。54、一個具有767個結(jié)點(diǎn)的完全二叉樹，其葉子結(jié)點(diǎn)個數(shù)為________。55、深度為90的滿二叉樹，第11層有________個結(jié)點(diǎn)。56、有100個結(jié)點(diǎn)的完全二叉樹，深度為________。57、設(shè)一棵二叉樹中度為2的結(jié)點(diǎn)10個，則該樹的葉子個數(shù)為________。58、若待散列的序列為(18,25,63,50,42,32,9)，散列函數(shù)為H(key)=keyMOD9，與18發(fā)生沖突的元素有_____________個。59、含有3個2度結(jié)點(diǎn)和4個葉結(jié)點(diǎn)的二叉樹可含__________個1度結(jié)點(diǎn)。60、一棵具有５層滿二叉樹中節(jié)點(diǎn)總數(shù)為___________。61、一棵含有16個結(jié)點(diǎn)的完全二叉樹，對他按層編號，對于編號為7的結(jié)點(diǎn)，他的雙親結(jié)點(diǎn)及左右結(jié)點(diǎn)編號為______、______、_______。62、深度為k(設(shè)根的層數(shù)為1)的完全二叉樹至少有_______個結(jié)點(diǎn),至多有_______個結(jié)點(diǎn)。63、若要對某二叉排序樹進(jìn)行遍歷，保證輸出所有結(jié)點(diǎn)的值序列按增序排列，應(yīng)對該二叉排序樹采用________遍歷法。64、在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24，需要進(jìn)行______________次元素之間的比較。65、設(shè)有10個值，構(gòu)成哈夫曼樹，則該哈夫曼樹共有______個結(jié)點(diǎn)。66、從樹中一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)之間的分支構(gòu)成這兩個結(jié)點(diǎn)之間的____________。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、對于有向圖，頂點(diǎn)的度分為入度和出度，以該頂點(diǎn)為終點(diǎn)的邊數(shù)目叫________；以該頂點(diǎn)為起點(diǎn)的邊數(shù)目叫_________。71、一個無向圖采用鄰接矩陣存儲方法，其鄰接矩陣一定是一個______________。72、有一個n個頂點(diǎn)的有向完全圖的弧數(shù)_____________。73、在無向圖中，若從頂點(diǎn)A到頂點(diǎn)B存在_________，則稱A與B之間是連通的。74、在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的___________倍。75、一個連通圖的生成樹是該圖的____________連通子圖。若這個連通圖有n個頂點(diǎn),則它的生成樹有__________條邊。76、無向圖的鄰接矩陣是一個_____________矩陣。77、如果從一無向圖的任意頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是____________。78、若采用鄰接表的存儲結(jié)構(gòu)，則圖的廣度優(yōu)先搜索類似于二叉樹的____________遍歷。79、若圖的鄰接矩陣是對稱矩陣，則該圖一定是________________。80、從如圖所示的臨接矩陣可以看出，該圖共有______個頂點(diǎn)。如果是有向圖，該圖共有______條弧；如果是無向圖，則共有________條邊。81、如果從一個頂點(diǎn)出發(fā)又回到該頂點(diǎn)，則此路徑叫做___________。82、一個具有個n頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要________條邊。83、給定序列{100,86,48,73,35,39,42,57,66,21},按堆結(jié)構(gòu)的定義,則它一定_________堆。84、從未排序序列中選擇一個元素，該元素將當(dāng)前參加排序的那些元素分成前后兩個部分，前一部分中所有元素都小于等于所選元素，后一部分中所有元素都大于或等于所選元素，而此時所選元素處在排序的最終位置。這種排序法稱為_____________排序法。85、折半搜索只適合用于___________________。86、結(jié)點(diǎn)關(guān)鍵字轉(zhuǎn)換為該結(jié)點(diǎn)存儲單元地址的函數(shù)H稱為_____________或叫__________。87、在索引查找中，首先查找________，然后查找相應(yīng)的_________，整個索引查找的平均查找長度等于查找索引表的平均長度與查找相應(yīng)子表的平均查找長度的_______。二、填空題答案：

1、運(yùn)算

2、空間復(fù)雜度。

3、有窮性，確定性，可行性，輸入，輸出

4、鏈表

5、直接前驅(qū)，直接后繼

6、1個直接，1個直接

7、循環(huán)

8、指針，數(shù)據(jù)

9、前驅(qū)，后繼

10、head->next!=Null

11、前驅(qū)，后繼

12、刪除p的后繼結(jié)點(diǎn)

13、后繼

14、s->next=p->next;p->next=s

15、不連續(xù)，連續(xù)

16、棧頂

17、top=-1

18、頭結(jié)點(diǎn)

19、s[0]，s[n-1]

20、隊列，隊尾隊頭

21、Q->font=Q->rear

22、(R-F)%n

23、17

24、子串，主串

25、Index(S,T,pos)

26、D

27、O(n)

28、1

29、DA1+(i-1)*k

30、1100+（6*2+3）*2=1130

3