數(shù)據(jù)結構與算法練習試卷1（共205題）

數(shù)據(jù)結構與算法練習試卷1（共8套）（共205題）數(shù)據(jù)結構與算法練習試卷第1套一、填空題(本題共20題，每題1.0分，共20分。)1、在具有n個單元的循環(huán)隊列中，隊滿時共有______個元素。標準答案：n-1知識點解析：暫無解析2、隊列和棧分別是______、______的線性表結構。標準答案：先進先出，后進先出知識點解析：暫無解析3、數(shù)據(jù)結構包括3個方面的內容是數(shù)據(jù)的______、數(shù)據(jù)的邏輯結構、數(shù)據(jù)的運算。標準答案：存儲結構知識點解析：暫無解析4、數(shù)據(jù)的基本單位是______。標準答案：數(shù)據(jù)元素知識點解析：暫無解析5、一個深度為n的滿二叉樹上的結點總數(shù)為______；一棵深度為n的完全二叉樹上的結點總數(shù)最小值為______，最大值為______。標準答案：2n-1，2n-1，2n-1知識點解析：暫無解析6、線性表、棧和隊列都是線性結構，可以在線性表的______位置插入和刪除元素；而對棧只能在______插入和刪除元素；對于隊列只能在______插入和在______刪除元素。標準答案：任何，棧頂，隊尾，隊首知識點解析：暫無解析7、廣義表(a，(a，B)，d，e，((i，j，k))的長度是______，深度是______。標準答案：5，3知識點解析：暫無解析8、長度為255的表，采用分塊查找法，每塊的最佳長度是______。標準答案：15知識點解析：暫無解析9、已知一個待散列存儲的線性表18，34，58，26，75，67，48，81，散列函數(shù)為H(k)=kmod11，若采用線性探測法解決沖突，則平均查找長度為______。若采用鏈接法解決沖突，則平均查找長度為______。標準答案：14/9，13/9知識點解析：暫無解析10、在一棵二叉排序樹中，按______遍歷得到的結點序列是有序序列。標準答案：中序知識點解析：暫無解析11、在堆排序、快速排序、希爾排序、插入排序、歸并排序、基數(shù)排序和選擇排序中，______平均比較次數(shù)最少，______需要內存容量最多。標準答案：快速排序，基數(shù)排序知識點解析：暫無解析12、對n個元素的序列采用冒泡排序的方法，最少的比較次數(shù)為______。標準答案：n-1知識點解析：暫無解析13、二分查找法的存儲結構要求是______，對元素要求______。標準答案：順序存儲結構，有序知識點解析：暫無解析14、在算法正確的前提下，評價一個算法的兩個標準是______、______。標準答案：時間復雜度，空間復雜度知識點解析：暫無解析15、在分塊查找方法中，首先查找______，然后再查找相應的______。標準答案：索引，塊知識點解析：暫無解析16、鏈表中數(shù)據(jù)元素的入棧順序為abcde，則其出棧順序為______。標準答案：edcba知識點解析：暫無解析17、設有關鍵字序列{23，4，67，2，65，2，59，13，42}，按堆排序思想選出當前序列最大元素67和65后，剩余元素構成的堆是______。標準答案：{59，42，23，13，5，2，2)知識點解析：暫無解析18、一棵有n個結點的樹，該樹中所有結點的入度之和為______。標準答案：n-1知識點解析：暫無解析19、對二叉樹結點的先序遍歷、中序遍歷、后序遍歷序列中，所有葉子結點的先后順序______。標準答案：相同知識點解析：暫無解析20、算法的時間復雜性是指該算法包含______的多少，它是一個算法運行時間的相對度量；一個算法的空間復雜性是指該算法在運行過程中臨時占用______的大小。標準答案：簡單操作次數(shù)，存儲空間知識點解析：暫無解析數(shù)據(jù)結構與算法練習試卷第2套一、填空題(本題共25題，每題1.0分，共25分。)1、數(shù)據(jù)元素之間______的整體稱為邏輯結構。標準答案：邏輯關系知識點解析：暫無解析2、一個算法的時間復雜性是______的函數(shù)。標準答案：算法輸入規(guī)模知識點解析：暫無解析3、在單鏈表中，NULL稱為______，它不指向任何結點，只起______作用。標準答案：空指針、標志知識點解析：暫無解析4、對長度為n的順序表的刪除算法，它的最壞情況時間復雜度及其量級分別是和______，平均時間復雜性及其量級分別為______和______。標準答案：n-1、O(n)、(n-1)/2、O(n)知識點解析：暫無解析5、存儲結點中數(shù)據(jù)域占用的存儲量與整個結點占用存儲量之比稱為______。標準答案：存儲密度知識點解析：暫無解析6、一般地，二叉樹可以有______種基本形態(tài)。標準答案：5知識點解析：暫無解析7、按照排序過程涉及的存儲設備的不同，排序可分為______和______。標準答案：內部排序、外部排序知識點解析：暫無解析8、評價排序算法優(yōu)劣的主要標準是______和______。標準答案：時間復雜度、算法需要的附加空間知識點解析：暫無解析9、穩(wěn)定的排序算法有______、______和______。標準答案：直接插入排序、冒泡排序、歸并排序知識點解析：暫無解析10、第一趟排序后序列中關鍵字最大的記錄交換到最后的排序方法是______。標準答案：冒泡排序知識點解析：暫無解析11、數(shù)據(jù)結構分為邏輯結構與存儲結構，線性鏈表屬于______。標準答案：存儲結構知識點解析：暫無解析12、在樹型結構中，樹根結點沒有______。標準答案：前件知識點解析：暫無解析13、數(shù)據(jù)的邏輯結構有線性結構和______兩大類。標準答案：非線性結構知識點解析：暫無解析14、順序存儲方法是把邏輯上相鄰的結點存儲在物理位置______的存儲單元中。標準答案：相鄰知識點解析：暫無解析15、當線性表采用順序存儲結構實現(xiàn)存儲時，其主要特點是______。標準答案：邏輯結構中相鄰的結點在存儲結構中仍相鄰知識點解析：暫無解析16、用鏈表表示線性表的突出優(yōu)點是______。標準答案：便于插入和刪除操作知識點解析：暫無解析17、棧和隊列通常采用的存儲結構是______。標準答案：鏈式存儲和順序存儲知識點解析：暫無解析18、當循環(huán)隊列非空且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進行入隊運算。這種情況稱為______。標準答案：上溢知識點解析：暫無解析19、數(shù)據(jù)結構包括數(shù)據(jù)的邏輯結構、數(shù)據(jù)的______以及對數(shù)據(jù)的操作運算。標準答案：存儲結構知識點解析：暫無解析20、算法的基本特征是可行性、確定性、______和擁有足夠的情報。標準答案：有窮性知識點解析：暫無解析21、在長度為n的有序線性表中進行二分查找，最壞的情況下，需要的比較次數(shù)為______。標準答案：log2n知識點解析：暫無解析22、長度為n的順序存儲線性表中，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為______。標準答案：n/2知識點解析：暫無解析23、排序是計算機程序設計中的一種重要操作，常見的排序方法有插入排序、______和選擇排序等。標準答案：交換掉序知識點解析：暫無解析24、設一棵二叉樹的中序遍歷結果為DBEAFC，前序遍歷結果為ABDECF，則后序遍歷結果為______。標準答案：DEBFCA知識點解析：暫無解析25、數(shù)據(jù)獨立性分為邏輯獨立性與物理獨立性。當數(shù)據(jù)的存儲結構改變時，其邏輯結構可以不變，因此，基于邏輯結構的應用程序不必修改，稱為______。標準答案：邏輯獨立性知識點解析：暫無解析數(shù)據(jù)結構與算法練習試卷第3套一、中文選擇題(本題共24題，每題1.0分，共24分。)1、對具有n個元素的順序表(采用順序存儲的線性表)進行______操作，其耗時與n的大小無關。A．在第i(1≤i≤n)個元素之后插入一個新元素B．刪除第i(1≤i≤n)個元素C．對順序表中的元素進行排序D．訪問第i(1≤i≤n)個元素的前驅和后繼A、

B、

C、

D、

標準答案：D知識點解析：暫無解析2、若字符串s的長度為n(n＞1)且其中的字符互不相同，則s的長度為2的子串有______個。A．nB．n-1C．n-2D．2A、

B、

C、

D、

標準答案：B知識點解析：暫無解析3、棧的運算特點是后進先出。元素a、b、c、d依次入棧，則不能得到的出棧序列是______。A．abcdB．cabdC．dcbaD．bcdaA、

B、

C、

D、

標準答案：B知識點解析：暫無解析4、設初始棧為空，s表示入棧操作，x表示出棧操作，則______是合法的操作序列。A．sxxsssxxxB．xxssxxssC．sxsxssxxD．XssssxxxA、

B、

C、

D、

標準答案：C知識點解析：暫無解析5、n個元素依次全部進入棧后，再陸續(xù)出棧并經過一個隊列輸出。那么，______。A．元素的出隊次序與進棧次序相同B．元素的出隊次序與進棧次序相反C．元素的進棧次序與進隊次序相同D．元素的出棧次序與出隊次序相反A、

B、

C、

D、

標準答案：B知識點解析：暫無解析6、與單向鏈表相比，雙向鏈表______。A．需要較少的存儲空間B．遍歷元素需要的時問較短C．較易于訪問相鄰節(jié)點D．較易于插入和刪除元素A、

B、

C、

D、

標準答案：C知識點解析：暫無解析7、若一個棧以向量V[1..n]存儲，且空棧的棧頂指針top為n+1，則將元素x入棧的正確操作是______。A．top=top+1；V[top]=x；B．V[top]=x；top=top+1；C．top=top-1；V[top]=x；D．V[top]=x；top=top-1；A、

B、

C、

D、

標準答案：C知識點解析：暫無解析8、在執(zhí)行遞歸過程時，通常使用的數(shù)據(jù)結構是______。A．堆棧(stack)B．隊列(queue)C．圖(graph)D．樹(tree)A、

B、

C、

D、

標準答案：A知識點解析：暫無解析9、設數(shù)組a[1..6，0..9]的元素以行為主序存放，每個元素占用一個存儲單元，則數(shù)組元素a[3，3]的地址為______。A．a+23B．a+27C．a+39D．a+35A、

B、

C、

D、

標準答案：A知識點解析：暫無解析10、若二維數(shù)組P[1..5，0..8]的首地址為base，數(shù)組元素按行存儲，且每個元素占用1個存儲單元，則元素P[3，3]在該數(shù)組空間的地址為______。A．base+13B．base+16C．base+18D．base+21A、

B、

C、

D、

標準答案：D知識點解析：暫無解析11、數(shù)組A[-5..5，0..8]按列存儲。若第一個元素的首地址為100，且每個元素占用4個存儲單元，則元素A[2，3]的存儲地址為______。A．244B．260C．364D．300A、

B、

C、

D、

標準答案：B知識點解析：暫無解析12、若二叉樹的前序遍歷序列與中序遍歷序列相同且樹中節(jié)點數(shù)大于1，則該二叉樹的______。A．只有根節(jié)點無左予樹B．只有根節(jié)點無右子樹C．非葉子節(jié)點只有左子樹D．非葉子節(jié)點只有右子樹A、

B、

C、

D、

標準答案：D知識點解析：暫無解析13、由關鍵字序列(12，7，36，25，18，2)構造一棵二叉排序樹(初始為空，第一個關鍵字作為根節(jié)點插入，此后對于任意關鍵字，若小于根節(jié)點的關鍵字，則插入左子樹中，若大于根節(jié)點的關鍵字，則插入右子樹中，且左、右子樹均為二叉排序樹)，該二叉排序樹的高度(層數(shù))為______。A．6B．5C．4D．3A、

B、

C、

D、

標準答案：C知識點解析：暫無解析14、在任意一棵非空的二叉樹中，終端節(jié)點(葉子)的數(shù)目總是比具有兩個孩子的非終端節(jié)點的數(shù)目______。A．多0個B．多1個C．多2個D．多3個A、

B、

C、

D、

標準答案：B知識點解析：暫無解析15、數(shù)據(jù)結構中的樹最適合用來表示______的情況。A．數(shù)據(jù)元素有序B．數(shù)據(jù)元素之間具有多對多關系C．數(shù)據(jù)元素無序D．數(shù)據(jù)元素之間具有一對多關系A、

B、

C、

D、

標準答案：D知識點解析：暫無解析16、二叉排序樹或者是一棵空樹，或者是具有如下性質的二叉樹：特其左子樹非空，則左子樹上所有節(jié)點的值均小于根節(jié)點的值；若其右子樹非空，則右子樹上所有節(jié)點的值均大于根節(jié)點的值；其左、右子樹本身就是兩棵二叉排序樹。根據(jù)該定義，對一棵非空的二叉排序樹進行______遍歷，可得到一個節(jié)點元素的遞增序列。A．前序(根、左、右)B．中序(左、根、右)C．后序(左、右、根)D．層序(從樹根開始，按層次)A、

B、

C、

D、

標準答案：D知識點解析：暫無解析17、若線性表(24，13，31，6，15，18，8)采用散列(Hash)法進行存儲和查找，設散列函數(shù)為H(Key)=Keymod11，則構造散列表時發(fā)生沖突的元素為______(其中的mod表示整除取余運算)。A．24和13B．6和15C．6和24D．18和8A、

B、

C、

D、

標準答案：A知識點解析：暫無解析18、線性表采用順序存儲結構，若表長為m，且在任何一個合法插入位置上進行插入操作的概率相同，則插入一個元素平均移動______個元素。A．m-1B．m/2C．m/2+1D．MA、

B、

C、

D、

標準答案：B知識點解析：暫無解析19、兩個遞增序列A和B的長度分別為m和n(m＜n)，將兩者歸并為一個長度為m+n的遞增序列時，______，歸并過程中元素的比較次數(shù)最少。A．當A的最大元素大于B的最大元素時B．當A的最大元素小于B的最小元素時C．當A的最小元素大于B的最小元素時D．當A的最小元素小于B的最大元素時A、

B、

C、

D、

標準答案：B知識點解析：暫無解析20、采用哈希(或散列)技術構造查找表時，需要考慮沖突(碰撞)的處理，沖突是指______。A．關鍵字相同的記錄被映射到不同的哈希地址B．關鍵字依次被映射到編號連續(xù)的哈希地址C．關鍵字不同的記錄被映射到同一個哈希地址D．關鍵字的數(shù)目超過哈希地址的數(shù)目A、

B、

C、

D、

標準答案：C知識點解析：暫無解析21、對于長度為11的順序存儲的有序表，若采用折半查找(向下取整)，則找到第5個元素需要與表中的______個元素進行比較操作(包括與第5個元素的比較)。A．5B．4C．3D．2A、

B、

C、

D、

標準答案：B知識點解析：暫無解析22、如果待排序序列中兩個元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。______是穩(wěn)定的排序方法，因為這種方法在比較相鄰元素時，值相同的元素并不進行交換。A．冒泡排序B．希爾排序C．快速排序D．簡單選擇排序A、

B、

C、

D、

標準答案：A知識點解析：暫無解析23、用二分法來檢索數(shù)據(jù)，最確切的說法是______。A．僅當數(shù)據(jù)隨機排列時，才能正確地檢索數(shù)據(jù)B．僅當數(shù)據(jù)有序排列時，才能正確地檢索數(shù)據(jù)C．僅當數(shù)據(jù)量較大時，才能有效地檢索數(shù)據(jù)D．僅當數(shù)據(jù)量較小時，才能有效地檢索數(shù)據(jù)A、

B、

C、

D、

標準答案：B知識點解析：暫無解析24、若原始數(shù)據(jù)序列(23，4，45，67，12，8，19，7)采用直接插入排序法(順序地將每個元素插入到它之前的適當位置)排序，則進行完第4趟后的排序結果是______。A．4，8，45，23，67，12，19，7B．4，7，8，12，23，45，67，19C．4，12，8，19，7，23，45，67D．4，12，23，45，67，8，19，7A、

B、

C、

D、

標準答案：D知識點解析：暫無解析二、流程圖題(本題共6題，每題1.0分，共6分。)25、閱讀以下說明和C語言函數(shù)，回答問題。[說明]函數(shù)sort(NODE*head)的功能是：用冒泡排序法對單鏈表中的元素進行非遞減排序。對于兩個相鄰節(jié)點中的元素，若較小的元素在后面，則交換這兩個節(jié)點中的元素值。其中，head指向鏈表的頭節(jié)點。排序時，為了避免每趟都掃描到鏈表的尾節(jié)點，設置一個指針endptr，使其指向下趟掃描需要到達的最后一個節(jié)點。例如，對于圖8-25(a)所示的鏈表進行一趟冒泡排序后，得到圖8-25(b)所示的鏈表。鏈表的節(jié)點類型定義如下：typedefStruetNode{intdata；structNode*next；}NODE;[C語言函數(shù)]voidsort(NODE*head){NODE*ptr,*preptr,*endptr;inttempdata;ptr=head-＞next;while(1)/*查找表尾節(jié)點*/ptr=ptr-＞next;endptr=ptr;/*令endptr指向表尾節(jié)點*/ptr=(2);while(ptr!=endptr){while((3)){if(ptr-＞data＞ptr-＞next-＞data){tempdata=ptr-＞data;/*交換相鄰節(jié)點的數(shù)據(jù)*/ptr-＞data=ptr-＞next-＞data;ptr-＞next-＞data=tempdata;}preptr=(4)；ptr=ptr-＞next;}endptr=(5);ptr=head-＞next;}}標準答案：ptr-＞nexthead-＞nextptr!=endptr，或其他等價形式ptrpreptr知識點解析：暫無解析26、閱讀以下說明和C程序，回答問題。[說明]下面的程序用DoleRob算法生成N階(N為奇數(shù))魔方陣(各行、列、對角線數(shù)字之和相等)。該算法的過程為：從1開始，按如下方法依次插入各自然數(shù)，直到N2為止。①在第一行的正中插入1。②新位置應當處于最近插入位置的右上方，若該位置已超出方陣的上邊界，則新位置取應選列的最下一個位置；若超出右邊界，則新位置取應選行的最左一個位置。③若最近插入的元素是N的整數(shù)倍，則選同列的下一行位置為新位置。例如，3階魔方陣如下所示：816357492[C程序]#include＜stdio.h＞#include＜stdlib.h＞#defineSIZE50main(){introw,col,n,value;inta[SIZE+1][SIZE+1];/*不使用下標為0的元素*/printf("請輸入要輸出魔方陣的階數(shù)n(奇數(shù),＜%d):n=",SIZE);scanf("%d",&n);if(!(n%2)||n＜1||(1)){printf("輸入數(shù)據(jù)有誤!\n");exit(0);}row=1;col=(n+1)/2;value=1;while(value＜=(2)){a[row][col]=value;/*計算下一位置*/if(value%n!=0){row--;(3);if(row＜1)row=n;if(col＞n)(4);}elserow++;value=(5);}printf("\n%d階魔方陣如下所示：\n\n",n);for(row=1;row＜=n;row++){for(col=1;col＜=n;col++)printf("%5d",a[row][col]);printf("\n");}}標準答案：n＞SIZE，或其等價表示n*ncol++，或++col，或col=col+1，或其等價表示col-=n，或col=1，或其等價表示value+1，或其等價表示知識點解析：程序中空(1)處判斷n的合法性，n需為奇數(shù)，矩陣規(guī)模應不超過SIZE2。所以(1)處應為n＞SIZE，或其等價表示。將數(shù)值填入方陣的語句為“a[row][col]=value;”，該語句在循環(huán)中，循環(huán)條件為“value＜=n*n”，所以(2)處應填入“n*n”。對于3階魔方陣，1填入第1行第2列，2填入第3行第3列，3填入第2行第1列，其余位置按照算法步驟類推。所以(3)處填入“col++”或其等價形式，(4)處填入“col=1”或“col-=n”。程序中，本次填入的數(shù)值為value的值，下一次要填入的數(shù)值為vahle加1，因此，空(5)處應填入“value+1”。27、[說明]計算機在處理算術表達式時，首先將其轉換為后綴表達式。例如，表達式“46+5*(120-37)”的后綴表達式形式為“46512037-*+”。計算后綴表達式時，從左至右掃描后綴表達式：若遇到運算對象，則壓入棧中；遇到運算符，則從棧中彈出相關運算對象進行計算，并將運算結果壓入棧中。重復以上過程，直到后綴表達式掃描結束。例如，后綴表達式“46512037-*+”的汁算過程如下。①依次將46、5、120、37壓入棧中。②遇到“-”，取出37、120，計算120-37=83，將其壓入棧中。③遇到“*”，取出83、5，計算5×83=415，將其壓入棧中。④遇到“+”，取出415、46，計算46+415=461，將其壓入棧中。⑤表達式結束，則計算過程完成。函數(shù)computing(charexpt[]，int*result)的功能是基于棧計算后綴形式的表達式(以串形式存入字符數(shù)組expr)的值，并通過參數(shù)result返回該值。函數(shù)的返回值為-1/0，分別表示表達式有/無錯誤。假設表達式中僅包含數(shù)字、空格和算術運算符號，其中所有項均以空格分隔，且運算符僅包含加(“+”)、減(“-”)、乘(“*”)、除(“\”)。函數(shù)computing中所用棧的基本操作的函數(shù)原型說明如下。voidInitStack(STACK*s)：初始化棧。voidPush(STACK*s,inte)：將一個整數(shù)壓棧，棧中元素數(shù)目增1。voidPop(STACK*s)：棧頂元素出棧，棧中元素數(shù)目減1。intTop(STACKs)：返回非空棧的棧頂元素值，棧中元素數(shù)目不變。intIsEmpty(STACKs)：若s是空棧，則返回1；否則返回0。[C函數(shù)]intcomputing(charexpr[],int*result){STACKs;inttnum,a,b;char*ptr;InitStack(&s);ptr=expr;pstr/*字符指針指向后綴表達式串的第一個字符*/while(*ptr!=’\0’){if(*ptr==’’){/*當前字符是空格*/(1);/*字符指針指向下一字符*/continue;}elseif(isdigit(*ptr)){/*當前字符是數(shù)字，則將該數(shù)字開始的數(shù)字串轉換為數(shù)值*/tnum=(2);while(*ptr＞=’0’&&*ptr＜=’9’){tnum=tnum*10+(3);ptr++;}push((4));}else/*當前字符是運算符或其他符號*/if(*ptr==’+’||*ptr==’-’||*ptr==’*’||*ptr==’/’){if(!IsEmpty(S)){a=Top(s);Pop(&s);/*取運算符的第二個運算數(shù)*/if(!IsEmpty(S)){b=Top(s);Pop(&s);/*取運算符的第一個運算數(shù)*/}elsereturn-1;}elsereturn-1;switch(*ptr){case’+’:Push(&S,b+a);break;case’-’:Push(&s,b-a);break;case’+’:Push(&s,b*a);break;case’/’:Push(&s,b/a);break;}elsereturn-1;ptr++;/*字符指針指向下一字符*/}/*while*/if(IsEmpty(s))return-1;else{(5)=Top(s);Pop(&s);/*取運算結果*/if(!IsEmpty(s))return-1;return0;}}標準答案：ptr++，或++ptr，或ptr=ptr+1，或其等價表示0，或tnum=0*ptr-48，或*ptr-‘0’，或其等價表示&s,tnum*result知識點解析：由于后綴表達式以字符串方式存儲且以空格分隔符號(數(shù)值、運算符)，因此遇到空格字符時，指向表達式中字符的指針ptr應增加1指向后續(xù)字符，所以(1)處應填入“ptr++”或其等價形式。tnum的初始值應為0，因此，空(2)處應填入“0”，空(3)所在表達式將數(shù)字字符轉換為數(shù)值，即空(3)處填入“*ptr-48”?？?4)處用于將轉換所得的數(shù)值tnum壓入棧項，根據(jù)題目中Push的原型“voidPush(STACK*s,inte)”，調用時第一個實際參數(shù)是STACK類型變量的地址，第二個實際參數(shù)是一個整數(shù)，因此，空(4)處填入“&s,tnum”。由于函數(shù)computing(charexpr[],int*result)通過參數(shù)result返回該表達式的值，因此需要將存在棧頂?shù)倪\算結果賦值給result指向的整型變量，即空(5)處填入“*result”。28、[說明]已知某二叉樹的非葉子節(jié)點都有兩個孩子節(jié)點，現(xiàn)將該二叉樹存儲在結構數(shù)組Ht中。節(jié)點結構及數(shù)組Ht的定義如下：#defineMAXLEAFNUM30Structnode{charch;char*pstr;intparent;intlchild,rchiid;};StructnodeHt[2*MAXLEAFNUM];該二叉樹的n個葉子節(jié)點存儲在下標為1～n的Ht數(shù)組元素中。例如，某二叉樹如圖8-26所示，其存儲結構如圖8-27所示，其中，與葉子節(jié)點a對應的數(shù)組元素下標為1，a的父節(jié)點存儲在Ht[5]，表示為Ht[1].parent=5。Ht[7].parent=0表示7號節(jié)點是樹根，Ht[7].lchild=3、Ht[7].rchild=6分別表示7號節(jié)點的左孩子是3號節(jié)點、右孩子是6號節(jié)點。如果用“0”或“1”分別標識二叉樹的左分支和右分支如圖8-26所示，從根節(jié)點開始到葉子節(jié)點為止，按所經過分支的次序將相應標識依次排列，可得到一個0、1序列，稱之為對應葉子節(jié)點的編碼。例如，圖8-26中a、b、c、d的編碼分別是100、101、0、11。函數(shù)LeafCode(Ht[]，n)的功能是：求解存儲在Ht中的二叉樹中所有葉子節(jié)點(n個)的編碼，葉子節(jié)點存儲在Ht[1]～Ht[n]中，求出的編碼存儲區(qū)由對應的數(shù)組元素pstr域指示。[函數(shù)]typedefenumStatus{ERROR，OK}Status;StatusLeafCode(StruetnodeHt[],intn){intpc,pf;inti,start;chartstr[31]={’\0’);for(i=1;(1);i++){start=29;pc=i;pf=Ht[i].parent;while(Pf!=(2)){if((3).lchiid==pc)tstr[--start]=’0’;elsetstr[-start]=’1’;pc=(4);pf=Ht[Pf].parent;}Ht[i].pstr=(char*)malloc(31-start);if(!Ht[i].pstr)returnERROR;strcpy(Ht[i].pstr,(5);}returnOK;}標準答案：i＜=n，或其等價形式0Ht[pf]，或(*(Ht+pf))pftstr+start或&tstr[start]知識點解析：題中已指出該二叉樹的n個葉子節(jié)點存儲在下標為1到n的Ht數(shù)組元素中，同時舉例說明父節(jié)點編號為0的節(jié)點是樹根節(jié)點。所以，(1)處應為“i＜=n”。而到達根即父節(jié)點為0時，所以(2)處為“0”。pc用于指出樹中的節(jié)點，pf則用于指出pc所對應節(jié)點的父節(jié)點，所以(3)處應為“Ht[pf]”，(4)處應為“pf”。根據(jù)tstr的作用，strcpy函數(shù)的實參應該是“tstr+start”或“&tstr[start]”，所以(5)處應該為“tstr+start”或“&tstr[start]”。29、[說明]已知包含頭節(jié)點(不存儲元素)的單鏈表的元素已經按照非遞減方式排序，函數(shù)compress(NODE*head)的功能是去掉其中重復的元素，使得鏈表中的元素互不相同。處理過程中，當元素重復出現(xiàn)時，保留元素第一次出現(xiàn)所在的節(jié)點。圖8-29(a)、(b)是經函數(shù)compress()處理前后的鏈表結構示例圖。鏈表的節(jié)點類型定義如下：typedefstructNode{intdata;structNode*next;}NODE;[C語言函數(shù)]voidcompress(NODE*head){NODE*ptr,*q;ptr=(1);/*取得第一個元素節(jié)點的指針*/while((2)&&ptr-＞next){q=ptr-＞next;while(q&&(3)){/*處理重復元素*/(4)=q-＞next;free(q);q=ptr-＞next;}(5)=ptr-＞next;}/*endofwhile*/}/*endofcompress*/標準答案：head＞nextptrptr-＞data==q-＞data或其等價形式ptr-＞nextptr知識點解析：本題考查的是對鏈表的查找、插入和刪除等運算。要找到重復的元素并將其刪除而使各元素互不相同。我們可以順序遍歷鏈表，比較邏輯上相鄰的兩個元素是否相同，如果相同則刪除后一個元素，以此類推。代碼如下：VOidCompress(NODE*head){NODE*ptr,*q;ptr=head-＞next;/*取得第一個元素節(jié)點的指針*/while(ptr&&ptr-＞next){q=ptr-＞next;while(q&&ptr-＞data==q＞data){/*處理重復元素*/ptr-＞next=q-＞next;free(q);q=ptr-＞next;}ptr=ptr-＞next;}/*endofwhile*/}/*endofcompress*/30、[說明]下面流程圖的功能是：在已知字符串A中查找特定字符串B，如果存在，則輸出B串首字符在A串中的位置，否則輸出-1。設串A由n個字符A(0)、A(1)、…、A(n-1)組成，串B由m個字符B(0)、B(1)、…、B(m-1)組成，其中n≥m＞0。在串A中查找串B的基本算法如下：從串A的首字符A(0)開始，取子串A(0)A(1)…i(m-1)與串B比較；若不同，則再取子串A(1)A(2)…A(m)與串B比較，以此類推。例如，字符串“CABBRFFD”中存在字符子串“BRF”(輸出3)，不存在字符子串“RFD”(輸出-1)。在流程圖中，i用于訪問串A中的字符(i=0，1，…，n-1)，j用于訪問串B中的字符(j=0，1，…，m-1)。在比較A(i)A(i+1)…A(i+m-1)與B(0)B(1)…B(m-1)時，需要對A(i)與B(0)、A(i+1)與B(1)、…、A(i+j)與B(j)、…逐對字符進行比較。若發(fā)現(xiàn)不同，則需要取下一個子串進行比較，以此類推。[流程圖]本題流程圖如圖8-30所示。標準答案：j+1i+10i-1知識點解析：依題意，在已知字符串A中查找特定字符串B，基本算法如下：從串A的首字符A(0)開始，取子串A(0)A(1)…A(m-1)與串B比較；若不同，則再取子串A(1)A(2)…A(m)與串B比較，以此類推。我們可以采用兩重循環(huán)來實現(xiàn)。初始時，i與j都設為0，i范圍為0至n-1，j范圍為m-1，比較A(i+j)與B(j)是否相等，在循環(huán)過程中只要存在一個j使得A(i+j)不等于B(i)，則退出本次循環(huán)，i+1后重新進行遍歷。如果最后i＞n-m則說明不存在B字符串。否則，返回B字符串的位置。數(shù)據(jù)結構與算法練習試卷第4套一、選擇題(本題共22題，每題1.0分，共22分。)1、二維數(shù)組A[0…8，0…9]中的每個元素占2個字節(jié)，從首地址300開始，按行優(yōu)先順序存放，則元素A[4，5]的存儲地址為()。A、390B、326C、230D、310標準答案：A知識點解析：暫無解析2、設有關鍵碼序列(16，9，4，25，15，2，13，18，17，5，8，24)，要按關鍵碼值遞增的次序排列，采用直接選擇排序法，一趟排序后的結果為()。A、2，9，4，25，15，16，13，18，17，5，8，24B、15，4，18，2，16，5，8，24，17，9，13，25C、9，4，16，15，2，13，18，17，5，8，24，25D、9，16，4，25，2，15，13，18，5，17，8，24標準答案：A知識點解析：暫無解析3、已知12個數(shù)據(jù)元素為34，76，45，18，26，54，92，60，25，37，03，78，對該數(shù)據(jù)按從小到大排序，若采用希爾排序方法排序，設第一趟排序的增量為6，第二趟排序的增量為3，則第二趟排序后的序列為()。A、60，34，25，18，03，54，92，76，45，37，26，78B、18，25，03，26，34，37，54，60，45，76，78，92C、18，03，25，34，26，45，37，60，54，92，76，78D、以上都不正確標準答案：C知識點解析：暫無解析4、對于初始關鍵字(49，38，65，97，76，13，27)，使用二路歸并排序，第一趟歸并之后其序列變?yōu)?)。A、38，49，65，97，13，27，76B、38，49，65，97，13，76，27C、13，27，38，49，65，76，97D、49，38，65，76，97，13，27標準答案：B知識點解析：暫無解析5、對隊列的基本運算，哪個說法是錯誤的?()A、將隊列初始化為空隊列B、求隊列的元素個數(shù)C、對隊尾元素的刪除D、取出隊頭元素標準答案：C知識點解析：暫無解析6、對于一維數(shù)組與線性表的敘述正確的是()。A、前者長度固定，后者長度可變B、兩者長度都固定C、兩者長度都可變D、后者長度固定，前者長度可變標準答案：A知識點解析：暫無解析7、對下列關鍵字序列用快速排序法進行排序時，速度最快的情形是()。A、21，25，5，17，9，23，30B、5，9，17，21，23，25，30C、25，23，30，17，21，5，9D、21，9，17，30，25，23，5標準答案：A知識點解析：選項A已經以5為基數(shù)分成了大于5和小于5的兩部分，這是快速排序的基本思想，其他選項則沒有這個特點，因此用快速排序方法對A排序最快。8、以下關于串的敘述中，哪一條是不正確的?()A、空串是由空格組成的串B、串是字符的有限序列C、模式匹配是串的一種重要運算D、串既可采用順序存儲，也可采用鏈接存儲標準答案：A知識點解析：暫無解析9、設棧S和隊列Q的初始狀態(tài)均為空，元素e1，e2，e3，e4，e5，e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的順序是e2，e4，e3，e6，e5，e1，則棧S的容量至少應是()。A、2B、3C、4D、6標準答案：B知識點解析：暫無解析10、一棵二叉樹的前根遍歷、后根遍歷和中根遍歷所產生的序列中，所有葉結點的先后順序是()。A、不相同B、完全相同C、前根遍歷與后根遍歷相同D、后根遍歷與中根遍歷相同標準答案：B知識點解析：對二叉樹的前根、后根、中根遍歷，在遍歷右子樹的葉子結點前一定會先遍歷左子樹的葉子結點，因此葉子結點的順序始終是一樣的。11、以下關于廣義表的敘述中，正確的是()。A、廣義表是0個或多個單元素或子表組成的有限序列B、廣義表至少有一個元素是子表C、廣義表不可以是自身的子表D、廣義表不能為空表標準答案：A知識點解析：暫無解析12、可以將一個堆序列看成是一棵完全二叉樹結點的層次序列，下面關鍵序列()就是一個堆。A、5，72，23，16，68，94B、68，94，23，72，5，16C、5，94，16，68，23，72D、5，23，16，68，94，72標準答案：D知識點解析：暫無解析13、二叉樹()個根結點，按一定的規(guī)則，任意一棵樹均可轉換成惟一對應的二叉樹。A、有且只有1B、有1或多于1C、有0或1D、有至少2標準答案：C知識點解析：暫無解析14、若對一個已經排好了序的序列進行排序，在下列四種排序方法中；哪種方法比較好?()A、冒泡法B、直接選擇法C、直接插入法D、歸并法標準答案：C知識點解析：暫無解析15、在下列存儲形式中，哪一個不是樹的存儲形式?()A、孩子兄弟表示法B、雙親表示法C、順序存儲表示法D、孩子鏈表表示法標準答案：C知識點解析：暫無解析16、設散列函數(shù)為H(k)=kmod7，現(xiàn)欲將關鍵碼23，14，9，6，30，12，18依次散列于地址O～6中，用線性探測法解決沖突，則在地址空間0～6中，得到的散列表是()。A、14，6，23，9，18，30，12B、14，18，23，9，30；12，6C、14，12，9，23，30，18，6D、6，23，30，14，18，12，9標準答案：B知識點解析：暫無解析17、一棵4層的滿二叉樹中，結點總數(shù)是()。A、31B、15C、7D、13標準答案：B知識點解析：暫無解析18、對排序文件的初始狀態(tài)不做任何要求的排序方法是()。A、直接插入排序和快速排序B、直接插入和歸并排序C、歸并排序與快速排序D、歸并排序與直接排序標準答案：A知識點解析：暫無解析19、以下關于順序存儲結構的敘述中，哪一條是不正確的?()A、存儲密度大B、邏輯上相鄰的結點物理上不必鄰接C、可以通過計算直接確定任意結點的存儲地址D、插入、刪除運算操作不方便標準答案：B知識點解析：暫無解析20、下列程序的時間復雜度為()。for(i=l；i＜2n；i++){y++；for(j=0；j＜a3n；j++)x++；}A、0(n-1)B、O(2n)C、0(n2)D、O(log2n)標準答案：C知識點解析：一個算法中所有語句重復執(zhí)行的次數(shù)之和構成了該算法的運算時間。題中語句y++執(zhí)行了2n-1次，語句x++執(zhí)行了(2n-1)(3n+1)=6n2-n-1次，則該算法的時間復雜度T(n)=6n2-n-1=O(n2)，21、對于一個棧，給出輸入項A，B，C。如果輸入項序列由A，B，C所組成，則不可能產生的輸出序列是()。A、BACB、ABCC、CABD、CBA標準答案：C知識點解析：此題主要考查棧的后進先出結構特點，輸入項序列為A，B，C，顯然可能輸出序列可以為CBA，若A，B，C都進棧后立即出棧，則輸出序列為ABC，A，B相繼進棧，B出棧，A再出棧，最后C入棧后出棧，則輸出序列為BAC。因此選項A，B，D組合都可能，對選項C，C是進棧的最后一個元素，卻是最先出棧元素，則必然是A，B，C進棧完了之后再出棧，這樣A不可能先于B出棧。22、在長度為n的順序表中，刪除第i個元素(0＜i＜n+1)時，需向前移動的元素個數(shù)為()。A、n-iB、n-i-1C、n-i+lD、i標準答案：A知識點解析：暫無解析數(shù)據(jù)結構與算法練習試卷第5套一、選擇題(本題共24題，每題1.0分，共24分。)1、以下關于順序存儲結構的敘述中，哪一條是不正確的?______。A、存儲密度大B、邏輯上相鄰的節(jié)點物理上不必鄰接C、可以通過計算直接確定第i個節(jié)點的存儲地址D、插入、刪除運算操作不方便標準答案：B知識點解析：暫無解析2、單鍵表的每個節(jié)點中包括一個指針link，它指向該節(jié)點的后繼節(jié)點?，F(xiàn)要將指針q指向的新節(jié)點插入到指針p指向的單鏈表節(jié)點之后，下面的操作序列中哪一個是正確的?______。A、q：=p^.link；p^.link：=q^.link；B、p^.link：=q^.link；q：=p^.link；C、q^.link：=p^.link；p^.link：=q；D、p^.link：=q；q^.link：=p^.link；標準答案：C知識點解析：暫無解析3、設有下三角矩陣A[0．．10,0．．10]，按行優(yōu)先順序存放其非零元素，每個非零元素占兩個字節(jié)，存放的基地址為100，則元素A[5,5]的存放地址為______。A、110B、120C、130D、140標準答案：D知識點解析：暫無解析4、棧S最多能容納4個元素?，F(xiàn)有6個元素按A、B、C、D、E、F的順序進棧，下列哪一個序列不是可能的出棧序列?______。A、A、D、E、C、B、FB、A、F、E、D、C、BC、C、B、E、D、A、FD、C、D、B、F、E、A標準答案：B知識點解析：暫無解析5、霍夫曼算法可以用于______。A、動態(tài)存儲管理B、表達式求值C、數(shù)據(jù)通信的二進制編碼D、城市間的交通網(wǎng)設計標準答案：C知識點解析：暫無解析6、設待排序關鍵碼序列為(25，18，9，33，67，82，53，95，12，70)，要按關鍵碼值遞增的順序進行排序，采取以第一個關鍵碼為分界元素的快速排序法，第一趟完成后關鍵碼33被放到了第幾個位置?______。A、3B、5C、7D、9標準答案：D知識點解析：暫無解析7、下列排序方法中，哪一種方法的總的關鍵碼比較次數(shù)與記錄的初始排列狀態(tài)無關?______。A、直接插入排序B、起泡排序C、快速排序D、直接選擇排序標準答案：B知識點解析：暫無解析8、以下關于數(shù)據(jù)的存儲結構的敘述中哪一條是正確的?______。A、數(shù)據(jù)的存儲結構是數(shù)據(jù)間關系的抽象描述B、數(shù)據(jù)的存儲結構是邏輯結構在計算機存儲器中的實現(xiàn)C、數(shù)據(jù)的存儲結構分為線性結構和非線性結構D、數(shù)據(jù)的存儲結構對數(shù)據(jù)運算的具體實現(xiàn)沒有影響標準答案：B知識點解析：暫無解析9、以下關于隊列的敘述中哪一條是不正確的?______。A、隊列的特點是先進先出B、隊列既能用順序方式存儲，也能用鏈接方式存儲C、隊列適用于二叉樹對稱序遍歷算法的實現(xiàn)D、隊列適用于樹的層次次序遍歷算法的實現(xiàn)標準答案：C知識點解析：暫無解析10、單鏈表的每個節(jié)點中包括一個指針link，它指向該節(jié)點的后繼節(jié)點。現(xiàn)要將指針q指向的新節(jié)點插入到指針p指向的單鏈表節(jié)點之后，下面的操作序列中哪一個是正確的?______。A、q：=p^.link；p^.link：=q^.link；B、p^.link：=q^.link；q：=p^.link；C、q^.link：=p^.link；p^link：=q；D、p^.link：=q；q^.link：=p^.link；標準答案：C知識點解析：暫無解析11、在順序表(3，6，8，10，12，15，16，18，21，25，30)中，用二分法查找關鍵碼值11，所需的關鍵碼比較次數(shù)為______。A、2B、3C、4D、5標準答案：C知識點解析：暫無解析12、設散列表的地址空間為0～10，散列函數(shù)為h(k)=kmod11，用線性探查法解決碰撞?，F(xiàn)從空的散列表開始，依次插入關鍵碼值95，14，27，68，82，則最后一個關鍵碼82的地址為：______。A、4B、5C、6D、7標準答案：C知識點解析：暫無解析13、設待排序關鍵碼序列為(25，18，9，33，67，82，53，95，12，70)，要按關鍵碼值遞增的順序進行排序，采取以第一個關鍵碼為分界元素的快速排序法，第一趟完成后關鍵碼96被放到了第幾個位置?______。A、7B、8C、9D、10標準答案：B知識點解析：暫無解析14、設平衡的二叉排序樹(AVL樹)的節(jié)點個數(shù)為n，則其平均檢索長度為______。A、O(1)B、O(log2n)C、O(n)D、O(nlog2n)標準答案：B知識點解析：暫無解析15、對于給出的一組權w={10,12,16,21,30}，通過霍夫曼算法求出的擴充二叉樹的帶權外部路徑長度為______。A、89B、189C、200D、300標準答案：C知識點解析：暫無解析16、如果一棵二叉樹節(jié)點的前序序列是A、B、C，后序序列是C、B、A，則該二叉樹節(jié)點的對稱序序列______。A、必為A、B、CB、必為A、C、BC、必為B、C、AD、不能確定標準答案：D知識點解析：暫無解析17、二維數(shù)組A[0．．8，0．．9]，其每個元素占2個字節(jié)，從首地址400開始，按行優(yōu)先順序存放，則元素A[8，5]的存儲地址為______。A、570B、506C、410D、482標準答案：A知識點解析：暫無解析18、以下哪一個不是棧的基本運算______?A、刪除棧頂元素B、刪除棧底元素C、判斷棧是否為空D、將棧置為空棧標準答案：B知識點解析：暫無解析19、以下關于數(shù)據(jù)結構的基本概念的敘述中哪一條是錯誤的?______。A、數(shù)據(jù)元素是數(shù)據(jù)的基本單位B、數(shù)據(jù)項是有獨立含義的數(shù)據(jù)最小單位C、數(shù)據(jù)結構概念包含的主要內容是數(shù)據(jù)的邏輯結構和數(shù)據(jù)的存儲結構D、數(shù)據(jù)的邏輯結構分為線性結構和非線性結構標準答案：A知識點解析：暫無解析20、以下關于鏈式存儲結構的敘述中哪一條是錯誤的?______。A、節(jié)點除自身信息外還包括指針域，因此存儲密度小于順序存儲結構B、邏輯上相鄰的節(jié)點物理上不必鄰接C、可以通過計算直接確定第i個節(jié)點的存儲地址D、插入、刪除運算操作方便，不必移動節(jié)點標準答案：C知識點解析：暫無解析21、棧結構不適用于下列哪一種應用?______。A、表達式求值B、樹的層次次序遍歷算法的實現(xiàn)C、二叉樹對稱序遍歷算法的實現(xiàn)D、快速排序算法的實現(xiàn)標準答案：B知識點解析：暫無解析22、設根節(jié)點的層次為0，則高度為k的二叉樹的最大節(jié)點數(shù)為______。A、2kB、2k-1C、2k+1D、2k+1-1標準答案：D知識點解析：暫無解析23、對線性表進行二分法查找，其前提條件是______。A、線性表以順序方式存儲，并已按關鍵碼值排好序B、線性表以順序方式存儲，并已按關鍵碼值的查找頻率排好序C、線性表以鏈接方式存儲，并已按關鍵碼值排好序D、線性表以鏈接方式存儲，并已按關鍵碼值的查找頻率排好序標準答案：A知識點解析：暫無解析24、在包含1000個元素的線性表中實現(xiàn)如下各運算，哪一個所需的執(zhí)行時間最長?______。A、線性表按順序方式存儲，在線性表的第10個節(jié)點后面插入一個新節(jié)點B、線性表按鏈接方式存儲，在線性表的第10個節(jié)點后面插入一個新節(jié)點C、線性表按順序方式存儲，刪除線性表的第990個節(jié)點D、線性表按鏈接方式存儲，刪除指針p所指向的節(jié)點標準答案：A知識點解析：暫無解析二、選擇題（含2小題）(本題共4題，每題1.0分，共4分。)下列問題基于如下描述：現(xiàn)有關鍵碼值分別為10、20、30、40的4個節(jié)點，按所有可能的插入順序去構造二叉排序樹。25、能構造出多少棵不同的二叉排序樹?______。A、24B、14C、10D、8標準答案：B知識點解析：暫無解析26、這些二叉排序樹中有多少棵是最佳二叉排序樹?______。A、6B、5C、4D、3標準答案：B知識點解析：暫無解析下列問題基于下面的敘述；某二叉樹節(jié)點的前序序列為E、A、C、B、D、G、F，對稱序序列為A、B、C、D、E、F、G。27、該二叉樹節(jié)點的后序序列為______。A、B、D、C、A、F、G、EB、B、D、C、F、A、G、EC、E、G、F、A、C、D、BD、E、G、A、C、D、F、B標準答案：A知識點解析：暫無解析28、該二叉樹對應的樹林包括多少棵樹?______。A、1B、2C、3D、4標準答案：B知識點解析：暫無解析數(shù)據(jù)結構與算法練習試卷第6套一、填空題(本題共11題，每題1.0分，共11分。)1、設只包含根節(jié)點的二叉樹的高度為0，則高度為k的二叉樹的最小節(jié)點數(shù)為_____。標準答案：k+1知識點解析：暫無解析2、在完全二叉樹的順序存儲中，若節(jié)點i有左子女，則其左子女是節(jié)點_____。標準答案：2i知識點解析：暫無解析3、二叉樹是節(jié)點的有限集合，這個有限集合或者為_____，或者由一個根節(jié)點及兩棵不相交的，分別稱作為根的左子樹和右子樹的二叉樹組成。標準答案：空集知識點解析：暫無解析4、m階B樹的根節(jié)點若不是葉節(jié)點，那么它至多有m棵子樹，至少有_____棵子樹。標準答案：2知識點解析：暫無解析5、對于關鍵碼序列18，30，35，10，46，38，5，40進行堆排序(假定堆的根節(jié)點為最小關鍵碼)，在初始建堆過程中需進行的關鍵碼交換次數(shù)為_____。標準答案：3知識點解析：暫無解析6、在有n個節(jié)點的二叉樹的llink-rlink法存儲表示中，n個節(jié)點所含有的2n個指針中，必有_____個為空指針。標準答案：n+1知識點解析：暫無解析7、對于給出的一組權w={5，6，8，12}，通過霍夫曼算法求出的擴充二叉樹的帶權外部路徑長度為_____。標準答案：61知識點解析：暫無解析8、對n個記錄的文件進行快速排序，最壞情況下的執(zhí)行時間為_____。標準答案：O(n2)知識點解析：暫無解析9、散列法存儲中處理碰撞的方法主要有兩類：拉鏈法和_____。標準答案：開放定址法知識點解析：暫無解析10、某二叉樹節(jié)點的對稱序序列為A、B、C、D、E、F、G，后序序列為B、D、C、A、F、G、E。則該二叉樹對應的樹林包括_____棵樹。標準答案：2知識點解析：暫無解析11、對線性表進行二分法檢索，其前提條件是：線性表以_____方式存儲，并且按關鍵碼值排好序。標準答案：順序知識點解析：暫無解析數(shù)據(jù)結構與算法練習試卷第7套一、選擇題(本題共23題，每題1.0分，共23分。)1、一棵具有5層的完全二叉樹中，結點總數(shù)最少是()。A、15B、5C、16D、31標準答案：C知識點解析：具有5層的樹結點最少的是完全二叉樹，第5層只有一個結點，其他4層是由滿二叉樹構成。2、設n、m為一棵二叉樹上的兩個結點，在中序遍歷時，若n在m的前面，則()。A、n為樹的左子樹上的結點，m為右子樹上的結點B、n是m的祖先結點C、n的層次比m層次高D、n在m的左方標準答案：D知識點解析：暫無解析3、對于深度為n，結點數(shù)為k，有m個葉子結點的滿二叉樹，下列關系正確的是()。A、k=m+nB、k=-2"-1C、n+m=2kD、re=k-1標準答案：B知識點解析：暫無解析4、快速排序方法在()條件下最不利于發(fā)揮其長處。A、待排序序列中含有多個相同關鍵字B、待排序序列數(shù)據(jù)基本有序C、待排序序列數(shù)據(jù)量很大D、待排序序列元素個數(shù)為奇數(shù)標準答案：C知識點解析：暫無解析5、在每一趟排序時，都將待排序序列中最大關鍵字選出來，并將此關鍵字從待排序序列中刪除，繼續(xù)對剩余元素進行同樣操作的排序方法稱之為()。A、快速排序B、堆排序C、起泡捧序D、選擇排序標準答案：C知識點解析：暫無解析6、設有1000個無序的元素，希望用最快的方式挑選出其中前10個最大元素，效率最高的排序方法是()。A、堆排序B、快速排序C、基數(shù)排序D、起泡排序標準答案：A知識點解析：暫無解析7、設哈希表長m=14，哈希函數(shù)H(key)=key%ll，表中已經有4個結點：addr(13)=4；addr(28)=5addr(51)=6；addr(77)=7如果用線性探測再與散列法處理沖突，關鍵字為49的結點地址為()。A、8B、5C、9D、3標準答案：A知識點解析：暫無解析8、對于一個序列中的若干元素，若想得到某個元素之前的部分排序，最好采用什么排序方法?()A、快速排序B、堆排序C、基數(shù)排序D、希爾排序標準答案：B知識點解析：暫無解析9、采用順序查找法查找長度為n的線性表時，每個元素的平均查找長度為()，A、(n+1)/2B、(n-1)/2C、n/2D、n標準答案：A知識點解析：暫無解析10、一個有序表{2，4，7，12，23，45，62，76，77，89，93，95，100}，若采用二分查找法查找值為93的關鍵字，需要()次比較才能查找成功。A、1B、8C、2D、4標準答案：D知識點解析：暫無解析11、一棵二叉樹的前序遍歷結點順序為EACBDGF，中序遍歷結點順序為ABCDEFG，則其后序遍歷結點順序為()。A、EGFACDBB、EGACDFBC、BDCAFGED、BDCFAGE標準答案：C知識點解析：由前序遍歷序列得知E是根結點，由中序序列可知：A、B、C、D在左子樹上，且是左子樹的中序序列，A是左子樹上的根，C是A的右子結點，B、D分別是C的左右結點，F(xiàn)、G在右子樹上，且是右子樹上的中序序列，G是右子樹上的根，F(xiàn)是G的左子結點。由此描繪一下該二叉樹，就可得到答案A。12、對以下關鍵字序列用快速排序方法排序速度最慢的是()。A、{15，21，5，12，9，20，31}B、{5，9，12，15，20，21，31)C、{15，9，12，31，21，20，5}D、{21，20，31，12，15，5，9)標準答案：B知識點解析：暫無解析13、用堆排序方法，在最壞情況下的時間復雜度為()。A、O(n+1)B、O(n2)C、O(log2n)D、O(nlog2n)標準答案：D知識點解析：暫無解析14、給定如下一組關鍵字序列{49，38，65，97，76，13，27，49，55，04}，采用希爾排序，則第二趟排序后的結果為()。A、13，04，49，38，27，49，55，65，97，76B、13，27，49，55，04，49，38，65，97，76C、04，13，27，49，49，38，55，65，76，97D、04，13，27，38，49，49，55，65，76，97標準答案：A知識點解析：暫無解析15、關于二叉樹，下列說法不正確的是()。A、在第i層上最多有2i-1個結點B、深度為k的二叉樹最多有2k-1個結點C、相同層次的滿二叉樹結點數(shù)比完全二叉樹結點多D、深度為k的滿二叉樹結點數(shù)一定為2k-1個標準答案：C知識點解析：暫無解析16、元素ABCDEF按序進入隊列，則隊列的出隊順序為()。A、FEDCBAB、ABCDEFC、DCBAEFD、ABFEDC標準答案：B知識點解析：暫無解析17、在判斷表達式中括號是否匹配的算法中，采用()數(shù)據(jù)結構最佳。A、線性表的順序存儲結構B、線性表的鏈式存儲結構C、廣義表D、棧標準答案：D知識點解析：暫無解析18、若待排序序列已基本有序，要使它完全有序，從關鍵碼的比較次數(shù)和移動次數(shù)考慮，應當采用的排序方法是()。A、直接插入排序B、快速排序C、直接選擇排序D、歸并排序標準答案：A知識點解析：暫無解析19、對一棵二叉樹的中序遍歷序列中，根結點的左邊包括()。A、左子樹上的葉子結點B、右子樹上的所有結點C、左子樹上的所有結點D、右子樹上的葉子結點標準答案：C知識點解析：暫無解析20、線索二叉樹是一種()結構。A、邏輯B、存儲C、線性D、物理標準答案：D知識點解析：暫無解析21、下圖①所示是一棵二叉樹，其后序遍歷序列是()。A、DEBGFCAB、ABCDEFGC、DEBFGCAD、DBEACGF標準答案：A知識點解析：暫無解析22、如下圖②所示，下列說法正確的是()。A、此樹不是滿二叉樹也不是完全二叉樹B、中序遍歷序列是HIDBEACFGC、此樹是完全二叉樹，也是滿二叉樹D、以上說法均不正確標準答案：D知識點解析：暫無解析23、棧結構通常采用的兩種存儲結構是()。A、順序存儲結構和鏈表存儲結構B、散列方式和索引方式C、后進先出結構和順序存儲結構D、線性存儲結構和非線性存儲結構標準答案：A知識點解析：暫無解析數(shù)據(jù)結構與算法練習試卷第8套一、選擇題(本題共46題，每題1.0分，共46分。)1、算法的時間復雜度是指______。A、執(zhí)行算法程序所需要的時間B、算法程序的長度C、算法執(zhí)行過程中所需要的基本運算次數(shù)D、算法程序中的指令條數(shù)標準答案：C知識點解析：暫無解析2、數(shù)據(jù)結構作為計算機的一門學科，主要研究數(shù)據(jù)的邏輯結構、對各種數(shù)據(jù)結構進行的運算，以及______。A、數(shù)據(jù)的存儲結構B、計算方法C、數(shù)據(jù)映像D、邏輯存儲標準答案：A知識點解析：暫無解析3、串的長度是______。A、串中不同字符的個數(shù)B、串中不同字母的個數(shù)C、串中所含字符的個數(shù)且字符個數(shù)大于零D、串中所含字符的個數(shù)標準答案：D知識點解析：暫無解析4、在計算機中，算法是指______。A、加工方法B、解題方案的準確而完整的描述C、排序方法D、查詢方法標準答案：B知識點解析：暫無解析5、在待排序的元素序列基本有序的前提下，效率最高的排序算法是______。A、冒泡排序B、選擇排序C、快速排序D、歸并排序標準答案：A知識點解析：暫無解析6、數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的______。A、存儲結構B、物理結構C、邏輯結構D、物理和存儲結構標準答案：C知識點解析：暫無解析7、樹是結點的集合，它的根結點數(shù)目是______。A、有且只有1B、1或多于1C、0或1D、至少2標準答案：A知識點解析：暫無解析8、在深度為5的滿二叉樹中，葉子結點的個數(shù)為______。A、32B、31C、16D、15標準答案：B知識點解析：暫無解析9、一些重要的程序語言(如C語言和Pascal語言)允許過程的遞歸調用。而實現(xiàn)遞歸調用中的存儲分配通常用______。A、棧B、堆C、數(shù)組D、鏈表標準答案：A知識點解析：暫無解析10、如果進棧序列為e1,e2,e3,e4，則可能的出棧序列是______。A、e3,e1,e4,e2B、e2,e4,e3,e1C、e3,e4,e1,e2D、任意順序標準答案：B知識點解析：暫無解析11、數(shù)據(jù)的______包括集合、線性結構、樹型結構和圖狀結構四種基本類型。A、算法描述B、基本運算C、邏輯結構D、存儲結構標準答案：C知識點解析：暫無解析12、數(shù)據(jù)的存儲結構包括順序、______、索引和散列四種基本類型。A、向量B、數(shù)組C、集合D、鏈式標準答案：D知識點解析：暫無解析把算法工作量大小和實現(xiàn)算法所需存儲單元多少分別稱為算法的①和②。①13、把算法工作量大小和實現(xiàn)算法所需存儲單元多少分別稱為算法的①和②。①A、可實現(xiàn)性B、時間復雜度C、困難度D、計算有效性標準答案：B知識點解析：暫無解析14、A、可行性B、高效性C、可實現(xiàn)性D、空間復雜度標準答案：D知識點解析：暫無解析15、單鏈表要求內存中可用存儲單元的地址______。A、必須是連續(xù)的B、一定是不連續(xù)的C、部分地址必須是連續(xù)的D、可以是連續(xù)的，也可以是不連續(xù)的標準答案：D知識點解析：暫無解析16、若某鏈表最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，則采用______存儲方式最節(jié)省時間。A、單鏈表B、雙鏈表C、單循環(huán)鏈表D、帶頭結點的雙循環(huán)鏈表標準答案：D知識點解析：暫無解析17、在循環(huán)雙鏈表的p結點之后插入s結點的操作是______。A、p→next=s；p→next→prior=s;s→prior=p；s→next=p→next；B、s→!next=p；s→next=p→n