單鏈表練習(xí)題選擇題

單鏈表練習(xí)題選擇題一、基本概念1.單鏈表是一種（）的數(shù)據(jù)結(jié)構(gòu)。A.線性B.非線性C.樹形D.圖形2.在單鏈表中，每個(gè)節(jié)點(diǎn)至少包含兩個(gè)部分：（）和指向下一個(gè)節(jié)點(diǎn)的指針。A.數(shù)據(jù)域B.指針域C.鍵值D.索引3.單鏈表的第一個(gè)節(jié)點(diǎn)稱為（）。A.頭節(jié)點(diǎn)B.尾節(jié)點(diǎn)C.中間節(jié)點(diǎn)D.孤立節(jié)點(diǎn)4.單鏈表的一個(gè)節(jié)點(diǎn)的指針域指向（）。A.頭節(jié)點(diǎn)B.尾節(jié)點(diǎn)C.中間節(jié)點(diǎn)D.NULL二、基本操作5.在單鏈表中插入一個(gè)新節(jié)點(diǎn)，需要修改（）。A.新節(jié)點(diǎn)的指針域B.原節(jié)點(diǎn)的指針域C.頭節(jié)點(diǎn)的指針域D.所有節(jié)點(diǎn)的指針域6.刪除單鏈表中的一個(gè)節(jié)點(diǎn)，需要修改（）。A.被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的指針域B.被刪除節(jié)點(diǎn)的指針域C.頭節(jié)點(diǎn)的指針域D.所有節(jié)點(diǎn)的指針域7.在單鏈表中查找第i個(gè)節(jié)點(diǎn)，其時(shí)間復(fù)雜度為（）。A.O(1)B.O(n)C.O(logn)D.O(n^2)8.單鏈表的長(zhǎng)度為n，插入一個(gè)新節(jié)點(diǎn)的時(shí)間復(fù)雜度為（）。A.O(1)B.O(n)C.O(logn)D.O(n^2)三、特殊操作9.反轉(zhuǎn)單鏈表的過(guò)程中，需要改變每個(gè)節(jié)點(diǎn)的（）。A.數(shù)據(jù)域B.指針域C.鍵值D.索引10.在單鏈表中查找中間節(jié)點(diǎn)，可以使用（）方法。A.順序查找B.二分查找C.快慢指針D.哈希查找11.判斷單鏈表是否有環(huán)，可以使用（）方法。A.順序查找B.快慢指針C.哈希表D.棧12.合并兩個(gè)有序單鏈表，需要保持原有順序，可以使用（）方法。A.順序合并B.歸并排序C.快速排序D.堆排序四、算法題13.編寫一個(gè)函數(shù)，實(shí)現(xiàn)單鏈表的創(chuàng)建。14.編寫一個(gè)函數(shù)，實(shí)現(xiàn)單鏈表的遍歷。15.編寫一個(gè)函數(shù)，實(shí)現(xiàn)單鏈表的插入操作。16.編寫一個(gè)函數(shù)，實(shí)現(xiàn)單鏈表的刪除操作。17.編寫一個(gè)函數(shù)，實(shí)現(xiàn)單鏈表的反轉(zhuǎn)。18.編寫一個(gè)函數(shù)，實(shí)現(xiàn)單鏈表的查找中間節(jié)點(diǎn)。19.編寫一個(gè)函數(shù)，判斷單鏈表是否有環(huán)。20.編寫一個(gè)函數(shù)，合并兩個(gè)有序單鏈表。五、鏈表排序A.冒泡排序B.插入排序C.快速排序D.歸并排序22.在單鏈表上進(jìn)行歸并排序時(shí)，需要找到鏈表的（）。A.中點(diǎn)B.最大值C.最小值D.尾節(jié)點(diǎn)23.對(duì)單鏈表進(jìn)行插入排序的過(guò)程中，需要維護(hù)一個(gè)已排序部分的（）。A.頭節(jié)點(diǎn)B.尾節(jié)點(diǎn)C.中間節(jié)點(diǎn)D.哨兵節(jié)點(diǎn)六、鏈表與遞歸A.鏈表的創(chuàng)建B.鏈表的遍歷C.鏈表的反轉(zhuǎn)D.鏈表的插入25.使用遞歸方法反轉(zhuǎn)單鏈表時(shí)，遞歸的基準(zhǔn)情況是（）。A.遇到頭節(jié)點(diǎn)B.遇到尾節(jié)點(diǎn)C.鏈表為空D.鏈表只有一個(gè)節(jié)點(diǎn)A.修改頭節(jié)點(diǎn)的指針域B.保存當(dāng)前節(jié)點(diǎn)的指針C.刪除當(dāng)前節(jié)點(diǎn)D.反轉(zhuǎn)鏈表七、鏈表與棧A.查找棧頂元素B.刪除棧底元素C.插入棧頂元素D.刪除棧頂元素28.在使用單鏈表實(shí)現(xiàn)的棧中，棧頂元素位于（）。A.頭節(jié)點(diǎn)B.尾節(jié)點(diǎn)C.中間節(jié)點(diǎn)D.任意節(jié)點(diǎn)A.入棧B.出棧C.查找棧頂元素D.遍歷棧八、鏈表與隊(duì)列A.插入隊(duì)尾B.刪除隊(duì)頭C.查找隊(duì)頭元素D.查找隊(duì)尾元素31.在使用單鏈表實(shí)現(xiàn)的隊(duì)列中，隊(duì)頭元素位于（）。A.頭節(jié)點(diǎn)B.尾節(jié)點(diǎn)C.中間節(jié)點(diǎn)D.任意節(jié)點(diǎn)A.入隊(duì)B.出隊(duì)C.查找隊(duì)頭元素D.遍歷隊(duì)列九、綜合應(yīng)用33.如何在單鏈表中找到倒數(shù)第k個(gè)節(jié)點(diǎn)？A.順序遍歷兩次B.使用快慢指針C.使用棧D.反轉(zhuǎn)鏈表后查找34.如何在不使用遞歸的情況下反轉(zhuǎn)單鏈表？A.使用棧B.使用頭插法C.使用尾插法D.使用雙指針35.如何在單鏈表中刪除重復(fù)的節(jié)點(diǎn)？A.使用哈希表B.使用排序C.使用快慢指針D.使用遞歸36.如何判斷兩個(gè)單鏈表是否相交？A.比較節(jié)點(diǎn)值B.比較節(jié)點(diǎn)地址C.反轉(zhuǎn)鏈表后比較D.使用快慢指針37.如何計(jì)算兩個(gè)相交單鏈表的交點(diǎn)？A.使用哈希表B.使用排序C.使用快慢指針D.使用遞歸38.如何在不修改節(jié)點(diǎn)值的情況下交換兩個(gè)節(jié)點(diǎn)的位置？A.修改節(jié)點(diǎn)數(shù)據(jù)域B.修改節(jié)點(diǎn)指針域C.使用棧D.使用遞歸39.如何在不額外空間的情況下復(fù)制一個(gè)帶隨機(jī)指針的鏈表？A.順序遍歷兩次B.使用哈希表C.使用快慢指針D.使用遞歸40.如何實(shí)現(xiàn)一個(gè)循環(huán)鏈表？A.使頭節(jié)點(diǎn)的指針域指向自身B.使尾節(jié)點(diǎn)的指針域指向頭節(jié)點(diǎn)C.使每個(gè)節(jié)點(diǎn)的指針域指向頭節(jié)點(diǎn)D.使每個(gè)節(jié)點(diǎn)的指針域指向尾節(jié)點(diǎn)答案一、基本概念1.A.線性2.A.數(shù)據(jù)域3.A.頭節(jié)點(diǎn)4.D.NULL二、基本操作5.B.原節(jié)點(diǎn)的指針域6.A.被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的指針域7.B.O(n)8.B.O(n)三、特殊操作9.B.指針域10.C.快慢指針11.B.快慢指針12.A.順序合并四、算法題（此部分為函數(shù)編寫題，不提供答案）五、鏈表排序21.C.快速排序22.A.中點(diǎn)23.B.尾節(jié)點(diǎn)六、鏈表與遞歸24.A.鏈表的創(chuàng)建25.B.遇到尾節(jié)點(diǎn)26.B.保存當(dāng)前節(jié)點(diǎn)的指針七、鏈表與棧27.D.刪除棧頂元素28.A.頭節(jié)點(diǎn)29.B.出棧八、鏈表與隊(duì)列30.A.插入隊(duì)尾31.A.頭節(jié)點(diǎn)32.B.出