-?數據構造與算法?復習題一、選擇題。1．在數據構造中，從邏輯上可以把數據構造分為C。A．動態構造和靜態構造B．緊湊構造和非緊湊構造C．線性構造和非線性構造D．內部構造和外部構造2．數據構造在計算機內存中的表示是指A。A．數據的存儲構造B．數據構造C．數據的邏輯構造D．數據元素之間的關系3．在數據構造中，與所使用的計算機無關的是數據的A構造。A．邏輯B．存儲C．邏輯和存儲D．物理4．在存儲數據時，通常不僅要存儲各數據元素的值，而且還要存儲C。A．數據的處理方法B．數據元素的類型C．數據元素之間的關系D．數據的存儲方法5．在決定選取何種存儲構造時，一般不考慮A。A．各結點的值如何B．結點個數的多少C．對數據有哪些運算D．所用的編程語言實現這種構造是否方便。6．以下說法正確的選項是D。A．數據項是數據的根本單位B．數據元素是數據的最小單位C．數據構造是帶構造的數據項的集合D．一些外表上很不一樣的數據可以有一樣的邏輯構造7．算法分析的目的是C，算法分析的兩個主要方面是A。A．找出數據構造的合理性B．研究算法中的輸入和輸出的關系C．分析算法的效率以求改進C．分析算法的易讀性和文檔性A．空間復雜度和時間復雜度B．正確性和簡明性C．可讀性和文檔性D．數據復雜性和程序復雜性8．下面程序段的時間復雜度是O(n2)。s=0;for(I=0;i<n;i++) for(j=0;j<n;j++) s+=B[i][j];sum=s;9．下面程序段的時間復雜度是O(n*m)。for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]＝0;10．下面程序段的時間復雜度是O(log3n)。i＝0；while〔i<=n〕 i=i*3；11．在以下的表達中，正確的選項是B。A．線性表的順序存儲構造優于鏈表存儲構造B．二維數組是其數據元素為線性表的線性表C．棧的操作方式是先進先出D．隊列的操作方式是先進后出12．通常要求同一邏輯構造中的所有數據元素具有一樣的特性，這意味著B。A．數據元素具有同一特點B．不僅數據元素所包含的數據項的個數要一樣，而且對應的數據項的類型要一致C．每個數據元素都一樣D．數據元素所包含的數據項的個數要相等13．鏈表不具備的特點是A。A．可隨機訪問任一結點B．插入刪除不需要移動元素C．不必事先估計存儲空間D．所需空間與其長度成正比14．不帶頭結點的單鏈表head為空的判定條件是A。A．head==NULLBhead->ne*t==NULLC．head->ne*t==headDhead!=NULL15．帶頭結點的單鏈表head為空的判定條件是B。A．head==NULLBhead->ne*t==NULLC．head->ne*t==headDhead!=NULL16．假設*表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點，則采用D存儲方式最節省運算時間。A．單鏈表B．給出表頭指針的單循環鏈表C．雙鏈表D．帶頭結點的雙循環鏈表17．需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲構造是B。A．單鏈表B．靜態鏈表C．線性鏈表D．順序存儲構造18．非空的循環單鏈表head的尾結點〔由p所指向〕滿足C。A．p->ne*t==NULLB．p==NULLC．p->ne*t==headD．p==head19．在循環雙鏈表的p所指的結點之前插入s所指結點的操作是D。A．p->prior=s；s->ne*t=p；p->prior->ne*t=s；s->prior=p->priorB．p->prior=s；p->prior->ne*t=s；s->ne*t=p；s->prior=p->priorC．s->ne*t=p；s->prior=p->prior；p->prior=s；p->prior->ne*t=sD．s->ne*t=p；s->prior=p->prior；p->prior->ne*t=s；p->prior=s20．如果最常用的操作是取第i個結點及其前驅，則采用D存儲方式最節省時間。A．單鏈表B．雙鏈表C．單循環鏈表D．順序表21．在一個具有n個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是B。A．O〔1〕B．O〔n〕C．O〔n2〕D．O〔nlog2n〕22．在一個長度為n〔n>1〕的單鏈表上，設有頭和尾兩個指針，執行B操作與鏈表的長度有關。A．刪除單鏈表中的第一個元素B．刪除單鏈表中的最后一個元素C．在單鏈表第一個元素前插入一個新元素D．在單鏈表最后一個元素后插入一個新元素23．與單鏈表相比，雙鏈表的優點之一是D。A．插入、刪除操作更簡單B．可以進展隨機訪問C．可以省略表頭指針或表尾指針D．順序訪問相鄰結點更靈活24．如果對線性表的操作只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用。A．只有表頭指針沒有表尾指針的循環單鏈表B．只有表尾指針沒有表頭指針的循環單鏈表C．非循環雙鏈表D．循環雙鏈表25．在長度為n的順序表的第i個位置上插入一個元素〔1≤i≤n+1〕，元素的移動次數為：A。A．n–i+1B．n–iC．iD．i–126．對于只在表的首、尾兩端進展插入操作的線性表，宜采用的存儲構造為C。A．順序表B．用頭指針表示的循環單鏈表C．用尾指針表示的循環單鏈表D．單鏈表27．下述哪一條是順序存儲構造的優點.C。插入運算方便B可方便地用于各種邏輯構造的存儲表示存儲密度大D刪除運算方便28．下面關于線性表的表達中，錯誤的選項是哪一個.B。線性表采用順序存儲，必須占用一片連續的存儲單元線性表采用順序存儲，便于進展插入和刪除操作。線性表采用鏈式存儲，不必占用一片連續的存儲單元線性表采用鏈式存儲，便于進展插入和刪除操作。29．線性表是具有n個B的有限序列。A．字符B．數據元素C．數據項D．表元素30．在n個結點的線性表的數組實現中，算法的時間復雜度是O〔1〕的操作是A。A．訪問第i〔1<=i<=n〕個結點和求第i個結點的直接前驅〔1<i<=n〕B．在第i〔1<=i<=n〕個結點后插入一個新結點C．刪除第i〔1<=i<=n〕個結點D．以上都不對31．假設長度為n的線性表采用順序存儲構造，在其第i個位置插入一個新元素的算法的時間復雜度為C。A．O(0)B．O(1)C．O(n)D．O(n2)32．對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為C。A．O(n)O(n)B．O(n)O(1)C．O(1)O(n)D．O(1)O(1)33．線性表〔a1,a2,?,an〕以鏈式方式存儲，訪問第i位置元素的時間復雜度為C。A．O(0)B．O(1)C．O(n)D．O(n2)34．單鏈表中，增加一個頭結點的目的是為了C。A．使單鏈表至少有一個結點 B．標識表結點中首結點的位置C．方面運算的實現D．說明單鏈表是線性表的鏈式存儲35．在單鏈表指針為p的結點之后插入指針為s的結點，正確的操作是B。A．p->ne*t=s；s->ne*t=p->ne*tB．s->ne*t=p->ne*t；p->ne*t=s;C．p->ne*t=s；p->ne*t=s->ne*tD．p->ne*t=s->ne*t；p->ne*t=s36．線性表的順序存儲構造是一種A。A．隨機存取的存儲構造B．順序存取的存儲構造C．索引存取的存儲構造D．Hash存取的存儲構造37．棧的特點是B，隊列的特點是A。A．先進先出B．先進后出38．棧和隊列的共同點是C。A．都是先進后出B．都是先進先出C．只允許在端點處插入和刪除元素D．沒有共同點39．一個棧的進棧序列是a，b，c，d，e，則棧的不可能的輸出序列是C。A．edcbaB．decbaC．dceabD．abcde40．設有一個棧，元素依次進棧的順序為A、B、C、D、E。以下C是不可能的出棧序列。A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A41．以下B不是隊列的根本運算.A．從隊尾插入一個新元素B．從隊列中刪除第i個元素C．判斷一個隊列是否為空D．讀取隊頭元素的值42．假設一個棧的進棧序列是1，2，3，，n，其輸出序列為p1，p2，p3，?，pn，假設p1＝n，則pi為C。A．iB．n－iC．n－i＋1D．不確定43．判定一個順序棧st〔最多元素為Ma*Size〕為空的條件是B。A．st->top!=-1B．st->top==-1C．st->top!=Ma*SizeD．st->top==Ma*Size44．判定一個順序棧st〔最多元素為Ma*Size〕為滿的條件是D。A．st->top!=-1B．st->top==-1C．st->top!=Ma*SizeD．st->top==Ma*Size45．一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是B。A．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，146．判定一個循環隊列qu〔最多元素為Ma*Size〕為空的條件是C。A．qu->rear–qu->front==Ma*SizeB．qu->rear–qu->front-1==Ma*SizeC．qu->rear==qu->frontD．qu->rear=qu->front-147．在循環隊列中，假設front與rear分別表示對頭元素和隊尾元素的位置，則判斷循環隊列空的條件是C。A．front==rear+1B．rear==front+1C．front==rearD．front==048．向一個棧頂指針為h的帶頭結點的鏈棧中插入指針s所指的結點時，應執行D操作。A．h->ne*t=s;B．s->ne*t=h;C．s->ne*t=h;h=s;D．s->ne*t=h->ne*t;h->ne*t=s;49．輸入序列為ABC，可以變為CBA時，經過的棧操作為B。A．push，pop，push，pop，push，popB．push，push，push，pop，pop，popC．push，push，pop，pop，push，popD．push，pop，push，push，pop，pop50．假設棧采用順序存儲方式存儲，現兩棧共享空間V[1m]，top[1]、top[2]分別代表第1和第2個棧的棧頂，棧1的底在V[1]，棧2的底在V[m]，則棧滿的條件是B。A．|top[2]-top[1]|=0B．top[1]+1=top[2]C．top[1]+top[2]=mD．top[1]=top[2]51．設計一個判別表達式中左、右括號是否配對出現的算法，采用D數據構造最正確。A．線性表的順序存儲構造B．隊列C．線性表的鏈式存儲構造D．棧52．允許對隊列進展的操作有D。A．對隊列中的元素排序B．取出最近進隊的元素C．在隊頭元素之前插入元素D．刪除隊頭元素53．對于循環隊列D。A．無法判斷隊列是否為空B．無法判斷隊列是否為滿C．隊列不可能滿D．以上說法都不對54．假設用一個大小為6的數值來實現循環隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再參加兩個元素后，rear和front的值分別為B。A．1和5B．2和4C．4和2D．5和155．隊列的“先進先出〞特性是指D。A．最早插入隊列中的元素總是最后被刪除B．當同時進展插入、刪除操作時，總是插入操作優先C．每當有刪除操作時，總是要先做一次插入操作D．每次從隊列中刪除的總是最早插入的元素56．和順序棧相比，鏈棧有一個比較明顯的優勢是A。A．通常不會出現棧滿的情況B．通常不會出現棧空的情況C．插入操作更容易實現D．刪除操作更容易實現57．用不帶頭結點的單鏈表存儲隊列，其頭指針指向隊頭結點，尾指針指向隊尾結點，則在進展出隊操作時C。A．僅修改隊頭指針B．僅修改隊尾指針C．隊頭、隊尾指針都可能要修改D．隊頭、隊尾指針都要修改58．假設串S=‘software’，其子串的數目是B。A．8B．37C．36D．959．串的長度是指B。A．串中所含不同字母的個數B．串中所含字符的個數C．串中所含不同字符的個數D．串中所含非空格字符的個數60．串是一種特殊的線性表，其特殊性表達在B。A．可以順序存儲B．數據元素是一個字符C．可以鏈式存儲D．數據元素可以是多個字符61．設有兩個串p和q，求q在p中首次出現的位置的運算稱為B。A．連接B．模式匹配C．求子串D．求串長62．數組A中，每個元素的長度為3個字節，行下標i從1到8，列下標j從1到10，從首地址SA開場連續存放的存儲器內，該數組按行存放，元素A[8][5]的起始地址為C。A．SA＋141B．SA＋144C．SA＋222D．SA＋22563．數組A中，每個元素的長度為3個字節，行下標i從1到8，列下標j從1到10，從首地址SA開場連續存放的存儲器內，該數組按行存放，元素A[5][8]的起始地址為C。A．SA＋141B．SA＋180C．SA＋222D．SA＋22564．假設聲明一個浮點數數組如下：froataverage[]=newfloat[30];假設該數組的內存起始位置為200，average[15]的內存地址是C。A．214B．215C．260D．25665．設二維數組A[1?m,1?n]按行存儲在數組B中，則二維數組元素A[i,j]在一維數組B中的下標為A。A．n*(i-1)+jB．n*(i-1)+j-1C．i*(j-1)D．j*m+i-166．有一個100×90的稀疏矩陣，非0元素有10，設每個整型數占2個字節，則用三元組表示該矩陣時，所需的字節數是B。A．20B．66C．18000D．3367．數組A[0?4，-1?-3，5?7]中含有的元素個數是A。A．55B．45C．36D．1668．對矩陣進展壓縮存儲是為了D。A．方便運算B．方便存儲C．提高運算速度D．減少存儲空間69．設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a1，1為第一個元素，其存儲地址為1，每個元素占1個地址空間，則a8，5的地址為B。A．13B．33C．18D．4070．稀疏矩陣一般的壓縮存儲方式有兩種，即C。A．二維數組和三維數組B．三元組和散列C．三元組和十字鏈表D．散列和十字鏈表71．樹最適合用來表示C。A．有序數據元素B．無序數據元素C．元素之間具有分支層次關系的數據D．元素之間無聯系的數據72．深度為5的二叉樹至多有C個結點。A．16B．32C．31C．1073．對一個滿二叉樹，m個葉子，n個結點，深度為h，則D。A．n=h+mBh+m=2nCm=h-1Dn=2h-174．任何一棵二叉樹的葉子結點在前序、中序和后序遍歷序列中的相對次序A。A．不發生改變B．發生改變C．不能確定D．以上都不對75．在線索化樹中，每個結點必須設置一個標志來說明它的左、右鏈指向的是樹構造信息，還是線索化信息，假設0標識樹構造信息，1標識線索，對應葉結點的左右鏈域，應標識為__D__。A．00B．01C．10D．1176．在下述論述中，正確的選項是D。①只有一個結點的二叉樹的度為0；②二叉樹的度為2；③二叉樹的左右子樹可任意交換；④深度為K的順序二叉樹的結點個數小于或等于深度一樣的滿二叉樹。A．①②③B．②③④C．②④D．①④77．設森林F對應的二叉樹為B，它有m個結點，B的根為p，p的右子樹的結點個數為n，森林F中第一棵樹的結點的個數是A。A．m-nB．m-n-1C．n+1D．不能確定78．假設一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點的個數是B。A．9B．11C．15D．不能確定79．具有10個葉子結點的二叉樹中有B個度為2的結點。A．8B．9C．10D．1180．在一個無向圖中，所有頂點的度數之和等于所有邊數的C倍。A．1/2B1C2D481．在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的B倍。A．1/2B1C2D482．*二叉樹結點的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結點數目為：CA．3B．2C．4D．583．一算術表達式的中綴形式為A＋B*C–D/E，后綴形式為ABC*+DE/–，其前綴形式為D。A．–A+B*C/DEB．–A+B*CD/EC–+*ABC/DED．–+A*BC/DEabcdef84．一個圖，如下列圖，假設從頂點a出發按深度搜索法進展遍歷，則可能得到的一種頂點序列為____D___abcdef①A．a，b，e，c，d，fB．a，c，f，e，b，dC．a，e，b，c，f，d，D．a，e，d，f，c，b②A．a，b，c，e，d，fB．a，b，c，e，f，dC．a，e，b，c，f，d，D．a，c，f，d，e，b85．采用鄰接表存儲的圖的深度優先遍歷算法類似于二叉樹的___A____。A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷86．采用鄰接表存儲的圖的廣度優先遍歷算法類似于二叉樹的___D____。A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷87．具有n個結點的連通圖至少有A條邊。A．n-1B．nC．n(n-1)/2D．2n88．廣義表〔〔a〕，a〕的表頭是C，表尾是C。A．aB〔〕C〔a〕D〔〔a〕〕89．廣義表〔〔a〕〕的表頭是C，表尾是B。A．aB〔〕C〔a〕D〔〔a〕〕90．順序查找法適合于存儲構造為B的線性表。A散列存儲B順序存儲或鏈式存儲C壓縮存儲D索引存儲91．對線性表進展折半查找時，要求線性表必須B。A以順序方式存儲B以順序方式存儲，且結點按關鍵字有序排列C以鏈式方式存儲D以鏈式方式存儲，且結點按關鍵字有序排列92．采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為D。AO(n2)BO(nlog2n)CO(n)DO(log2n)93．有一個有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當折半查找值為82的結點時，C次比較后查找成功。A．11B5C4D894．二叉樹為二叉排序樹的充分必要條件是其任一結點的值均大于其左孩子的值、小于其右孩子的值。這種說法B。A正確B錯誤95．下面關于B樹和B+樹的表達中，不正確的結論是A。AB樹和B+樹都能有效的支持順序查找BB樹和B+樹都能有效的支持隨機查找CB樹和B+樹都是平衡的多叉樹DB樹和B+樹都可用于文件索引構造96．以下說法錯誤的選項是B。A．散列法存儲的思想是由關鍵字值決定數據的存儲地址B．散列表的結點中只包含數據元素自身的信息，不包含指針。C．負載因子是散列表的一個重要參數，它反映了散列表的飽滿程度。D．散列表的查找效率主要取決于散列表構造時選取的散列函數和處理沖突的方法。97．查找效率最高的二叉排序樹是C。A．所有結點的左子樹都為空的二叉排序樹。B．所有結點的右子樹都為空的二叉排序樹。C．平衡二叉樹。D．沒有左子樹的二叉排序樹。98．排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進展比較，將其放入已排序序列的正確位置上的方法，稱為C。A．希爾排序B。冒泡排序C插入排序D。選擇排序99．在所有的排序方法中，關鍵字比較的次數與記錄的初始排列次序無關的是D。A．希爾排序B．冒泡排序C．直接插入排序D．直接選擇排序100．堆是一種有用的數據構造。以下關鍵碼序列D是一個堆。A．94,31,53,23,16,72B．94,53,31,72,16,23C．16,53,23,94,31,72D．16,31,23,94,53,72101．堆排序是一種B排序。A．插入B．選擇C．交換D．歸并102．D在鏈表中進展操作比在順序表中進展操作效率高。A．順序查找B．折半查找C．分塊查找D．插入103．直接選擇排序的時間復雜度為D。〔n為元素個數〕A．O〔n)B．O(log2n)C．O(nlog2n)D．O(n2)二、填空題。1．數據邏輯構造包括線性構造、樹形構造和圖狀構造三種類型，樹形構造和圖狀構造合稱非線性構造。2．數據的邏輯構造分為集合、線性構造、樹形構造和圖狀構造4種。3．在線性構造中，第一個結點沒有前驅結點，其余每個結點有且只有1個前驅結點；最后一個結點沒有后續結點，其余每個結點有且只有1個后續結點。4．線性構造中元素之間存在一對一關系，樹形構造中元素之間存在一對多關系，圖形構造中元素之間存在多對多關系。5．在樹形構造中，樹根結點沒有前驅結點，其余每個結點有且只有1個前驅結點；葉子結點沒有后續結點，其余每個結點的后續結點可以任意多個。6．數據構造的根本存儲方法是順序、鏈式、索引和散列存儲。7．衡量一個算法的優劣主要考慮正確性、可讀性、強健性和時間復雜度與空間復雜度。8．評估一個算法的優劣，通常從時間復雜度和空間復雜度兩個方面考察。9．算法的5個重要特性是有窮性、確定性、可行性、輸入和輸出。10．在一個長度為n的順序表中刪除第i個元素時，需向前移動n-i-1個元素。11．在單鏈表中，要刪除*一指定的結點，必須找到該結點的前驅結點。12．在雙鏈表中，每個結點有兩個指針域，一個指向前驅結點，另一個指向后繼結點。13．在順序表中插入或刪除一個數據元素，需要平均移動n個數據元素，移動數據元素的個數與位置有關。14．當線性表的元素總數根本穩定，且很少進展插入和刪除操作，但要求以最快的速度存取線性表的元素是，應采用順序存儲構造。15．根據線性表的鏈式存儲構造中每一個結點包含的指針個數，將線性鏈表分成單鏈表和雙鏈表。16．順序存儲構造是通過下標表示元素之間的關系的；鏈式存儲構造是通過指針表示元素之間的關系的。17．帶頭結點的循環鏈表L中只有一個元素結點的條件是L->ne*t->ne*t=L。18．棧是限定僅在表尾進展插入或刪除操作的線性表，其運算遵循后進先出的原則。19．空串是零個字符的串，其長度等于零。空白串是由一個或多個空格字符組成的串，其長度等于其包含的空格個數。20．組成串的數據元素只能是單個字符。21．一個字符串中任意個連續字符構成的局部稱為該串的子串。22．子串〞str〞在主串〞datastructure〞中的位置是5。23．二維數組M的每個元素是6個字符組成的串，行下標i的*圍從0到8，列下標j的*圍從1到10，則存放M至少需要540個字節；M的第8列和第5行共占108個字節。24．稀疏矩陣一般的壓縮存儲方法有兩種，即三元組表和十字鏈表。25．廣義表〔〔a〕，〔〔b〕，c〕，〔〔〔d〕〕〕〕的長度是3，深度是4。26．在一棵二叉樹中，度為零的結點的個數為n0，度為2的結點的個數為n2，則有n0＝n2+1。27．在有n個結點的二叉鏈表中，空鏈域的個數為__n+1__。28．一棵有n個葉子結點的哈夫曼樹共有__2n-1_個結點。29．深度為5的二叉樹至多有31個結點。30．假設*二叉樹有20個葉子結點，有30個結點僅有一個孩子，則該二叉樹的總結點個數為69。31．*二叉樹的前序遍歷序列是abdgcefh，中序序列是dgbaechf，其后序序列為gdbehfca。32．線索二叉樹的左線索指向其遍歷序列中的前驅，右線索指向其遍歷序列中的后繼。33．在各種查找方法中，平均查找長度與結點個數n無關的查找方法是散列查找法。34．在分塊索引查找方法中，首先查找索引表，然后查找相應的塊表。35．一個無序序列可以通過構造一棵二叉排序樹而變成一個有序序列，構造樹的過程即為對無序序列進展排序的過程。36．具有10個頂點的無向圖，邊的總數最多為__45__。37．圖G的鄰接表如下列圖，其從頂點v1出發的深度優先搜索序列為_v1v2v3v6v5v4_，其從頂點v1出發的廣度優先搜索序列為_v1v2v5v4v3v6__。vv1v2v3v4∧v5v6∧v3v2v6∧v4v5∧v5v6v3∧v4∧38．索引是為了加快檢索速度而引進的一種數據構造。一個索引隸屬于*個數據記錄集，它由假設干索引項組成，索引項的構造為關鍵字和關鍵字對應記錄的地址。39．Prim算法生成一個最小生成樹每一步選擇都要滿足邊的總數不超過n-1，當前選擇的邊的權值是候選邊中最小的，選中的邊參加樹中不產生回路三項原則。40．在一棵m階B樹中，除根結點外，每個結點最多有m棵子樹，最少有m/2棵子樹。三、判斷題。1．在決定選取何種存儲構造時，一般不考慮各結點的值如何。〔√〕2．抽象數據類型〔ADT〕包括定義和實現兩