數(shù)據(jù)結(jié)構(gòu)(第二版)復習題及答案

復習題一、選擇：1、數(shù)據(jù)的基本單位是（B），在計算機中作為整體進行處理A、數(shù)據(jù)項B、數(shù)據(jù)元素C、數(shù)據(jù)對象D、數(shù)據(jù)結(jié)構(gòu)2、在一個順序表中，如果第一個元素的存儲地址為100，每個元素的長度為2，則第5個元素的地址為（B）計算過程：100+（5-1）*2=108A、110B、108C、100D、1203、鏈表不具備的特點是（A）A、可以隨機訪問B、插入刪除不必移動元素C、不必事先估計存儲空間D、所需空間與其長度成正比4、在一個長度為n的順序表的第i個元素前插入一個元素時，需要向后移動（A）個元素A、n-i+1B、n–iC、n–i–1D、i5、在一個單鏈表中，如果在P所指的結(jié)點后插入S所指結(jié)點，則執(zhí)行(B)A、s->next=pp->next=sB、s->next=p->nextp->next=sC、s->next=p->nextp=sD、p->next=ss->next=p6、刪除一個長度為n的順序表的第i個元素，需要向前移動（B）個元素A、n-i+1B、n–iC、n–i–1D、i7、從一個具有n個結(jié)點的單鏈表中查找其值為x的結(jié)點，在查找成功的情況下，需要比較（D）個結(jié)點A、nB、n/2C、(n–1)/2D、(n+1)/28、在一個單鏈表中，q是p所指結(jié)點的前趨結(jié)點，如果在q和p之間插入s結(jié)點，則執(zhí)行(C)A、s->next=p->nextp->next=sB、p->next=s>nexts->next=pC、q->next=ss->next=pD、p->next=ss->next=q9、使帶頭結(jié)點的單鏈表為空的判定條件是（B）A、head=NULLB、head->next==NULLC、head->next=headD、head!=NULL10、在一個具有n個結(jié)點的有序鏈表中插入一個新結(jié)點并仍然有序的時間復雜度是(B)A、O（1）B、O（n）C、O（n2）D、O（nlog2n）11、如果1，2，3依次進棧，則出棧順序不可能是（C）A、321B、213C、312D、132解析：123分別進棧321分別出棧1進2進2出1出3進3出1進1出2進3進3出2出12、非空的循環(huán)單鏈表head的尾結(jié)點P滿足（C）A、p->next==NULLB、P==NULLC、P->next==headD、p==head13、建立有序單鏈表的時間復雜度為（C）A、O（1）B、O(n)C、O(n2)D、O(nlog2n)14、不帶頭結(jié)點的單鏈表為空的判定條件是（A）A、head=NULLB、head->next==NULLC、head->next=headD、head!=NULL15、判斷鏈隊為空的條件是（A）A、Q->front==Q->rearB、Q->front！=Q->rearC、Q->front==（Q->rear+1）%nD、Q->front！=（Q->rear+1）%n16、循環(huán)隊列的頭尾指針分別為front和rear，則循環(huán)隊列為滿的條件是（C）A、Q->front==Q->rearB、Q->front！=Q->rearC、Q->front==（Q->rear+1）%nD、Q->front！=（Q->rear+1）%n17、進隊序列為1,2,3,4,進行1次出隊運算后，隊頭結(jié)點為（B）A、1B、2C、3D、418、在一個單鏈表中，刪除P所指結(jié)點的后繼結(jié)點，應執(zhí)行（A）A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->nextD、p=p->next->next19、鏈表的優(yōu)點是（C）A、便于隨機存取B、花費的存儲空間比順序表少C、便于插入與刪除D、數(shù)據(jù)元素的物理順序與邏輯順序相同20、在一個鏈隊中，假設f和r分別為隊首和隊尾指針，則插入s所指結(jié)點的運算是（B）A、f->next=s;f=s;B、r->next=s;r=s;C、s->next=r;r=s;D、s->next=f;f=s;21、設高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此二叉樹中包含的結(jié)點數(shù)至少為（B）個A、2hB、2h-1C、2h+1D、22、一個棧的進棧序列是1,2,3,4，則出棧序列不可能是（C）A、1234B、4321C、4132D、324123、采用鄰接表存儲的圖的深度優(yōu)先搜索遍歷類似于二叉樹的（A）A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷24、從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，則執(zhí)行（D）A、x=HS;HS=HS->nextB、x=HS->data;C、HS=HS->next;x=HS->dataD、x=HS->data;HS=HS->next25、具有6個結(jié)點的無向圖至少有（A）條邊才能形成連通圖A、5B、6C、7D、826、在鏈隊Q中，插入S所指結(jié)點需執(zhí)行的命令是（B）A、Q->front->next=s;f=sB、Q->rear->next=s;Q.rear=sC、s->next=Q->rearQ->rear=sD、S->next=Q->frontQ->front=s;27、如果二叉樹的先序遍歷序列為ABDGCEFH，中序遍歷序列為DGBAECHF,則后序遍歷序列為（D）A、BDGCEFHAB、GDBECFHAC、BDGAECHFD、GDBEHFCA28、具有5個頂點的無向完全圖有（A）條邊A、10B、24C、25D、2029、采用鄰接表存儲的圖的廣度優(yōu)先搜索遍歷類似于二叉樹的（D）A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷30、在鏈隊Q中，刪除一個結(jié)點需執(zhí)行的命令是（B）A、Q->rear=Q->front->nextB、Q->rear->next=Q->rear->next->nextC、Q->front->next=Q->front->next->nextD、Q->front=Q->rear->next31、在解決計算機與打印機之間速度不匹配問題時通常設置一個打印緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)，打印機則從緩沖區(qū)取出數(shù)據(jù)打印，該緩沖區(qū)使用（B）結(jié)構(gòu)A、堆棧B、隊列C、數(shù)組D、樹32、在有向圖的鄰接表存儲結(jié)構(gòu)中，頂點v在表結(jié)點中出現(xiàn)的次數(shù)是（B）A、頂點v的度B、頂點的出度C、頂點v的入度D、依附于頂點V的邊數(shù)33、將一棵有100個結(jié)點的完全二叉樹從上到下，從左到右依次對結(jié)點編號，根結(jié)點編號為1，則編號為49的結(jié)點的左孩子為（B）A、99B、98C、50D、4834、二維數(shù)組SA中，每個元素的長度為3個字節(jié)，行下標從0到7，列下標從0到9，從首地址SA開始連續(xù)存放在存儲器中，該數(shù)組按列存放，元素A[4][7]的地址為（B）A、SA+141B、SA+180C35、數(shù)組A中，每個元素的長度是3字節(jié)，行下標i從1到8，列下標j從1到10，從首地址開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是（B）。A、80B、100C、240D、27036、將一個A[15][15]的下三角矩陣，按行優(yōu)先存入一維數(shù)組B[120]中，A中元素A[6][5]在B數(shù)組中的位置K為（B）A、19B、26C、21D、1537、廣義表A=(a,b,(c,d),(e,(f,g))),則Head(Tail(Head(Tail(Tail(A)))))=(D)A、(g)B、（d）C、cD、d38、在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（B）A、1/2B、2C、1D、439、已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac，則前序遍歷序列為（D）A、acbedB、decabC、deabcD、cedba40、由權(quán)為8，2，5，7的四個葉子結(jié)點構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（D）A、23B、37C、46D、4341、下面結(jié)論正確的是（D）A、在無向圖中，邊的條數(shù)是結(jié)點度數(shù)之和B、在圖結(jié)構(gòu)中，結(jié)點可以沒有任何前趨和后繼C、在n個結(jié)點的無向圖中，如果邊數(shù)大于n-1;則該圖必是連通圖D、圖的鄰接矩陣必定是對稱矩陣42、由下圖得到的拓樸序列，以下選項中合理的為（A）1123456 A、V1V4V6V2V5V3B、V1V2V3V4V5V6C、V1V4V2V3V6V5D、V1V2V4V6V3V5二、填空題1、數(shù)據(jù)常用的存儲表示方法有三種，分別為樹結(jié)構(gòu)、線性結(jié)構(gòu)和圖結(jié)構(gòu)。2、算法的時間復雜度取決于問題的規(guī)模。3、線性表的存儲方式有二種，分別為循序存儲和鏈式存儲4、線性表的順序存儲結(jié)構(gòu)是一種隨機存儲結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)是一種循序存儲結(jié)構(gòu)。5、為結(jié)點p申請一個存儲空間，則使用語句p=（NODE*）malloc（sizeof（NODE））6、算法的特點包括：可行性、確定性、有窮性輸入和輸出。7、雙向鏈表中，每個結(jié)點有兩個域，一個指向直接前驅(qū)，一個指向直接后續(xù)。8、評價算法優(yōu)劣時需要考慮正確性、可續(xù)性、健壯性和高效性。9、鏈式存儲結(jié)構(gòu)中，指針域只有一個指針的線性表稱為單鏈表10、串的順序存儲方式分別為非緊縮格式、緊縮格式和單字節(jié)儲存格式。11、鏈表中的結(jié)點包括兩個域，數(shù)據(jù)域存放結(jié)點值，指針域存放結(jié)點后續(xù)地址12、如果鏈表最后一個結(jié)點的指針域指向其頭結(jié)點，則該鏈表為循環(huán)鏈表13、線性結(jié)構(gòu)中元素之間存在一對一關系，樹型結(jié)構(gòu)元素之間存在一對多關系，圖形結(jié)構(gòu)元素之間存在多對多關系。14、棧滿時進棧稱為上溢，?？諘r出棧稱為下溢15、進行串的模式匹配時，BF算法和KMP算法的區(qū)別在于BF算法有回溯，KMP算法無回溯16、為了解決假溢出并使得隊列的空間得到充分利用，使用循環(huán)隊列形成首尾相接的環(huán)形。17、對于一個單鏈表，在p所指的結(jié)點后插入S所指結(jié)點，應執(zhí)行s->next=p->next和p->next=s18、串的賦值使用assign算法實現(xiàn)，求子串使用sub算法實現(xiàn)19、算法分析有兩個方面，分別為時間復雜度和空間復雜度20、數(shù)據(jù)元素由數(shù)據(jù)項組成，數(shù)據(jù)項是數(shù)據(jù)的最小單位21、棧的特點是后進先出，隊列的特點是先進先出。棧中元素的插入和刪除在棧頂進行，22、隊列只能在隊尾插入元素，在對頭刪除元素。23、串的模式匹配的算法分別為BF算法和KMP算法24、時間復雜度用數(shù)量級表示，記為T（n）25、數(shù)據(jù)結(jié)構(gòu)指數(shù)據(jù)之間的關系，包括三方面的內(nèi)容，分別為邏輯結(jié)構(gòu)、儲存結(jié)構(gòu)和算法26、一棵深度為5的完全二叉樹的第5層有5個葉子結(jié)點，則共有20個結(jié)點27、矩陣中含有大量零元素的矩陣稱為系數(shù)矩陣28、數(shù)據(jù)的存儲結(jié)構(gòu)包括四種，分別為順序儲存、非順序儲存、索引儲存和哈希儲存29、稀疏矩陣使用三元組表進行壓縮存儲30、在頂點活動圖中，如果從頂點vi到vj有一條路徑，則頂點vi必在vj之前，滿足此關系的線性序列稱為拓撲序列31、樹與二叉樹的區(qū)別為二叉樹中的每個結(jié)點最多只能有兩顆子樹，并且有左右之分32、深度優(yōu)先搜索類似于樹的先序遍歷，廣度優(yōu)先搜索類似于樹的層次遍及33、在二叉樹的第i層至多有2的i-1次方個結(jié)點。34、構(gòu)造最小生成樹的算法有兩種，分別為普利姆和克魯斯卡爾35、深度為k的二叉樹至多有2的k次方-1個結(jié)點。36、圖的遍歷方式有兩種，分別為深度優(yōu)先搜索遍及和廣度優(yōu)先搜索遍及37、具有n個結(jié)點的完全二叉樹的深度為[log2n]+1。3