數(shù)據(jù)結(jié)構(gòu)智慧樹知到期末考試答案章節(jié)答案2024年中央財(cái)經(jīng)大學(xué)

數(shù)據(jù)結(jié)構(gòu)智慧樹知到期末考試答案+章節(jié)答案2024年中央財(cái)經(jīng)大學(xué)加權(quán)quick-union算法中，若一共有N個(gè)節(jié)點(diǎn)，任意節(jié)點(diǎn)x的深度不超過(guò)lgN。（）

答案:對(duì)廣度優(yōu)先搜索是先搜索一個(gè)頂點(diǎn)的所有鄰接頂點(diǎn)，然后再搜索其他頂點(diǎn)。（）

答案:對(duì)可以使用無(wú)序鏈表實(shí)現(xiàn)符號(hào)表。（）

答案:對(duì)二叉查找樹的查找最壞代價(jià)是對(duì)數(shù)級(jí)別的。（）

答案:錯(cuò)有序符號(hào)表的類可定義為：classST,Value>。（）

答案:錯(cuò)有向圖的強(qiáng)連通分量中的每?jī)蓚€(gè)頂點(diǎn)之間都有互相指向的邊。（）

答案:對(duì)Bellman-Ford算法可以獲得含有負(fù)權(quán)重回路的加權(quán)有向圖的最短路徑。（）

答案:錯(cuò)二叉查找樹的查找和插入性能是同一數(shù)量級(jí)的。（）

答案:對(duì)用頂點(diǎn)的集合可以表示無(wú)向圖。（）

答案:錯(cuò)拓?fù)渑判蛩惴軌颢@得含有負(fù)權(quán)重的加權(quán)有向圖的最短路徑。（）

答案:對(duì)一棵大小為N的完全二叉樹的高度可以表示為（），當(dāng)N是2的冪次時(shí)，樹的高度加1。

答案:log2N一個(gè)迭代器需要具有hasNext和（）方法。

答案:next鏈表的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（）。

答案:分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針二叉堆的形狀是一棵（）。

答案:完全二叉樹如果我們知道一個(gè)棧的入棧序列是1，2，3，4，……，n，輸出序列的第一個(gè)為n，那么第i個(gè)為（）。

答案:n-i+1（）的數(shù)據(jù)結(jié)構(gòu)無(wú)法表示無(wú)向圖。

答案:頂點(diǎn)的集合下邊四種排序算法中，（）的空間復(fù)雜度最大。

答案:歸并排序?qū)σ唤M數(shù)據(jù){84,47,25,15,21,16}進(jìn)行一次遞增長(zhǎng)度為3的希爾排序后，結(jié)果為（）。

答案:{15,21,16,84,47,25}基于二叉查找樹的有序符號(hào)表中，如果計(jì)算某個(gè)節(jié)點(diǎn)的排名，需要的平均計(jì)算代價(jià)是（）。

答案:logN在一個(gè)單鏈表中若p所指節(jié)點(diǎn)不是最后節(jié)點(diǎn)，在p之后插入s節(jié)點(diǎn)的操作是（）。

答案:s->next=p->next;p->next=s在左斜的紅黑二叉查找樹中，（）。

答案:從根節(jié)點(diǎn)到null鏈接的每條路徑都有相同數(shù)量的黑色鏈接Bellman-Ford算法可以用于（）情況下加權(quán)有向圖的最短路徑計(jì)算。

答案:不存在負(fù)權(quán)重回路二分查找可以用最多（）的鍵值比較完成大小為N的排序數(shù)組的查找。

答案:1+lgN在無(wú)向圖中，如果有V的頂點(diǎn)，E條邊，采用鄰接表表示無(wú)向圖，添加一條邊的時(shí)間復(fù)雜度為（）。

答案:1在有向圖中，可以通過(guò)（）次深度優(yōu)先搜索獲取強(qiáng)連通分量。

答案:2二叉查找樹的英文縮寫為（）。

答案:BST有N個(gè)元素的雙探針的拉鏈法散列表可以將最長(zhǎng)鏈的期望長(zhǎng)度降低為（）。

答案:loglogN如果從空棧進(jìn)行pop操作，則會(huì)（）。

答案:下溢（）是實(shí)現(xiàn)2-3樹的有效二叉樹。

答案:紅黑樹二分查找法最壞條件下的代價(jià)為（）。

答案:lgN拉鏈法散列表中每一key對(duì)應(yīng)一個(gè)（）。

答案:鏈表如果用有序數(shù)組實(shí)現(xiàn)符號(hào)表，其插入的最壞代價(jià)是（）。

答案:N將一棵有100個(gè)節(jié)點(diǎn)的完全二叉樹從根這一層開(kāi)始，每一層上從左到右依次對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)，根節(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的節(jié)點(diǎn)的左孩子編號(hào)為（）。

答案:98用拉鏈法散列表將N個(gè)元素散列到M大小的數(shù)組中，探測(cè)的數(shù)量正比于（）。

答案:N/M編譯器實(shí)現(xiàn)一個(gè)函數(shù)時(shí)，函數(shù)調(diào)用過(guò)程中（）當(dāng)前環(huán)境并保存其地址。

答案:push在有向圖中，如果有V的頂點(diǎn)，E條邊，采用鄰接表表示有向圖，采用Kosaraju算法計(jì)算強(qiáng)連通分量的時(shí)間復(fù)雜度為（）。

答案:E+V在不存在負(fù)權(quán)重回路的加權(quán)有向圖中，如果有V的頂點(diǎn)，E條邊，采用鄰接表表示加權(quán)有向圖，若采用基于隊(duì)列的Bellman-Ford算法計(jì)算最短路徑，則最壞情況下的時(shí)間復(fù)雜度為（）。

答案:E*V算法的運(yùn)行時(shí)間取決于（）。

答案:操作的代價(jià)和操作的頻率二叉堆是一個(gè)堆有序的完全二叉樹的數(shù)組表示，可以用數(shù)組索引在樹中實(shí)現(xiàn)查找，節(jié)點(diǎn)k的父節(jié)點(diǎn)(若存在)的索引為（）。

答案:k/2對(duì)于二叉查找樹來(lái)說(shuō)，（）方法可以獲得某個(gè)元素在所有元素中的排名。

答案:rank加權(quán)quick-union通過(guò)什么連接方式避免樹變高？（）。

答案:小樹連接到大樹上采用Kruskal算法可以實(shí)現(xiàn)加權(quán)圖的最小生成樹生成算法，其中，MinPQ是用來(lái)存儲(chǔ)邊的最小優(yōu)先隊(duì)列類，UF是Union-Find類，具體如下：publicclassKruskalMST{

privateQueuemst=newQueue();

publicKruskalMST(EdgeWeightedGraphG)

{

MinPQpq=newMinPQ(G.edges());

UFuf=newUF(G.V());

while(!pq.isEmpty()&&mst.size()<G.V()-1)

{

Edgee=pq.delMin();

intv=().either(),w=e.other(v);

if(!uf.connected(v,w))

{

uf.union(v,w);

mst.enqueue(e);

}

}

}

publicIterableedges()

{returnmst;}}

答案:e在平均散列的假設(shè)下，大小為M，且包含N=aM的鍵的線性探測(cè)散列表查找命中的平均探測(cè)數(shù)量為（）。

答案:(2-a)/(2-2a)在加權(quán)無(wú)向圖中，如果有V的頂點(diǎn)，E條邊，采用鄰接表表示加權(quán)無(wú)向圖，若采用即時(shí)的Prime算法計(jì)算最小生成樹，則最壞情況下的時(shí)間復(fù)雜度為（）。

答案:ElogV在加權(quán)有向無(wú)環(huán)圖中，如果有V的頂點(diǎn)，E條邊，采用鄰接表表示加權(quán)有向圖，若采用拓?fù)渑判蛩惴ㄓ?jì)算最短路徑，則最壞情況下的時(shí)間復(fù)雜度為（）。

答案:E+V在無(wú)向圖中，歐拉回路計(jì)算可以通過(guò)（）實(shí)現(xiàn)。

答案:深度優(yōu)先搜索在不存在負(fù)權(quán)重的加權(quán)有向圖中，如果有V的頂點(diǎn)，E條邊，采用鄰接表表示加權(quán)有向圖，若采用Dijkstra算法計(jì)算最短路徑，則最壞情況下的時(shí)間復(fù)雜度為（）。

答案:ElogV在選擇排序、插入排序和希爾排序中，（）是穩(wěn)定的。

答案:插入排序在線性探測(cè)法散列表中，為了在M大小的散列表中查找key對(duì)應(yīng)的val，可以采用如下的代碼，其中keys為散列表中用來(lái)保存key的數(shù)組，vals是保存key的數(shù)組：publicValueget(Keykey){for(inti=hash(key);keys[i]!=null;i=(

？))

{if(key.equals(keys[i])){returnvals[i];}returnnull;}

答案:(i+1)%M給定無(wú)向圖的數(shù)據(jù)結(jié)構(gòu)，進(jìn)行插入和查找的操作，請(qǐng)根據(jù)要求填空。publicclassGraph{

privatefinalintV;

privateintE;privateBag[]adj;}publicclassBreadthFirstPaths{

privatestaticfinalintINFINITY=Integer.MAX_VALUE;

privateboolean[]marked;

//marked[v]=isthereans-vpath

privateint[]edgeTo;

//edgeTo[v]=previousedgeonshortests-vpath

privateint[]distTo;

//distTo[v]=numberofedgesshortests-vpath

publicBreadthFirstPaths(GraphG,ints){

marked=newboolean[G.V()];

distTo=newint[G.V()];

edgeTo=newint[G.V()];

bfs(G,s);

}

//breadth-firstsearchfromasinglesource

privatevoidbfs(GraphG,ints){

Queueq=newQueue();

for(intv=0;v<G.V();v++)

distTo[v]=INFINITY;

distTo[s]=0;

marked[s]=(

？

);

q.enqueue(s);

while(!q.isEmpty()){

intv=q.dequeue();

for(intw:G.adj(v)){

if(!marked[w]){

edgeTo[w]=v;

distTo[w]=distTo[v]+1;

marked[w]=true;

q.enqueue(w);

}

}

}

}}

答案:true用于計(jì)算最短路徑的Dijkstra和用于計(jì)算最小生成樹的Prim算法是同一算法家族。（）

答案:對(duì)關(guān)于有向圖的最短路徑計(jì)算，正確的是（）。

答案:Bellman-Ford算法不能處理帶有負(fù)權(quán)重回路的加權(quán)有向圖###拓?fù)渑判蛩惴ú荒芴幚泶嬖诨芈返募訖?quán)有向圖###Dijkstra算法不能處理帶有負(fù)權(quán)重的加權(quán)有向圖給定如下的加權(quán)圖的數(shù)據(jù)結(jié)構(gòu)，完成最小生成樹的延時(shí)prim方法的計(jì)算（prim方法）操作。publicclassEdgeimplementsComparable{

privatefinalintv;

privatefinalintw;privatefinaldoubleweight;}publicclassEdgeWeightedGraph{

privatefinalintV;

privateintE;privateBag[]adj;}publicclassLazyPrimMST{

privatestaticfinaldoubleFLOATING_POINT_EPSILON=1E-12;

privatedoubleweight;

//totalweightofMST

privateQueuemst;

//edgesintheMST

privateboolean[]marked;

//marked[v]=trueiffvontree

privateMinPQpq;

//edgeswithoneendpointintree

publicLazyPrimMST(EdgeWeightedGraphG){

mst=newQueue();

pq=newMinPQ();

marked=newboolean[G.V()];

for(intv=0;v<G.V();v++)

//runPrimfromallverticesto

if(!marked[v])prim(G,v);

//getaminimumspanningforest

}

//runPrim'salgorithmprivatevoidprim(EdgeWeightedGraphG,ints){

marked[s]=true;

for(Edgee:G.adj(s))

if(!marked[e.other(s)])(

？

);

while(!pq.isEmpty()){

//bettertostopwhenmsthasV-1edges

Edgee=pq.delMin();

//smallestedgeonpq

intv=e.either(),w=e.other(v);

//twoendpoints

if(marked[v]&&marked[w])continue;

//lazy,bothvandwalreadyscanned

mst.enqueue(e);

//addetoMST

weight+=e.weight();

if(!marked[v])scan(G,v);

//vbecomespartoftree

if(!marked[w])scan(G,w);

//wbecomespartoftree

}

}}

答案:pq.insert(e)以下說(shuō)法，錯(cuò)誤的是（）。

答案:加權(quán)無(wú)向圖是一個(gè)包含頂點(diǎn)和加權(quán)有向邊的圖結(jié)構(gòu)給定二叉查找樹的數(shù)據(jù)結(jié)構(gòu)，進(jìn)行插入操作。publicclassBST,Value>{

privateNoderoot;

//rootofBST

privateclassNode{

privateKeykey;

//sortedbykey

privateValueval;

//associateddata

privateNodeleft,right;

//leftandrightsubtrees

privateintsize;

//numberofnodesinsubtree

publicNode(Keykey,Valueval,intsize){

this.key=key;

this.val=val;

this.size=size;

}}

publicBST(){

}

privateNodeput(Nodex,Keykey,Valueval){

if(x==null)returnnewNode(key,val,1);

intcmp=pareTo(x.key);

if

(cmp<0)x.left

=put(x.left,

key,val);

elseif(cmp>0)x.right=put(x.right,key,val;

else

x.val

=val;

return(

？

);}}

答案:x給定如下的紅黑樹的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)完成紅黑樹的插入（put方法）操作。publicclassRedBlackBST,Value>{

privatestaticfinalbooleanRED

=true;

privatestaticfinalbooleanBLACK=false;

privateNoderoot;

//rootoftheBST

//BSThelpernodedatatype

privateclassNode{

privateKeykey;

//key

privateValueval;

//associateddata

privateNodeleft,right;

//linkstoleftandrightsubtrees

privatebooleancolor;

//colorofparentlink

privateintsize;

//subtreecount

publicNode(Keykey,Valueval,booleancolor,intsize){

this.key=key;

this.val=val;

this.color=color;

this.size=size;

}

}

publicRedBlackBST(){

}

//isnodexred;falseifxisnull?

privatebooleanisRed(Nodex){

if(x==null)returnfalse;

returnx.color==RED;}

privateNoderotateRight(Nodeh){

assert(h!=null)&&isRed(h.left);

//assert(h!=null)&&isRed(h.left)&&

!isRed(h.right);

//forinsertiononly

Nodex=h.left;

h.left=x.right;

x.right=h;

x.color=h.color;

h.color=RED;

x.size=h.size;

h.size=size(h.left)+size(h.right)+1;

returnx;}

//makearight-leaninglinkleantotheleft

privateNoderotateLeft(Nodeh){

assert(h!=null)&&isRed(h.right);

//assert(h!=null)&&isRed(h.right)&&!isRed(h.left);

//forinsertiononly

Nodex=h.right;

h.right=x.left;

x.left=h;

x.color=h.color;

h.color=RED;

returnx;

}

//flipthecolorsofanodeanditstwochildren

privatevoidflipColors(Nodeh){

h.color=!h.color;

h.left.color=!h.left.color;

h.right.color=!h.right.color;

}

//insertthekey-valuepairinthesubtreerootedathprivateNodeput(Nodeh,Keykey,Valueval){

if(h==null)returnnewNode(key,val,RED,1);

intcmp=pareTo(h.key);

if

(cmp<0)h.left

=put(h.left,

key,val);

elseif(cmp>0)h.right=put(h.right,key,val);

else

h.val

=val;

//fix-upanyright-leaninglinks

if(isRed(h.right)&&!isRed(h.left))

h=rotateLeft(h);

if(isRed(h.left)

&&

isRed(h.left.left))h=rotateRight(h);

if(isRed(h.left)

&&

isRed(h.right))

flipColors(h);

return(

？

);}}}

答案:h以下關(guān)于紅黑樹的說(shuō)法，錯(cuò)誤的是（）。

答案:其他選項(xiàng)均不正確在考慮有序性操作的情況下，符號(hào)表應(yīng)該優(yōu)先采用散列表而不是平衡樹進(jìn)行表示。（）

答案:錯(cuò)以下關(guān)于散列表的說(shuō)法，錯(cuò)誤的是（）。

答案:散列表又叫做哈希表###如果采用雙向散列函數(shù)，散列表可以被可以攻擊###散列表需要采用散列函數(shù)進(jìn)行散列值的計(jì)算###散列表解決的碰撞的方法有拉鏈法和線性探測(cè)法假設(shè)要從2000個(gè)元素中得到10個(gè)最小元素，最好采用（）。

答案:堆排序給定數(shù)組{16,22,3,24,10,8,18}，用16作為切分元素完成一次快速排序切分后，其結(jié)果為（）。

答案:{10,8,3,16,24,22,18}找出最小元素。在MaxPQ中加入一個(gè)min()方法。你的實(shí)現(xiàn)所需的時(shí)間和空間都應(yīng)該是常數(shù)。publicclassMaxPQimplementsIterable{

privateKey[]pq;

privateintn;

privatekeymin;

……

publicvoidinsert(Keyx){

if(n==pq.length-1)resize(2*pq.length);

if(isEmpty())

min=x;

elseif(((Comparable)x).compareTo(min)<0)

min=x;

pq[(

？

)]=x;

swim(n);}publicKeydelMax(){

if(isEmpty())

returnnull;

if(n==1)

min=null;

Keymax=pq[1];

exch(1,n--);

sink(1);

pq[n+1]=null;

if((n>0)&&(n==(pq.length-1)/4))resize(pq.length/2);

returnmax;

}publicKeygetMin(){

returnmin;}……}

答案:++n自然的歸并排序。編寫一個(gè)自底向上的歸并排序，當(dāng)需要將兩個(gè)子數(shù)組排序時(shí)能夠利用數(shù)組中已經(jīng)有序的部分。首先找到一個(gè)有序的子數(shù)組（移動(dòng)指針直到當(dāng)前元素比上一個(gè)元素小為止），然后再找出另一個(gè)并將它們歸并。publicclassMergeBUN{

//GetIndex函數(shù)功能：從index[1]開(kāi)始記錄第二個(gè)自然分組以及之后每個(gè)自然分組的"開(kāi)始下標(biāo)"

privatestaticintGetIndex(Comparable[]a,int[]a_index)

{

intj=0;

a_index[j++]=0;

//第一個(gè)自然分組開(kāi)始下標(biāo)默認(rèn)為0

for(inti=0;i<a.length-1;i++){

if(less(a[i+1],a[i])){

a_index[j++]=i+1;

}

}

//j為自然分組的個(gè)數(shù)

return

(

？

);

}

privatestaticvoidmerge(Comparable[]a,Comparable[]aux,intlo,intmid,inthi){

//copytoaux[]

for(intk=lo;k<=hi;k++){

aux[k]=a[k];

}

//mergebacktoa[]

inti=lo,j=mid+1;

for(intk=lo;k<=hi;k++){

if

(i>mid)

a[k]=aux[j++];

elseif(j>hi)

a[k]=aux[i++];

elseif(less(aux[j],aux[i]))

a[k]=aux[j++];

else

a[k]=aux[i++];

}

}

publicstaticvoidsort(Comparable[]a){

intn=a.length;

Comparable[]aux=newComparable[n];

int[]index=newint[n];

intnum=GetIndex(a,index);

//識(shí)別數(shù)組中的自然分組

intmergeNum=num;

//保存自然分組的個(gè)數(shù)

for(inti=2;i/2<num;i*=2){

//

intcount=0;