数据结构智慧树知到期末考试答案章节答案2024年中央财经大学

数据结构智慧树知到期末考试答案+章节答案2024年中央财经大学加权quick-union算法中，若一共有N个节点，任意节点x的深度不超过lgN。（）

答案:对广度优先搜索是先搜索一个顶点的所有邻接顶点，然后再搜索其他顶点。（）

答案:对可以使用无序链表实现符号表。（）

答案:对二叉查找树的查找最坏代价是对数级别的。（）

答案:错有序符号表的类可定义为：classST,Value>。（）

答案:错有向图的强连通分量中的每两个顶点之间都有互相指向的边。（）

答案:对Bellman-Ford算法可以获得含有负权重回路的加权有向图的最短路径。（）

答案:错二叉查找树的查找和插入性能是同一数量级的。（）

答案:对用顶点的集合可以表示无向图。（）

答案:错拓扑排序算法能够获得含有负权重的加权有向图的最短路径。（）

答案:对一棵大小为N的完全二叉树的高度可以表示为（），当N是2的幂次时，树的高度加1。

答案:log2N一个迭代器需要具有hasNext和（）方法。

答案:next链表的存储结构所占存储空间（）。

答案:分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针二叉堆的形状是一棵（）。

答案:完全二叉树如果我们知道一个栈的入栈序列是1，2，3，4，……，n，输出序列的第一个为n，那么第i个为（）。

答案:n-i+1（）的数据结构无法表示无向图。

答案:顶点的集合下边四种排序算法中，（）的空间复杂度最大。

答案:归并排序对一组数据{84,47,25,15,21,16}进行一次递增长度为3的希尔排序后，结果为（）。

答案:{15,21,16,84,47,25}基于二叉查找树的有序符号表中，如果计算某个节点的排名，需要的平均计算代价是（）。

答案:logN在一个单链表中若p所指节点不是最后节点，在p之后插入s节点的操作是（）。

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

答案:从根节点到null链接的每条路径都有相同数量的黑色链接Bellman-Ford算法可以用于（）情况下加权有向图的最短路径计算。

答案:不存在负权重回路二分查找可以用最多（）的键值比较完成大小为N的排序数组的查找。

答案:1+lgN在无向图中，如果有V的顶点，E条边，采用邻接表表示无向图，添加一条边的时间复杂度为（）。

答案:1在有向图中，可以通过（）次深度优先搜索获取强连通分量。

答案:2二叉查找树的英文缩写为（）。

答案:BST有N个元素的双探针的拉链法散列表可以将最长链的期望长度降低为（）。

答案:loglogN如果从空栈进行pop操作，则会（）。

答案:下溢（）是实现2-3树的有效二叉树。

答案:红黑树二分查找法最坏条件下的代价为（）。

答案:lgN拉链法散列表中每一key对应一个（）。

答案:链表如果用有序数组实现符号表，其插入的最坏代价是（）。

答案:N将一棵有100个节点的完全二叉树从根这一层开始，每一层上从左到右依次对节点进行编号，根节点的编号为1，则编号为49的节点的左孩子编号为（）。

答案:98用拉链法散列表将N个元素散列到M大小的数组中，探测的数量正比于（）。

答案:N/M编译器实现一个函数时，函数调用过程中（）当前环境并保存其地址。

答案:push在有向图中，如果有V的顶点，E条边，采用邻接表表示有向图，采用Kosaraju算法计算强连通分量的时间复杂度为（）。

答案:E+V在不存在负权重回路的加权有向图中，如果有V的顶点，E条边，采用邻接表表示加权有向图，若采用基于队列的Bellman-Ford算法计算最短路径，则最坏情况下的时间复杂度为（）。

答案:E*V算法的运行时间取决于（）。

答案:操作的代价和操作的频率二叉堆是一个堆有序的完全二叉树的数组表示，可以用数组索引在树中实现查找，节点k的父节点(若存在)的索引为（）。

答案:k/2对于二叉查找树来说，（）方法可以获得某个元素在所有元素中的排名。

答案:rank加权quick-union通过什么连接方式避免树变高？（）。

答案:小树连接到大树上采用Kruskal算法可以实现加权图的最小生成树生成算法，其中，MinPQ是用来存储边的最小优先队列类，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在平均散列的假设下，大小为M，且包含N=aM的键的线性探测散列表查找命中的平均探测数量为（）。

答案:(2-a)/(2-2a)在加权无向图中，如果有V的顶点，E条边，采用邻接表表示加权无向图，若采用即时的Prime算法计算最小生成树，则最坏情况下的时间复杂度为（）。

答案:ElogV在加权有向无环图中，如果有V的顶点，E条边，采用邻接表表示加权有向图，若采用拓扑排序算法计算最短路径，则最坏情况下的时间复杂度为（）。

答案:E+V在无向图中，欧拉回路计算可以通过（）实现。

答案:深度优先搜索在不存在负权重的加权有向图中，如果有V的顶点，E条边，采用邻接表表示加权有向图，若采用Dijkstra算法计算最短路径，则最坏情况下的时间复杂度为（）。

答案:ElogV在选择排序、插入排序和希尔排序中，（）是稳定的。

答案:插入排序在线性探测法散列表中，为了在M大小的散列表中查找key对应的val，可以采用如下的代码，其中keys为散列表中用来保存key的数组，vals是保存key的数组：publicValueget(Keykey){for(inti=hash(key);keys[i]!=null;i=(

？))

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

答案:(i+1)%M给定无向图的数据结构，进行插入和查找的操作，请根据要求填空。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用于计算最短路径的Dijkstra和用于计算最小生成树的Prim算法是同一算法家族。（）

答案:对关于有向图的最短路径计算，正确的是（）。

答案:Bellman-Ford算法不能处理带有负权重回路的加权有向图###拓扑排序算法不能处理存在回路的加权有向图###Dijkstra算法不能处理带有负权重的加权有向图给定如下的加权图的数据结构，完成最小生成树的延时prim方法的计算（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)以下说法，错误的是（）。

答案:加权无向图是一个包含顶点和加权有向边的图结构给定二叉查找树的数据结构，进行插入操作。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给定如下的红黑树的数据结构，请完成红黑树的插入（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以下关于红黑树的说法，错误的是（）。

答案:其他选项均不正确在考虑有序性操作的情况下，符号表应该优先采用散列表而不是平衡树进行表示。（）

答案:错以下关于散列表的说法，错误的是（）。

答案:散列表又叫做哈希表###如果采用双向散列函数，散列表可以被可以攻击###散列表需要采用散列函数进行散列值的计算###散列表解决的碰撞的方法有拉链法和线性探测法假设要从2000个元素中得到10个最小元素，最好采用（）。

答案:堆排序给定数组{16,22,3,24,10,8,18}，用16作为切分元素完成一次快速排序切分后，其结果为（）。

答案:{10,8,3,16,24,22,18}找出最小元素。在MaxPQ中加入一个min()方法。你的实现所需的时间和空间都应该是常数。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自然的归并排序。编写一个自底向上的归并排序，当需要将两个子数组排序时能够利用数组中已经有序的部分。首先找到一个有序的子数组（移动指针直到当前元素比上一个元素小为止），然后再找出另一个并将它们归并。publicclassMergeBUN{

//GetIndex函数功能：从index[1]开始记录第二个自然分组以及之后每个自然分组的"开始下标"

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

{

intj=0;

a_index[j++]=0;

//第一个自然分组开始下标默认为0

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

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

a_index[j++]=i+1;

}

}

//j为自然分组的个数

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);

//识别数组中的自然分组

intmergeNum=num;

//保存自然分组的个数

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

//

intcount=0;