數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料

第1章緒論一、填空題數(shù)據(jù)結(jié)構(gòu)就是一門研究非數(shù)值計(jì)算得程序設(shè)計(jì)問題中計(jì)算機(jī)得 以及它們之間得 與 等得學(xué)科。數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D就是 得有限集合，R就是D上得 有限集合。數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別就是 與 。若細(xì)分為4類，分別就是 、 、 與 。線性結(jié)構(gòu)中元素之間存在 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 關(guān)系。在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 后繼結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 個(gè)后繼結(jié)點(diǎn)。在樹形結(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ù)可以任意。在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)得前驅(qū)結(jié)點(diǎn)數(shù)與后繼結(jié)點(diǎn)數(shù)可以 。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)得、數(shù)據(jù)得與數(shù)據(jù)得這三個(gè)方面得內(nèi)容。數(shù)據(jù)得存儲結(jié)構(gòu)可用四種基本得存儲方法表示，它們分別就是 、 、 與 。數(shù)據(jù)得運(yùn)算最常用得有5種，它們分別就是 、 、 、 、 。一個(gè)算法得效率可分為 效率與 效率。二、單項(xiàng)選擇題數(shù)據(jù)結(jié)構(gòu)中，與所使用得計(jì)算機(jī)無關(guān)得就是數(shù)據(jù)得（）結(jié)構(gòu)。A、存儲 B、物理 C、邏輯 D、物理與存儲算法分析得目得就是（）。A、找出數(shù)據(jù)結(jié)構(gòu)得合理性 B、研究算法中得輸入與輸出得關(guān)系C、分析算法得效率以求改進(jìn) D、分析算法得易懂性與文檔性算法分析得兩個(gè)主要方面就是：（）。A、空間復(fù)雜性與時(shí)間復(fù)雜性 B、正確性與簡明性C、可讀性與文檔性 D、數(shù)據(jù)復(fù)雜性與程序復(fù)雜性計(jì)算機(jī)算法指得就是（）。A、計(jì)算方法 B、排序方法 C、解決問題得有限運(yùn)算序列 D、調(diào)度方法計(jì)算機(jī)算法必須具備輸入、輸出與（）等5個(gè)特性。A、可行性、可移植性與可擴(kuò)充性 B、可行性、確定性與有窮性C、確定性、有窮性與穩(wěn)定性 D、易讀性、穩(wěn)定性與安全性三、判斷下列敘述得對錯(cuò)。（）數(shù)據(jù)元素就是數(shù)據(jù)得最小單位。（）數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)對象與對象中數(shù)據(jù)元素之間關(guān)系得集合。（）數(shù)據(jù)結(jié)構(gòu)就是具有結(jié)構(gòu)得數(shù)據(jù)對象。（）算法與程序原則上沒有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時(shí)二者就是通用得。（）所謂數(shù)據(jù)得邏輯結(jié)構(gòu)就是指數(shù)據(jù)元素之間得邏輯關(guān)系。（）數(shù)據(jù)得邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身得內(nèi)容與形式無關(guān)。（）數(shù)據(jù)結(jié)構(gòu)就是指相互之間存在一種或多種關(guān)系得數(shù)據(jù)元素得全體。（）從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。四、設(shè)n為正整數(shù),分析下列各程序段中加下劃線得語句得執(zhí)行次數(shù)。for(inti=1；i<=n；i++） for(intj=1;j<=n;j++）{c[i][j]=0、0；for（intk=1;k<=n;k++）c[i][j]=c[i][j]+a[i][k]*b[k][j]； }x=0；y=0；for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)for(intk=1;k<=j;k++)x=x+y； 2)/2=n(n+1)/4+n(n+1)(2n+1)/12=n(n+1)(3+2n+1)/12=n(n+1)(n+2)/6n（3）k=0; for(i=1;i<=n;i++) for(j=i;j<=n;j++) k++; (4)i=1;j=0; while(i+j<=n){ if(i>j)j++; elsei++; } (5) x=n;y=0; while(x>=(y+1)*(y+1)) y++ ; (6) x=91;y=100; while(y>0){ if(x>100){x-=10;y--;} elsex++; }五、分析下面各程序段得時(shí)間復(fù)雜度2、2、s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;1、1、for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;3、x=0;3、x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;4、i=1;while(i<=n)i=i*3;六、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=（D,R），試按各小題所給條件畫出這些邏輯結(jié)構(gòu)得圖示，并確定相對于關(guān)系R，哪些結(jié)點(diǎn)就是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)就是終端結(jié)點(diǎn)？D={d1,d2,d3,d4}R={(d1,d2),(d2,d3),(d3,d4)}D={d1,d2,…,d9}R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5),(d6,d7),(d8,d9)}D={d1,d2,…,d9}R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9),(d5,d6),(d8,d9),(d9,d7),(d4,d7),(d4,d6)}

第二章線性表一、填空在順序表中插入或刪除一個(gè)元素，需要平均移動元素，具體移動得元素個(gè)數(shù)與有關(guān)。向一個(gè)長度為n得向量得第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)元素時(shí)，需向后移動個(gè)元素。向一個(gè)長度為n得向量中刪除第i個(gè)元素(1≤i≤n)時(shí)，需向前移動個(gè)元素。在順序表中訪問任意一結(jié)點(diǎn)得時(shí)間復(fù)雜度均為，因此，順序表支持 訪問。順序表中邏輯上相鄰得元素得物理位置 相鄰。單鏈表中邏輯上相鄰得元素得物理位置 相鄰。在帶頭結(jié)點(diǎn)得非空單鏈表中，頭結(jié)點(diǎn)得存儲位置由

指示，首元素結(jié)點(diǎn)得存儲位置由

指示，除首元素結(jié)點(diǎn)外，其它任一元素結(jié)點(diǎn)得存儲位置由

指示。在n個(gè)結(jié)點(diǎn)得單鏈表中要刪除已知結(jié)點(diǎn)*p，需找到它得，其時(shí)間復(fù)雜度為。循環(huán)單鏈表La中，指針P所指結(jié)點(diǎn)為表尾結(jié)點(diǎn)得條件就是

。已知L就是無表頭結(jié)點(diǎn)得單鏈表，且P結(jié)點(diǎn)既不就是首元素結(jié)點(diǎn)，也不就是尾元素結(jié)點(diǎn)。a、在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)得語句序列就是： 。b、在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)得語句序列就是： 。c、在表首插入S結(jié)點(diǎn)得語句序列就是： 。d、在表尾插入S結(jié)點(diǎn)得語句序列就是： 。二、判斷正誤（）1、鏈表得每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。（）2、順序存儲結(jié)構(gòu)只能用來存放線性結(jié)構(gòu)；鏈?zhǔn)酱鎯Y(jié)構(gòu)只能用來存放非線性結(jié)構(gòu)。（）3、鏈表得刪除算法很簡單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會自動將后續(xù)各個(gè)單元向前移動。（）4、線性表得每個(gè)結(jié)點(diǎn)只能就是一個(gè)簡單類型，而鏈表得每個(gè)結(jié)點(diǎn)可以就是一個(gè)復(fù)雜類型。（）5、順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。（）6、順序存儲方式得優(yōu)點(diǎn)就是存儲密度大，且插入、刪除運(yùn)算效率高。（）7、線性表在物理存儲空間中也一定就是連續(xù)得。（）8、線性表在順序存儲時(shí)，邏輯上相鄰得元素未必在存儲得物理位置次序上相鄰。（）9、順序存儲方式只能用于存儲線性結(jié)構(gòu)。（）10、線性表得邏輯順序與存儲順序總就是一致得。三、單項(xiàng)選擇題（）1、數(shù)據(jù)在計(jì)算機(jī)存儲器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且就是連續(xù)得，稱之為： A、存儲結(jié)構(gòu) B、邏輯結(jié)構(gòu) C、順序存儲結(jié)構(gòu) D、鏈?zhǔn)酱鎯Y(jié)構(gòu)（）2、在n個(gè)結(jié)點(diǎn)得順序表中，算法得時(shí)間復(fù)雜度就是O（1）得操作就是： A、訪問第i個(gè)結(jié)點(diǎn)（1≤i≤n）與求第i個(gè)結(jié)點(diǎn)得直接前驅(qū)（2≤i≤n） B、在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n） C、刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n） D、將n個(gè)結(jié)點(diǎn)從小到大排序（）3、鏈表不具有得特點(diǎn)就是

。 A、可隨機(jī)訪問任一個(gè)元素 B、插入刪除不需要移動元素C、不必事先估計(jì)存儲空間

D、所需空間與線性表得長度成正比（）4、鏈接存儲得存儲結(jié)構(gòu)所占存儲空間： A、分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系得指針 B、只有一部分，存放結(jié)點(diǎn)值 C、只有一部分，存儲表示結(jié)點(diǎn)間關(guān)系得指針 D、分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)（）5、對于只在表得首、尾進(jìn)行插入操作得線性表，宜采用得存儲結(jié)構(gòu)為:。 A、順序表 B、用頭指針表示得單循環(huán)鏈表 C、用尾指針表示得單循環(huán)鏈表 D、單鏈表（）6、線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元得地址： A、必須就是連續(xù)得 B、部分地址必須就是連續(xù)得 C、一定就是不連續(xù)得 D、連續(xù)或不連續(xù)都可以（）7、線性表Ｌ在情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。 Ａ、需經(jīng)常修改Ｌ中得結(jié)點(diǎn)值 Ｂ、需不斷對Ｌ進(jìn)行刪除插入 Ｃ、Ｌ中含有大量得結(jié)點(diǎn) Ｄ、Ｌ中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜（）8、單鏈表得存儲密度 Ａ、大于1 Ｂ、等于1 Ｃ、小于1 D、不能確定（）9、設(shè)a1、a2、a3為3個(gè)結(jié)點(diǎn)，整數(shù)P0，3，4代表地址，則如下得鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為P034P0a13a24A30 Ａ、循環(huán)鏈表 Ｂ、單鏈表 Ｃ、雙向循環(huán)鏈表 D、雙向鏈表（）10、若線性表最常用得操作就是存取第i個(gè)元素及其前驅(qū)得值，則采用

存儲方式節(jié)省時(shí)間。 A、單鏈表 B、雙鏈表 C、單循環(huán)鏈表 D、順序表四、簡答題1、試比較順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)得優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？2、在單鏈表與單循環(huán)鏈表中，若僅知道指針p指向某一結(jié)點(diǎn)，不知道表頭指針，能否將結(jié)點(diǎn)*p從鏈表中刪去？若可以，其時(shí)間復(fù)雜度各為多少？五、閱讀分析題指出以下算法中得錯(cuò)誤與低效（即費(fèi)時(shí)）之處，并將它改寫為一個(gè)既正確又高效得算法。注：上題涉及得類型定義如下：#defineLISTINITSIZE100#defineLISTINCREMENT10注：上題涉及得類型定義如下：#defineLISTINITSIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;//存儲空間基址Intlength;//當(dāng)前長度Intlistsize;//當(dāng)前分配得存儲容量}SqList;StatusDeleteK(SqList&a,inti,intk){//本過程從順序存儲結(jié)構(gòu)得線性表a中刪除第i個(gè)元素起得k個(gè)元素if(i<1||k<0||i+k>a、length)returnINFEASIBLE;//參數(shù)不合法else{for(count=1;count<k;count++){//刪除一個(gè)元素for(j=a、length;j>=i+1;j--)a、elem[j-1]=a、elem[j];a、length--;}returnOK;}//DeleteK1、已知L就是無表頭結(jié)點(diǎn)得單鏈表，且P結(jié)點(diǎn)既不就是首元結(jié)點(diǎn)，也不就是尾元結(jié)點(diǎn)，請寫出在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)得核心語句序列。2、試分別以不同得存儲結(jié)構(gòu)實(shí)現(xiàn)線性表得就地逆置算法，即在原表得存儲空間將線性表（a1,a2、、、,an）逆置為（an,an-1,、、、,a1）。（1）以順序表作存儲結(jié)構(gòu)。（2）以單鏈表作存儲結(jié)構(gòu)。3、已知帶有頭結(jié)點(diǎn)得循環(huán)鏈表中頭指針為head，試寫出刪除并釋放數(shù)據(jù)域值為x得所有結(jié)點(diǎn)得c函數(shù)。4、已知有單鏈表表示得線性表中含有三類字符得數(shù)據(jù)元素（如字母字符、數(shù)字字符與其它字符），試編寫算法來構(gòu)造三個(gè)以循環(huán)鏈表表示得線性表，使每個(gè)表中只含同一類得字符，且利用原表中得結(jié)點(diǎn)空間作為這三個(gè)表得結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。

第三章棧與隊(duì)列一、選擇題一個(gè)棧得輸入序列為A，B，C，D，則借助一個(gè)棧所得到得輸出序列不可能得就是

。

A、A，B，C，D B、D，C，B，AC、A，C，D，B

D、D，A，B，CS最多能容納4個(gè)元素?，F(xiàn)有6個(gè)元素按A、B、C、D、E、F得順序進(jìn)棧,問下列哪一個(gè)序列就是可能得出棧序列?。A、E，D，C，B，A，F(xiàn) B、B，C，E，F(xiàn)，A，DC、C,B，E，D，A，F(xiàn) D、A，D，F(xiàn)，E，B，C設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)得結(jié)構(gòu)為（data,next），且top就是指向棧頂?shù)弥羔槨Ｈ粝朐阪準(zhǔn)綏５脳ｍ敳迦胍粋€(gè)由指針s所指得結(jié)點(diǎn)，則應(yīng)執(zhí)行下列哪一個(gè)操作？。A、top->next=s； B、s->next=top->next；top->next=s；C、s->next=top；top=s； D、s->next=top；top=top->next；一個(gè)隊(duì)列得入隊(duì)序列就是1，2，3，4，則隊(duì)列得輸出序列就是

。

A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，設(shè)循環(huán)隊(duì)列得結(jié)構(gòu)就是 constintMaxSize=100； typedefintDataType；typedefstruct{ DataTypedata[MaxSize]； intfront,rear； }Queue；若有一個(gè)Queue類型得隊(duì)列Q，試問判斷隊(duì)列滿得條件應(yīng)就是下列哪一個(gè)語句？。A、Q、front==Q、rear； B、Q、front-Q、rear==MaxSize；C、Q、front+Q、rear==MaxSize；D、Q、front==（Q、rear+1）%MaxSize；設(shè)循環(huán)隊(duì)列得結(jié)構(gòu)就是 constintMaxSize=100； typedefintDataType；typedefstruct{ DataTypedata[MaxSize]； intfront，rear； }Queue； 若有一個(gè)Queue類型得隊(duì)列Q，試問應(yīng)用下列哪一個(gè)語句計(jì)算隊(duì)列元素個(gè)數(shù)？。 A、（Q、rear-Q、front+MaxSize）%MaxSize；B、Q、rear-Q、front+1；C、Q、rear-Q、front-1； D、Q、rear-Qfront；以下哪一個(gè)不就是隊(duì)列得基本運(yùn)算？。A、從隊(duì)尾插入一個(gè)新元素 B、從隊(duì)列中刪除第i個(gè)元素C、判斷一個(gè)隊(duì)列就是否為空 D、讀取隊(duì)頭元素得值二、簡答題簡述棧與隊(duì)列得共同點(diǎn)與不同點(diǎn)。它們與線性表有什么關(guān)系？按圖3、1(b)所示鐵道（兩側(cè)鐵道均為單向行駛道）進(jìn)行車廂調(diào)度，回答：

⑴如進(jìn)站得車廂序列為123，則可能得到得出站車廂序列就是什么？⑵如進(jìn)站得車廂序列為123456，能否得到435612與135426得出站序列，并說明原因。（即寫出以“S”表示進(jìn)棧、以“X”表示出棧得棧操作序列）。設(shè)有一個(gè)順序棧S，元素s1,s2,s3,s4,s5,s6依次進(jìn)棧，如果6個(gè)元素得出棧順序?yàn)閟2,s3,s4,s6,s5,s1，則順序棧得容量至少應(yīng)為多少？簡述以下算法得功能（其中棧與隊(duì)列得元素類型均為int）：（1）voidproc_1(StackS){inti,n,A[255];

n=0;

while(!EmptyStack(S))

{n++;

Pop(&S,

&A[n]);}

for(i=1;

i<=n;

i++)

Push(&S,

A[i]);

}（2）voidproc_2(StackS,

inte){StackT;

intd;InitStack(&T);

while(!EmptyStack(S))

{Pop(&S,

&d);

if(d!=e)Push(&T,

d);

}

while(!EmptyStack(T))

{Pop(&T,

&d);

Push(&S,

d);

}}（3）voidproc_3(Queue

*Q){StackS;

intd;InitStack(&S);

while(!EmptyQueue(*Q))

{DeleteQueue(Q,

&d);Push(&S,

d);

}

while(!EmptyStack(S))

{Pop(&S,

&d);

EnterQueue(Q，d)

}

}三、算法題1、試寫一個(gè)算法，判斷依次讀入得一個(gè)以@為結(jié)束符得字母序列，就是否為形如‘序列1&序列2’模式得字符序列。其中序列1與序列2中都不含字符’&’，且序列2就是序列1得逆序列。例如，‘a(chǎn)+b&b+a’就是屬該模式得字符序列，而‘１+３&３－１

第四章串一、選擇題下面關(guān)于串得敘述中，哪一個(gè)就是不正確得？。A、串就是字符得有限序列 B、空串就是由空格構(gòu)成得串C、模式匹配就是串得重要運(yùn)算 D、串既可順序存儲，也可采用鏈?zhǔn)酱鎯?、串就是一種特殊得線形表，其特殊性體現(xiàn)在____

_。A、可以順序存儲 B、數(shù)據(jù)元素就是一個(gè)字符C、可以鏈接存儲 D、數(shù)據(jù)元素可以就是多個(gè)字符3、長度為1得串等價(jià)于一個(gè)字符型常量，這種說法就是。A、正確得 B、錯(cuò)誤得二、簡答題設(shè)s=’IAMASTUDENT’，

t=’GOOD’，

q=’WORKER’。給出下列操作得結(jié)果：StrLength(s)；

SubString(sub1,s,1,7)；SubString(sub2,s,7,1)；StrIndex(s,’A’,4)；StrReplace(s,’STUDENT’,q)；StrCat(StrCat(sub1,t),StrCat(sub2,q))。設(shè)主串為”abcaabbabcabaacbacba”模式串為”abcabaa”。計(jì)算模式串得next,nextval函數(shù)值，并給出利用nextval函數(shù)值進(jìn)行KMP模式匹配得每一趟過程。第五章數(shù)組與廣義表一、選擇題1、稀疏矩陣一般得壓縮存儲方法有兩種,即。A、數(shù)組與三維數(shù)組 B、三元組與散列C、三元組與十字鏈表 D、散列與十字鏈表2、若采用三元組壓縮技術(shù)存儲稀疏矩陣,只要把每個(gè)元素得行下標(biāo)與列下標(biāo)互換,就完成了對該矩陣得轉(zhuǎn)置運(yùn)算,這種觀點(diǎn)（）。A、正確 B、錯(cuò)誤3、數(shù)組元素得下標(biāo)值越大，存取時(shí)間越長，這種說法就是。A、正確得 B、錯(cuò)誤得4、廣義表(a,(b),((c)))得表尾就是。A、((c)) B、(((c)))C、(c) D、((b),((c)))二、填空題1、一維數(shù)組得邏輯結(jié)構(gòu)就是，存儲結(jié)構(gòu)就是。對于二維數(shù)組，有與兩種不同得存儲方式。對于一個(gè)二維數(shù)組A[m][n]，若采取按行存儲得方式，則任一數(shù)組元素A[i][j]相對于A[0][0]得地址為。2、二維數(shù)組A[10][20]采用列序?yàn)橹鞣绞酱鎯Γ總€(gè)元素占一個(gè)存儲單元，并且A[0][0]得存儲地址就是200，則A[6][12]得地址就是。3、設(shè)n行n列得下三角矩陣A已壓縮到一維數(shù)組S[1、、n*(n+1)/2]中,若按行序?yàn)橹鞔鎯?則A[i][j]對應(yīng)得S中得存儲位置就是。三、簡答題1、設(shè)有一個(gè)1010得對稱矩陣A[10][10]，采取按行壓縮存儲得方式將其上三角得矩陣元存放于一個(gè)一維數(shù)組B[]中，則數(shù)組B[]得容量應(yīng)有多大？若設(shè)A[0][0]為第一個(gè)元素，存放于B[0]，且數(shù)組A[][]得每一個(gè)數(shù)組元素在數(shù)組B[]中占一個(gè)數(shù)組元素位置，則A[8][5]在數(shù)組B[]中得地址就是多少？2（*）、設(shè)有三對角矩陣A[n][n]，將其三條對角線中得元素逐行存儲到一維數(shù)組B[3n-2]中，使得B[k]=A[i][j]。試求用i，j表示k得地址轉(zhuǎn)換公式。3（*）、畫出下面廣義表得兩種存儲結(jié)構(gòu)圖示：

(((a,b),(((),d,(e,f)))))4、求下列廣義表運(yùn)算得結(jié)果：（1）GETHEAD[((a,B,(c,D、)))]；（2）GETTAIL[((a,B、,(c,D、)))]；（3）GETTAIL[GETHEAD[((a,B,(c,D)))]]；（4）GETHEAD[GETTAIL[GETHEAD[((a,B、,(c,D、)))]]]；5、設(shè)廣義表L=((),())，則GETHEAD(L)就是；GETTAIL(L)就是；L得長度就是；深度就是。四、算法題1、將數(shù)組C[n]中所有奇數(shù)移到偶數(shù)之前，要求時(shí)間復(fù)雜度為O(n)。第六章樹與森林一、選擇題1、設(shè)二叉樹有n個(gè)結(jié)點(diǎn)且根結(jié)點(diǎn)處于第1層，則其高度為（）。 A、n-1 B、log2（n+1）-1 C、log2n+1 2、設(shè)高度為h（空二叉樹得高度為0，只有一個(gè)結(jié)點(diǎn)得二叉樹得高度為1）得二叉樹只有度為2與度為0得結(jié)點(diǎn)，則該二叉樹中所含結(jié)點(diǎn)至少有（）個(gè)。A、2h B、2h-1 C、2h+1 D、h+13、設(shè)森林F中有4棵樹，第1、2、3、4棵樹得結(jié)點(diǎn)個(gè)數(shù)分別為n1、n2、n3、n4，當(dāng)把森林F轉(zhuǎn)換成一棵二叉樹后，其根結(jié)點(diǎn)得右子樹中有（）個(gè)結(jié)點(diǎn)。A、n1-1 B、n1+n2+n3 C、n2+n3+n4 D、n4、將含有82個(gè)結(jié)點(diǎn)得完全二叉樹從根結(jié)點(diǎn)開始順序編號，根結(jié)點(diǎn)為第1號，其她結(jié)點(diǎn)自上向下，同一層自左向右連續(xù)編號。則第40號結(jié)點(diǎn)得雙親結(jié)點(diǎn)得編號為（）。A、20 B、19 C、81 D、805、對二叉樹從1開始編號，要求每個(gè)結(jié)點(diǎn)得編號大于其左右孩子得編號，同一個(gè)結(jié)點(diǎn)得左右孩子中，其左孩子得編號小于其右孩子得編號，則可采用（）實(shí)現(xiàn)編號。

A、先序遍歷

B、中序遍歷

C、后序遍歷

D、從根開始進(jìn)行層次遍歷6、某二叉樹得先序序列與后序序列正好相反，則該二叉樹一定就是（）得二叉樹。

A、空或只有一個(gè)結(jié)點(diǎn)

B、高度等于其結(jié)點(diǎn)數(shù)

C、任一結(jié)點(diǎn)無左孩子

D、任一結(jié)點(diǎn)無右孩子7、在線索化二叉樹中,t所指結(jié)點(diǎn)沒有左子樹得充要條件就是（）。A、t-〉left==NULL B、t-〉ltag==1 C、t-〉ltag==1且t-〉left==NULL D、、以上都不對8、二叉樹按某種順序線索化后,任一結(jié)點(diǎn)均有指向其前趨與后繼得線索,這種說法（）。A、正確 B、錯(cuò)誤9、二叉樹得前序遍歷序列中,任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)得前面,這種說法（）。A、正確 B、錯(cuò)誤10、設(shè)高度為h得二叉樹上只有度為0與度為2得結(jié)點(diǎn),則此類二叉樹中所包含得結(jié)點(diǎn)數(shù)至少為（）。A、2h B、2h-1 C、2h+1 D、h+111、如果T2就是由有序樹T轉(zhuǎn)換而來得二叉樹，那么T中結(jié)點(diǎn)得前序就就是T2中結(jié)點(diǎn)得（）。A、前序 B、中序 C、后序 D、層次序12、在一非空二叉樹得中序遍歷序列中，根結(jié)點(diǎn)得右邊（）。A、只有右子樹上得所有結(jié)點(diǎn) B、只有右子樹上得部分結(jié)點(diǎn)C、只有左子樹上得部分結(jié)點(diǎn) D、只有左子樹上得所有結(jié)點(diǎn)二、填空題（每空1分，共7分）N個(gè)結(jié)點(diǎn)得二叉樹采用二叉鏈表存放，共有空鏈域個(gè)數(shù)為。一棵含有101個(gè)結(jié)點(diǎn)得完全二叉樹存儲在數(shù)組A[1、、101]中,對1≤k≤101,若A[k]就是非葉子結(jié)點(diǎn),則k得最小值就是:，k得最大值就是:。設(shè)根結(jié)點(diǎn)得層數(shù)為1，則高度為k得二叉樹具有得結(jié)點(diǎn)數(shù)目，最少為，最多為。一棵二叉樹有67個(gè)結(jié)點(diǎn)，這些結(jié)點(diǎn)得度要么就是0，要么就是2。這棵二叉樹中度為2得結(jié)點(diǎn)有個(gè)。將一棵有50個(gè)結(jié)點(diǎn)得完全二叉樹從根結(jié)點(diǎn)開始，由根向下，每一層從左至右，順序地存儲在一個(gè)一維數(shù)組bt[1、、50]中，這棵二叉樹最下面一層上最左邊一個(gè)結(jié)點(diǎn)存儲在數(shù)組元素bt[]中。三、判斷題（每小題1分，共11分）（）1、樹結(jié)構(gòu)與二叉樹結(jié)構(gòu)都就是樹形結(jié)構(gòu),所以它們就是相同得數(shù)據(jù)結(jié)構(gòu)。（）2、滿二叉樹得結(jié)點(diǎn)個(gè)數(shù)必為奇數(shù)。（）3、若有一個(gè)結(jié)點(diǎn)就是二叉樹中某個(gè)子樹得中序遍歷結(jié)果序列得最后一個(gè)結(jié)點(diǎn)，則它一定就是該子樹得前序遍歷結(jié)果序列得最后一個(gè)結(jié)點(diǎn)。（）4、若有一個(gè)結(jié)點(diǎn)就是二叉樹中某個(gè)子樹得前序遍歷結(jié)果序列得最后一個(gè)結(jié)點(diǎn)，則它一定就是該子樹得中序遍歷結(jié)果序列得最后一個(gè)結(jié)點(diǎn)。（）5、將一棵樹轉(zhuǎn)換為二叉樹表示后,該二叉樹得根結(jié)點(diǎn)沒有右子樹。（）6、采用二叉樹來表示樹時(shí)，樹得先根次序遍歷結(jié)果與其對應(yīng)得二叉樹得前序遍歷結(jié)果就是一樣得。（）7、在Huffman樹中，權(quán)值較大得葉子結(jié)點(diǎn)離根較遠(yuǎn)。（）8、將一個(gè)森林轉(zhuǎn)換為二叉樹后,該二叉樹得根結(jié)點(diǎn)一定有右子樹。（）9、哈夫曼樹根結(jié)點(diǎn)得權(quán)值等于所有葉結(jié)點(diǎn)得權(quán)值之與。（）10、如果一個(gè)二叉樹中沒有度為1得結(jié)點(diǎn)，則必為滿二叉樹。（）11、由二叉樹結(jié)點(diǎn)得先根序列與后根序列可以唯一地確定一棵二叉樹。四、簡答題在結(jié)點(diǎn)個(gè)數(shù)為n（n>1）得各棵樹中，高度最小得樹得高度（根結(jié)點(diǎn)在第1層）就是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？高度最大得樹得高度（根結(jié)點(diǎn)在第1層）就是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？若有3個(gè)數(shù)據(jù)1，2，3，由它們構(gòu)造出來得中序遍歷結(jié)果都為1，2，3得不同二叉樹有哪些？ 試分別找出滿足以下條件得所有二叉樹：二叉樹得前序序列與中序序列相同；二叉樹得中序序列與后序序列相同；二叉樹得前序序列與后序序列相同。在前序線索樹中，要找出結(jié)點(diǎn)P得直接后繼結(jié)點(diǎn)，請寫出有關(guān)語句。LtagLcdataRtagRc在中序線索樹上，要找出結(jié)點(diǎn)P得直接后繼結(jié)點(diǎn)，請寫出相關(guān)語句。

ltaglcdatartagrc四、構(gòu)造題已知一棵二叉樹得前序遍歷結(jié)果就是ABECDFGHIJ，中序遍歷結(jié)果就是EBCDAFHIGJ，試畫出這棵二叉樹，并寫出它得后序遍歷序列。假定用于通信得電文僅由8個(gè)字母c1，c2，c3，c4，c5，c6，c7，c8組成，各字母在電文中出現(xiàn)得頻度分別為5，25，3，6，10，11，36，4。試為這8個(gè)字母設(shè)計(jì)不等長Huffman編碼，并給出該電文得總碼數(shù)。畫出與下列樹對應(yīng)得二叉樹：五、算法設(shè)計(jì)題若用二叉鏈表作為二叉樹得存儲表示，試編寫遞歸算法，統(tǒng)計(jì)二叉樹中葉結(jié)點(diǎn)得個(gè)數(shù)。若用二叉鏈表作為二叉樹得存儲表示，試編寫遞歸算法，交換每個(gè)結(jié)點(diǎn)得左孩子與右孩子。設(shè)二叉樹按二叉鏈表存放，寫算法判別一棵二叉樹就是否就是一棵正則二叉樹。正則二叉樹就是指：在二叉樹中不存在子樹個(gè)數(shù)為1得結(jié)點(diǎn)。設(shè)一顆二叉樹以二叉鏈表為存儲結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法求此二叉樹上度為1得結(jié)點(diǎn)個(gè)數(shù)。

第七章一、選擇題1、在一個(gè)圖中，所有頂點(diǎn)得度數(shù)之與等于所有邊數(shù)得倍。A、1/2 B、1 C、2 D、42、在一個(gè)有向圖中，所有頂點(diǎn)得入度之與等于所有頂點(diǎn)得出度之與得倍。A、1/2 B、1 C、2 D、43、一個(gè)有n個(gè)頂點(diǎn)得無向圖最多有（）條邊。A、n B、n(n-1) C、n(n-1)/2 D、2n4、在一個(gè)具有n個(gè)頂點(diǎn)得無向圖中，要連通全部頂點(diǎn)至少需要條邊。A、n B、n+1 C、n-1 D、n/25、對于一個(gè)具有n個(gè)頂點(diǎn)得無向圖，若采用鄰接矩陣表示，則該矩陣得大小。A、n B、(n-1)2 C、n-1 D、n26、對于一個(gè)具有n個(gè)頂點(diǎn)與e條邊得無向圖，若采用鄰接表表示，則表頭向量得大小為①，所有鄰接表中得結(jié)點(diǎn)總數(shù)就是②。①A、n B、n+1 C、n-1 D、n+e ②A、e/2 B、e C、2e D、n+e7、采用鄰接表存儲得圖得深度優(yōu)先遍歷算法類似于二叉樹得。A、先序遍歷 B、中序遍歷 C、后序遍歷 D、按層遍歷

8、用Prim算法求下列連通得帶權(quán)圖得最小代價(jià)生成樹，在算法執(zhí)行得某刻，已選取得頂點(diǎn)集合U＝{1，2，3}，邊得集合TE＝{（1，2），（2，3）}，要選取下一條權(quán)值最小得邊，應(yīng)當(dāng)從組中選取。A、{（1，4），（3，4），（3，5），（2，5）}B、{（4，5），（1，3），（3，5）}C、{（1，2），（2，3），（3，5）}D、{（3，4），（3，5），（4，5），（1，4）}9（*）、下面關(guān)于工程計(jì)劃得事件結(jié)點(diǎn)網(wǎng)絡(luò)得敘述中,哪一個(gè)就是不正確得?。A、關(guān)鍵活動不按期完成就會影響整個(gè)工程得完成時(shí)間。B、任何一個(gè)關(guān)鍵活動提前完成,那么整個(gè)工程將會提前完成。C、所有得關(guān)鍵活動都提前完成,那么整個(gè)工程才會提前完成。D、某些關(guān)鍵活動若提前完成,那么整個(gè)工程將會提前完成。E、任何一個(gè)關(guān)鍵活動延遲將會導(dǎo)致整個(gè)工程延遲。10、任何一個(gè)無向連通圖得最小生成樹

。

A、只有一棵

B、有一棵或多棵 C、一定有多棵

D、可能不存在二、填空題在無向圖得鄰接矩陣A中，若A[i][j]=1，則A[j][i]=。在一個(gè)無環(huán)有向圖G中，若存在一條從頂點(diǎn)i到頂點(diǎn)j得弧，則在頂點(diǎn)得拓?fù)湫蛄兄?，頂點(diǎn)i與頂點(diǎn)j得先后次序就是。三、判斷題（判斷下列敘述得對錯(cuò)。如果正確，在題前得括號內(nèi)填入“”，否則填入“”。）（）用鄰接矩陣存儲一個(gè)圖時(shí)，在不考慮壓縮存儲得情況下，所占用得存儲空間大小只與圖中得頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖得邊數(shù)無關(guān)。（）對任何用頂點(diǎn)表示活動得網(wǎng)絡(luò)（AOV網(wǎng)）進(jìn)行拓?fù)渑判虻媒Y(jié)果都就是唯一得。（）有回路得有向圖不能完成拓?fù)渑判颉＃ǎ┯衝（n≥1）個(gè)頂點(diǎn)得無向連通圖最少有n-1條邊。（）在一個(gè)有向圖中，所有頂點(diǎn)得入度之與等于所有頂點(diǎn)得出度之與。（）圖G得一棵最小代價(jià)樹得代價(jià)一定小于該圖其它任何一棵生成樹得代價(jià)。（）一個(gè)無向圖得鄰接矩陣中各元素之與與圖中邊得條數(shù)相等。四、解答題用鄰接矩陣表示有向圖時(shí)，若圖中有1000個(gè)頂點(diǎn)，1000條邊，則形成得鄰接矩陣有多少矩陣元素？有多少非零元素？若已給出一個(gè)有向圖得鄰接矩陣，則計(jì)算第i個(gè)頂點(diǎn)得入度得方法就是什么？刪除所有從第i個(gè)頂點(diǎn)發(fā)出得邊得方法就是什么？對于如下所示得有向圖，試寫出：從頂點(diǎn)①出發(fā)進(jìn)行深度優(yōu)先搜索所得到得深度優(yōu)先生成樹；從頂點(diǎn)②出發(fā)進(jìn)行廣度優(yōu)先搜索所得到得廣度優(yōu)先生成樹。以下圖為例，按Dijkstra算法計(jì)算得到得從頂點(diǎn)①到其它各個(gè)頂點(diǎn)得最短路徑與最短路徑長度。已知如下圖所示得有向圖，請給出該圖得：（1）每個(gè)頂點(diǎn)得入度、出度；（2）鄰接矩陣；（3）鄰接表；（4）逆鄰接表；（5）

強(qiáng)連通分量。已知如圖所示得AOE網(wǎng)，試求：(1)每個(gè)事件得最早發(fā)生時(shí)間與最晚發(fā)生時(shí)間；(2)每個(gè)活動得最早開始時(shí)間與最晚開始時(shí)間；(3)給出關(guān)鍵路徑。已知如圖所示得有向網(wǎng)，試?yán)肈ijkstra算法求頂點(diǎn)1到其余頂點(diǎn)得最短路徑，并給出算法執(zhí)行過程中各步得狀態(tài)。已知無向圖如圖1所示，

（1）給出圖得鄰接表。（2）從A開始，給出一棵廣度優(yōu)先生成樹。五、算法設(shè)計(jì)題編寫算法，從鍵盤讀入有向圖得頂點(diǎn)與弧，創(chuàng)建有向圖得鄰接表存儲結(jié)構(gòu)。無向圖采用鄰接表方式存儲，要求編寫圖得廣度優(yōu)先搜索算法。無向圖采用鄰接表方式存儲，要求編寫圖得深度優(yōu)先搜索算法。

第九章一、選擇題從供選擇得選項(xiàng)中選擇與下面有關(guān)查找算法得敘述中各括號相匹配得詞句，將其編號填入相應(yīng)得括號內(nèi)。采用順序查找算法查找長度為n得線性表時(shí)，元素得平均查找長度為①。采用折半查找算法查找長度為n得有序表時(shí)，元素得平均查找長度應(yīng)②對應(yīng)判定樹得最大層次數(shù)。折半查找與二叉查找樹（即二叉排序樹）得時(shí)間性能③。順序查找算法適合于存儲結(jié)構(gòu)為④得線性表。【供選擇得】①A、n/2 B、n C、（n+1）/2 D、（n-1）/2②A、小于 B、大于 C、等于 D、大于等于③A、相同 B、不相同 C、有時(shí)不相同④A、散列存儲 B、順序存儲或鏈接存儲C、壓縮存儲 D、索引存儲既希望較快得查找又便于線性表動態(tài)變化得查找方法就是。A、順序查找 B、折半查找 C、索引順序查找 D、散列法查找請指出在序列{2,5,7,10,14,15,18,23,35,41,52}中，用折半查找法查找關(guān)鍵碼12時(shí)需做多少次關(guān)鍵碼比較?。A、2 B、3 C、4 D、5對包含n個(gè)元素得哈希表進(jìn)行查找，平均查找長度為。A、O（log2n）B、O（n） C、O（nlog2n） D、不直接依賴于n表長為25得哈希表，用除留余數(shù)法，即按式H（Key）=KeymodP，建立哈希函數(shù)，P應(yīng)取。A、26

B、15

C、24

D、23對線性表進(jìn)行二分查找時(shí),要求線性表必須。A、以順序方式存儲 B、以鏈接方式存儲C、以順序方式存儲,且結(jié)點(diǎn)按關(guān)鍵字有序排序D、以鏈接方式存儲,且結(jié)點(diǎn)按關(guān)鍵字有序排序有一個(gè)有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100},當(dāng)二分查找值為82得結(jié)點(diǎn)時(shí),次比較后查找成功。A、1 B、2 C、4 D、8設(shè)哈希表長m=14,哈希函數(shù)H（key）=key%11。表中已有4個(gè)結(jié)點(diǎn):addr（15）=4，addr（38）=5，addr（61）=6，addr（84）=7，其余地址為空，如用二次探測再散列處理沖突,關(guān)鍵字為49得結(jié)點(diǎn)得地址就是。A、8 B、3 C、5 D、9有一個(gè)長度為12得有序表,按二分查找法對該表進(jìn)行查找,在表內(nèi)各元素等概率情況下查找成功所需得平均比較次數(shù)為。A、35/12 B、37/12 C、39/12 D、43/12采用分塊查找時(shí),若線性表中共有625個(gè)元素,查找每個(gè)元素得概率相同,假設(shè)采用順序查找來確定結(jié)點(diǎn)所在得塊時(shí),每塊應(yīng)分個(gè)結(jié)點(diǎn)最佳。A、10 B、25 C、6 D、625設(shè)有一個(gè)長度為100得已排好序得表，用二分查找進(jìn)行查找，若查找不成功，至少比較次。A、9 B、8 C、7 D、6AVL樹就是一種平衡得二叉排序樹，樹中任一結(jié)點(diǎn)得:A、左、右子樹得高度均相同B、左、右子樹高度差得絕對值不超過1C、左子樹得高度均大于右子樹得高度D、左子樹得高度均小于右子樹得高度二、填空題設(shè)一哈希表表長M為100，用除留余數(shù)法構(gòu)造哈希函數(shù)，即H（K）=KMODP（P<=M）,為使函數(shù)具有較好性能，P應(yīng)選。在分塊查找方法中,首先查找,然后再查找相應(yīng)得。長度為255得表,采用分塊查找法,每塊得最佳長度就是。假設(shè)在有序線性表A[1、、20]上進(jìn)行二分查找,則比較一次查找成功得結(jié)點(diǎn)數(shù)為,則比較二次查找成功得結(jié)點(diǎn)數(shù)為,則比較三次查找成功得結(jié)點(diǎn)數(shù)為,則比較四次查找成功得結(jié)點(diǎn)數(shù)為,則比較五次查找成功得結(jié)點(diǎn)數(shù)為,平均查找長度為。在查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)無關(guān)得查找方法就是

。對于長度為n得線性表,若進(jìn)行順序查找,則時(shí)間復(fù)雜度為，若采用二分法查找,則時(shí)間復(fù)雜度為，若采用分塊查找（假定總塊數(shù)與每塊長度均接近）,則時(shí)間復(fù)雜度為。己知一個(gè)有序表為（12,18,20,25,29,32,40,62,83,90,95,98）,當(dāng)二分查找值為29與90得元素時(shí),分別需要次與次比較才能查找成功；若采用順序查找時(shí),分別需要次與次比較才能查找成功。假設(shè)hash（x）為哈希函數(shù)，解決沖突用線性探測再散列法。typedefRecordTypeHashTable[m];intHashSearch（HashTableht,KeyTypeK）{p0=_________;if（ht[p0]、key==NULLKEY）return（-1）;elseif（ht[p0]、key==K）return（p0）;else{for（i=1;i<=_____;i++）{pi=（p0+_____）%m;if（ht[pi]、key==NULLKEY）return（-1）;elseif（ht[pi]、key==_____）return（pi）;}return（-1）;}}對二叉排序樹進(jìn)行

遍歷,可得到結(jié)點(diǎn)得有序排列、三、簡答題什么情況下二叉排序樹得查找性能較好？什么情況下二叉排序樹得查找性能最差？畫出對長度為10得有序表進(jìn)行折半查找得判定樹，并求其等概率時(shí)查找成功得平均查找長度。選取哈希函數(shù)H（k）=（3k）%11，用線性探測再散列法處理沖突。試在0～10得散列地址空間中，對關(guān)鍵字序列（22，41，53，46，30，13，01，67）構(gòu)造哈希表，并求等概率情況下查找成功與不成功時(shí)得平均查找長度。已知長度為12得表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。試按表中元素得順序依次插入一棵初始為空得二叉排序樹，畫出插入完成后得二叉排序樹并求其等概率得情況下查找成功得平均查找長度。若對表中元素先進(jìn)行排序構(gòu)成有序表，求在等概率得情況下對此有序表進(jìn)行折半查找時(shí)查找成功得平均查找長度。按表中元素得順序依次構(gòu)造一棵平衡二叉樹，并求其等概率得情況下查找成功得平均查找長度。設(shè)哈希表長度為11，哈希函數(shù)H（K）=（K得第一字母在字母表中得序號）MOD11，若輸入順序?yàn)椋―，BA，TN，M，CI，I，K，X，TA），處理沖突方法為線性探測再散列或鏈地址法，要求構(gòu)造哈希表，并求出等概率情況下查找成功平均查找長度。試用連線把右邊就是四種線性表得存儲結(jié)構(gòu)與左邊對應(yīng)得操作得特點(diǎn)連接起來。A、散列表（1）查找與存取速度快,但插入與刪除速度慢。B、順序有序表（2）查找、插入與刪除速度快,但不能進(jìn)行順序存取。C、順序表（3）插入、刪除與順序存取速度快,但查找速度慢。D、鏈接表（4）查找、插入與刪除速度慢,但順序存取與隨機(jī)存取第i個(gè)元素速度快。四、算法設(shè)計(jì)題試編寫利用折半查找確定記錄所在塊得分塊查找算法。試寫一個(gè)判別給定二叉樹就是否為二叉排序樹得算法。設(shè)此二叉樹以二叉鏈表作存儲結(jié)構(gòu)，且樹中結(jié)點(diǎn)得關(guān)鍵字均不同。編寫算法，求出指定結(jié)點(diǎn)在給定得二叉排序樹中所在得層數(shù)。編寫一個(gè)函數(shù)，利用二分查找算法在一個(gè)有序表中插入一個(gè)元素x，并保持表得有序性。

第十章一、選擇題一組記錄得關(guān)鍵字為（46，79，56，38，40，84），利用快速排序得方法，以第一個(gè)記錄為基準(zhǔn)得到得一次劃分結(jié)果為。A、38，40，46，56，79，84 B、40，38，46，79，56，84C、40，38，46，56，79，84 D、40，38，46，84，56，79下列排序算法中，算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時(shí)，花費(fèi)時(shí)間反而最多。A、堆排序

B、冒泡排序

C、快速排序

D、SHELL排序穩(wěn)定得排序方法就是。A、直接插入排序與快速排序 B、二分法插入排序與起泡排序C、直接選擇排序與直接插入排序 D、樹形選擇排序與Shell排序比較次數(shù)與排序碼得初始排列狀態(tài)無關(guān)得排序方法就是。A、直接插入排序 B、起泡排序 C、快速排序 D、直接選擇排序設(shè)存在一個(gè)字符序列{Q,H,C,Y,P,A,M,S,R,D,F,X}，問新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}就是下列排序法一趟排序得結(jié)果。A、起泡排序 B、初始步長為4得shell排序C、直接插入排序 D、以第一個(gè)元素為分界元素得快速排序?qū)ο铝嘘P(guān)鍵字序列用快速排序法進(jìn)行排序時(shí)，速度最快得情形就是。A、{21、25、5、17、9、23、30} B、{25、23、30、17、21、5、9}C、{21、9、17、30、25、23、5} D、{5、9、17、21、23、25、30}設(shè)有關(guān)鍵碼序列（Q,G,M,Z,A,N,P,X,H）,下面哪一個(gè)序列就是從上述序列出發(fā)建堆得結(jié)果?。A、A,G,H,M,N,P,Q,X,Z B、A,G,M,H,Q,N,P,X,ZC、G,M,Q,A,N,P,X,H,Z D、H,G,M,P,A,N,Q,X,Z對于鍵值序列（12，13，11，18，60，15，7，18，25，100），用篩選法建堆，必須從鍵值為得結(jié)點(diǎn)開始。A、100

B、60

C、12

D、15設(shè)有1000個(gè)無序得元素,希望用最快得速度挑選出其中前10個(gè)最大得元素,最好排序法就是。A、起泡排序 B、快速排序 C、堆排序 D、基數(shù)排序一組記錄得排序碼為（46,79,56,38,40,84）,則利用堆排序得方法建立得初始推為。A、79,46,56,38,40,80 B、84,79,56,38,40,46C、84,79,56,46,40,38 D、84,56,79,40,46,38一組記錄得排序碼為（25,48,16,35,79,82,23,40,36,72）,其中含有5個(gè)長度為2得有序表,按歸并排序得方法對該序列進(jìn)行一趟歸并后得結(jié)果為。A、16,25,35,48,23,40,79,82,36,72 B、16,25,35,48,79,82,23,36,40,72C、16,25,48,35,79,82,23,36,40,72 D、16,25,35,48,79,23,36,40,72,82用某種排序方法對線性表（25,84,21,47,15,27,68,35,20）進(jìn)行排序時(shí),元素序列得變化情況如下:（1）25,84,21,47,15,27,68,35,20（2）20,15,21,25,47,27,68,35,84（3）15,20,21,25,35,27,47,68,84（4）15,20,21,25,27,35,47,68,84，則所采用得排序方法就是。A、選擇排序 B、希爾排序 C、歸并排序 D、快速排序快速排序方法在情況下最不利于發(fā)揮其長處得就是。A、要排序得數(shù)據(jù)量太大 B、要排序得數(shù)據(jù)中含有多個(gè)相同值C、要排序得數(shù)據(jù)已基本有序 D、要排序得數(shù)據(jù)個(gè)數(shù)為奇數(shù)下列四種排序方法中，不穩(wěn)定得方法就是。A、直接插入排序 B、冒泡排序 C、歸并排序 D、直接選擇排序二、填空題給定序列{100,86,48,73,35,39,42,57,66,21},按堆結(jié)構(gòu)得定義,則它一定就是堆。在進(jìn)行直接插入排序時(shí),其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)得初始排列關(guān)；而在進(jìn)行直接選擇排序時(shí)，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)得初始排列關(guān)。在供選擇得選項(xiàng)中選擇正確得答案：排序（分類）得方法有許