本站
非官方網(wǎng)站，信息完全免費(fèi)，僅供參考，不收取任何費(fèi)用，具體請以官網(wǎng)公布為準(zhǔn)！
數(shù)據(jù)結(jié)構(gòu)線性表練習(xí)題及答案
一 選擇題
1. 下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)？（A）。
A．存儲密度大 B．插入運(yùn)算方便 C．刪除運(yùn)算方便 D．可方便地用于各種邏輯結(jié)構(gòu)的存儲表示
2.下面關(guān)于線性表的敘述中，錯誤的是哪一個？（B）
A．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。
B．線性表采用順序存儲，便于進(jìn)行插入和刪除操作。
C．線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。
D．線性表采用鏈接存儲，便于插入和刪除操作。
3．線性表是具有n個（ C）的有限序列（n>0）。
A．表元素 B．字符 C．?dāng)?shù)據(jù)元素 D．?dāng)?shù)據(jù)項(xiàng) E．信息項(xiàng)
4．若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（A）存儲方式最節(jié)省時間。
A．順序表 B．雙鏈表 C．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D．單循環(huán)鏈表
5．某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（D）存儲方式最節(jié)省運(yùn)算時間。
A．單鏈表 B．僅有頭指針的單循環(huán)鏈表 C．雙鏈表 D．僅有尾指針的單循環(huán)鏈表
6．設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用(D)最節(jié)省時間。
A. 單鏈表 B.單循環(huán)鏈表 C. 帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表
7．若某表最常用的操作是在最后一個結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)或刪除最后一個結(jié)點(diǎn)。則采用（D）存儲方式最節(jié)省運(yùn)算時間。
A．單鏈表 B．雙鏈表 C．單循環(huán)鏈表 D．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表
8. 靜態(tài)鏈表中指針表示的是（C）。
A． 內(nèi)存地址 B．?dāng)?shù)組下標(biāo) C．下一元素地址 D．左、右孩子地址
9. 鏈表不具有的特點(diǎn)是（B）。
A．插入、刪除不需要移動元素 B．可隨機(jī)訪問任一元素 C．不必事先估計(jì)存儲空間 D．所需空間與線性長度成正比
10. 下面的敘述不正確的是（B,C）。
A．線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值成正比
B. 線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值無關(guān)
C. 線性表在順序存儲時，查找第i個元素的時間同i 的值成正比
D. 線性表在順序存儲時，查找第i個元素的時間同i的值無關(guān)
11. 對于順序存儲的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時間復(fù)雜度為（C）。
A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
二、判斷題
1. 鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識的作用。(×)
2. 順序存儲結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作。(√)
3．線性表采用鏈表存儲時，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)的。(√)
4．順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶谩?×)
5. 對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。(×)
6．順序存儲方式只能用于存儲線性結(jié)構(gòu)。(×)
7．集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。(×)
8. 所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。(×)
9. 線性表的特點(diǎn)是每個元素都有一個前驅(qū)和一個后繼。(×)
10. 取線性表的第i個元素的時間同i的大小有關(guān). (×)
11. 循環(huán)鏈表不是線性表. (×)
12. 線性表只能用順序存儲結(jié)構(gòu)實(shí)現(xiàn)。(×)
13. 線性表就是順序存儲的表。(×)
14．為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。(√)
15. 順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。(×)
16. 鏈表是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表,進(jìn)行插入、刪除操作時，在鏈表中比在順序存儲結(jié)構(gòu)中效率高。 (√)
三、填空
1．當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用__順序__存儲結(jié)構(gòu)。
2．線性表L=（a1,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是__（n-1）/2__。
3．設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn) , 若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下語句:py->next=px->next； px->next=py;
4．在一個長度為n的順序表中第i個元素（1<=i<=n）之前插入一個元素時，需向后移動 n-i+1個元素。
5．在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是主要是使插入和刪除等操作統(tǒng)一，在第一個元素之前插入元素和刪除第一個結(jié)點(diǎn)不必另作判斷。另外，不論鏈表是否為空，鏈表指針不變。。
6．對于一個具有n個結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為O(1),在給定值為x的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為O(n)。
7．根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點(diǎn)包含的指針個數(shù)，將線性鏈表分成單鏈表和多重鏈表；而又根據(jù)指針的連接方式，鏈表又可分成（動態(tài)）鏈表和靜態(tài)鏈表。
8． 在雙向循環(huán)鏈表中,向p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作是f->next=p->next、f->prior=p、p->next->prior=f、p->next=f。
四、應(yīng)用題
1．線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：
（1）如果有 n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數(shù)也會自動地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)？ 為什么？
答：選鏈?zhǔn)酱鎯Y(jié)構(gòu)。它可動態(tài)申請內(nèi)存空間，不受表長度（即表中元素個數(shù)）的影響，插入、刪除時間復(fù)雜度為O（1）。
（2）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲結(jié)構(gòu)？為什么？
答：選順序存儲結(jié)構(gòu)。順序表可以隨機(jī)存取，時間復(fù)雜度為O（1）。
2．線性表的順序存儲結(jié)構(gòu)具有三個弱點(diǎn)：其一，在作插入或刪除操作時，需移動大量元素；其二，由于難以估計(jì)，必須預(yù)先分配較大的空間，往往使存儲空間不能得到充分利用；其三，表的容量難以擴(kuò)充。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是否一定都能夠克服上述三個弱點(diǎn)，試討論之。
答：鏈?zhǔn)酱鎯Y(jié)構(gòu)一般說克服了順序存儲結(jié)構(gòu)的三個弱點(diǎn)。首先，插入、刪除不需移動元素，只修改指針，時間復(fù)雜度為O(1)；其次，不需要預(yù)先分配空間，可根據(jù)需要動態(tài)申請空間；其三，表容量只受可用內(nèi)存空間的限制。其缺點(diǎn)是因?yàn)橹羔樤黾恿丝臻g開銷，當(dāng)空間不允許時，就不能克服順序存儲的缺點(diǎn)。
3．若較頻繁地對一個線性表進(jìn)行插入和刪除操作，該線性表宜采用何種存儲結(jié)構(gòu)？為什么？
答：采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，它根據(jù)實(shí)際需要申請內(nèi)存空間，而當(dāng)不需要時又可將不用結(jié)點(diǎn)空間返還給系統(tǒng)。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中插入和刪除操作不需要移動元素。
4．線性表（a1，a2，…，an）用順序映射表示時，ai和ai+1（1<=i＜n〉的物理位置相鄰嗎？鏈接表示時呢？
答：順序映射時，ai與ai+1的物理位置相鄰；鏈表表示時ai與ai+1的物理位置不要求相鄰。
5. 說明在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針與頭結(jié)點(diǎn)之間的根本區(qū)別；頭結(jié)點(diǎn)與首元結(jié)點(diǎn)的關(guān)系。
答：在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點(diǎn)則是鏈表的頭結(jié)點(diǎn)的指針，頭指針具有標(biāo)識作用，故常用頭指針冠以鏈表的名字。頭結(jié)點(diǎn)是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無意義（當(dāng)然有些情況下也可存放鏈表的長度、用做監(jiān)視哨等等），有頭結(jié)點(diǎn)后，對在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一結(jié)點(diǎn)，其操作與對其它結(jié)點(diǎn)的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。首元結(jié)點(diǎn)也就是第一元素結(jié)點(diǎn)，它是頭結(jié)點(diǎn)后邊的第一個結(jié)點(diǎn)。
五、算法設(shè)計(jì)題
1． 假設(shè)有兩個按元素值遞增次序排列的線性表，均以單鏈表形式存儲。請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來兩個單鏈表的結(jié)點(diǎn)存放歸并后的單鏈表。
答： [題目分析]因?yàn)閮涉湵硪寻丛刂颠f增次序排列，將其合并時，均從第一個結(jié)點(diǎn)起進(jìn)行比較，將小的鏈入鏈表中，同時后移鏈表工作指針。該問題要求結(jié)果鏈表按元素值遞減次序排列。故在合并的同時，將鏈表結(jié)點(diǎn)逆置。
LinkedList Union(LinkedList la,lb)
∥la,lb分別是帶頭結(jié)點(diǎn)的兩個單鏈表的頭指針，鏈表中的元素值按遞增序排列，本算法將兩鏈表合并成一個按元素值遞減次序排列的單鏈表。
{ pa=la->next; pb=lb->next;∥pa，pb分別是鏈表la和lb的工作指針
la->next=null; ∥la作結(jié)果鏈表的頭指針，先將結(jié)果鏈表初始化為空。
while(pa!=null && pb!=null) ∥當(dāng)兩鏈表均不為空時作
if(pa->data<=pb->data)
{ r=pa->next; ∥將pa 的后繼結(jié)點(diǎn)暫存于r。
pa->next=la->next; ∥將pa結(jié)點(diǎn)鏈于結(jié)果表中，同時逆置。
la->next=pa;
pa=r; ∥恢復(fù)pa為當(dāng)前待比較結(jié)點(diǎn)。
}
else
{r=pb->next; ∥ 將pb 的后繼結(jié)點(diǎn)暫存于r。
pb->next=la->next; ∥將pb結(jié)點(diǎn)鏈于結(jié)果表中，同時逆置。
la->next=pb;
pb=r; ∥恢復(fù)pb為當(dāng)前待比較結(jié)點(diǎn)。
}
while(pa!=null) ∥將la表的剩余部分鏈入結(jié)果表，并逆置。
{r=pa->next; pa->next=la->next; la->next=pa; pa=r; }
while(pb!=null)
{r=pb->next; pb->next=la->next; la->next=pb; pb=r; }
}∥算法Union結(jié)束。
［算法討論］上面兩鏈表均不為空的表達(dá)式也可簡寫為while(pa&&pb),兩遞增有序表合并成遞減有序表時，上述算法是邊合并邊逆置。也可先合并完，再作鏈表逆置。后者不如前者優(yōu)化。算法中最后兩個while語句，不可能執(zhí)行兩個，只能二者取一，即哪個表尚未到尾，就將其逆置到結(jié)果表中，即將剩余結(jié)點(diǎn)依次前插入到結(jié)果表的頭結(jié)點(diǎn)后面。
2. 試編寫在帶頭結(jié)點(diǎn)的單鏈表中刪除（一個）最小值結(jié)點(diǎn)的（高效）算法。void delete（Linklist &L）
答： [題目分析] 本題要求在單鏈表中刪除最小值結(jié)點(diǎn)。單鏈表中刪除結(jié)點(diǎn)，為使結(jié)點(diǎn)刪除后不出現(xiàn)“斷鏈”，應(yīng)知道被刪結(jié)點(diǎn)的前驅(qū)。而“最小值結(jié)點(diǎn)”是在遍歷整個鏈表后才能知道。所以算法應(yīng)首先遍歷鏈表，求得最小值結(jié)點(diǎn)及其前驅(qū)。遍歷結(jié)束后再執(zhí)行刪除操作。
LinkedList Delete（LinkedList L）
∥L是帶頭結(jié)點(diǎn)的單鏈表，本算法刪除其最小值結(jié)點(diǎn)。
{p=L->next； ∥p為工作指針。指向待處理的結(jié)點(diǎn)。假定鏈表非空。
pre=L； ∥pre指向最小值結(jié)點(diǎn)的前驅(qū)。
q=p； ∥q指向最小值結(jié)點(diǎn)，初始假定第一元素結(jié)點(diǎn)是最小值結(jié)點(diǎn)。
while（p->next!=null）
{if（p->next->datadata）{pre=p；q=p->next；} ∥查最小值結(jié)點(diǎn)
p=p->next； ∥指針后移。
}
pre->next=q->next；∥從鏈表上刪除最小值結(jié)點(diǎn)
free（q）； ∥釋放最小值結(jié)點(diǎn)空間
}∥結(jié)束算法delete。
[算法討論] 算法中函數(shù)頭是按本教材類C描述語言書寫的。原題中void delete（linklist &L），是按C++的“引用”來寫的，目的是實(shí)現(xiàn)變量的“傳址”，克服了C語言函數(shù)傳遞只是“值傳遞”的缺點(diǎn)。
3. 已知非空線性鏈表由list指出，鏈結(jié)點(diǎn)的構(gòu)造為（data,link）.請寫一算法，將鏈表中數(shù)據(jù)域值最小的那個鏈結(jié)點(diǎn)移到鏈表的最前面。要求：不得額外申請新的鏈結(jié)點(diǎn)。
答： [題目分析] 本題要求將鏈表中數(shù)據(jù)域值最小的結(jié)點(diǎn)移到鏈表的最前面。首先要查找最小值結(jié)點(diǎn)。將其移到鏈表最前面，實(shí)質(zhì)上是將該結(jié)點(diǎn)從鏈表上摘下（不是刪除并回收空間），再插入到鏈表的最前面。
LinkedList delinsert（LinkedList list）
∥list是非空線性鏈表，鏈結(jié)點(diǎn)結(jié)構(gòu)是（data，link），data是數(shù)據(jù)域，link是鏈域。
∥本算法將鏈表中數(shù)據(jù)域值最小的那個結(jié)點(diǎn)移到鏈表的最前面。
{p=list->link；∥p是鏈表的工作指針
pre=list； ∥pre指向鏈表中數(shù)據(jù)域最小值結(jié)點(diǎn)的前驅(qū)。
q=p； ∥q指向數(shù)據(jù)域最小值結(jié)點(diǎn)，初始假定是第一結(jié)點(diǎn)
while （p->link!=null）
{if（p->link->datadata）{pre=p；q=p->link；} ∥找到新的最小值結(jié)點(diǎn)；
p=p->link；
}
if (q!=list->link) ∥若最小值是第一元素結(jié)點(diǎn)，則不需再操作
{pre->link=q->link； ∥將最小值結(jié)點(diǎn)從鏈表上摘下；
q->link= list->link； ∥將q結(jié)點(diǎn)插到鏈表最前面。
list->link=q；
}
}∥算法結(jié)束
[算法討論] 算法中假定list帶有頭結(jié)點(diǎn)，否則，插入操作變?yōu)閝->link=list；list=q。
4. 已知p指向雙向循環(huán)鏈表中的一個結(jié)點(diǎn)，其結(jié)點(diǎn)結(jié)構(gòu)為data、llink、rlink三個域，寫出算法change(p),交換p所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)的順序。
答： [題目分析] 知道雙向循環(huán)鏈表中的一個結(jié)點(diǎn)，與前驅(qū)交換涉及到四個結(jié)點(diǎn)（p結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)，前驅(qū)的前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn)）六條鏈。
void Exchange（LinkedList p）
∥p是雙向循環(huán)鏈表中的一個結(jié)點(diǎn)，本算法將p所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。
{q=p->llink；
q->llink->rlink=p； ∥p的前驅(qū)的前驅(qū)之后繼為p
p->llink=q->llink； ∥p的前驅(qū)指向其前驅(qū)的前驅(qū)。
q->rlink=p->rlink； ∥p的前驅(qū)的后繼為p的后繼。
q->llink=p； ∥p與其前驅(qū)交換
p->rlink->llink=q； ∥p的后繼的前驅(qū)指向原p的前驅(qū)
p->rlink=q； ∥p的后繼指向其原來的前驅(qū)
}∥算法exchange結(jié)束。
5. 線性表(a1,a2,a3,…,an)中元素遞增有序且按順序存儲于計(jì)算機(jī)內(nèi)。要求設(shè)計(jì)一算法完成：
（1） 用最少時間在表中查找數(shù)值為x的元素。
（2） 若找到將其與后繼元素位置相交換。
（3） 若找不到將其插入表中并使表中元素仍遞增有序。
答： [題目分析] 順序存儲的線性表遞增有序，可以順序查找，也可折半查找。題目要求“用最少的時間在表中查找數(shù)值為x的元素”，這里應(yīng)使用折半查找方法。
void SearchExchangeInsert（ElemType a[]；ElemType x）
∥a是具有n個元素的遞增有序線性表，順序存儲。本算法在表中查找數(shù)值為x的元素，如查到則與其后繼交換位置；如查不到，則插入表中，且使表仍遞增有序。
{ low=0；high=n-1； ∥low和high指向線性表下界和上界的下標(biāo)
while（low<=high）
{mid=（low+high）/2； ∥找中間位置
if（a[mid]==x） break； ∥找到x，退出while循環(huán)。
else if （a[mid] ＜x） low=mid+1；∥到中點(diǎn)mid的右半去查。
else high=mid-1； ∥到中點(diǎn)mid的左部去查。
}
if（a[mid]==x && mid!=n）∥ 若最后一個元素與x相等，則不存在與其后繼交換的操作。
{t=a[mid]；a[mid]=a[mid+1]；a[mid+1]=t；} ∥ 數(shù)值x與其后繼元素位置交換。
if（low>high） ∥查找失敗，插入數(shù)據(jù)元素x
{for（i=n-1；i>high；i--） a[i+1]=a[i]；∥后移元素。
a[i+1]=x；∥插入x。
} ∥結(jié)束插入
}∥結(jié)束本算法。
[算法討論] 首先是線性表的描述。算法中使用一維數(shù)組a表示線性表，未使用包含數(shù)據(jù)元素的一維數(shù)組和指示線性表長度的結(jié)構(gòu)體。若使用結(jié)構(gòu)體，對元素的引用應(yīng)使用a.elem[i]。另外元素類型就假定是ElemType，未指明具體類型。其次，C中一維數(shù)組下標(biāo)從0開始，若說有n個元素的一維數(shù)組，其最后一個元素的下標(biāo)應(yīng)是n-1。第三，本算法可以寫成三個函數(shù)，查找函數(shù)，交換后繼函數(shù)與插入函數(shù)。寫成三個函數(shù)顯得邏輯清晰，易讀。
海南高考志愿填報(bào) http://xjuit.com/yanzhao/
