數(shù)據(jù)結(jié)構(gòu)從概念到Java實(shí)現(xiàn)賴小平課后參考答案

第一章概述1.6基礎(chǔ)知識(shí)檢測(cè)一、填空題1、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中的操作對(duì)象以及他們之間的（關(guān)系）和（運(yùn)算）的學(xué)科。2、從邏輯關(guān)系看，可以把數(shù)據(jù)結(jié)構(gòu)分為（線性結(jié)構(gòu)）和（非線性結(jié)構(gòu)）兩大類。3、算法具有5個(gè)特性：（有窮性）、（確定性）、（可行性或有效性）、（有零個(gè)或多個(gè)輸入）、（有一個(gè)或多個(gè)輸出）。4、數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)性能指標(biāo)是：（時(shí)間復(fù)雜度）和（空間復(fù)雜度）。二、選擇題5、下列數(shù)據(jù)結(jié)構(gòu)，（D）不屬于線性結(jié)構(gòu)。A．線性表與串B．棧和隊(duì)列C．?dāng)?shù)組D．集合6、鏈?zhǔn)酱鎯?chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（C）。A．一定連續(xù)B．一定不連續(xù)C．不一定連續(xù)D．部分連續(xù)，部分不連續(xù)7、下列（D）結(jié)構(gòu)中的數(shù)據(jù)元素的關(guān)系是“多對(duì)多”的關(guān)系。A．線性表B．二叉樹(shù)C．棧和隊(duì)列D．圖1.7.1實(shí)驗(yàn)1：熟悉編程環(huán)境【實(shí)驗(yàn)要求】已知求數(shù)組最小元素的值及下標(biāo)的算法如下，編寫主函數(shù)進(jìn)行測(cè)試，要求輸入任意數(shù)組，給出運(yùn)行結(jié)果。【Java源代碼】publicstaticvoidmax(double[]arr){ doublem=arr[0];//初始化最小值 intloc=0;//初始化數(shù)組下標(biāo)intlen=arr.length; for(inti=0;i<len;i++){ if(arr[i]<m){ m=arr[i]; loc=i; } } System.out.printf("數(shù)組中最小的元素值為：%f\n其在數(shù)組中的下標(biāo)是：%d",m,loc);}【C++源代碼】voidmax(doublearr[],intlen){ doublem=arr[0];//初始化最小值 intloc=0;//初始化數(shù)組下標(biāo) for(inti=0;i<len;i++){ if(arr[i]<m){ m=arr[i]; loc=i; } } cout<<"數(shù)組中最小的元素值為："<<m<<",其在數(shù)組中的下標(biāo)是："<<loc<<endl;}【運(yùn)行結(jié)果參考】運(yùn)行結(jié)果如下圖1-22所示。圖1-22運(yùn)行結(jié)果圖【Java源代碼】publicstaticvoidmain(String[]args){ Scannersc=newScanner(System.in); System.out.print("請(qǐng)輸入數(shù)組元素個(gè)數(shù)："); intlen=sc.nextInt(); doublearr[]=newdouble[len];//創(chuàng)建數(shù)組 System.out.print("請(qǐng)輸入數(shù)組元素："); for(inti=0;i<len;i++) arr[i]=sc.nextDouble();//輸入數(shù)組元素 max(arr);//方法調(diào)用 sc.close();}【C++源代碼】#include<iostream>usingnamespacestd;voidmax(doublearr[],intlen){ doublem=arr[0];//初始化最小值 intloc=0;//初始化數(shù)組下標(biāo) for(inti=0;i<len;i++){ if(arr[i]<m){ m=arr[i]; loc=i; } } cout<<"數(shù)組中最小的元素值為："<<m<<",其在數(shù)組中的下標(biāo)是："<<loc<<endl;}voidmain(){ intn;doublech; cout<<"請(qǐng)輸入數(shù)組元素的個(gè)數(shù)："; cin>>n; cout<<"請(qǐng)輸入數(shù)組元素："; for(inti=0;i<n;i++) { cin>>ch; arr.push_back(ch);//輸入數(shù)組元素 }double*arr=newdouble[n]; max(arr,n);//方法調(diào)用;}【運(yùn)行結(jié)果參考】運(yùn)行結(jié)果如下圖1-23所示。圖1-23實(shí)驗(yàn)1運(yùn)行結(jié)果圖1.7.2實(shí)驗(yàn)2：簡(jiǎn)單算法設(shè)計(jì)與分析【實(shí)驗(yàn)要求】設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n)的算法，實(shí)現(xiàn)將數(shù)組arr[n]中所有元素循環(huán)左移k個(gè)位置?！具\(yùn)行結(jié)果參考】運(yùn)行結(jié)果如下圖1-24所示。圖1-24運(yùn)行結(jié)果圖【Java源代碼】packagecom.gdlg.sy1_1;importjava.util.Scanner;publicclassShiYan1_2{ publicstaticvoidConverse(int[]array,intk){ reverse(array,0,k-1);//倒置前k個(gè)元素 reverse(array,k,array.length-1);//倒置后length-k個(gè)元素 reverse(array,0,array.length-1);//倒置所有元素 } privatestaticvoidreverse(int[]array,intbegin,intend){ intlength=end-begin+1; inthalf=length/2; for(inti=0;i<half;i++){ inttemp=array[begin];array[begin]=array[end];array[end]=temp;begin++;end--; } } publicstaticvoidmain(String[]args){ intn,m;ShiYan1_2conv;System.out.println("請(qǐng)輸入數(shù)組元素個(gè)數(shù)：");Scannersc=newScanner(System.in);n=sc.nextInt();int[]arr=newint[n];System.out.println("請(qǐng)輸入"+n+"個(gè)數(shù)組元素：");for(inti=0;i<n;i++)arr[i]=sc.nextInt();System.out.println("請(qǐng)輸入數(shù)組左移位置數(shù)：");m=sc.nextInt();Converse(arr,m);System.out.println("數(shù)組循環(huán)左移"+m+"個(gè)位置后，數(shù)組元素為：");for(intj=0;j<n;j++)System.out.print(arr[j]+""); sc.close();}}【C++源代碼】#include"stdio.h"#include"iostream.h"voidReverse(intarr[],intfrom,intto){//將數(shù)組arr中元素從from到to逆置inttemp;for(inti=0;i<(to-from+1)/2;i++){//填空temp=arr[from+i];//填空，交換元素arr[from+i]=arr[to-i];arr[to-i]=temp;}}voidConverse(intarr[],intn,intk){Reverse(arr,0,k-1);//調(diào)用函數(shù)Reverse(arr,k,n-1);Reverse(arr,0,n-1);}intmain(){intn,m;cout<<"請(qǐng)輸入數(shù)組元素個(gè)數(shù)：";cin>>n;int*arr=newint[n];//填空，創(chuàng)建數(shù)組cout<<"請(qǐng)輸入"<<n<<"個(gè)數(shù)組元素："<<endl;for(inti=0;i<n;i++)cin>>arr[i];//填空，輸入數(shù)組元素cout<<"請(qǐng)輸入數(shù)組左移位置數(shù)：";cin>>m;Converse(arr,n,m);//填空，調(diào)用左移函數(shù)cout<<"數(shù)組循環(huán)左移"<<m<<"個(gè)位置后，數(shù)組元素為："<<endl;for(intj=0;j<n;j++)cout<<arr[j]<<"";return0;}【運(yùn)行結(jié)果】圖1-25運(yùn)行結(jié)果圖1.7.3實(shí)驗(yàn)拓展1．設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n)的算法，實(shí)現(xiàn)將數(shù)組b[n]中所有元素調(diào)整為左右兩部分，左邊為奇數(shù)，右邊為偶數(shù)。2．編寫主函數(shù)進(jìn)行測(cè)試。3．給出運(yùn)行結(jié)果。【Java源代碼】importjava.util.Scanner;publicclassAdjustTest{ publicstaticvoidAdjust(inta[],intn){ inti=0,j=n-1,temp; while(i<j){ while(a[i]%2!=0)i++; while(a[j]%2==0)j--; if(i<j){ temp=a[i]; a[i]=a[j]; a[j]=temp; } } } publicstaticvoidmain(String[]args){ intn,m; System.out.println("請(qǐng)輸入數(shù)組元素個(gè)數(shù)："); Scannersc=newScanner(System.in);n=sc.nextInt(); int[]arr=newint[n]; System.out.println("請(qǐng)輸入"+n+"個(gè)數(shù)組元素："); for(inti=0;i<n;i++) arr[i]=sc.nextInt(); Adjust(arr,n); System.out.println("奇偶調(diào)整后，數(shù)組元素為："); for(intj=0;j<n;j++) System.out.println(arr[j]+"");}}【C++源代碼】#include"iostream.h"voidAdjust(inta[],intn){ inti=0,j=n-1,temp; while(i<j){ while(a[i]%2!=0)i++; while(a[j]%2==0)j--; if(i<j){ temp=a[i]; a[i]=a[j]; a[j]=temp; } }}voidmain(){ intn,m;cout<<"請(qǐng)輸入數(shù)組元素個(gè)數(shù)：";cin>>n;int*arr=newint[n];cout<<"請(qǐng)輸入"<<n<<"個(gè)數(shù)組元素："<<endl;for(inti=0;i<n;i++)cin>>arr[i];Adjust(arr,n);cout<<"奇偶調(diào)整后，數(shù)組元素為："<<endl;for(intj=0;j<n;j++)cout<<arr[j]<<"";}【運(yùn)行結(jié)果】圖1-26運(yùn)行結(jié)果圖第二章線性表結(jié)構(gòu)2.8基礎(chǔ)知識(shí)檢測(cè)一、填空題1、線性表L=（a1,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是（（n-1）/2）。2、在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)（n+1-i）個(gè)元素。3、線性表（a1,a2,…,an）以鏈?zhǔn)酱鎯?chǔ)時(shí)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜性為（O（n））。4、線性表是具有n個(gè)（?數(shù)據(jù)元素??）的有限序列（n>0）。二、選擇題5、以下關(guān)于線性表的敘述，正確的是（C）Ⅰ）線性表中每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼；Ⅱ）線性表中的所有元素必須按從小到大或從大到小的順序排列；Ⅲ）線性表是由有限個(gè)相同類型的數(shù)據(jù)元素構(gòu)成的序列；Ⅳ）線性表基本操作的實(shí)現(xiàn)取決于采用哪一種存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)不同實(shí)現(xiàn)的算法也不同。A．Ⅰ、Ⅱ、ⅢB．Ⅱ、Ⅲ、ⅣC．Ⅲ、ⅣD．Ⅲ6、線性表是一個(gè)（C）位置對(duì)數(shù)據(jù)元素進(jìn)行插入、刪除操作的序列容器。A．僅可在表頭B．僅可在表尾C．可在任意D．都是7、一個(gè)線性表最常用的操作是存取任意指定序號(hào)的數(shù)據(jù)元素和在最后進(jìn)行插入、刪除操作，則用（A）存儲(chǔ)方式可以節(jié)省時(shí)間。A．順序表B．雙向鏈表C．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D．單循環(huán)鏈表8、線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址(?D?)?。??A．必須是連續(xù)的B．部分地址必須是連續(xù)的C．一定是不連續(xù)的?D．連續(xù)與否均可以9、用鏈表表示線性表的優(yōu)點(diǎn)是?（C?）。??A．便于隨機(jī)存取??B．花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少??C．便于插入和刪除??D．?dāng)?shù)據(jù)元素的物理順序與邏輯順序相同?2.9.1實(shí)驗(yàn)1：順序表的基本操作【實(shí)驗(yàn)要求】設(shè)計(jì)并將如下順序表操作的部分補(bǔ)充完整，并將運(yùn)行結(jié)果截圖，在主函數(shù)中提示用戶選擇順序表操作，例如圖2-11：圖2-11菜單選擇【運(yùn)行結(jié)果參考】運(yùn)行結(jié)果如下圖2-12、圖2-13、圖2-14、圖2-15所示。圖2-12運(yùn)行結(jié)果圖圖2-13插入位置不合理圖2-14表滿圖2-15刪除位置不合理【Java源代碼】1．定義順序表接口IList2．定義順序表類SqList3．定義測(cè)試類（包括顯示菜單方法和main方法）：publicstaticvoidmain(String[]args)throwsException{ //第一步：初始化順序表，表長(zhǎng)為5 SqListL=newSqList(8);//構(gòu)造一個(gè)8個(gè)存儲(chǔ)空間的順序表 Scannersc=newScanner(System.in); intitem; for(inti=0;i<5;i++){ System.out.print("順序表第"+i+"個(gè)元素是："); item=sc.nextInt(); L.insert(i,item);//輸入的5個(gè)值依次插入表中 } System.out.println("順序表初始化完成！"); //第二步：顯示操作菜單 menu(); //第三步：循環(huán)選擇操作菜單，直到輸入操作代碼為0結(jié)束程序 intop; do{ System.out.print("請(qǐng)輸入操作代碼（0-退出）:"); op=sc.nextInt(); switch(op){ case1: System.out.println("順序表的長(zhǎng)度:"+L.length()); break; case2: System.out.println("請(qǐng)輸入要插入的位置:"); //位置是從0開(kāi)始的 intloc=sc.nextInt(); System.out.println("請(qǐng)輸入要插入該位置的值:"); intnum=sc.nextInt(); L.insert(loc,num); System.out.println("插入操作成功！"); break; case3: System.out.print("請(qǐng)輸入要?jiǎng)h除元素的位置:"); loc=sc.nextInt(); L.remove(loc); System.out.println("刪除操作成功"); break; case4: System.out.print("請(qǐng)輸入要查找的元素:"); num=sc.nextInt(); System.out.println(num+"在表中的位置："+(L.indexOf(num))); break; case5: System.out.print("請(qǐng)輸入要查找元素的位置:"); loc=sc.nextInt(); System.out.println(loc+"位置上的元素為："+L.get(loc)); break; case6: L.display(); break; case0: System.out.print("程序結(jié)束！"); return; default: System.out.print("輸入操作代碼有誤，請(qǐng)重新選擇！"); } }while(op!=0); sc.close(); } //顯示操作菜單方法 publicstaticvoidmenu(){ System.out.println("-----------------------------"); System.out.println("操作選項(xiàng)菜單"); System.out.println("1.輸出表長(zhǎng)"); System.out.println("2.插入元素"); System.out.println("3.刪除元素"); System.out.println("4.定位元素"); System.out.println("5.取表元素"); System.out.println("6.顯示線性表"); System.out.println("0.退出"); System.out.println("-----------------------------"); System.out.println("作者：XXX班級(jí)：17軟件工程X班"); }}【C++源代碼】voidmain(){SeqList1s1(100,5);s1.input();cout<<"線性表初始化完成！"<<endl;;//顯示菜單cout<<"======================"<<endl;cout<<"1:添加元素"<<endl;cout<<"2:插入元素"<<endl;cout<<"3:刪除元素"<<endl;cout<<"4:查找元素"<<endl;cout<<"5:取表元素"<<endl;cout<<"6:顯示線性表"<<endl;cout<<"其他:退出"<<endl;cout<<"======================"<<endl;cout<<"作者：XXXX班級(jí)：YYYY"<<endl;cout<<endl;inti=1,op,x,index,res;while(i==1){cout<<"請(qǐng)選擇操作代碼：";cin>>op;switch(op){ case1:cout<<"請(qǐng)輸入要添加的元素："; cin>>x; res=s1.add(x); if(res==0)cout<<"添加成功！"<<endl; elsecout<<"添加失?。?<<endl; break; case2:cout<<"請(qǐng)輸入要插入的位置和元素（用空格分隔）："; cin>>index; cin>>x; res=s1.insert(x,index); if(res==0)cout<<"插入成功！"<<endl; elsecout<<"插入失敗！"<<endl; break;case3:cout<<"請(qǐng)輸入要?jiǎng)h除元素的位置："; cin>>index; res=s1.remove(index); if(res==0)cout<<"刪除成功！"<<endl; elsecout<<"刪除失??！"<<endl; break; case4:cout<<"請(qǐng)輸入要查找的元素："; cin>>x; res=s1.search(x); if(res!=-1)cout<<"元素"<<x<<"為線性表中第"<<res+1<<"個(gè)元素"<<endl; elsecout<<"查找失?。?<<endl; break;case5:cout<<"請(qǐng)輸入要取元素的位置："; cin>>index; res=s1.get(index); if(res!=-1)cout<<"線性表中第"<<index+1<<"個(gè)元素為："<<res<<endl; elsecout<<"獲取元素失??！"<<endl; break; case6: s1.output(); cout<<"線性表長(zhǎng)度："<<s1.length()<<endl; break; default:i=0; }}}2.9.2實(shí)驗(yàn)2：鏈表的基本操作【實(shí)驗(yàn)要求】定義一鏈表類型，并定義帶有頭結(jié)點(diǎn)的單鏈表。補(bǔ)充代碼段，并將運(yùn)行結(jié)果截圖，要求如實(shí)驗(yàn)1?！具\(yùn)行結(jié)果參考】運(yùn)行結(jié)果如實(shí)驗(yàn)1所示。圖2-16運(yùn)行結(jié)果【Java源代碼】1．定義線性表接口IList2．定義單鏈表結(jié)點(diǎn)類Node3．定義單鏈表類LinkListpublicclassShiYan2_2{ publicstaticvoidmain(String[]args)throwsException{ //第一步：初始化順序表，表長(zhǎng)為5，用頭插法構(gòu)造一個(gè)8個(gè)存儲(chǔ)空間的鏈表 LinkListL=newLinkList(4,true); Scannersc=newScanner(System.in); //第二步：顯示操作菜單 menu(); //第三步：循環(huán)選擇操作菜單，直到輸入操作代碼為0結(jié)束程序 intop; do{ System.out.print("請(qǐng)輸入操作代碼（0-退出）:"); op=sc.nextInt(); switch(op){ case1: System.out.println("順序表的長(zhǎng)度:"+L.length()); break; case2: System.out.println("請(qǐng)輸入要插入的位置:");//位置從0開(kāi)始 intloc=sc.nextInt(); System.out.println("請(qǐng)輸入要插入該位置的值:"); Objectnum=sc.next(); L.insert(loc,num); System.out.println("插入操作成功！"); break; case3: System.out.print("請(qǐng)輸入要?jiǎng)h除元素的位置:"); loc=sc.nextInt(); L.remove(loc); System.out.println("刪除操作成功"); break; case4: System.out.print("請(qǐng)輸入要查找的元素:"); num=sc.next(); System.out.println(num+"在表中的位置："+(L.indexOf(num))); break; case5: System.out.print("請(qǐng)輸入要查找元素的位置:"); loc=sc.nextInt(); System.out.println(loc+"位置上的元素為："+L.get(loc)); break; case6: L.display(); break; case0: System.out.print("程序結(jié)束！"); return; default: System.out.print("輸入操作代碼有誤，請(qǐng)重新選擇！"); } }while(op!=0); sc.close(); } publicstaticvoidmenu(){//顯示操作菜單方法 System.out.println("-----------------------------"); System.out.println("操作選項(xiàng)菜單"); System.out.println("1.輸出表長(zhǎng)"); System.out.println("2.插入元素"); System.out.println("3.刪除元素"); System.out.println("4.定位元素"); System.out.println("5.取表元素"); System.out.println("6.顯示線性表"); System.out.println("0.退出"); System.out.println("-----------------------------"); System.out.println("作者：XXX班級(jí)：17軟件工程X班"); }}【C++源代碼】voidmain(){LinkLists1;s1.input();cout<<"鏈表初始化完成！"<<endl;;//顯示菜單cout<<"======================"<<endl;cout<<"1:添加元素"<<endl;cout<<"2:插入元素"<<endl;cout<<"3:刪除元素"<<endl;cout<<"4:查找元素"<<endl;cout<<"5:顯示線性表"<<endl;cout<<"其他:退出"<<endl;cout<<"======================"<<endl;inti=1,op,x,index;while(i==1){cout<<"請(qǐng)選擇操作代碼：";cin>>op;switch(op){ case1:cout<<"請(qǐng)輸入要添加的元素："; cin>>x; s1.add(x); break; case2:cout<<"請(qǐng)輸入要插入的位置和元素（用空格分隔）："; cin>>index; cin>>x; s1.insert(index,x); break;case3:s1.remove(); break; case4:cout<<"請(qǐng)輸入要查找的元素："; cin>>x; s1.search(x); break;case5:s1.output(); cout<<"鏈表長(zhǎng)度："<<s1.getLen()<<endl; break; default:i=0; }}}2.9.3實(shí)驗(yàn)3：棧的基本操作【實(shí)驗(yàn)要求】順序棧功能測(cè)試?！具\(yùn)行結(jié)果參考】運(yùn)行結(jié)果如下圖2-17、2-18所示。圖2-17運(yùn)行結(jié)果圖圖2-18運(yùn)行異?！綣ava源代碼】1．定義棧接口IStack2．定義順序棧類SqStack3．定義測(cè)試類（包括顯示菜單方法和main方法）publicclassTestSqStack{ publicstaticvoidmenu(){ System.out.println("----------順序棧基本操作-----------"); System.out.println("1.長(zhǎng)度"); System.out.println("2.入棧"); System.out.println("3.出棧"); System.out.println("4.打印棧"); System.out.println("0.退出"); System.out.println("-----------------------------"); System.out.println("作者：XXX班級(jí)：17軟件工程X班"); } publicstaticvoidmain(String[]args)throwsException{ //TODOAuto-generatedmethodstubSqStackss=newSqStack(10);//創(chuàng)建一個(gè)容量為10的棧Scannersc=newScanner(System.in);menu();intop;do{ System.out.print("請(qǐng)輸入操作代碼（0-退出）:"); op=sc.nextInt(); switch(op){ case1: System.out.println("順序棧的長(zhǎng)度:"+ss.length()); break; case2: System.out.println("請(qǐng)輸入一組數(shù)執(zhí)行入棧操作（輸入0結(jié)束）:"); while(true){ Objectnum=sc.next(); if(num.equals("0"))break; elsess.push(num); } System.out.println("入棧操作成功！"); break; case3: Objectp=ss.pop(); System.out.println(p.toString()+"出棧成功！"); break; case4: ss.display(); break; case0: System.out.print("程序結(jié)束！"); return; default: System.out.print("輸入操作代碼有誤，請(qǐng)重新選擇！"); } }while(op!=0); sc.close(); }}【C++源代碼】publicstaticvoidmain(String[]args){ int[]data={23,45,3,7,6,945}; IStack<Integer>stack=newLinkStack<Integer>(); //入棧操作 System.out.println("*******入棧操作*******"); for(inti=0;i<data.length;i++){ stack.push(data[i]); System.out.println(data[i]+"入棧"); }intsize=stack.size();//出棧操作System.out.println("*******出棧操作*******");for(inti=0;i<size;i++){System.out.println(stack.pop()+"出棧");} }}2.9.4實(shí)驗(yàn)4：哈希表的應(yīng)用【實(shí)驗(yàn)要求】1．根據(jù)哈希函數(shù)和解決沖突的方法設(shè)計(jì)哈希表。2．哈希表的查找，求查找平均長(zhǎng)度?！緦?shí)驗(yàn)內(nèi)容】2．設(shè)有一個(gè)用線性探測(cè)法解決沖突得到的散列表，空間分配如下圖所示，散列函數(shù)為H(k)=k%11，請(qǐng)將關(guān)鍵字為13、25、80、16、17、6、14依次映射到相應(yīng)的存儲(chǔ)單元中。012345678910 13258016176143．

設(shè)哈希表長(zhǎng)m=14，哈希函數(shù)為H(k)=kMOD11。如果用二次探測(cè)再散列處理沖突，請(qǐng)將關(guān)鍵字為15、38、49、61、84的記錄填寫在相應(yīng)的存儲(chǔ)單元中。01234567891011121315386184494．設(shè)哈希（Hash）表的地址范圍為0～17，哈希函數(shù)為：H（K）＝KMOD16。K為關(guān)鍵字，用線性探測(cè)法再散列法處理沖突，輸入關(guān)鍵字序列：（10，24，32，17，31，30，46，47，40，63，49），造出Hash表，試回答下列問(wèn)題：畫出哈希表的示意圖；若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比較？查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容比較，即63vs31,no;然后順移，與46,47,32,17,63相比，一共比較了6次！若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？查找60,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但因?yàn)?2號(hào)單元為空（應(yīng)當(dāng)有空標(biāo)記），未找到，所以應(yīng)當(dāng)只比較這一次即可。（4）假定每個(gè)關(guān)鍵字的查找概率相等，分別求查找成功時(shí)和查找不成功時(shí)的平均查找長(zhǎng)度。對(duì)于查找元素32、17、24、10、30、31，各比較1次，共6次；對(duì)其它元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，ASL=（6*2＋2＋3×3）/11＝23/11≈2.09ASLu=（5+4+3+2+1*4+4+3+2+1*3+9+8）/16=47/162.9.5實(shí)驗(yàn)拓展1．在線性表類添加兩個(gè)函數(shù)：（1）實(shí)現(xiàn)對(duì)順序表或單鏈表就地逆置；（2）統(tǒng)計(jì)某一元素在表中出現(xiàn)的次數(shù)?！綣ava源代碼】【C++代碼】voidLinkList::inverse(){// 鏈表的逆置 NodeType*p,*q; p=Head->next;//讓p指向第一個(gè)元素 Head->next=NULL;//讓Head的指針域?yàn)榭? while(p!=NULL){ 。。。 }}2．設(shè)計(jì)算法，把十進(jìn)制數(shù)轉(zhuǎn)換為二至九進(jìn)制之間的任一進(jìn)制輸出，采用順序棧實(shí)現(xiàn)?！綣ava源代碼】importjava.util.*;publicclassDeci{publicstaticvoidDecimalTor(intnum,intr){ inttop=-1; intk,n=num;int[]data=newint[n]; while(num!=0){ k=num%r; data[++top]=k; num=num/r; } System.out.println("十進(jìn)制數(shù)"+n+"轉(zhuǎn)換為"+r+"進(jìn)制數(shù)結(jié)果："); while(top!=-1)System.out.print(data[top--]); }publicstaticvoidmain(String[]args){ Scannersc=newScanner(System.in); intnum,r; System.out.println("請(qǐng)輸入十進(jìn)制數(shù)：");num=sc.nextInt();System.out.println("要轉(zhuǎn)換的進(jìn)制數(shù)：");r=sc.nextInt();DecimalTor(num,r);}}【C++源代碼】voidCstack::DecimalTor(intnum,intr){ top=-1; intk,n=num; while(num!=0){ k=num%r; data[++top]=k; num=num/r; } cout<<"十進(jìn)制數(shù)"<<n<<"轉(zhuǎn)換為"<<r<<"進(jìn)制數(shù)結(jié)果："; while(top!=-1)cout<<data[top--]; cout<<endl;}voidmain(){Cstackcs; intnum,r; cout<<"請(qǐng)輸入十進(jìn)制數(shù)：";cin>>num;cout<<"要轉(zhuǎn)換的進(jìn)制數(shù)：";cin>>r;cs.DecimalTor(num,r);}第三章樹(shù)結(jié)構(gòu)3.8基礎(chǔ)知識(shí)檢測(cè)一.選擇題以下表述正確的是B。A．二叉樹(shù)的度為2B．二叉樹(shù)中結(jié)點(diǎn)的度可以小于2

C．二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2D．二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)（即子結(jié)點(diǎn)）個(gè)數(shù)是C。A.不確定B.9C.11D.15如果根的層次為1，具有61個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為_(kāi)_B____。A.5B.6C.7D.8對(duì)下圖所示的二叉樹(shù)進(jìn)行中序遍歷（左子樹(shù)、根、右子樹(shù)）的結(jié)果是D。A.253461 B.253416 C.265413 D.264531若某二叉樹(shù)的先序遍歷序列和中序遍歷序列分別為PBECD、BEPCD，則該二叉樹(shù)的后序遍歷序列為D。

A.PBCDEB.DECBPC.EBPDCD.EBDCP若二叉樹(shù)的先序遍歷序列與中序序列相同且樹(shù)中結(jié)點(diǎn)數(shù)大于1，則該二叉樹(shù)的D。A.只有根結(jié)點(diǎn)無(wú)左子樹(shù)B.只有根結(jié)點(diǎn)無(wú)右子樹(shù)C.非葉子結(jié)點(diǎn)只有左子樹(shù)D.非葉子結(jié)點(diǎn)只有右子樹(shù)對(duì)一棵非空的二叉排序樹(shù)進(jìn)行B遍歷，可得到一個(gè)結(jié)點(diǎn)元素的遞增序列。

A．先序B．中序C．后序D．層次由關(guān)鍵字序列（12，7，36，25，18，2）構(gòu)造一棵二叉排序樹(shù)，該二叉排序樹(shù)的高度（層數(shù)）為C。A.6B.5C.4D.3在哈夫曼編碼中，若編碼長(zhǎng)度小于等于4，已對(duì)兩個(gè)字符編碼1和01，還可以最多對(duì)__C___個(gè)字符編碼。A.2B.3C.4D.5二.填空題已知（L,N），（G,K），（G,L），（G,M），（B,E），（B,F），（D,G），（D,H），（D,I），（D,J），（A,B），（A,C），（A,D）是表示一棵樹(shù)中具有父子關(guān)系的邊（1）樹(shù)形表示圖；（2）樹(shù)的根節(jié)點(diǎn)A；（3）樹(shù)的葉子點(diǎn)L，M，H，I，J，E，F(xiàn)，K；（4）樹(shù)的高度5；（5）節(jié)點(diǎn)D的度數(shù)4；（6）節(jié)點(diǎn)B的層數(shù)1；（7）節(jié)點(diǎn)G的兄弟H，I，J，祖先A，B，D，子孫L，M。數(shù)組T存儲(chǔ)著一棵二叉樹(shù)，根指針Root=4，-1為空鏈域。（1）畫出該樹(shù)的樹(shù)形圖，（2）這是一棵完全二叉樹(shù)嗎？Root=4數(shù)組T下標(biāo)LsonDataRson05B11-1E-12-1F-13-1C240A35-1D-1樹(shù)形圖為：是否為完全二叉樹(shù)？否假設(shè)一棵二叉樹(shù)的中序序列為DCBGEAHFIJK和后序序列為DCEGBFHKJIA。請(qǐng)畫出該樹(shù)。3.9上機(jī)實(shí)驗(yàn)【實(shí)驗(yàn)?zāi)康摹苛私鈽?shù)和二叉樹(shù)的基本概念、二叉樹(shù)的基本性質(zhì)；掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和處理方法；掌握二叉樹(shù)遍歷算法、建立算法的實(shí)現(xiàn)；理解二叉排序樹(shù)的特點(diǎn)；掌握二叉排序樹(shù)查找、插入、刪除結(jié)點(diǎn)的算法；了解哈夫曼樹(shù)的基本概念；掌握哈夫曼樹(shù)的構(gòu)造和哈夫曼編碼、譯碼的方法。3.9.1實(shí)驗(yàn)1：二叉樹(shù)的建立與遍歷【實(shí)驗(yàn)要求】1．采用二叉鏈表作為存貯結(jié)構(gòu)，完成二叉樹(shù)的基本操作。包括：可采用兩種方式構(gòu)造二叉樹(shù)：給出二叉樹(shù)擴(kuò)充的先序序列構(gòu)造和編寫方法自動(dòng)構(gòu)造。輸出三種遍歷序列。輸出二叉樹(shù)的高度、葉子結(jié)點(diǎn)數(shù)和結(jié)點(diǎn)數(shù)。2．輸入數(shù)據(jù)：樹(shù)中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)類型設(shè)定為整數(shù)型?！具\(yùn)行結(jié)果參考】運(yùn)行結(jié)果參考如下圖3-34所示。圖3-34二叉樹(shù)的基本操作【Java源代碼】測(cè)試類：publicclassDebugBiTree{ publicBiTreecreateBiTree(){//構(gòu)造二叉樹(shù) BiTreeNoded=newBiTreeNode('D'); BiTreeNodeg=newBiTreeNode('G'); BiTreeNodeh=newBiTreeNode('H'); BiTreeNodee=newBiTreeNode('E',g,null); BiTreeNodeb=newBiTreeNode('B',d,e); BiTreeNodef=newBiTreeNode('F',null,h); BiTreeNodec=newBiTreeNode('C',f,null); BiTreeNodea=newBiTreeNode('A',b,c); returnnewBiTree(a); //創(chuàng)建根結(jié)點(diǎn)為a的二叉樹(shù) } publicstaticvoidmain(String[]args){ DebugBiTreedebugBiTree=newDebugBiTree(); BiTreebiTree=debugBiTree.createBiTree(); BiTreeNoderoot=biTree.getRoot();//取得樹(shù)的根結(jié)點(diǎn) System.out.println("該樹(shù)的樹(shù)形如下:"); biTree.printTree(root,1); //調(diào)試先根遍歷 System.out.print("(遞歸)先根遍歷序列為:"); biTree.preOrder(); System.out.println();//輸出換行 //調(diào)試中根遍歷 System.out.print("(遞歸)中根遍歷序列為:"); biTree.inOrder(); System.out.println(); //調(diào)試后根遍歷 System.out.print("(遞歸)后根遍歷序列為:"); biTree.postOrder(); System.out.println(); //調(diào)試層次遍歷 System.out.print("層次遍歷序列為:"); biTree.levelTraverse(); System.out.println(); intdepth=biTree.getDepth(root); System.out.println("深度為:"+depth); System.out.println("該樹(shù)的結(jié)點(diǎn)數(shù)目:"+biTree.countNode(root)); System.out.print("該樹(shù)的葉子結(jié)點(diǎn)數(shù)目:"+biTree.countLeafNode(root)); }}3.9.2實(shí)驗(yàn)2：二叉排序樹(shù)的查找算法實(shí)現(xiàn)【實(shí)驗(yàn)要求】1．定義二叉排序樹(shù)的數(shù)據(jù)結(jié)構(gòu)；2．實(shí)現(xiàn)二叉排序樹(shù)的插入、刪除算法與查找結(jié)點(diǎn)的算法，并建立二叉排序樹(shù)；【運(yùn)行結(jié)果參考】運(yùn)行結(jié)果參考如下圖3-35所示。圖3-35二叉排序樹(shù)的基本操作【Java源代碼】測(cè)試類：importjava.util.Scanner;publicclassDebugBSTree{ publicstaticvoidmenu(){ System.out.println("==========二叉排序樹(shù)=========="); System.out.println("1創(chuàng)建"); System.out.println("2查找元素"); System.out.println("3中序遍歷"); System.out.println("4插入元素"); System.out.println("5刪除元素"); System.out.println("0退出"); System.out.println("============================"); System.out.println("作者：XXX班級(jí)：軟件工程X班"); } publicstaticvoidmain(String[]args){ menu(); Scannersc=newScanner(System.in); intop; BSTreebsTree=null; do{ System.out.print("請(qǐng)輸入操作代碼（0-退出）:"); op=sc.nextInt(); switch(op){ case1: System.out.print("請(qǐng)輸入二叉樹(shù)元素值個(gè)數(shù)："); intn=sc.nextInt(); int[]arr=newint[n]; System.out.print("請(qǐng)輸入"+n+"個(gè)二叉樹(shù)元素值："); for(inti=0;i<n;i++) arr[i]=sc.nextInt(); bsTree=newBSTree(arr); System.out.println("二叉排序樹(shù)創(chuàng)建完成！"); break; case2: System.out.print("請(qǐng)輸入要查找的元素值:"); intdata=sc.nextInt(); if(bsTree!=null) bsTree.searchBST(data); else System.out.println("二叉排序樹(shù)未創(chuàng)建！"); break; case3: if(bsTree!=null){ System.out.println("中序遍歷序列為："); bsTree.inOrder(); }else System.out.println("二叉排序樹(shù)未創(chuàng)建！"); break; case4: System.out.print("請(qǐng)輸入插入的元素值："); data=sc.nextInt(); if(bsTree!=null){ if(bsTree.insertBST(data)) System.out.println("插入成功！"); else System.out.println("插入失敗，元素已存在！"); }else System.out.println("二叉排序樹(shù)未創(chuàng)建！"); break; case5: System.out.print("請(qǐng)輸入刪除的元素值："); data=sc.nextInt(); if(bsTree!=null){ if(bsTree.removeBST(data)!=null) System.out.println("刪除成功！"); elseSystem.out.println("刪除失敗，元素不存在?。?); }else System.out.println("二叉排序樹(shù)未創(chuàng)建！"); break; case0: System.out.println("程序結(jié)束！"); return; default: System.out.println("輸入操作代碼有誤，請(qǐng)重新選擇！"); } }while(op!=0); sc.close(); }}3.9.3實(shí)驗(yàn)3：哈夫曼樹(shù)的應(yīng)用【實(shí)驗(yàn)要求】在數(shù)據(jù)通信中，需要將傳送的文字轉(zhuǎn)換成二進(jìn)制的字符串，用0，1碼的不同排列來(lái)表示字符。例如，需傳送的報(bào)文為“AFTERDATAEARAREARTAREA”，這里用到的字符集為“A，E，R，T，F(xiàn)，D”，各字母出現(xiàn)的次數(shù)為{8，4，5，3，1，1}?，F(xiàn)要求為這些字母設(shè)計(jì)編碼。（1）請(qǐng)構(gòu)造出哈夫曼樹(shù)；（2）給出每個(gè)字符的編碼；（3）并給出報(bào)文編碼；（4）對(duì)以下編碼譯碼“010111011000110011”（1）哈夫曼樹(shù)（2）各字符編碼A：11E：00R：10T：011F：0100D：0101（3）“AFTERDATAEARAREARTAREA”報(bào)文編碼110100011001001011101111001110111000111001111100011（4）譯碼結(jié)果：DATETEA3.9.4實(shí)驗(yàn)拓展【實(shí)驗(yàn)要求】普通樹(shù)的基本操作：（1）定義樹(shù)的孩子兄弟鏈表存儲(chǔ)中結(jié)點(diǎn)類；（2）定義普通樹(shù)類，包含構(gòu)造方法、先根遍歷方法、后根遍歷方法、統(tǒng)計(jì)結(jié)點(diǎn)個(gè)數(shù)的方法；（3）定義測(cè)試類，包含創(chuàng)建如下圖3-36所示樹(shù)的方法。圖3-36一棵普通樹(shù)【運(yùn)行結(jié)果參考】運(yùn)行結(jié)果參考如下圖3-37所示。圖3-37普通樹(shù)基本操作【Java源代碼】測(cè)試類：publicclassDebugTree{ publicstaticTreecreateTree(){ TreeNodem=newTreeNode('M'); TreeNodel=newTreeNode('L',m,null); TreeNodek=newTreeNode('K'); TreeNodej=newTreeNode('J',null,k); TreeNodei=newTreeNode('I',j,l); TreeNodeh=newTreeNode('H',i,null); TreeNodeg=newTreeNode('G',null,h); TreeNodee=newTreeNode('E'); TreeNodef=newTreeNode('F'); TreeNoded=newTreeNode('D',null,f); TreeNodec=newTreeNode('C',d,e); TreeNodeb=newTreeNode('B',c,g); TreeNodea=newTreeNode('A',b,null); System.out.println("樹(shù)構(gòu)造完成！"); returnnewTree(a); //創(chuàng)建根結(jié)點(diǎn)為a的樹(shù) } publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstubTreetree=createTree();System.out.println("樹(shù)的結(jié)點(diǎn)數(shù)為："+tree.countNode());System.out.println("樹(shù)的先跟遍歷序列：");tree.preRootTraverse();System.out.println("樹(shù)的后跟遍歷序列：");tree.postRootTraverse(); }}數(shù)據(jù)結(jié)構(gòu)（從概念到Java實(shí)現(xiàn)）——參考代碼及答案第四章圖結(jié)構(gòu)4.5基礎(chǔ)知識(shí)檢測(cè)一、填空題1.鄰接矩陣、鄰接表，深度優(yōu)先遍歷、廣度優(yōu)先遍歷2．出度3.N4.O(n2)5.O(n+e)6.鄰接表7.鄰接矩陣8.有向9.將鄰接矩陣的第i行全部置0。10.不是11.O(n2)O(n+e)12.11.O(n2)O(n+e)13.小或相等14.O(n2)O(elog2e)15.克魯斯卡爾(Kruskal)16.普里姆(Prim)17.遞增18.0二、選擇題CBBCCBACDDAADA4.2.1實(shí)驗(yàn)1：圖的存儲(chǔ)【實(shí)驗(yàn)要求】1．圖的鄰接矩陣存儲(chǔ)及輸出。2．圖的鄰接表存儲(chǔ)及輸出?！具\(yùn)行結(jié)果參考】圖4-25鄰接矩陣存儲(chǔ)運(yùn)行結(jié)果1．圖的鄰接矩陣存儲(chǔ)及輸出?！距徑泳仃嘕ava源代碼】（1）圖的接口IGraph.javapublicinterfaceIGraph{ voidcreateGraph();//創(chuàng)建一個(gè)圖 intgetVexNum();//返回頂點(diǎn)數(shù) intgetArcNum();//返回邊數(shù) ObjectgetVex(intv)throwsException;//返回v表示結(jié)點(diǎn)的值，0<=v<vexNum intlocateVex(Objectvex);//給定頂點(diǎn)的值vex，返回其在圖中的位置，如果圖中不包含此頂點(diǎn)，則返回-1 intfirstAdjVex(intv)throwsException;//返回v的第一個(gè)鄰接點(diǎn)，若v沒(méi)有鄰接點(diǎn)，則返回-1，其中0≤v<vexNum intnextAdjVex(intv,intw)throwsException;//返回v相對(duì)于w的下一個(gè)鄰接點(diǎn)，若w是v的最后一個(gè)鄰接點(diǎn)，則返回-1，其中0≤v,w<vexNum}（2）圖的種類有向圖、有向網(wǎng)、無(wú)向圖、無(wú)向網(wǎng)GraphKind.javapublicenumGraphKind{ UDG,//無(wú)向圖（UnDirectedGraph) DG,//有向圖（DirectedGraph) UDN,//無(wú)向網(wǎng)（UnDirectedNetwork) DN;//有向網(wǎng)（DirectedNetwork)}（3）圖類MGraph.javaimportjava.util.Scanner;publicclassMGraphimplementsIGraph{ publicfinalstaticintINFINITY=Integer.MAX_VALUE; privateGraphKindkind;//圖的種類 privateintvexNum,arcNum;//圖的頂點(diǎn)數(shù)和邊數(shù) privateObject[]vexs;//頂點(diǎn)集合 privateint[][]arcs;//邊集 publicMGraph(){ this(null,0,0,null,null); } publicMGraph(GraphKindkind,intvexNum,intarcNum,Object[]vexs, int[][]arcs){ this.kind=kind; this.vexNum=vexNum; this.arcNum=arcNum; this.vexs=vexs; this.arcs=arcs; } //創(chuàng)建圖 publicvoidcreateGraph(){ Scannersc=newScanner(System.in); System.out.println("請(qǐng)輸入圖的類型"); kind=GraphKind.valueOf(sc.next()); switch(kind){ caseUDG: createUDG(); return; caseDG: createDG(); return; caseUDN: createUDN(); return; caseDN: createDN(); return; } } privatevoidcreateUDG(){ Scannersc=newScanner(System.in); System.out.println("請(qǐng)分別輸入圖的頂點(diǎn)數(shù)、圖的邊數(shù)："); vexNum=sc.nextInt(); arcNum=sc.nextInt(); vexs=newObject[vexNum]; System.out.println("請(qǐng)分別輸入各個(gè)頂點(diǎn)："); for(intv=0;v<vexNum;v++) //構(gòu)造頂點(diǎn)向量 vexs[v]=sc.next(); arcs=newint[vexNum][vexNum]; for(intv=0;v<vexNum;v++) //初始化鄰接矩陣 for(intu=0;u<vexNum;u++) arcs[v][u]=0; System.out.println("請(qǐng)輸入各個(gè)邊的兩個(gè)頂點(diǎn)："); for(intk=0;k<arcNum;k++){ intv=locateVex(sc.next()); intu=locateVex(sc.next()); arcs[v][u]=arcs[u][v]=1; } } privatevoidcreateDG(){ Scannersc=newScanner(System.in); System.out.println("請(qǐng)分別輸入圖的頂點(diǎn)數(shù)、圖的邊數(shù)："); vexNum=sc.nextInt(); arcNum=sc.nextInt(); vexs=newObject[vexNum]; System.out.println("請(qǐng)分別輸入各個(gè)頂點(diǎn)："); for(intv=0;v<vexNum;v++) //構(gòu)造頂點(diǎn)向量 vexs[v]=sc.next(); arcs=newint[vexNum][vexNum]; for(intv=0;v<vexNum;v++) //初始化鄰接矩陣 for(intu=0;u<vexNum;u++) arcs[v][u]=0; System.out.println("請(qǐng)輸入各個(gè)邊的兩個(gè)頂點(diǎn)："); for(intk=0;k<arcNum;k++){ intv=locateVex(sc.next()); intu=locateVex(sc.next()); arcs[v][u]=1; } } privatevoidcreateUDN(){ Scannersc=newScanner(System.in); System.out.println("請(qǐng)分別輸入圖的頂點(diǎn)數(shù)、圖的邊數(shù)："); vexNum=sc.nextInt(); arcNum=sc.nextInt(); vexs=newObject[vexNum]; System.out.println("請(qǐng)分別輸入各個(gè)頂點(diǎn)："); for(intv=0;v<vexNum;v++) //構(gòu)造頂點(diǎn)向量 vexs[v]=sc.next(); arcs=newint[vexNum][vexNum]; for(intv=0;v<vexNum;v++) //初始化鄰接矩陣 for(intu=0;u<vexNum;u++) arcs[v][u]=INFINITY; System.out.println("請(qǐng)輸入各個(gè)邊的兩個(gè)頂點(diǎn)及權(quán)值："); for(intk=0;k<arcNum;k++){ intv=locateVex(sc.next()); intu=locateVex(sc.next()); arcs[v][u]=arcs[u][v]=sc.nextInt(); } } //創(chuàng)建有向網(wǎng) privatevoidcreateDN(){ Scannersc=newScanner(System.in); System.out.println("請(qǐng)分別輸入圖的頂點(diǎn)數(shù)、圖的邊數(shù)："); vexNum=sc.nextInt(); arcNum=sc.nextInt(); vexs=newObject[vexNum]; System.out.println("請(qǐng)分別輸入各個(gè)頂點(diǎn)："); for(intv=0;v<vexNum;v++) //構(gòu)造頂點(diǎn)向量 vexs[v]=sc.next(); arcs=newint[vexNum][vexNum]; for(intv=0;v<vexNum;v++) //初始化鄰接矩陣 for(intu=0;u<vexNum;u++) arcs[v][u]=INFINITY;