1. 演算法的時間複雜度取決於（ c ）
a）問題的規模 b） 待處理資料的初態 c） a和b
2.計算機演算法指的是解決問題的步驟序列，它必須具備（ b ） 這三個特性。
a）可執行性、可移植性、可擴充性b） 可執行性、確定性、有窮性c） 確定性、有窮性、穩定性d） 易讀性、穩定性、安全性
5．從邏輯上可以把資料結構分為（ c ）兩大類。
a）動態結構、靜態結構b）順序結構、鏈式結構c）線性結構、非線性結構 d）初等結構、構造型結構
6．在下面的程式段中，對x的賦值的語句頻度為（ c ）
a） o(2n) b）o(n) c．o(n2) d．o(log2n)
7．下面的程式段中， n為正整數，則最後一行的語句頻度在最壞情況下是（ d ）
a. o（n） b） o(nlog2n) c） o(n3) d） o(n2)
2. 對於給定的n個元素,可以構造出的邏輯結構有集合、線性結構、樹形結構、圖狀結構或網狀結構四種。
4．資料結構中評價演算法的兩個重要指標是：演算法的時間複雜度和空間複雜度。
5. 資料結構是研討資料的__邏輯結構_和_物理結構_以及它們之間的相互關係，並對與這種結構定義相應的_操作（運算）_設計出相應的_演算法_。
6．乙個演算法具有5個特性：有窮性_、確定性、可行性，有零個或多個輸入、有乙個或多個輸出。
9．已知如下程式段
語句1執行的頻度為_n+1_;語句2執行的頻度為_n__；語句3執行的頻度為_n(n+3)/2_；語句4執行的頻度為_n(n+1)/2_。
10．在下面的程式段中，對ｘ的賦值語句的頻度為表示為n的函式）
for(i=0;i>n;i++)
for(j=0;j>i;j++)
for(k=0;k>j;k++)
delta;【答案】1+（1+2）+（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6 ， o(n3)
11.下面程式段中帶下劃線的語句的執行次數的數量級是
i=1; while(i12. 計算機執行下面的語句時，語句s的執行次數為
13. 下面程式段的時間複雜度為n>1)
1．對於線性表最常用的操作是查詢指定序號的元素和在末尾插入元素，則選擇（ a ）最節省時間
a）順序表 b）帶頭結點的雙迴圈鍊錶c）單鏈表d）帶尾結點的單迴圈鍊錶
2 ．若長度為n的線性表採用順序儲存結構，在其第i個位置插入乙個新元素的演算法時間複雜度為（ c ）(1≤i≤n+1)。
a） o(0b） o(1c） o(nd） o(n2)
3．雙向鍊錶中有兩個指標域，prior和next，分別指向前驅及後繼，設p指向鍊錶中的乙個結點，q指向一待插入結點，現要求在p前插入q，則正確的插入為（d ）
a） p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;
b） q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next;
c） q->next=p; p->next=q; p->prior->next=q; q->next=p;
d） p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q;
4．在乙個具有n個結點的有序單鏈表中插入乙個新結點並仍然保持有序的時間複雜度是（c ）
a）o(nlog2n） b） o(1） c） o(n） d） o(n2）
5． 在乙個以 h 為頭指標的單迴圈鏈中，p 指標指向鏈尾結點的條件是（ b ）
a）p->next==null b） p->next==hc）p->next->next==hd） p->data==-1
6．對於乙個具有n個結點的線性表，建立其單鏈表的時間複雜度是（ a ）
a）o(n) b） o(1c）o(nlog2nd） o(n2)
8．在雙向鍊錶儲存結構中，刪除p所指的結點時須修改指標（ a ）
a）p->prior->next=p->next p->next->prior=p->prior;b）p->prior=p->prior->prior p->prior->next=p;
c）p->next->prior=p p->next=p->next->nextd）p->next=p->prior->prior p->prior=p->next->next;
9．線性表採用鏈式儲存時，其元素位址（d ）
a）必須是連續的 b）一定是不連續的 c）部分位址是連續的d）連續與否均可
1．線性表l=（a1，a2，…，an）用陣列表示，假定刪除表中任一元素的概率相同，則刪除乙個元素平均需要移動元素的個數是答案】（n-1）/2
2．在單鏈表中設定頭結點的作用是答案】主要是使插入和刪除等操作統一，在第乙個元素之前插入元素和刪除第乙個結點不必另作判斷。另外，不論鍊錶是否為空，煉表頭指標不變。
3．線性表的順序儲存是通過來反應元素之間的邏輯關係，而鏈式儲存結構是通過來反應元素之間的邏輯關係。【答案】（1）資料元素的前後順序 （2）元素中的指標
4．當對乙個線性表經常進行的是訪問操作，而很少進行插入和刪除操作時，則採用儲存結構最節省時間，相反當經常進行插入和刪除操作時，則採用儲存結構最節省時間。【答案】（1）順序 （2）鏈式
5．對於乙個具有n個結點的單鏈表，在已知的結點*p後插入乙個新結點的時間複雜度為在給定值為x的結點後插入乙個新結點的時間複雜度為答案】（1）o(1) （2）o(n)
7. 對於雙向鍊錶，在兩個結點之間插入乙個新結點需修改的指標共_____4________個，單鏈表為_____2________個。
8. 迴圈單鏈表的最大優點是答案】從任一結點出發都可訪問到鍊錶中每乙個元素。
9．若要在乙個不帶頭結點的單鏈表的首結點*p結點之前插入乙個*s結點時，可執行下列操作：
s->next
p->next=s;
t=p->data;
p->data
s->data答案】（1）p->next （2）s->data （3） t
10．某線性表採用順序儲存結構，每個元素佔據4個儲存單元，首位址為100，則下標為11的（第12個）元素的儲存位址為144
11．帶頭結點的雙迴圈鍊錶l中只有乙個元素結點的條件是答案】l->next->next==l
1．取線性表的第i個元素的時間同i的大小有關（ ）【答案】×
2．線性表的特點是每個元素都有乙個前驅和乙個後繼（ ）【答案】×
3． 順序儲存方式的優點是儲存密度大，且插入、刪除運算效率高（ ）【答案】×
4．線性表採用鍊錶儲存時，結點的儲存空間可以是不連續的（ ）【答案】√
5．鍊錶是採用鏈式儲存結構的線性表，進行插入、刪除操作時，在鍊錶中比在順序儲存結構中效率高（ ）【答案】√
6．順序儲存方式只能用於儲存線性結構（ ）【答案】×解析】線性結構、樹型結構和圖狀結構均可用順序儲存表示。
9．順序儲存結構的主要缺點是不利於插入或刪除操作（ ）【答案】√
10．順序儲存方式插入和刪除時效率太低，因此它不如鏈式儲存方式好（ ）【答案】×
1．設順序表va中的資料元素遞增有序。試設計乙個演算法，將x插入到順序表的適當位置上，以保持該錶的有序性。
2．設 a=（a1，a2，…，am） 和 b=（b1，b2，…，bn）均為順序表，試設計乙個比較a，b大小的演算法（請注意：在演算法中，不要破壞原表a和b）。
資料結構課堂習題解
課堂習題參考解答 圖部分1.以鄰接表為儲存結構，寫出圖的深度優先遍歷的非遞迴演算法。答 補充圖的鄰接表儲存結構 void dfs algraph g,vertexttype v if top 0 單鏈表部分 1.請寫乙個演算法將線性表 a1,a2,an 逆置為 an,an 1,a1 typedef ...
複習資料結構習題解答
1 空格串是由空格組成的串，空串是不含任何字元的串，因此空格串和空串不是乙個概念。2 從整體上看，資料在儲存器內有兩種存放的方式 一是集中存放在乙個連續的記憶體儲存區中 一是利用儲存器中的零星區域，分散地存放在記憶體的各個地方。3 如果一棵滿二叉樹的深度為6，那麼它共有 63 個結點，有 32 個葉...
資料結構習題
第5章陣列和廣義表 一 選擇題 1.在以下講述中，正確的是 b a 線性表的線性儲存結構優於鍊錶儲存結構 b 二維陣列是其資料元素為線性表的線性表 c 棧的操作方式是先進先出 d 佇列的操作方式是先進後出 2.若採用三元組壓縮技術儲存稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉...