二級(jí)Java語(yǔ)言程序設(shè)計(jì)-公共基礎(chǔ)知識(shí)-第1章數(shù)據(jù)結(jié)構(gòu)與算法[單選題]1.下列敘述中正確的是()A.所謂算法就是計(jì)算方法B.程序可以作為算法的一種描述方法C.算法設(shè)計(jì)只需考慮得到計(jì)算結(jié)果D.算法設(shè)計(jì)（江南博哥）可以忽略算法的運(yùn)算時(shí)間 正確答案：B參考解析：A項(xiàng)錯(cuò)誤，算法并不等同于計(jì)算方法，是指對(duì)解題方案的準(zhǔn)確而完整的描述；C項(xiàng)錯(cuò)誤，算法設(shè)計(jì)需要考慮可行性、確定性、有窮性與足夠的情報(bào)；D項(xiàng)錯(cuò)誤，算法設(shè)計(jì)有窮性要求操作步驟有限且必須在有限時(shí)間內(nèi)完成，耗費(fèi)太長(zhǎng)時(shí)間得到的正確結(jié)果是沒(méi)有意義的B項(xiàng)正確，程序可以作為算法的一種描述方法,算法在實(shí)現(xiàn)時(shí)需要用具體的程序設(shè)計(jì)語(yǔ)言描述答案選擇B選項(xiàng)[單選題]2.算法的有窮性是指()A.算法程序的運(yùn)行時(shí)間是有限的B.算法程序所處理的數(shù)據(jù)量是有限的C.算法程序的長(zhǎng)度是有限的D.算法只能被有限的用戶(hù)使用 正確答案：A參考解析：算法設(shè)計(jì)有窮性要求操作步驟有限且必須在有限時(shí)間內(nèi)完成，耗費(fèi)太長(zhǎng)時(shí)間得到的正確結(jié)果是沒(méi)有意義的答案選擇A選項(xiàng)[單選題]4.算法的時(shí)間復(fù)雜度是指()A.算法的執(zhí)行時(shí)間B.算法所處理的數(shù)據(jù)量C.算法程序中的語(yǔ)句或指令條數(shù)D.算法在執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù) 正確答案：D參考解析：算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。

算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量，即基本運(yùn)算次數(shù)；算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間答案選擇D選項(xiàng)[單選題]5.算法時(shí)間復(fù)雜度的度量方法是()A.算法程序的長(zhǎng)度B.執(zhí)行算法所需要的基本運(yùn)算次數(shù)C.執(zhí)行算法所需要的所有運(yùn)算次數(shù)D.執(zhí)行算法所需要的時(shí)間 正確答案：B參考解析：算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，即算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量的答案選擇B選項(xiàng)[單選題]6.算法的空間復(fù)雜度是指()A.算法程序的長(zhǎng)度B.算法程序中的指令條數(shù)C.算法程序所占的存儲(chǔ)空間D.算法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間 正確答案：D參考解析：算法的空間復(fù)雜度是指算法在執(zhí)行過(guò)程中所需要的計(jì)算機(jī)存儲(chǔ)空間包括算法程序所占空間，輸入的初始數(shù)據(jù)所占空間和執(zhí)行過(guò)程中所需要的額外空間答案選擇D選項(xiàng)[單選題]7.算法的空間復(fù)雜度是指()A.算法在執(zhí)行過(guò)程中所需要的計(jì)算機(jī)存儲(chǔ)空間B.算法所處理的數(shù)據(jù)量C.算法程序中的語(yǔ)句或指令條數(shù)D.算法在執(zhí)行過(guò)程中所需要的臨時(shí)工作單元數(shù) 正確答案：A參考解析：算法的空間復(fù)雜度是指算法在執(zhí)行過(guò)程中所需要的計(jì)算機(jī)存儲(chǔ)空間包括算法程序所占空間，輸入的初始數(shù)據(jù)所占空間和執(zhí)行過(guò)程中所需要的額外空間。

答案選擇A選項(xiàng)[單選題]8.算法空間復(fù)雜度的度量方法是()A.算法程序的長(zhǎng)度B.算法所處理的數(shù)據(jù)量C.執(zhí)行算法所需要的工作單元D.執(zhí)行算法所需要的存儲(chǔ)空間 正確答案：D參考解析：算法的空間復(fù)雜度是指算法在執(zhí)行過(guò)程中所需要的計(jì)算機(jī)存儲(chǔ)空間包括算法程序所占空間，輸入的初始數(shù)據(jù)所占空間和執(zhí)行過(guò)程中所需要的額外空間答案選擇D選項(xiàng)[單選題]9.下列敘述中錯(cuò)誤的是()A.算法的時(shí)間復(fù)雜度與算法所處理數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有直接關(guān)系B.算法的空間復(fù)雜度與算法所處理數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有直接關(guān)系C.算法的時(shí)間復(fù)雜度與空間復(fù)雜度有直接關(guān)系D.算法的時(shí)間復(fù)雜度與算法程序執(zhí)行的具體時(shí)間是不一致的 正確答案：C參考解析：算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)直接決定數(shù)據(jù)輸入，因此會(huì)影響算法所執(zhí)行的基本運(yùn)算次數(shù)，A項(xiàng)正確；算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間，其中包括輸入數(shù)據(jù)所占的存儲(chǔ)空間，B項(xiàng)正確；算法的時(shí)間復(fù)雜度與空間復(fù)雜度沒(méi)有直接關(guān)系，C項(xiàng)錯(cuò)誤；算法程序執(zhí)行的具體時(shí)間受到所使用的計(jì)算機(jī)、程序設(shè)計(jì)語(yǔ)言以及算法實(shí)現(xiàn)過(guò)程中的許多細(xì)節(jié)影響，而算法的時(shí)間復(fù)雜度與這些因素?zé)o關(guān)，所以算法的時(shí)間復(fù)雜度與算法程序執(zhí)行的具體時(shí)間是不一致的，D項(xiàng)正確。

答案選擇C選項(xiàng)[單選題]10.下列關(guān)于算法復(fù)雜度敘述正確的是()A.最壞情況下的時(shí)間復(fù)雜度一定高于平均情況的時(shí)間復(fù)雜度B.時(shí)間復(fù)雜度與所用的計(jì)算工具無(wú)關(guān)C.對(duì)同一個(gè)問(wèn)題，采用不同的算法，則它們的時(shí)間復(fù)雜度是相同的D.時(shí)間復(fù)雜度與采用的算法描述語(yǔ)言有關(guān) 正確答案：B參考解析：A項(xiàng)錯(cuò)誤，最壞情況下的時(shí)間復(fù)雜度有可能與平均情況的時(shí)間復(fù)雜度相同；C項(xiàng)錯(cuò)誤，對(duì)同一個(gè)問(wèn)題，不同的算法時(shí)間復(fù)雜度有時(shí)可能差距很大；D項(xiàng)錯(cuò)誤，算法的時(shí)間復(fù)雜度與實(shí)現(xiàn)算法的描述語(yǔ)言、運(yùn)行環(huán)境無(wú)關(guān)，算法的時(shí)間復(fù)雜度是對(duì)算法執(zhí)行時(shí)所花時(shí)間的度量答案選擇B選項(xiàng)[單選題]11.下面關(guān)于算法的敘述中，正確的是()A.算法的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)B.算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止C.算法的空間復(fù)雜度是指算法程序中指令（或語(yǔ)句）的條數(shù)D.算法所執(zhí)行的基本運(yùn)算次數(shù)與問(wèn)題的規(guī)模無(wú)關(guān) 正確答案：B參考解析：A項(xiàng)錯(cuò)誤，不同的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)有不同的數(shù)據(jù)讀取效率，會(huì)影響到算法的執(zhí)行；C項(xiàng)錯(cuò)誤，算法的空間復(fù)雜度是對(duì)這個(gè)算法所需要的內(nèi)存空間的量度，包括：①算法程序所占的空間；②輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間；③算法執(zhí)行中所需要的額外空間；D項(xiàng)錯(cuò)誤，算法所執(zhí)行的基本運(yùn)算次數(shù)與問(wèn)題的規(guī)模有關(guān)。

答案選擇B選項(xiàng)[單選題]12.下列關(guān)于算法的描述中錯(cuò)誤的是()A.算法強(qiáng)調(diào)動(dòng)態(tài)的執(zhí)行過(guò)程，不同于靜態(tài)的計(jì)算公式B.算法必須能在有限個(gè)步驟之后終止C.算法設(shè)計(jì)必須考慮算法的復(fù)雜度D.算法的優(yōu)劣取決于運(yùn)行算法程序的環(huán)境 正確答案：D參考解析：算法是指對(duì)解題方案的準(zhǔn)確而完整的描述A項(xiàng)正確，算法強(qiáng)調(diào)實(shí)現(xiàn)，不同于數(shù)學(xué)上的計(jì)算方法；B項(xiàng)正確，算法的有窮性是指，算法中的操作步驟為有限個(gè)，且每個(gè)步驟都能在有限時(shí)間內(nèi)完成；C項(xiàng)正確，算法設(shè)計(jì)必須考慮執(zhí)行算法所需要的資源，即時(shí)間復(fù)雜度與空間復(fù)雜度；D項(xiàng)錯(cuò)誤，算法的優(yōu)劣取決于算法復(fù)雜度，只有當(dāng)算法被編程實(shí)現(xiàn)運(yùn)行時(shí)才會(huì)受到運(yùn)行環(huán)境影響答案選擇D選項(xiàng)[單選題]13.線性表常采用的兩種存儲(chǔ)結(jié)構(gòu)是()A.散列方法和索引方式B.鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組C.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu) 正確答案：C參考解析：線性表常用的存儲(chǔ)結(jié)構(gòu)為：①順序存儲(chǔ)結(jié)構(gòu)，物理上連續(xù)存儲(chǔ)，空間位置隱含邏輯位置；②鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，各元素物理存儲(chǔ)上不連續(xù)，通過(guò)指針相連答案選擇C選項(xiàng)[單選題]14.下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是()A.雙向鏈表B.循環(huán)鏈表C.二叉鏈表D.循環(huán)隊(duì)列 正確答案：C參考解析：線性結(jié)構(gòu)要滿(mǎn)足兩個(gè)條件：①有且僅有一個(gè)根結(jié)點(diǎn)；②每個(gè)結(jié)點(diǎn)最多有一個(gè)前驅(qū)，也最多有一個(gè)后繼。

線性表、棧、隊(duì)列都是線性結(jié)構(gòu)，循環(huán)鏈表和雙向鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，屬于線性結(jié)構(gòu)，只是存儲(chǔ)結(jié)構(gòu)不連續(xù)；循環(huán)隊(duì)列是一個(gè)頭結(jié)點(diǎn)和尾結(jié)點(diǎn)互為前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的特殊的隊(duì)列，屬于線性結(jié)構(gòu)；二叉鏈表是二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)槎鏄?shù)有些結(jié)點(diǎn)有兩個(gè)后繼結(jié)點(diǎn)，不符合線性結(jié)構(gòu)的定義，所以二叉鏈表是非線性結(jié)構(gòu)答案選擇C選項(xiàng)[單選題]15.以下數(shù)據(jù)結(jié)構(gòu)中，屬于非線性數(shù)據(jù)結(jié)構(gòu)的是()A.棧B.線性表C.隊(duì)列D.二叉樹(shù) 正確答案：D參考解析：線性結(jié)構(gòu)必須滿(mǎn)足下列兩個(gè)條件：①有且只有一個(gè)根結(jié)點(diǎn)；②每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱(chēng)之為非線性結(jié)構(gòu)二叉樹(shù)中的結(jié)點(diǎn)后繼不惟一，屬于非線性結(jié)構(gòu)，棧和隊(duì)列都是操作受限的線性表，是線性結(jié)構(gòu)答案選擇D選項(xiàng)[單選題]16.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的()A.存儲(chǔ)結(jié)構(gòu)B.物理結(jié)構(gòu)C.邏輯結(jié)構(gòu)D.線性結(jié)構(gòu) 正確答案：C參考解析：數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及數(shù)據(jù)運(yùn)算，其中邏輯結(jié)構(gòu)反映的是數(shù)據(jù)元素之間的邏輯關(guān)系，與使用的計(jì)算機(jī)無(wú)關(guān)答案選擇C選項(xiàng)[單選題]17.數(shù)據(jù)結(jié)構(gòu)主要研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算和()。

A.數(shù)據(jù)的方法B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C.數(shù)據(jù)的對(duì)象D.數(shù)據(jù)的邏輯存儲(chǔ) 正確答案：B參考解析：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，主要研究數(shù)據(jù)元素及其之間的相互關(guān)系和數(shù)據(jù)運(yùn)算，包括：①數(shù)據(jù)的邏輯結(jié)構(gòu)；②數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；③數(shù)據(jù)的運(yùn)算其中邏輯結(jié)構(gòu)反映的是數(shù)據(jù)元素之間的邏輯關(guān)系，與使用的計(jì)算機(jī)無(wú)關(guān)答案選擇B選項(xiàng)[單選題]18.下列描述中，正確的是()A.線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B.棧與隊(duì)列是非線性結(jié)構(gòu)C.雙向鏈表是非線性結(jié)構(gòu)D.只有根結(jié)點(diǎn)的二叉樹(shù)是線性結(jié)構(gòu) 正確答案：A參考解析：線性結(jié)構(gòu)是指如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿(mǎn)足下列兩個(gè)條件：①有且只有一個(gè)根結(jié)點(diǎn)；②每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件B項(xiàng)錯(cuò)誤，棧和隊(duì)列都是操作受限的線性表；C項(xiàng)錯(cuò)誤，雙向鏈表是線性結(jié)構(gòu)；D項(xiàng)錯(cuò)誤，二叉樹(shù)中的結(jié)點(diǎn)后繼不唯一，屬于非線性結(jié)構(gòu)答案選擇A選項(xiàng)[單選題]19.下列關(guān)于線性表的敘述中，不正確的是()A.線性表可以是空表B.線性表是一種線性結(jié)構(gòu)C.線性表的所有結(jié)點(diǎn)有且僅有一個(gè)前件和后件D.線性表是由n個(gè)元素組成的一個(gè)有限序列 正確答案：C參考解析：線性表是由n個(gè)元素組成的一種線性結(jié)構(gòu)，當(dāng)n=0時(shí)線性表為空表。

C項(xiàng)錯(cuò)誤，線性表中，第一個(gè)結(jié)點(diǎn)沒(méi)有前件，最后一個(gè)結(jié)點(diǎn)沒(méi)有后件答案選擇C選項(xiàng)[單選題]20.以下描述中，不是線性表順序存儲(chǔ)結(jié)構(gòu)特征的是()A.可隨機(jī)訪問(wèn)B.需要連續(xù)的存儲(chǔ)空間C.不便于插入和刪除D.邏輯相鄰的數(shù)據(jù)物理位置上不相鄰 正確答案：D參考解析：在計(jì)算機(jī)中用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素稱(chēng)為順序存儲(chǔ)，其中邏輯上相鄰的元素在物理位置上也相鄰順序存儲(chǔ)結(jié)構(gòu)中可以隨機(jī)訪問(wèn)元素，但插入和刪除需要移動(dòng)大量數(shù)據(jù)，耗費(fèi)資源答案選擇D選項(xiàng)[單選題]21.下列敘述中正確的是()A.所有數(shù)據(jù)結(jié)構(gòu)必須有根結(jié)點(diǎn)B.所有數(shù)據(jù)結(jié)構(gòu)必須有終端結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）C.只有一個(gè)根結(jié)點(diǎn)，且只有一個(gè)葉子結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)D.沒(méi)有根結(jié)點(diǎn)或沒(méi)有葉子結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu) 正確答案：D參考解析：D項(xiàng)正確，線性結(jié)構(gòu)的特點(diǎn)是：①集合中必存在“第一個(gè)元素”且惟一；②集合中必存在“最后一個(gè)元素”且惟一；③除最后一個(gè)元素外，其他數(shù)據(jù)元素均有惟一的“后繼”；④除第一個(gè)元素外，其他數(shù)據(jù)元素均有惟一的“前驅(qū)”所以沒(méi)有根結(jié)點(diǎn)或沒(méi)有葉子結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)AB兩項(xiàng)錯(cuò)誤，不是所有數(shù)據(jù)結(jié)構(gòu)都必須有根結(jié)點(diǎn)和葉子結(jié)點(diǎn)；C項(xiàng)錯(cuò)誤，數(shù)據(jù)結(jié)構(gòu)中若有中間結(jié)點(diǎn)不滿(mǎn)足只有一個(gè)前件或者后件的條件，就不是線性結(jié)構(gòu)。

答案選擇D選項(xiàng)[單選題]22.設(shè)數(shù)據(jù)元素的集合D={1,2,3,4,5}，則滿(mǎn)足下列關(guān)系R的數(shù)據(jù)結(jié)構(gòu)中為線性結(jié)構(gòu)的是()A.R={(1,2),(3,4),(5,1),(1,2)}B.R={(1,3),(4,1),(3,2),(5,4)}C.R={(1,2),(2,3),(4,5),(2,3)}D.R={(1,3),(2,4),(3,5),(1,2)} 正確答案：B參考解析：一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)如果滿(mǎn)足以下兩個(gè)條件：有且只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件，稱(chēng)為線性結(jié)構(gòu)不同時(shí)滿(mǎn)足以上兩個(gè)條件的數(shù)據(jù)結(jié)構(gòu)就稱(chēng)為非線性結(jié)構(gòu)A選項(xiàng)，5是1的前件，1是2的前件，3是4的前件，則關(guān)系R中含有兩個(gè)結(jié)構(gòu)，即34和512，其中3和5均為根結(jié)點(diǎn)，故A項(xiàng)錯(cuò)誤B選項(xiàng)根結(jié)點(diǎn)為5，排列順序?yàn)?4132，B選項(xiàng)正確C選項(xiàng)有兩個(gè)根結(jié)點(diǎn)1。