算法與數(shù)據(jù)結構常見考題筆試題

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

1、運算

2、空間復雜度。

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

4、鏈表

5、直接前驅，直接后繼

6、1個直接，1個直接

7、循環(huán)

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

9、前驅，后繼

10、head->next!=Null

11、前驅，后繼

12、刪除p的后繼結點

13、后繼

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

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

16、棧頂

17、top=-1

18、頭結點

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