第1章緒論1自測習題二、選擇題．以下數據結構中，屬于線性結構的是(B)A）有向圖B）串）線索二叉樹D）B樹．下列與數據元素有關的敘述中錯誤的是(A)A）數據元素是有獨立含義的數據最小單位B）數據元素是描述數據的基本單位）數據元素可以稱做結點）數據元素可以稱做記錄．以下術語中與數據的存儲結構無關的是(A)A）棧B）散列表）順序表）雙鏈表．以下數據結構中，屬于線性結構的是(B)A）有向圖B）串）線索二叉樹D）B樹三、填空題．數據結構包括的三方面內容分別是：數據的邏輯結構、數據感謝閱讀的存儲結構和數據的運算。結點、謝謝閱讀記錄和頂點。4種基本形態包括集合結構、線性結構、樹精品文檔放心下載型結構和圖（網）結構。5、輸出、感謝閱讀可行性和有窮性。鏈式、索引和散列四種。精品文檔放心下載．一個數據結構在計算機中的映象稱為存儲結構。7．一個算法的效率主要是指該算法的時間效率和空間效謝謝閱讀率。．以下程序段的時間復雜度T（）=_O(n2)。感謝閱讀sum=0;for(i=0;i<n;i++)for(j=0;j<n;j++)sum+=a[i][j];printf("%d\n",sum);第2章2自測習題二、選擇題B）感謝閱讀A）單向鏈表和雙向鏈表B）雙向鏈表和循環鏈表）單向鏈表和循環鏈表D）單向鏈表、雙向鏈表和循環鏈表．線性表是具有n個(B)的有限序列。A）數據項B）數據元素C）表元素）字符n的線性表采用鏈式存儲i個元素的算謝謝閱讀法時間復雜度為(B)A）B）O(n)）2)）O(logn)感謝閱讀2．在長度為n的順序表中，若要刪除第i（1≤i≤n）個元素，則感謝閱讀需要向前移動的元素的次數為(B)A）iB）n-i）n-i+1n的順序表中第精品文檔放心下載為留出插入位置所需移動元素的次數為(C)A））i）n-i+1）n-i-1三、填空題．有一單鏈表結構如下：data…BCD…p圖填空題1附圖若要刪除值為c的結點，應做的操作是精品文檔放心下載p->link=p->link->link。．線性表L=(a,a,…a用數組存儲。假定刪除表中任一元素的概謝謝閱讀12n率相同，則刪除一個元素平均需要移動的元素個數是(n-1)/2。．設有結點定義structnode{intdata;structnode*next;且已建立如圖2-2所示的帶有頭結點的單向鏈表：datahead頭…^圖填空題3附圖函數sum的功能是：計算鏈表中各結點數據域之和，作為函數值返精品文檔放心下載回。請填空。intsum(structnode*head)精品文檔放心下載{ints=0;structnode*p;p=head->next;do{s=s+p->data;p=p->next;}while(p!=NULLreturns;}第3章棧和隊列3自測習題二、選擇題．有6個元素按、、4、、2、1的順序進棧，進棧過程中可以謝謝閱讀出棧，則以下可能的出棧序列是（B，）A）、、3、、、6）6、5、、、、1感謝閱讀）、、4、、、5）5、6、、4、、1謝謝閱讀．棧和隊列都是（）A）順序存儲的線性結構）鏈式存儲的線性結構）限制存取點的線性結構D）限制存取點的非線性結構謝謝閱讀．設循環隊列的隊首指針用front表示，隊尾指針用rear表示，感謝閱讀則判斷隊空的條件是（A）A）front==rearB）front+1=rearC）rear+1=front謝謝閱讀）rear==04、設有中綴算術表達式：15–3*（7+2）,其對應的后綴算感謝閱讀術表達式為（B）A）3-72+*B）372+*-C）153*72+精品文檔放心下載）3-*72+三、填空題感謝閱讀性表，其操作特點是先進先出。，精品文檔放心下載謝謝閱讀后，現在已出棧的序列是、、5，棧頂指針是。謝謝閱讀3．設有后綴算術表達式：2xy+*3y-/，其對應的中綴表達精品文檔放心下載式為2*(x+y)/(3-y)。4．已知一算術表達式的中綴形式為：(a+b)-(b+c)/2，其對應的前精品文檔放心下載綴表達式形式應為-+ab/+bc2。第4章串4.1自測習題一．選擇題．設有一個字符串S=“ABC123XYZ”，問該串的長度為（）精品文檔放心下載A）9）10C））12．設有一個字符串S=”windows”，其子串的數目是29個)精品文檔放心下載A）25個）26個）27個）28個謝謝閱讀．串是一種特殊的線性表，其特殊性表現在A）串中允許有空串）串可以順序存儲）串可以鏈式存儲）數據元素是一個字符。二．填空題１．已知串S=”abaabccd”，求該串S的子串運算結果，精品文檔放心下載SubStr(“abaabccd”,4,3)=感謝閱讀5,0)=＿∮＿。２．兩個串相等的充分必要條件是＿不僅兩個串的長度相等，而感謝閱讀＿且各個位置上對應的字符也要相等。３．不含任何字符的串稱為＿空串＿＿，其長度為＿。感謝閱讀４．只含有空格字符的串稱為精品文檔放心下載的個數＿。第5章數組與廣義表5自測習題一．選擇題１．設有二維數組A9,]，其每個元素占２個字感謝閱讀節，數組按行優先順序存儲，第一個元素的存儲地址為100，那感謝閱讀么元素A[8,12]的存儲地址為２．設有一個10謝謝閱讀順序存儲，a11為第一個元素，其存儲地址為1，且每個元素占1個地址空間，則a的地址為(A)75Ａ）Ｂ）17Ｃ）33Ｄ）二．填空題１．設有二維數組謝謝閱讀A[6,6]精品文檔放心下載的存儲地址為＿＿＿＿。下標從0開始)２．設有廣義表A=((x,(a,b)),((x,(a,b)),y)則廣義表謝謝閱讀A的長度為＿＿2＿＿，深度為＿＿4＿＿。第6章樹6自測習題三.選擇題如果結點A是結點B的雙親，而且結點Ｂ有４個兄弟，則結點A謝謝閱讀的度是(D)A）234）5設有一棵二叉樹，其１度結點有m個，２度結點有n個，則該二謝謝閱讀叉樹的結點總數為A）m+n）））m+2*n+1感謝閱讀設有一棵二叉樹，其先序遍歷序列是：ABCDEFG，中序遍歷序列謝謝閱讀是：CBDAFEG，則該二叉樹的后序遍歷序列是(A)感謝閱讀A）CDBFGEAB）CDFGBEAC）CDBAFGED）CDBFEGA設有13個值，由它們組成一棵哈夫曼樹，則該哈夫曼樹中結點感謝閱讀個數共有(D)。A）B））25設電文中出現的字母為A、B、、D和E，每個字母在電文中出精品文檔放心下載現的次數分別為：，23，，5和12，按哈夫曼編碼，則字母C謝謝閱讀的編碼應是(C)(D)已知一棵二叉樹的先序遍歷序列為EFHIGJK，中序遍歷序列為感謝閱讀HFIEJGK，則該二叉樹根的右子樹的根是(G)A）EB）FC）G）J設結點A有左孩子結點B，右孩子結點C，則在先序遍歷、中序謝謝閱讀遍歷、后序遍歷這三種基本遍歷序列中B一定是C的(A)謝謝閱讀A）前驅）不相鄰結點四.填空題采用二叉鏈式存儲結構，具有n個結點的二叉樹中，一共有感謝閱讀2n個指針域，其中n+1個指針域為空。一棵非空的二叉樹，其第i層上最多有＿2i1＿＿＿＿個結點。謝謝閱讀滿二叉樹是一棵深度為k的且恰好有＿2k-1＿＿＿＿個結點的精品文檔放心下載二叉樹。i精品文檔放心下載結點有左孩子，則其編號為；如該結點有右孩子，則謝謝閱讀其編號為2i+1。精品文檔放心下載葉子結點的個數是m，則左、右子樹都非空的結點個數是＿m-1精品文檔放心下載＿＿＿＿設有一棵樹（如圖6-5感謝閱讀根結點是＿A＿；葉子結點有＿DHIJFC的孩子是＿無；Ｅ的子孫有＿＿HIJ＿＿；Ｄ的兄弟是E＿＿；Ｂ謝謝閱讀C感謝閱讀的子樹深度是＿；這棵樹的度是＿＿。圖填空題6的附圖現有一表達式(a+b)*c-d/e，寫出該表達式的波蘭式＿精品文檔放心下載-*+abc/de＿＿＿，以及逆波蘭式＿ab+c*de/-＿＿＿＿＿。謝謝閱讀第7章圖7自測習題二、選擇題．對如圖7-4所示的無向圖G，若從頂點V1開始，按深度優先搜精品文檔放心下載索法進行遍歷，則可能的訪問順序為（A）V1V2V3V5V6V4V7V8圖7-4選擇題1的附圖A）V1V2V4V8V5V6V3V7V2V3V4V5V6V7V8感謝閱讀）V1V2V3V4V8V5V6V7V2V4V5V8V3V6V7謝謝閱讀．對如圖7-5所示的無向圖G，若從頂點V1開始，按廣度優先搜感謝閱讀索法進行遍歷，則可能的訪問順序為（）V1V2V6V3V4V5V7V8圖7-5選擇題2的附圖A）V1V2V3V4V5V6V7V8B）V1V2V6V3V4V5V7V8感謝閱讀）V1V2V6V3V4V7V8V5D）V1V2V6V3V5V4V7V8感謝閱讀．在一個無向圖中，所有頂點的度數之和等于所有邊數的（B）精品文檔放心下載A）1倍B）2倍）1/2倍）不確定三、填空題．有n個頂點的無向連通圖至少有n-1條邊，有n個頂點的有向精品文檔放心下載強連通圖至少有n條弧。．在一個有n個頂點的無向圖中，要連通所有頂點，至少需要謝謝閱讀條邊。n=500條邊，謝謝閱讀則形成的鄰接矩陣共有25000個元素，其中1000個非零元素。謝謝閱讀4．有n個頂點的無向圖的鄰接矩陣是對稱的，因而只需存儲精品文檔放心下載(n2+n)/2條邊即可。．在一個有向圖中，所有頂點的度數之和等于圖中弧數的2倍。感謝閱讀在一個有向圖中，所有頂點的出度之和等于圖中弧數的1倍。謝謝閱讀n個頂點和e精品文檔放心下載分別為n和n-1。．無向圖的鄰接矩陣中一行中非零元素的個數表示該行所對應的感謝閱讀頂點的度，一列中非零元素的個數表示該列所對應的頂點的感謝閱讀度。第8章查找三、選擇題．使用折半查找，線性表必須DA）以順序方式存儲精品文檔放心下載序）以鏈式方式存儲D）以順序方式存儲，且元素已按值排好序．散列表的地址區間為0~16，散列函數為H1(K)=K%精品文檔放心下載性探測法解決沖突，將關鍵字序列26，，72，38，，18，依精品文檔放心下載次存儲到散列表中（）元素59存放在散列表中的地址為(D)A）8B）9）10）11（2）查找元素，需要比較的次數為)A）2B）3）45四、填空題．采用折半查找算法在長度為12的有序表中查找一個元素時，查精品文檔放心下載找成功的平均查找長度為_37/12____。，，，，精品文檔放心下載找算法依次搜索4、1、3。精品文檔放心下載第9章排序二、選擇題．下列排序方法中，哪一種是穩定的排序方法：(B)A）選擇排序B）歸并排序）快速排序D）希爾排序．快速排序每次劃分的效果好壞和以下何種因素有直接關系：(C)精品文檔放心下載A）關鍵字的排列情況B）數據元素的個數）軸的相對大?。╆P鍵字值的最大值．對以下幾個關鍵字序列進行快速排序，以第一個元素為軸，一次精品文檔放心下載劃分效果最好的是：(c)A），，3，，5B），，3，，5），1，2，4，5），，，，4．對以下幾個關鍵字序列進行快速排序，以第一個元素為軸，一次感謝閱讀劃分效果不好的是：A），，2，，，，7B），，1，，，，2謝謝閱讀），，1，，，，5），2，3，4，5，，7精品文檔放心下載5．設待排序數據元素序列為[4，1，2，3]，應用一種排序方法進精品文檔放心下載行遞增序排序，已知兩趟后的結果為[1，，3，4]，則所選用的排精品文檔放心下載序方法為：(C)A）直接插入B）直接選擇）冒泡（從前向后）C冒泡（從后向前）與記錄的初始排列無關謝謝閱讀A）希爾排序B）歸并排序有關)）直接選擇排序）直接插入排序．下列字符序列中，不符合堆定義的為：A）ACDGHMPQRX）