一、緒論
選擇題1.資料結構是一門研究非數值計算的程式設計問題中計算機的 1 以及它們之間的 2 和運算等的學科。
1 a.資料元素 b.計算方法 c.邏輯儲存 d.資料映像
2 a.結構 b.關係 c.運算 d.演算法
2.資料結構被形式地定義為 (k, r),其中k是 1 的有限集,r是k上的 2 有限集。
1 a.演算法 b.資料元素 c.資料操作 d.邏輯結構
2 a.操作 b.映像 c.儲存 d.關係
3.在資料結構中,從邏輯上可以把資料結構分成 。
a.動態結構和靜態結構 b.緊湊結構和非緊湊結構
c.線性結構和非線性結構 d.內部結構和外部結構
4.線性結構的順序儲存結構是一種 1 的儲存結構,線性表的鏈式儲存結構是一種 2 的儲存結構。
a.隨機訪問 b.順序訪問 c.索引訪問 d.雜湊訪問
5.演算法分析的目的是 1 ,演算法分析的兩個主要方面是 2 。
1 a.找出資料結構的合理性 b.研究演算法中的輸入和輸出的關係
c.分析演算法的效率以求改進 d.分析演算法的易懂性和文件性
2 a.空間複雜度和時間複雜度 b.正確性和簡單性
c.可讀性和文件性 d.資料複雜性和程式複雜性
6.計算機演算法指的是 1 ,它必須具備輸入、輸出和 2 等 5個特性。
1 a.計算方法 b.排序方法 c.解決問題的有限運算序列 d.排程方法
2 a.可執行性、可移植性和可擴充性 b.可行性、確定性和有窮性
c.確定性、有窮性和穩定性 d.易讀性、穩定性和安全性
7.線性表的邏輯順序與儲存順序總是一致的,這種說法 。
a.正確b.不正確
8線性表若採用鏈式儲存結構時,要求記憶體中可用儲存單元的位址 。
a.必須連續的 b.部分位址必須連續的 c.一定是不續的 d連續不連續都可以
9.以下的敘述中,正確的是 。
a.線性表的儲存結構優於鏈式儲存結構 b.二維陣列是其資料元素為線性表的線性表
c.棧的操作方式是先進先出d.佇列的操作方式是先進後出
10.每種資料結構都具備三個基本運算:插入、刪除和查詢,這種說法 。
a.正確b.不正確
填空題1.資料邏輯結構包括三種型別和 ,樹形結構和圖形結構合稱為 。
2.**性結構中,第乙個結點前驅結點,其餘每個結點有且只有個前驅結點;最後乙個結點後續結點,其餘每個結點有且只有個後續結點。
3.在樹形結構中,樹根結點沒有結點,其餘每個結點有且只有個前驅結點;葉子結點沒有結點,其餘每個結點的後續可以 。
4.在圖形結構中,每個結點的前驅結點數和後續結點數可以 。
5.線性結構中元素之間存在關係,樹形結構中元素之間存在關係,圖形結構中元素之間存在關係。
6.演算法的五個重要特性是
7.下面程式段的時間複雜度是 。
for( i = 0; i < n; i++)
for( j = 0; j < m; j++)
a[i][j] = 0;
8.下面程式段的時間複雜度是 。
i = s = 0;
while ( s < n)
9.下面程式段的時間複雜度是 。
s = 0;
for( i = 0; i < n; i++)
for( j = 0; j < n; j++)
s += b[i][j];
sum = s;
10.下面程式段的時間複雜度是 。
i = 1;
while ( i <= n )
i = i * 3;
二、線性表
單項選擇題
1.乙個向量第乙個元素的儲存位址是100,每個元素的長度為2,則第5個元素的位址是 。
a.110 b.108 c.100 d.120
2.乙個棧的入棧序列是a、b、c、d、e,則棧的不可能輸出序列是 。
3.若乙個棧的入棧序列是1、2、3、… 、n,其輸出序列為p1、p2、p3、… 、pn,若p1=n,則pi為 。
a. i b. n = i c. n - i +1 d.不確定
4.棧結構通常採用的兩種儲存結構是 。
a.線性儲存結構和鍊錶儲存結構 b.雜湊方式和索引方式
c.鍊錶儲存結構和陣列 d.線性儲存結構和非線性儲存結構
5.判斷乙個棧st (最多元素為m) 為空的條件是 。
>top!=0 b. st->top==0 c. st->top!= m d. st->top== m
6.判斷乙個棧st (最多元素為m) 為滿棧的條件是 。
>top!=0 b. st->top==0 c. st->top!= m-1 d. st->top== m-1
7.棧的特點是 1 ,佇列的特點是 2 。
a.先進先出 b.先進後出
8.乙個佇列的入隊序列是1、2、3、4,則佇列輸出序列是 。
a.4、3、2、1 b.1、2、3、4 c.1、4、3、2 d.3、2、4、1
9.判斷乙個佇列qu (最多元素為m) 為空的條件是 。
a. qu->rear-qu->front == m b. qu->rear-qu->front-1 == m
c. qu->front == qu->reard. qu->front-qu->rear + 1
10.判斷乙個佇列qu (最多元素為m) 為滿佇列的條件是 。
a. qu->rear-qu->front == m b. qu->rear-qu->front-1 == m
c. qu->front == qu->reard. qu->front-qu->rear + 1
11.判斷乙個迴圈佇列qu (最多元素為m) 為空的條件是 。
a. qu->front == qu->rear b. qu->front != qu->rear
c. qu->front == (qu->rear + 1) %m d. qu->front != (qu->rear + 1) %m
12.判斷乙個迴圈佇列qu (最多元素為m) 為滿佇列的條件是 。
a. qu->front == qu->rear b. qu->front != qu->rear
c. qu->front == (qu->rear + 1) %m d. qu->front != (qu->rear + 1) %m
13迴圈佇列用陣列a[0, m-1]存放其元素值,已知其頭尾指標分別是front和rear,則當前佇列中的元素個數是 。
a.(rear-front + m) %m b. rear-front + 1 c. rear-front-1 d. rear-front
14.棧和佇列的共同點是 。
a.都是先進後出b.都是先進先出
c.只允許在端點處插入、刪除元素 d.沒有共同點
填空題1.向量、棧和佇列都是結構,可以在向量的位置插入和刪除元素;對於棧只能在插入和刪除元素;對於佇列只能在插入元素和刪除元素。
2.在乙個長度為n的向量中的第i個元素(1≤i≤n)之前插入乙個元素時,需向後移動個元素。
3.在乙個長度為n的向量中的刪除第i個元素(1≤i≤n)時,需要向前移動個元素。
4.向棧中壓入元素的操作是
5.對棧進行退棧時的操作是
6.在乙個迴圈佇列中,隊首指標指向隊首元素的
7.從迴圈佇列中刪除乙個元素時,其操作是
8.在具有n個單元的迴圈佇列中,隊滿時共有個元素的。
9.乙個棧的輸入序列是12345,則棧的輸出序列43512是 。
10.乙個棧的輸入序列是12345,則棧的輸出序列12345是 。
三、鍊錶
單項選擇題
1.不帶頭結點的單鏈表head為空的判定條件是 。
>nxt==null >next==head
2.帶頭結點的單鏈表head為空的判定條件是 。
>nxt==null >next==head
3.非空的迴圈單鏈表head的尾結點(由p所指向)滿足 。
>next==null >next==head
4.在迴圈雙鏈表的p所指結點之後插入s所指結點的操作是 。
a. p->right=s;s->left=p;p->right->left=s;s->right=p->right;
b. p->right=s;p->right->left=s;s->left=p;s->right=p->right;
c. s->left=p;s->right=p->right;p->right=s;p->right->left=s;
資料結構複習題
1.資料結構可用三元式表示 d,s,p 其中 d是資料物件,s是d上的關係,p是對d的基本操作集。f 2 簡單地說,資料結構是帶有結構的資料元素的集合。t 3 判斷帶頭結點的非空迴圈單鏈表 頭指標為l 中指標p所指結點是最後乙個元素結點的條件是 p next l。t 4 線性表的鏈式儲存結構具有可直...
資料結構複習題
資料結構複習題 2004年6月 一 單項選擇題 1 鏈棧和順序棧相比,有乙個較明顯的優點是 a.通常不會出現棧滿的情況 b.通常不會出現棧空的情況 c.插入操作更加方便c.刪除操作更加方便 2 若待排序物件序列在排序前已按其排序碼遞增順序排序,則採用 方法比較次數最少。a 直接插入排序b 分劃交換排...
資料結構複習題
1 如果以鍊錶作為棧的儲存結構,則退棧操作時 a.必須判別棧是否滿 b.對棧不作任何判別 c.必須判別棧是否空 d.判別棧元素的型別 2 設陣列data 0.m 作為迴圈佇列sq的儲存空間,front為隊頭指標,rear為隊尾指標,則執行出隊操作的語句為 a.front front 1 b.fron...