数据结构智慧树知到答案章节测试2023年中央财经大学

绪论单元测试数据结构是计算机科学与技术专业的基础核心课程。（）

A:错

B:对

答案:B第一章测试用链表实现栈，当栈顶位于链表首部时，最坏情况下对栈的每次push和pop操作仅需要常数时间。（）

A:对

B:错

答案:A对容量已满的栈执行push操作，会发生（）。

A:上溢

B:对象游离

C:空指针异常

D:下溢

答案:A泛型可以在编译期发现类型不匹配的错误。（）

A:对

B:错

答案:A二分查找可以用最多lgN次键值比较完成对大小为N的排序数组的查找。（）

A:对

B:错

答案:B算法理论分析中的常用符号有（）。

A:波浪线

B:BigTheta

C:BigOmega

D:BigO

答案:ABCD第二章测试假设对N个元素进行归并排序，则需要的归并操作的次数约为（）。

A:logN

B:N/2

C:N

D:NlogN

答案:A假设要从2000个元素中得到10个最小元素，最好采用（）。

A:插入排序

B:快速排序

C:归并排序

D:堆排序

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

A:{10,3,8,16,22,24,18}

B:{3,8,10,16,18,22,24}

C:{10,8,3,16,24,22,18}

D:{8,3,10,16,24,18,22}

答案:C自然的归并排序。编写一个自底向上的归并排序，当需要将两个子数组排序时能够利用数组中已经有序的部分。首先找到一个有序的子数组（移动指针直到当前元素比上一个元素小为止），然后再找出另一个并将它们归并。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;

intj=0;

for(inttemp=0;temp<mergeNum/2;temp++){

//内循环次数是分组个数除以2的整数部分，如分组个数为5，则内循环2次

intlo=index[j];

//记录归并起始位

intmid

=index[j+i/2]-1;

//记录两个归并分组中第一个分组的最后一位

inthi=0;

if(j+i>num-1)

hi=a.length-1;

else

hi=index[j+i]-1;

//记录两个归并分组中第二个分组的最后一位merge(a,aux,lo,mid,hi);

count++;

//记录每次内循环完成的归并次数

j=j+i;

}

mergeNum=mergeNum-count;

//得到剩余需要归并的分组个数

}

}

privatestaticbooleanless(Comparablev,Comparablew){

returnpareTo(w)<0;

}

privatestaticvoidshow(Comparable[]a){

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

StdOut.print(a[i]);

}

}

publicstaticvoidmain(String[]args){

String[]a={“D”,“R”,“T”,“E”,“X”,“A”,“M”,“C”,“L”,“B”,“O”,“R”,“T”,“E”,“X”,“A”,“M”,“G”,“L”,“A”,“M”,“I”,“L”};

MergeBUN.sort(a);

show(a);

}}

A:a_index

B:a

C:i

D:j

答案:D找出最小元素。在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;}……}

A:其他选项均不正确

B:n++

C:++n

D:n

答案:C第三章测试以下关于红黑树的说法，错误的是（）。

A:其他选项均不正确

B:红黑树是一棵二叉查找树

C:红黑树是一棵平衡树

D:红黑树表示的是一棵2-3查找树

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

A:散列表需要采用散列函数进行散列值的计算

B:散列表又叫做哈希表

C:散列表解决的碰撞的方法有拉链法和线性探测法

D:如果采用双向散列函数，散列表可以被可以攻击

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

A:错

B:对

答案:A给定二叉查找树的数据结构，进行插入操作。publicclassBST<KeyextendsComparable,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(

？

);}}

A:x.val

B:val

C:x

D:key

答案:C给定如下的红黑树的数据结构，请完成红黑树的插入（put方法）操作。publicclassRedBlackBST<KeyextendsComparable,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(

？

);}}}

A:h.right

B:null

C:h

D:h.left

答案:C第四章测试以下说法，错误的是（）。

A:加权无向图是一个包含顶点和加权有向边的图结构

B:有向图是一个包含顶点和有向边的图结构

C:无向图是一个包含顶点和无向边的图结构

D:其他选项均不正确

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

A:Bellman-Ford算法不能处理带有负权重回路的加权有向图

B:Dijkstra算法不能处理带有负权重的加权有向图

C:拓扑排序算法不能处理存在回路的加权有向图

答案:ABC用于计算最短路径的Dijkstra和用于计算最小生成树的Prim算法是同一算法家族。（）

A:对

B:错

答案:A给定无向图的数据结构，进行插入和查找的操作，请根据要求填空。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);

}

}

}

}}

A:true

B:null

C:false

D:v

答案:A给定如下的加权图的数据结构，完成最小生成树的延时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(