2024年10月自考02331數(shù)據(jù)結(jié)構(gòu)押題及答案含解析匯總

自考02331數(shù)據(jù)結(jié)構(gòu)押題及答案含解析匯總第一章單選1.數(shù)據(jù)結(jié)構(gòu)不包含的內(nèi)容是（）A.數(shù)據(jù)的元素來源B.數(shù)據(jù)的邏輯結(jié)構(gòu)C.數(shù)據(jù)的存儲結(jié)構(gòu)D.對數(shù)據(jù)施加的操作答案:A解析:本題考查了數(shù)據(jù)結(jié)構(gòu)的內(nèi)容、作用和意義。數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，并且也包含某些算法，如散列存儲就需要利用某種特定的算法來實(shí)現(xiàn)，不過數(shù)據(jù)結(jié)構(gòu)不包含元素來源。2.在數(shù)據(jù)結(jié)構(gòu)中，它的基本單位是（）A.數(shù)據(jù)B.數(shù)據(jù)項(xiàng)C.數(shù)據(jù)元素D.數(shù)據(jù)對象答案:C解析:本題考查了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)的基本單位。數(shù)據(jù)結(jié)構(gòu)的基本單位是數(shù)據(jù)元素。3.下列關(guān)于線性結(jié)構(gòu)的說法中錯誤的是（）A.結(jié)構(gòu)中只含有一個開始結(jié)點(diǎn)B.結(jié)構(gòu)中只含有一個終端結(jié)點(diǎn)C.結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對一的對應(yīng)關(guān)系D.結(jié)構(gòu)中的所有結(jié)點(diǎn)都有一個直接前趨和直接后繼答案:D解析:本題考查了數(shù)據(jù)結(jié)構(gòu)中的線性結(jié)構(gòu)。在線性結(jié)構(gòu)中，開始結(jié)點(diǎn)只有直接后繼，終端結(jié)點(diǎn)只有直接前趨，其他說法均正確。4.下列關(guān)于非線性結(jié)構(gòu)的說法中正確的是（）A.結(jié)構(gòu)中只含有一個開始結(jié)點(diǎn)B.結(jié)構(gòu)中只含有一個終端結(jié)點(diǎn)C.結(jié)構(gòu)中的結(jié)點(diǎn)之間必定存在一對一的對應(yīng)關(guān)系D.結(jié)構(gòu)中的結(jié)點(diǎn)可能存在多對多的對應(yīng)關(guān)系答案:D解析:本題考查了數(shù)據(jù)結(jié)構(gòu)中的非線性結(jié)構(gòu)。在非線性結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對多或多對多的對應(yīng)關(guān)系，所以可能有多個開始結(jié)點(diǎn)或終端結(jié)點(diǎn)。5.在存儲結(jié)構(gòu)的四種基本存儲方法中，需要引用“指針”的是（）A.順序存儲方法B.鏈接存儲方法C.索引存儲方法D.散列存儲方法答案:B解析:本題考查了存儲結(jié)構(gòu)中的鏈接存儲方法。在鏈接存儲方法中，元素間的邏輯關(guān)系是由附加的指針域表示的，需要引用“指針”。6.下列不屬于五個算法準(zhǔn)則的是（）A.輸入B.有窮性C.隨機(jī)性D.可行性答案:C解析:本題考查了算法的五個準(zhǔn)則。算法的五個準(zhǔn)則包括：輸入、輸出、有窮性、確定性和可行性。7.若要實(shí)現(xiàn)更快速地解決問題，就需要高效率的算法，我們把執(zhí)行算法耗費(fèi)的時間稱為（）A.時間復(fù)雜度B.空間復(fù)雜度C.可讀性D.可操作性答案:A解析:本題考查了算法分析中的時間復(fù)雜性概念。時間復(fù)雜性，是指執(zhí)行算法所耗費(fèi)的時間。8.算法中有一指令“for(i=0；i<=9；i++)”，則該指令的執(zhí)行次數(shù)和頻度分別為（）A.9,9B.9,10C.10,10D.10,11答案:D解析:本題考查了算法的頻度和時間復(fù)雜度。在該指令中，i的值由0增至9，共循環(huán)執(zhí)行10次，但由于指令自身的特點(diǎn)，i的最終值為10，共計算了11次，所以該指令的執(zhí)行次數(shù)為10，自身執(zhí)行次數(shù)（頻度）為11。9.A.AB.BC.CD.D答案:A解析:本題考查了算法的時間復(fù)雜度。對于任何一個總執(zhí)行次數(shù)為常數(shù)的算法，我們都表示成1，即。10.下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是（）A.棧B.隊(duì)列C.單鏈表D.二叉樹答案:D解析:本題考查了非線性結(jié)構(gòu)的概念。選項(xiàng)中只有二叉樹是非線性結(jié)構(gòu)，其余均為線性結(jié)構(gòu)。11.下列關(guān)于算法的說法錯誤的是（）A.每一步算法的含義要明確B.算法的執(zhí)行次數(shù)是有限的C.算法只能解決數(shù)值計算問題D.同一種問題可以有多種解決算法答案:C解析:本題考查了算法的概念。通過設(shè)計不同的算法可以實(shí)現(xiàn)不同的功能，不僅僅局限于數(shù)值計算問題，其余說法均正確。12.“算法+數(shù)據(jù)結(jié)構(gòu)=程序”中的數(shù)據(jù)結(jié)構(gòu)指的是（）A.邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)B.線性結(jié)構(gòu)和非線性結(jié)構(gòu)C.順序存儲和非線性結(jié)構(gòu)D.線性結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)答案:A解析:本題考查了數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)包含邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。13.若結(jié)點(diǎn)的存儲地址與其關(guān)鍵字之間存在某種映射關(guān)系，則稱這種存儲結(jié)構(gòu)為（）A.順序存儲結(jié)構(gòu)B.鏈?zhǔn)酱鎯Y(jié)構(gòu)C.索引存儲結(jié)構(gòu)D.散列存儲結(jié)構(gòu)答案:D解析:本題考查了數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)中的散列存儲方法。散列存儲方法根據(jù)元素的關(guān)鍵字直接計算出該元素的存儲地址。14.算法分析的兩個主要方面是（）A.正確性和簡明性B.時間復(fù)雜性和空間復(fù)雜性C.可讀性和可維護(hù)性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性答案:B解析:本題考查了算法分析的兩個主要概念。算法分析中要考慮時間復(fù)雜性和空間復(fù)雜性。15.算法指的是（）A.計算機(jī)程序B.解決問題的計算方法C.解決問題的有限運(yùn)算序列D.排序算法答案:C解析:本題考查了算法的描述。算法指的是解決問題的有限運(yùn)算序列。第一章填空+簡答1.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)項(xiàng)，是具有獨(dú)立含義的________標(biāo)識單位。答案:最小解析:本題考查了數(shù)據(jù)項(xiàng)的概念。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識單位。2.在線性結(jié)構(gòu)中，沒有直接后繼的是_______結(jié)點(diǎn)。答案:終端解析:本題考查了線性結(jié)構(gòu)中的終端結(jié)點(diǎn)的概念。線性結(jié)構(gòu)中的開始結(jié)點(diǎn)沒有直接前趨，只有直接后繼。終端結(jié)點(diǎn)有直接前趨，沒有直接后繼。3.算法五原則分別是輸入、輸出、_________、確定性和可行性。答案:有窮性解析:本題考查了算法的五個準(zhǔn)則。算法五原則分別是輸入、輸出、有窮性、確定性和可行性。4.數(shù)據(jù)結(jié)構(gòu)一般包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和______三個方面的內(nèi)容。答案:數(shù)據(jù)運(yùn)算解析:本題考查了數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)一般包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)運(yùn)算。5.數(shù)據(jù)的邏輯結(jié)構(gòu)可分為非線性結(jié)構(gòu)和_________兩大類。答案:線性結(jié)構(gòu)解析:本題考查了數(shù)據(jù)的邏輯結(jié)構(gòu)的概念。邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。6.數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）一般可以用_________、鏈接存儲方法、索引存儲方法和散列存儲方法等四種存儲方法表示。答案:順序存儲方法解析:本題考查了存儲結(jié)構(gòu)的四種基本的存儲方法。包括順序存儲方法、鏈接存儲方法、索引存儲方法和散列存儲方法。7.設(shè)有一批數(shù)據(jù)元素，為了方便地插入一個元素，宜用______結(jié)構(gòu)存儲。答案:鏈接解析:本題考查了存儲結(jié)構(gòu)中鏈接存儲方法的概念。鏈接存儲方法可以方便地插入一個元素。8.答案:9.答案:10.答案:11.答案:第二章單選11.A.AB.BC.CD.D答案:A解析:2.A.3B.5C.8D.10答案:D解析:3.已知某線性表中含有6個元素，現(xiàn)要在第2位和第3位元素之間插入一個新的元素，那么需要移動的元素總數(shù)為（）A.2B.4C.6D.0答案:B解析:本題考查了線性表的插入運(yùn)算。欲在第2位和第3位元素之間插入新元素，那么這個元素應(yīng)插在第3位上，則從第3位開始，包括之后的所有元素都需向后移動一位，總數(shù)為：4.已知某線性表中含有6個元素，現(xiàn)要刪除第3位元素，那么需要移動的元素總數(shù)為（）A.0B.1C.2D.3答案:D解析:本題考查了線性表的刪除運(yùn)算。欲刪除第3位元素，則該位置之后的所有元素都需向前移動一位，總數(shù)為：5.在線性表的單鏈表存儲結(jié)構(gòu)中，結(jié)點(diǎn)中data和next分別表示（）A.存儲的元素，直接前趨的地址B.存儲的元素，直接后繼的地址C.指針的數(shù)量，直接前趨的地址D.指針的數(shù)量，直接后繼的地址答案:B解析:本題考查了鏈表中結(jié)點(diǎn)的存儲結(jié)構(gòu)。結(jié)點(diǎn)包含兩個域，數(shù)據(jù)域（data）中存放的是存儲的元素，指針域（next）中存放的是元素的直接后繼的地址，利用指針指向該直接后繼的結(jié)點(diǎn)，實(shí)現(xiàn)鏈?zhǔn)酱鎯Α?.在單鏈表中實(shí)現(xiàn)插入時，為使插入后的元素順序與輸入的元素順序一致，可采用（）A.頭插法建表_________B.尾插法建表C.中間法建表_________D.指針法建表答案:B解析:本題考查了單鏈表中尾插法建表。利用頭插法建表，每次都將新元素插在表頭，最終的元素順序?qū)⑴c輸入的元素順序相反；利用尾插法建表，每次都將新元素插在表尾，最終的元素順序和輸入的元素順序相同。7.下列選項(xiàng)中，屬于順序存儲結(jié)構(gòu)優(yōu)點(diǎn)的是（）A.插入運(yùn)算方便B.刪除運(yùn)算方便C.存儲密度大D.方便存儲各種邏輯結(jié)構(gòu)答案:C解析:本題考查了順序存儲結(jié)構(gòu)的特點(diǎn)。在順序存儲結(jié)構(gòu)中，不方便做元素的插入和刪除運(yùn)算，因?yàn)槊看味夹枰苿雍芏嘣?，并且只能存儲線性結(jié)構(gòu)的元素，不適于存儲非線性結(jié)構(gòu)的元素。8.在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，方便做元素的插入和刪除運(yùn)算，原因是（）A.存儲的元素數(shù)量很少B.可進(jìn)行隨機(jī)存取C.元素的存儲地址都是連續(xù)的D.采用了“指針”表示法答案:D解析:本題考查了鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，利用“指針”指向下一個存儲的結(jié)點(diǎn)，在進(jìn)行元素的插入和刪除時，只需改變指針的指向即可，不需要移動大量元素。9.下列關(guān)于線性表的說法正確的是（）A.線性表可以含有無限個元素B.線性表中的元素只能是具體的數(shù)字C.線性表是一種線性結(jié)構(gòu)D.長度為n的線性表最多可含有n-1個元素答案:C解析:本題考查了線性表的概念。長度為n的線性表可含有n個元素，存放元素數(shù)量有限，并且也可存放字符和圖片等。10.若某線性表中第三個數(shù)據(jù)元素的存儲地址為5，每個元素占3個存儲單元，那么第10個元素的存儲地址是（）A.10B.20C.30D.26答案:D解析:第二章單選+填空+算法閱讀+算法設(shè)計1.下列關(guān)于線性結(jié)構(gòu)的說法錯誤的是（）A.結(jié)構(gòu)中只有一個開始結(jié)點(diǎn)B.結(jié)構(gòu)中只有一個終端結(jié)點(diǎn)C.終端結(jié)點(diǎn)的直接后繼指向開始結(jié)點(diǎn)D.結(jié)構(gòu)中的數(shù)據(jù)元素呈線性關(guān)系答案:C解析:本題考查了線性表的邏輯特征。線性結(jié)構(gòu)中，數(shù)據(jù)元素是一一對應(yīng)的線性關(guān)系，結(jié)構(gòu)中只含有一個開始結(jié)點(diǎn)和一個終端結(jié)點(diǎn)，并且開始結(jié)點(diǎn)無直接前趨，終端結(jié)點(diǎn)無直接后繼。2.下列數(shù)據(jù)結(jié)構(gòu)中，不屬于線性結(jié)構(gòu)的是（）A.棧B.隊(duì)列C.樹D.單鏈表答案:C解析:本題考查了線性表的邏輯結(jié)構(gòu)特征。除了樹是非線性結(jié)構(gòu)，其他均為線性結(jié)構(gòu)。3.一個線性表含有10個數(shù)據(jù)元素，每個元素占2個存儲單元，若第一個元素的存儲地址為100，則第10個數(shù)據(jù)元素的存儲地址為（）A.100B.110C.118D.190答案:C解析:4.下列關(guān)于順序存儲結(jié)構(gòu)說法正確的是（）A.便于元素的插入B.便于元素的刪除C.含有指針D.可實(shí)現(xiàn)隨機(jī)存取答案:D解析:本題考查了順序存儲結(jié)構(gòu)的特點(diǎn)。順序存儲結(jié)構(gòu)不便于元素的插入和刪除，鏈?zhǔn)酱鎯Y(jié)構(gòu)含有指針。5.線性表序列為{1311182031}，若將元素22插入該表中，則需移動的元素數(shù)量為（）A.1B.2C.3D.4答案:A解析:本題考查了線性表的插入運(yùn)算。22應(yīng)插在20和31之間，所以應(yīng)后移1位元素“31”。6.對于一個需要經(jīng)常進(jìn)行元素在單循環(huán)鏈表中，令頭指針head指向頭結(jié)點(diǎn)，則下列表示該鏈表為空的是（）A.head==NULLB.head！=NULLC.head→next==headD.head→next==NULL答案:C解析:本題考查了單循環(huán)鏈表的概念?？諉窝h(huán)鏈表中無任何結(jié)點(diǎn)，頭指針只能指向自己。7.下列關(guān)于鏈?zhǔn)酱鎯Y(jié)構(gòu)的說法正確的是（）A.可實(shí)現(xiàn)隨機(jī)存取B.引用“指針”來呈現(xiàn)數(shù)據(jù)關(guān)系C.不利于元素的插入D.不利于元素的刪除答案:B解析:本題考查了鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)。鏈?zhǔn)酱鎯Y(jié)構(gòu)利于元素的插入和刪除，不可實(shí)現(xiàn)隨機(jī)存取，并引用了指針概念。8.線性表序列為{01122334455}，若將元素33刪除，則需移動的元素數(shù)量為（）A.1B.2C.3D.4答案:B解析:本題考查了線性表的插入運(yùn)算。23應(yīng)插在22和33之間，所以應(yīng)前移2位元素。9.若線性表中每個元素占5個存儲單元，第1個元素的存儲地址為5，則第5個元素的存儲地址為（）A.10B.15C.20D.25答案:D解析:10.順序表中，邏輯上相鄰的元素，其存儲地址（）A.一定相鄰B.一定不相鄰C.不一定相鄰D.可能不相鄰答案:A解析:本題考查了順序表中順序存儲結(jié)構(gòu)的特點(diǎn)。順序表的特點(diǎn)是將邏輯上相鄰的元素存儲到地址也相鄰的物理地址中，所以存儲地址一定相鄰。11.在單鏈表中，結(jié)點(diǎn)D所指的結(jié)點(diǎn)不是終端結(jié)點(diǎn)，那么將結(jié)點(diǎn)H插入到結(jié)點(diǎn)D后的語句是_______。答案:H→next=D→next；D→next=H解析:本題考查了單鏈表的插入運(yùn)算。“H→next=D→next”實(shí)現(xiàn)結(jié)點(diǎn)H指向結(jié)點(diǎn)D的下一個結(jié)點(diǎn)，“D→next=H”實(shí)現(xiàn)結(jié)點(diǎn)D指向結(jié)點(diǎn)H。12.在線性結(jié)構(gòu)中，沒有直接前趨的是_______結(jié)點(diǎn)。答案:開始解析:本題考查了線性表的邏輯特征。線性結(jié)構(gòu)中的開始結(jié)點(diǎn)沒有直接前趨，只有直接后繼。13.順序表中第一個元素的存儲地址為100，其中每個元素占5個存儲單元，那么第7個元素的存儲地址為_______。答案:130解析:本題考查了線性表中元素的存儲地址關(guān)系。100+（7-1）*5=130。14.在一個長度為n的順序表中刪除第i個元素，需要向前移動_______個元素。答案:n-i解析:本題考查了順序表的刪除運(yùn)算。需要刪除第i個元素，所以要向前移動n-i個元素。15.在用p指針訪問單鏈表時，判斷不是訪問結(jié)束的條件是______。答案:p!=NULL；解析:本題考查了單鏈表的概念。當(dāng)訪問到最后的終端結(jié)點(diǎn)無后繼結(jié)點(diǎn)，所以終端結(jié)點(diǎn)的指針域?yàn)榭眨肗ULL表示。16.在訪問單循環(huán)鏈表時，判斷不是訪問表結(jié)束的條件是________。答案:p!=head；解析:本題考查了單循環(huán)鏈表的概念。單循環(huán)鏈表的終端結(jié)點(diǎn)的指針域不為空，而是指向鏈表的頭結(jié)點(diǎn)，從而構(gòu)成了一個循環(huán)鏈表。17.對于一個需要經(jīng)常進(jìn)行元素增減的線性表，宜采用_______存儲結(jié)構(gòu)。答案:鏈?zhǔn)浇馕?本題考查了鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)。在線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)中，鏈?zhǔn)酱鎯Y(jié)構(gòu)方便元素的插入和刪除。18.下列函數(shù)的功能是：在帶頭結(jié)點(diǎn)的單鏈表上進(jìn)行選擇排序。請在空白處填上適當(dāng)內(nèi)容將函數(shù)補(bǔ)充完整，并說明該算法是否是穩(wěn)定的。答案:（1）q->next（2）p->next=q->next（3）r->next=q該算法是穩(wěn)定的。解析:本題考查單鏈表的刪除與插入（調(diào)換）。算法語句含義：從第一個和第二個結(jié)點(diǎn)開始比較，若第一個結(jié)點(diǎn)大于第二個結(jié)點(diǎn)，則繼續(xù)比較第二個和第三個結(jié)點(diǎn)；若第一個結(jié)點(diǎn)小于第二個結(jié)點(diǎn)，則交換兩結(jié)點(diǎn)的位置；直到查找完畢整條鏈表。該算法的目的是，將鏈表中的結(jié)點(diǎn)按關(guān)鍵字大小的升序進(jìn)行排列，通過對算法的分析發(fā)現(xiàn)，此類算法并不會破壞關(guān)鍵字的相對次序，所以是穩(wěn)定的。19.下列函數(shù)的功能是在帶頭結(jié)點(diǎn)的單鏈表head中刪除所有數(shù)據(jù)域值為x的結(jié)點(diǎn)，請在空白處填上適當(dāng)?shù)恼Z句，使其完成指定的功能。答案:（1）p->next=q（2）q=q->next （或q=p->next）解析:本題考查的是單鏈表的刪除操作指令。20.設(shè)非空雙向循環(huán)鏈表L的頭指針為head，表結(jié)點(diǎn)類型為DLNode。但L中所有結(jié)點(diǎn)的prior域均為空（NULL），函數(shù)f30的功能就是為每個結(jié)點(diǎn)的prior域賦值，請將下列算法補(bǔ)充完整。答案:（1）head（2）p->next->prior（3）head->prior解析:本題考查了雙向循環(huán)鏈表的構(gòu)成和指針域的賦值。（1）該語句用來判斷鏈表是否是空鏈；（2）該語句完成prior域的賦值，使p指向的結(jié)點(diǎn)指向p本身，構(gòu)成雙向循環(huán)鏈表；（3）該語句令頭結(jié)點(diǎn)head指向最后一個結(jié)點(diǎn)。21.設(shè)帶頭結(jié)點(diǎn)的單鏈表初始為空。將從鍵盤讀入的每個字符作為一個結(jié)點(diǎn)加入該鏈表表尾，當(dāng)讀入回車符時結(jié)束并返回鏈表表頭指針。請在空白處填寫適當(dāng)內(nèi)容，完成其功能。答案:（1）p=(ListNode*)malloc(sizeof(ListNode))（2）rear->next=p（3）head解析:本題考查單鏈表的“尾插法建表”。22.閱讀下列程序，回答問題。style="max-width:100%;">（1）若鏈表L={12,0,15,77,26,42}，則f30（L）的輸出結(jié)果是？（2）函數(shù)f30的功能是什么？答案:（1）77（2）返回（找出）鏈表中結(jié)點(diǎn)的最大值。23.閱讀下列算法，并回答問題。style="max-width:100%;">（1）若SL1->data中的數(shù)據(jù)為{25，4，256，9，-38，47，128，256，64}，SL2->data中的數(shù)據(jù)為{22，4，-63，15，29，34，42，3}，則算法f33（&SL1，&SL2）后SL1->data和SL2->data中的數(shù)據(jù)各是什么？（2）該算法的功能是什么？答案:本題考查了線性表的插入和刪除運(yùn)算。（1）SL1->data中的數(shù)據(jù)是{25，4，256，15，29，47，128，256，64}SL2->data中的數(shù)據(jù)是{22，4，-63，9，-38，34，42，3}（2）該算法比較兩個線性表中相同下標(biāo)位置的兩個元素，較大者移動到較長的線性表中，較小者移動到較短的線性表中。解析:該題程序較長，但算法簡單，需耐心分析。該算法的含義是，先比較兩個線性表的長度，將長度較長的線性表作為SL1代入f33函數(shù)中，將長度較小的線性表作為SL2代入f33函數(shù)中。比較兩個線性表中相同下標(biāo)位置的兩個元素，較大者移動到較長的線性表中，較小者移動到較短的線性表中。24.設(shè)有兩個順序表A和B，且都遞增有序。試寫一算法，從A中刪除與B中相同的那些元素（也就是計算A-B）。答案:解析:本題考查了順序表的刪除運(yùn)算。算法思想是：掃描整個B表，順序取表中每個元素，然后與表A中從某下標(biāo)開始的元素進(jìn)行比較（因?yàn)閮杀矶际怯行虻?，不必每次從頭開始，用一個變量k標(biāo)識上一次比較結(jié)束的位置），當(dāng)B中的某元素值大于或等于A的某個元素時，比較結(jié)束。記住A表的當(dāng)前下標(biāo)值k，之后再比較兩元素值是否相等，若相等，則從表A中刪除該元素，而后繼續(xù)B中的下一個元素與A中從第k個元素開始向后比較；否則，繼續(xù)，……，直到B中所有元素比較完為止。25.設(shè)有一個帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，head為鏈表的頭指針。試寫一算法，實(shí)現(xiàn)在值為x的結(jié)點(diǎn)之前插入一個值為y的結(jié)點(diǎn)。答案:解析:本題考查了雙向循環(huán)鏈表的查找運(yùn)算。因?yàn)殒湵硎请p向循環(huán)鏈表，所以不需要用指針指向x之前的結(jié)點(diǎn)，但要先從開始結(jié)點(diǎn)用循環(huán)找到要插入的位置，也就是x結(jié)點(diǎn)的位置。第三章單選1.若入棧的一列元素序列為1,2,3,4，則可能的出棧順序是（）A.1,4,2,3B.3,4,1,2C.2,4,3,1D.4,1,3,2答案:C解析:本題考查了棧的“后進(jìn)先出”原則。棧中的元素遵循“后進(jìn)先出”的原則，先使1進(jìn)棧，然后2進(jìn)棧，再立刻讓2出棧，之后3和4入棧，再依次使4、3、1出棧。在其他選項(xiàng)中，出棧順序不符合“后進(jìn)先出”原則。2.已知棧頂元素為1，則下列表示元素1出棧的運(yùn)算是（）A.InitStack(&S)B.GetTop(S)C.Push（&S,1)D.Pop（&S)答案:D解析:本題考查了棧的基本運(yùn)算中的出棧運(yùn)算。在棧的運(yùn)算中，Pop（&S)表示刪除棧頂元素，即出棧。3.下列可用于判斷順序棧是否為空棧的運(yùn)算為（）A.S-＞top=-1B.returnS-＞top==-1C.returnS-＞top==StackSize-1D.S-＞top=S-＞top+1答案:B解析:本題考查了順序?；具\(yùn)算中的置空棧?！皉eturnS-＞top==-1”用來判斷?？?，而“S-＞top=-1”是用來令棧為空棧的。4.在棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，不需要設(shè)置頭結(jié)點(diǎn)的原因是（）A.該存儲結(jié)構(gòu)中的結(jié)點(diǎn)沒有直接前趨B.該存儲結(jié)構(gòu)中的結(jié)點(diǎn)沒有直接后繼C.棧是非線性結(jié)構(gòu)D.只在棧頂?shù)囊欢诉M(jìn)行元素的插入和刪除答案:D解析:本題考查了棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)的概念。由于棧的“后進(jìn)先出”原則，元素的插入和刪除都只在棧頂進(jìn)行，所以不需要設(shè)置頭結(jié)點(diǎn)。5.下列可用于判斷鏈棧是否為空棧的運(yùn)算為（）A.returntop==NULLB.top=pC.p-＞next=topD.top=p-＞next答案:A解析:本題考查了鏈棧基本運(yùn)算中的判?？?。在鏈棧中，用于判斷空棧的運(yùn)算是“returntop==NULL”。6.下列關(guān)于棧和隊(duì)列的相同之處，說法正確的是（）A.都只在一端進(jìn)行元素的插入和刪除B.都遵循“先進(jìn)先出”原則C.鏈?zhǔn)酱鎯Y(jié)構(gòu)中都不需要設(shè)置頭結(jié)點(diǎn)D.鏈?zhǔn)酱鎯Y(jié)構(gòu)中都需要設(shè)置頭結(jié)點(diǎn)答案:A解析:本題考查了棧和隊(duì)列的概念。對于棧，只在棧頂進(jìn)行元素的插入和刪除，而在隊(duì)列中，在隊(duì)尾實(shí)現(xiàn)元素的插入，在隊(duì)頭實(shí)現(xiàn)元素的刪除，遵循“先進(jìn)先出”原則，最先插入的元素也會最先被刪除；由于元素的插入和刪除的實(shí)現(xiàn)方式不同，所以鏈棧不需要設(shè)置頭結(jié)點(diǎn)，而鏈?zhǔn)疥?duì)列需要。7.在隊(duì)列的基本運(yùn)算中，表示將元素1插入隊(duì)列中的是（）A.InitQueue(Q)B.EnQueue(Q,1)C.DeQueue(Q)D.GetFront(Q)答案:B解析:本題考查了隊(duì)列的基本算法中的入隊(duì)列。在隊(duì)列的基本運(yùn)算中，“EnQueue(Q,1)”表示將元素1插入到隊(duì)列中。8.若用一個大小為5的數(shù)組保存循環(huán)隊(duì)列Q，若經(jīng)過一次元素的插入和兩次元素的刪除后，rear和front的值分別是1、4，那么在此之前rear和front的值分別是（）A.0,1B.1,2C.0,2D.1,3答案:C解析:本題考查了順序循環(huán)隊(duì)列的rear值和front值的判斷。在循環(huán)隊(duì)列中，每經(jīng)過一次元素的插入則rear的值加一，每經(jīng)過一次元素的刪除則front的值加一，所以應(yīng)選擇C。9.循環(huán)隊(duì)列的rear和front的值分別是1,5，若出隊(duì)一個元素，入隊(duì)兩個元素，則rear和front的值分別是（）A.2,5B.3,6C.2,7D.3,7答案:B解析:本題考查了順序循環(huán)隊(duì)列的rear值和front值的判斷。在循序隊(duì)列中，入隊(duì)時rear的值加1，出隊(duì)時front的值加1，所以選擇B。10.在鏈棧中，判?？盏闹噶钍牵ǎ〢.returntop==NULLB.returntopC.top==NULLD.returnS-＞data[S-＞top]答案:A解析:本題考查了鏈棧的基本運(yùn)算中的判棧空。鏈棧的判棧空為“returntop==NULL”。11.清空順序棧中所有數(shù)據(jù)元素的指令是（）A.S-＞top=-1B.returnS-＞top==-1C.returnS-＞top==StackSize-1D.returntop==NULL答案:A解析:本題考查了順序?；具\(yùn)算中的置空棧。置空棧即可達(dá)到想要的結(jié)果，而置空棧的指令為S-＞top=-1，而returnS-＞top==-1是用來判斷空棧的。12.若棧S的序列為{0123}，則執(zhí)行一次Pop（&S)后，棧頂元素為（）A.0B.1C.2D.3答案:C解析:本題考查了棧的出棧運(yùn)算。Pop（&S)是出棧指令，將會刪去棧頂元素，所以執(zhí)行后的棧頂元素為2。13.用于判斷順序棧是否為空棧的是（）A.S-＞top=-1B.returnS-＞top==-1C.returnS-＞top==StackSize-1D.returntop==NULL答案:B解析:本題考查了順序?；具\(yùn)算中的判?？铡Ｅ袟？眨簉eturnS-＞top==-1。14.在鏈棧中，“p-＞data=x；p-＞next=top；top=p；”的含義為（）A.數(shù)據(jù)域?yàn)閜的結(jié)點(diǎn)x的進(jìn)棧B.數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)p的進(jìn)棧C.數(shù)據(jù)域?yàn)閜的結(jié)點(diǎn)p的出棧D.數(shù)據(jù)域?yàn)閜的結(jié)點(diǎn)x的出棧答案:B解析:本題考查了鏈棧的進(jìn)棧運(yùn)算?！皃-＞data=x”的含義為將x賦給結(jié)點(diǎn)P的數(shù)據(jù)域，“p-＞next=top；top=p”的含義為插入結(jié)點(diǎn)p。15.循環(huán)隊(duì)列的rear和front的值分別是0,2，若出隊(duì)兩個元素，入隊(duì)一個元素，則rear和front的值分別是（）A.0,1B.0,2C.1,3D.1,4答案:D解析:本題考查了循環(huán)隊(duì)列中rear值和front值的概念。在循序隊(duì)列中，入隊(duì)時rear的值加1，出隊(duì)時front的值加1，所以選擇D。16.用于判斷順序棧是否飽和的是（）A.S-＞top=-1B.returnS-＞top==-1C.returnS-＞top==StackSize-1D.returntop==NULL答案:C解析:本題考查了順序棧的判棧滿運(yùn)算。判棧滿：returnS-＞top==StackSize-1。17.在鏈棧中，“top=p-＞next；free(p)”的含義為（）A.結(jié)點(diǎn)p的進(jìn)棧B.結(jié)點(diǎn)p的出棧C.利用結(jié)點(diǎn)p判?？誅.利用結(jié)點(diǎn)p判棧滿答案:B解析:本題考查了鏈棧的基本運(yùn)算。見“押題精華”鏈?；具\(yùn)算的實(shí)現(xiàn)。18.若棧S的序列為{0123}，x=0，則執(zhí)行一次Push（&S,x)后，棧頂元素為（）A.0B.1C.2D.3答案:A解析:本題考查了棧的入棧運(yùn)算。Push（&S,x)是入棧指令，最終棧頂元素為x=0。19.順序棧中，“S-＞top=S-＞top+1；S-＞data[S-＞top]=x”的含義是（）A.判?？誃.判棧滿C.元素x進(jìn)棧D.元素x出棧答案:C解析:本題考查了順序棧的進(jìn)棧運(yùn)算。順序棧棧頂指針top的值加1，然后將元素x放入棧頂，實(shí)現(xiàn)元素x的進(jìn)棧。第三章填空+解答1.現(xiàn)有可容納100個元素的數(shù)組A[0...99]，該數(shù)組供給兩個棧使用，為了充分利用存儲空間，若第一個棧的棧底元素保存在A[99]中，那么第二個棧的棧底元素應(yīng)保存在______中。答案:A[0]解析:本題考查了棧的順序存儲結(jié)構(gòu)。為實(shí)現(xiàn)存儲空間的充分利用，應(yīng)使兩個棧從頭和尾（相向而行）分別開始進(jìn)行元素的存儲，這樣一可避免為某個棧分配的存儲空間不足，二可實(shí)現(xiàn)存儲空間的充分利用。2.假設(shè)以S和X分別表示進(jìn)棧和退棧操作，則對輸入序列a,b,c,d,e進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為_______。答案:b,c,e,d,a解析:本題考查了棧的基本算法的進(jìn)棧和退棧操作。3.設(shè)順序棧存放在S.data[maxsize]中，棧底位置是maxsize-1，則?？諚l件是_______；棧滿條件是______。答案:s.top==maxsize;s.top==0解析:本題考查了順序棧的基本運(yùn)算的判?？蘸团袟M。4.從循環(huán)隊(duì)列中刪除一個元素時，其操作是先_______，后_______。答案:取出隊(duì)頭元素移動隊(duì)頭指針解析:本題考查了循環(huán)隊(duì)列的基本運(yùn)算中的出隊(duì)列運(yùn)算。5.若循環(huán)隊(duì)列用數(shù)組data[m]存儲元素值，用front和rear分別作為頭尾指針，則當(dāng)前元素的個數(shù)為______。答案:（rear-front+m）%m解析:本題考查了對循環(huán)隊(duì)列中rear值和front值的運(yùn)用。6.一個直接調(diào)用自己或間接調(diào)用自己的函數(shù)，稱為______。答案:遞歸函數(shù)解析:本題考查了遞歸的概念。7.假設(shè)輸入棧的元素為a、b、c，在棧S的輸出端得到一個輸出序列為a、b、c，試寫出在輸入端所有可能的輸入序列。答案:可能的輸入序列為：a,b,c;a,c,b;b,a,c;c,a,b;c,b,a。解析:本題考查了棧的基本特性。8.設(shè)將整數(shù)1,2,3,4依次進(jìn)棧，進(jìn)棧的同時可以出棧，請回答下述問題：（1）若入、出棧次序?yàn)镻ush(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop()，則出棧的數(shù)字序列是什么？（這里Push（i）表示i進(jìn)棧，Pop（）表示出棧）（2）能否得到出棧序列1423和1432？并說明為什么？（3）請分析1,2,3,4的24種排列中，哪些序列是可以通過相應(yīng)的入、出棧操作得到的？答案:（1）出棧序列為：1324。（2）不能得到1423序列。因?yàn)橐玫?4的出棧序列，則應(yīng)做Push（1）,Pop(),Push（2）,Push（3）,Push（4）,Pop()。這樣3在棧頂，2在棧底，所以不能得到23的出棧序列。能得到1432的出棧序列。具體操作為：Push（1）,Pop(),Push（2）,Push（3）,Push（4）,Pop(),Pop(),Pop()。（3）在1,2,3,4的24種排列中，可通過相應(yīng)入、出棧操作得到的序列是：1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321，不能得到的序列是：1423,2413,3124,3142,3412,4123,4132,4213,4231,4312.解析:本題考查了棧的基本入、出棧操作。第三章算法閱讀+算法設(shè)計1.已知棧的基本操作定義如下，請在空白處填寫適當(dāng)內(nèi)容，完成相應(yīng)的功能。答案:（1）s->top==-1（2）s->data[s->top++] （或s->data[++s->top]）（3）s->data[s->top--]解析:已知棧的基本操作定義本題考查棧的基本運(yùn)算指令。2.閱讀下列程序，寫出f31的輸出結(jié)果。答案:catch!解析:本題考查了棧的基本運(yùn)算算法。根據(jù)算法中的操作指令，棧中的元素會發(fā)生改變，最終借助“while”循環(huán)并利用參數(shù)“y”將棧中的元素一一輸出。3.假設(shè)循環(huán)隊(duì)列中只設(shè)rear和quelen來分別指示隊(duì)尾元素的位置和隊(duì)中元素的個數(shù)，試給出判別此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)的入隊(duì)和出隊(duì)算法，要求出隊(duì)時需返回隊(duì)頭元素。答案:解析:本題考查了循環(huán)隊(duì)列基本運(yùn)算的判隊(duì)滿、入隊(duì)與出隊(duì)。第四章單選1.A.AB.BC.CD.D答案:B解析:2.A.AB.BC.CD.D答案:C解析:3.A.AB.BC.CD.D答案:D解析:4.A.AB.BC.CD.D答案:C解析:5.A.AB.BC.CD.D答案:B解析:6.A.AB.BC.CD.D答案:D解析:7.A.AB.BC.CD.D答案:C解析:8.A.AB.BC.CD.D答案:B解析:9.A.AB.BC.CD.D答案:C解析:A.AB.BC.CD.D答案:D解析:11.A.AB.BC.CD.D答案:D解析:本題考查了數(shù)組的順序存儲概念。12.A.AB.BC.CD.D答案:B解析:本題考查了上三角矩陣的壓縮存儲。第四章填空+簡答1.若廣義表A的長度為1，并且head（A）=tail（A），則A=________。答案:（（））解析:本題考查了廣義表的定義和基本運(yùn)算。該廣義表含有一個由空表組成的元素，head（A）=（），tail（A）=（）。2.若廣義表S=（（a，（b）），c，（）），則head（S）=________。答案:（a，（b））解析:本題考查了廣義表的基本運(yùn)算。head（LS）取廣義表LS展開后的第一個子表或元素。3.若廣義表LS=（（），a，（b），c），則head（LS）=________。答案:（）解析:本題考查了廣義表的基本運(yùn)算。head（LS）取廣義表LS展開后的第一個子表或元素，（）是一個空子表。4.______是指相同值的元素或零元素在矩陣中的分布有一定規(guī)律的矩陣。答案:特殊矩陣解析:本題考查了特殊矩陣的概念。5.特殊矩陣和稀疏矩陣哪一種壓縮存儲后會失去隨機(jī)存取的功能？為什么？答案:因?yàn)橄∈杈仃嚨姆橇阍氐姆植际菦]有規(guī)律的，其壓縮存儲是采用三元組表方式。所以稀疏矩陣壓縮后會失去隨機(jī)存取的功能。解析:本題考查了特殊矩陣和稀疏矩陣的概念。6.設(shè)廣義表L=（（），（）），試求head(L)、tail（L）、length（L）和depth（L）。答案:head(L)=（）tail（L）=（（））length（L）=2depth（L）=2解析:本題考查了廣義表的定義。第四章算法閱讀+算法設(shè)計1.答案:解析:見押題精華第四章“稀疏矩陣”。2.答案:3.試寫一個算法，建立順序存儲稀疏矩陣的三元組表。答案:解析:本題考查了稀疏矩陣的三元組表表示方法。假設(shè)A為一個稀疏矩陣，其數(shù)據(jù)存儲在二維數(shù)組a中，b為一個存放對應(yīng)于A矩陣生成的三元組表。在這個算法中，要進(jìn)行二重循環(huán)來判斷每個矩陣元素是否為零，若不為零，則將其行、列下標(biāo)及其值存入b中。4.當(dāng)稀疏矩陣A和B以三元組表作為存儲結(jié)構(gòu)時，試寫出矩陣相加的算法，其結(jié)果存放在三元組表C中。答案:解析:本題考查了稀疏矩陣的算法。矩陣相加就是將兩個矩陣中同一位置的元素值相加。由于兩個稀疏矩陣的非零元素按三元組表形式存放，在建立新的三元組表C時，為了使三元組元素仍按行優(yōu)先排列，所以每次插入的三元組不一定是A的，按照矩陣元素的行列去找A中的三元組，若有，則加入C，同時，這個元素如果在B中也有，則加上B的這個元素值，否則這個值就不變；如果A中沒有，則找B，有則插入C，無則查找下一個矩陣元素。第五章單選1.某樹的結(jié)構(gòu)如下，那么根節(jié)點(diǎn)是（）A.AB.CC.ED.F答案:A解析:本題考查了樹的定義。樹由根節(jié)點(diǎn)開始，由上至下蔓延，一棵樹的根結(jié)點(diǎn)有且只有1個，位于樹的最頂端。2.結(jié)點(diǎn)C的度數(shù)和樹的度數(shù)分別是（）A.1,2B.2,2C.2,3D.3,3答案:C解析:本題考查了樹的基本術(shù)語中度的概念。結(jié)點(diǎn)C的子樹數(shù)為2，所以結(jié)點(diǎn)C的度數(shù)為2；樹中根結(jié)點(diǎn)A的度數(shù)為3，是所有結(jié)點(diǎn)的度數(shù)中最大的，所以樹的度數(shù)為3。3.樹含有的葉子結(jié)點(diǎn)數(shù)量是（）A.0B.1C.3D.4答案:D解析:本題考查了樹的基本術(shù)語中葉子結(jié)點(diǎn)的概念。度數(shù)為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，樹中度數(shù)為0的結(jié)點(diǎn)有B、E、F、G，所以樹的葉子結(jié)點(diǎn)數(shù)量是4。4.結(jié)點(diǎn)F、G的雙親分別是（）A.結(jié)點(diǎn)A、結(jié)點(diǎn)AB.結(jié)點(diǎn)A、結(jié)點(diǎn)CC.結(jié)點(diǎn)C、結(jié)點(diǎn)DD.結(jié)點(diǎn)A、結(jié)點(diǎn)D答案:C解析:本題考查了樹的基本術(shù)語中孩子結(jié)點(diǎn)的概念。結(jié)點(diǎn)F所在的子樹屬于結(jié)點(diǎn)C，所以結(jié)點(diǎn)F的雙親為結(jié)點(diǎn)C，結(jié)點(diǎn)C的孩子為結(jié)點(diǎn)E和結(jié)點(diǎn)F；同理，結(jié)點(diǎn)G的雙親為結(jié)點(diǎn)D，結(jié)點(diǎn)D只有一個孩子，即結(jié)點(diǎn)G。5.樹的深度為（）A.0B.2C.3D.4答案:C解析:本題考查了樹的基本術(shù)語中樹中結(jié)點(diǎn)的層次。樹的層數(shù)即為樹的深度，其中根結(jié)點(diǎn)為第一層，所以樹的深度為3。6.下列關(guān)于二叉樹的說法錯誤的是（）A.二叉樹中的每個結(jié)點(diǎn)至少有兩個孩子B.二叉樹中的每個結(jié)點(diǎn)至多有兩個孩子C.二叉樹的第3層上最多有4個結(jié)點(diǎn)D.深度為3的二叉樹最多有7個結(jié)點(diǎn)答案:A解析:本題考查了二叉樹的定義。二叉樹中的每個結(jié)點(diǎn)至多只能有兩個孩子，故A項(xiàng)錯誤，第1題中的樹并非二叉樹，其余說法均正確。7.現(xiàn)有一棵二叉樹，它的葉子結(jié)點(diǎn)數(shù)為4，度數(shù)為2的結(jié)點(diǎn)數(shù)為Y，則Y的值為（）A.1B.2C.3D.4答案:C解析:8.某二叉樹結(jié)構(gòu)如下，若對其進(jìn)行前序遍歷，則遍歷序列為（）A.ABCDEFB.ABDECFC.DBEACFD.DEBFCA答案:B解析:本題考查了二叉樹遍歷中的前序遍歷。該二叉樹的前序遍歷為ABDECF，詳見押題精華“三種遍歷算法”。9.對其進(jìn)行中序遍歷，則遍歷序列為（）A.ABCDEFB.ABDECFC.DBEACFD.DEBFCA答案:C解析:本題考查了二叉樹遍歷中的中序遍歷。該二叉樹的中序遍歷為DBEACF，詳見押題精華“三種遍歷算法”。10.若對其進(jìn)行后序遍歷，則遍歷序列為（）A.ABCDEFB.ABDECFC.DBEACFD.DEBFCA答案:D解析:本題考查了二叉樹遍歷中的后序遍歷。該二叉樹的后序遍歷為DEBFCA，詳見押題精華“三種遍歷算法”。11.下列關(guān)于哈夫曼樹的說法錯誤的是（）A.同一結(jié)點(diǎn)序列構(gòu)成的二叉樹中，哈夫曼樹的WPL是最小的B.哈夫曼樹中各結(jié)點(diǎn)的度為0或2C.用n個結(jié)點(diǎn)構(gòu)造的哈夫曼樹是唯一的D.樹中兩個權(quán)值最小的結(jié)點(diǎn)可能是兄弟結(jié)點(diǎn)答案:C解析:本題考查了哈夫曼樹的權(quán)值、帶權(quán)路徑長度和構(gòu)造。相同的結(jié)點(diǎn)序列構(gòu)成的哈夫曼樹并不是唯一的；若最小的權(quán)值相同且有3個，那么其中兩個權(quán)值形成的結(jié)點(diǎn)未必是兄弟結(jié)點(diǎn)，所以D項(xiàng)是正確的，只有C項(xiàng)錯誤。12.某哈夫曼樹結(jié)構(gòu)如下，則它的WPL為（）A.8B.10C.12D.14答案:C解析:本題考查了哈夫曼樹的帶權(quán)路徑長度。在該哈夫曼樹中，結(jié)點(diǎn)6的路徑長度為1，結(jié)點(diǎn)1和結(jié)點(diǎn)2的路徑長度均為2，WPL=6*1+1*2+2*2=12。13.結(jié)點(diǎn)1的哈夫曼編碼為（）A.000B.011C.010D.111答案:C解析:本題考查了哈夫曼樹的編碼。哈夫曼編碼的編碼原則為：左子樹為0，右子樹為1。所以結(jié)點(diǎn)1的哈夫曼編碼為010。14.二叉樹的結(jié)構(gòu)如下，對其進(jìn)行前序遍歷，則輸出的遍歷序列為（）A.ABCDEFB.CBDAFEC.CDBFEAD.FEDCBA答案:A解析:本題考查了二叉樹的前序遍歷。見押題精華“三種遍歷算法”。15.二叉樹的結(jié)構(gòu)如下，對其進(jìn)行中序線索化后，結(jié)點(diǎn)F的左指針應(yīng)指向（）A.BB.DC.AD.E答案:C解析:本題考查了二叉樹的線索化。先對其進(jìn)行中序遍歷，得到遍歷序列為CBDAFE，則結(jié)點(diǎn)F的左指針應(yīng)指向左邊的結(jié)點(diǎn)A。16.若構(gòu)造一棵含有n個葉子結(jié)點(diǎn)的哈夫曼樹，則樹中的結(jié)點(diǎn)數(shù)量為（）A.n-1B.n+1C.2n-1D.2n+1答案:C解析:本題考查了哈夫曼樹的構(gòu)造。根據(jù)哈夫曼樹的特點(diǎn)，假設(shè)現(xiàn)有3個葉子結(jié)點(diǎn)，那么這3個葉子結(jié)點(diǎn)可以構(gòu)成一棵含有5個結(jié)點(diǎn)的哈夫曼樹，我們將n=3代入選項(xiàng)，發(fā)現(xiàn)只有C項(xiàng)的結(jié)果是5，所以選擇C項(xiàng)。17.二叉樹的結(jié)構(gòu)如下，對其進(jìn)行前序遍歷，則輸出的遍歷序列為（）A.ABCDEFGB.CBEDAFGC.CEDBGFAD.GFEDCBA答案:A解析:本題考查了二叉樹的前序遍歷。見押題精華“三種遍歷算法”。18.在有n個結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個數(shù)為（）A.2n+1B.2n-1C.n-1D.n+1答案:C解析:本題主要考查了二叉鏈表。對n個結(jié)點(diǎn)的二叉鏈表，共有2n個鏈域（每個結(jié)點(diǎn)有左、右兩個鏈域），除根結(jié)點(diǎn)外，二叉鏈表中每個結(jié)點(diǎn)都有一個從其雙親結(jié)點(diǎn)指向它的指針，也就是說，2n個鏈域中，只有n-1個用來指向結(jié)點(diǎn)的左、右孩子，其余的n+1個鏈域?yàn)榭罩?，所以值為非空的鏈域共有n-1個。19.A.AB.BC.CD.D答案:D解析:本題考查了森林與二叉樹的轉(zhuǎn)換。將森林轉(zhuǎn)換為二叉樹，森林中除第一棵子樹外的其余樹一并構(gòu)成二叉樹的右子樹。第五章填空1.答案:WPL解析:本題考查了哈夫曼樹的帶權(quán)路徑長度。在此類條件下，哈夫曼樹的特性就是WPL最小。2.答案:8解析:3.答案:7解析:4.答案:2解析:5.答案:不變解析:本題考查了二叉樹的前序和后序遍歷。任意畫一棵二叉樹，進(jìn)行兩次遍歷后即可發(fā)現(xiàn)其特點(diǎn)。6.答案:葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)解析:本題考查了樹的基本術(shù)語中葉子結(jié)點(diǎn)的概念。7.對于具有n個結(jié)點(diǎn)的二叉樹，路徑長度最短的是_________；加權(quán)以后，帶權(quán)路徑長度最小的是________樹。答案:完全二叉樹哈夫曼解析:本題考查了二叉樹中的完全二叉樹和哈夫曼樹的概念。8.對一棵二叉線索鏈表結(jié)構(gòu)中所有結(jié)點(diǎn)的空指針域按照某種遍歷次序加線索的過程稱為_______。答案:線索化解析:本題考查了二叉樹的線索化。9.答案:滿二叉樹解析:本題考查了滿二叉樹的概念。第五章解答1.若某電文字符集為{a1、a2、a3、a4、a5}，各字符出現(xiàn)的次數(shù)分別為{8,12,15,24,3}?，F(xiàn)要為該字符集設(shè)計哈夫曼編碼。請回答下列問題：（1）畫出構(gòu)造的哈夫曼樹；（2）給出各字符的哈夫曼編碼；（3）計算電文編碼總長。答案:2.答案:解析:二叉樹結(jié)構(gòu)如下。（此類題目需熟練掌握三種遍歷算法，根據(jù)題目已知信息慢慢推導(dǎo)）3.請寫出下列二叉樹的前序遍歷。答案:AGEBDCF解析:

見“押題精華”二叉樹的三種遍歷算法。4.請將權(quán)值分別是15,30,8,12,10的五個葉子結(jié)點(diǎn)構(gòu)造成一棵哈夫曼樹。答案:5.畫出下圖中所示各二叉樹所對應(yīng)的森林。答案:解析:本題考查了二叉樹到森林的轉(zhuǎn)化。第五章算法閱讀+算法設(shè)計1.答案:（1）returnNULL（2）CopyBin(Bt->lchild)（3）CopyBin(Bt->rchild)2.答案:（1）查找成功

（2）44解析:

本題算法語句含義為：從根結(jié)點(diǎn)開始，若根結(jié)點(diǎn)的關(guān)鍵字與K相同輸出“查找成功”；否則，若大于k值，輸出根結(jié)點(diǎn)的左子樹，小于K值則輸出根結(jié)點(diǎn)的右子樹。3.答案:（1）23,15,19,14（2）按中序查找二叉樹中滿足條件“root->key>=left&&root->key<right”的結(jié)點(diǎn)，并按中序遍歷二叉樹的次序依次輸出。（大意相同即可）解析:該題中的編程，功能是查找大于或等于14并且小于30的結(jié)點(diǎn)，并輸出。要注意，等于14可以輸出，但是等于30不可輸出，所以第（1）問中的答案中有結(jié)點(diǎn)14，但不應(yīng)該有結(jié)點(diǎn)30。4.答案:ABCCBA解析:此類題目中含有另一個子函數(shù)f31，所以在分析和執(zhí)行算法時一定要注意執(zhí)行步驟。解題思路：本題中，我們可人為的將核心算法分為三步（再次調(diào)用子函數(shù)f31的語句視為第二步）。第一個輸入是根結(jié)點(diǎn)A，當(dāng)執(zhí)行到第二步時，算法暫停，先去執(zhí)行另一個f31函數(shù)，將根結(jié)點(diǎn)A的左子樹B作為根結(jié)點(diǎn)（第二個輸入）代入執(zhí)行f31。結(jié)點(diǎn)B執(zhí)行到第二步時，算法暫停，先去執(zhí)行另一個f31函數(shù)，將根結(jié)點(diǎn)B的左子樹C作為根結(jié)點(diǎn)（第三個輸入）代入執(zhí)行f31。最終結(jié)點(diǎn)C的算法全部執(zhí)行完畢，結(jié)點(diǎn)B的f31函數(shù)繼續(xù)執(zhí)行，結(jié)束后執(zhí)行結(jié)點(diǎn)A的f31函數(shù)。以上是算法的執(zhí)行順序，根據(jù)該執(zhí)行順序和題干中的語句，我們可得到輸出結(jié)果ABCCBA。5.答案:（1）T=NULL（2）NewT（3）f33(T->rchild)（4）f33(T->lchild)（5）NewT6.答案:7.答案:解析:本題考查了二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)。因?yàn)檎{(diào)用函數(shù)只能進(jìn)行值傳遞，當(dāng)返回類型為void時，就必須把實(shí)際參數(shù)的地址傳給函數(shù)，否則函數(shù)不會對實(shí)際參數(shù)進(jìn)行任何操作，也就得不到所需結(jié)果了。所以，newroot要說明為BinTree型指針。8.以二叉鏈表為存儲結(jié)構(gòu)，分別寫出在二叉樹中查找值為x的結(jié)點(diǎn)及求x所在結(jié)點(diǎn)在樹中層數(shù)的算法。答案:解析:本題考查了二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)的運(yùn)算。第六章單選1.下列屬于非線性的數(shù)據(jù)結(jié)構(gòu)是（）A.線性表B.棧C.隊(duì)列D.圖答案:D解析:本題考查了圖的定義。圖和二叉樹均屬于非線性結(jié)構(gòu)。2.在有向圖中，每條邊都是有方向的，這種邊也被稱為（）A.長B.度C.路徑D.弧答案:D解析:本題考查了有向圖的概念。只有在有向圖，邊才有方向，這種邊也被稱為弧。3.在有向圖中，兩個頂點(diǎn)之間可以最多擁有的邊數(shù)是（）A.1條B.2條C.3條D.4條答案:B解析:本題考查了有向圖的概念。在有向圖中，每個頂點(diǎn)最多有兩條邊，一條為出邊，一條為入邊。4.在有向圖中，一個頂點(diǎn)的度數(shù)最大可為（）A.2B.3C.4D.5答案:C解析:本題考查了有向圖的度。在有向圖中，兩個頂點(diǎn)間最多存在兩條邊，所以一個頂點(diǎn)最多可以有兩條出邊和兩條入邊，即最大的度數(shù)為4。5.若在某有向圖中共有三個頂點(diǎn)，它們的度數(shù)分別為2,3,3，那么該圖中的總邊數(shù)為（）A.1條B.2條C.3條D.4條答案:D解析:本題考查了圖的頂點(diǎn)、邊數(shù)和度數(shù)之間的關(guān)系。無論是有向圖還是無向圖，圖的總邊數(shù)是總度數(shù)的一半，即為（2+3+3）/2=4條。6.在有三個頂點(diǎn)的有向完全圖中，它的總邊數(shù)為（）A.0B.2C.4D.6答案:D解析:7.用鄰接矩陣表示有n個頂點(diǎn)和e條邊的無向圖，并采用壓縮方式存儲，那么矩陣中的零元素數(shù)量為（）A.n(n+1)/2-eB.n(n+1)/2-2eC.n*n-eD.n*n-2e答案:A解析:本題考查了無向圖的鄰接矩陣的壓縮存儲。這種題目只能通過“先假設(shè)再代入”的方式解決，我們假設(shè)無向圖中有3個頂點(diǎn)兩條邊（即n=3,e=2），轉(zhuǎn)換為鄰接矩陣后有5個零元素，但是經(jīng)過壓縮存儲后只有4個零元素了。我們將n=3，e=2，代入各個選項(xiàng)中，發(fā)現(xiàn)只有A項(xiàng)的結(jié)果為4，所以選擇A項(xiàng)。8.若無向圖中所有頂點(diǎn)的度數(shù)和為16，那么無向圖的邊數(shù)和為（）A.2B.4C.6D.8答案:D解析:本題考查了圖的頂點(diǎn)、邊數(shù)和度數(shù)之間的關(guān)系。無論是有向圖還有無向圖，它們的邊數(shù)和是所有頂點(diǎn)的度數(shù)和的一半。9.現(xiàn)有一個有向圖，令頂點(diǎn)代表編號，那么它的鄰接矩陣為（）A.AB.BC.CD.D答案:C解析:本題考查了圖的鄰接矩陣表示法。與無向圖中構(gòu)造原則一致。不過在有向圖中，只統(tǒng)計出邊。頂點(diǎn)0分別指向頂點(diǎn)1和頂點(diǎn)2，所以矩陣中第0行第1列和第0行第2列的位置為“1”，其余列為“0”，由此類推，可構(gòu)造出該有向圖的鄰接矩陣。A.1256374B.1325674C.1365247D.1374526答案:B解析:本題考查了圖的深度優(yōu)先搜索遍歷。在深度優(yōu)先搜索遍歷中，先任意選定一個頂點(diǎn)開始訪問，然后每次都隨機(jī)訪問它的一個鄰近頂點(diǎn)，對于其他的頂點(diǎn)也是如此；若沒有鄰近頂點(diǎn)，則任意選擇一個未被訪問的頂點(diǎn)開始遍歷。在B項(xiàng)中，頂點(diǎn)3的鄰近頂點(diǎn)不是頂點(diǎn)2，所以不能直接由3到2。A.1324B.1423C.1432D.2341答案:A解析:本題考查了圖的廣度優(yōu)先搜索遍歷。可先將圖按樹的深度進(jìn)行分層，樹的根結(jié)點(diǎn)任意。由ABC選項(xiàng)可知，選擇的根結(jié)點(diǎn)為頂點(diǎn)1，分層原則為按照頂點(diǎn)的鄰近關(guān)系進(jìn)行分層，第一層必定為頂點(diǎn)1，它的鄰近頂點(diǎn)分別為3和2，所以頂點(diǎn)3和2位第二層，頂點(diǎn)4為第三層，如圖示。按照廣度優(yōu)先搜索遍歷的訪問原則，只有A項(xiàng)正確。12.A.AB.BC.CD.D答案:C解析:13.A.1,2,1,2B.2,2,1,1C.3,4,2,3D.4,4,2,2答案:C解析:本題考查了圖的鄰接矩陣表示法。因?yàn)猷徑泳仃嚥皇且粋€對稱的矩陣，所以這肯定是一個有向圖的鄰接矩陣。根據(jù)有向圖的鄰接矩陣生成原則，矩陣中只統(tǒng)計每個頂點(diǎn)的出邊，但是有向圖中頂點(diǎn)的邊數(shù)為出邊加上入邊的量，所以應(yīng)選擇C。若對下圖進(jìn)行深度優(yōu)先遍歷，則不可能得到的遍歷序列為（）A.AEDCFBB.ABEDCFC.AEFCBDD.ABCEFD答案:D解析:本題考查了深度優(yōu)先遍歷。頂點(diǎn)B和頂點(diǎn)C不相鄰，所以錯誤。若對下圖進(jìn)行廣度優(yōu)先遍歷，則不可能得到的遍歷序列為（）A.ABCEFDB.ACBEFDC.ACEBDFD.AEBCFD答案:C解析:本題考查了廣度優(yōu)先遍歷。第二層的訪問順序?yàn)镃EB，所以第三層的訪問順序必定是FD，而不是DF。16.下列說法不正確的是（）A.生成樹是連通圖的極小連通子圖B.任何連通圖的連通分量只有一個C.連通分量是無向圖中的極小連通子圖D.非連通圖至少有一個以上的連通分量答案:C解析:本題考查了連通圖。無向圖的極大連通子圖稱為連通分量；任何連通圖的連通分量只有一個，即自身；非連通的無向圖有多個連通分量；生成圖是連通圖的極小連通子圖。17.無向圖的鄰接矩陣是一個（）A.零矩陣B.對稱矩陣C.對角矩陣D.上三角矩陣答案:B解析:本題考查了圖的鄰接矩陣。無向圖的鄰接矩陣是一個對稱矩陣。18.下列說法中不正確的是（）A.圖的深度優(yōu)先搜索的方法不適用有向圖B.圖的遍歷過程中每一頂點(diǎn)僅被訪問一次C.圖的深度優(yōu)先搜索是一個遞歸過程D.遍歷圖的基本方法有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種答案:A解析:本題考查了圖的遍歷。圖的遍歷方法有兩種，深度優(yōu)先搜索和廣度優(yōu)先搜索。兩種遍歷方法，對有向圖和無向圖都適用。第六章填空+解答1.答案:無向圖解析:本題考查了無向圖的鄰接矩陣。無向圖的鄰接矩陣一定是對稱的。2.在無向圖的鄰接矩陣中，A[2][3]=0，則A[3][2]=________。答案:0解析:本題考查了無向圖的鄰接矩陣。無向圖的鄰接矩陣是一個關(guān)于主對角線對稱的矩陣，所以A[3][2]=A[2][3]=0。3.一個連通圖的子圖，如果是一棵包含了該連通圖所有的頂點(diǎn)的樹，則該子圖稱為連通圖的_________。答案:生成樹解析:本題考查了生成樹的概念。一個連通圖的一個子圖，如果是一棵包含該連通圖的所有頂點(diǎn)的樹，則該子圖稱為連通圖的生成樹。4.答案:3解析:本題考查了圖的頂點(diǎn)、邊數(shù)和度數(shù)之間的關(guān)系。無論是有向圖還是無向圖，圖的總度數(shù)是總邊數(shù)的2倍。5.答案:有向無環(huán)圖解析:本題考查了頂點(diǎn)活動網(wǎng)的概念。有向且無環(huán)的圖才存在拓?fù)浣Y(jié)構(gòu)。6.一個無向連通圖的生成樹是含有該連通圖的全部頂點(diǎn)的________子圖。答案:極小連通解析:本題考查了生成樹的概念。一個無向連通圖的生成樹是含有該連通圖的全部頂點(diǎn)的極小連通子圖。7.一個帶權(quán)的無向連通圖的最小生成樹有_________。答案:一顆或多顆解析:本題考查了最小生成樹。由于一個網(wǎng)（帶權(quán)圖）中會有權(quán)值相同的邊，所以從不同的頂點(diǎn)出發(fā)，可以得到不同的最小生成樹。8.設(shè)圖G有n個頂點(diǎn)和e條邊，進(jìn)行深度優(yōu)先搜索的時間復(fù)雜度至多為_________，進(jìn)行廣度優(yōu)先搜索的時間復(fù)雜度至多為________。答案:解析:9.已知一個有向圖G的鄰接矩陣表示，計算第i個結(jié)點(diǎn)的入度的方法是________。答案:求矩陣第i列非零元素之和解析:本題考查了有向圖的鄰接矩陣。計算第i個結(jié)點(diǎn)的入度的方法是求矩陣第i列非零元素之和。10.普里姆算法的時間復(fù)雜度是_________，與網(wǎng)中__________無關(guān)。答案:解析:11.對于一個具有n個頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為________，所有鄰接表中的結(jié)點(diǎn)總數(shù)是___________。答案:n，2n解析:本題考查了無向圖的鄰接表表示法。表頭向量的大小為n，所有鄰接表中的結(jié)點(diǎn)總數(shù)是2n。12.答案:13.答案:解析:構(gòu)造原則是，先選擇圖中最小權(quán)的邊，然后從該邊連接的所有頂點(diǎn)開始，找出頂點(diǎn)鄰近的最小權(quán)的邊；接著一直重復(fù)下去，直到所有頂點(diǎn)連通。注意，不可形成回路。14.答案:15.請給出下圖中的一棵最小生成樹。答案:16.答案:（1）是

（2）A，B，E，D，G，C，F(xiàn) （另一種序列：A，B，E，D，C，G，F(xiàn)）解析:（1）圖中無“回路”，所以是有向無環(huán)圖。（2）拓?fù)浣Y(jié)構(gòu)排序的原則是，每次都從圖中選出一個無入邊的頂點(diǎn)，輸出并從圖中刪除，然后重復(fù)。該題共有兩種拓?fù)浣Y(jié)構(gòu)排序，寫出一種即可。第六章算法設(shè)計題1.試在無向圖的鄰接矩陣和鄰接表上實(shí)現(xiàn)如下算法：（1）往圖中插入一個頂點(diǎn)。（2）往圖中插入一條邊。（3）刪去圖中某頂點(diǎn)。（4）刪去圖中某條邊。答案:第七章單選+填空1.A.AB.BC.CD.D答案:D解析:2.A.AB.BC.CD.D答案:B解析:3.A.AB.BC.CD.D答案:D解析:4.已知關(guān)鍵字序列為{65,8,32,18,25,15,12,4}，該關(guān)鍵字序列經(jīng)過升序冒泡排序后，第一趟的輸出序列為（）A.4,8,12,15,18,25,32,65B.65,32,25,18,15,12,8,4C.4,65,8,32,18,25,15,12D.65,32,8,25,18,15,12,4答案:C解析:本題考查了冒泡排序。將關(guān)鍵字進(jìn)行兩兩對比，并判斷是否應(yīng)交換位置。5.A.AB.BC.CD.D答案:A解析:6.關(guān)鍵字序列{21,7,54,32,11}構(gòu)成的大根堆序列為（）A.54,32,21,11,7B.32,54,21,7,11C.54,32,21,7,11D.32,54,11,21,7答案:C解析:本題考查了堆排序中大根堆的構(gòu)造。根據(jù)大根堆的構(gòu)造原則，檢查結(jié)點(diǎn)是否滿足大根堆條件。7.對關(guān)鍵字序列{12,8,54,18,36}進(jìn)行升序的歸并排序，第二趟的排序結(jié)果為（）A.8,12,36,18,54B.8,12,18,54,36C.8,12,18,36,54D.、8,12,18,54,36答案:D解析:本題考查了歸并排序。第一趟的排序結(jié)果為8,12,18,54,36，兩兩成組排序后，第二趟的結(jié)果不變。8.若待排序的關(guān)鍵字已基本有序，這種情況下，下列排序法花費(fèi)的時間反而會增加的是（）A.快速排序B.冒泡排序C.希爾排序D.插入排序答案:A解析:本題考查了排序的時間復(fù)雜度。當(dāng)待排序的關(guān)鍵字有序或基本有序時，使用快速排序反而效率降低，其時間復(fù)雜度增大，使快速排序變?yōu)槊芭菖判?。效率最高的排序是直接插入排序?.每一趟都可以將元素放在確定的最終位置上的排序法是（）A.直接選擇排序B.希爾排序C.插入排序D.歸并排序答案:A解析:本題考查了直接選擇排序。直接選擇排序每次都可以選出一個最小的元素，將其放在序列最前端。10.以下排序方法中，時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，而且恒為的方法是（）A.冒泡排序B.直接選擇排序C.堆排序D.快速排序答案:B解析:11.下列排序方法中，記錄關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的方法是（）A.希爾排序B.直接插入排序C.直接選擇排序D.冒泡排序答案:C解析:本題考查了直接選擇排序。直接選擇排序無論待排序記錄的初始狀態(tài)如何，每次選擇需要作