數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)試題和答案解析12級(jí)

./一、選擇題。<每小題2分,共40分><1>計(jì)算機(jī)識(shí)別.存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為____A____。A.數(shù)據(jù) B.數(shù)據(jù)元素 C.數(shù)據(jù)結(jié)構(gòu) D.數(shù)據(jù)類型<2>數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的____A_____及它們之間的聯(lián)系。A.存儲(chǔ)和邏輯結(jié)構(gòu)B.存儲(chǔ)和抽象C.理想和抽象D.理想與邏輯<3>不是數(shù)據(jù)的邏輯結(jié)構(gòu)是____A______。A.散列結(jié)構(gòu)B.線性結(jié)構(gòu)C.樹結(jié)構(gòu)D.圖結(jié)構(gòu)<4>數(shù)據(jù)結(jié)構(gòu)被形式地定義為<D,R>,其中D是____B_____的有限集,R是____C_____的有限集。A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.邏輯結(jié)構(gòu)<5>組成數(shù)據(jù)的基本單位是____A______。A.數(shù)據(jù)項(xiàng) B.數(shù)據(jù)類型 C.數(shù)據(jù)元素 D.數(shù)據(jù)變量<6>設(shè)數(shù)據(jù)結(jié)構(gòu)A=<D,R>,其中D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},則數(shù)據(jù)結(jié)構(gòu)A是____A______。A.線性結(jié)構(gòu) B.樹型結(jié)構(gòu) C.圖型結(jié)構(gòu) D.集合<7>數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí),物理地址與邏輯地址相同并且是連續(xù)的,稱之為___C____。A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲(chǔ)結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)<8>在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為___A____。A.內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)B.靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu)C.線性結(jié)構(gòu)與非線性結(jié)構(gòu) D.緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)<9>對(duì)一個(gè)算法的評(píng)價(jià),不包括如下____B_____方面的內(nèi)容。A.健壯性和可讀性B.并行性C.正確性D.時(shí)空復(fù)雜度<10>算法分析的兩個(gè)方面是__A____。A.空間復(fù)雜性和時(shí)間復(fù)雜性B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性<11>線性表是具有n個(gè)___C_____的有限序列〔n≠0>。A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)<12>線性表的存儲(chǔ)結(jié)構(gòu)是一種____B____的存儲(chǔ)結(jié)構(gòu)。A.隨機(jī)存取B.順序存取C.索引存取D.HASH存取<13>在一個(gè)長度為n的順序表中,向第i個(gè)元素〔1≤i≤n＋１之前插入一個(gè)新元素時(shí),需要向后移動(dòng)____B____個(gè)元素。A.n-iB.n-i+1C.n-i-1D.i<14>鏈表是一種采用____B____存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表；A.順序B.鏈?zhǔn)紺.星式D.網(wǎng)狀<15>下面關(guān)于線性表的敘述錯(cuò)誤的是___D_____。A.線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間 B.線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間C.線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)D.線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)<16>設(shè)指針q指向單鏈表中結(jié)點(diǎn)A,指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B,指針s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A和結(jié)點(diǎn)B之間插入結(jié)點(diǎn)X的操作序列為__B______。A.s->next=p->next；p->next=-s； B.q->next=s；s->next=p；C.p->next=s->next；s->next=p； D.p->next=s；s->next=q；<17>設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A,則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為___A_____。A.p->next=p->next->next B.p=p->next C.p=p->next->next D.p->next=p<18>下列說法哪個(gè)正確？____D______A.堆棧是在兩端操作、先進(jìn)后出的線性表B.堆棧是在一端操作、先進(jìn)先出的線性表C.隊(duì)列是在一端操作、先進(jìn)先出的線性表D.隊(duì)列是在兩端操作、先進(jìn)先出的線性表<19>棧和隊(duì)列的共同點(diǎn)是_____C_______。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)<20>棧與一般線性表的區(qū)別主要在_____D______。A、元素個(gè)數(shù)B、元素類型C、邏輯結(jié)構(gòu)D、插入、刪除元素的位置<21>鏈棧與順序棧相比,比較明顯的優(yōu)點(diǎn)是_____D_____。A、插入操作更加方便B、刪除操作更加方便C、不會(huì)出現(xiàn)下溢的情況D、不會(huì)出現(xiàn)上溢的情況<22>以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)___D______。A.隊(duì)列

B.棧

C.線性表

D.二叉樹<23>若已知一個(gè)棧的入棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pn,若p1=n,則pi為_____C______。A.i

B.B.n=i

C.n-i+1

D.不確定<24>當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)棧時(shí),假定用top==N表示棧空,則向這個(gè)棧插入一個(gè)元素時(shí),首先應(yīng)執(zhí)行____B______語句修改top指針。A.top++

B.top--

C.top=0

D.top<25>4個(gè)元素進(jìn)S棧的順序是A,B,C,D,經(jīng)運(yùn)算POP<S>后,棧頂元素是___C_______。A.A

B.B

C.C

D.D<26>一個(gè)棧的輸入序列是a,b,c,d,e,則棧的不可能的輸出序列是____C_____。A.edcba

B.decba

C.dceab

D.abcde<27>設(shè)輸入序列是1、2、3、……、n,經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n,則輸出序列中第i個(gè)輸出元素是____C______。A.n-i

B.n-1-i

C.n+1-i

D.不能確定<28>字符A、B、C、D依次進(jìn)入一個(gè)棧,按出棧的先后順序組成不同的字符串,至多可以組成___B___個(gè)不同的字符串？A.15

B.14

C.16

D.21<29>設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?則刪除棧頂元素的操作序列為____D_______。A.top=top+1;

B.top=top-1;

C.top->next=top;

D.top=top->next;<30>設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素E1、E2、E3、E4、E5和E6依次通過棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6個(gè)元素出列的順序?yàn)镋2、E4、E3、E6、E5和E1,則棧S的容量至少應(yīng)該是____C_____。A.6

B.4

C.3

D.2<31>若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列,且當(dāng)前rear和front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素,再加入兩個(gè)元素后,rear和front的值分別為____B_____。A.1和5

B.2和4

C.4和2

D.5和1<32>設(shè)順序循環(huán)隊(duì)列Q[0：M-1]的頭指針和尾指針分別為F和R,頭指針F總是指向隊(duì)頭元素的前一位置,尾指針R總是指向隊(duì)尾元素的當(dāng)前位置,則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為____C_____。A.R-F

B.F-R

C.<R-F+M>%M

D.<F-R+M>%M

<33>設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針,指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針,指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X,則入隊(duì)列的操作序列為____C_____。A.front->next=s；front=s；

B.s->next=rear；rear=s；C.rear->next=s；rear=s；

D.s->next=front；front=s；<34>如下陳述中正確的是___A______。A.串是一種特殊的線性表B.串的長度必須大于零C.串中元素只能是字母D.空串就是空白串<35>下列關(guān)于串的敘述中,正確的是___D______。A.串長度是指串中不同字符的個(gè)數(shù)B.串是n個(gè)字母的有限序列C.如果兩個(gè)串含有相同的字符,則它們相等D.只有當(dāng)兩個(gè)串的長度相等,并且各個(gè)對(duì)應(yīng)位置的字符都相符時(shí)才相等<36>字符串的長度是指___C______。A.串中不同字符的個(gè)數(shù)B.串中不同字母的個(gè)數(shù)C.串中所含字符的個(gè)數(shù)D.串中不同數(shù)字的個(gè)數(shù)<37>兩個(gè)字符串相等的充要條件是____C______。A.兩個(gè)字符串的長度相等B.兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等C.同時(shí)具備<A>和<B>兩個(gè)條件D.以上答案都不對(duì)<38>串是一種特殊的線性表,其特殊性體現(xiàn)在____B_______。A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符<39>設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作____B______。A.連接B.模式匹配C.求子串D.求串長<40>設(shè)串sI="ABCDEFG",s2="PQRST",函數(shù)con<x,y>返回x和y串的連接串,subs<s,i,j>返回串s的從序號(hào)i的字符開始的j個(gè)字符組成的子串,len<s>返回串s的長度,則con<subs<s1,2,1en<s2>>,subs<sl,len<s2>,2>>的結(jié)果串是__D___。A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF<41>函數(shù)substr<"DATASTRUCTURE",5,9>的返回值為___A______。A."STRUCTURE"B."DATA"C."ASTRUCTUR"D."DATASTRUCTURE"<42>設(shè)串S="IAMATEACHER!",其長度是____D______。A.16B.11C.14D.15<43>假定在一棵二叉樹中,雙分支結(jié)點(diǎn)數(shù)為15個(gè),單分支結(jié)點(diǎn)數(shù)為32個(gè),則葉子結(jié)點(diǎn)數(shù)為____B____。A.15B.16C.17D.47<44>假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18個(gè),則它的最小高度____B____。A.4B.5C.6D.18<45>在一棵二叉樹中第五層上的結(jié)點(diǎn)數(shù)最多為____C____。A.8B.15C.16D.32<46>在一棵具有五層的滿二叉樹中,結(jié)點(diǎn)總數(shù)為____A____。A.31B.32C.33D.16<47>已知8個(gè)數(shù)據(jù)元素為<34、76、45、18、26、54、92、65>,按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹后,最后兩層上的結(jié)點(diǎn)總數(shù)為____B____。A.1B.2C.D.4<48>由分別帶權(quán)為9、2、5、7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹,該樹的帶權(quán)路徑長度為____C____。A.23B.37C.44D.46<49>在樹中除根結(jié)點(diǎn)外,其余結(jié)點(diǎn)分成m<m≥0>個(gè)____A____的集合T1,T2,T3...Tm,每個(gè)集合又都是樹,此時(shí)結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn),Ti稱為T的子結(jié)點(diǎn)<1≤i≤m>。A.互不相交B.可以相交C.葉結(jié)點(diǎn)可以相交D.樹枝結(jié)點(diǎn)可以相交<50>如果結(jié)點(diǎn)A有三個(gè)兄弟,而且B是A的雙親,則B的出度是____B____。A.3B.4C.5D.1<51>在一個(gè)有向圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的____B____倍。A.1/2B.1C.2D.4<52>具有n個(gè)頂點(diǎn)的無向完全圖,邊的總數(shù)為____D____條。A.n-1B.nC.n+1D.n*<n-1>/2<53>在無向圖G的鄰接矩陣A中,若A[i,j]等于1,則A[j,i]等于____C____。A.i+jB.i-jC.1D.0<54>圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復(fù)雜性均為____A____。<訪問標(biāo)志位數(shù)組空間>A.O<n>B.O<e>C.O<n-e>D.O<n+e><55>請指出在順序表{2、5、7、10、14、15、18、23、35、41、52}中,用折半法查找關(guān)鍵碼12需做____C___次關(guān)鍵碼比較。A.2B.3C.4D.5<56>對(duì)線性表進(jìn)行折半查找時(shí),必須要求線性表____C____。A.以順序方式存儲(chǔ)B.以鏈接方式存儲(chǔ)C.以順序方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排列D.以鏈接方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排列<57>設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn),則在二叉排序樹的平均查找長度為___B_____。A.O<1> B.O<log2n> C.O<n> D.O<n2><58>依次插入序列<50,72,43,85,75,20,35,45,65,30>后建立的二叉搜索樹中,查找元素35要進(jìn)行__A___元素間的比較。A.4次 B.5次 C.7次 D.10次<59>設(shè)散列表中有m個(gè)存儲(chǔ)單元,散列函數(shù)H<key>=key%p,則p最好選擇___B_____。A.小于等于m的最大奇數(shù) B.小于等于m的最大素?cái)?shù)C.小于等于m的最大偶數(shù) D.小于等于m的最大合數(shù)<60>____D_____是HASH查找的沖突處理方法。A.求余法B.平方取中法C.二分法D.開放地址法<61>當(dāng)α的值較小時(shí),散列存儲(chǔ)通常比其他存儲(chǔ)方式具有_____B______的查找速度。A.較慢 B.較快 C.相同D.不確定<62>對(duì)線性表進(jìn)行折半查找最方便的存儲(chǔ)結(jié)構(gòu)是____B_______。A．順序表B．有序的順序表C．鏈表D．有序的鏈表<63>如果要求一個(gè)線性表既能較快的查找,又能適應(yīng)動(dòng)態(tài)變化的要求,可以采用_____D____查找方法。A．分塊B．順序C．折半D．散列<64>散列函數(shù)有一個(gè)共同性質(zhì),即函數(shù)值應(yīng)按___C______取其值域的每一個(gè)值。A．最大概率B．最小概率C．同等概率D．平均概率<65>下述排序算法中,穩(wěn)定的是___B_____。A.直接選擇排序B.直接插入排序C.快速排序D.堆排序<66>下列排序算法中,____A____需要的輔助存儲(chǔ)空間最大。A.快速排序 B.插入排序 C.希爾排序 D.基數(shù)排序<67>下列各種排序算法中平均時(shí)間復(fù)雜度為O<n2>是___D_____。A.快速排序 B.堆排序 C.歸并排序 D.冒泡排序<68>在基于關(guān)鍵碼比較的排序算法中,____C_____算法在最壞情況下,關(guān)鍵碼比較次數(shù)不高于O<nlog2n>。A.起泡排序 B.直接插入排序 C.二路歸并排序 D.快速排序<69>一組記錄為{46,79,56,38,84,40},則采用冒泡排序法按升序排列時(shí)第一趟排序結(jié)果是___B_____。A.46,79,56,38,40,84B.46,56,38,79,40,84C.38,40,46,56,84,79D.38,46,79,56,40,84<70>每次從無序表中取出一個(gè)元素,把它插入到有序表中的適當(dāng)位置,此種排序方法叫做___A_____排序。A.插入B.堆C.快速D.歸并<71>每次從無序表中挑選出一個(gè)最小或最大元素,把它交換到有序表的一端,此種排序方法叫做___B_____排序。A.插入B.堆C.快速D.歸并<72>設(shè)一組初始記錄關(guān)鍵字序列<5,2,6,3,8>,以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為____C____。 A.2,3,5,8,6 B.3,2,5,8,6 C.3,2,5,6,8 D.2,3,6,5,8<73>下列排序方法中,哪一種方法的比較次數(shù)與紀(jì)錄的初始排列狀態(tài)無關(guān)___D_____。A.直接插入排序B.起泡排序C.快速排序D.直接選擇排序<74>設(shè)有關(guān)鍵碼初始序列{Q,H,C,Y,P,A,M,S,R,D,F,X},新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}是采用____C____方法對(duì)初始序列進(jìn)行第一趟掃描的結(jié)果。A.直接插入排序B．二路歸并排序C．以第一元素為分界元素的快速排序D．基數(shù)排序<75>在待排序文件已基本有序的前提下,下述排序方法中效率最高的是__C____。A.直接插入排序B.直接選擇排序C．快速排序D．歸并排序<76>若需在O<nlog2n>的時(shí)間內(nèi)完成對(duì)數(shù)組的排序,且要求排序是穩(wěn)定的,則可選排序方法是___C_____。A.快速排序B．堆排序C．歸并排序D．直接插入排序<77>將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表,其最少的比較次數(shù)是___B_______。A．nB．2n-1C．2nD．n-1<78>下列排序算法中,____C____算法可能會(huì)出現(xiàn)下面情況：初始數(shù)據(jù)有序時(shí),花費(fèi)的間反而最多。A.堆排序B．冒泡排序C．快速排序D．SHELL排序二、填空題。<每空1分,共10分><1>數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的數(shù)據(jù)以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。<2>數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)結(jié)構(gòu)和物理結(jié)構(gòu)結(jié)構(gòu)。<3>數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：____線性數(shù)據(jù)結(jié)構(gòu)_______、____樹型結(jié)構(gòu)______和_____圖結(jié)構(gòu)______。<4>數(shù)據(jù)的物理結(jié)構(gòu)被分為___順序存儲(chǔ)______、___鏈?zhǔn)酱鎯?chǔ)_____、____索引存儲(chǔ)______和______散列表〔Hash存儲(chǔ)_____四種。<5>一種抽象數(shù)據(jù)類型包括_____變量的取值范圍_____和____操作的類別_____兩個(gè)部分。<6>數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素間的邏輯關(guān)系,數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)元素存儲(chǔ)方式或者數(shù)據(jù)元素的物理關(guān)系。<7>數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的____關(guān)系__________。當(dāng)結(jié)點(diǎn)之間存在M對(duì)N〔M：N的聯(lián)系時(shí),稱這種結(jié)構(gòu)為________網(wǎng)狀結(jié)構(gòu)________。當(dāng)結(jié)點(diǎn)之間存在1對(duì)N〔1：N的聯(lián)系時(shí),稱這種結(jié)構(gòu)為_____樹結(jié)構(gòu)__________。<8>對(duì)算法從時(shí)間和空間兩方面進(jìn)行度量,分別稱為空間復(fù)雜度和時(shí)間復(fù)雜度分析。<9>算法的效率可分為______空間_________效率和______時(shí)間_________效率。<10>for<i=1,t=1,s=0；i<=n；i++>{t=t*i；s=s+t；}的時(shí)間復(fù)雜度為___Ο<n>______。<11>線性表是n個(gè)元素的_________有限序列____________________。<12>線性表的存儲(chǔ)結(jié)構(gòu)有_________順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)____________________。<13>設(shè)線性表中有n個(gè)數(shù)據(jù)元素,則在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為_____Ｏ<n>______,在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為____O<n>_______。<14>設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素,則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中___n-i+1____個(gè)數(shù)據(jù)元素；刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中___n-i____個(gè)元素。<15>若頻繁地對(duì)線性表進(jìn)行插入與刪除操作,該線性表應(yīng)采用_____鏈?zhǔn)絖________存儲(chǔ)結(jié)構(gòu)。<16>鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)包含______數(shù)據(jù)__________域和_____指針__________域。<17>對(duì)于一個(gè)長度為n的單鏈存儲(chǔ)的線性表,在表頭插入元素的時(shí)間復(fù)雜度為___Ο<1>______,在表尾插入元素的時(shí)間復(fù)雜度為_____Ο<n>_______。<18>棧的插入和刪除只能在棧的棧頂進(jìn)行,后進(jìn)棧的元素必定先出棧,所以又把棧稱為____FILO________表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行,先進(jìn)隊(duì)列的元素必定先出隊(duì)列,所以又把隊(duì)列稱為_____FIFO______表。<19>s="Iamaman"長度為____10_______。<20>s1="hello",s2="boy",s1,s2連接后為：________helloboy______________。<21>s="thisisthemainstring",sub="string",strindex<s,sub>是：_______13_______。<22>inta[10][10],已知a=1000,sizeof<int>=2,求a[3][3]地址：_______1066___________。<23>設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱為________模式匹配________。<24>在樹型結(jié)構(gòu)中,樹根結(jié)點(diǎn)沒有______前趨______結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且僅有______一______個(gè)前驅(qū)結(jié)點(diǎn)；樹葉結(jié)點(diǎn)沒有______后繼______結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)的______后繼______結(jié)點(diǎn)數(shù)不受限制。<25>在一棵二叉樹中,度為0的結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2,則：n0=______n2+1______。<26>由分別帶權(quán)為3,9,6,2,5的共五個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹,則帶權(quán)路徑長度為______55______。<27>在圖G的鄰接表表示中,每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù),對(duì)于無向圖來說等于該頂點(diǎn)的______度數(shù)______,對(duì)于有向圖來說等于該頂點(diǎn)的______出度數(shù)______。<28>假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊,則采用鄰接矩陣表示的空間復(fù)雜性為______O<n2>______,采用鄰接表表示的空間復(fù)雜性為______O<n+e>______。<29>對(duì)于長度為n的線性表,若進(jìn)行順序查找,則時(shí)間復(fù)雜度為______O<n>____；若采用折半法查找,則時(shí)間復(fù)雜度為______O<log2n>____。<30>假設(shè)在有序線性表A[1..20]上進(jìn)行折半查找,則比較一次查找成功的結(jié)點(diǎn)數(shù)為____1_______,則比較二次查找成功的結(jié)點(diǎn)數(shù)為____2_______,則比較三次查找成功的結(jié)點(diǎn)數(shù)為____4_______,則比較四次查找成功的結(jié)點(diǎn)數(shù)為_____8______,則比較五次查找成功的結(jié)點(diǎn)數(shù)為____5_______,平均查找長度為_____log2<n+1>-1______。<31>在一棵二叉排序樹中,每個(gè)分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定_____小于______該結(jié)點(diǎn)的值,右子樹上所有結(jié)點(diǎn)的值一定____大于_______該結(jié)點(diǎn)的值。<32>對(duì)一棵二叉排序樹進(jìn)行中序遍歷時(shí),得到的結(jié)點(diǎn)序列是一個(gè)_______增序序列_______________。<33>對(duì)于線性表〔70,34,55,23,65,41,20進(jìn)行散列存儲(chǔ)時(shí),若選用H〔K=K%7作為散列函數(shù),則散列地址為0的元素是_____70_________,散列地址為6的是____34,20,55_________。<34>在線性表的散列存儲(chǔ)中,裝填因子又稱為裝填系數(shù),若用m表示散列表的長度,n表示待散列存儲(chǔ)的元素的個(gè)數(shù),則等于____n/m_______。<35>散列表中解決沖突的兩種方法是____開放地址法_________和____鏈地址法_________。<36>在散列存儲(chǔ)中,裝填因子a的值越大,則_______產(chǎn)生沖突的可能性就越大____________；a的值越小,則_____產(chǎn)生沖突的可能性就越小___________。<37>散列法存儲(chǔ)的基本思想是由________關(guān)鍵碼直接______________決定數(shù)據(jù)的存儲(chǔ)地址。<38>構(gòu)造哈希函數(shù)的方法有<寫二個(gè)>______________直接定址法,數(shù)字分析法,平方取中法,折疊法,除留余數(shù)法,隨機(jī)數(shù)法_________________________________________。<39>在分塊查找中首先查找_____索引________,然后再查找相應(yīng)的______塊_________。<40>散列表的查找效率主要取決于散列表造表時(shí)選擇的_____哈希函數(shù)________和______裝填因子_________。<41>對(duì)兩棵具有相同關(guān)鍵字集合而形狀不同的二叉排序樹,____中序_______遍歷它們得到的序列的順序是一樣的。<42>當(dāng)待排序的記錄數(shù)較大,排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí),宜采用______快速_________排序；當(dāng)待排序的記錄數(shù)較大,存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí),宜采用______歸并_________排序。<43>在堆排序的過程中,對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為___O<log2n>_____,整個(gè)堆排序過程的時(shí)間復(fù)雜度為____O<nlog2n>____。<44>當(dāng)向一個(gè)大根堆插入一個(gè)具有最大值的元素時(shí),需要逐層____向上_____調(diào)整,直到被調(diào)整到_____根結(jié)點(diǎn)_______位置為止。<45>對(duì)一組初始關(guān)鍵字序列〔40,50,95,20,15,70,60,45,10進(jìn)行冒泡排序,則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為____8______,在整個(gè)排序過程中最多需要進(jìn)行_____8_____趟排序才可以完成。<46>在在插入排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中,平均比較次數(shù)最少的排序是___快速_______,需要內(nèi)存容量最多的是____歸并______。<47>堆排序是不穩(wěn)定,空間復(fù)雜度為____O<1>_____。在最壞情況下,其時(shí)間復(fù)雜度也為___O<nlog2n>______。<48>若待排序的文件中存在多個(gè)關(guān)鍵字相同的記錄,經(jīng)過某種排序方法排序后,具有相同關(guān)鍵字的記錄間的相對(duì)位置保持不變,則這種排序方法是____穩(wěn)定_______的排序方法。<49>在對(duì)一組記錄<50,40,95,20,15,70,60,45,80>進(jìn)行直接插入排序時(shí),當(dāng)把第7個(gè)記錄60插入到有序表時(shí),為尋找插入位置需比較____3_____次。<50>二路歸并排序的時(shí)間復(fù)雜度是___O<nlog2n>______。<51>對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序,所需的附加空間消耗是___O<n>______。<52>設(shè)表中元素的初始狀態(tài)是按鍵值遞增的,分別用堆排序、快速排序、冒泡排序和歸并排序方法對(duì)其仍按遞增順序進(jìn)行排序,則______冒泡排序_________最省時(shí)間,____快速排序________最費(fèi)時(shí)間。三、判斷題。<每小題1分,共10分><×>1．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位。<×>2．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位。<√>3．順序存儲(chǔ)的線性表可以隨機(jī)存取。<√>4．線性表中的元素可以是各種各樣的,但同一線性表中的數(shù)據(jù)元素具有相同的特性,因此,是屬于同一數(shù)據(jù)對(duì)象。<×>5．在單鏈表中,任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系,因?yàn)榭梢詮念^結(jié)點(diǎn)查找任何一個(gè)元素。<×>6．在單鏈表中,要取得某個(gè)元素,只要知道該元素的指針即可,因此,單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。<×>7．鏈表的每個(gè)結(jié)點(diǎn)中,都恰好包含一個(gè)指針。<×>8．?dāng)?shù)組是同類型值的集合。<√>9．使用三元組表示稀疏矩陣的元素,有時(shí)并不能節(jié)省存儲(chǔ)時(shí)間。<√>10.線性表可以看成是廣義表的特例,如果廣義表中的每個(gè)元素都是原子,則廣義表便成為線性表。<√>11.由樹轉(zhuǎn)換成二叉樹,其根結(jié)點(diǎn)的右子樹總是空的。<×>12.后序遍歷樹和中序遍歷與該樹對(duì)應(yīng)的二叉樹,其結(jié)果不同。<×>13.若有一個(gè)結(jié)點(diǎn)是某二叉樹子樹的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn),則它必是該子樹的前序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。<√>14.若一個(gè)樹葉是某子樹的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn),則它必是該子樹的前序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。<×>15.已知二叉樹的前序遍歷和后序遍歷序列并不能唯一地確定這棵樹,因?yàn)椴恢罉涞母Y(jié)點(diǎn)是哪一個(gè)。<×>16.在哈夫曼編碼中,當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí),其編碼也相同,對(duì)于這種情況應(yīng)作特殊處理。<√>17.有回路的圖不能進(jìn)行拓?fù)渑判颉?lt;×>18.連通分量是無向圖中的極小連通子圖。<√>19.散列法存儲(chǔ)的基本思想是由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址。<√>20.散列表的查找效率取決于散列表造表時(shí)選取的散列函數(shù)和處理沖突的方法。<√>21.m階B-樹每一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)都小于或等于m。<√>22.中序遍歷二叉排序樹的結(jié)點(diǎn)就可以得到排好序的結(jié)點(diǎn)序列。<√>23.在二叉排序樹上插入新的結(jié)點(diǎn)時(shí),不必移動(dòng)其它結(jié)點(diǎn),僅需改動(dòng)某個(gè)結(jié)點(diǎn)的指針,由空變?yōu)榉强占纯伞?lt;√>24.當(dāng)待排序的元素很多時(shí),為了交換元素的位置,移動(dòng)元素要占用較多的時(shí)間,這是影響時(shí)間復(fù)雜性的主要因素。<√>25.對(duì)于n個(gè)記錄的集合進(jìn)行快速排序,所需要的平均時(shí)間是O<nlog2n>。<√>26.對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序,所需要的平均時(shí)間是O<nlog2n>。<√>27.堆中所有非終端結(jié)點(diǎn)的值均小于或等于〔大于或等于左右子樹的值。<×>28.磁盤上的順序文件中插入新的記錄時(shí),必須復(fù)制整個(gè)文件。<×>29.在索引順序文件中插入新的記錄時(shí),必須復(fù)制整個(gè)文件。<×>30.索引順序文件是一種特殊的順序文件,因此通常存放在磁帶上。四、簡答題。<共6小題,每小題約5分,共32分>1.簡述下列術(shù)語：數(shù)據(jù)、數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素、數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類型和算法。數(shù)據(jù)：數(shù)據(jù)是信息的載體,是計(jì)算機(jī)程序加工和處理的對(duì)象,包括數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)指不可分割的、具有獨(dú)立意義的最小數(shù)據(jù)單位,數(shù)據(jù)項(xiàng)有時(shí)也稱為字段或域。數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位,在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理,一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)就是指數(shù)據(jù)元素間的關(guān)系。數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的物理結(jié)構(gòu)表示數(shù)據(jù)元素的存儲(chǔ)方式或者數(shù)據(jù)元素的物理關(guān)系。數(shù)據(jù)類型：是指變量的取值范圍和所能夠進(jìn)行的操作的總和。算法：是對(duì)特定問題求解步驟的一種描述,是指令的有限序列。2.簡述棧和線性表的區(qū)別。答：一般線性表使用數(shù)組來表示的。線性表一般有插入、刪除、讀取等對(duì)于任意元素的操作。而棧只是一種特殊的線性表。棧只能在線性表的一端插入〔稱為入棧,push或者讀取棧頂元素或者稱為"彈出、出棧"<pop>。3.簡述棧和隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)的相同點(diǎn)和不同點(diǎn)。答：相同點(diǎn)：棧和隊(duì)列都是特殊的線性表,只在端點(diǎn)處進(jìn)行插入,刪除操作。不同點(diǎn)：棧只在一端〔棧頂進(jìn)行插入,刪除操作；隊(duì)列在一端〔top刪除,一端<rear>插入。4.如果進(jìn)棧的元素序列為A,B,C,D,則可能得到的出棧序列有多少種?寫出全部的可能序列。答：可能序列有14種：ABCD;ACBD;ACDB;ABDC;ADCB;BACD;BADC;BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA。5.如果進(jìn)棧的元素序列為1,2,3,4,5,6,能否得到4,3,5,6,1,2和1,3,5,4,2,6的出棧序列?并說明為什么不能得到或如何得到。答：不能得到4,3,5,6,1,2,最先出棧的是4,則按321的方式出,不可能得到1在2前的序列,可以得到1,3,5,4,2,6,按如下方式進(jìn)行push<1>,pop<>,push<2>,push<3>,pop<>,push<4>,push<5>,pop<>,pop<>,pop<>,push<6>,pop<>。6.設(shè)s="IAMASTUDENT",t="GOOD",q="WORKER"。求：StrLength<s>,StrLength<t>,SubStr<s,8,7>,SubStr<t,2,1>,StrIndex<s,"A">,StrIndex<s,t>,StrRep<s,"STUDENT",q>,SubStr<SubStr<s,6,2>,StrConcat<t,SubStr<s,7,8>>>。答：StrLength<s>=14,StrLength<t>=4,SubStr<s,8,7>="STUDENT",SubStr<t,2,1>="O",StrIndex<s,"A">=3,StrIndex<s,t>=0,StrRep<s,"STUDENT",q>="IAMAWORKER",7.簡述下列每對(duì)術(shù)語的區(qū)別：空串和空格串；串變量和串常量；主串和子串；串變量的名字和串變量的值。答：空串：不含任何字符；空格串：所含字符都是空格。串變量和串常量:串常量在程序的執(zhí)行過程中只能引用不能改變；串變量的值在程序執(zhí)行過程中是可以改變和重新賦值的。主串與子串：子串是主串的一個(gè)子集。串變量的名字與串變量的值:串變量的名字表示串值的標(biāo)識(shí)符。8.設(shè)有二維數(shù)組A<6×8>,每個(gè)元素占6個(gè)字節(jié)存儲(chǔ),順序存放,A的起地址為1000,計(jì)算：<1>數(shù)組A的體積<即存儲(chǔ)量>；<2>數(shù)組的最后一個(gè)元素A??的起地址；<3>按行優(yōu)先存放時(shí),元素A1,4的起地址；<4>按列優(yōu)先存放時(shí),元素A4,7的起地址。<1>6*8*6=288<2>1000+47*6=1282<3>1000+<8+4>*8=1096<4>1000+<6*7+4>*8=13689.分別畫出含三個(gè)結(jié)點(diǎn)的無序樹與二叉樹的所有不同形態(tài)。答：無序樹形態(tài)如下：二叉樹形態(tài)如下：10.分別寫出圖1中所示二叉樹的先序遍歷、中序遍歷、后序遍歷的結(jié)點(diǎn)訪問序列。答：先序遍歷序列:ABDEHICFJG中序遍歷序列:DBHEIAFJCG后序遍歷序列:DHIEBJFGCA11.試找出分別滿足下列條件的所有二叉樹。<1>先序序列與中序序列相同。<2>后序序列與中序序列相同。<3>先序序列與后序序列相同。答：<1>先序序列和中序序列相同：空樹或缺左子樹的單支樹； <2>后序序列和中序序列相同：空樹或缺右子樹的單支樹； <3>先序序列和后序序列相同：空樹或只有根結(jié)點(diǎn)的二叉樹。12.已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA,試畫出這棵二叉樹。答：這棵二叉樹為:13.分別寫出圖2中所示二叉樹的先序遍歷、中序遍歷、后序遍歷的結(jié)點(diǎn)訪問序列。答：先序遍歷序列:ABDGCEHF中序遍歷序列:DGBAEHCF后序遍歷序列:GDBHEFCA14.給定權(quán)值<7,18,3,32,5,26,12,8>,構(gòu)造的哈夫曼樹。答：哈夫曼樹為:15.假設(shè)用于通信的電文僅由8個(gè)字母組成,字母在電文中出現(xiàn)的頻率分別為7,19,2,6,32,3,21,10,試為這8個(gè)設(shè)計(jì)哈夫曼編碼。答：哈夫曼樹為:在上述哈夫曼樹的每個(gè)左分支上標(biāo)以0,右分支上標(biāo)以1,并設(shè)這8個(gè)字母分別為A、B、C、D、E、F、G和H,則它們的哈夫曼樹為分別為:A：0000B：10C：00110D：0010E：01F：00111G：11H：000116.畫出無向圖G1的鄰接矩陣和鄰接表示意圖,并寫出每個(gè)頂點(diǎn)的度。答：〔1鄰接矩陣:〔2鄰接鏈表：〔3每個(gè)頂點(diǎn)的度：頂點(diǎn)度V13V23V32V43V5317.畫出有向圖G2的鄰接矩陣、鄰接表和逆鄰接表示意圖,并寫出每個(gè)頂點(diǎn)的入度和出度。答：〔1鄰接鏈表：〔2逆鄰接鏈表：〔3頂點(diǎn)入度出度V130V222V312V413V521V62318.對(duì)應(yīng)圖G3,寫出從v1出必的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列各三個(gè)。答：深度優(yōu)先查找遍歷序列：V1V2V3V4V5;V1V3V5V4V2;V1V4V3V5V2廣度優(yōu)先查找遍歷序列：V1V2V3V4V5;V1V3V2V4V5;V1V4V3V2V519.何謂二叉排序樹?答：一棵二叉排序樹<又稱二叉查找樹>或者是一棵空樹,或者是一棵同時(shí)滿足下列條件的二叉樹：<1>若它的左子樹不空,則左子樹上所有結(jié)點(diǎn)的鍵值均小于它根結(jié)點(diǎn)鍵值。<2>若它的右子樹不空,則右子樹上所有結(jié)點(diǎn)的鍵值均大于它根結(jié)點(diǎn)鍵值。<3>它的左、右子樹也分別為二叉排序樹。20.順序查找時(shí)間為O<n>,二分查找時(shí)間為O<log2n>,散列查找時(shí)間為O<1>,為什么有高效率的