數(shù)據(jù)結(jié)構(gòu)基本復(fù)習(xí)題答案

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