數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)題

1、一、填空題 1、數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是 的有限集合，R是D上的 有限集合。2、一個算法的效率可分為 復(fù)雜性和 復(fù)雜性。3、向一個長度為n的線性表的第i個元素(1in+1)之前插入一個元素時，需向后移動 _ _個元素。4、在一個循環(huán)隊列中，隊首指針指向隊首元素的 前一個位置 位置。5、在具有n個單元的循環(huán)隊列中，隊滿時共有 個元素。6、向棧中壓入元素的操作是先 ，后 。7、 稱為空串； 稱為空格串。8、假設(shè)有二維數(shù)組A6×8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000，則數(shù)組A的體積（存儲量）為 ；末尾元素A57的第一

2、個字節(jié)地址為 ；若按行存儲時，元素A14的第一個字節(jié)地址為 ；若按列存儲時，元素A47的第一個字節(jié)地址為 。9、設(shè)一棵完全二叉樹具有1000個結(jié)點，則此完全二叉樹有 個葉子結(jié)點，有 個度為2的結(jié)點，有 個結(jié)點只有非空左子樹，有 個結(jié)點只有非空右子樹。10、線性有序表（a1，a2，a3，a256）是從小到大排列的，對一個給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索 次。設(shè)有100個結(jié)點，用二分法查找時，最大比較次數(shù)是 。11、散列法存儲的基本思想是由 決定數(shù)據(jù)的存儲地址。12、在線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點之間分別存在著 、 和 的聯(lián)系。13、在線

3、性表的單鏈表存儲中，若一個元素所在結(jié)點的地址為p，則其后繼結(jié)點的地址為 ，若假定p為一個數(shù)組a中的下標，則其后繼結(jié)點的下標的 。14、在初始化一個稀疏矩陣的函數(shù)定義中，矩陣形參應(yīng)說明為 參數(shù)。15、棧又稱為 表，隊列又稱為 表。16、后綴表達式“4 5+3*2 4+ *”的值為 。17、一棵深度為5的滿二叉樹中的結(jié)點數(shù)為 個，一棵深度為3的滿四叉樹中的結(jié)點數(shù)為 個。18、對關(guān)鍵字序列(50，34，92，19，11，68，56，41，79)進行直接插入排序，當將第7個關(guān)鍵字56插入到當前的有序子表中時，為尋找插入位置需進行 _ _次關(guān)鍵字之間的比較。19、從一棵二叉排序樹中查找一個元素時， 若元

4、素的值等于根結(jié)點的值，則表明 ，若元素的值小于根結(jié)點的值，則繼續(xù)向 查找，若元素的大于根結(jié)點的值，則向 查找。20、當向一個小頂堆插入一個具有最小值的元素時，該元素需要逐層 調(diào)整，直到被調(diào)整到 位置為止。21、對于一個具有n個頂點的圖，若采用鄰接炬陣表示，則矩陣大小為 。22、對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為 和 。23、從有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素時，其查找長度分別為 和 。24、每次從無序中表示順序取出一個元素，把插入到有序表中的適當位置，此種排序方法叫做_ _排序，每次從無序中表中挑選出一個最小

5、或最大元素，把它交換到有序表的一端，此種排序方法叫做_ _排序。25、若一個算法中的語句頻度之和為T(n)=3720n+4nlogn，則算法的時間復(fù)雜度為 。26、在一棵二叉排序樹中,每個分支點的左子樹上所有結(jié)點的值一定_ _該結(jié)點的值,右子樹上所有結(jié)點的值一定_ _該結(jié)點的值。27、在歸并排序中，進行每趟歸并的時間復(fù)雜度為 ，整個排序過程的時間復(fù)雜度為 ，空間復(fù)雜度為 。28、在如圖所示的鏈表中，若在指針p所指的結(jié)點之后插入數(shù)據(jù)域值相繼為a和b的兩個結(jié)點，則可用下列兩個語句實現(xiàn)該操作，它們依次是_ _和_ _。29、在一個長度為n的循環(huán)鏈表中，刪除其元素值為x的結(jié)點的時間復(fù)雜度(考慮等概率

6、)為_。 30、已知指針p指向某單鏈表中的一個結(jié)點，則判別該結(jié)點有且僅有一個后繼結(jié)點的條件是_。 31、如果入棧序列是1，3，5，97，99，且出棧序列的第一個元素為99，則出棧序列中第30個元素為_。 32、假設(shè)以行優(yōu)先順序存儲三維數(shù)組A567，其中元素A000的地址為1100，且每個元素占2個存儲單元，則A456的地址是_。 33、已知一棵二叉樹的先序序列為ABCD，中序序列為BCAD，則它的后序序列為_。 34、在含n個頂點的連通圖中，任意兩個不同頂點之間的一條簡單路徑最多包含_條邊。 35、對關(guān)鍵字序列(50，34，92，19，11，68，56，41，79)進行直接插入排序，當將第7個

7、關(guān)鍵字56插入到當前的有序子表中時，為尋找插入位置需進行_次關(guān)鍵字之間的比較。 36、對有序表進行二分查找的過程可用判定樹來描述，其判定樹的形態(tài)只取決于_。 37、 若一個算法中的語句頻度之和為T(n)=3720n+4nlogn，則算法的時間復(fù)雜度為_。 二、判斷題（ ）1. 隊列是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結(jié)構(gòu)。（ ）2.滿二叉樹中所有結(jié)點個數(shù)是2k-1-1，其中k是樹的深度。 （ ）3. 棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。 （ ）4.二叉樹中所有結(jié)點，如果不存在非空左子樹，則不存在非空右子樹。 （ ）5.對于一棵非空二叉樹，它的根結(jié)點作為

8、第一層，則它的第i層上最多能有2i1個結(jié)點。 （ ）6. 鏈表的刪除算法很簡單，因為當刪除鏈中某個結(jié)點后，計算機會自動將后續(xù)各個單元向前移動。 （ ）7.用二叉鏈表法存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n+1個為空指針。（ ）8. 具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。（ ）9. 線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。（ ）10. 順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。 三、單項選擇題1數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：（A）存儲結(jié)構(gòu) （B）邏輯結(jié)構(gòu) （C）順序存儲結(jié)構(gòu) （D）鏈式存儲結(jié)

9、構(gòu)2. 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是 （A）110 （B）108 （C）100 （D）1203. 在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O（1）的操作是：（A） 訪問第i個結(jié)點（1in）和求第i個結(jié)點的直接前驅(qū)（2in） （B） 在第i個結(jié)點后插入一個新結(jié)點（1in）（C） 刪除第i個結(jié)點（1in） （D） 將n個結(jié)點從小到大排序4. 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 個元素（A）8 （B）63.5 （C）63 （D）75. 判定一個隊列QU（最多元素為m0）為空隊列的條件是QU->rear Q

10、U->front = = m0 QU->rear QU->front 1= = m0 QU->front = = QU->rear QU->front = = QU->rear+16. 鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表；（A）順序 （B）鏈式 （C）星式 （D）網(wǎng)狀7. 線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址:（A）必須是連續(xù)的 （B）部分地址必須是連續(xù)的（C）一定是不連續(xù)的 （D）連續(xù)或不連續(xù)都可以8 線性表在 情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。（）需經(jīng)常修改中的結(jié)點值 （）需不斷對進行刪除插入 （）中含有大量的結(jié)點 （）中結(jié)點結(jié)構(gòu)

11、復(fù)雜9. 若已知一個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為 i n=i n-i+1 不確定10、在一個長度為n的順序存儲的線性表中，刪除第i個元素（1in）時，需要從前向后依次前移動 個元素。A n-i B n-i+1C n-i-1 C i11、由權(quán)值分別為3，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為_A、24 B、48 C、72 D、5312、假定一個順序隊列的隊首和隊尾指針分別為f和r，則判斷隊空的條件為 。A f+1= =r B r+1= =fC f= =0 D f= =r13、從堆中刪除一個元素的時間復(fù)雜度為 。A O

12、（1） B O（n）C O（1og2n） D O（nlog2n）14、若需要利用形參直接訪問實參，則應(yīng)把形參變量說明為參數(shù)。A指針B引用C值15.數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的( ) A.邏輯結(jié)構(gòu) B.存儲結(jié)構(gòu) C.線性結(jié)構(gòu) D.非線性結(jié)構(gòu) 16.某帶頭結(jié)點的單鏈表的頭指針為head，判定該鏈表為非空的條件是( ) A.head=NULL B.head->next=NULL C.head!=NULL D.head->next!=NULL 17.導(dǎo)致棧上溢的操作是( ) A.棧滿時執(zhí)行的出棧 B.棧滿時執(zhí)行的入棧 C.?？諘r執(zhí)行的出棧 D.?？諘r執(zhí)行的入棧 18.

13、設(shè)數(shù)組Am為循環(huán)隊列Q的存儲空間，front為隊頭指針，rear為隊尾指針，則判定Q為空隊列的條件是( ) A.(rear-front)%m= =1 B.front= =rear C.(rear-front)%m= =m-1 D.front= =(rear+1)%m 19.假設(shè)S=I AM A STUDENT，則運算substr(S,4,8)的結(jié)果為( ) A.M A S B.M A STUD C.A STUDEN D.STUD 20.假設(shè)一棵完全二叉樹按層次遍歷的順序依次存放在數(shù)組BTm中，其中根結(jié)點存放在BT0，若BTi中的結(jié)點有左孩子，則左孩子存放在( ) A.BTi/2 B.BT2*i

14、-1 C.BT2*i D.BT2*i+1 21.連通圖是指圖中任意兩個頂點之間( ) A.都連通的無向圖 B.都不連通的無向圖 C.都連通的有向圖 D.都不連通的有向圖 22.對記錄序列(314，298，508，123，486，145)依次按個位和十位進行兩趟基數(shù)排序之后所得結(jié)果為( ) A.123，145，298，314，486，508 B.508，314，123，145，486，298 C.486，314，123，145，508，298 D.298，123，508，486，145，314 23.在待排關(guān)鍵字序列基本有序的前提下，效率最高的排序方法是( ) A.直接插入排序 B.快速排序 C

15、.直接選擇排序 D.歸并排序 24下列排序算法中，（）算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時，花費的時間反而最多。  A、堆排序  B、冒泡排序  C、快速排序  D、SHELL排序25已知一個有向圖如右所示，則從頂點a出發(fā)進行深度優(yōu)先偏歷，不可能得到的DFS序列為( ) Aa d b e f c Ba d c e f b Ca d c b f e Da d e f b c26一個棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是（ ）。  A、2 3 4 1 5   B、5 4 1 3 2  C、2 3

16、 1 4 5   D、1 5 4 3 227不可能生成右圖所示二叉排序樹的關(guān)鍵字序列是( ) A4 5 3 1 2 B4 2 5 3 1 C4 5 2 1 3 D4 2 3 1 5 28ALV樹是一種平衡的二叉排序樹，樹中任一結(jié)點的( )A 左、右子樹的高度均相同 B 左、右子樹高度差的絕對值不超過1C 左子樹的高度均大于右子樹的高度 D 左子樹的高度均小于右子樹的高度29若結(jié)點的存儲地址與其關(guān)鍵字之間存在某種映射關(guān)系，則稱這種存儲結(jié)構(gòu)為( ) A.順序存儲結(jié)構(gòu) B.鏈式存儲結(jié)構(gòu) C.索引存儲結(jié)構(gòu) D.散列存儲結(jié)構(gòu)四、簡答題 1、 已知如圖所示的有向圖，請給出該圖的:（1） 每個頂點

17、的入/出度；（2） 鄰接矩陣；（3） 鄰接表；（4） 逆鄰接表。頂點123456入度出度 2、 假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個字母設(shè)計哈夫曼編碼。使用07的二進制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。3、 線性表具有兩種存儲方式，即順序方式和鏈接方式?，F(xiàn)有一個具有五個元素的線性表L=23，17，47，05，31，若它以鏈接方式存儲在下列100119號地址空間中，每個結(jié)點由數(shù)據(jù)（占2個字節(jié)）和指針（占2個字節(jié)）組成，如下所示（其中U、X、V、Y、Z為

18、相應(yīng)結(jié)點指針域的指針）：05 U 17 X 23 V 31 Y 47 Z100120其中指針X，Y，Z的值分別為多少？該線性表的首結(jié)點起始地址為多少？末結(jié)點的起始地址為多少？ 4、己知一個帶權(quán)圖的頂點集V和邊集6分別為： V=0，1，2，3，4，5，6，7； E=（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20； 則求出該圖的最小生成樹的權(quán)。 5、對于線性表（18，25，63，50，42，32，90，66）進行散列存儲時，若選用H（K）=K9作為散列函數(shù)，則散列地址為0的元素有 個，散列地址為3的

19、元素有 個，散列地址為5的元素有 個。 6、假定一組記錄的排序碼為（46，79，56，38，40，80，25，34），將其建立二叉排序樹，對應(yīng)二叉排序樹的深度為 ，分支結(jié)點數(shù)為 。7、試推導(dǎo)一棵滿k叉樹（每個結(jié)點的度數(shù)為k或0）上的葉子結(jié)點數(shù)a與非葉子結(jié)點數(shù)b之間滿足以下關(guān)系：a=(k-1)b+1 8、已知關(guān)鍵字序列在R1.8中的初始狀態(tài)為 48 70 33 65 24 56 12 92 寫出在將它進行堆排序過程中每一次數(shù)組R和堆樹的狀態(tài)。9、已知樹T的先序遍歷序列為ABCDEFGHIJKL，后序遍歷序列為CBEFDJIKLHGA。請畫出樹T。10、試證明：若借助棧由輸入序列1 2 n得到的輸

20、出序列為p1，p2，pn，(它是輸入序列的一個排列)，則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j<k，使pj<pk<pi。五、寫出下列程序段的輸出結(jié)果（棧的元素類型SElemType為char） 。1、  int f1(SSTable ST, KeyType kval) /ST為順序查找表 low=1;high=ST.length; while(low<=high) mid=(low+high)/2; if(kval=ST.elemmid.key) return mid; else if(kval<ST.elemmid.key) high=m

21、id-1; else low=mid+1; return 0; 函數(shù)f1的功能為_。2、  int f2(LinkQueue &Q, QelemType &e) /Q為一個帶表頭結(jié)點鏈隊列 if(Q.front=Q.rear) return 0; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear=p) Q.rear=Q.front; delete p; return 1; 函數(shù)f2的功能為_。3、void f3(SqList &L) /L為一個順序表且0下標不存放元

22、素 for(i=1;i<L.length;i+) j=i; for(k=i+1;k<=L.length;k+) if(L.rk.key<L.rj) j=k; if(i!=j) w=L.ri; L.ri=L.rj; L.rj=w; 函數(shù)f3的功能為_。4、void main( )Stack S;char x,y;InitStack(S);x=c;y=k;push(S,x); push(S,a); push(S,y);pop(S,x); push(S,t); push(S,x);pop(S,x); push(S,s);while(!StackEmpty(S) pop(S,y);p

23、rintf(y); ;printf(x);結(jié)果：_5、寫出下列程序段的輸出結(jié)果（隊列中的元素類型QElemType為char）。void main( )Queue Q; Init Queue (Q);Char x=e; y=c;EnQueue (Q,h); EnQueue (Q,r); EnQueue (Q,y);DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ;Printf(x);結(jié)果：_六、算法填空（在下列算法的橫線內(nèi)填上適當?shù)?/p>

24、語句或表達式。） 1、直接選擇排序void selectsort (int R ) / 按遞增序?qū) 0 Rn-1 進行直接選擇排序 int i, j, k, temp ; for (i=0; i<= ; i+) k=i ; for (j= ; j<=n-1; j+) if (R j R k ) k=j; if （ ） temp=R i ; R i = ; R k =temp; 2、中序遍歷二叉樹 設(shè)二叉樹用二叉鏈表表示，以t為根指針，二叉鏈表結(jié)點的類型為node；棧s的元素類型為指向node的指針類型, 棧容量m足夠大。中序遍歷的非遞歸算法如下：struct node char

25、data; node *lc,*rc; ;void preorder (node *t) node *sm ，*p=t ; int top =- 1；/置棧空 do while (p!=NULL) s+top = ; ; if (top!= -) p=stop- -； ； ； while () | ( p ! =NULL ); 3、 從一維數(shù)組An中二分查找關(guān)鍵字為K的元素的遞歸算法，若查找成功則返回對應(yīng)元素的下標，否則返回1。 int Binsch（Elem Type A，int low，int high，KeyType K） if（low<=high） int mid=（low+hi

26、gh）/2； if（K= =Amid.key） ； else if(K<Amid.key) ； else ；else return -1；4、從一維數(shù)組An上進行快速排序的遞歸算法。void QuickSort(ElemType A, int s, int t)int i=s j=t+1;ElemType x=As;do do i+; while ( ); /填寫一個循環(huán)條件do j-; while (Aj.key>x.key);if (i<j)ElemType temp=Ai; Ai=Aj; Aj=temp; while (i<j);As=Aj; Aj=x;if (s

27、<j-1) ;if (j+1<t) ;5、如果希望循環(huán)隊列中的向量單元都能得到利用，則可設(shè)置一個標志域tag,每當尾指針和頭指針值相同時，以tag的值為0或1來區(qū)分隊列狀態(tài)是“空”還是“滿”。請對下列函數(shù)填空，使其分別實現(xiàn)與此結(jié)構(gòu)相應(yīng)的入隊列和出隊列的算法。 int EnQueue(CirQueue *Q,DataType x) if(_) return 0; Q->dataQ->rear=x; Q->rear=(Q->rear+1)% MAXQSIZE Q->tag=_; return 1; int DeQueue(CirQueue *Q,DataT

28、ype *x) if(_) return 0; *x=Q->dataQ->front; Q->front=_ ; Q->tag=_ ; return 1; 6、已知具有n個結(jié)點的完全二叉樹采用順序存儲結(jié)構(gòu)存儲在向量BT1.n中，結(jié)點的數(shù)據(jù)元素為字符類型，請閱讀下列算法，并回答問題： (1)假設(shè)向量BT中的內(nèi)容為： ABCDEFBT : 1 2 3 4 5 6 寫出執(zhí)行f31(BT,6)后的輸出結(jié)果； (2)說明該算法的功能。 void f31(char BT,int n) int i=1; while(i>0) if(i<=n) printf(%c, BTi

29、); i=i*2; else do i=i/2; while(i%2); if(i>0) i+; 7、 以下函數(shù)中，h是帶頭結(jié)點的雙向循環(huán)鏈表的頭指針。 (1)、說明程序的功能(函數(shù)值只能是0或1)； (2)、當鏈表中結(jié)點數(shù)分別為1和6(不包括頭結(jié)點)時，請寫出程序中while循環(huán)體的執(zhí)行次數(shù)。 int f(DListNode *h) DListNode *p,*q; int j=1; p=h->next; q=h->prior; while(p!=q && p->prior!=q) if(p->data=q->data) p=p->n

30、ext; q=q->prior; else j=0; return j; 8、下列算法利用二分查找方法在有序表r中插入元素x，并保持表r的有序性，其中參數(shù)*n為表r的長度。請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。 void BinInsert(SeqList r,int *n,DataType x) int low=1,high=*n,mid,i; while(low<=high) mid= _ ; if (x.key<rmid.key)high=mid-1; else _ ; for(i=*n; _ ;i-) ri+1=ri; _ ; *n+; 七、算法設(shè)計1、指

31、出以下算法中的錯誤和低效（即費時）之處，并將它改寫為一個既正確又高效的算法。Status DeleteK(SqList &a, int i, int k)/本算法是從順序存儲結(jié)構(gòu)的線性表a中刪除第i個元素起的k個元素if ( i<1 | k<0 | i+k> a.length ) return INFEASIBLE; /參數(shù)不合法elsefor(count = 1; count <k; count + ) /刪除一個元素for ( j = a.length; j>=i+1; j-) a.elemj-1 = a.elemj;a.length - -; ret

32、urn OK; / DeleteK注：涉及的類型定義如下：# define LIST INIT SIZE 100# define LISTINCREMENT 10typedef struct Elem Type *elem; /存儲空間基址Int length; /當前長度Int listsize; /當前分配的存儲容量SqList;2、編寫在以BST為樹根指針的二叉排序樹上進行查找值為item的結(jié)點的非遞歸算法，若查找item帶回整個結(jié)點的值并返回1，否則返回0。int Find（BtreeNode*BST，ElemType &item）bool   Find（B

33、treeNode*BST，ElernTypeitem）        while（BST！=NULL）                    if（item= =BST一>data）item=BST一>data；  return  true;            else if（itemBST一>dataBSTBST一>left;else BST=BST一>right；                return