習(xí)題

1.填空題

（1）已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)需占m個(gè)存儲(chǔ)單元，若第0個(gè)元素的地址為address，則第i個(gè)結(jié)點(diǎn)的地址為_____。

（2）線性表有兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，就兩種存儲(chǔ)結(jié)構(gòu)完成下列填空：

_____存儲(chǔ)密度較大，_____存儲(chǔ)利用率較高，_____可以隨機(jī)存取，_____不可以隨機(jī)存取，_____插入和刪除操作比較方便。

（3）順序表中邏輯上相鄰的元素在物理位置上_____，在鏈表中邏輯上相鄰的元素的物理位置_____相鄰。

（4）一個(gè)長度為n的順序表中，在第i個(gè)元素（0≤i≤n）之前插入一個(gè)新元素，具有最壞時(shí)間復(fù)雜度，對應(yīng)的i值是_____，具有最好時(shí)間復(fù)雜度，對應(yīng)的i值是_____。

（5）在順序表la的第i個(gè)元素前插入一個(gè)新元素，則有效的i值范圍是_____；在順序表lb的第j個(gè)元素之后插入一個(gè)新元素，則j的有效范圍是_____；要?jiǎng)h除順序表lc的第k個(gè)元素，則k的有效范圍是_____。

（6）在n個(gè)結(jié)點(diǎn)的順序表中插入一個(gè)結(jié)點(diǎn)，平均需要移動(dòng)_____個(gè)結(jié)點(diǎn)，具體的移動(dòng)次數(shù)取決于_____和_____。

（7）在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需要找到_____，其時(shí)間復(fù)雜度為_____；在雙鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，其時(shí)間復(fù)雜度為_____；

（8）在單鏈表中要在已知結(jié)點(diǎn)*p之前插入一個(gè)新結(jié)點(diǎn)，需找到_____，其時(shí)間復(fù)雜度為_____；而在雙鏈表中，完成同樣操作時(shí)其時(shí)間復(fù)雜度為_____。

（9）在單鏈表上，刪除指針p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語句是_____。

（10）帶頭結(jié)點(diǎn)的單鏈表（頭結(jié)點(diǎn)由head指向），對其判空的條件是_____；不帶頭結(jié)點(diǎn)的單鏈表（第一個(gè)結(jié)點(diǎn)由head指向），對其判空的條件是_____；帶頭結(jié)點(diǎn)的單向循環(huán)鏈表（頭結(jié)點(diǎn)由head指向），對其判空的條件是_____；不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表（第一個(gè)結(jié)點(diǎn)由head指向），對其判空的條件是_____。

（11）刪除帶頭結(jié)點(diǎn)的單鏈表（頭結(jié)點(diǎn)由head指向）的第一個(gè)結(jié)點(diǎn)的語句是_____，刪除不帶頭結(jié)點(diǎn)的單鏈表（第一個(gè)結(jié)點(diǎn)由head指向）的第一個(gè)結(jié)點(diǎn)的語句是_____。

（12）在一雙向循環(huán)鏈表上，要交換指針p所指結(jié)點(diǎn)的前驅(qū)與后繼結(jié)點(diǎn)的值，則相應(yīng)的操作語句是_____。

（13）在雙向循環(huán)鏈表中（頭結(jié)點(diǎn)由head指向），指針p所指的結(jié)點(diǎn)是該鏈表的尾結(jié)點(diǎn)的條件是_____。

2.判斷題

（1）鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。

（2）鏈表中指向第一個(gè)結(jié)點(diǎn)的指針稱為頭指針。

（3）鏈表的刪除算法很簡單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)將后續(xù)各個(gè)單元向前移動(dòng)。

（4）線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。

（5）順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。

（6）順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。

（7）對單鏈表的插入運(yùn)算，帶頭結(jié)點(diǎn)的單鏈表與不帶頭結(jié)點(diǎn)的單鏈表相比，前者對應(yīng)的算法更簡單。

（8）線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。

（9）順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。

（10）線性表的邏輯順序與存儲(chǔ)順序總是一致的。

3.簡答題

（1）比較雙向循環(huán)鏈表與單向循環(huán)鏈表，試簡述各自的優(yōu)缺點(diǎn)。

（2）描述下列算法的功能。

ListNode* Demo1(LinkList head,ListNode *p)
{  /* head是指向單鏈表的頭指針 */
   q=head->next;
   while(q&&q->next!=p)
      q=q->next;
   return(q);
}

（3）描述下列算法的功能。

void Demo2(ListNode *p,ListNode *q)
{  temp=p->data;
   p->data=q->data;
   q->data=temp;
}

4.算法設(shè)計(jì)題

（1）試用順序表作為存儲(chǔ)結(jié)構(gòu)，編寫算法實(shí)現(xiàn)線性表就地逆置的操作，即在原表的存儲(chǔ)空間中將線性表（a1,a2,…,an）逆置為（an,an-1,…,a1）。

（2）寫一算法，從順序表中刪除自第i個(gè)元素開始的k個(gè)元素。

（3）若已建立一個(gè)帶有頭結(jié)點(diǎn)的單向鏈表，h為指向頭結(jié)點(diǎn)的指針，且鏈表中存放的數(shù)據(jù)按由小到大的順序排列。編寫函數(shù)實(shí)現(xiàn)算法，把x值插入到鏈表中，插入后鏈表中結(jié)點(diǎn)數(shù)據(jù)仍保持有序。

（4）假設(shè)在長度大于1的單循環(huán)鏈表中，既無頭結(jié)點(diǎn)也無頭指針，p為指向該鏈表中某個(gè)結(jié)點(diǎn)的指針，編寫算法實(shí)現(xiàn)刪除該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。

（5）設(shè)h為一指向單向鏈表頭結(jié)點(diǎn)的指針，該鏈表中結(jié)點(diǎn)的值按非降序排列，設(shè)計(jì)算法刪除鏈表中值相同的結(jié)點(diǎn)，使之只保留一個(gè)。

（6）對給定的帶頭結(jié)點(diǎn)的單鏈表，h為指向頭結(jié)點(diǎn)的指針，編寫一個(gè)刪除表中值為x的結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的算法。

（7）如果以單鏈表表示集合，假設(shè)集合A用單鏈表la表示，集合B用單鏈表lb表示，設(shè)計(jì)算法求兩個(gè)集合的差，即A-B。

（8）假設(shè)線性表a、b表示兩個(gè)集合，即同一個(gè)線性表中的元素各不相同，且均以元素值遞增有序排列，現(xiàn)要求構(gòu)成一個(gè)新的線性表c，c表示集合a與b的交，且c中元素也遞增有序。試分別以順序表和單鏈表為存儲(chǔ)結(jié)構(gòu)，編寫實(shí)現(xiàn)上述運(yùn)算的算法。

（9）已知線性表的元素是無序的，且以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)，試編寫算法實(shí)現(xiàn)刪除表中所有值大于min且小于max的元素。

（10）已知在單鏈表表示的線性表中，含有兩類字符的數(shù)據(jù)元素，如字母字符和數(shù)字字符，試編寫算法構(gòu)造兩個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這兩個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。

（11）有兩個(gè)雙向循環(huán)鏈表，頭指針分別為head1和head2，編寫一個(gè)函數(shù)將鏈表 head1鏈接到鏈表 head2 ，鏈接后的鏈表仍是循環(huán)鏈表。

（12）已知一帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，指向頭結(jié)點(diǎn)的指針為head，p指針指向其中某一結(jié)點(diǎn)，寫一算法刪除p指向結(jié)點(diǎn)的前驅(qū)。