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

數(shù)據(jù)結(jié)構(gòu)題集第一章緒論一、 單選題在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成【C】。動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指【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)系【A】是數(shù)據(jù)的最小單位，【B】是數(shù)據(jù)的基本單位。數(shù)據(jù)項(xiàng) B.數(shù)據(jù)元素C.信息項(xiàng) D.表元素計(jì)算機(jī)所處理數(shù)據(jù)一般具有某種內(nèi)在聯(lián)系，這是指【B】。數(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)系算法分析的目的是【C】。找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性在存儲(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ǔ)方法算法分析的主要任務(wù)是分析【D】。算法是否具有較好的可讀性算法中是否存儲(chǔ)語(yǔ)法錯(cuò)誤和邏輯錯(cuò)誤算法的功能是否符合設(shè)計(jì)要求算法的執(zhí)行時(shí)間與問(wèn)題規(guī)模之間的關(guān)系。數(shù)據(jù)的運(yùn)算【A】。效率與采用何種存儲(chǔ)結(jié)構(gòu)有關(guān)是根據(jù)存儲(chǔ)結(jié)構(gòu)來(lái)定義的有算術(shù)運(yùn)算和關(guān)系運(yùn)算兩大類(lèi)必須用程序設(shè)計(jì)語(yǔ)言來(lái)描述算法的計(jì)算量的大小稱(chēng)為算法的【B】。A.效率 B.時(shí)間復(fù)雜度 C.現(xiàn)實(shí)性D.難度連續(xù)存儲(chǔ)分配時(shí)，存儲(chǔ)單元的地址【A】。A.一定連續(xù) B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù)，部分不連續(xù)二、 判斷題數(shù)據(jù)元素是數(shù)據(jù)結(jié)構(gòu)的最小單位【.X】。數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)系，它依賴(lài)于計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)【X.】。數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)元素的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系【X.】。算法的優(yōu)劣與算法的描述語(yǔ)言無(wú)關(guān)，但與使用的計(jì)算機(jī)有關(guān)【.X】。數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)【.X】。三、 填空題數(shù)據(jù)的邏輯結(jié)構(gòu)指 。一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示 稱(chēng)為存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序存儲(chǔ)結(jié)構(gòu)的表示和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 的表示。數(shù)據(jù)邏輯結(jié)構(gòu)包括集合、線(xiàn)性結(jié)構(gòu)、樹(shù)和圖 四種，樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)統(tǒng)稱(chēng)為 。順序存儲(chǔ)方法把邏輯匕邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里；鏈?zhǔn)酱鎯?chǔ)方法中結(jié)點(diǎn)間的邏輯關(guān)系是由指針域 表示的。數(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)的。算法的執(zhí)行時(shí)間是問(wèn)題規(guī)模n的函數(shù)。以下是4個(gè)算法所有語(yǔ)句頻度之和的表達(dá)式，其中的復(fù)雜度相同的是A和B。TA(n)=2n3+3n2+1000 B.TB(n)=n3-n2log2n-1000C.TC(n)=n2log2n+n2 D.TD(n)=n2+1000四、 解答題簡(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)，例如，線(xiàn)性結(jié)構(gòu)可以采取順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱娲纸Y(jié)構(gòu)表示。數(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è)體特征。當(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)。第二章線(xiàn)性表一、單選題鏈表不具備的特點(diǎn)是【A】?？呻S機(jī)訪(fǎng)問(wèn)任一結(jié)點(diǎn) 8.插入刪除不需要移動(dòng)元素C.不必事先估算存儲(chǔ)空間D.所需空間與其長(zhǎng)度成正比設(shè)線(xiàn)性表有n個(gè)元素，以下操作中，【A】在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。輸出第i（IWiWn）個(gè)元素的值順序輸出這n個(gè)元素交換第1個(gè)與第2個(gè)元素的值輸出與給定值x相等的元素在線(xiàn)性表中的序號(hào)如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用【D】存儲(chǔ)方法最節(jié)省時(shí)間。A.單鏈表 8.雙鏈表 C.線(xiàn)性鏈表D.順序表線(xiàn)性表是具有n個(gè)【C】的有限序列（nN0）。A.表元素 B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)下面關(guān)于線(xiàn)性表的敘述中，錯(cuò)誤的是【B】。線(xiàn)性表采用順序存儲(chǔ)，則必須占用一片連續(xù)的存儲(chǔ)單元線(xiàn)性表采用順序存儲(chǔ)，則便于插入和刪除操作線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)，則不必占用一片連續(xù)的存儲(chǔ)單元線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)，則便于插入和刪除操作線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種【A】。A.隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B.順序存取的存儲(chǔ)結(jié)構(gòu)C.索引存取的存儲(chǔ)結(jié)構(gòu)D.Hash存取的存儲(chǔ)結(jié)構(gòu)單鏈表中增加一個(gè)頭結(jié)點(diǎn)的目的是為了【C】。A.使單鏈表至少有一個(gè)結(jié)點(diǎn) B.標(biāo)識(shí)表首結(jié)點(diǎn)的位置方便運(yùn)算的實(shí)現(xiàn)說(shuō)明單鏈表是線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)不帶頭結(jié)點(diǎn)的單鏈表（頭指針為h）為空的條件是【A】。A.h==NULLB.h->next==NULLC.h->next==hD.h!=NULL帶頭結(jié)點(diǎn)的單鏈表（頭指針為h）為空的條件是【B】。A.h==NULLB.h->next==NULLC.h->next==hD.h!=NULL帶頭結(jié)點(diǎn)的循環(huán)雙向鏈表（頭指針為L(zhǎng)）為空的條件是【D】。A.L==NULL B.L->next->prior==NULLC.L->prior==NULL D.L->next==L非空的循環(huán)單鏈表（頭指針為head）的尾結(jié)點(diǎn)（由p指向）滿(mǎn)足【C】。A.p->next==NULLB.p==NULLC.p->next==headD.p==head設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用【A】最節(jié)省時(shí)間。A.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表 D.單鏈表若某線(xiàn)性表最常用的操作存取任意指定序號(hào)的元素和在表尾進(jìn)行插入和刪除，則選用【A】的存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表 8.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D.單循環(huán)鏈表在n個(gè)結(jié)點(diǎn)的線(xiàn)性表的順序?qū)崿F(xiàn)中，算法的時(shí)間復(fù)雜度為0(1)的操作是【A】。訪(fǎng)問(wèn)第i個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)刪除第i個(gè)結(jié)點(diǎn) D.以上都不對(duì)若長(zhǎng)度為n的線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，在第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為【C】。A.O(0) B.0(1) C.0(n) D.0(n2)對(duì)于順序存儲(chǔ)的線(xiàn)性表，訪(fǎng)問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為【C】。A.O(n)O(n)B.0(n)0(1) C.0(1)0(n) D.0(1)0(1)線(xiàn)性表以鏈?zhǔn)椒绞酱鎯?chǔ)，訪(fǎng)問(wèn)第i個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為【C】。A.0(i) B.0(1) C.0(n) D.0(i-1)循環(huán)鏈表H尾結(jié)點(diǎn)p的特點(diǎn)是【A】。A.p->next==HB.p->next==H->nextC.p==H D.p==H->next二、 判斷題【X】1.取線(xiàn)性表的第i個(gè)元素的時(shí)間同i的大小有關(guān)?！綳】2.線(xiàn)性表中每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼?！綳】3.順序存儲(chǔ)方式只能用于存儲(chǔ)線(xiàn)性結(jié)構(gòu)?！綳】4.線(xiàn)性表采用鏈?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)。三、 填空題向一個(gè)長(zhǎng)度為n的順序表中的第i個(gè)元素之前插入一個(gè)元素時(shí)，需要向后移動(dòng)_M+1個(gè)元素。在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素時(shí)，需要向前移動(dòng)n-i個(gè)元素。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是簡(jiǎn)化插入、刪除算法 。在單鏈中要?jiǎng)h除某一指定結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。訪(fǎng)問(wèn)單鏈表中的結(jié)點(diǎn)，必須沿著指針域依次進(jìn)行。在雙鏈表中每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向直接前驅(qū)結(jié)點(diǎn) ，一個(gè)指向直接后繼結(jié)點(diǎn)。在 —鏈表中，刪除最后一個(gè)結(jié)點(diǎn)的算法時(shí)間復(fù)雜度為0(1)。訪(fǎng)問(wèn)一個(gè)線(xiàn)性表中具有給定值的時(shí)間復(fù)雜度的數(shù)量級(jí)。由n個(gè)數(shù)據(jù)元素生成一個(gè)順序表，若每次都調(diào)用插入算法把一個(gè)元素插入到表頭，則TOC\o"1-5"\h\z整個(gè)算法的時(shí)間復(fù)雜度為，若每次都調(diào)用插入算法把一個(gè)元素插入到表尾，則整個(gè)算法的時(shí)間復(fù)雜度為0(n2) 。在 鏈表中，可以用表尾指針代替表頭指針。根據(jù)n個(gè)數(shù)據(jù)元素建立對(duì)應(yīng)的順序表和單鏈表存儲(chǔ)結(jié)構(gòu)，其算法的時(shí)間復(fù)雜度最好的情況是 ，最壞的情況是 。求線(xiàn)性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的長(zhǎng)度的算法時(shí)間復(fù)雜度分別是 0(1) 和0(n)。在一個(gè)帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過(guò)程是否相同？ 。在一個(gè)不帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過(guò)程是否相同？ 。四、 簡(jiǎn)答題闡述順序表和鏈表存儲(chǔ)方式的特點(diǎn)。答：順序表存儲(chǔ)方式為數(shù)據(jù)分配連續(xù)的存儲(chǔ)單元，數(shù)據(jù)元素按邏輯順序依次存儲(chǔ)到相應(yīng)存儲(chǔ)單元中，使得邏輯相鄰的數(shù)據(jù)元素物理也相鄰，因此可以實(shí)現(xiàn)隨機(jī)訪(fǎng)問(wèn)線(xiàn)性表的數(shù)據(jù)元素，即數(shù)據(jù)訪(fǎng)問(wèn)的時(shí)間復(fù)雜度為0(1)。鏈表存儲(chǔ)方式分配的存儲(chǔ)單元可以不連續(xù)，通過(guò)每個(gè)結(jié)點(diǎn)的指針域來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，只能順序訪(fǎng)問(wèn)線(xiàn)性表中的數(shù)據(jù)元素。若頻繁地對(duì)一個(gè)線(xiàn)性表進(jìn)行插入和刪除操作，則該線(xiàn)性表宜采用何種存儲(chǔ)結(jié)構(gòu)，為什么？答：若頻繁地對(duì)一個(gè)線(xiàn)性表進(jìn)行插入和刪除操作，則該線(xià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)系。在單鏈表、雙向循環(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ù)雜度為0(n)，雙循環(huán)鏈表刪除P結(jié)點(diǎn)的時(shí)間復(fù)雜度為0(1)。對(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ì)題已知一個(gè)線(xiàn)性表用含頭結(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);}已知一個(gè)順序表L，其中的元素按值遞增有序排列，設(shè)計(jì)一個(gè)算法插入一個(gè)值為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;}寫(xiě)一個(gè)算法，從順序表中刪除值為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ì)列一、單選題對(duì)于棧操作數(shù)據(jù)的原則是【C】。A.先進(jìn)先出 B.后進(jìn)后出C.后進(jìn)先出 D.不分順序隊(duì)列的先進(jìn)先出特征是指【A】。最后插入隊(duì)列的元素總是最后被刪除當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先每當(dāng)有刪除操作時(shí)，總要先做一次插入操作每次從隊(duì)中刪除的元素總是最早插入的元素與順序棧相比較，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是【A】。A.通常不會(huì)出現(xiàn)棧滿(mǎn)的情況8.插入操作更容易實(shí)現(xiàn)C.通常不會(huì)出現(xiàn)?？盏那闆rD.刪除操作更容易實(shí)現(xiàn)棧和隊(duì)列的共同點(diǎn)是【C】。A.都是先進(jìn)先出 B.都是后進(jìn)后出C.只允許在端點(diǎn)處進(jìn)行插入和刪除D.無(wú)共同點(diǎn)棧的特點(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ǔ)的線(xiàn)性結(jié)構(gòu) B.鏈?zhǔn)酱鎯?chǔ)的線(xiàn)性結(jié)構(gòu)C.限制存取點(diǎn)的線(xiàn)性結(jié)構(gòu)D.限制存取點(diǎn)的非線(xiàn)性結(jié)構(gòu)④⑤A.3,2,1,4B.3,2,4,1C.4,2,3,1 D.1,2,3,4用單鏈表表示的鏈隊(duì)列的隊(duì)頭在鏈表的【A】。A.鏈頭B.鏈尾 C.鏈中 D.都不是設(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,5輸入序列是ABC，若輸出序列變?yōu)镃BA，經(jīng)過(guò)的棧操作為【B】。push,pop,push,pop,push,poppush,push,push,pop,pop,poppush,push,pop,pop,push,poppush,pop,push,push,pop,pop棧在【D】應(yīng)用。A.遞歸調(diào)用 B.函數(shù)調(diào)用C.表達(dá)式求值D.A,B,C設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)的算法，采用【D】數(shù)據(jù)結(jié)構(gòu)最佳。A.線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu) B.隊(duì)列C.線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D.棧允許對(duì)隊(duì)列進(jìn)行的操作有【D】。A.對(duì)隊(duì)列中的元素排序B.取出最近進(jìn)隊(duì)的元素C.在隊(duì)頭之前插入元素D.刪除隊(duì)頭元素對(duì)于循環(huán)隊(duì)列【D】。無(wú)法判斷隊(duì)列是否為空 B.無(wú)法判斷隊(duì)列是否為滿(mǎn)C.隊(duì)列不可能滿(mǎn) D.以上說(shuō)法都不對(duì)隊(duì)列存放在A[0..M-1]中，則入隊(duì)時(shí)的操作為【B】。A.rear=rear+1 B.rear=(rear+1)%MC.rear=(rear+1)%(M+1)D.rear=(rear+1)%(M-1)隊(duì)列存放在A[0..M-1]中，則出隊(duì)時(shí)的操作為【B】。A.front=front+1 B.front=(front+1)%MC.front=(front+1)%(M+1)D.front=(front+1)%(M-1)循環(huán)隊(duì)列的最大容量為M，則隊(duì)空的條件是【A】。A.rear==front B.(rear+1)%M==frontC.rear+1==front D.(rear-1)%M==front循環(huán)隊(duì)列的最大容量為M，則隊(duì)滿(mǎn)的條件是【B】。A.rear==front B.(rear+1)%M==frontC.rear+1==front D.(rear-1)%M==front二、判斷題【X】1.隊(duì)列在函數(shù)調(diào)用時(shí)必不可少，因此遞歸離不開(kāi)隊(duì)列?！尽薄?.棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞健！尽薄?.設(shè)尾指針的循環(huán)鏈表表示隊(duì)列，則入隊(duì)和出隊(duì)算法的時(shí)間復(fù)雜度為0(1)?！綳】4.隊(duì)列邏輯上是一個(gè)上端和下端既能增加又能減少的線(xiàn)性表?！?】5.在鏈隊(duì)列中，即使不設(shè)置尾指針也能進(jìn)行入隊(duì)操作?！尽薄?.棧和隊(duì)列度是限制存取點(diǎn)的線(xiàn)性結(jié)構(gòu)?！綳】7.即使對(duì)不含相同元素的同一輸入序列進(jìn)行兩組不同的合法的入棧和出棧操作，所得的輸出序列一定相同?！尽薄?.棧是實(shí)現(xiàn)函數(shù)調(diào)用所必需的數(shù)據(jù)結(jié)構(gòu)?！尽薄?.順序隊(duì)列中的元素個(gè)數(shù)，可以根據(jù)隊(duì)首指針和隊(duì)尾指針的值計(jì)算出來(lái)。三、 填空題TOC\o"1-5"\h\z循環(huán)隊(duì)列的引入，目的是為了克月 。區(qū)分循環(huán)隊(duì)列的空與滿(mǎn)有3種方法，它們是少用一個(gè)元素、設(shè)空滿(mǎn)標(biāo)志、用計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù) 。棧和隊(duì)列的區(qū)別是棧只能在表一端進(jìn)行插入和刪除操作，隊(duì)列限制在表的一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作 。一個(gè)棧的輸入序列是12345,則棧的輸出序列43512是 。設(shè)棧采取順序存儲(chǔ)結(jié)構(gòu)，棧中已有i-1個(gè)元素，則第i個(gè)元素進(jìn)棧操作的算法時(shí)間復(fù)雜度是O(1) 。若用不帶頭結(jié)點(diǎn)的單鏈表表示棧，則創(chuàng)建一個(gè)空棧要執(zhí)行的操作 —。從循環(huán)隊(duì)列中刪除一個(gè)元素的操作是 。從循環(huán)隊(duì)列中插入一個(gè)元素的操作是 。判斷鏈隊(duì)列中只有一個(gè)結(jié)點(diǎn)的條件是 。如果棧的最大長(zhǎng)度難以估計(jì)，最好使用鏈棧。四、 簡(jiǎn)答題為什么說(shuō)棧是一種后進(jìn)先出表？答：因?yàn)闂Ｊ窍薅ㄔ诒淼囊欢诉M(jìn)行插入和刪除操作，所以后入棧的數(shù)據(jù)元素總是先出棧，所以說(shuō)棧是一種后進(jìn)先出表。對(duì)于一個(gè)棧，其輸入序列是A,B,C,試給出全部可能的輸出序列。答：可能的出棧序列是：ABC、ACB、BAC、BCA、CBA。何謂隊(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ì)操作：Q.rear=(Q.rear+1)%MSize出隊(duì)操作：Q.front=(Q.front+1)%MSize隊(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)。簡(jiǎn)述線(xiàn)性表、棧和隊(duì)列的異同？答：棧和隊(duì)列都是操作位置受限的線(xiàn)性表，即對(duì)插入和刪除操作的位置加以限制。棧是僅允許在表的一端進(jìn)行插入和刪除操作的線(xiàn)性表，因而是后進(jìn)先出表。隊(duì)列是允許在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線(xiàn)性表，因而是先進(jìn)先出表。線(xiàn)性表可以在任何位置進(jìn)行插入和刪除操作。五、算法設(shè)計(jì)題設(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);}設(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); 〃此時(shí)必須用另一個(gè)變量y，才能保留棧底元素在x中Push(st,y);}DestroyStack(tmpst);return(x);}設(shè)計(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;}第四章串一、 單選題串是任意有限個(gè)【D】。A.符號(hào)構(gòu)成的集合 B.符號(hào)構(gòu)成的序列C.字符構(gòu)成的集合 D.字符構(gòu)成的序列串是一種特殊的線(xiàn)性表，其特殊性體現(xiàn)在【B】。A.可以順序存儲(chǔ) B.數(shù)據(jù)元素是一個(gè)字符C.數(shù)據(jù)元素可以使多個(gè)字符 D.可以鏈接存儲(chǔ)兩個(gè)串相等必有串長(zhǎng)度相等且【B】。A.串的各位置字符任意 B.串中各位置字符均對(duì)應(yīng)相等C.兩個(gè)串含有相同的字符 D.兩個(gè)串所含字符任意設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)著【B】。A.連接 B.模式匹配C.求子串 D.求串長(zhǎng)二、 填空空串是 。一個(gè)串中 任意連續(xù)字符組成的子序列 稱(chēng)為該串的子串。設(shè)s="abcd”，則執(zhí)行語(yǔ)句s2=Substr(s,2,2)后，s2= “bc”?？瞻状怯梢粋€(gè)或多個(gè)空格字符組成的串 ，其長(zhǎng)度等于其所包含的空格字符的個(gè)數(shù)。第五章數(shù)組一、 單選題一維數(shù)組與線(xiàn)性表的區(qū)別是【A】。前者長(zhǎng)度固定，后者長(zhǎng)度可變后進(jìn)長(zhǎng)度固定，前者長(zhǎng)度可變兩者長(zhǎng)度均固定 D.兩者長(zhǎng)度均可變多維數(shù)組的數(shù)組元素之間的關(guān)系，【A】。A.是線(xiàn)性的B.是樹(shù)型的既是線(xiàn)性的，又是樹(shù)型的既不是線(xiàn)性的，也不是樹(shù)型的設(shè)有數(shù)組A[8][10]，每個(gè)元素占3個(gè)存儲(chǔ)單元，存放該數(shù)組的存儲(chǔ)單元數(shù)為【C】。A,80B.100C.240D.270設(shè)有數(shù)組A[8][10]，每個(gè)元素占3個(gè)存儲(chǔ)單元，首地址為SA，則元素[7][5]的起始地址是【D】。A.SA+141 B.SA+144 C.SA+222D.SA+225設(shè)有一個(gè)n*n的對(duì)稱(chēng)矩陣，采用壓縮存儲(chǔ)，則存入內(nèi)存的元素個(gè)數(shù)為【C】。A.n*nB.n*n/2 C.n*(n+1)/2 D,(n+1)2/2設(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-1 B.i(i-1)/2+jC.i(i+1)/2+j-1 D.i(i+1)/2+j稀疏矩陣一般的壓縮方法有兩種，即【C】。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表 D.散列和十字鏈表設(shè)有一個(gè)10*10的對(duì)稱(chēng)矩陣A，以行主次序進(jìn)行壓縮存儲(chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，a11的地址是1，則A8,5的起始地址是【B】。 ’A.13 B.33 C.18 D.40二、 解答題1.設(shè)數(shù)組A[50][80]，其基地址為2000，每個(gè)元素占2個(gè)存儲(chǔ)單元，以行序位主序順序存儲(chǔ)，回答下列問(wèn)題：該數(shù)據(jù)組由多少元素？該數(shù)組占用多少存儲(chǔ)單元？數(shù)組元素a[30][30]的存儲(chǔ)地址是多少？答：該數(shù)組有：50*80=4000個(gè)元素該數(shù)組占用4000*4=8000個(gè)存儲(chǔ)單元loc(30,30)=2000+(30*80+30)*2=2000+4860=6860第六章樹(shù)與二叉樹(shù)一、單選題有關(guān)二叉樹(shù)下列說(shuō)法正確的是【B】。A.二叉樹(shù)的度為2 B.一棵二叉樹(shù)的度可以小于2C.一棵二叉樹(shù)至少有一個(gè)結(jié)點(diǎn)的度為2 D.二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度為2利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是【C】。A.指向最左孩子 B.指向最右孩子C.空 D.非空若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)為【B】。TOC\o"1-5"\h\zA.9 B.11C.15 D.不確定一棵二叉樹(shù)有1001個(gè)結(jié)點(diǎn)，其中葉結(jié)點(diǎn)的個(gè)數(shù)為【D】。A.250 B.490C.254 D.不確定一棵完全二叉樹(shù)有1001個(gè)結(jié)點(diǎn)，其中葉結(jié)點(diǎn)的個(gè)數(shù)為【D】。A.250 B.500C.254 D.以上答案均不對(duì)一棵具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為【C】。A.11 B.11C.11至1025之間D.10至1024之間一棵124個(gè)葉結(jié)點(diǎn)的完全樹(shù)，最多具有【B】個(gè)結(jié)點(diǎn)。A.247 B.248C.249 D.251一棵具有10個(gè)葉結(jié)點(diǎn)的二叉樹(shù)具有【B】度為2的結(jié)點(diǎn)。A.8 B.9C.10 D.11已知一棵完全二叉樹(shù)有625個(gè)結(jié)點(diǎn)，葉結(jié)點(diǎn)的個(gè)數(shù)為【C】。A.311 B.312C.313 D.其它一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高h(yuǎn)為【AB】。A.Llog2n」+1 B.「log2n+1]C.log2n+1 D.log2n-1由8個(gè)權(quán)值構(gòu)造一棵哈夫曼樹(shù)，該哈夫曼樹(shù)有【A】個(gè)結(jié)點(diǎn)。TOC\o"1-5"\h\zA.15 B.16C.17 D.14由3個(gè)結(jié)點(diǎn)可以構(gòu)造【D】種不同的二叉樹(shù)。A.2 B.3C.4 D.5樹(shù)最適合用來(lái)表示【C】。A.有序數(shù)據(jù)元素 B.無(wú)序數(shù)據(jù)元素C.元素間具有分支層次關(guān)系的數(shù)據(jù) D.元素間無(wú)聯(lián)系的數(shù)據(jù)下圖中4棵二叉樹(shù)中，【C】不是完全二叉樹(shù)。A. B. C. D.某二叉樹(shù)的先序遍歷序列和后序便利序列正好相反，則該二叉樹(shù)一定是【A】。A.空或只有一個(gè)結(jié)點(diǎn) B.完全二叉樹(shù)C.二叉排序樹(shù) D.高度等于其結(jié)點(diǎn)數(shù)在一棵非空二叉樹(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)任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序【A】。A.不發(fā)生上改變 B.發(fā)生改變C.不能確定 D.以上都不對(duì)一棵滿(mǎn)二叉樹(shù)，m個(gè)葉結(jié)點(diǎn)，n個(gè)結(jié)點(diǎn)，深度為^則【D】。A.n=h+m B.h+m=2nC.m=h-1 D.n=2h-1設(shè)n，m是二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m之前的條件是【C】。A.n在m右方 B.n是m的祖先C.n在m左方 D.n是m的子孫設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類(lèi)二叉樹(shù)中包含的結(jié)點(diǎn)數(shù)最少為【B】。A.2h B.2h-1 C.2h+1 D.h+1二、 判斷題【X】1.二叉樹(shù)是一般樹(shù)的特殊樹(shù)型?！尽薄?.樹(shù)與二叉樹(shù)是兩種不同的樹(shù)形結(jié)構(gòu)?！綳】3.對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度為log2n?！尽薄?.完全二叉樹(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)離根最近。【”】8.哈夫曼樹(shù)的結(jié)點(diǎn)個(gè)數(shù)不偶數(shù)。三、 填空題深度為k的完全二叉樹(shù)至少有 個(gè)結(jié)點(diǎn)，至多有個(gè)結(jié)點(diǎn)。在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則有n0=n2+1 。一棵二叉樹(shù)第i層最多有2i-1 個(gè)結(jié)點(diǎn)，一棵有n個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)共有31個(gè)結(jié)點(diǎn)，共有2K-1 個(gè)葉結(jié)點(diǎn)。根據(jù)二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)共有 5 種不同形態(tài)，它們分別是.

TOC\o"1-5"\h\z在在一棵完全二叉樹(shù)中，編號(hào)i和j的兩個(gè)結(jié)點(diǎn)處于同一層的條件是」logi==JlogjI o^2 ^2具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，共有 個(gè)空指針域。具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，如果有m個(gè)葉結(jié)點(diǎn)，則一定有m-1個(gè)度為2的結(jié)點(diǎn)，有 一個(gè)度為1的結(jié)點(diǎn)。在二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，指針p所指結(jié)點(diǎn)為葉結(jié)點(diǎn)的條件是p->lchild=NULL&&p->rchild==NULL。TOC\o"1-5"\h\z二叉樹(shù)的先序序列和中序序列相等的條件是任何結(jié)點(diǎn)至多只有右子樹(shù) 。有一棵如下圖所示的樹(shù)，回答下列問(wèn)題：這棵樹(shù)的根結(jié)點(diǎn)是 a。這棵樹(shù)的葉子結(jié)點(diǎn)是 。結(jié)點(diǎn)c的度為—2 o這棵樹(shù)的深度是 4 。結(jié)點(diǎn)c的孩子結(jié)點(diǎn)是e,f。結(jié)點(diǎn)c的雙親結(jié)點(diǎn)是 a。這棵樹(shù)的度是 。樹(shù)中結(jié)點(diǎn)的最大度沒(méi)有限制，二叉樹(shù)結(jié)點(diǎn)的最大樹(shù)與二叉樹(shù)的兩個(gè)主要差別是度限定為2、樹(shù)的結(jié)點(diǎn)無(wú)左右之分，二叉樹(shù)的的結(jié)點(diǎn)有左右之分。樹(shù)中結(jié)點(diǎn)的最大度沒(méi)有限制，二叉樹(shù)結(jié)點(diǎn)的最大樹(shù)中任一結(jié)點(diǎn)允許有0個(gè)或多個(gè)孩子個(gè)孩子結(jié)點(diǎn)，除根結(jié)點(diǎn)之外，其余結(jié)點(diǎn)有1個(gè)雙親結(jié)點(diǎn)。四、簡(jiǎn)答題設(shè)有如下圖所示的二叉樹(shù)，給出其前序、中序和后序遍歷結(jié)果。答：前序序列：eadcbifghj中序序列：abcdiefhgj后序序列：bcidahjgfe2.給出下圖所示的樹(shù)的二叉樹(shù)表示。答：下圖為其樹(shù)的二叉樹(shù)表示。3.有一份電文共有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è)字符的哈夫曼編碼。字符編碼：a：011b：10c：00d：010e：114.假設(shè)一棵二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)，如下圖所示。0 5 10 15 20eafdgcjhib回答些列問(wèn)題：①畫(huà)出二叉樹(shù)表示。

寫(xiě)出先序、中序和后序遍歷結(jié)果寫(xiě)出結(jié)點(diǎn)c的雙親結(jié)點(diǎn)和左、右孩子結(jié)點(diǎn)畫(huà)出此二叉樹(shù)還原成森林的圖答：①二叉樹(shù)表示如下圖所示。先序序列為：eadcbjfghi中序序列為：acbdjefhgi后序序列為：bcjdahigfe結(jié)點(diǎn)。的雙親結(jié)點(diǎn)是d，左孩子為b，無(wú)右孩子該二叉樹(shù)對(duì)應(yīng)的森林為第七章圖一、 單選題在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊的【C】倍。TOC\o"1-5"\h\zA.1/2 B.1 C.2 D.4在一個(gè)有向圖中，所有頂點(diǎn)的入度數(shù)之和等于所有頂點(diǎn)的出度之和的【B】倍。A.1/2 B.1 C.2 D.4一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有【C】條邊。A.n B.n(n-1) C.n(n-1)/2 D.2n具有4個(gè)頂點(diǎn)的無(wú)向完全圖有【A】條邊。A.6 B.12 C.16 D.20具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有【A】條邊才能確保是一個(gè)連通圖。A.5 B.6 C.7 D.8一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是【D】。A.n B.(n-1)2 C.(n-1) D.n2對(duì)某個(gè)無(wú)向圖的鄰接矩陣來(lái)說(shuō)，【A】。第i行上的非0元素個(gè)數(shù)等于第i列上非0元素個(gè)數(shù)矩陣中非0元素個(gè)數(shù)等于圖中的邊數(shù)第i行、第i列上非0元素個(gè)數(shù)等于頂點(diǎn)vi的度數(shù)矩陣中非全0行的行數(shù)等于圖中的頂點(diǎn)數(shù)對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的大小為【①A】；所有鄰接表中結(jié)點(diǎn)總數(shù)為【②C】。A.n B.n+1 C.n-1D.n2A.e/2B.eC.2eD.n+e二、 判斷題【X】1.n個(gè)頂點(diǎn)的無(wú)向圖至多有n(n-1)條邊。【”】2.有向圖中，各頂點(diǎn)的入度之和等于各頂點(diǎn)的出度之和?！尽薄?.鄰接矩陣只存儲(chǔ)了邊的信息，沒(méi)有存儲(chǔ)頂點(diǎn)的信息。【X]4.連通分量是無(wú)向圖的極小連通子圖。?！綳]5.如果表示有向圖的鄰接矩陣是對(duì)稱(chēng)的，則該有向圖一定是完全有向圖。【X]6.如果表示圖的鄰接矩陣是對(duì)稱(chēng)的，則該圖一定是無(wú)向圖。【”】7.如果表示圖的鄰接矩陣不是對(duì)稱(chēng)的，則該圖一定是有向圖。三、 填空題有n個(gè)頂點(diǎn)的無(wú)向圖最多有 條邊。具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖至少有條邊。具有n個(gè)頂點(diǎn)的有向圖最多有 條邊。一個(gè)圖的臨接矩陣 表示法是唯一的，而鄰接表 表示法是不唯一的。具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為45 。在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可。已知一個(gè)有向圖采用鄰接矩陣表示，計(jì)算第i個(gè)頂點(diǎn)的入度的方法是 求第i列非0元素個(gè)數(shù)。已知一個(gè)有向圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的弧的方法是將第i行對(duì)應(yīng)的1置成0 。對(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ù) 。對(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ù)。無(wú)向圖的連通分量指無(wú)向圖中最大連通子圖 。若無(wú)向圖有m條邊，，則表示該無(wú)向圖的鄰接表中有—2m 結(jié)點(diǎn)。四、簡(jiǎn)答題從占用的存儲(chǔ)空間來(lái)看，對(duì)于稠密圖和稀疏圖，采用鄰接矩陣和鄰接表那個(gè)更好些？答：從占用存儲(chǔ)空間看，稠密圖采用鄰接矩陣更好，稀疏圖采用鄰接表更好。用鄰接矩陣表示圖時(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。第九章查找一、單選題順序查找法適合于存儲(chǔ)結(jié)構(gòu)為【B】的查找表。散列存儲(chǔ) B.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C.壓縮存儲(chǔ) D.索引存儲(chǔ)對(duì)查找表進(jìn)行折半查找時(shí)，要求查找表必須【B】。以順序方式存儲(chǔ)以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列以鏈?zhǔn)椒绞酱鎯?chǔ)以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列采用順序查找法查找長(zhǎng)度為n的查找表時(shí)，每個(gè)元素查找的平均查找長(zhǎng)度為【C】。A.nB.n/2 C.(n+1)/2 D,(n-1)/2采用折半查找法查找長(zhǎng)度為n的查找表時(shí)，每個(gè)元素查找的平均查找長(zhǎng)度為【D】。A.O(n2) B.O(nlog2n)C.O(n) D.O(log2n)采用分塊查找時(shí)，若查找表中有625個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)對(duì)索引表和塊都采用順序查找，每塊應(yīng)分【B】個(gè)結(jié)點(diǎn)最佳。A.10 B.25 C.6 D.625查找n個(gè)元素的有序表時(shí)，最有效的查找方法是【C】。順序查找 B.分塊查找 C.折半查找 D.二叉排序樹(shù)如果要求一個(gè)查找表既能快速查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用【A】查找方法。A.分塊 B.順序 C.折半 D.散列在關(guān)鍵字隨機(jī)分布的情況下，用二叉排序樹(shù)的方法進(jìn)行查找，其查找長(zhǎng)度與【B】量級(jí)相當(dāng)。順序查找 B.折半查找 C.分塊查找 D.前三個(gè)都不正確查找效率最高的二叉排序樹(shù)是【C】。所有結(jié)點(diǎn)的左子樹(shù)都為空的二叉排序樹(shù)所有結(jié)點(diǎn)的右子樹(shù)都為空的二叉排序樹(shù)平衡二叉樹(shù)沒(méi)有左子樹(shù)的二叉排序樹(shù)假定有k個(gè)關(guān)鍵字互為同義詞，若用線(xiàn)性探測(cè)再散列法把這k個(gè)關(guān)鍵字的紀(jì)錄插入到散列表中，至少要進(jìn)行【D】次探測(cè)。A.k-1B.kC.k+1 D.k(k+1)/2以下說(shuō)法錯(cuò)誤的是【B】。散列法存儲(chǔ)的基本思想是由記錄關(guān)鍵字決定數(shù)據(jù)存儲(chǔ)地址散列法的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含任何指針裝填因子是散列法的一個(gè)重要參數(shù)，它反映了散列表的裝填程度散列表的查找效率取決于散列造表是的散列函數(shù)和沖突處理的方法散列表的平均查找長(zhǎng)度【A】。與沖突處理方法有關(guān)而與表的長(zhǎng)度無(wú)關(guān)與沖突處理方法無(wú)關(guān)而與表的長(zhǎng)度有關(guān)與沖突處理方法有關(guān)且與表的長(zhǎng)度有關(guān)與沖突處理方法無(wú)關(guān)且與表的長(zhǎng)度無(wú)關(guān)二、 判斷題【”】1.順序查找法適合于順序或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的查找表。【X】2.順序查找法只能在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行?！綳】3.二分查找可以在有序的雙向鏈表上進(jìn)行。【X】4.在二叉排序樹(shù)中，每個(gè)結(jié)點(diǎn)的關(guān)鍵字比左孩子的關(guān)鍵字大，比右孩子的關(guān)鍵字小。【X】5.每個(gè)結(jié)點(diǎn)的關(guān)鍵字都比左孩子的關(guān)鍵字大，比右孩子的關(guān)鍵字小，這樣的二叉樹(shù)都是二叉排序樹(shù)?！?】6.哈希存儲(chǔ)法只能存儲(chǔ)數(shù)據(jù)元素的值，不能存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系?！綳】7.哈希沖突是指同一個(gè)關(guān)鍵字對(duì)應(yīng)多個(gè)不同的哈希地址。三、 填空題順序查找含n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為n次；若查找不成功，則比較關(guān)鍵字的次數(shù)為n+1次。TOC\o"1-5"\h\z在含有n個(gè)元素的有序順序表中進(jìn)行二分查找，最大的比較次數(shù)是.1logn+1 。2用二分查找一個(gè)查找表，該查找表必須具有的特點(diǎn)是順序存儲(chǔ)且關(guān)鍵字有序 。分塊查找發(fā)將待查找的表均勻地分成若干塊且塊中諸記錄的順序可以是任意的，但塊與塊之間 關(guān)鍵字有序 。在分塊查找方法中，首先查找關(guān)鍵字表，然后再查找相應(yīng)的對(duì)應(yīng)的塊 。用二叉排序樹(shù)在n個(gè)元素中進(jìn)行查找，最壞情況下查找時(shí)間復(fù)雜度為O(n)，最好情況的查找時(shí)間復(fù)雜度為 。折半查找的存儲(chǔ)結(jié)構(gòu)僅限于順序存儲(chǔ)結(jié)構(gòu)，且是 。一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序 樹(shù)而變成有序序列，構(gòu)造樹(shù)的過(guò)程即是對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。用二叉排序樹(shù)查找，在最壞的情況下，平均查找長(zhǎng)度為(n+1)/2 ，最好的情況下，平均查找長(zhǎng)度為 。在哈希函數(shù)H(key)=key/p中，p最好取 。哈希表是誦過(guò)將關(guān)鍵字按選定的哈希函數(shù)和沖突處理方法，把記錄按關(guān)鍵字轉(zhuǎn)換為地址進(jìn)行存儲(chǔ)的存儲(chǔ)表，哈希方法的關(guān)鍵是選擇好的哈希函數(shù)和沖突處理的方法。一個(gè)好的哈希函數(shù)其轉(zhuǎn)換地址應(yīng)盡可能均勻 ，而且函數(shù)運(yùn)算應(yīng)盡可能 。四、解答題1、畫(huà)出對(duì)長(zhǎng)度為10的右序表進(jìn)行折半查找的一棵判定樹(shù)，并求