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

經(jīng)典word整理文檔，僅參考，雙擊此處可刪除頁眉頁腳。本資料屬于網(wǎng)絡(luò)整理，如有侵權(quán)，請聯(lián)系刪除，謝謝！數(shù)據(jù)結(jié)構(gòu)考試試題及答案2009-05-1209:22計(jì)科2班期中考試題word//192.168.130.50的“計(jì)科2班考試”文件夾中。一．填空題（每題1分，共10分）（）已知一個(gè)順序存儲的線性表，設(shè)每個(gè)結(jié)點(diǎn)需占m個(gè)存儲單元，若第0個(gè)元素的地址為address,則第i個(gè)結(jié)點(diǎn)的地址是（address+i*m）。（）線性表有兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，就兩種存儲結(jié)構(gòu)完成下列填空：（順序存儲結(jié)構(gòu)可以隨機(jī)存取，（鏈?zhǔn)酱鎯Y(jié)構(gòu)）不可以隨機(jī)存取，（鏈?zhǔn)酱鎯Y(jié)構(gòu)）插入和刪除操作比較方便。（3也相鄰不一定）相鄰。）存儲密度較大，（鏈?zhǔn)酱鎯Y(jié)構(gòu)）存儲利用率較高，（順序存儲結(jié)構(gòu)）（）在一個(gè)長度為ni0<=i<=nn-i+1）個(gè)元素。（）在順序表la的第i個(gè)元素前插入一個(gè)新元素，則有效的i值范圍是（0<=i<=length-1表lb的第j個(gè)元素之后插入一個(gè)新元素，則j的有效范圍是（0<=j<=length-1）；要?jiǎng)h除順序表lc的第k個(gè)元素，則k的有效范圍是（0<=k<=length-1）。（）設(shè)有一個(gè)空棧，現(xiàn)有輸入序列為1，，，，5，經(jīng)過操作序列push,pop,push,push,pop,push,push,pop后，現(xiàn)在已出棧的序列是1,3,54。，棧頂元素的值是（）設(shè)有棧S，若線性表元素入棧順序?yàn)椋?，，，得到的出棧序列?，3，，，則用棧的基本運(yùn)算Push,Pop描述的操作序列為push,pop,push,push,pop,push,pop,。（）在隊(duì)列結(jié)構(gòu)中，允許插入的一端為隊(duì)尾，允許刪除的一端為對頭（）在一個(gè)鏈隊(duì)列中，若隊(duì)頭指針為隊(duì)尾指針為，則判斷該隊(duì)列只有一個(gè)結(jié)點(diǎn)的條件Q.front->next=Q.rear（10）設(shè)循環(huán)隊(duì)列的頭指針front指向隊(duì)頭元素，尾指針rear指向隊(duì)尾元素后的一個(gè)空閑元素，隊(duì)列的最大空間為MAX，則隊(duì)空的標(biāo)志為Q.front=Q.rear，隊(duì)滿的標(biāo)志為(Q.rear+1)%MAX=Q.rear<front時(shí)隊(duì)列長度是Q.rear-Q.front+MAX）；在順序。。當(dāng)二．判斷題（每題0.5分，共5分。正確用T表示，錯(cuò)誤用F表示）（）棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。T（）設(shè)棧的輸入序列是，，····，若輸出序列的第一個(gè)元素是，則第i個(gè)輸出元素是n-i+1.F（）若一個(gè)棧的輸入序列是，，···，輸出序列的第一個(gè)元素是，則第i個(gè)輸出元素不確定。T（）循環(huán)隊(duì)列不會(huì)發(fā)生溢出。F（）鏈隊(duì)列與循環(huán)隊(duì)列相比，前者不會(huì)發(fā)生溢出。T（）直接或間接調(diào)用自身的算法就是遞歸算法。T（）數(shù)據(jù)元素是數(shù)據(jù)的最小單位。F（）數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。T（）算法的時(shí)間復(fù)雜度是算法執(zhí)行時(shí)間的絕對度量。F（10）算法的正確性是指算法不存在錯(cuò)誤。F三．簡答題（滿分5分）（1）假設(shè)我們要從線性表中刪除一個(gè)數(shù)據(jù)元素，如圖1-1所示，已知p為其單鏈表存儲結(jié)構(gòu)中指向結(jié)點(diǎn)a的指針。寫出刪除結(jié)點(diǎn)b后，修改指針的語句。（此題2分）ab1cpp→next=p→next→next圖1-1（）編制一程序（可用偽碼描述，寫出解題思路可酌情得分）：對于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，輸出與其等值的16進(jìn)制數(shù)。（此題3分）voidconversion(){InitStack(S);scanf(“%d”N)while(N){Push(S,N%16);N=N/16;}while(!StackEmpty(s)){Pop(S,e);Printf(“%d”,e)}}輸入一個(gè)十進(jìn)制數(shù)N，使N對16求余，構(gòu)造一個(gè)空棧，并將余數(shù)入棧，再將N除16的值賦給；依次循還，再將棧中元素進(jìn)行出棧操作即可。1．用單鏈表方式存儲的線性表，存儲每個(gè)結(jié)點(diǎn)需要兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是（.B）。A.當(dāng)前結(jié)點(diǎn)的所在地址C.空指針域B.后繼結(jié)點(diǎn)的所在地址D.空閑域2．在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，則刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的正確操作是(C)C.p->next=p->next->next應(yīng)該是在頂端進(jìn)行取數(shù)據(jù)的操作)4．設(shè)數(shù)組Data[0..m]作為循環(huán)隊(duì)列SQfront為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作的語句為（D）．front=front+1D.front=(front+1)%(m+1)5.已知函數(shù)Sub(s,i,j)的功能是返回串s中從第i個(gè)字符起長度為j的功能為復(fù)制串t到。若字符串〃SCIENCESTUDY〃，則調(diào)用函數(shù)Scopy(P,Sub(S,1,7))后得到(A)2〃SCIENCE〃C.S=〃SCIENCE〃6．在最好和最壞情況下的時(shí)間復(fù)雜度均為O(nlogn)且穩(wěn)定的排序方法是(C)B.堆排序D.基數(shù)排序7．圖的鄰接表如下所示，從頂點(diǎn)V1出發(fā)采用深度優(yōu)先搜索法遍歷該圖，則可能的頂點(diǎn)序列是()A.V1V2V3V4V5C.V1V4V3V5V2)直接插入排序法C.基數(shù)排序法B.冒泡排序法D.歸并排序法數(shù)據(jù)結(jié)構(gòu)考試試題及答案1一、判斷下列敘述的對錯(cuò)。（）線性表的邏輯順序與物理順序總是一致的。（）線性表的順序存儲表示優(yōu)于鏈?zhǔn)酱鎯Ρ硎?。（）線性表若采用鏈?zhǔn)酱鎯Ρ硎緯r(shí)所有結(jié)點(diǎn)之間的存儲單元地址可連續(xù)可不連續(xù)。（）二維數(shù)組是其數(shù)組元素為線性表的線性表。（）每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算：插入、刪除和搜索。二、設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為typedefstructnode{file://鏈表結(jié)點(diǎn)定義ElemType；file://數(shù)據(jù)structnode*；file://結(jié)點(diǎn)后繼指針}ListNode；（）已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè)操作？A.s->link=；p->link=；B.s->link=；p->link=s；C.s->link=；p=s；D.p->link=；s->link=；（）非空的循環(huán)單鏈表first的尾結(jié)點(diǎn)（由p所指向）滿足：A.p->link==NULL；B.p==NULL；C.p->link==first；D.p==first；Ss1，，，s4，s5，s6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)?，，s4，，，，則順序棧的容量至少應(yīng)為多少？四、一棵具有n個(gè)結(jié)點(diǎn)的理想平衡二叉樹（即除離根最遠(yuǎn)的最底層外其他各層都是滿的，最底層有若干結(jié)3點(diǎn)）有多少層？若設(shè)根結(jié)點(diǎn)在第0層，則樹的高度h如何用n來表示（注意n可能為）？五、從供選擇的答案中選擇與下面有關(guān)圖的敘述中各括號相匹配的詞句，將其編號填入相應(yīng)的括號內(nèi)。（）對于一個(gè)具有n個(gè)結(jié)點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則頂點(diǎn)表的大小為（表中邊結(jié)點(diǎn)的總數(shù)為（B（）采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于樹的（（）采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于樹的（（）判斷有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用（E供選擇的答案：①②③n-1④n+eB：①②③④n+eC~D：①中根遍歷②先根遍歷③后根遍歷④按層次遍歷E：①求關(guān)鍵路徑的方法②求最短路徑的Dijkstra方法③深度優(yōu)先遍歷算法④廣度優(yōu)先遍歷算法六、填空題（）在用于表示有向圖的鄰接矩陣中，對第i行的元素進(jìn)行累加，可得到第i個(gè)頂點(diǎn)的（①）度，而對第j列的元素進(jìn)行累加，可得到第j個(gè)頂點(diǎn)的（②）度。（）一個(gè)連通圖的生成樹是該圖的（③）連通子圖。若這個(gè)連通圖有n個(gè)頂點(diǎn)，則它的生成樹有（④）條邊。（{100，，48，，35，，42，，66，，按堆結(jié)構(gòu)的定義，則它一定（⑤）堆。（）在進(jìn)行直接插入排序時(shí)，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列（⑥）關(guān)；而在進(jìn)行直接選擇排序時(shí)，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列（⑦）關(guān)。（）利用關(guān)鍵碼分別為10，20，30，40的四個(gè)結(jié)點(diǎn)，能構(gòu)造出（⑧）種不同的二叉搜索樹。七、設(shè)帶表頭結(jié)點(diǎn)的雙向鏈表的定義為typedefint；typedefstructdnode{file://雙向鏈表結(jié)點(diǎn)定義ElemType；file://數(shù)據(jù)structdnode*，*rLink；file://結(jié)點(diǎn)前驅(qū)與后繼指針；typedefDblNode*DblList；file://雙向鏈表試設(shè)計(jì)一個(gè)算法，改造一個(gè)帶表頭結(jié)點(diǎn)的雙向鏈表，所有結(jié)點(diǎn)的原有次序保持在各個(gè)結(jié)點(diǎn)的右鏈域rLink中，并利用左鏈域lLink把所有結(jié)點(diǎn)按照其值從小到大的順序連接起來。八、設(shè)有一個(gè)關(guān)鍵碼的輸入序列{55，31，，37，46，73，63，02，07，（）從空樹開始構(gòu)造平衡二叉搜索樹，畫出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹的形態(tài)。若發(fā)生不平衡，指明需做的平衡旋轉(zhuǎn)的類型及平衡旋轉(zhuǎn)的結(jié)果。（）計(jì)算該平衡二叉搜索樹在等概率下的查找成功的平均查找長度和查找不成功的平均查找長度。4九、下面是求連通網(wǎng)絡(luò)的最小生成樹的Prim算法的實(shí)現(xiàn)，中間有5個(gè)地方缺失，請閱讀程序后將它們補(bǔ)上。constintMaxInt=INT_MAX；file://INT_MAX的值在中constintn=6；file://圖的頂點(diǎn)數(shù)，應(yīng)由用戶定義typedefint；file://用二維數(shù)組作為鄰接矩陣表示typedefstructfile://生成樹的邊結(jié)點(diǎn)intfromVex，toVex；邊的起點(diǎn)與終點(diǎn)intweight；file://邊上的權(quán)值；typedefTreeEdgeNode；file://最小生成樹定義voidPrimMST（AdjMatrix，MST，intrt）{file://從頂點(diǎn)rt出發(fā)構(gòu)造圖G的最小生成樹，rt成為樹的根結(jié)點(diǎn)TreeEdgeNode；inti，k=，，，；for（i=；i<n；i++）file://初始化最小生成樹Tif（i！=rt）{T[k>.fromVex=rt；T[k>.toVex=I；T[k++>.weight=G[rt>；}for（k=；k<；k++）{file://依次求MST的候選邊min=MaxInt；for（i=；i<n-1；i++）file://遍歷當(dāng)前候選邊集合if（T.weight<min）file://選具有最小權(quán)值的候選邊{min=；minpos=i；}if（min==MaxInt）圖不連通，出錯(cuò)處理{cerr《“Graphis！”《；exit（1）；}e=；T[minpos>=T[k>；T[k>=；v=；for（i=；i<n-1；i++）修改候選邊集合if（G[v>[T.toVex><T.weight）T.weight=G[v>[T.toVex>；T.fromVex=v；參考答案）錯(cuò)（）錯(cuò)（）對（）錯(cuò)（5）對）B（）C三、35四、h（）五、①B.③②④③六、①出②入③極?、躰-1⑤是（最?。抻孝邿o⑧14七、算法如下voidsort（DblNode*L）{DblNode*s=L->rlink；file://指針s指向待插入結(jié)點(diǎn)，初始時(shí)指向第一個(gè)結(jié)點(diǎn)while（s！=NULL）{file://處理所有結(jié)點(diǎn)pre=；p=；file://指針p指向待比較的結(jié)點(diǎn)，pre是p的前驅(qū)指針while（p！=NULL&&s->data<p->data）file://循lLink鏈尋找結(jié)點(diǎn)*s的插入位置{pre=；p=；}pre->lLink=；s->lLink=；s=；file://結(jié)點(diǎn)*s在lLink方向插入到*pre與*p之間}八、關(guān)鍵碼的輸入序列{，31，，37，46，73，63，02，07}在等概率下查找成功的平均查找長度在等概率下查找不成功的平均查找長度九①T[k>.toVex=i②min=MaxInt③minpos=i④（）⑤T.fromVex=v數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案2009-01-0411:22期末樣卷參考答案一．是非題（每題1分共10分）1.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。F2.棧和隊(duì)列也是線性表。如果需要，可對它們中的任一元素進(jìn)行操作。F3．字符串是數(shù)據(jù)對象特定的線性表。T4．在單鏈表P指針?biāo)附Y(jié)點(diǎn)之后插入S結(jié)點(diǎn)的操作是：P->next=S;S->next=P->next;F5．一個(gè)無向圖的連通分量是其極大的連通子圖。T6．鄰接表可以表示有向圖，也可以表示無向圖。T7．假設(shè)B是一棵樹，B′是對應(yīng)的二叉樹。則B的后根遍歷相當(dāng)于B′的中序遍歷。T8．通常，二叉樹的第i層上有2i-1個(gè)結(jié)點(diǎn)。F69．對于一棵m階的B-樹,樹中每個(gè)結(jié)點(diǎn)至多有m個(gè)關(guān)鍵字。除根之外的所有非終端結(jié)點(diǎn)至少有ém/2ù個(gè)關(guān)鍵字。F10．對于任何待排序序列來說，快速排序均快于起泡排序。F二．選擇題（每題2分共28分）1．在下列排序方法中，（c）方法平均時(shí)間復(fù)雜度為0(nlogn)，最壞情況下時(shí)間復(fù)雜度為0(n2)；（d）方法所有情況下時(shí)間復(fù)雜度均為0(nlogn)。a.插入排序b.希爾排序c.快速排序d.堆排序2.在有n個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表表示中，空指針數(shù)為（b）。a.不定3.下列二叉樹中，（a）可用于實(shí)現(xiàn)符號不等長高效編碼。a.最優(yōu)二叉樹b.次優(yōu)查找樹c.二叉平衡樹d.二叉排序樹4.下列查找方法中，（a）適用于查找有序單鏈表。a.順序查找b.二分查找c.分塊查找5.在順序表查找中，為避免查找過程中每一步都檢測整個(gè)表是否查找完畢，可采用（a）方法。a.設(shè)置監(jiān)視哨b.鏈表存貯c.二分查找d.快速查找6.在下列數(shù)據(jù)結(jié)構(gòu)中，（c）具有先進(jìn)先出特性，（b）具有先進(jìn)后出特性。a．線性表b．棧c．隊(duì)列d．廣義表7．具有m個(gè)結(jié)點(diǎn)的二叉排序樹，其最大深度為（f），最小深度為（b）。b.n+1c.nd.n-1d.哈希查找a.log2mb.└log2m┘+1e.┌m/2┐c.m/2f.md.┌m/2┐-18．已知一組待排序的記錄關(guān)鍵字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。下列選擇中（c）是快速排序一趟排序的結(jié)果。（b）是希爾排序（初始步長為4）一趟排序的結(jié)果。（d）是基數(shù)排序一趟排序的結(jié)果。（a）是初始堆（大堆頂）。a.84，79，64，37，57，52，58，26，28，34，56。b.28，34，57，26，56，52，58，37，79，84，64。c.28，34，37，26，52，56，64，79，58，84，57。d.52，34，64，84，56，26，37，57，58，28，79。e.34，56，26，58，52，64，37，28，79，57，84。f.34，56，26，58，52，79，37，64，28，84，57。三．填空題（每題2分共20分）1．有向圖的存儲結(jié)構(gòu)有（鄰接矩陣）、（鄰接表）、（十字鏈表）等方法。2．已知某二叉樹的先序遍歷次序?yàn)閍fbcdeg，中序遍歷次序?yàn)閏edbgfa。其后序遍歷次序?yàn)椋╡dcgbfa）。層次遍歷次序?yàn)椋╝fbcgde）。3．設(shè)有二維數(shù)組A5x7每一元素用相鄰的4個(gè)字節(jié)存儲，存儲器按字節(jié)編址。已知A00的存儲地址為100。則按行存儲時(shí)，元素A14的第一個(gè)字節(jié)的地址是（144）；按列存儲時(shí)，元素A14的第一個(gè)字節(jié)的地址是（184）。4．請?jiān)谙聞澗€上填入適當(dāng)?shù)恼Z句，完成以下法算。StatusPreordertraverse(BitreeT,Status(*Visit)(Telemtypee)){//先序非遞歸遍歷二叉樹。Initstack(S);Push(S,T);While(!stackempty(S)){While(gettop(S,p)&&p){visit(p->data);push(S,p->lchild;}Pop(S,p);If(!stackempty(s)){pop(S,p);push(S,p->rchild);}7}returnok;四．簡答題（每題5分共25分）1．將圖示森林轉(zhuǎn)換為二叉樹，并對該二叉樹中序全序線索化。hdajibfecmlkg2．已知Hash函數(shù)為H（K）=Kmod13，散列地址為0--14，用二次探測再散列處理沖突，給出關(guān)鍵字（23，34，56，24，75，12，49,52，36，92，06，55）在散列地址的分布。012345678910111213143.右圖為一棵3階B樹。20，25）a.畫出在該樹上插入元素15后的B樹。／│＼b.接著，再刪除元素35，畫出刪除后的B樹。(10,14)（21）（35）4.已知某無向圖的鄰接表存儲結(jié)構(gòu)如圖所示。a.請畫出該圖。b.根據(jù)存儲結(jié)構(gòu)給出其深度優(yōu)先遍歷序列及廣度優(yōu)先遍歷序列。c.畫出其深度優(yōu)先生成樹及廣度優(yōu)先生成樹。0a1b2c3d4e224/\314/\4/\01/\012/\5.設(shè)在某通信系統(tǒng)中使用了八個(gè)字符，它們出現(xiàn)的頻率分別為0.080.050.10.120.260.180.140.07，試構(gòu)造一棵赫夫曼樹，并給出赫夫曼編碼。五．算法設(shè)計(jì)題（共17分）1.單鏈表結(jié)點(diǎn)的類型定義如下：typedefstructLNode{intdata;structLNode*next;}LNode,*Linklist;寫一算法，將帶頭結(jié)點(diǎn)的有序單鏈表A和B合并成一新的有序表C。8(注:不破壞A和B的原有結(jié)構(gòu).)Merge(LinklistA,LinklistB,Linklist&C)voidMerge(LinklistA,LinklistB,Linklist&C){C=(Linklist)malloc(sizeof(LNode));pa=A->next;pb=B->next;pc=C;while(pa&&pb){pc->next=(Linklist)malloc(sizeof(LNode));pc=pc->next;if(pa->data<=pb->data){pc->data=pa->data;pa=pa->next;}else{pc->data=pb->data;pb=pb->next;}}if(!pa)pa=pb;while(pa){pc->next=(Linklist)malloc(sizeof(LNode));pc=pc->next;pc->data=pa->data;pa=pa->next;}pc->next=NULL;}2.二叉樹用二叉鏈表存儲表示。typedefstructBiTNode{TelemTypedata;StructBiTNode*lchild,*rchild;}BiTNode,*BiTree;編寫一個(gè)復(fù)制一棵二叉樹的遞歸算法。BiTreeCopyTree(BiTreeT){if(!T)returnNULL;if(!(newT=(BiTNode*)malloc(sizeof(BiTNode))))exit(Overflow);newT->data=T->data;newT->lchild=CopyTree(T->lchild);newT->rchild=CopyTree(T->rchild);returnnewT;}//CopyTree數(shù)據(jù)結(jié)構(gòu)期中考試試題及答案一、單選題（每小題2分，共8分）1.在一個(gè)長度為n的線性表中順序查找值為x的元素時(shí)，查找成功時(shí)的平均查找長度（即x同元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為C。A.nB.n/2C.(n+1)/2D.(n-1)/292.在一個(gè)帶附加表頭的單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行D。A.HL=p;p->next=HL;C.p->next=HL;p=HL;B.p->next=HL;HL=p;D.p->next=HL->next;HL->next=p;3．若讓元素A，B，C，D依次入棧，則出棧次序不可能出現(xiàn)D種情況。A.D,C,B,AB.A,D,C,BC.B,A,D,CD.D,A,B,C4．從一個(gè)順序隊(duì)列刪除元素時(shí)，首先需要A.前移一位隊(duì)首指針B。B.后移一位隊(duì)首指針C.取出隊(duì)首指針?biāo)肝恢蒙系脑谼.取出隊(duì)尾指針?biāo)肝恢蒙系脑囟?、填空題（每空1分，共32分）1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性、樹型、圖形四種。2.函數(shù)重載要求參數(shù)個(gè)數(shù)、參數(shù)類型或參數(shù)次序有所不同。3表頭附加結(jié)點(diǎn)的左右指針域指向表頭附加結(jié)點(diǎn)。4．在以HL為表頭指針的帶附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為HL->next==NULL和HL==HL->next。5．在由數(shù)組a中元素結(jié)點(diǎn)構(gòu)成的單鏈表中，刪除下標(biāo)為i的結(jié)點(diǎn)后，需要把該結(jié)點(diǎn)插入到空閑表的表頭，具體操作為a[i].next=a[1].next、a[1].next=i。6ai的結(jié)點(diǎn)的后繼結(jié)點(diǎn)并將被刪除結(jié)點(diǎn)的下標(biāo)賦給i時(shí)，所進(jìn)行的操作（需要用一個(gè)臨時(shí)變量p）描述為p=a[i].next和a[i].next=a[p].next;i=p。7．在稀疏矩陣的十字鏈接存儲中，每個(gè)結(jié)點(diǎn)的down指針域指向列號相同的下一個(gè)結(jié)點(diǎn)，right指針域指向行號相同的下一個(gè)結(jié)點(diǎn)。8．一個(gè)廣義表中的元素分為單元素和表元素兩類。9．廣義表A=((a,(b,(),c),((d),e)))的長度為1，深度為4。10．向一個(gè)順序棧插入一個(gè)元素時(shí)，首先應(yīng)top++，然后再將待插入元素放入棧頂位置。1011．對于隊(duì)列，應(yīng)在隊(duì)尾進(jìn)行插入，在隊(duì)首進(jìn)行刪除。12．中綴表達(dá)式2+7/(4-1)所對應(yīng)的后綴表達(dá)式為2741-/+@。13．后綴表達(dá)式“10354-*-1+32+-”的值為3。14.一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g))),則e結(jié)點(diǎn)的雙親結(jié)點(diǎn)為a，孩子結(jié)點(diǎn)為f，樹的深度為4。三、運(yùn)算題（每小題8分，共24分）1．假定線性表L=（33,69,78,22,44,88）,i=3,x=34,y=22,則對L進(jìn)行下列一組操作`ListEmpty(L);falseGetElem(L,i);78InsertFront(L,x);InsertRear(L,x);DeleteFront(L);Delete(L,y);(34336978224488)(3433697822448834)(33697822448834)(336978448834)(333444697888)(33344466697888)Sort(L);Insert(L,66);請寫出每步操作后的結(jié)果。2．假定線性表L=（33,85,21,56,30,63,42,91,76）,調(diào)用順序表的排序算法voidSort(List&L)對此表進(jìn)行排序，請寫出排序過程。（將每一步結(jié)果寫出）（1）[3385]21563063429176（2）[213385]563063429176（3）[21335685]3063429176（4）[2130335685]63429176（5）[213033566385]429176（6）[21303342566385]917611（7）[2130334256638591]76（8）[213033425663768591]3．已知一個(gè)中綴表達(dá)式為：10-3*(2+1)+(3-1)/2@，請畫出其轉(zhuǎn)換為后綴表達(dá)式過程中S2及R棧的變化。S10321R@-*(+S10321