舊數(shù)據(jù)結構導論試卷一

1、數(shù)據(jù)結構導論試題一數(shù)據(jù)結構導論試題一（課程代碼：（課程代碼：2142）一、單項選擇題（本大題共一、單項選擇題（本大題共15小題，每小題小題，每小題2分，共分，共30分）分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。括號內。錯選、多選或未選均無分。1算法指的是【A】A對特定問題求解步驟的一種描述。B計算

2、機程序C排序方法D數(shù)據(jù)處理2在數(shù)據(jù)結構課程里決定選取何種存儲結構時，一般不考慮【A】A各結點的值如何B結點個數(shù)的多少C對數(shù)據(jù)有哪些運算D所用編程語言實現(xiàn)這種結構是否方便3線性表采用鏈接存儲時，其地址【D】A必須是連續(xù)的B部分地址必須是連續(xù)的C一定是不連續(xù)的D連續(xù)與否均可以4設線性表有n個元素，在順序表上實現(xiàn)比在鏈表上實現(xiàn)效率高的算法是【A】A輸出第i(0≤i≤n—1)個元素值B交換第0個元素與第1個元素的值C順序輸出這n個元素的值D輸出

3、與給定值x相等的元素在線性表中的序號5在一個以head為頭指針的非空循環(huán)單鏈表中，尾結點指針p滿足【A】A.pnext==headB.pnext==NULLC.p==NULLD.p==head6若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且隊尾指針rear和隊頭指針front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少【B】A.1和5B.2和4C.4和2D.5和17若一個棧的輸入序列是1，2，

4、3，…，n，輸出序列的第一個元素是n，則第i個輸出元素是【D】A不確定BniCni1Dni18對特殊矩陣采用壓縮存儲的目的主要是為了【D】A表達變得簡單B對矩陣元素的存取變得簡單C去掉矩陣中的多余元素D減少不必要的存儲空間9設二叉樹有n個結點，則其深度為【D】An一1BnCD不能確定10按照二叉樹的定義，具有3個結點的二叉樹有【C】素，與已經排序序列中的元素作比較，將其放入已排序序列的正確位置上。15對n個元素進行冒泡排序，在所有元素有

5、序的情況下比較的次數(shù)為n(n1)2。三、應用題（本大題共三、應用題（本大題共5小題，每小題小題，每小題5分，共分，共25分）分）1若頻繁地對一個線性表進行插入和刪除操作，則該線性表宜采用何種存儲結構，為什么鏈式存儲結構。因為插入和刪除操作需要從頭結點起查找被插入或刪除結點的前驅結點，并修改這些結點的指針域，查找過程平均移動指針域為表長的一半；而采用順序結構存儲線性表，插入和刪除操作需要平均移動表中的一半元素。但移動指針域操作比移動元素操

6、作花費的時間少得多。2設有編號為1，2，3，4，5，6的六輛列車，順序進入一個棧式結構的站臺，問：能否得到編號序列為435612不能和135426能的出站順序，并說明為什么不能得到或者如何得到。（進棧操作用push表示出棧操作用pop表示）3對如下圖所示的一棵二叉樹，試寫出它的先根遍歷、中根遍歷和后根遍歷的結果序列。先根：ABDEGCF中根：DBGEACF后根：DGEBFCA4一棵二叉排序樹的結構如下圖，結點的值為1～8，請在各結點所在