数据结构与算法-电子科技大学中国大学mooc课后章节答案期末考试题库2023年

数据结构与算法_电子科技大学中国大学mooc课后章节答案期末考试题库2023年哈希函数H(k)=k%11,采用开放地址法的平方探测再散列（di=1,4,9,16,......)解决冲突，输入关键字（9,31,26,19,1,13,2,11,27,16,21)，表长为13，建立的哈希表为（），ASL(成功）=（）

参考答案:

地址0123456789101112关键字1111322627161993121

查找次数11121121122

ASL（成功）=15/11

请对下列数据13，24，7，1，8，9，11，56，34，51，2，77，5，进行简单插入排序，冒泡排序（每趟大数冒到后面）和选择排序，2趟后的排序结果为：（）

参考答案:

2趟后的简单插入排序序列为：7,13，24，1，8，9，11，56，34，51，2，77，52趟后的冒泡排序为：7，1，8，9，11，13，24，34，2，51，5，56，772趟后的选择排序为：1，2，7，13，8，9，11，56，34，51，24，77，5

已知输入数据13，24，7，1，8，9，11，56，34，51，2，77，5，请采用2路归并递归排序算法进行排序，2趟排序后的结果为（）

参考答案:

1，7，13，24，8，9，11，34，51，56，2，5，77

已知输入数据13，24，7，1，8，9，11，56，34，51，2，77，5，请采用快速归排序算法进行排序，其中枢纽采用3者取中法，2趟排序后的结果为（）注意：答案中的括号表示快排中的分组

参考答案:

（（2，5，1），7，（8，9）），11，（（13，34，24），51，（77，56））

已知输入数据13，24，7，1，8，9，11，56，34，51，2，77，5，增量序列d=5,3,1,请采用希尔排序算法进行排序，2趟排序后的结果为（）

参考答案:

1，7，5，2，8，9，24，11，34，51，13，77，56

已知输入数据1，2，8，5，9，11，34，56，51，77，请分析数据，采用（）排序算法效率最低

参考答案:

选择排序

已知某递归算法的复杂度为：T(n)=2T(n/2)+4,则求解该递归式的解为：（）

参考答案:

T(n)=O(n)

动态规划与贪心算法的最大区别（）

参考答案:

贪心算法不是递归问题，动态规划是递归问题

分治法所能解决的问题一般具有以下几个特征:1.该问题的规模缩小到一定的程度就可以容易地解决；2.____________3.利用该问题分解出的子问题的解可以合并为该问题的解；4.该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

参考答案:

最优子结构

求一个数据序列的逆序数量不可以通过______排序中增加1个计数器实现。提示:一个排列含有逆序的个数称为这个排列的逆序数。例如排列263451含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。

参考答案:

堆排序

下面（）说法是正确的

参考答案:

大部分递归程序可以转换为非递归程序，非递归程序运行速度更快。

已知求一组数据连续若干数和的最大值采用分治方法得到O(nlogn)的时间复杂度，请完成下面分治法求解的代码：/************************************************************************//*分治法最大和子数组有三种情况：1)A[1...mid]2)A[mid+1...N]3)A[i..mid..j]/************************************************************************///findmaxcrossingleftandrightintFind_Max_Crossing_Subarray(intarr[],intlow,intmid,inthigh){constintinfinite=-9999;intleft_sum=infinite;intright_sum=infinite;intmax_left=-1,max_right=-1;intsum=0;//frommidtoleft;for(inti=mid;i>=low;i--){sum+=arr[i];if(sum>left_sum){left_sum=sum;max_left=i;}}sum=0;//frommidtorightfor(intj=mid+1;j<=high;j++){sum+=arr[j];if(sum>right_sum){right_sum=sum;max_right=j;}}return(left_sum+right_sum);}intFind_Maximum_Subarray(intarr[],intlow,inthigh){if(high==low)//onlyoneelement;returnarr[low];else{intmid=(low+high)/2;intleftSum=Find_Maximum_Subarray(arr,low,mid);intrightSum=Find_Maximum_Subarray(arr,mid+1,high);intcrossSum=Find_Max_Crossing_Subarray(arr,low,mid,high);——————————完成这里的代码——————————————————}}

参考答案:

inttmp=(leftSum>rightSum?leftSum:rightSum;return(tmp>crossSum?tmp:crossSum);

下面（）术语与数据的存储结构无关

参考答案:

队列

算法分析的目的是（）

参考答案:

分析算法的效率以求改进

下图不是合法的拓扑排序有（）【图片】

参考答案:

ACDBEF

最小生成树除了prim和kuscal算法，还有没有其他的算法？

参考答案:

还有其他算法，包括破圈法在内的其他最小生成树算法，效率没有比prim或者kruscal算法更好。

汽车加油问题问题描述：一辆汽车加满油可以行驶n公里（km)。旅途中有若干加油站。设计1个有效算法，指出应该在哪些加油站加油，使得沿途加油次数最少。数据输入：第一行2个正整数n和k，表示汽车加满油可以行驶n公里，沿途有k个加油站。第二行有k+1个正整数，表示第i个加油站和第i+1个加油站的距离。第0个加油站是出发地，汽车已经加满油，第k+1个加油站代表目的地。输出：输出1个正整数表示最少加油次数输入示例：7712345166输出结果：4下面说法不正确的是（）

参考答案:

采用贪心算法，每一个加油站都去加油，使得油箱出发的时候都是满的，即使加油站隔的很远，比如大于n公里，也能够开到下一个加油站。

求城市a到其他城市的最短距离及路线【图片】

参考答案:

a到其他城市的最短距离及路径分别为：(1)a->b:23

(2)a->c:18

(3)a->c->e:30

(4)a->c->e->d:36(5)a->c->e->f:39

(6)a->c->e->g:55

下面程序段的时间复杂度是（）i=s=0;while(s

参考答案:

O(sqrt(n))

注释：sqrt(n)表示对n开方

双向链表中有2个指针域pre和next，分别指向直接前驱和直接后继，假设有指针p指向链表中的一个结点，指针q指向一个待插入的结点，现在要求在p的前面插入q所指结点，则正确的插入语句为（）

参考答案:

p->pre->next=q;q->next=p;q->pre=p->pre;p->pre=q;

在一个具有n个链结点的线性链表中，按数据内容查找某一个结点，如果查找成功，需要平均比较（）个结点。

参考答案:

(n+1)/2

假设按照行优先存储整数数组A[9][8]，第一个元素a11的首字节地址是100，每个整数占4个字节，则元素a32的存储地址是（）提示：数组大小是9行8列，第一个位置是1，不是0

参考答案:

168

一个栈的入栈序列是a,b,c,d,e,则不可能的出栈输出序列是（）

参考答案:

dceab

当对一个线性表经常进行存取而很少进行插入及删除操作时，采用（）存储结构最节省时间；如果经常进行插入，删除操作时，则采用（）存储结构最节省时间。

参考答案:

顺序，链式

已知数据3,4,-2,0,8存储在顺序存储结构中，编程实现删除x的操作为（）提示：数据从顺序存储结构的第0个位置开始存储

参考答案:

voiddel(SqListL,elemtypex){

inti=0;

while(i

已知不带头结点的单链表L，下面用函数实现的在第一个元素前面插入值为x的元素结点的算法错误的是（）

参考答案:

void

insert(List*L,elemtypex){

ptrp=*L;

noded=newnode(x);

ptrq=&d;

p->next=q;

L=&q;}

下面程序段的输出结果是（）voidmain(){QueueQ;InitQueue(Q);charx='e',y='c';EnQueue(Q,'h');EnQueue(Q,'r');EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,'a‘);while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);}printf(x);

参考答案:

char

当在一个有序的顺序存储表上查找一个数据时，可用折半查找，也可用顺序查找，但前者比后者的查找速度()

参考答案:

大部分情况下快

关键字越大，优先级越高。为了更好的为优先级高的顾客服务，银行应该采用什么存储结构支撑算法？

参考答案:

有序链表

已知由关键字序列17,28,36,54,30,27,94,15,21,83,40构造小顶堆，按照层序输出的关键字序列为：（）注意：用空格分隔输出序列

参考答案:

1517272130369454288340

【图片】从顶点1开始，用prim算法按次序输出最小生成树的边()

参考答案:

（1，2）（2，4）（4，5）（5，6）（6，3）

用kruscal算法，按顺序输出最小生成树的各边（）【图片】

参考答案:

（5，6）（4，5）（2，4）（1，2）（2，3）

3个不同的结点，可以构成（）颗不同的二叉树

参考答案:

5

利用dijkstra算法计算从节点1到其他节点的最短路径，算法执行到下图状态之后，接下来应该把哪个节点添加到探索集中？（）【图片】

参考答案:

结点5

已知由一组字符组成的字符串，其中各个字符的访问次数分别为17,28,36,54,30,27,94,15,21,83,40，请对该字符串中的字符进行最优编码，其最优编码的带权路径长度为（）

参考答案:

1447

数据的关系有逻辑关系和存储关系。其中逻辑关系是进行算法分析和设计需要考虑与使用的，而存储关系是编程实现的时候需要考虑的，逻辑关系和存储关系之间并没有关系

参考答案:

错误

已知由关键字序列17,28,36,54,30,27,94,15,21,83,40得到的平衡二叉树AVL的查找成功的平均查找长度ASL为()注意：结果用最简分数形式

参考答案:

3

考虑下面的整数线性规划问题：【图片】其中：【图片】【图片】是非负整数，且【图片】下面（）是正确求解过程

参考答案:

首先给出该问题的子问题描述：且

的最优值为m(i,j)

，也就是m(i,j)表示在背包容量是j，可以选择物品1,2,...,i的时候背包问题的最优值。由背包问题的最优子结构性质，可以建立计算m(i,j)的递归关系式如下：m(i,j)=其中初始值，m(0,j)=m(i,0)=0,m(i,j)=

已知由关键字序列17,28,36,54,30,27,94,15,21,83,40得到的二叉排序树的查找成功的平均查找长度ASL为()注意：结果用最简分数形式

参考答案:

39/11

已知由关键字序列17,28,36,54,30,27,94,15,21,83,40得到的二叉排序树，删除关键字36的结点的最佳操作是（）

参考答案:

用右子树的最小关键字40替换关键字结点36

已知有一系列输入数据为32,14,78,2,62,5,需要得到5,2,2,7,4,2，请问用什么数据结构支撑算法？

参考答案:

用栈将数据全部入栈，再出栈，出栈的数据取个位，就得到需要的输出序列。

下面的递归函数时间复杂度是O(1)intfact(intn){if(n<=1)return1;elsereturnn*fact(n-1);}

参考答案:

错误

程序存储问题问题描述：假设有n个程序（1,2,3....,n）要存放在长度为L的磁带上。程序i存放在磁带上的长度是【图片】,【图片】.程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得尽量快地能够在磁带上存储尽可能多的程序。数据输入：第一行读入2个正整数，分别表示文件个数n和磁带程度L;第二行读入n个正整数，分别表示n个文件存储在磁带上的长度。输出：输出1个整数数为满足要求的最多存储的文件数输入示例：650231388020输出：5下面的选项正确的是（）

参考答案:

先如果,则将所有程序都可以放入磁带，因此能够存放的最多程序数量为n。否则，将程序按照在磁带上的存储长度非递减排序，假设排序后，第i个程序的长度为,其中且。则采用贪心算法，将程序长度最小的程序依次存放到磁带上，直到第k个磁带不能存储到磁带，则结束。磁带能够存放的程序个数为k-1(k

某一工程作业的网络图如图所示，其中箭头表示作业，箭头上的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-3-4-8-10-11）表示进行作业的路径。其中0表示工程开始，11表示工程的结束。求（1）完成此工程的关键路径；（2）完成此工程所需的最少天数【图片】

参考答案:

（1）关键路径上的事件为：0-2-6-9-11（2）20天

设顺序表L是一个非递减的有序表，下面的哪个算法，能够将元素x插入L中，并使L仍然有序。

参考答案:

//L是顺序存储结构voidinsert(list*L,elemtypex){

inti=L->length-1;

while(i>=0)

{

if(xdata[i]){L->data[i+1]=L->data[i];--i;}

}

L->data[i]=x；

L->length+=1;}

算法可以用不同的语言描述，比如C或者java，所以算法实际上就是程序。

参考答案:

错误

找零钱问题用（）算法

参考答案:

贪心算法，不能得到全局最优解

下面程序段的时间复杂度是（）i=1;while(i<=n)i=i*3;

参考答案:

O(logn)注释：对数复杂度

给定权值总数有n个，其哈夫曼树的结点总数是()

参考答案:

2n-1

二叉排序树的()结果是一个关键字的递增有序序列

参考答案:

中序遍历

在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序()

参考答案:

完全相同

下列四个序列中，哪一个是堆()

参考答案:

75,45,65,30,15,25,20,10

二叉树的先序序列是EFHIGJK，中序序列为HFIEJKG，该二叉树右子树的根是()

参考答案:

G

一棵完全二叉树上有1001个结点，其叶子结点的个数是()

参考答案:

501

二叉树的先序和中序遍历序列相同，则此二叉树为（）

参考答案:

任一结点无左子树

假设完全二叉树的树根为第1层，树中第10层有5个叶子结点，则完全二叉树最