數(shù)據(jù)結構考題

單元練習1數(shù)據(jù)有邏輯結構和（儲存結構）兩種結構。數(shù)據(jù)邏輯結構除了集合以外，還包括線性結構、樹形結構和圖形結構線性結構中的元素之間存在一對一的關系。樹形結構中的元素之間存在一對多的關系。圖形結構中的元素之間存在多對多的關系。數(shù)據(jù)在計算機存儲器內表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為順序儲存結構鏈式存儲的存儲結構所占空間分為兩部分，一部分存放結點的值，另一部分存表示結點間的關系指針單元練習2順序表相對于鏈表的優(yōu)先的是：節(jié)省存儲和隨機存儲。鏈表相對于順序表的優(yōu)點的是：插入、刪除方便。當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入、刪除操作，但要求以最快速度存取表中元素時，應采取竝存儲結構。在一個長度為n的順序表中刪除第i個元素，要移動n-i個元素。在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移動n-i+l個元素。線性表的元素總數(shù)不確定，且經(jīng)常需要進行插入和刪除操作，應采用鏈式存儲結構。t20j-I：如圖M小的鏈我小'笫杵指計P所用的沽，■：之||I插入數(shù)山域仇為-和h的網(wǎng)平結點.剛可用下列兩個語旬：和P->next=S;來冥觀諫操一411一411卜和I--iS已知一個順序表的線性表，設每個節(jié)點占m個存儲單位，若第一個節(jié)點的地址為B,則第i個節(jié)點的地址為B+(i-l)*m兩個指針P和Q,分別指向單向鏈表的兩個元素，P所指的元素是Q所指的元素的前驅的條件是p->fromt==Lt.己知踐性表中的元盍星無序的.井-兇帶表頭結點的單漲發(fā)作存儲m試寫一尊法，刪除注中所有大T-mm，小的兀盤，試完成下列程用坦空口X^iii-d-elele1llilislhead;dnCalyptini?nnitij.jcJ[q-hea^l->juext;while(pMSOJLL)[if?fh->da[2j<=tiiin卜11 4 |7山3=口口、p[時;?ih?xi:]eljie{q->tiexi=n->anixi.dCHicf]>j;]j=q->HKXI:]單元練習3在線性結構中，允許插入、刪除的一端稱為棧頂在順序表中，當棧頂指針top=-1時，表示?？杖邕M棧的次序的A、B、C、D、E,執(zhí)行3次出棧操作后，棧頂元素為B4個元素按A、B、C、D順序進S棧，執(zhí)行兩次Pop(S,x)運算后，x的值是C插入和刪除操作只能在一端進行的相形表，稱為棧設有編號為1,2,3,4的四輛列車，順序進入一個棧結構的站臺，不可能的出站順序是1423經(jīng)過下列棧的運算后(InitStack(s);Push(s,a);Pop(s);),在執(zhí)行ReadTop(s)的值是a寫出運方下列程序段的輸出結果voidntainOIS;cJiaLk,y；hiitStackfS). //初始化找k-nc嚴叫"；Push瞎x):PiiishCS「H巧；Push時型:卩op^S,j):PusbCS,"-"):Vtj.wh祐，k)；PapfS.k>：Pueli洛Ts:(tSEniiilyfS)){lJupfS,y):tdut?^;}；cout<<.x;答:屯tack■單元練習4在隊列中存取數(shù)據(jù)應遵循的原則是先進先出隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。在隊列中，允許插入的一端稱為隊尾在隊列中，允許刪除的一端稱為隊首隊列在進行出隊操作時，首先要判斷隊列是否為空解決順序隊列“假溢出”的方法是循環(huán)隊列循環(huán)隊列的隊首指針為front，隊尾指針為rear，則隊空的條件是front==rear隊列Q經(jīng)過下列運算：InitQueue(Q);InQueue(Q,a);InQueue(Q,b);QutQueue(Q,x);ReadFront(Q,x);QFmpty;后的值是(0)。隊列Q經(jīng)過InitQueue(Q);InQueue(Q,a);InQueue(Q,b);QutQueue(Q,x);ReadFront(Q,x);后，x的值是a隊列是限定在端點進行操作的線性表。如進隊的序列為A、B、C、D,則出隊額序列是ABCD4個元素按A、B、C、D順序連續(xù)進隊Q,則隊尾元素是D4個元素按A、B、C、D順序連續(xù)進隊Q,執(zhí)行一次OutQueue(Q)操作后，對頭元素是B四個元素按A、B、C、D順序連續(xù)進隊Q,執(zhí)行四次OutQueue(Q)操作后，在執(zhí)行QEmpty(Q);后的值是1隊列Q,經(jīng)過下列運算后(InitQueue(Q);InQueue(Q，a);InQueue(Q，b)InQueue(Q，x;);ReadFront(Q,x);)，x的值是bo循環(huán)隊列SQ隊滿的條件端點(SQ->rear+l)%MAXLEN==SQ->front若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前front和rear的值分別為3和0,當從列隊中刪除一個元素后,再加入兩個元素后,fronth和rear的值分別為4和2單元練習7在樹中，一個結點所擁有的子樹成為該結點的度度為零的結點稱為葉子結點。樹中結點的最大層次稱為樹的深度對于二叉樹來說，第i層上至多有2i-1個結點。深度為h的二叉樹至多有2h-l個結點。有20個結點的完全二叉樹，編號為10的結點的父結點的編號是5已知完全二叉樹的第8層有8個結點，則其頁結點樹是68由樹轉換成二叉樹時，其根節(jié)點無有子樹三個結點可以組成2種不同形態(tài)樹。將一顆完全二叉樹按層次編號,對于任意一個編號為i的結點,其左孩子結點的編號為2iAEF119)跆定如下圏所示的二AEF119)跆定如下圏所示的二XR.:K］汎字城肪垮列為：玄BEFHCG「根據(jù)二叉樹的定義，具有3個結點的二叉樹有5種樹形o下列4操樹中■IB)￡礎憲全二夏関.A.B.CxC,E.K下列4操樹中■IB)￡礎憲全二夏関.A.B.CxC,E.K仃、H、IA.B.D,II、T-E.<2、F,GC-卜I、D?]-2、E、A，F(xiàn)、C\GD-H--1-<0、Fj--R■■F-.G-hC-.ABC門HAHDFHCFGD.^HCTJRFGII門仍對丁下邊的二咒其中序序列為A.DBEiHAFCU B.DBEIFAFCG把一顆樹轉化為二叉樹后，這顆二叉樹的形態(tài)是唯一的將一顆有100個結點的完全二叉樹從上到下，從左到右一次編號，根節(jié)點額編號為1，則編號為45的結點的有孩子編號為9^

oo4,分別匱出具有3oo4,分別匱出具有3個箱點前胡和三傘結點的二叉轉的所有不同形東.?:J三個姑點的枸⑵三個皓點的二夏樹樹人/OA2C?E6ORrLOA2C?E6ORrL把下列=般樹轉換為二彌(\)A13BHE?5.A13BHE?5.杷-卜列淼林轉換為二叉摘AEGCEDHFe,杷下列AEGCEDHFe,杷下列二叉樹加IS為栽林K：還廂后的二戛樹溝二\8□9355<j)\77.某二夏樹的錯點數(shù)據(jù)黑用順M存「酉其結羈如下:⑴再出該_叉樹〔3分）（即崗出按層次垢出的箱點序列t2^>⑴層找適歷的踣點序列：EAFDHCGIB試訓出柑問的嗆大鮭初井計訓人潸權坷壯也*T1-C2flS)*2t-((j>7^)*a^l>a')*l15313.緒定一亍祝?琨W=M^生入8i:.^WPL,■fi.12.闔F!AF1)11CG1L(J單元練習8A.rhr,8.[1.11A<1&I).掀廠膽沉光迸行遍也,MlnJ'fllifi?fi;的種頂恵r?列為A.rhr,8.[1.11A<1&I).掀廠膽沉光迸行遍也,MlnJ'fllifi?fi;的種頂恵r?列為d.f.cJ".Cih〔D匯.d1\t.b；E七下圖氏猖從頂點"岀疑；⑷如下圖所示，從頂點&出易1心紀疋優(yōu)論辿f」迪!乩副可能爲剋的一種1S點序列為hic.Cid.單元練習9靜態(tài)查找表所含元素個數(shù)在查找階段是固定不變的。在關鍵字序列(7,10,12,18,28,36,45,92)中，用二分查找法查找關鍵字92要比較4次才找到。散列表的查找效率主要取決于散列表造表時選取的散列函數(shù)和處理(沖突)的方法。設散列函數(shù)H和減值kl,k2,若klHk2，而H(kl)=H(k2),則這種情況為沖突散列表查找法德平均查找長度與元素個數(shù)n無關。查找表是以集合為查找結構的。對線性表進行二分查找時，要求線性表必須依順序方式存儲，且結點按關鍵字有序排序衡量查找算法效率的主要目標是平均查找長度一個有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100},當二分查找值為82的結點時，4次比較查找成功。有一個長度為12的有序表，按二分查找法對其驚醒查找，在表內各元素等概率情況下查找成功所需的平均比較次數(shù)為37/12設哈希表長m=14，哈希函數(shù)H(key)=key%11o表中有4個結點：Addr(15)=4Addr(38)=5Addr(61)=6Addr(84)=7其余為空。如果用二次探測在散列處理沖突，關鍵字為49的結點地址是9對于包含n個元素的散列表進行查找，平