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