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

第1章緒論一、填空題數(shù)據(jù)結(jié)構(gòu)就是一門研究非數(shù)值計算得程序設計問題中計算機得 以及它們之間得 與 等得學科。數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D就是 得有限集合，R就是D上得 有限集合。數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別就是 與 。若細分為4類，分別就是 、 、 與 。線性結(jié)構(gòu)中元素之間存在 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 關(guān)系。在線性結(jié)構(gòu)中，第一個結(jié)點 前驅(qū)結(jié)點，其余每個結(jié)點有且只有 個前驅(qū)結(jié)點；最后一個結(jié)點 后繼結(jié)點，其余每個結(jié)點有且只有 個后繼結(jié)點。在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 結(jié)點，其余每個結(jié)點有且只有 個前驅(qū)結(jié)點；葉子結(jié)點沒有后繼結(jié)點，其余每個結(jié)點得后繼結(jié)點數(shù)可以任意。在圖形結(jié)構(gòu)中，每個結(jié)點得前驅(qū)結(jié)點數(shù)與后繼結(jié)點數(shù)可以 。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)得、數(shù)據(jù)得與數(shù)據(jù)得這三個方面得內(nèi)容。數(shù)據(jù)得存儲結(jié)構(gòu)可用四種基本得存儲方法表示，它們分別就是 、 、 與 。數(shù)據(jù)得運算最常用得有5種，它們分別就是 、 、 、 、 。一個算法得效率可分為 效率與 效率。二、單項選擇題數(shù)據(jù)結(jié)構(gòu)中，與所使用得計算機無關(guān)得就是數(shù)據(jù)得（）結(jié)構(gòu)。A、存儲 B、物理 C、邏輯 D、物理與存儲算法分析得目得就是（）。A、找出數(shù)據(jù)結(jié)構(gòu)得合理性 B、研究算法中得輸入與輸出得關(guān)系C、分析算法得效率以求改進 D、分析算法得易懂性與文檔性算法分析得兩個主要方面就是：（）。A、空間復雜性與時間復雜性 B、正確性與簡明性C、可讀性與文檔性 D、數(shù)據(jù)復雜性與程序復雜性計算機算法指得就是（）。A、計算方法 B、排序方法 C、解決問題得有限運算序列 D、調(diào)度方法計算機算法必須具備輸入、輸出與（）等5個特性。A、可行性、可移植性與可擴充性 B、可行性、確定性與有窮性C、確定性、有窮性與穩(wěn)定性 D、易讀性、穩(wěn)定性與安全性三、判斷下列敘述得對錯。（）數(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ù)據(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)。四、設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++; }五、分析下面各程序段得時間復雜度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ù)據(jù)邏輯結(jié)構(gòu)S=（D,R），試按各小題所給條件畫出這些邏輯結(jié)構(gòu)得圖示，并確定相對于關(guān)系R，哪些結(jié)點就是開始結(jié)點，哪些結(jié)點就是終端結(jié)點？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)}

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

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

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

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

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

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

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

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

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

。

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

D、D，A，B，CS最多能容納4個元素。現(xiàn)有6個元素按A、B、C、D、E、F得順序進棧,問下列哪一個序列就是可能得出棧序列?。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設鏈式棧中結(jié)點得結(jié)構(gòu)為（data,next），且top就是指向棧頂?shù)弥羔?。若想在鏈式棧得棧頂插入一個由指針s所指得結(jié)點，則應執(zhí)行下列哪一個操作？。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；一個隊列得入隊序列就是1，2，3，4，則隊列得輸出序列就是

。

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

⑴如進站得車廂序列為123，則可能得到得出站車廂序列就是什么？⑵如進站得車廂序列為123456，能否得到435612與135426得出站序列，并說明原因。（即寫出以“S”表示進棧、以“X”表示出棧得棧操作序列）。設有一個順序棧S，元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素得出棧順序為s2,s3,s4,s6,s5,s1，則順序棧得容量至少應為多少？簡述以下算法得功能（其中棧與隊列得元素類型均為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、試寫一個算法，判斷依次讀入得一個以@為結(jié)束符得字母序列，就是否為形如‘序列1&序列2’模式得字符序列。其中序列1與序列2中都不含字符’&’，且序列2就是序列1得逆序列。例如，‘a(chǎn)+b&b+a’就是屬該模式得字符序列，而‘１+３&３－１

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

_。A、可以順序存儲 B、數(shù)據(jù)元素就是一個字符C、可以鏈接存儲 D、數(shù)據(jù)元素可以就是多個字符3、長度為1得串等價于一個字符型常量，這種說法就是。A、正確得 B、錯誤得二、簡答題設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))。設主串為”abcaabbabcabaacbacba”模式串為”abcabaa”。計算模式串得next,nextval函數(shù)值，并給出利用nextval函數(shù)值進行KMP模式匹配得每一趟過程。第五章數(shù)組與廣義表一、選擇題1、稀疏矩陣一般得壓縮存儲方法有兩種,即。A、數(shù)組與三維數(shù)組 B、三元組與散列C、三元組與十字鏈表 D、散列與十字鏈表2、若采用三元組壓縮技術(shù)存儲稀疏矩陣,只要把每個元素得行下標與列下標互換,就完成了對該矩陣得轉(zhuǎn)置運算,這種觀點（）。A、正確 B、錯誤3、數(shù)組元素得下標值越大，存取時間越長，這種說法就是。A、正確得 B、錯誤得4、廣義表(a,(b),((c)))得表尾就是。A、((c)) B、(((c)))C、(c) D、((b),((c)))二、填空題1、一維數(shù)組得邏輯結(jié)構(gòu)就是，存儲結(jié)構(gòu)就是。對于二維數(shù)組，有與兩種不同得存儲方式。對于一個二維數(shù)組A[m][n]，若采取按行存儲得方式，則任一數(shù)組元素A[i][j]相對于A[0][0]得地址為。2、二維數(shù)組A[10][20]采用列序為主方式存儲，每個元素占一個存儲單元，并且A[0][0]得存儲地址就是200，則A[6][12]得地址就是。3、設n行n列得下三角矩陣A已壓縮到一維數(shù)組S[1、、n*(n+1)/2]中,若按行序為主存儲,則A[i][j]對應得S中得存儲位置就是。三、簡答題1、設有一個1010得對稱矩陣A[10][10]，采取按行壓縮存儲得方式將其上三角得矩陣元存放于一個一維數(shù)組B[]中，則數(shù)組B[]得容量應有多大？若設A[0][0]為第一個元素，存放于B[0]，且數(shù)組A[][]得每一個數(shù)組元素在數(shù)組B[]中占一個數(shù)組元素位置，則A[8][5]在數(shù)組B[]中得地址就是多少？2（*）、設有三對角矩陣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、求下列廣義表運算得結(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、設廣義表L=((),())，則GETHEAD(L)就是；GETTAIL(L)就是；L得長度就是；深度就是。四、算法題1、將數(shù)組C[n]中所有奇數(shù)移到偶數(shù)之前，要求時間復雜度為O(n)。第六章樹與森林一、選擇題1、設二叉樹有n個結(jié)點且根結(jié)點處于第1層，則其高度為（）。 A、n-1 B、log2（n+1）-1 C、log2n+1 2、設高度為h（空二叉樹得高度為0，只有一個結(jié)點得二叉樹得高度為1）得二叉樹只有度為2與度為0得結(jié)點，則該二叉樹中所含結(jié)點至少有（）個。A、2h B、2h-1 C、2h+1 D、h+13、設森林F中有4棵樹，第1、2、3、4棵樹得結(jié)點個數(shù)分別為n1、n2、n3、n4，當把森林F轉(zhuǎn)換成一棵二叉樹后，其根結(jié)點得右子樹中有（）個結(jié)點。A、n1-1 B、n1+n2+n3 C、n2+n3+n4 D、n4、將含有82個結(jié)點得完全二叉樹從根結(jié)點開始順序編號，根結(jié)點為第1號，其她結(jié)點自上向下，同一層自左向右連續(xù)編號。則第40號結(jié)點得雙親結(jié)點得編號為（）。A、20 B、19 C、81 D、805、對二叉樹從1開始編號，要求每個結(jié)點得編號大于其左右孩子得編號，同一個結(jié)點得左右孩子中，其左孩子得編號小于其右孩子得編號，則可采用（）實現(xiàn)編號。

A、先序遍歷

B、中序遍歷

C、后序遍歷

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

A、空或只有一個結(jié)點

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

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

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

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

第七章一、選擇題1、在一個圖中，所有頂點得度數(shù)之與等于所有邊數(shù)得倍。A、1/2 B、1 C、2 D、42、在一個有向圖中，所有頂點得入度之與等于所有頂點得出度之與得倍。A、1/2 B、1 C、2 D、43、一個有n個頂點得無向圖最多有（）條邊。A、n B、n(n-1) C、n(n-1)/2 D、2n4、在一個具有n個頂點得無向圖中，要連通全部頂點至少需要條邊。A、n B、n+1 C、n-1 D、n/25、對于一個具有n個頂點得無向圖，若采用鄰接矩陣表示，則該矩陣得大小。A、n B、(n-1)2 C、n-1 D、n26、對于一個具有n個頂點與e條邊得無向圖，若采用鄰接表表示，則表頭向量得大小為①，所有鄰接表中得結(jié)點總數(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)圖得最小代價生成樹，在算法執(zhí)行得某刻，已選取得頂點集合U＝{1，2，3}，邊得集合TE＝{（1，2），（2，3）}，要選取下一條權(quán)值最小得邊，應當從組中選取。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)于工程計劃得事件結(jié)點網(wǎng)絡得敘述中,哪一個就是不正確得?。A、關(guān)鍵活動不按期完成就會影響整個工程得完成時間。B、任何一個關(guān)鍵活動提前完成,那么整個工程將會提前完成。C、所有得關(guān)鍵活動都提前完成,那么整個工程才會提前完成。D、某些關(guān)鍵活動若提前完成,那么整個工程將會提前完成。E、任何一個關(guān)鍵活動延遲將會導致整個工程延遲。10、任何一個無向連通圖得最小生成樹

。

A、只有一棵

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

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

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

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

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

B、15

C、24

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

。對于長度為n得線性表,若進行順序查找,則時間復雜度為，若采用二分法查找,則時間復雜度為，若采用分塊查找（假定總塊數(shù)與每塊長度均接近）,則時間復雜度為。己知一個有序表為（12,18,20,25,29,32,40,62,83,90,95,98）,當二分查找值為29與90得元素時,分別需要次與次比較才能查找成功；若采用順序查找時,分別需要次與次比較才能查找成功。假設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）;}}對二叉排序樹進行

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

第十章一、選擇題一組記錄得關(guān)鍵字為（46，79，56，38，40，84），利用快速排序得方法，以第一個記錄為基準得到得一次劃分結(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ù)有序時，花費時間反而最多。A、堆排序

B、冒泡排序

C、快速排序

D、SHELL排序穩(wěn)定得排序方法就是。A、直接插入排序與快速排序 B、二分法插入排序與起泡排序C、直接選擇排序與直接插入排序 D、樹形選擇排序與Shell排序比較次數(shù)與排序碼得初始排列狀態(tài)無關(guān)得排序方法就是。A、直接插入排序 B、起泡排序 C、快速排序 D、直接選擇排序設存在一個字符序列{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、以第一個元素為分界元素得快速排序?qū)ο铝嘘P(guān)鍵字序列用快速排序法進行排序時，速度最快得情形就是。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}設有關(guān)鍵碼序列（Q,G,M,Z,A,N,P,X,H）,下面哪一個序列就是從上述序列出發(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é)點開始。A、100

B、60

C、12

D、15設有1000個無序得元素,希望用最快得速度挑選出其中前10個最大得元素,最好排序法就是。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個長度為2得有序表,按歸并排序得方法對該序列進行一趟歸并后得結(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）進行排序時,元素序列得變化情況如下:（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ù)中含有多個相同值C、要排序得數(shù)據(jù)已基本有序 D、要排序得數(shù)據(jù)個數(shù)為奇數(shù)下列四種排序方法中，不穩(wěn)定得方法就是。A、直接插入排序 B、冒泡排序 C、歸并排序 D、直接選擇排序二、填空題給定序列{100,86,48,73,35,39,42,57,66,21},按堆結(jié)構(gòu)得定義,則它一定就是堆。在進行直接插入排序時,其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)得初始排列關(guān)；而在進行直接選擇排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)得初始排列關(guān)。在供選擇得選項中選擇正確得答案：排序（分類）得方法有許