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

論1．簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、抽 (1)在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成()。A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) (2)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的()。A.存儲結(jié)構(gòu)B.存儲實現(xiàn)CD.運算實現(xiàn) (3)通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著()。A.數(shù)據(jù)具有同一特點B.不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致C.每個數(shù)據(jù)元素都一樣D.數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等 (4)以下說法正確的是()。A.數(shù)據(jù)元素是數(shù)據(jù)的最小單位B.數(shù)據(jù)項是數(shù)據(jù)的基本單位C.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合D.一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu) (5)以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是()。A.順序隊列B.鏈表C.有序表D.鏈棧 (6)以下數(shù)據(jù)結(jié)構(gòu)中，()是非線性數(shù)據(jù)結(jié)構(gòu)A.樹B.字符串C.隊D.棧6.試分析下面各程序段的時間復(fù)雜度。 {x=x-10;y--;} j foriini++)forjjn;j++)while(i<=n)x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)(6)x=n;.next=s;(*s).next=(*p).next;C.s->next=p->next;p->next=s->next;D.s->next=p->next;p->next=s;(14)在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針()。A.p->next_>prior=p_>prior;p->prior->next=p->next;Bp>next=p->next->next;p_>next->prior=p;Cppriornextpppriorp_>prior->prior;orpnextnextpnextppriorprior(15)在雙向循環(huán)鏈表中，在p指針所指的結(jié)點后插入q所指向的新結(jié)點，其修改指針)。Ap_>next=q;q->prior=p;p_>next->prior=q;q_>next=q;B.p_>next=q;p_>next->prior=q;q->prior=p;q_>next=p->next;C.q->prior=p;q_>next=p->next;p_>next->prior=q;p_>next=q;D.q->prior=p;q_>next=p->next;p_>next=q;p_>next->prior=q;.算法設(shè)計題(I)將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間，不另外占用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){pa=La->next;pb=Lb->next;Lc=pc=La;想摘除棧頂結(jié)點，并將刪除結(jié)點的值保存到x中，則應(yīng)執(zhí)行A.x=top->data;top=top->link;B.top=top->link;x=top->link;C.x=top;top=top->link;D.x=top->link;intfact(intn){線性表的鏈式存儲結(jié)構(gòu)D.棧(II)用鏈接方式存儲的隊列，在進行刪除運算時()。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改(12)循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操)。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)A.(rear+1)%n==frontearfront(14)棧和隊列的共同點是()。A都是先進先出C處插入和刪除元素(15)—個遞歸算法必須包括()。A遞歸部分t"abba”和“abdba”均是回文，但“good”10110100B.10010110C.IIIOIOIO②通過對①的分析，寫②設(shè)被判定的操作序列已存入一維數(shù)組A中。intJudge(charA[])M-1]實現(xiàn)循環(huán)隊列，其中M是隊列長度。設(shè)隊頭指針front和隊尾指針rear，(1)#defineM隊列可能達到的最大長度typedefstructelemtpdataMintfront,rear;eue(2)elemtpdelqueue(cycqueueQ)n+1當!h=DA.808B.818C.1010D.1020(7)設(shè)有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字A.BA+141B.BA+180C.BA+222D.BA+225元素，其存儲地址為1,每個元素占一個地址空間，則a85的地址為()。A.13B.33C.18D.40nA行(包括主對角線上所有A.i*(i-1)/2+jB.j*(j-1)/2+iC.i*(i+1)/2+jD.j*(j+1)/2+i(10)A[N,N]是對稱矩陣，將下面三角(包括對角線)以行序存儲到一維數(shù)組T[N(N+1)/2]kA.i(i-1)/2+jB.j(j-1)/2+iC.i(j-i)/2+1D.j(i-1)/2+1(11)設(shè)二維數(shù)組A[1..nBmnA.(i-1)*n+jB.(i-1)*n+j-1C.i*(j-1)D.j*m+i-1A.55B.45C.36D.16adTailTailAA(g)B.(d)C.cD.d(1)廣義表((a,b,c,d))的表頭是()，表尾是()。A.aB.()C.(a,b,c,d)D.(b,c,d)(15)設(shè)廣義表L=((a,b,c)),則L的長度和深度分別為()。A.1和1B.1和3C.1和2D.2和3jt串next[j]05nextval[j]05abcaab2b6baabc33335890004422227第一趟匹配:第二趟匹配:abcaabbabcabaacbacbaabcab(i=5,j=5)abcaabbabcabaacbacbaabc(i=7,j=3)abcaabbabcabaacbacbaa(i=7,j=1)abcaabbabcabaacbacbaabaaij第三趟匹配:9，列下標從1到11，從首地址S開始連續(xù)存放主存儲器16位。求：第四趟匹配:中，主存儲器字長為(成功)①存放該數(shù)組所需多少單元存放數(shù)組第4列所有元素至少需多少單元③數(shù)組按行存放時，元素A[7,4]的起始地址是多少④數(shù)組按列存放時，元素A[4,7]的起始地址是多少每個元素32個二進制位，主存字長16位，故每個元素占2個字長，行下標可平移至1到trawberrybananapeachpearHHTHTH(T(L)))))))voidCount()是字符串輸入結(jié)束標志{InvertStore(A);Aichmnmn個整數(shù)。①寫一個算法判斷a中所有元素是否互不相同輸出相關(guān)信息(yes/no)；②試分析算法的時間復(fù)雜度。元素要同本行后面的元素比較一次(下面第一個循環(huán)控制變量p的for循環(huán))，然后同第i+1行及以后各行元素比較一次，這就是循環(huán)控制變量k和p的二層for循環(huán)。intJudgEqual(inga[m][n],intm,n)比較一次，比較次數(shù)為n。最佳情況(已排好，正數(shù)在前，負數(shù)空間復(fù)雜度為O(1).EDED第5章樹和二叉樹 (1)把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是()。.A.唯一的有多種..C.有多種，但根結(jié)點都沒有左孩子有多種，但根結(jié)點都沒有右孩子. (2)由3個結(jié)點可以構(gòu)造出多少種不同的二叉樹()ABC.4D.5 (3)一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是()。A.250B.500C.254D.501 (4)一個具有1025個結(jié)點的二叉樹的高h為()。A.11B.10C.11至1025之間D.10至1024之間 (5)深度為h的滿m叉樹的第k層有()個結(jié)點。(1=<k=<h)A.mk-1B.mk-1C.mh-1D.mh-1 (6)利用二叉鏈表存儲樹，則根結(jié)點的右指針是()。A.指向最左孩子B.指向最右孩子C.空D.非空 (7)對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用()遍歷A.先序B.中序C.后序D.從根開始按層次遍歷 (8)若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用()遍歷方法最合適。A.前序B.中序C.后序D.按層次9)在下列存儲形式中，()不是樹的存儲形式A.雙親表示法B.孩子鏈表表示法C.孩子兄弟表示法D.順序存儲表示法 二叉樹一定滿足()。A.所有的結(jié)點均無左孩子B.所有的結(jié)點均無右孩子C.只有一個葉子結(jié)點D.是任意一棵二叉樹 (11)某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是A.空或只有一個結(jié)點B.任一結(jié)點無左子樹)的二叉樹。C.高度等于其結(jié)點數(shù)D.任一結(jié)點無右子樹 X索樹中一個有左孩子的結(jié)點，且X不為根，則X的前驅(qū)為()。AX的雙親C.X的左子樹中最右結(jié)點 (13)引入二叉線索樹的目的是(A.加快查找結(jié)點的前驅(qū)或后繼的速度除C親 (14)線索二叉樹是一種()結(jié)構(gòu)。B的進行插入與刪OA.邏輯B.邏輯和存儲C.物理D.線性O(shè)域為空的結(jié)點有()個。A.n-1B.nC.n+1D.n+2①先序序列與后序序列相同②中序序列與后序序列相同③先序序列與中序序列相同④中序序列與層次遍歷序列相同先序遍歷二叉樹的順序是"根一左子樹一右子樹”，中序遍歷"左子樹一根一右子樹”，若先序序列與后序序列相同，則或為空樹，或為只有根結(jié)點的二叉樹若中序序列與后序序列相同，則或為空樹，或為任一結(jié)點至多只有左子樹的二叉樹.若先序序列與中序序列相同，則或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹.(4)若中序序列與層次遍歷序列相同，則或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹③將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹(或森林)AAM(3)假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為①①②③②③w={7,19,2,6,32,3,21,10}，按哈夫曼規(guī)則:,10)】, [7103方案比較:2345WPL4+++5+=++=WPL+++++++=3字母對應(yīng)出現(xiàn)編號編碼頻率001010011100—000000000000000000000000000000000000000ght37428123456789pareparentweight3374285902012389890000000867234567890000000543902?算法設(shè)計題odeCountBiTreeT{return0;c;}隊列C.樹D.圖(9)用鄰接表表示圖進行深度優(yōu)先遍歷時,通常借助()來實現(xiàn)算法。A.棧B.隊列C.樹D.圖(10)深度優(yōu)先遍歷類似于二叉樹的()°A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷(11)廣度優(yōu)先遍歷類似于二叉樹的()。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷BFSDFS)。A.小B.相等C.小或相等D.大或相等已知圖的鄰接矩陣如圖所示，則從頂點0111001110001001100110101101001010001的結(jié)果是()A.0243156B.0136542C.0134256D.03615420出發(fā)按廣度優(yōu)先遍歷的結(jié)果是(),按0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是(),按深度優(yōu)先遍歷的結(jié)果是()。B.0231C.0321D.0123 (15)下面()方法可以判斷出一個有向圖是否有環(huán)。A.深度優(yōu)先遍歷B.拓撲排序C.求最短路徑D.求關(guān)鍵路徑 出:每個頂點的入度和出度；①鄰接矩陣；②④③<j)A*]2223114L3呂21623CJ陣⑶鄲接表⑷連鄰接農(nóng)(2)已知如圖所示的無向網(wǎng)，請給出:①鄰接矩陣；②鄰接表；③最小生成樹43445954595595595765576573765465422656aabcdefffAAAdfg5573266fffff別深度優(yōu)先生就屈廣度優(yōu)先生成厠00D0 (4)有向網(wǎng)如圖所示，試用迪杰斯特拉算法求出從頂點a到其他各頂點間的最短路徑,{a,c,f,e,d,g,b}acfdg{a,c,f,e,d,g}H(a,c,f,d){a,c,f,e,d}(a,c,f,d)aceacf,e}bcdefgS終ace6cfcf2 (5)試對圖所示的AOE網(wǎng):①求這個工程最早可能在什么時間結(jié)②求每個活動的最早開始時間和最遲③確定哪些活動是關(guān)鍵活動AOE【解答】按拓撲有序的順序計算各個頂點的最早可能開始時間Ve和最遲允許開始時間04652<<,2><5,<<,2><5,6><<,5><4,6>4>4>e00e0000000880000880此工程最早完成時間為43此工程最早完成時間為43。關(guān)鍵路徑為<1,3><3,2><2,5><5,6>①增添一個新頂點v,lnsertVex(G,v)；③增加一條邊<v,w>,InsertArc(G,v,w);④刪除一條邊<v,w>,DeleteArc(G,v,w)。{}dj55}St