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

鄭州航空工業(yè)管理學(xué)院《數(shù)據(jù)構(gòu)造》習(xí)題集第1章緒論1、填空題常見的數(shù)據(jù)構(gòu)造有集合、_線性__構(gòu)造，__樹___構(gòu)造，__圖__構(gòu)造等三種。常見的存儲構(gòu)造有__次序存儲___構(gòu)造，__鏈?zhǔn)酱鎯__構(gòu)造等兩種。數(shù)據(jù)的基本單位是_數(shù)據(jù)元素__，它在計算機中是作為一種整體來解決的。數(shù)據(jù)構(gòu)造中的構(gòu)造是指數(shù)據(jù)間的邏輯關(guān)系，常見的邏輯構(gòu)造可分為兩大類：__線性構(gòu)造____和__非線性構(gòu)造___。2、選擇題數(shù)據(jù)構(gòu)造是一門研究非數(shù)值計算的程序設(shè)計中計算機的A以及它們之間的C和運算等的學(xué)科。（A）數(shù)據(jù)元素（B）計算辦法（C）關(guān)系（D）數(shù)據(jù)映像在數(shù)據(jù)構(gòu)造中，與所使用的計算機無關(guān)的是數(shù)據(jù)的A構(gòu)造。（A）邏輯（B）存儲（C）物理（D）邏輯與存儲3、應(yīng)用題(1)、給出下列算法的時間復(fù)雜度.voidfun(intn){ inti=1,k=100; while(i<n) { k=k+1; i=i+2; }}上述算法的時間復(fù)雜度為：___O(n)_____。(2)、給出下列算法的時間復(fù)雜度.voidfun2(intn){ inti=1,k=100; while(i<n) { i=i*10; k=k+1; }}上述算法的時間復(fù)雜度為：___O(log10n)______。第2章線性表1、填空題線性表按照存儲構(gòu)造不同重要有兩種實現(xiàn)方式，一種是__次序_表，另一種是___鏈___表。次序表采用__隨機___訪問機制對數(shù)據(jù)元素進行訪問。若在單鏈表結(jié)點p的背面插入一種新的結(jié)點s，則其操作序列為:____s->next=p->next_____________；___p->next=s___________________；在單向鏈表中，若要刪除某個結(jié)點p，普通要找到__p的直接前驅(qū)__結(jié)點，才干實現(xiàn)該操作。2、選擇題將兩個各有n個元素的有序表歸并成一種有序表，其最少的比較次數(shù)是A。(A)n(B)2n－1(C)2n(D)n-1在單鏈表中，如果在結(jié)點p之后插入一種新結(jié)點s，其操作為A。（A）s->next=p->next;p->next=s;（B）p->next=s;s->next=p->next;（C）s->next=p;p->next=s->next;（D）p->next=s;s->next=p;若長度為n的線性表采用次序存儲構(gòu)造，在其第i個位置刪除一種元素的算法的平均時間復(fù)雜度為(C)。(1≤i≤n)(A)．O(0)(B)．O(1)(C).O(n)(D)．O(n2)若長度為n的線性表采用次序存儲構(gòu)造，在其第i個位置插入一種新元素需要移動的元素個數(shù)為(B)。(1≤i≤n+1)(A)．n-i(B)．n-i+1(C).I(D)．n-i-13、判斷題(1).線性表中每一種元素都有一種前驅(qū)和一種后繼。（錯）第3章棧和隊列1、填空題(1).棧和隊列在本質(zhì)上都是操作受限的_線性表__________。(2).棧的操作特點是__后進先出_。隊列的操作特點是_先進先出__。2、選擇題(1).消除遞歸不一定需要使用棧，此說法__A____。(A).對的(B).錯誤(2).一種棧的進展序列為（1，2，3，4），則不可能得到的輸出序列是__D____。(A)（1，2，3，4）(B)（4，3，2，1）(C)（1，3，4，2）(D)（3，1，2，4）(3).用單循環(huán)鏈表表達隊列，對的的說法是B。(A)可設(shè)一種頭指針使入隊、出隊都方便；(B)可設(shè)一種尾指針使入隊、出隊都方便；(C)必須設(shè)頭尾指針才干使入隊、出隊都方便；(D)無論如何,只可能使入隊方便。3、判斷題(1).棧的特點是先進先出。（錯）(2).能夠在隊列的任意位置插入元素。（錯）(3).遞歸程序化非遞歸程序必須用到棧。（錯）(4).如果進棧的序列為（1，2，3，4），則（4，2，3，1）不可能是出棧序列。（對）(5).在用次序表表達的循環(huán)隊列中，能夠設(shè)一種變量L作為標(biāo)志位來分辨隊空或隊滿的條件，當(dāng)L==0時表達隊列為空，等L的值為空間的大小時表達隊列為滿。（對）(6).當(dāng)用數(shù)組做為棧的存儲構(gòu)造時，應(yīng)把棧頂設(shè)在高地址哪一端，這樣入棧、出棧不需要移動其它元素。（對）(7).當(dāng)用單鏈表作為棧的存儲構(gòu)造時，應(yīng)把棧頂設(shè)立鏈表的頭部，這樣入棧、出棧不需要移動其它元素。（對）第4章串1、選擇題(1).串是任意有限個（D）(A).符號構(gòu)成的序列 (B).符號構(gòu)成的集合(C).字符構(gòu)成的集合 (D).字符構(gòu)成的序列(2).串是一種特殊的線性表，其特殊性體現(xiàn)在（B）(A).能夠次序存儲(B).數(shù)據(jù)元素是一種字符(C).能夠連接存儲(D).數(shù)據(jù)元素能夠是多個字符(3).下列（D）是“abcd321ABCD”的子串。(A).abcd (B).321AB(C).“abcABC”(D).“21AB”(4).兩個串相等必有串長度相等且（B）。(A).串的各位置字符任意(B).串中各位置字符均對應(yīng)相等(C).兩個串含有相似的字符(D).兩個所含字符任意(5).設(shè)有兩個串p和q，求q在p中初次出現(xiàn)的位置的運算稱作（B）(A)．連接(B)．模式匹配(C)．求子串(D)．求串長(6).若串s=“software”，其子串的個數(shù)是（C）。(A).8 (B).37(C).36 (D).92、判斷題(1).空串和空格串是同一種概念，兩者沒有區(qū)別。（錯）(2).空格串就是由空格構(gòu)成的串。（對）第5章數(shù)組和廣義表1、填空題(1).二維數(shù)組在內(nèi)存中存儲能夠有兩種存儲方式，一種是__按行__優(yōu)先存儲，一種是按列優(yōu)先存儲。(2).設(shè)廣義表L＝(（），（），（（））)。則head(L)是（）；tail(L)是(（），（（））)；L的長度是3；L的深度是3。(3).設(shè)廣義表L＝(（a），（b），（（c））)，則head(L)是__（a）__；tail(L)是__(（b），（（c））)__。2、選擇題(1).在C語言中，如果有數(shù)組定義intA[8][9]；假定每個整型數(shù)據(jù)占2字節(jié)，則數(shù)組元素A[4][4]的地址是（A）。(A).A+80 (B).A+76 (C).A+82 (D).以上都不對(2).廣義表A=（a,b,(c,d),(e,(f,g))）,則下面式子的值為(D)；Head(Tail(Head(Tail(Tail(A)))))(A)．（g） (B).(d) (C).c (D).d3、判斷題在C語言中，多維數(shù)組的存儲采用的是行優(yōu)先的方式。（對）廣義表在本質(zhì)上也是線性表，這種說法是錯誤的。（對）廣義表L的取表頭操作是Head(L)，得到的是L中的第一種元素。（對）廣義表L的取表尾操作是Tail(L)，得到的是L中的除了第一種元素外全部元素構(gòu)成的表。（對）能夠用三元組存儲法來壓縮存儲稀疏矩陣。（對）已知廣義表A=((a,b,c),(d,e,f)),從A中取出原子e的運算是head(tail(head(tail(A))))。(對)第6章樹和二叉樹1、填空題一棵62個葉結(jié)點的完全二叉樹,最多有__125______個結(jié)點。若規(guī)定僅有根的二叉樹的高度為1，那么高為h的完全二叉樹最多有2h-1___個結(jié)點，最少有__2h-1_個結(jié)點。設(shè)只包含有根結(jié)點的二叉樹的高度為0，則高度為k的二叉樹的最大結(jié)點數(shù)為___2k+1-1____________，最小結(jié)點數(shù)為__k+1_____。設(shè)僅包含根結(jié)點的二叉樹的高度為1，則高度為k的二叉樹的最大結(jié)點數(shù)為___2k-1___，最小結(jié)點數(shù)為__k___。在一棵二叉樹中，如果度為2的結(jié)點個數(shù)為100，則葉子結(jié)點個數(shù)為101。在一棵哈夫曼樹中，如果葉子結(jié)點個數(shù)為100，則度為1的結(jié)點總個數(shù)為0。在一棵哈夫曼樹中，如果葉子結(jié)點個數(shù)為100，則度為2的結(jié)點總個數(shù)為99。在一棵哈夫曼樹中，如果葉子結(jié)點個數(shù)為100，則結(jié)點總個數(shù)為199。2、選擇題含有N個結(jié)點的完全二叉樹的深度是_B___。(A)?log2N?(B)?log2N?+1(C)?log2(N)?(D)?log2N?-1設(shè)二叉樹的樹根為第一層，則第i層上至多有__C____結(jié)點。(A)1(B)2(C)2i-1(D)2i-13、判斷題二叉樹的左右子樹次序是嚴(yán)格的，不能夠任意變化。（對）若根為第一層，則深度為k的滿二叉樹的結(jié)點數(shù)為2^k-1。（對）二叉樹的三叉鏈表存儲構(gòu)造能夠方便的訪問到雙親結(jié)點。（對）4、應(yīng)用題(1).請證明對于任何一棵二叉樹，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。見教材P123ABECFGABECFGDHIJ圖1先：ABCDEFGHIJ中：BCDAFEHJIG后：DCBFJIHGEA(3).寫出如圖2所示二叉樹的中序遍歷成果。DDACFGEHB圖2中：ADBCHFEG(4).已知某二叉樹的前序遍歷序列為：ABCDEFG和中序遍歷序列為：CBEDAFG。請畫出該二叉樹并寫出它的后序遍歷序列。見教材P154例6-5(5).設(shè)一棵二叉樹的先序遍歷序列為abcde，中序遍歷序列為badce，請畫出對應(yīng)的二叉樹，并寫出對應(yīng)后序遍歷序列。bbedca圖3二叉樹見圖3后：bdeca(6).在一段文字中，共出現(xiàn)a、b、c、d、e、f六種字符，每種字符出現(xiàn)的頻率分別為7,9,12,22,23,27。請回答下列問題：（a）什么是哈夫曼樹？帶權(quán)途徑長度最小的二叉樹。2828121627239457圖42255100（b）根據(jù)題目所給頻率值，畫出對應(yīng)的哈夫曼樹。哈夫曼樹見圖4（c）給出各個字符對應(yīng)的哈夫曼編碼。7：11109：111112：11022：0023：0127：105、讀程序?qū)懗晒鸄BABCDEstructNode{ intdata; Node*lchild,*rchild;};某棵二叉樹的形態(tài)如右圖：根據(jù)規(guī)定解答下題：1、intfun1(Node*root){ if(root==0)return0; intl,r; l=fun1(root->lchild); r=fun1(root->rchild); if(l>=r)returnl+1; elsereturnr+1;}(1)當(dāng)root是指向結(jié)點A的指針時，函數(shù)fun1的返回值是：3。(2)函數(shù)fun1的功效是：求二叉樹的葉子個數(shù)。2、intfun2(Node*root){ if(root==0)return0; intl=fun2(root->lchild); intr=fun2(root->rchild); returnl+r+1;}（1）當(dāng)root是指向結(jié)點A的指針時，函數(shù)fun2的返回值是：3。（2）函數(shù)fun2的功效是求二叉樹的高度第7章圖1、填空題有n個頂點的有向連通圖最多有n(n-1)條邊，最少有n條邊。含有n個頂點的完全無向圖有__n(n-1)/2__條邊，完全有向圖有__n(n-1)______條邊。____拓撲排序_____辦法能夠判斷出一種有向圖中與否有環(huán)（回路）。含有n個頂點的有向圖最多有__n(n-1)__條邊。4、應(yīng)用題（1）、已知某圖的存儲構(gòu)造以下，試寫出該圖從頂點A開始的深度優(yōu)先、廣度優(yōu)先遍歷序列。ABCDEFGHIJKA01111100000B00000010000C00000001000D00000000100E00000000010F00000000001G01000000000H00100000000I00010000000J00001000000K00000100000圖1深度優(yōu)先遍歷：ABGCHDIEJFK廣度優(yōu)先遍歷：ABCDEFGHIJK（2）.請給出圖2的全部最小生成樹。aaebdfc1238665圖2 答案：有兩個aaebdfc12365答案一aaebdfc12365答案二（3）.請給出圖3的全部拓撲排序序列。圖圖3abdfgceh答案：有兩個(1)abcdefgh(2)acbdefgh（4）、對于有向無環(huán)圖（如圖4），寫出它的全部不同的拓撲有序序列。112435678圖4答案：有兩個3245678（2）31245678（5）.已知某圖采用如圖5所示的鄰接矩陣表達法，請回答下列問題。01234561A10110002B21001103C31000114D40100005E50110006F6001000圖5(a)請畫出該圖。DBDBEAEACFCF（b）對其從頂點A開始進行深度優(yōu)先遍歷，寫出遍歷序列。深度優(yōu)先遍歷：ABDECF(7)、構(gòu)造圖6的最小生成樹。aaefgdbhc21111222243圖6bgebge22222211da11da11chf11chf第9章查找1、選擇題若在線性表中采用二分查找法查找元素，該線性表應(yīng)當(dāng)C。（A）．元素按值有序（B）．采用次序存儲構(gòu)造（C）．元素按值有序，且采用次序存儲構(gòu)造（D）．元素按值有序，且采用鏈?zhǔn)酱鎯?gòu)造對二叉排序樹進行___B______遍歷，能夠得到該二叉樹全部結(jié)點構(gòu)成的有序序列。(A).前序 (B).中序 (C).后序 (D).按層次運用逐點插入法建立序列(51，71，43，81，74，20，34，45，64，30)對應(yīng)的二叉排序樹后來，查找元素34要進行(A)元素間的比較。（A）．4次 （B）．5次 （C）．7次 (D)．10對二叉排序樹進行___B_____遍歷，能夠得到該二叉樹全部結(jié)點構(gòu)成的有序序列。(A)．前序 (B)．中序 (C)．后序 (D).按層次散列函數(shù)有一種共同性質(zhì)，即函數(shù)值應(yīng)按___C_____取其值域的每一種值。(A).最大概率 (B).最小概率 (C).同等概率 (D).平均概率一種哈希函數(shù)被認為是“好的”，如果它滿足條件__A____。(A)哈希地址分布均勻(B)確保不產(chǎn)生沖突(C)全部哈希地址在表長范疇內(nèi)(D)滿足(B)和(C)哈希表的平均查找長度是____D_____的函數(shù)。（A）哈希表的長度（B）表中元素的多少（C）哈希函數(shù)（D）哈希表的裝滿程度平均查找長度最短的查找辦法是__C___。（A）折半查找（B）次序查找（C）哈希查找（4）其它2、判斷題在有序表的查詢過程中，設(shè)立“哨兵”的作用是為了減少比較次數(shù)，提高查詢效率。（對）對于折半查找，其前提條件是待查找序列只要是有序的即可。（錯）3、應(yīng)用題（1）.輸入一種正整數(shù)序列（53,17,12,66,58,70,87,25,56,60），試完畢下列各題。(a)按輸入次序構(gòu)造一棵二叉排序樹（一步一步畫出構(gòu)造二叉排序樹的過程，每插入一種結(jié)點，畫一棵二叉排序樹）。5353176658701287256056(b)依此二叉排序樹，如何得到一種從小到大的有序序列？對二叉排序樹進行中序遍歷（2）、若一棵排序二叉樹的核心字輸入序列為{80，6，10，7，8，25，100，90}，請畫出該二叉樹。80680610090710825（3）.已知一組核心字為{1,14,27,29,55,68,10