線性表部分
一選擇題
1．下述哪一條是順序儲存結構的優點？（ ）
a．儲存密度大 b．插入運算方便 c．刪除運算方便 d．可方便地用於各種邏輯結構的儲存表示
2．下面關於線性表的敘述中，錯誤的是哪乙個？（ ）
a．線性表採用順序儲存，必須占用一片連續的儲存單元。
b．線性表採用順序儲存，便於進行插入和刪除操作。
c．線性表採用鏈結儲存，不必占用一片連續的儲存單元。
d．線性表採用鏈結儲存，便於插入和刪除操作。
3．線性表是具有n個（ ）的有限序列（n>0）。
a．表元素 b．字元 c．資料元素 d．資料項 e．資訊項
4．若某線性表最常用的操作是訪問任一指定序號的元素和在最後進行插入和刪除運算，則利用（ ）儲存方式最節省時間。
a．順序表 b．雙鏈表 c．帶頭結點的雙迴圈鍊錶 d．單迴圈鍊錶
5．某線性表中最常用的操作是在最後乙個元素之後插入乙個元素和刪除第乙個元素，則採用（ ）儲存方式最節省運算時間。
a．單鏈表 b．僅有頭指標的單迴圈鍊錶 c．雙鏈表 d．僅有尾指標的單迴圈鍊錶
6. 若長度為n的線性表採用順序儲存結構，在其第i個位置插入乙個新元素的演算法的時間複雜度為（ ）(1<=i<=n+1)。
a. o(0) b. o(1c. o(nd. o(n2)
7．線性表（ a1,a2,…,an）以鏈結方式儲存時，訪問第i位置元素的時間複雜性為（ ）
a．o（i） b．o（1） c．o（n） d．o（i-1）
8．在單鏈表指標為p的結點之後插入指標為s的結點，正確的操作是：（ ）。
a．p->next=s;s->next=p->next; b． s->next=p->next;p->next=s;
c．p->next=s;p->next=s->next; d． p->next=s->next;p->next=s;
9．對於乙個頭指標為head的帶頭結點的單鏈表，判定該錶為空表的條件是（ ）
a．head==null b．head→next==null c．head→next==head d．head!=null
二、判斷
1. 鍊錶中的頭結點僅起到標識的作用。(×)
2. 順序儲存結構的主要缺點是不利於插入或刪除操作。(√)
3．順序儲存方式插入和刪除時效率太低，因此它不如鏈式儲存方式好。(×)
4．對任何資料結構鏈式儲存結構一定優於順序儲存結構。(×)
5. 順序儲存方式只能用於儲存線性結構。(×)
6．線性表的特點是每個元素都有乙個前驅和乙個後繼。(×)
7. 取線性表的第i個元素的時間同i的大小有關. (×)
8. 順序儲存方式的優點是儲存密度大，且插入、刪除運算效率高。(×)
9. 鍊錶是採用鏈式儲存結構的線性表,進行插入、刪除操作時，在鍊錶中比在順序儲存結構中效率高。 (√)
三、填空
1．當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度訪問線性表中的元素時，應採用_順序_儲存結構。
2．線性表l=（a1,a2,…,an）用陣列表示，假定刪除表中任一元素的概率相同，則刪除乙個元素平均需要移動元素的個數是_（n-1）/2 _。
3．在乙個長度為n的順序表中第i個元素（1<=i<=n）之前插入乙個元素時，需向後移動_ n-i+1_個元素。
4．在單鏈表中設定頭結點的作用是：主要是使插入和刪除等操作統一，在第乙個元素之前插入元素和刪除第乙個結點不必另作判斷；另外，不論鍊錶是否為空，鍊錶指標不變。
5．根據線性表的鏈式儲存結構中每乙個結點包含的指標個數，將線性鍊錶分成_單鏈表_和多重鍊錶；而又根據指標的連線方式，鍊錶又可分成（動態）鍊錶和靜態鍊錶。
6．鏈結儲存的特點是利用_指標_來表示資料元素之間的邏輯關係。
7.順序儲存結構是通過_物理上相鄰表示元素之間的關係的;鏈式儲存結構是通過_指標_表示元素之間的關係的。
8. 已知指標p指向單鏈表l中的某結點，則刪除其後繼結點的語句是：
u=p->next; p->next=u->next; free(u);
9. 在單鏈表l中，指標p所指結點有後繼結點的條件是：p->next!=null
10. 以下程式的功能是實現帶附加頭結點的單鏈表資料結點逆序連線，
請填空完善之。
void reverse(sqlist h)
/* h為附加頭結點指標；型別pointer */
棧和佇列部分
一選擇題
1. 對於棧運算元據的原則是（ ）。
a. 先進先出 b. 後進先出 c. 後進後出 d. 不分順序
2. 在作進棧運算時,應先判別棧是否( ① ),在作退棧運算時應先判別棧是否( ② )。當棧中元素為n個,作進棧運算時發生上溢,則說明該棧的最大容量為( ③ )。
為了增加記憶體空間的利用率和減少溢位的可能性,由兩個棧共享一片連續的記憶體空間時,應將兩棧的 ( ④ )分別設在這片記憶體空間的兩端,這樣,當( ⑤ )時，才產生上溢。
①, ②: a. 空 b. 滿c. 上溢 d. 下溢
③: a. n-1 b. nc. n+1 d. n/2
④: a. 長度 b. 深度 c. 棧頂 d. 棧底
⑤: a. 兩個棧的棧頂同時到達棧空間的中心點.
b. 其中乙個棧的棧頂到達棧空間的中心點.
c. 兩個棧的棧頂在棧空間的某一位置相遇.
d. 兩個棧均不空,且乙個棧的棧頂到達另乙個棧的棧底.
3. 乙個棧的輸入序列為123…n，若輸出序列的第乙個元素是n，輸出第i（1<=i<=n）個元素是（ ）。
a. 不確定b. n-i+1c. id. n-i
4. 某堆疊的輸入序列為a, b，c ，d,下面的四個序列中，不可能是它的輸出序列的是（ ）。
a. a，c，b，d b. b, c，d，a c. c, d，b, a d. d, c，a，b
5. 依次讀入資料元素序列進棧,每進乙個元素，機器可要求下乙個元素進棧或彈棧，如此進行，則棧空時彈出的元素構成的序列是以下哪些序列？
a． b.
c. d.
6. 迴圈佇列a[0..m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當前佇列中的元素數是( )。
a. (rear-front+m)%m b. rear-front+1 c. rear-front-1 d. rear-front
7. 迴圈佇列儲存在陣列a[0..m]中，則入隊時的操作為（ ）。
a. rear=rear+1b. rear=(rear+1) mod (m-1)
c. rear=(rear+1) mod m d. rear=(rear+1)mod(m+1)
8. 若用乙個大小為6的陣列來實現迴圈佇列，且當前rear和front的值分別為0和3，當從佇列中刪除乙個元素，再加入兩個元素後，rear和front的值分別為多少？( )
a. 1和 5 b. 2和4c. 4和2 d. 5和1
9. 最大容量為n的迴圈佇列，隊尾指標是rear，隊頭是front，則隊空的條件是 （ ）。
a. (rear+1) mod n=frontb. rear=front
c．rear+1=frontd. (rear-l) mod n=front
10. 棧和佇列的共同點是（ ）。
a. 都是先進先出b. 都是先進後出
c. 只允許在端點處插入和刪除元素 d. 沒有共同點
11. 設棧s和佇列q的初始狀態為空，元素e1，e2，e3，e4,e5和e6依次通過棧s，乙個元素出棧後即進佇列q，若6個元素出隊的序列是e2，e4，e3,e6,e5,e1則棧s的容量至少應該是( )。
a． 6b. 4c. 3d. 2
二判斷題
1. 消除遞迴不一定需要使用棧，此說法（√）
2. 棧是實現過程和函式等子程式所必需的結構。（√）
3. 兩個棧共用靜態儲存空間，對頭使用也存在空間溢位問題。（√）
4．兩個棧共享一片連續記憶體空間時，為提高記憶體利用率，減少溢位機會，應把兩個棧的棧底分別設在這片記憶體空間的兩端。（√）
5. 即使對不含相同元素的同一輸入序列進行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（×）
6. 棧與佇列是一種特殊操作的線性表。（√）
7. 若輸入序列為1,2,3,4,5,6,則通過乙個棧可以輸出序列3,2,5,6,4,1. （√）
《資料結構》習題答案
習題1一 選擇題 1 c 2 b 3 b 4 b d 5 c 6 a 7 c b 8 d 9 b 10 d 二 填空題 1 相互關係 2 一對 一 一對多 多對多 3 線性結構 集合 圖 樹 4 有窮性 確定性 可行性 輸入 輸出 5 o n 6 o n2 7 物理 8 1 log2n n n2 2...
資料結構課後習題答案
5 選擇題 ccbdca 6 試分析下面各程式段的時間複雜度。1 o 1 2 o m n 3 o n2 4 o log3n 5 因為x 共執行了n 1 n 2 1 n n 1 2，所以執行時間為o n2 6 o 1 選擇題 babadbcabdcddac 2 演算法設計題 6 設計乙個演算法，通過一...
資料結構課後習題答案
1.填空 是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。解答 資料元素 是資料的最小單位，是討論資料結構時涉及的最小資料單位。解答 資料項，資料元素 分析 資料結構指的是資料元素以及資料元素之間的關係。從邏輯關係上講，資料結構主要分為和 解答 集合，線性結構，樹結構，圖結構 資料的儲...