一
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
二
請在每小題的空格中填上正確答案
for (i= for(j=i;j t=t+1 17.設某非空單鏈表，其結點形式為 date next ， 若要刪除指針q所指結點的直接後繼結點，則需執行下列語句序列： p=q->next;________;free(p); 18.隊列可以看成是一種運算受限制的線性表，也稱為______線性表。Tw.wINgwit.cOm 19.鏈棧的類型定義如下： typedef struct node { DateType date; struct node *next; }LStackTp; 若棧非空，則退棧操作可以用下列算法片段實現： p=ls;/* ls為棧頂指針*/ *x=p->date; /*棧頂元素通過參數返回*/ ___________; free(p); /*釋放原棧頂結點空間*/ 20.在非空樹上，_____沒有直接前趨。 21.設有33個值，用它們組成一棵哈夫曼樹，則該哈夫曼樹中共有____個結點。 22.無向圖中的連通分量定義為無向圖的_________。 23.在開散列表上查找鍵值等於K的結點，首先必須計算該鍵值的______，然後再通過指針查找該結點。 24.對靜態表順序查找算法采用設置崗哨方式與普通的設置循環控制變量相比，進行一次查找所花費的平均時間大約減少_____。 25.若要對某二叉排序樹進行遍歷，保證輸出的所有結點鍵值序列按遞增次序排列，應對該二叉樹采用_________遍歷法。 26.文件的基本存取單位是_________。 27.設需將一組數據按升序排序。在無序區中依次比較相鄰兩個元素a i 和a i+1 的值，若a i 的值大於a i+1 的值，則交換a i 和a i+1 。如此反復，直到某一趟中沒有記錄需要交換為止，該排序方法被稱為_________。 28.在插入排序、快速排列、堆排序、歸並排序中，排序方法不穩定的有_________。 三、應用題 (本大題共5小題，共30分) 29.現有一組單詞(WEK,SUN,MON,TUE,WED,THU,FRI,SAT),其相應的散列函數值為(3，2，6，3，2，5，6，0)，散列表長度為10(散列地址空間為0..9)，要求：(6分) (1)構造該閉散列表，並用線性探測法解決沖突; (2)若對每個元素查找一次，求總的比較次數。 30.已知無向圖G的鄰接矩陣如下。假設對其訪問時每行元素必須從右到左，請畫出其所有的連通分量，並且寫出按深度優先搜索時各連通分量的訪問序列。(8分)
31.設要將序列(Q，H，C，Y，P，A，M，S，R)按字母升序排序，請畫出采用堆排序方法時建立的初始堆及第一次輸出堆頂元素後篩選調整以後的堆。(8分) 32.設二叉樹後根遍歷的結果為BCA，畫出所有可得到這一結果的二叉樹。(5分) 33.設有一循環隊列sq.data[maxsize],一般情況下隊列中至多可存放多少個元素?為什麼?(3分) 四、設計題 (本大題共2小題，共14分) 34.設有兩個按升序排列的單鏈表X和Y，其頭指針分別為p,q結點結構說明如下： typedef struct nodel { int data; struct nodel *next }node; 試設計一個算法void concat(node *p,*q)將它們合並成一個以p為頭指針的單鏈表Z，使其仍然有序。(6分) 35.設有序表r長度為n，欲在表中查找鍵值為Kn的某元素。若查找成功，則返回該元素在有序表r中的位置，若不成功，則返回0值。用二分查找法，編寫一算法完成上述操作，並給出該算法的平均查找長度。該有序表存儲結構定義如下：(8分) typedef struct { keytype key; Elemtype data; }rec; typedef struct { rec item[maxsize+1]; int n; }sqtable;
From:http://tw.wingwit.com/Article/program/sjjg/201311/23603.html