數(shù)據(jù)結(jié)構(gòu)題集答案

數(shù)據(jù)結(jié)構(gòu)題集答案數(shù)據(jù)結(jié)構(gòu)題集答案數(shù)據(jù)結(jié)構(gòu)題集答案數(shù)據(jù)結(jié)構(gòu)題集答案編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:數(shù)據(jù)結(jié)構(gòu)題集第一章緒論一、單選題1.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成【C】。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2.數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指【A】。A.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) B.數(shù)據(jù)結(jié)構(gòu)C.數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)D.數(shù)據(jù)元素之間的關(guān)系3.【A】是數(shù)據(jù)的最小單位，【B】是數(shù)據(jù)的基本單位。A.數(shù)據(jù)項(xiàng) B.數(shù)據(jù)元素C.信息項(xiàng)D.表元素4.計(jì)算機(jī)所處理數(shù)據(jù)一般具有某種內(nèi)在聯(lián)系，這是指【B】。A.數(shù)據(jù)與數(shù)據(jù)之間存在某種關(guān)系B.數(shù)據(jù)元素與數(shù)據(jù)元素之間存在某種關(guān)系C.元素內(nèi)部存在某種結(jié)構(gòu)D.數(shù)據(jù)項(xiàng)與數(shù)據(jù)項(xiàng)之間存在某種關(guān)系5.算法分析的目的是【C】。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性6.在存儲(chǔ)數(shù)據(jù)時(shí)，不僅要考慮存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)【C】。A.數(shù)據(jù)處理的方法B.數(shù)據(jù)元素的類(lèi)型C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲(chǔ)方法7.算法分析的主要任務(wù)是分析【D】。A.算法是否具有較好的可讀性B.算法中是否存儲(chǔ)語(yǔ)法錯(cuò)誤和邏輯錯(cuò)誤C.算法的功能是否符合設(shè)計(jì)要求D.算法的執(zhí)行時(shí)間與問(wèn)題規(guī)模之間的關(guān)系。8.數(shù)據(jù)的運(yùn)算【A】。A.效率與采用何種存儲(chǔ)結(jié)構(gòu)有關(guān)B.是根據(jù)存儲(chǔ)結(jié)構(gòu)來(lái)定義的C.有算術(shù)運(yùn)算和關(guān)系運(yùn)算兩大類(lèi)D.必須用程序設(shè)計(jì)語(yǔ)言來(lái)描述9.算法的計(jì)算量的大小稱(chēng)為算法的【B】。A.效率B.時(shí)間復(fù)雜度C.現(xiàn)實(shí)性D.難度10.連續(xù)存儲(chǔ)分配時(shí)，存儲(chǔ)單元的地址【A】。A.一定連續(xù)B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù)，部分不連續(xù)二、判斷題1.數(shù)據(jù)元素是數(shù)據(jù)結(jié)構(gòu)的最小單位【.×】。2.數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)系，它依賴(lài)于計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)【×.】。3.數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)元素的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系【×.】。4.算法的優(yōu)劣與算法的描述語(yǔ)言無(wú)關(guān)，但與使用的計(jì)算機(jī)有關(guān)【.×】。5.數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)【.×】。三、填空題1.數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)元素之間的邏輯關(guān)系。2.一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱(chēng)為存儲(chǔ)結(jié)構(gòu)。3.數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序存儲(chǔ)結(jié)構(gòu)的表示和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的表示。4.數(shù)據(jù)邏輯結(jié)構(gòu)包括集合、線性結(jié)構(gòu)、樹(shù)和圖四種，樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)統(tǒng)稱(chēng)為非線性結(jié)構(gòu)。5.順序存儲(chǔ)方法把邏輯上邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里；鏈?zhǔn)酱鎯?chǔ)方法中結(jié)點(diǎn)間的邏輯關(guān)系是由指針域表示的。6、數(shù)據(jù)結(jié)構(gòu)研究的是邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對(duì)于這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法。7.算法的執(zhí)行時(shí)間是問(wèn)題規(guī)模n的函數(shù)。8.以下是4個(gè)算法所有語(yǔ)句頻度之和的表達(dá)式，其中的復(fù)雜度相同的是A和B。(n)=2n3+3n2+1000(n)=n3-n2log2n-1000(n)=n2log2n+n2(n)=n2+1000四、解答題1.簡(jiǎn)述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的關(guān)系。答：在數(shù)據(jù)結(jié)構(gòu)中，邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是密切相關(guān)的，存儲(chǔ)結(jié)構(gòu)不僅將數(shù)據(jù)元素存儲(chǔ)到計(jì)算機(jī)中，而且還要表示各數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)與計(jì)算機(jī)無(wú)關(guān)，存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中的表示。通常情況下，一種邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，例如，線性結(jié)構(gòu)可以采取順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱娲纸Y(jié)構(gòu)表示。2.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類(lèi)型有什么區(qū)別答：數(shù)據(jù)結(jié)構(gòu)是相互間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，一般包括三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和多數(shù)據(jù)的運(yùn)算。數(shù)據(jù)類(lèi)型是一個(gè)值得集合和定義在這個(gè)值集上的一組操作的總稱(chēng)。數(shù)據(jù)結(jié)構(gòu)重點(diǎn)考慮元素之間的關(guān)系，數(shù)據(jù)類(lèi)型重點(diǎn)考慮數(shù)據(jù)的個(gè)體特征。3.當(dāng)為解決某一問(wèn)題已經(jīng)選定其數(shù)據(jù)的邏輯結(jié)構(gòu)后，選擇數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)時(shí)，應(yīng)從哪些方面考慮答：通常從兩個(gè)方面考慮：第一是算法實(shí)現(xiàn)的存儲(chǔ)空間復(fù)雜度；第二是算法執(zhí)行的時(shí)間復(fù)雜度。若存儲(chǔ)空間難以確定，宜選擇鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，否則選擇順序存儲(chǔ)結(jié)構(gòu)。若插入、刪除操作頻繁，則選鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，否則選擇順序存儲(chǔ)結(jié)構(gòu)。

第二章線性表一、單選題1.鏈表不具備的特點(diǎn)是【A】。A.可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B.插入刪除不需要移動(dòng)元素C.不必事先估算存儲(chǔ)空間D.所需空間與其長(zhǎng)度成正比2.設(shè)線性表有n個(gè)元素，以下操作中，【A】在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。A.輸出第i（1≤i≤n）個(gè)元素的值B.順序輸出這n個(gè)元素C.交換第1個(gè)與第2個(gè)元素的值D.輸出與給定值x相等的元素在線性表中的序號(hào)3.如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用【D】存儲(chǔ)方法最節(jié)省時(shí)間。A.單鏈表B.雙鏈表C.線性鏈表D.順序表4.線性表是具有n個(gè)【C】的有限序列（n≥0）。A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)5.下面關(guān)于線性表的敘述中，錯(cuò)誤的是【B】。A.線性表采用順序存儲(chǔ)，則必須占用一片連續(xù)的存儲(chǔ)單元B.線性表采用順序存儲(chǔ)，則便于插入和刪除操作C.線性表采用鏈?zhǔn)酱鎯?chǔ)，則不必占用一片連續(xù)的存儲(chǔ)單元D.線性表采用鏈?zhǔn)酱鎯?chǔ)，則便于插入和刪除操作6.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種【A】。A.隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B.順序存取的存儲(chǔ)結(jié)構(gòu)C.索引存取的存儲(chǔ)結(jié)構(gòu)存取的存儲(chǔ)結(jié)構(gòu)7.單鏈表中增加一個(gè)頭結(jié)點(diǎn)的目的是為了【C】。A.使單鏈表至少有一個(gè)結(jié)點(diǎn)B.標(biāo)識(shí)表首結(jié)點(diǎn)的位置C.方便運(yùn)算的實(shí)現(xiàn)D.說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)8.不帶頭結(jié)點(diǎn)的單鏈表（頭指針為h）為空的條件是【A】。==NULL>next==NULL>next==h!=NULL9.帶頭結(jié)點(diǎn)的單鏈表（頭指針為h）為空的條件是【B】。==NULL>next==NULL>next==h!=NULL10.帶頭結(jié)點(diǎn)的循環(huán)雙向鏈表（頭指針為L(zhǎng)）為空的條件是【D】。==NULL>next->prior==NULL>prior==NULL>next==L11.非空的循環(huán)單鏈表（頭指針為head）的尾結(jié)點(diǎn)（由p指向）滿足【C】。>next==NULL==NULL>next==head==head12.設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用【A】最節(jié)省時(shí)間。A.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.單鏈表13.若某線性表最常用的操作存取任意指定序號(hào)的元素和在表尾進(jìn)行插入和刪除，則選用【A】的存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表14.在n個(gè)結(jié)點(diǎn)的線性表的順序?qū)崿F(xiàn)中，算法的時(shí)間復(fù)雜度為O(1)的操作是【A】。A.訪問(wèn)第i個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)B.在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C.刪除第i個(gè)結(jié)點(diǎn)D.以上都不對(duì)15.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為【C】。(0)(1)(n)(n2)16.對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為【C】。(n)O(n)(n)O(1)(1)O(n)(1)O(1)17.線性表以鏈?zhǔn)椒绞酱鎯?chǔ)，訪問(wèn)第i個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為【C】。(i)(1)(n)(i-1)18.循環(huán)鏈表H尾結(jié)點(diǎn)p的特點(diǎn)是【A】。>next==H>next==H->next==H==H->next二、判斷題【×】1.取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān)?！尽痢?.線性表中每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼?！尽痢?.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)?！尽痢?.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以不連續(xù)。【×】5.在一個(gè)設(shè)有頭指針和尾指針的單鏈表中，執(zhí)行刪除單鏈表最后一個(gè)結(jié)點(diǎn)的操作與鏈表的長(zhǎng)度無(wú)關(guān)。三、填空題1.向一個(gè)長(zhǎng)度為n的順序表中的第i個(gè)元素之前插入一個(gè)元素時(shí)，需要向后移動(dòng)n-i+1個(gè)元素。2.在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素時(shí)，需要向前移動(dòng)n-i個(gè)元素。3.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是簡(jiǎn)化插入、刪除算法。4.在單鏈中要?jiǎng)h除某一指定結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。5.訪問(wèn)單鏈表中的結(jié)點(diǎn)，必須沿著指針域依次進(jìn)行。6.在雙鏈表中每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向直接前驅(qū)結(jié)點(diǎn)，一個(gè)指向直接后繼結(jié)點(diǎn)。7.在雙向循環(huán)鏈表中，刪除最后一個(gè)結(jié)點(diǎn)的算法時(shí)間復(fù)雜度為O(1)。8.訪問(wèn)一個(gè)線性表中具有給定值的時(shí)間復(fù)雜度的數(shù)量級(jí)是O(n)。9.由n個(gè)數(shù)據(jù)元素生成一個(gè)順序表，若每次都調(diào)用插入算法把一個(gè)元素插入到表頭，則整個(gè)算法的時(shí)間復(fù)雜度為O(n)，若每次都調(diào)用插入算法把一個(gè)元素插入到表尾，則整個(gè)算法的時(shí)間復(fù)雜度為O(n2)。10.在雙向鏈表中，可以用表尾指針代替表頭指針。11.根據(jù)n個(gè)數(shù)據(jù)元素建立對(duì)應(yīng)的順序表和單鏈表存儲(chǔ)結(jié)構(gòu)，其算法的時(shí)間復(fù)雜度最好的情況是O(n)，最壞的情況是O(n2)。12.求線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的長(zhǎng)度的算法時(shí)間復(fù)雜度分別是O(1)和O(n)。13.在一個(gè)帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過(guò)程是否相同相同。14.在一個(gè)不帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過(guò)程是否相同不相同。四、簡(jiǎn)答題1.闡述順序表和鏈表存儲(chǔ)方式的特點(diǎn)。答：順序表存儲(chǔ)方式為數(shù)據(jù)分配連續(xù)的存儲(chǔ)單元，數(shù)據(jù)元素按邏輯順序依次存儲(chǔ)到相應(yīng)存儲(chǔ)單元中，使得邏輯相鄰的數(shù)據(jù)元素物理也相鄰，因此可以實(shí)現(xiàn)隨機(jī)訪問(wèn)線性表的數(shù)據(jù)元素，即數(shù)據(jù)訪問(wèn)的時(shí)間復(fù)雜度為O(1)。鏈表存儲(chǔ)方式分配的存儲(chǔ)單元可以不連續(xù)，通過(guò)每個(gè)結(jié)點(diǎn)的指針域來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，只能順序訪問(wèn)線性表中的數(shù)據(jù)元素。2.若頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，則該線性表宜采用何種存儲(chǔ)結(jié)構(gòu)，為什么答：若頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，則該線性表宜采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)在插入和刪除數(shù)據(jù)元素時(shí)不需要移動(dòng)數(shù)據(jù)元素，只需要修改結(jié)點(diǎn)的指針域就可以改變數(shù)據(jù)元素之間的邏輯關(guān)系。3.在單鏈表、雙向循環(huán)鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)p從相應(yīng)的鏈表中刪除若可以，時(shí)間復(fù)雜度各為多少。答：要實(shí)現(xiàn)刪除p結(jié)點(diǎn)的操作，必須找到其前驅(qū)結(jié)點(diǎn)，修改其指針域的值使其指向p的后繼結(jié)點(diǎn)，以實(shí)現(xiàn)刪除結(jié)點(diǎn)p。單鏈表不行，因?yàn)椴恢李^指針就無(wú)法找到結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)。雙向循環(huán)鏈表和單循環(huán)鏈表可以可以實(shí)現(xiàn)刪除p結(jié)點(diǎn)。單循環(huán)鏈表刪除p結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)，雙循環(huán)鏈表刪除P結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)。4.對(duì)鏈表設(shè)置頭結(jié)點(diǎn)的作用是什么答：對(duì)帶頭結(jié)點(diǎn)的鏈表，在表的任何結(jié)點(diǎn)之前插入結(jié)點(diǎn)或刪除任何位置的結(jié)點(diǎn)，所要做的都是修改前一個(gè)結(jié)點(diǎn)的指針域，因?yàn)樵趲ь^結(jié)點(diǎn)的鏈表中任何元素結(jié)點(diǎn)都有前驅(qū)結(jié)點(diǎn)。如果沒(méi)有頭結(jié)點(diǎn)，在首元結(jié)點(diǎn)前插入結(jié)點(diǎn)或刪除首元結(jié)點(diǎn)都要修改頭指針，其算法要比帶頭結(jié)點(diǎn)的算法復(fù)雜些。其次，帶頭結(jié)點(diǎn)的鏈表結(jié)構(gòu)，初始化后的頭指針就固定了，除撤銷(xiāo)算法外，所有算法都不會(huì)修改頭指針，可以減少出錯(cuò)的可能性。五、算法設(shè)計(jì)題1.已知一個(gè)線性表用含頭結(jié)點(diǎn)的單鏈表做存儲(chǔ)結(jié)構(gòu)，寫(xiě)一個(gè)算法求單鏈表的長(zhǎng)度。解：算法基本思想：從頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開(kāi)發(fā)，遍歷單鏈表的每個(gè)結(jié)點(diǎn)，每遇到一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)計(jì)算器加1。intlistlenght(linklistL){intlength=0;P=L->next;while(p){length++;p=p->next;}return(length);}2.已知一個(gè)順序表L，其中的元素按值遞增有序排列，設(shè)計(jì)一個(gè)算法插入一個(gè)值為x的元素后保持該順序表仍然遞增有序，且空間復(fù)雜度為0（1）。voidinsertsq(sqlistL,elemtypex){n=;while(n>=0&<(x,[n]){[n+1]=[n];n--;}[n+1]=x;}++;return;}3.寫(xiě)一個(gè)算法，從順序表中刪除值為x的所有元素。voiddelallsq(Sqlist&L){inti=0,j=0;while(j<{if[j]!=x)[i++]=[j];j++;}=i;}

第三章棧和隊(duì)列一、單選題1.對(duì)于棧操作數(shù)據(jù)的原則是【C】。A.先進(jìn)先出B.后進(jìn)后出C.后進(jìn)先出D.不分順序2.隊(duì)列的先進(jìn)先出特征是指【A】。A.最后插入隊(duì)列的元素總是最后被刪除B.當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先C.每當(dāng)有刪除操作時(shí)，總要先做一次插入操作D.每次從隊(duì)中刪除的元素總是最早插入的元素3.與順序棧相比較，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是【A】。A.通常不會(huì)出現(xiàn)棧滿的情況B.插入操作更容易實(shí)現(xiàn)C.通常不會(huì)出現(xiàn)?？盏那闆rD.刪除操作更容易實(shí)現(xiàn)4.棧和隊(duì)列的共同點(diǎn)是【C】。A.都是先進(jìn)先出B.都是后進(jìn)后出C.只允許在端點(diǎn)處進(jìn)行插入和刪除D.無(wú)共同點(diǎn)5.棧的特點(diǎn)是【①B】，隊(duì)列的特點(diǎn)是【②A】；棧和隊(duì)列都是【③C】若入棧序列是1，2，3，4，則【④A】是不可能的出棧序列；若進(jìn)隊(duì)列的序列是1，2，3，4，則【⑤D】是可能的出隊(duì)序列。①②A.先進(jìn)先出B.后進(jìn)先出C.進(jìn)優(yōu)先于出D.出優(yōu)先于進(jìn)③A.順序存儲(chǔ)的線性結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)C.限制存取點(diǎn)的線性結(jié)構(gòu)D.限制存取點(diǎn)的非線性結(jié)構(gòu)④⑤,2,1,4,2,4,1,2,3,1,2,3,46.用單鏈表表示的鏈隊(duì)列的隊(duì)頭在鏈表的【A】。A.鏈頭B.鏈尾C.鏈中D.都不是7.設(shè)入棧序列為1,2,3,4,5,則可能得到的出棧序列為【C】。,2,5,3,4,1,2,5,4,2,5,4,1,4,2,3,58.輸入序列是ABC，若輸出序列變?yōu)镃BA，經(jīng)過(guò)的棧操作為【B】。,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop9.棧在【D】應(yīng)用。A.遞歸調(diào)用B.函數(shù)調(diào)用C.表達(dá)式求值,B,C10.設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)的算法，采用【D】數(shù)據(jù)結(jié)構(gòu)最佳。A.線性表的順序存儲(chǔ)結(jié)構(gòu)B.隊(duì)列C.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.棧11.允許對(duì)隊(duì)列進(jìn)行的操作有【D】。A.對(duì)隊(duì)列中的元素排序B.取出最近進(jìn)隊(duì)的元素C.在隊(duì)頭之前插入元素D.刪除隊(duì)頭元素12.對(duì)于循環(huán)隊(duì)列【D】。A.無(wú)法判斷隊(duì)列是否為空B.無(wú)法判斷隊(duì)列是否為滿C.隊(duì)列不可能滿D.以上說(shuō)法都不對(duì)13.隊(duì)列存放在A[0..M-1]中，則入隊(duì)時(shí)的操作為【B】。=rear+1=(rear+1)%M=(rear+1)%(M+1)=(rear+1)%(M-1)14.隊(duì)列存放在A[0..M-1]中，則出隊(duì)時(shí)的操作為【B】。=front+1B.front=(front+1)%MC.front=(front+1)%(M+1)D.front=(front+1)%(M-1)15.循環(huán)隊(duì)列的最大容量為M，則隊(duì)空的條件是【A】。==frontB.(rear+1)%M==front+1==frontD.(rear-1)%M==front16.循環(huán)隊(duì)列的最大容量為M，則隊(duì)滿的條件是【B】。==frontB.(rear+1)%M==front+1==frontD.(rear-1)%M==front二、判斷題【×】1.隊(duì)列在函數(shù)調(diào)用時(shí)必不可少，因此遞歸離不開(kāi)隊(duì)列?！尽獭?.棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞健！尽獭?.設(shè)尾指針的循環(huán)鏈表表示隊(duì)列，則入隊(duì)和出隊(duì)算法的時(shí)間復(fù)雜度為0(1)?！尽痢?.隊(duì)列邏輯上是一個(gè)上端和下端既能增加又能減少的線性表?！尽獭?.在鏈隊(duì)列中，即使不設(shè)置尾指針也能進(jìn)行入隊(duì)操作?！尽獭?.棧和隊(duì)列度是限制存取點(diǎn)的線性結(jié)構(gòu)?！尽痢?.即使對(duì)不含相同元素的同一輸入序列進(jìn)行兩組不同的合法的入棧和出棧操作，所得的輸出序列一定相同。【√】8.棧是實(shí)現(xiàn)函數(shù)調(diào)用所必需的數(shù)據(jù)結(jié)構(gòu)。【√】9.順序隊(duì)列中的元素個(gè)數(shù)，可以根據(jù)隊(duì)首指針和隊(duì)尾指針的值計(jì)算出來(lái)。三、填空題1.循環(huán)隊(duì)列的引入，目的是為了克服順序隊(duì)列的假溢出。2.區(qū)分循環(huán)隊(duì)列的空與滿有3種方法，它們是少用一個(gè)元素、設(shè)空滿標(biāo)志、用計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)。3.棧和隊(duì)列的區(qū)別是棧只能在表一端進(jìn)行插入和刪除操作，隊(duì)列限制在表的一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作。4.一個(gè)棧的輸入序列是12345，則棧的輸出序列43512是錯(cuò)誤的。5.設(shè)棧采取順序存儲(chǔ)結(jié)構(gòu)，棧中已有i-1個(gè)元素，則第i個(gè)元素進(jìn)棧操作的算法時(shí)間復(fù)雜度是O（1）。6.若用不帶頭結(jié)點(diǎn)的單鏈表表示棧，則創(chuàng)建一個(gè)空棧要執(zhí)行的操作是top=NULL。7.從循環(huán)隊(duì)列中刪除一個(gè)元素的操作是=+1)%QSize。8.從循環(huán)隊(duì)列中插入一個(gè)元素的操作是=+1)%QSize。9.判斷鏈隊(duì)列中只有一個(gè)結(jié)點(diǎn)的條件是>next==。10.如果棧的最大長(zhǎng)度難以估計(jì)，最好使用鏈棧。四、簡(jiǎn)答題1.為什么說(shuō)棧是一種后進(jìn)先出表答：因?yàn)闂Ｊ窍薅ㄔ诒淼囊欢诉M(jìn)行插入和刪除操作，所以后入棧的數(shù)據(jù)元素總是先出棧，所以說(shuō)棧是一種后進(jìn)先出表。2.對(duì)于一個(gè)棧，其輸入序列是A,B,C,試給出全部可能的輸出序列。答：可能的出棧序列是：ABC、ACB、BAC、BCA、CBA。3.何謂隊(duì)列上溢何為假溢出現(xiàn)象有哪些解決假溢出問(wèn)題的方法，并分別闡述其工作原理。答：隊(duì)列上溢指在隊(duì)列的順序存儲(chǔ)分配中，所有單元中已有元素，再進(jìn)行插入操作時(shí)稱(chēng)為隊(duì)列上溢。假溢出指在隊(duì)列的順序存儲(chǔ)分配中，分配給隊(duì)列的存儲(chǔ)空間有存儲(chǔ)單元未被占用，但按照操作規(guī)則而使進(jìn)隊(duì)的數(shù)據(jù)元素?zé)o法進(jìn)隊(duì)的現(xiàn)象。解決假溢出問(wèn)題的方法是在隊(duì)列的順序存儲(chǔ)分配中，分配給隊(duì)列的存儲(chǔ)空間可以循環(huán)使用，其進(jìn)本原理是用表示隊(duì)頭和隊(duì)尾指針與分配給隊(duì)列的存儲(chǔ)空間長(zhǎng)度進(jìn)行取模運(yùn)算。即：入隊(duì)操作：=+1)%MSize出隊(duì)操作：=+1)%MSize4.隊(duì)列可以用單循環(huán)鏈表來(lái)實(shí)現(xiàn)，故可以只設(shè)一個(gè)頭指針或只設(shè)一個(gè)尾指針，請(qǐng)分析用哪種方案最合適。答：使用循環(huán)鏈表來(lái)表示隊(duì)列，設(shè)置尾指針比較合適，因?yàn)槿腙?duì)操作可以直接在尾結(jié)點(diǎn)后進(jìn)行插入操作，出隊(duì)操作時(shí)可以根據(jù)尾指針很容易找到鏈表的頭結(jié)點(diǎn)，入隊(duì)出隊(duì)操作的算法時(shí)間復(fù)雜度均為O(1)。若只設(shè)頭指針，則出隊(duì)操作的算法時(shí)間復(fù)雜度為O(1)，入隊(duì)操作的算法時(shí)間復(fù)雜度為O(n)。5.簡(jiǎn)述線性表、棧和隊(duì)列的異同答：棧和隊(duì)列都是操作位置受限的線性表，即對(duì)插入和刪除操作的位置加以限制。棧是僅允許在表的一端進(jìn)行插入和刪除操作的線性表，因而是后進(jìn)先出表。隊(duì)列是允許在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表，因而是先進(jìn)先出表。線性表可以在任何位置進(jìn)行插入和刪除操作。五、算法設(shè)計(jì)題1.設(shè)計(jì)一個(gè)算法，利用棧和隊(duì)列的基本運(yùn)算將指定棧中的元素順序逆轉(zhuǎn)。解：算法基本思想：先將棧中元素出棧運(yùn)算移至隊(duì)列中，再將隊(duì)列中元素出隊(duì)列移至棧中。voidreverse(Stack&st){Queuesq；ElemTypex;InitQueue(sq)while(!StackEmpty(st){pop(st,x)EnQueue(sq,x);}while(!QueueEmpty(sq){DeQueue(sq,x);Push(st,x);}DestroyQueue(sq);}2.設(shè)計(jì)一個(gè)算法，利用棧的基本運(yùn)算返回指定棧中棧底元素。解：先將棧中元素依次移至另一個(gè)臨時(shí)棧中，最后一個(gè)元素即為棧底元素，設(shè)為x.。再將臨時(shí)棧中元素移至原棧中，即恢復(fù)棧內(nèi)容。ElemTypebottom(Stack&st){ElemTypex,y;Stacktmpst;InitStack(tmpst)while(!StackEmpty(st){pop(st,x)push(tmpst,x);}while(!QueueStack(temst){pop(tmpst,y);計(jì)一個(gè)算法，利用棧來(lái)實(shí)現(xiàn)帶頭結(jié)點(diǎn)的單鏈表h的逆序。解：算法基本思想：將單鏈表結(jié)點(diǎn)依次放入鏈棧中，鏈棧本身就是一個(gè)單鏈表，即實(shí)現(xiàn)了原單鏈表的逆序。假設(shè)鏈棧不帶頭結(jié)點(diǎn)，再加上原來(lái)的頭結(jié)點(diǎn)，就完成了原單鏈表的逆序。Voidrevert(SNode*h){SNode*st=NULL,*p=h->next,q;While(p){q=p->next;p->next=st;st=p;p=q;}h->next=st;}

第四章串一、單選題1.串是任意有限個(gè)【D】。A.符號(hào)構(gòu)成的集合B.符號(hào)構(gòu)成的序列C.字符構(gòu)成的集合D.字符構(gòu)成的序列2.串是一種特殊的線性表，其特殊性體現(xiàn)在【B】。A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.數(shù)據(jù)元素可以使多個(gè)字符D.可以鏈接存儲(chǔ)3.兩個(gè)串相等必有串長(zhǎng)度相等且【B】。A.串的各位置字符任意B.串中各位置字符均對(duì)應(yīng)相等C.兩個(gè)串含有相同的字符D.兩個(gè)串所含字符任意4.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)著【B】。A.連接B.模式匹配C.求子串D.求串長(zhǎng)二、填空1.空串是長(zhǎng)度為0的串。2.一個(gè)串中任意連續(xù)字符組成的子序列稱(chēng)為該串的子串。3.設(shè)s=“abcd”，則執(zhí)行語(yǔ)句s2=Substr(s,2,2)后，s2=“bc”。4.空白串是由一個(gè)或多個(gè)空格字符組成的串，其長(zhǎng)度等于其所包含的空格字符的個(gè)數(shù)。

第五章數(shù)組一、單選題1.一維數(shù)組與線性表的區(qū)別是【A】。A.前者長(zhǎng)度固定，后者長(zhǎng)度可變B.后進(jìn)長(zhǎng)度固定，前者長(zhǎng)度可變C.兩者長(zhǎng)度均固定D.兩者長(zhǎng)度均可變2.多維數(shù)組的數(shù)組元素之間的關(guān)系，【A】。A.是線性的B.是樹(shù)型的C.既是線性的，又是樹(shù)型的D.既不是線性的，也不是樹(shù)型的3.設(shè)有數(shù)組A[8][10]，每個(gè)元素占3個(gè)存儲(chǔ)單元，存放該數(shù)組的存儲(chǔ)單元數(shù)為【C】。4.設(shè)有數(shù)組A[8][10]，每個(gè)元素占3個(gè)存儲(chǔ)單元，首地址為SA，則元素[7][5]的起始地址是【D】。+141+144+222+2255.設(shè)有一個(gè)n*n的對(duì)稱(chēng)矩陣，采用壓縮存儲(chǔ)，則存入內(nèi)存的元素個(gè)數(shù)為【C】。*n*n/2*(n+1)/2D.(n+1)2/26.設(shè)A是一個(gè)n*n的對(duì)稱(chēng)矩陣，壓縮存儲(chǔ)到一個(gè)一維數(shù)組B[0..n(n+1)/2-1]中，則下三角部分元素ai,j在B中的位置是【A】。A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j7.稀疏矩陣一般的壓縮方法有兩種，即【C】。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表8.設(shè)有一個(gè)10*10的對(duì)稱(chēng)矩陣A，以行主次序進(jìn)行壓縮存儲(chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，a1,1的地址是1，則A8,5的起始地址是【B】。二、解答題1.設(shè)數(shù)組A[50][80]，其基地址為2000，每個(gè)元素占2個(gè)存儲(chǔ)單元，以行序位主序順序存儲(chǔ)，回答下列問(wèn)題：（1）該數(shù)據(jù)組由多少元素（2）該數(shù)組占用多少存儲(chǔ)單元（3）數(shù)組元素a[30][30]的存儲(chǔ)地址是多少答：（1）該數(shù)組有：50*80=4000個(gè)元素（2）該數(shù)組占用4000*4=8000個(gè)存儲(chǔ)單元（3）loc(30,30)=2000+(30*80+30)*2=2000+4860=6860

第六章樹(shù)與二叉樹(shù)一、單選題1.有關(guān)二叉樹(shù)下列說(shuō)法正確的是【B】。A.二叉樹(shù)的度為2B.一棵二叉樹(shù)的度可以小于2C.一棵二叉樹(shù)至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度為22.利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是【C】。A.指向最左孩子B.指向最右孩子C.空D.非空3.若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)為【B】。D.不確定4.一棵二叉樹(shù)有1001個(gè)結(jié)點(diǎn)，其中葉結(jié)點(diǎn)的個(gè)數(shù)為【D】。D.不確定5.一棵完全二叉樹(shù)有1001個(gè)結(jié)點(diǎn)，其中葉結(jié)點(diǎn)的個(gè)數(shù)為【D】。D.以上答案均不對(duì)6.一棵具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為【C】。至1025之間至1024之間7.一棵124個(gè)葉結(jié)點(diǎn)的完全樹(shù)，最多具有【B】個(gè)結(jié)點(diǎn)。8.一棵具有10個(gè)葉結(jié)點(diǎn)的二叉樹(shù)具有【B】度為2的結(jié)點(diǎn)。9.已知一棵完全二叉樹(shù)有625個(gè)結(jié)點(diǎn)，葉結(jié)點(diǎn)的個(gè)數(shù)為【C】。D.其它10.一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高h(yuǎn)為【AB】。A.log2n+1B.log2n+1+111.由8個(gè)權(quán)值構(gòu)造一棵哈夫曼樹(shù)，該哈夫曼樹(shù)有【A】個(gè)結(jié)點(diǎn)。12.由3個(gè)結(jié)點(diǎn)可以構(gòu)造【D】種不同的二叉樹(shù)。13.樹(shù)最適合用來(lái)表示【C】。A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素間具有分支層次關(guān)系的數(shù)據(jù)D.元素間無(wú)聯(lián)系的數(shù)據(jù)14.下圖中4棵二叉樹(shù)中，【C】不是完全二叉樹(shù)。A.B.C.D.15.某二叉樹(shù)的先序遍歷序列和后序便利序列正好相反，則該二叉樹(shù)一定是【A】。A.空或只有一個(gè)結(jié)點(diǎn)B.完全二叉樹(shù)C.二叉排序樹(shù)D.高度等于其結(jié)點(diǎn)數(shù)16.在一棵非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊【A】。A.只有右子樹(shù)上的所有結(jié)點(diǎn)B.只有右子樹(shù)上的部分結(jié)點(diǎn)C.只有左子樹(shù)上的部分結(jié)點(diǎn)D.只有左子樹(shù)上的所有結(jié)點(diǎn)17.任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序【A】。A.不發(fā)生上改變B.發(fā)生改變C.不能確定D.以上都不對(duì)18.一棵滿二叉樹(shù)，m個(gè)葉結(jié)點(diǎn)，n個(gè)結(jié)點(diǎn)，深度為h，則【D】。=h+m+m=2n=h-1=2h-119.設(shè)n，m是二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m之前的條件是【C】。在m右方是m的祖先在m左方是m的子孫20.設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類(lèi)二叉樹(shù)中包含的結(jié)點(diǎn)數(shù)最少為【B】。+1+1二、判斷題【×】1.二叉樹(shù)是一般樹(shù)的特殊樹(shù)型?！尽獭?.樹(shù)與二叉樹(shù)是兩種不同的樹(shù)形結(jié)構(gòu)?！尽痢?.對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度為log2n。【√】4.完全二叉樹(shù)中，若一個(gè)沒(méi)有左孩子，則它必定是葉結(jié)點(diǎn)?！尽獭?.一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，從上到下、從左到右用自然數(shù)對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，結(jié)點(diǎn)為i的結(jié)點(diǎn)的左孩子的編號(hào)為2i(2i<n)。【×】6.一棵樹(shù)中的葉結(jié)點(diǎn)數(shù)一定等于與其對(duì)應(yīng)的二叉樹(shù)的葉結(jié)點(diǎn)數(shù)?！尽獭?.哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路經(jīng)上權(quán)值較大的結(jié)點(diǎn)離根最近?！尽獭?.哈夫曼樹(shù)的結(jié)點(diǎn)個(gè)數(shù)不偶數(shù)。三、填空題1.深度為k的完全二叉樹(shù)至少有2K-1個(gè)結(jié)點(diǎn)，至多有2K-1個(gè)結(jié)點(diǎn)。2.在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則有n0=n2+1。3.一棵二叉樹(shù)第i層最多有2i-1個(gè)結(jié)點(diǎn)，一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)共有2K-1個(gè)結(jié)點(diǎn)，共有2K-1個(gè)葉結(jié)點(diǎn)。4.根據(jù)二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)共有5種不同形態(tài)，它們分別是。5.在一棵完全二叉樹(shù)中，結(jié)點(diǎn)個(gè)數(shù)為n，則編號(hào)最大的分支結(jié)點(diǎn)的編號(hào)為.n/2。6.在一棵完全二叉樹(shù)中，編號(hào)i和j的兩個(gè)結(jié)點(diǎn)處于同一層的條件是.log2i==.log2j。7.具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，共有n+1個(gè)空指針域。8.具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，如果有m個(gè)葉結(jié)點(diǎn)，則一定有m-1個(gè)度為2的結(jié)點(diǎn)，有n-2m+1個(gè)度為1的結(jié)點(diǎn)。9.在二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，指針p所指結(jié)點(diǎn)為葉結(jié)點(diǎn)的條件是p->lchild==NULL&&p->rchild==NULL。10.二叉樹(shù)的先序序列和中序序列相等的條件是任何結(jié)點(diǎn)至多只有右子樹(shù)。11.有一棵如下圖所示的樹(shù)，回答下列問(wèn)題：①這棵樹(shù)的根結(jié)點(diǎn)是a。②這棵樹(shù)的葉子結(jié)點(diǎn)是b,e,g,d。③結(jié)點(diǎn)c的度為2。④這棵樹(shù)的深度是4。⑤結(jié)點(diǎn)c的孩子結(jié)點(diǎn)是e,f。⑥結(jié)點(diǎn)c的雙親結(jié)點(diǎn)是a。⑦這棵樹(shù)的度是3。aabcdefg12.樹(shù)與二叉樹(shù)的兩個(gè)主要差別是樹(shù)中結(jié)點(diǎn)的最大度沒(méi)有限制，二叉樹(shù)結(jié)點(diǎn)的最大度限定為2、樹(shù)的結(jié)點(diǎn)無(wú)左右之分，二叉樹(shù)的的結(jié)點(diǎn)有左右之分。13.樹(shù)中任一結(jié)點(diǎn)允許有0個(gè)或多個(gè)孩子個(gè)孩子結(jié)點(diǎn)，除根結(jié)點(diǎn)之外，其余結(jié)點(diǎn)有1個(gè)雙親結(jié)點(diǎn)。四、簡(jiǎn)答題1.設(shè)有如下圖所示的二叉樹(shù)，給出其前序、中序和后序遍歷結(jié)果。答：前序序列：eadcbifghj中序序列：abcdiefhgj后序序列：bcidahjgfeeeafdigcjbh2.給出下圖所示的樹(shù)的二叉樹(shù)表示。eeafdigcjbhk答：下圖為其樹(shù)的二叉樹(shù)表示。eeadfcbhgijk3.有一份電文共有5個(gè)字符：a,b,c,d,e,它們出現(xiàn)的頻率依次為4，7，5，2，9，構(gòu)造對(duì)應(yīng)的哈夫曼樹(shù)，求哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度和每個(gè)字符的哈夫曼編碼。11117956421627字符編碼：a：011b：10c：00d：010e：114.假設(shè)一棵二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)，如下圖所示。05101520eafdgcjhib回答些列問(wèn)題：①畫(huà)出二叉樹(shù)表示。②寫(xiě)出先序、中序和后序遍歷結(jié)果③寫(xiě)出結(jié)點(diǎn)c的雙親結(jié)點(diǎn)和左、右孩子結(jié)點(diǎn)④畫(huà)出此二叉樹(shù)還原成森林的圖aefdaefdjhbgci②先序序列為：eadcbjfghi中序序列為：acbdjefhgi后序序列為：bcjdahigfe③結(jié)點(diǎn)c的雙親結(jié)點(diǎn)是d，左孩子為b，無(wú)右孩子④該二叉樹(shù)對(duì)應(yīng)的森林為aefaefdjhbgci一、單選題1.在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊的【C】倍。22.在一個(gè)有向圖中，所有頂點(diǎn)的入度數(shù)之和等于所有頂點(diǎn)的出度之和的【B】倍。23.一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有【C】條邊。(n-1)(n-1)/24.具有4個(gè)頂點(diǎn)的無(wú)向完全圖有【A】條邊。5.具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有【A】條邊才能確保是一個(gè)連通圖。6.一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是【D】。B.(n-1)2C.(n-1)D.n27.對(duì)某個(gè)無(wú)向圖的鄰接矩陣來(lái)說(shuō)，【A】。A.第i行上的非0元素個(gè)數(shù)等于第i列上非0元素個(gè)數(shù)B.矩陣中非0元素個(gè)數(shù)等于圖中的邊數(shù)C.第i行、第i列上非0元素個(gè)數(shù)等于頂點(diǎn)vi的度數(shù)D.矩陣中非全0行的行數(shù)等于圖中的頂點(diǎn)數(shù)8.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的大小為【①A】；所有鄰接表中結(jié)點(diǎn)總數(shù)為【②C】。①+1②2+e二、判斷題【×】個(gè)頂點(diǎn)的無(wú)向圖至多有n(n-1)條邊?！尽獭?.有向圖中，各頂點(diǎn)的入度之和等于各頂點(diǎn)的出度之和?！尽獭?.鄰接矩陣只存儲(chǔ)了邊的信息，沒(méi)有存儲(chǔ)頂點(diǎn)的信息。【×】4.連通分量是無(wú)向圖的極小連通子圖。?！尽痢?.如果表示有向圖的鄰接矩陣是對(duì)稱(chēng)的，則該有向圖一定是完全有向圖?！尽痢?.如果表示圖的鄰接矩陣是對(duì)稱(chēng)的，則該圖一定是無(wú)向圖?！尽獭?.如果表示圖的鄰接矩陣不是對(duì)稱(chēng)的，則該圖一定是有向圖。三、填空題1.有n個(gè)頂點(diǎn)的無(wú)向圖最多有n(n-1)/2條邊。2.具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖至少有n條邊。3.具有n個(gè)頂點(diǎn)的有向圖最多有n(n-1)條邊。4.一個(gè)圖的臨接矩陣表示法是唯一的，而鄰接表表示法是不唯一的。5.具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為45。6.在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)n-1。7.已知一個(gè)有向圖采用鄰接矩陣表示，計(jì)算第i個(gè)頂點(diǎn)的入度的方法是求第i列非0元素個(gè)數(shù)。8.已知一個(gè)有向圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的弧的方法是將第i行對(duì)應(yīng)的1置成0。9.對(duì)于n的頂點(diǎn)的無(wú)向圖，采用鄰接矩陣表示，求圖中邊的方法是計(jì)算鄰接矩陣中元素值為1的個(gè)數(shù)，判斷任意兩個(gè)頂點(diǎn)是否有邊相連的方法是判斷對(duì)應(yīng)鄰接矩陣元素的值是否為1，再除以2，求任意頂點(diǎn)的度的方法是求鄰接矩陣中對(duì)應(yīng)頂點(diǎn)所在行值為1的元素個(gè)數(shù)。10.對(duì)于n的頂點(diǎn)的有向圖，采用鄰接矩陣表示，求圖中邊的方法是計(jì)算鄰接矩陣中元素值為1的個(gè)數(shù)，判斷任意兩個(gè)頂點(diǎn)是否有邊相連的方法是判斷對(duì)應(yīng)鄰接矩陣元素的值是否為1，求任意頂點(diǎn)的度的方法是求鄰接矩陣中對(duì)應(yīng)頂點(diǎn)所在行和列的元素值為1的個(gè)數(shù)。11.無(wú)向圖的連通分量指無(wú)向圖中最大連通子圖。12.若無(wú)向圖有m條邊，，則表示該無(wú)向圖的鄰接表中有2m結(jié)點(diǎn)。四、簡(jiǎn)答題1.從占用的存儲(chǔ)空間來(lái)看，對(duì)于稠密圖和稀疏圖，采用鄰接矩陣和鄰接表那個(gè)更好些答：從占用存儲(chǔ)空間看，稠密圖采用鄰接矩陣更好，稀疏圖采用鄰接表更好。2.用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)與邊的條數(shù)是否相關(guān)為什么。答：用鄰接矩陣表示圖，矩陣元素的個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)直接相關(guān)，與邊的條數(shù)無(wú)關(guān)。因?yàn)榧僭O(shè)定點(diǎn)個(gè)數(shù)為n，則鄰接矩陣的大小為n2。

第九章查找一、單選題1.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為【B】的查找表。A.散列存儲(chǔ)B.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C.壓縮存儲(chǔ)D.索引存儲(chǔ)2.對(duì)查找表進(jìn)行折半查找時(shí)，要求查找表必須【B】。A.以順序方式存儲(chǔ)B.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列C.以鏈?zhǔn)椒绞酱鎯?chǔ)D.以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列3.采用順序查找法查找長(zhǎng)度為n的查找表時(shí)，每個(gè)元素查找的平均查找長(zhǎng)度為【C】。2C.(n+1)/2D.(n-1)/24.采用折半查找法查找長(zhǎng)度為n的查找表時(shí)，每個(gè)元素查找的平均查找長(zhǎng)度為【D】。(n2)(nlog2n)(n)(log2n)5.采用分塊查找時(shí)，若查找表中有625個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)對(duì)索引表和塊都采用順序查找，每塊應(yīng)分【B】個(gè)結(jié)點(diǎn)最佳。6.查找n個(gè)元素的有序表時(shí)，最有效的查找方法是【C】。A.順序查找B.分塊查找C.折半查找D.二叉排序樹(shù)7.如果要求一個(gè)查找表既能快速查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用【A】查找方法。A.分塊B.順序C.折半D.散列8.在關(guān)鍵字隨機(jī)分布的情況下，用二叉排序樹(shù)的方法進(jìn)行查找，其查找長(zhǎng)度與【B】量級(jí)相當(dāng)。A.順序查找B.折半查找C.分塊查找D.前三個(gè)都不正確9.查找效率最高的二叉排序樹(shù)是【C】。A.所有結(jié)點(diǎn)的左子樹(shù)都為空的二叉排序樹(shù)B.所有結(jié)點(diǎn)的右子樹(shù)都為空的二叉排序樹(shù)C.平衡二叉樹(shù)D.沒(méi)有左子樹(shù)的二叉排序樹(shù)10.假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)再散列法把這k個(gè)關(guān)鍵字的紀(jì)錄插入到散列表中，至少要進(jìn)行【D】次探測(cè)。+1(k+1)/211.以下說(shuō)法錯(cuò)誤的是【B】。A.散列法存儲(chǔ)的基本思想是由記錄關(guān)鍵字決定數(shù)據(jù)存儲(chǔ)地址B.散列法的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含任何指針C.裝填因子是散列法的一個(gè)重要參數(shù)，它反映了散列表的裝填程度D.散列表的查找效率取決于散列造表是的散列函數(shù)和沖突處理的方法12.散列表的平均查找長(zhǎng)度【A】。A.與沖突處理方法有關(guān)而與表的長(zhǎng)度無(wú)關(guān)B.與沖突處理方法無(wú)關(guān)而與表的長(zhǎng)度有關(guān)C.與沖突處理方法有關(guān)且與表的長(zhǎng)度有關(guān)D.與沖突處理方法無(wú)關(guān)且與表的長(zhǎng)度無(wú)關(guān)二、判斷題【√】1.順序查找法適合于順序或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的查找表?！尽痢?.順序查找法只能在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行。【×】3.二分查找可以在有序的雙向鏈表上進(jìn)行。【×】4.在二叉排序樹(shù)中，每個(gè)結(jié)點(diǎn)的關(guān)鍵字比左孩子的關(guān)鍵字大，比右孩子的關(guān)鍵字小?！尽痢?.每個(gè)結(jié)點(diǎn)的關(guān)鍵字都比左孩子的關(guān)鍵字大，比右孩子的關(guān)鍵字小，這樣的二叉樹(shù)都是二叉排序樹(shù)?！尽獭?.哈希存儲(chǔ)法只能存儲(chǔ)數(shù)據(jù)元素的值，不能存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系。【×】7.哈希沖突是指同一個(gè)關(guān)鍵字對(duì)應(yīng)多個(gè)不同的哈希地址。三、填空題1.順序查找含n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為n次；若查找不成功，則比較關(guān)鍵字的次數(shù)為n+1次。2.在含有n個(gè)元素的有序順序表中進(jìn)行二分查找，最大的比較次數(shù)是.log2n+1。3.用二分查找一個(gè)查找表，該查找表必須具有的特點(diǎn)是順序存儲(chǔ)且關(guān)鍵字有序。4.分塊查找發(fā)將待查找的表均勻地分成若干塊且塊中諸記錄的順序可以是任意的，但塊與塊之間關(guān)鍵字有序。5.在分塊查找方法中，首先查找關(guān)鍵字表，然后再查找相應(yīng)的對(duì)應(yīng)的塊。6.用二叉排序樹(shù)在n個(gè)元素中進(jìn)行查找，最壞情況下查找時(shí)間復(fù)雜度為O(n)，最好情況的查找時(shí)間復(fù)雜度為O(log2n)。7.折半查找的存儲(chǔ)結(jié)構(gòu)僅限于順序存儲(chǔ)結(jié)構(gòu)，且是關(guān)鍵字有序排列。8.一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成有序序列，構(gòu)造樹(shù)的過(guò)程即是對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。9.用二叉排序樹(shù)查找，在最壞的情況下，平均查找長(zhǎng)度為（n+1）/2，最好的情況下，平均查找長(zhǎng)度為.(log2n+1)-1。10.在哈希函數(shù)H(key)=key/p中，p最好取小于或等于m的最大質(zhì)數(shù)。11.哈希表是通過(guò)將關(guān)鍵字按選定的哈希函數(shù)和沖突處理方法，把記錄按關(guān)鍵字轉(zhuǎn)換為地址進(jìn)行存儲(chǔ)的存儲(chǔ)表，哈希方法的關(guān)鍵是選擇好的哈希函數(shù)