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

數(shù)據(jù)構(gòu)造題集第一章緒論一、單項(xiàng)選擇題1.在數(shù)據(jù)構(gòu)造中，從邏輯上可以把數(shù)據(jù)構(gòu)造提成【C】。A.動(dòng)態(tài)構(gòu)造和靜態(tài)構(gòu)造B.緊湊構(gòu)造和非緊湊構(gòu)造C.線性構(gòu)造和非線性構(gòu)造D.內(nèi)部構(gòu)造和外部構(gòu)造2.數(shù)據(jù)構(gòu)造在計(jì)算機(jī)內(nèi)存中的表達(dá)是指【A】。A.數(shù)據(jù)的存儲(chǔ)構(gòu)造 B.數(shù)據(jù)構(gòu)造C.數(shù)據(jù)構(gòu)造的邏輯構(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)絡(luò)，這是指【B】。A.數(shù)據(jù)與數(shù)據(jù)之間存在某種關(guān)系B.數(shù)據(jù)元素與數(shù)據(jù)元素之間存在某種關(guān)系C.元素內(nèi)部存在某種構(gòu)造D.數(shù)據(jù)項(xiàng)與數(shù)據(jù)項(xiàng)之間存在某種關(guān)系5.算法分析的目的是【C】。A.找出數(shù)據(jù)構(gòu)造的合理性B.研究輸入和輸出的關(guān)系C.分析算法的效率以求改善D.分析算法的易懂性6.在存儲(chǔ)數(shù)據(jù)時(shí)，不僅要考慮存儲(chǔ)各數(shù)據(jù)元素的值，并且還要存儲(chǔ)【C】。A.數(shù)據(jù)處理的措施B.數(shù)據(jù)元素的類型C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲(chǔ)措施7.算法分析的重要任務(wù)是分析【D】。A.算法與否具有很好的可讀性B.算法中與否存儲(chǔ)語法錯(cuò)誤和邏輯錯(cuò)誤C.算法的功能與否符合設(shè)計(jì)規(guī)定D.算法的執(zhí)行時(shí)間與問題規(guī)模之間的關(guān)系。8.數(shù)據(jù)的運(yùn)算【A】。A.效率與采用何種存儲(chǔ)構(gòu)造有關(guān)B.是根據(jù)存儲(chǔ)構(gòu)造來定義的C.有算術(shù)運(yùn)算和關(guān)系運(yùn)算兩大類D.必須用程序設(shè)計(jì)語言來描述9.算法的計(jì)算量的大小稱為算法的【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ù)構(gòu)造的最小單位【.×】。2.數(shù)據(jù)的邏輯構(gòu)造闡明數(shù)據(jù)元素之間的次序關(guān)系，它依賴于計(jì)算機(jī)的存儲(chǔ)構(gòu)造【×.】。3.數(shù)據(jù)的邏輯構(gòu)造指數(shù)據(jù)元素的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系【×.】。4.算法的優(yōu)劣與算法的描述語言無關(guān)，但與使用的計(jì)算機(jī)有關(guān)【.×】。5.數(shù)據(jù)構(gòu)造的抽象操作的定義與詳細(xì)實(shí)既有關(guān)【.×】。三、填空題1.數(shù)據(jù)的邏輯構(gòu)造指數(shù)據(jù)元素之間的邏輯關(guān)系。2.一種數(shù)據(jù)構(gòu)造在計(jì)算機(jī)中的表達(dá)稱為存儲(chǔ)構(gòu)造。3.數(shù)據(jù)的物理構(gòu)造重要包括次序存儲(chǔ)構(gòu)造的表達(dá)和鏈?zhǔn)酱鎯?chǔ)構(gòu)造的表達(dá)。4.數(shù)據(jù)邏輯構(gòu)造包括集合、線性構(gòu)造、樹和圖四種，樹構(gòu)造和圖構(gòu)造統(tǒng)稱為非線性構(gòu)造。5.次序存儲(chǔ)措施把邏輯上邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里；鏈?zhǔn)酱鎯?chǔ)措施中結(jié)點(diǎn)間的邏輯關(guān)系是由指針域表達(dá)的。6、數(shù)據(jù)構(gòu)造研究的是邏輯構(gòu)造和物理構(gòu)造以及它們之間的互相關(guān)系，并對(duì)于這種構(gòu)造定義對(duì)應(yīng)的運(yùn)算，設(shè)計(jì)出對(duì)應(yīng)的算法。7.算法的執(zhí)行時(shí)間是問題規(guī)模n的函數(shù)。8.如下是4個(gè)算法所有語句頻度之和的體現(xiàn)式，其中的復(fù)雜度相似的是A和B。A.TA(n)=2n3+3n2+1000B.TB(n)=n3-n2log2n-1000C.TC(n)=n2log2n+n2D.TD(n)=n2+1000四、解答題1.簡述數(shù)據(jù)的邏輯構(gòu)造和存儲(chǔ)構(gòu)造的關(guān)系。答：在數(shù)據(jù)構(gòu)造中，邏輯構(gòu)造和存儲(chǔ)構(gòu)造是親密有關(guān)的，存儲(chǔ)構(gòu)造不僅將數(shù)據(jù)元素存儲(chǔ)到計(jì)算機(jī)中，并且還要表達(dá)各數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯構(gòu)造與計(jì)算機(jī)無關(guān)，存儲(chǔ)構(gòu)造是數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中的表達(dá)。一般狀況下，一種邏輯構(gòu)造可以有多種存儲(chǔ)構(gòu)造，例如，線性構(gòu)造可以采用次序存儲(chǔ)構(gòu)造或鏈?zhǔn)酱娲謽?gòu)造表達(dá)。2.數(shù)據(jù)構(gòu)造和數(shù)據(jù)類型有什么區(qū)別？答：數(shù)據(jù)構(gòu)造是互相間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，一般包括三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯構(gòu)造、存儲(chǔ)構(gòu)造和多數(shù)據(jù)的運(yùn)算。數(shù)據(jù)類型是一種值得集合和定義在這個(gè)值集上的一組操作的總稱。數(shù)據(jù)構(gòu)造重點(diǎn)考慮元素之間的關(guān)系，數(shù)據(jù)類型重點(diǎn)考慮數(shù)據(jù)的個(gè)體特性。3.當(dāng)為處理某一問題已經(jīng)選定其數(shù)據(jù)的邏輯構(gòu)造后，選擇數(shù)據(jù)的存儲(chǔ)構(gòu)造時(shí)，應(yīng)從哪些方面考慮？答：一般從兩個(gè)方面考慮：第一是算法實(shí)現(xiàn)的存儲(chǔ)空間復(fù)雜度；第二是算法執(zhí)行的時(shí)間復(fù)雜度。若存儲(chǔ)空間難以確定，宜選擇鏈?zhǔn)酱鎯?chǔ)構(gòu)造，否則選擇次序存儲(chǔ)構(gòu)造。若插入、刪除操作頻繁，則選鏈?zhǔn)酱鎯?chǔ)構(gòu)造，否則選擇次序存儲(chǔ)構(gòu)造。

第二章線性表一、單項(xiàng)選擇題1.鏈表不具有的特點(diǎn)是【A】。A.可隨機(jī)訪問任一結(jié)點(diǎn)B.插入刪除不需要移動(dòng)元素C.不必事先估算存儲(chǔ)空間D.所需空間與其長度成正比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ǔ)構(gòu)造是一種【A】。A.隨機(jī)存取的存儲(chǔ)構(gòu)造B.次序存取的存儲(chǔ)構(gòu)造C.索引存取的存儲(chǔ)構(gòu)造D.Hash存取的存儲(chǔ)構(gòu)造7.單鏈表中增長一種頭結(jié)點(diǎn)的目的是為了【C】。A.使單鏈表至少有一種結(jié)點(diǎn)B.標(biāo)識(shí)表首結(jié)點(diǎn)的位置C.以便運(yùn)算的實(shí)現(xiàn)D.闡明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)8.不帶頭結(jié)點(diǎn)的單鏈表（頭指針為h）為空的條件是【A】。A.h==NULLB.h->next==NULLC.h->next==hD.h!=NULL9.帶頭結(jié)點(diǎn)的單鏈表（頭指針為h）為空的條件是【B】。A.h==NULLB.h->next==NULLC.h->next==hD.h!=NULL10.帶頭結(jié)點(diǎn)的循環(huán)雙向鏈表（頭指針為L）為空的條件是【D】。A.L==NULLB.L->next->prior==NULLC.L->prior==NULLD.L->next==L11.非空的循環(huán)單鏈表（頭指針為head）的尾結(jié)點(diǎn)（由p指向）滿足【C】。A.p->next==NULLB.p==NULLC.p->next==headD.p==head12.設(shè)一種鏈表最常用的操作是在末尾插入結(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.訪問第i個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)B.在第i個(gè)結(jié)點(diǎn)后插入一種新結(jié)點(diǎn)C.刪除第i個(gè)結(jié)點(diǎn)D.以上都不對(duì)15.若長度為n的線性表采用次序存儲(chǔ)構(gòu)造，在第i個(gè)位置插入一種新元素的算法的時(shí)間復(fù)雜度為【C】。A.O(0)B.O(1)C.O(n)D.O(n2)16.對(duì)于次序存儲(chǔ)的線性表，訪問結(jié)點(diǎn)和增長、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為【C】。A.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)17.線性表以鏈?zhǔn)椒绞酱鎯?chǔ)，訪問第i個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為【C】。A.O(i)B.O(1)C.O(n)D.O(i-1)18.循環(huán)鏈表H尾結(jié)點(diǎn)p的特點(diǎn)是【A】。A.p->next==HB.p->next==H->nextC.p==HD.p==H->next二、判斷題【×】1.取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān)?！尽痢?.線性表中每個(gè)元素均有一種直接前驅(qū)和一種直接后繼?！尽痢?.次序存儲(chǔ)方式只能用于存儲(chǔ)線性構(gòu)造?！尽痢?.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以不持續(xù)?！尽痢?.在一種設(shè)有頭指針和尾指針的單鏈表中，執(zhí)行刪除單鏈表最終一種結(jié)點(diǎn)的操作與鏈表的長度無關(guān)。三、填空題1.向一種長度為n的次序表中的第i個(gè)元素之前插入一種元素時(shí)，需要向后移動(dòng)n-i+1個(gè)元素。2.在一種長度為n的次序表中刪除第i個(gè)元素時(shí)，需要向前移動(dòng)n-i個(gè)元素。3.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是簡化插入、刪除算法。4.在單鏈中要?jiǎng)h除某一指定結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。5.訪問單鏈表中的結(jié)點(diǎn)，必須沿著指針域依次進(jìn)行。6.在雙鏈表中每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一種指向直接前驅(qū)結(jié)點(diǎn)，一種指向直接后繼結(jié)點(diǎn)。7.在雙向循環(huán)鏈表中，刪除最終一種結(jié)點(diǎn)的算法時(shí)間復(fù)雜度為O(1)。8.訪問一種線性表中具有給定值的時(shí)間復(fù)雜度的數(shù)量級(jí)是O(n)。9.由n個(gè)數(shù)據(jù)元素生成一種次序表，若每次都調(diào)用插入算法把一種元素插入到表頭，則整個(gè)算法的時(shí)間復(fù)雜度為O(n)，若每次都調(diào)用插入算法把一種元素插入到表尾，則整個(gè)算法的時(shí)間復(fù)雜度為O(n2)。10.在雙向鏈表中，可以用表尾指針替代表頭指針。11.根據(jù)n個(gè)數(shù)據(jù)元素建立對(duì)應(yīng)的次序表和單鏈表存儲(chǔ)構(gòu)造，其算法的時(shí)間復(fù)雜度最佳的狀況是O(n)，最壞的狀況是O(n2)。12.求線性表的次序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的長度的算法時(shí)間復(fù)雜度分別是O(1)和O(n)。13.在一種帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過程與否相似？相似。14.在一種不帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過程與否相似？不相似。四、簡答題1.論述次序表和鏈表存儲(chǔ)方式的特點(diǎn)。答：次序表存儲(chǔ)方式為數(shù)據(jù)分派持續(xù)的存儲(chǔ)單元，數(shù)據(jù)元素按邏輯次序依次存儲(chǔ)到對(duì)應(yīng)存儲(chǔ)單元中，使得邏輯相鄰的數(shù)據(jù)元素物理也相鄰，因此可以實(shí)現(xiàn)隨機(jī)訪問線性表的數(shù)據(jù)元素，即數(shù)據(jù)訪問的時(shí)間復(fù)雜度為O(1)。鏈表存儲(chǔ)方式分派的存儲(chǔ)單元可以不持續(xù)，通過每個(gè)結(jié)點(diǎn)的指針域來表達(dá)數(shù)據(jù)元素之間的邏輯關(guān)系，只能次序訪問線性表中的數(shù)據(jù)元素。2.若頻繁地對(duì)一種線性表進(jìn)行插入和刪除操作，則該線性表宜采用何種存儲(chǔ)構(gòu)造，為何？答：若頻繁地對(duì)一種線性表進(jìn)行插入和刪除操作，則該線性表宜采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造。由于鏈?zhǔn)酱鎯?chǔ)構(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從對(duì)應(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。單鏈表不行，由于不懂得頭指針就無法找到結(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)，所要做的都是修改前一種結(jié)點(diǎn)的指針域，由于在帶頭結(jié)點(diǎn)的鏈表中任何元素結(jié)點(diǎn)均有前驅(qū)結(jié)點(diǎn)。假如沒有頭結(jié)點(diǎn)，在首元結(jié)點(diǎn)前插入結(jié)點(diǎn)或刪除首元結(jié)點(diǎn)都要修改頭指針，其算法要比帶頭結(jié)點(diǎn)的算法復(fù)雜些。另一方面，帶頭結(jié)點(diǎn)的鏈表構(gòu)造，初始化后的頭指針就固定了，除撤銷算法外，所有算法都不會(huì)修改頭指針，可以減少出錯(cuò)的也許性。五、算法設(shè)計(jì)題1.已知一種線性表用含頭結(jié)點(diǎn)的單鏈表做存儲(chǔ)構(gòu)造，寫一種算法求單鏈表的長度。解：算法基本思想：從頭結(jié)點(diǎn)的下一種結(jié)點(diǎn)開發(fā)，遍歷單鏈表的每個(gè)結(jié)點(diǎn)，每碰到一種結(jié)點(diǎn)，結(jié)點(diǎn)計(jì)算器加1。intlistlenght(linklistL){intlength=0;P=L->next;while(p){length++;p=p->next;}return(length);}2.已知一種次序表L，其中的元素按值遞增有序排列，設(shè)計(jì)一種算法插入一種值為x的元素后保持該次序表仍然遞增有序，且空間復(fù)雜度為0（1）。voidinsertsq(sqlistL,elemtypex){n=L.length-1;while(n>=0&<(x,L.elem[n]){L.elem[n+1]=L.elem[n];n--;}L.elem[n+1]=x;}L.lenght++;return;}3.寫一種算法，從次序表中刪除值為x的所有元素。voiddelallsq(Sqlist&L){inti=0,j=0;while(j<L.length){if(L.elem[j]!=x)L.elem[i++]=L.elem[j];j++;}L.longth=i;}

第三章棧和隊(duì)列一、單項(xiàng)選擇題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)同步進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先C.每當(dāng)有刪除操作時(shí)，總要先做一次插入操作D.每次從隊(duì)中刪除的元素總是最早插入的元素3.與次序棧相比較，鏈棧有一種比較明顯的優(yōu)勢是【A】。A.一般不會(huì)出現(xiàn)棧滿的狀況B.插入操作更輕易實(shí)現(xiàn)C.一般不會(huì)出現(xiàn)棧空的狀況D.刪除操作更輕易實(shí)現(xiàn)4.棧和隊(duì)列的共同點(diǎn)是【C】。A.都是先進(jìn)先出B.都是后進(jìn)后出C.只容許在端點(diǎn)處進(jìn)行插入和刪除D.無共同點(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ǔ)的線性構(gòu)造B.鏈?zhǔn)酱鎯?chǔ)的線性構(gòu)造C.限制存取點(diǎn)的線性構(gòu)造D.限制存取點(diǎn)的非線性構(gòu)造④⑤A.3,2,1,4B.3,2,4,1C.4,2,3,1D.1,2,3,46.用單鏈表表達(dá)的鏈隊(duì)列的隊(duì)頭在鏈表的【A】。A.鏈頭B.鏈尾C.鏈中D.都不是7.設(shè)入棧序列為1,2,3,4,5,則也許得到的出棧序列為【C】。A.1,2,5,3,4B.3,1,2,5,4C.3,2,5,4,1D.1,4,2,3,58.輸入序列是ABC，若輸出序列變?yōu)镃BA，通過的棧操作為【B】。A.push,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.體現(xiàn)式求值D.A,B,C10.設(shè)計(jì)一種鑒別體現(xiàn)式中左、右括號(hào)與否配對(duì)的算法，采用【D】數(shù)據(jù)構(gòu)造最佳。A.線性表的次序存儲(chǔ)構(gòu)造B.隊(duì)列C.線性表的鏈?zhǔn)酱鎯?chǔ)構(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.無法判斷隊(duì)列與否為空B.無法判斷隊(duì)列與否為滿C.隊(duì)列不也許滿D.以上說法都不對(duì)13.隊(duì)列寄存在A[0..M-1]中，則入隊(duì)時(shí)的操作為【B】。A.rear=rear+1B.rear=(rear+1)%MC.rear=(rear+1)%(M+1)D.rear=(rear+1)%(M-1)14.隊(duì)列寄存在A[0..M-1]中，則出隊(duì)時(shí)的操作為【B】。A.front=front+1B.front=(front+1)%MC.front=(front+1)%(M+1)D.front=(front+1)%(M-1)15.循環(huán)隊(duì)列的最大容量為M，則隊(duì)空的條件是【A】。A.rear==frontB.(rear+1)%M==frontC.rear+1==frontD.(rear-1)%M==front16.循環(huán)隊(duì)列的最大容量為M，則隊(duì)滿的條件是【B】。A.rear==frontB.(rear+1)%M==frontC.rear+1==frontD.(rear-1)%M==front二、判斷題【×】1.隊(duì)列在函數(shù)調(diào)用時(shí)必不可少，因此遞歸離不開隊(duì)列?！尽獭?.棧和隊(duì)列的存儲(chǔ)方式，既可以是次序方式，又可以是鏈?zhǔn)椒绞??！尽獭?.設(shè)尾指針的循環(huán)鏈表表達(dá)隊(duì)列，則入隊(duì)和出隊(duì)算法的時(shí)間復(fù)雜度為0(1)。【×】4.隊(duì)列邏輯上是一種上端和下端既能增長又能減少的線性表?！尽獭?.在鏈隊(duì)列中，雖然不設(shè)置尾指針也能進(jìn)行入隊(duì)操作?！尽獭?.棧和隊(duì)列度是限制存取點(diǎn)的線性構(gòu)造?！尽痢?.雖然對(duì)不含相似元素的同一輸入序列進(jìn)行兩組不一樣的合法的入棧和出棧操作，所得的輸出序列一定相似?！尽獭?.棧是實(shí)現(xiàn)函數(shù)調(diào)用所必需的數(shù)據(jù)構(gòu)造?！尽獭?.次序隊(duì)列中的元素個(gè)數(shù)，可以根據(jù)隊(duì)首指針和隊(duì)尾指針的值計(jì)算出來。三、填空題1.循環(huán)隊(duì)列的引入，目的是為了克服次序隊(duì)列的假溢出。2.辨別循環(huán)隊(duì)列的空與滿有3種措施，它們是少用一種元素、設(shè)空滿標(biāo)志、用計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)。3.棧和隊(duì)列的區(qū)別是棧只能在表一端進(jìn)行插入和刪除操作，隊(duì)列限制在表的一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作。4.一種棧的輸入序列是12345，則棧的輸出序列43512是錯(cuò)誤的。5.設(shè)棧采用次序存儲(chǔ)構(gòu)造，棧中已經(jīng)有i-1個(gè)元素，則第i個(gè)元素進(jìn)棧操作的算法時(shí)間復(fù)雜度是O（1）。6.若用不帶頭結(jié)點(diǎn)的單鏈表表達(dá)棧，則創(chuàng)立一種空棧要執(zhí)行的操作是top=NULL。7.從循環(huán)隊(duì)列中刪除一種元素的操作是Q.front=(Q.front+1)%QSize。8.從循環(huán)隊(duì)列中插入一種元素的操作是Q.rear=(Q.rear+1)%QSize。9.判斷鏈隊(duì)列中只有一種結(jié)點(diǎn)的條件是Q.front->next==Q.rear。10.假如棧的最大長度難以估計(jì)，最佳使用鏈棧。四、簡答題1.為何說棧是一種后進(jìn)先出表？答：由于棧是限定在表的一端進(jìn)行插入和刪除操作，所后來入棧的數(shù)據(jù)元素總是先出棧，因此說棧是一種后進(jìn)先出表。2.對(duì)于一種棧，其輸入序列是A,B,C,試給出所有也許的輸出序列。答：也許的出棧序列是：ABC、ACB、BAC、BCA、CBA。3.何謂隊(duì)列上溢？何為假溢出現(xiàn)象？有哪些處理假溢出問題的措施，并分別論述其工作原理。答：隊(duì)列上溢指在隊(duì)列的次序存儲(chǔ)分派中，所有單元中已經(jīng)有元素，再進(jìn)行插入操作時(shí)稱為隊(duì)列上溢。假溢出指在隊(duì)列的次序存儲(chǔ)分派中，分派給隊(duì)列的存儲(chǔ)空間有存儲(chǔ)單元未被占用，但按照操作規(guī)則而使進(jìn)隊(duì)的數(shù)據(jù)元素?zé)o法進(jìn)隊(duì)的現(xiàn)象。處理假溢出問題的措施是在隊(duì)列的次序存儲(chǔ)分派中，分派給隊(duì)列的存儲(chǔ)空間可以循環(huán)使用，其進(jìn)本原理是用表達(dá)隊(duì)頭和隊(duì)尾指針與分派給隊(duì)列的存儲(chǔ)空間長度進(jìn)行取模運(yùn)算。即：入隊(duì)操作：Q.rear=(Q.rear+1)%MSize出隊(duì)操作：Q.front=(Q.front+1)%MSize4.隊(duì)列可以用單循環(huán)鏈表來實(shí)現(xiàn)，故可以只設(shè)一種頭指針或只設(shè)一種尾指針，請(qǐng)分析用哪種方案最合適。答：使用循環(huán)鏈表來表達(dá)隊(duì)列，設(shè)置尾指針比較合適，由于入隊(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.簡述線性表、棧和隊(duì)列的異同？答：棧和隊(duì)列都是操作位置受限的線性表，即對(duì)插入和刪除操作的位置加以限制。棧是僅容許在表的一端進(jìn)行插入和刪除操作的線性表，因而是后進(jìn)先出表。隊(duì)列是容許在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表，因而是先進(jìn)先出表。線性表可以在任何位置進(jìn)行插入和刪除操作。五、算法設(shè)計(jì)題1.設(shè)計(jì)一種算法，運(yùn)用棧和隊(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ì)一種算法，運(yùn)用棧的基本運(yùn)算返回指定棧中棧底元素。解：先將棧中元素依次移至另一種臨時(shí)棧中，最終一種元素即為棧底元素，設(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);//此時(shí)必須用另一種變量y，才能保留棧底元素在x中Push(st,y);}DestroyStack(tmpst);return(x);}3.設(shè)計(jì)一種算法，運(yùn)用棧來實(shí)現(xiàn)帶頭結(jié)點(diǎn)的單鏈表h的逆序。解：算法基本思想：將單鏈表結(jié)點(diǎn)依次放入鏈棧中，鏈棧自身就是一種單鏈表，即實(shí)現(xiàn)了原單鏈表的逆序。假設(shè)鏈棧不帶頭結(jié)點(diǎn)，再加上本來的頭結(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;}

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

第五章數(shù)組一、單項(xiàng)選擇題1.一維數(shù)組與線性表的區(qū)別是【A】。A.前者長度固定，后者長度可變B.后進(jìn)長度固定，前者長度可變C.兩者長度均固定D.兩者長度均可變2.多維數(shù)組的數(shù)組元素之間的關(guān)系，【A】。A.是線性的B.是樹型的C.既是線性的，又是樹型的D.既不是線性的，也不是樹型的3.設(shè)有數(shù)組A[8][10]，每個(gè)元素占3個(gè)存儲(chǔ)單元，寄存該數(shù)組的存儲(chǔ)單元數(shù)為【C】。A.80B.100C.240D.2704.設(shè)有數(shù)組A[8][10]，每個(gè)元素占3個(gè)存儲(chǔ)單元，首地址為SA，則元素[7][5]的起始地址是【D】。A.SA+141B.SA+144C.SA+222D.SA+2255.設(shè)有一種n*n的對(duì)稱矩陣，采用壓縮存儲(chǔ)，則存入內(nèi)存的元素個(gè)數(shù)為【C】。A.n*nB.n*n/2C.n*(n+1)/2D.(n+1)2/26.設(shè)A是一種n*n的對(duì)稱矩陣，壓縮存儲(chǔ)到一種一維數(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è)有一種10*10的對(duì)稱矩陣A，以行主次序進(jìn)行壓縮存儲(chǔ)，每個(gè)元素占一種存儲(chǔ)單元，a1,1的地址是1，則A8,5的起始地址是【B】。A.13B.33C.18D.40二、解答題1.設(shè)數(shù)組A[50][80]，其基地址為，每個(gè)元素占2個(gè)存儲(chǔ)單元，以行序位主序次序存儲(chǔ)，回答問題：（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)=+(30*80+30)*2=+4860=6860

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

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