一、單項選擇題(本大題共15小題，每小題2分，共30分。在每小題的四個備選答案中，選出乙個正確答案，並將正確答案的序號填在題幹的括號內)
1.下面程式段的時間複雜度是( ) 。
for(i=0;i for(j=1;j a[i][j]=0；
a.o(nb.o(m+n+1) c.o(m+nd.o(m*n)
2.在單鏈表中，指標p指向元素為x的結點，實現「刪除x的後繼」的語句是
a.p=p->nextb.p->next=p->next->next;
c.p->next=pd.p=p->next->next;
3.在頭指標為head且表長大於1的單迴圈鍊錶中，指標p指向表中某個結點，若p->next->next= head,則
a.p指向頭結點b.p指向尾結點
c.*p的直接後繼是頭結點 d.*p的直接後繼是尾結點
4.判定「帶頭結點的鏈隊列為空」的條件是
a.q.front==nullb.q.rear==null
c.q.front==q.reard.q.front!=q.rear
5.設有兩個串t和p，求p在t中首次出現的位置的串運算稱作
a.聯接b.求子串 c.字元定位 d.子串定位
6.廣義表a=(a,(b),(),(c,d,e))的長度為
a.4 b.5 c.6 d.7
7.一棵含18個結點的二叉樹的高度至少為
a.3 b.4 c.5 d.6
8.已知二叉樹的先序序列為abdecf，中序序列為dbeafc，則後序序列為( ) 。
9.無向圖中乙個頂點的度是指圖中
a.通過該頂點的簡單路徑數 b.與該頂點相鄰接的頂點數
c.通過該頂點的回路數d.與該頂點連通的頂點數
10.已知乙個圖如下所示，從頂點a出發進行廣度優先遍歷可能得到的序列為( ) 。
a.a c e f b d b.a c b d f e c.a c b d e f d.a c d b f e
11.在下列排序方法中，平均時間效能為o(nlogn)且空間效能最好的是( b )。
a.快速排序
b.堆排序
c.歸併排序
d.基數排序
12.已知一組關鍵字為，其中每相鄰兩個為有序子串行。對這些子串行進行一趟兩兩歸併的結果是
a. c.
13.設順序儲存的線性表共有123個元素，按分塊查詢的要求等分成3塊。若對索引表採用順序查詢來確定塊，並在確定的塊中進行順序查詢，則在查詢概率相等的情況下，分塊查詢成功時的平均查詢長度為( b ) 。
a.21 b.23 c.41 d.62
14.索引非順序檔案的特點是
a.主檔案無序，索引表有序 b.主檔案有序，索引表無序
c.主檔案有序，索引表有序 d.主檔案無序，索引表無序
15.倒排檔案的主要優點是
a.便於進行插入和刪除運算 b.便於進行檔案的恢復
c.便於進行多關鍵字查詢d.節省儲存空間
二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分)
16.抽象資料型別的特點是將___資料_____和____運算____封裝在一起，從而現實資訊隱藏。 17.
從順序表中刪除乙個元素時，表中所有在被刪元素之後的元素均需___前移___乙個位置。 18.在佇列中，允許進行插入操作的一端稱為____隊尾____，允許進行刪除操作的一端稱為___隊頭___。
19.如圖兩個棧共享乙個向量空間，top1和top2分別為指向兩個棧頂元素的指標，則「棧滿」 的判定條件是__top1=top2-1____。
20.設s1="good",s2=" ",s3="book"，則s1，s2和s3依次聯接後的結果是_ good book__。
21.假設三維陣列a[10][9][8]按行優先順序儲存，若每個元素佔3個儲存單元，且首位址為100，則元素a[9][8][7]的儲存位址是__2257_____。
22.已知在一棵含有n個結點的樹中，只有度為k的分支結點和度為0的葉子結點，則該樹中含有的葉子結點的數目為__（(n-1)/k）*(k-1)+1_或 n - (n-1)/k__。
23.能夠成功完全拓撲排序的圖一定是乙個__有向無環圖__。
24.如果在排序前，關鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用__堆排序__較為適當。
25.假設雜湊表的表長為m，雜湊函式為h(key)，若用線性探查法解決衝突，則探查位址序列的形式表達為__hi=(h(key)+i)/m___。
三、解答題(本大題共4小題，每小題5分，共20分)
26.假設通訊電文使用的字符集為，名字元在電文中出現的頻度分別為：34，5，12，23，8，18，試為這6個字元設計哈夫曼編碼。
請先畫出你所構造的哈夫曼樹(要求樹中左孩子結點的權值小於右孩子結點的權值)，然後分別寫出每個字元對應的編碼。
27.已知乙個圖如下所示，其頂點按a、b、c、d、e、f順序存放在鄰接表的頂點表中，請畫出該圖的鄰接表，使得按此鄰接表進行深度優先遍歷時得到的頂點序列為acbefd，進行廣度優先遍歷時得到的頂點序列為acbdfe。
答案：28.已知兩個4×5的稀疏矩陣的三元組表分別如下：
0 1 4 16 0 1 1 32
1 2 2 18 1 2 2 －22
2 3 4 －25 2 2 5 69
3 4 2 28 3 3 4 25
4 4 2 51
請畫出這兩個稀疏矩陣之和的三元組表。
解: 29.從空樹起，依次插入關鍵字40，8，90，15，62，95，12，23，56，32，構造一棵二叉排序樹。
(1)畫出該二叉排序樹
(2)畫出刪去該樹中元素值為90的結點之後的二叉排序樹。
四、演算法閱讀題(本大題共4小題，每小題5分，共20分)
30.如圖所示，利用同一迴圈向量空間實現兩個佇列，其型別queue2定義如下：
typedef struct queue2;
對於i=0或1,front[i]和length[i]分別為第i個佇列的頭指標和長度域。請在空缺處填入合適的內容，實現第i個迴圈佇列的入隊操作。
int enqueue(queue2*q,int i,datatype x)
解:(1) (q->front[i]+q->length[i]%maxsize==q->front[(i+1)%2]
(2) (q->front[i]+->length[i]%maxsize
(3) i
31.某二叉樹的線索鍊錶儲存結構如圖(b)所示，其中p為指向根結點的指標，圖(a)為結點結構。
閱讀下列演算法，並回答問題：
(1)寫出執行函式呼叫f(p)的輸出結果；
(2)簡述函式f的功能。
void f(binthrtree t)
}答案（1）abdfcegh (2) 先根遍歷
32.下列函式findcycle(g,i)的功能是，對乙個採用鄰接表作儲存結構的有向圖g，利用深度優先搜尋策略尋找一條經過頂點vi的簡單迴路。陣列cycle_path用於儲存搜尋過程中形成的迴路，cycle_path[k]=j(j≥0)表示在迴路中頂點vk的下乙個頂點是vj。
全國高等教育自學考試資料結構
全國2012年10月高等教育自學考試 資料結構導論試題及答案 課程 02142 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把答題紙上...
全國高等教育自學考試資料結構
全國2013年10月高等教育自學考試 資料結構試題 課程 02331 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把答題紙上對應題目的...
全國高等教育自學考試資料結構試題
全國2007年10月高等教育自學考試 資料結構試題 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.下面程式段的時間複雜度為 s 0 for i 1 i for j ...