數(shù)據(jù)結構（Java語言描述）習題及答案（羅福強）第1-5章

數(shù)據(jù)結構（Java語言描述）習題及答案

1.5習題

填空題

1.數(shù)據(jù)的物理結構包括順序結構的表示和存儲和鏈式結構的表示和存儲。

2.對于給定的n個元素，可以構造出的邏輯結構有（集合結構），（線性結構），（樹

型結構），（圖型結構）四種。

3.一個算法具有5個特性：（有窮性）、（確定性）、（可行性），有零個或多個

輸入、有一個或多個輸出。

4.抽象數(shù)據(jù)類型被形式地定義為（D,S,P）,其中D是（數(shù)據(jù)元素）的有限

集合，S是D上的（關系）有限集合，P是對D的（基本操作）集合。

5.數(shù)據(jù)結構主要包括數(shù)據(jù)的（邏輯結構）、數(shù)據(jù)的（存儲結構）和數(shù)據(jù)的（操

作）這三個方面的內(nèi)容。

6.一個算法的效率可分為（時間）效率和（空間）效率。

二.單項選擇題

1.線性結構是數(shù)據(jù)元素之間存在一種（D）。

A.一對多關系B.多對多關系C.多對一關系D.一對一關系

2.數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的（C）結構。

A.存儲B.物理C.邏輯D.物理和存儲

3.算法分析的目的是（B）。

A.找出數(shù)據(jù)結構的合理性B.分析算法的效率以求改進

C.研究算法中的輸入和輸出的關系D.分析算法的易懂性和文檔性

4.算法分析的兩個主要方面是（A）。

A.空間復雜性和時間復雜性B.正確性和簡明性

C.可讀性和文檔性D.數(shù)據(jù)復雜性和程序復雜性

5.計算機算法指的是（C）。

A.計算方法B.排序方法

C.解決問題的有限運算序列D.調(diào)度方法

6.從邏輯上可以把數(shù)據(jù)結構分為（A）。

1

A.線性結構和非線性結構B.緊湊結構和非緊湊結構

C.動態(tài)結構和靜態(tài)結構D.內(nèi)部結構和外部結構

三.計算題

1.計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為（（n-2）（n+3）/2）。

for（i=l；i<n-l；i++）

for（j=n;j>=i;j-）

2.在有n個選手參加的單循環(huán)賽中，總共將進行（n（n-l）/2）場比賽。

3.試給出下面兩個算法的時間復雜度。

（1）for（i=l；i<=n；i++）0（n）

x=x+l;

（2）for（i=l；i<=n；i++）0（n2）

for（j=l；j<=n；j++）

x=x+l;

2.4習題

一.填空題

1.線性表的兩種存儲結構分別為（順序存儲）和（鏈式存儲）。

2.順序表中，邏輯上相鄰的元素，其物理位置一一定相鄰。在單鏈表中，

邏輯上相鄰的元素，其物理位置不一定相鄰。

3.若經(jīng)常需要對線性表進行插入和刪除操作，則最好采用（鏈式）存儲結

構，若線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求

以最快的速度存取線性表中的元素，則最好采用（順序）存儲結構。

4.在順序表中等概率下插入或刪除一個元素，需要平均移動（n/2）元素，具體

移動的元素個數(shù)與（插入或刪除位置）有關。

5.在帶頭結點的非空單鏈表中，頭結點的存儲位置由（head頭指針）指示，首

元素結點的存儲位置由（head.next）指示，除首元素結點外，其它任一元

素結點的存儲位置由（其直接前驅(qū)）指示。

6.已知L是帶頭結點的單鏈表，且p結點既不是首元素結點，也不是尾元素

結點。按要求從下列語句中選擇合適的語句序列。

a.在p結點后插入s結點的語句序列是：o

s.next=p.next;p.next=s;

b.在p結點前插入s結點的語句序列是：o

2

q=head;while(q.next!=p)q=q.next;s.next=p;q.next=s;

C.在表首插入S結點的語句序列是：0

s.next=head.next;head.next=s;

d.在表尾插入s結點的語句序列是：o

while(p.next!=null)p=p.next;s.next=null;p.next=s;

二.單項選擇題

1.線性表是(A)。

A.一個有限序列，可以為空B.一個有限序列，不能為空

C.一個無限序列，可以為空D.一個無限序列，不能為空

2.帶頭結點的單鏈表L為空的判定條件是(B)。

A.head==nullB.head,next==null

C.head.next==LD.head!=null

3.在表長為n的單鏈表中，算法時間復雜度為0(n)的操作為(D)。

A.刪除p結點的直接后繼結點B.在p結點之后插入一個結點

C.刪除表中第一個結點D.查找單鏈表中第i個結點

4.在表長為n的順序表中，算法時間復雜度為0(1)的操作為(C)。

A.在第i個元素前插入一個元素B.刪除第i個元素

C.在表尾插入一個元素D.查找其值與給定值相等的一個元素

5.設單鏈表中指針p指向結點ai,若要刪除ai之后的結點，則需修改指針的

操作為(B)。

A.p=p.nextB.p.next=p.next.next

C.p=p.next.nextD.next=p

三.綜合題

1.試比較線性表的兩種存儲結構各自的優(yōu)缺點。

順序存儲：

優(yōu)點：存儲密度大，存儲空間利用率高，可隨機存取。

缺點：插入或刪除元素時不方便。

鏈式存儲：

優(yōu)點：插入或刪除元素時很方便，使用靈活。

結點空間可以動態(tài)申請和釋放；

缺點：存儲密度小，存儲空間利用率低，非隨機存取。

2.設線性表存于數(shù)組a[0..n-l]的前R個分量中，且遞增有序，試寫一算法，

將x插入到線性表的適當位置上，以保持線性表的有序性。

publicvoidsortOrder(Tx){

inti=0,j;

3

while(i<length)

if(((Comparable)x).compareTo(listArray[i])>=0)

i++;

else{

for(j=length-1；j>=i;j-)

listArray[j+1]=listArray[j];

listArray[i]=x;

length++;

break;

3.試分別以不同的存儲結構實現(xiàn)線性表的就地逆置算法，即在原表的存儲空

間將線性表(al,a2,an)逆置為(an,an-1,al)o

就地逆置：(al,a2,...,an)逆置為(an,...,a2,al)

publicvoidinverse(){

inti=0,j;

Ttemp;

for(j=length-l;i<=j;i++,j-){

temp=listArrayfi];

listArray[i]=listArray[j];

listArray[j]=temp;

)

)

〃先將L的頭節(jié)點head的Next域置為NULL變成一個空鏈表，然后用p結點

采用頭插法插入到L中。

publicvoidinverse(){

if(head!=null||head.next!=null){

Node<T>p=head.next;

head.next=null;

Node<T>q=null;

while(p!=null){

q=p;

p二p.next;

q.next=head.next;

head.next=q;

4.試編寫在帶頭結點的單鏈表中刪除一個最小值結點的算法。

publicvoiddelMin()

{

Node<T>p=head,q=head.next,p1=null,q1=null;

if(!isEmpty()){

Tmin=q.data;

while(q!=null){

if(((Comparable)min).compareTo(q.data)>0){

min=q.data;

pl=p;

ql=q;

4

p=q；

q=q.next;

)

pl.next=ql.next;

}

Length—;

)

5.設有一個雙鏈表，每個結點中除有prior、data和next三個域外，還有一個

訪問頻度域freq,在鏈表被起用之前，其值均初始化為零。每當對鏈表進

行一次LocateNode(L,x)運算，便令元素值為x的結點的freq域的值加1,

并調(diào)整表中結點的次序，使其按訪問頻度的遞減序排列，以便使頻繁訪問

的結點總是靠近表頭。試寫一個符合上述要求的算法LocateNode(L,x)o

static<TextendsComparable>booleanLocateNode(dlinklistL,Tx){

DuNode<T>p=L.getHead().next;

〃指針p用于查找第一個data域等于x的結點

DuNode<T>q;

while(p!=null&&(p.data).equals(x)==false)

p=p.next;

if(p=null)//p為空，意味著沒有找到data域等于x的結點

returnfalse;

else{

p.freq++;//將找到的data域等于x的結點的訪問頻度值加1

q=p.prior;

//指針q用于查找p的前面結點中第一個freq域不小于當前p所指

結點的freq域的結點

while(q!=L.getHead()&&(q.freq).compareTo(p.freq)<0))

q=q.prior;

if(q!=p.prior){〃如果q發(fā)生了前移，才有必要移動p

p.prior.next=p.next;

if(p.next!=null){

p.next.prior=p.prior;

〃如果p不是終端結點，才有必要修改p的后繼結點的

prior域

p.prior=q;

p.next=q.next;

q.next=p;

p.next.prior=p;//將p插入到q的后邊

returntrue;

6.一個單循環(huán)鏈表F,每個結點包含三個域：pre>data和next,其中pre為

null,將其變?yōu)殡p循環(huán)鏈表的算法如下，請對算法中的空白處填空：

intdouble_list(DuLinkListF)

5

DuLNode*p,*q;

if(F.next==F)

{F.pre二F;return;}/*循環(huán)鏈表為空的情況*/

q=F;p=F.next;

while(p!=q)

{

p.pre=q;

q=_B____；

p=p.next;

}/*while*/

p.pre=q;

return0;

3.4習題

一.單項選擇題

1.一個棧的入棧序列a,b,c,d,e,則棧的不可能的輸出序列是_C_o

A.edcbaB.decbaC.dceabD.abcde

2.若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間top[i]代表第i個棧

(i=l,2)棧頂，棧1的底在v[l],棧2的底在V[m],則棧滿的條件是

(B)o

A.top[2]-top[l]|=0B.top[l]+l=top[2]

C.top[l]+top[2]=mD.topfl]=top[2]

3.若已知一個棧的入棧序列是1,2,3,…，n,其輸出序列為pl,p2,

p3,...?pn,若pl=n,則pi為_C_。

A.iB.n=iC.n-i+1D.不確定

4.棧結構通常采用的兩種存儲結構是_A_。

A.順序存儲結構和鏈式存儲結構B.散列方式和索引方式

C.鏈表存儲結構和數(shù)組D.線性存儲結構和非線性存儲結構

5.判定一個棧ST(最多元素為m0)為空的條件是_B_。

A.ST.top!=-1B.ST.top==-1

C.ST.top!=mO-1D.ST.top==mO-1

6.判定一個棧ST(最多元素為mO)為棧滿的條件是_D_。

A.ST.top!=-1B.ST.top==-1

C.ST.top!=mO-1D.ST.top==mO-1

7.棧的特點是_B—,隊列的特點是_A_o

A.先進先出B.先進后出

8.一個隊列的入列序列是1,2,3,4,則隊列的輸出序列是_B_。

A.4,3,2,1B.1,2,3,4

6

C.1,4,3,2D.3,2,4,1

9.判定一個循環(huán)隊列QU（最多元素為mO）為空的條件是_A_o

A.front==rearB.front!=rear

C.front==（rear+1）%m0D.front!=（rear+1）%m0

10.判定一個循環(huán)隊列QU（最多元素為mO）為滿隊列的條件是_C_o

A.front==rearB.front!=rear

C.front==（rear+1）%m0D.front!=（rear+1）%m0

11.循環(huán)隊列用數(shù)組A[0,m-1]存放其元素值，已知其頭尾指針分別是front和

rear,則當前隊列中的元素個數(shù)是_A_。

A.（rear-front+m）%mB.rear-front+1

C.rear-front-1D.rear-front

12.棧和隊列的共同點是_C_o

A.都是先進后出B.都是先進先出

C.只允許在端點處插入和刪除元素D.沒有共同點

13.向一個棧頂指針為HS的鏈棧中插入一個s所指結點時，則執(zhí)行_C_。（不帶

空的頭結點）

A.HS.next=s;B.s.next=HS.next;HS.next=s;

C.s.next=HS;HS=s;D.s.next=HS;HS=HS.next;

14.從一個棧頂指針為HS的鏈棧中刪除一個結點時，用x保存被刪結點的值，

則執(zhí)行_D_。（不帶空的頭結點）

A.x=HS;HS=HS.next;B.x=HS.data;

C.HS=HS.next;x=HS.data;D.x=HS.data;HS=HS.next;

二.填空題

1.向棧中壓入元素的操作是（先移動棧頂指針，后存入元素）。

2.對棧進行退棧時的操作是（先取出數(shù)據(jù)元素，后移動棧頂指針）。

3.在一個循環(huán)隊列中，隊首指針指向隊首元素的（前一個位置）。

4.從循環(huán)隊列中刪除一個元素時，其操作是（先移動隊首指針，后取出元

素）。

5.在具有n個單元的循環(huán)隊列中，隊滿時共有（n-1）個元素。

6.一個棧的輸入序列是12345,則棧的輸出序列43512是（不可能的）。

7.一個棧的輸入序列是12345,則棧的輸出序列12345是（可能的）。

8.在棧頂指針為HS的鏈棧中，判定?？盏臈l件是（HS==null）。

三.算法設計題：

1.設順序表va中的數(shù)據(jù)元數(shù)遞增有序。試寫一算法，將x插入到順序表的適

當位置上，以保持該表的有序性。

2.試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表

（al,a2,….an）逆置為（an,al）。

7

3.試編寫一個遍歷及顯示隊列中元素的算法。

publicvoidnextOrder()

inti,j=front;

for(i=1;i<=size();i++)

j=(j+1)%queueArray.length;

System.out.println(queueArray[j]);

4.設一循環(huán)隊列Queue,只有頭指針front,不設尾指針，另設一個內(nèi)含元素

個數(shù)的計數(shù)器，試寫出相應的進隊、出隊算法。

publicvoidEnQueue（Tobj）

if(count=queueArray.length-l){〃隊滿

T[]p=(T[])newObject[queueArray.length*2];

inti=front+1,j=l,m=1;

while(m<count){

p[j]=queueArray[i];

i=(i+l)%queueArray.length;

j++;m++；

)

queueArray=p;

front=0;

}

count++；

queueArray[(front+count)%queueArray.length]=obj;

)

publicTDeQueue()

(

if(count==0){

System.out.println("隊列已空，無法出隊！”);

returnnull;

)

front=(front+1)%queueArray.length;

count-;

returnqueueArray[front];

5.設計一算法能判斷一個算術表達式中的圓括號配對是否正確。（提示：對

表達式進行掃描，凡遇到“（”就進棧，遇到“）”就退出棧頂?shù)摹埃ā保磉_式

掃描完畢時棧若為空則圓括號配對正確。）

publicstaticbooleanmatching(char[]exp)

intstate=l,i=0;

sequenceStack<Character>s=newsequenceStack<Character>();

/*盅義一個順序棧*/

while(i<exp.length&&state==l){

switch(exp[i]){

8

case

{

s.push(exp[i]);

i++；

break;

)

case

(

if(!s.isEmpty()){

if(s.getHead()=='('){

s.pop();

i++；

elsestate=O;

)

elsestate=O;

break;

}

default:{i++;break;}

if(s.isEmpty()&&state==1)

returntrue;

elsereturnfalse;

4.7習題

單項選擇題

1.空串與空格串是相同的，這種說法B。

A.正確B.不正確

2.串是一中特殊的線性表，其特殊性體現(xiàn)在一旦_。

A.可以順序存儲B.數(shù)據(jù)元素是一個字符

C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符

3.設有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱作g。

A.連接B.模式匹配C.求子串D.求串長

4.設串sl='ABCDEFGLs2=,PQRST,,函數(shù)con(x,y)返回x和y串的連接

串，subs(s,i,j)返回串s的從序號i的字符開始的j個字符組成的子串，len(s)

返回串s的長度，則con(subs(sl,2,len(s2)),subs(sl,len(s2),2))的結果串是

D0

A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF

5.常對數(shù)組進行的兩種基本操作是C。

A.建立與刪除B.索引和修改C.查找和修改D.查找與索引

9

6.二維數(shù)組M的成員是6個字符(每個字符占一個存儲單元，即一個字節(jié))

組成的串，行下標i的范圍從0到8,列下標j的范圍從1到10,則存放M

至少需要D個字節(jié):M的第8列和第5行共占A個字節(jié)。

①A.90B.180C.240D.540

②A.108B.114C.54D.60

二.填空題(將正確的答案填在相應的空中)

1.串的兩種最基本的存儲方式是順序存儲和鏈式存儲。

2.兩個串相等的充分必要條件是長度相等且對應位置字符相等。

3.空串是。個字符的串，其長度等于空格串是由一個或多個空格字符

組成的串，其長度等于空格字符個數(shù)。

4.設sTHAMoAoTEACHER'淇長度是14。(□表示空格)

三.算法設計題：

1.編寫算法，實現(xiàn)remove(stringt)操作，即從當前串中刪除所有和串t相同的

子串。

publicintremove(stringt){

〃在當前串中刪除所有與串t相等的子串，并返回刪除的次數(shù)

inttime=0,m;

for(intj=O;j<this.length-t.length+l;j++){

if(this.chars[j]==t.chars[O]){

intx=0;

for(inti=O;i<t.length;i++){

if(this.chars[j+i]==t.chars[i]){

x++;

}

else

break;

)

if(x==t.length){

m=j；

for(inti=j+t.length;i<this.length;i++){

this.chars[m]=this.chars[i];

m++;

}

time++;

this.length-=t.getLength();

returntime;

)

2.編寫算法，實現(xiàn)replace(stringt,stringv)操作，即從當前串中用串v替換所

有與串t相等的子串，并返回替換的次數(shù)串的。

publicintreplace(stringt,stringv){

〃在當前串中用串v替換所有與串t相等的子串，并返回替換的次數(shù)

intpoor=v.getLength()-t.getLength();

10

intl=O,num=O,m=O,n=O,size=maxSize;

if(maxSize<maxSize+num*poor)

size=maxSize+num*poor;

stringtl=newstring(size);

intcycle=O;

for(inti=O;i<this.length-t.length+1;i++){

if(this.chars[i]==t.chars[0]){

intx=0;

for(intj=0;j<t.length;j++){

if(this.chars[j+i]==t.chars[j])

x++；

else

break;

)

if(x=t.length){

num++;

n=i;

for(l=m;l<n;l++)

tl.chars[tl.length++]=this.chars[l];

for(intj=0;j<v.length;j++)

11.chars[t1.length++]=v.chars[j];

m=i+t.length;

i+=t.length-1;

this.chars=tl.chars;

this.length=tl.length;

returnnum;

}

3.設A=((a,b),(c,d)),求下列操作結果:

Tail(Head(A))=?(b)

Tail(Head(Tail(A)))=?(d)

5.7習題

一.單項選擇題

1.在一棵度為3的樹中，度為3的結點數(shù)為2個，度為2的結點數(shù)為1個，度為1的結點

數(shù)為2個，則度為0的結點數(shù)為（C）個。

A.4B.5C.6D.7

2.假設在一棵二叉樹中，雙分支結點數(shù)為15,單分支結點數(shù)為30個，則葉子結點數(shù)為

（B）個。

A.15B.16C.17D.47

3.假定一棵三叉樹的結點數(shù)為50,則它的最小高度為（C）。

A.3B.4C.5D.6

4.在一棵二叉樹上第4層的結點數(shù)最多為（D）。

A.2B.4C.6D.8

11

5.用順序存儲的方法將完全二叉樹中的所有結點逐層存放在數(shù)組中R[l..n],結點R[i]若

有左孩子，其左孩子的編號為結點（B）。

A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]

6.由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為

（D）?

A.24B.48C.72D.53

7.線索二叉樹是一種（A）結構。

A.邏輯B.邏輯和存儲C.物理D.線性

8.線索二叉樹中，結點p沒有左子樹的充要條件是（B）。

A.p.lChild=nullB.p.ltag=l

C.p.ltag=l且p.IChild=nullD.以上都不對

9.設n,m為一棵二叉樹上的兩個結點，在中序遍歷序列中n在m前的條件是（B）。

A.n在m右方B.n在m左方

C.n是m的祖先D.n是m的子孫

10.如果F是由有序樹T轉換而來的二叉樹，那么T中結點的前序就是F中結點的

（B）?

A.中序B.前序C.后序D.層次序

11.欲實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹采用

（A）存儲結構。

A.三叉鏈表B.廣義表C.二叉鏈表D.順序

12.下面敘述正確的是（D）。

A.二叉樹是特殊的樹B.二叉樹等價于度為2的樹

C.完全二叉樹必為滿二叉樹D.二叉樹的左右子樹有次序之分

13.任何一棵二叉樹的葉子結點在先序、中序和后序遍歷序列中的相對次序（A）。

A.不發(fā)生改變B.發(fā)生改變

C.不能確定D.以上都不對

14.已知一棵完全二叉樹的結點總數(shù)為9個,則最后一層的結點數(shù)為（B）。

A.1B.2C.3D.4

15.根據(jù)先序序列ABDC和中序序列DBAC確定對應的二叉樹，該二叉樹（A）?

A.是完全二叉樹B.不是完全二叉樹

C.是滿二叉樹D.不是滿二叉樹

二.判斷題

（X）1.二叉樹中每個結點的度不能超過2,所以二叉樹是一種特殊的樹。

（V）2.二叉樹的前序遍歷中，任意結點均處在其子女結點之前。

（V）3.線索二叉樹是一種邏輯結構。

（J）4.哈夫曼樹的總結點個數(shù)（多于1時）不能為偶數(shù)。

（X）5.由二叉樹的先序序列和后序序列可以唯一確定一顆二叉樹。

（X）6.樹的后序遍歷與其對應的二叉樹的后序遍歷序列相同。）

（X）7.根據(jù)任意一種遍歷序列即可唯一確定對應的二叉樹。

（J）8.滿二叉樹也是完全二叉樹。

（X）9.哈夫曼樹一定是完全二叉樹。

（X）10.樹的子樹是無序的。

三.填空題

1.假定一棵樹的廣義表表示為A（B（E）,C（F（H,I,J）,G）,D）,則該樹的度為

3,樹的深度為/終端結點的個數(shù)為單分支結點的個數(shù)為」雙分支結點的

個數(shù)為1，三分支結點的個數(shù)為2,C結點的雙親結點為其孩子結點為

F和G結點。

2.設F是一個森林，B是由F轉換得到的二叉樹，F(xiàn)中有n個非終端結點，則B中右指針

域為空的結點有n+1個。

12

3.對于一個有n個結點的二叉樹，當它為一棵定全二叉樹時具有最小高度，即為

llogznl+1,當它為一棵單支樹具有最大高度,即為工。

4.由帶權為3,9,6,2,5的5個葉子結點構成一棵哈夫曼樹，則帶權路徑長度為國。

5.在一棵二叉排序樹上按中序遍歷得到的結點序列是一個有序序列。

6.對于一棵具有n個結點的二叉樹，當進行鏈接存儲時，其二叉鏈表中的指針域的總數(shù)

為2n個,其中n-1個用于鏈接孩子結點,n+1個空閑著。

7.在一棵二叉樹中，度為0的結點個數(shù)為nO,度為2的結點個數(shù)為n2,則n0=丁+1。

8.一棵深度為k的滿二叉樹的結點總數(shù)為立1，一棵深度為k的完全二叉樹的結點總數(shù)

的最小值為絲，最大值為四1。

9.由三個結點構成的二叉樹，共有工種不同的形態(tài)。

10.設高度為h的二叉樹中只有度為0和度為2的結點，則此類二叉樹中所包含的結點數(shù)

至少為2h-l?

11.一棵含有n個結點的k叉樹，單支樹形態(tài)達到最大深度，完全二叉樹形態(tài)達到最

小深度。

12.對于一棵具有n個結點的二叉樹，若一個結點的編號為i（l<iWn）,則它的左孩子結

點的編號為2i,右孩子結點的編號為2i+l,雙親結點的編號為|i/2|。

13.對于一棵具有n個結點的二叉樹，采用二叉鏈表存儲時，鏈表中指針域的總數(shù)為理

個，其中nT個用于鏈接孩子結點,n+1個空閑著。

14.哈夫曼樹是指帶權路徑長度最小的二叉樹。

15.