对应课程:点击查看
起止时间:2021-08-31到2022-06-30
更新状态:每周周末更新
第二章 线性表 第二章 线性表测验
1、 下面关于线性表的叙述中，正确的是哪些？Which of the followings about linear list are correct?（There are more than one answers.）Select the answer that matches
A:线性表采用顺序存储，必须占用一片连续的存储单元。Linear lists use sequential storage which must occupy a continuous memory units.
B:线性表采用顺序存储，便于进行插入和删除操作。Linear lists using sequential storage, it is easy to do insert and delete operations.
C:线性表采用链接存储，不必占用一片连续的存储单元。Linear lists using the linked storage, do not occupy a continuous memory units.
D:线性表采用链接存储，便于插入和删除操作。Linear lists using the linked storage, it is easy for insert and deleting operations.
答案: 线性表采用顺序存储，必须占用一片连续的存储单元。Linear lists use sequential storage which must occupy a continuous memory units.;
线性表采用链接存储，不必占用一片连续的存储单元。Linear lists using the linked storage, do not occupy a continuous memory units.;
线性表采用链接存储，便于插入和删除操作。Linear lists using the linked storage, it is easy for insert and deleting operations.
2、 下面的叙述中正确的是：Select the answer that matches （There are more than one correct answers）
A:线性表在链式存储时，查找第i个元素的时间与i的数值无关。When the linear list stored in linked form, the time to find the i-th element is regardless of the value of i.
B:线性表在顺序存储时，查找第i个元素的时间与i的数值成正比。When the linear list stored sequentially, the time to find the i-th element is proportional to value with i.
C:线性表在顺序存储时，查找第i个元素的时间与i的数值无关。When the linear list stored sequentially, the time to find the i-th element is regardless of the value of i.
D:线性表在链式存储时，插入第i个元素的时间与i的数值成正比。When linear lists stored in the linked form, the time to insert the i-th element is proportional to value with i.
答案: 线性表在顺序存储时，查找第i个元素的时间与i的数值无关。When the linear list stored sequentially, the time to find the i-th element is regardless of the value of i.;
线性表在链式存储时，插入第i个元素的时间与i的数值成正比。When linear lists stored in the linked form, the time to insert the i-th element is proportional to value with i.
3、 完成在双循环链表结点p之后插入s的操作为：The operation to insert s after the doubly circular linked list’s node p is: (There are more than one answers.)
A:p->next->prev=s; s->prev=p; s->next=p->next; p->next=s;
B:p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
C:s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
D:s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;
答案: p->next->prev=s; s->prev=p; s->next=p->next; p->next=s; ;
s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;
4、 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为O(),在给定值为x的结点后插入一个新结点的时间复杂度为O()。（请依次填入,格式为(a)(b),如果您的答案中出现字母，请使用小写;后一空系统基于字符匹配来判定答案，所以您的答案中不要出现空格）For a single linked list with n nodes, and after a known node p to insert a new node, the time complexity is O (); after a given node with x value insert a new node, the time complexity is O (). (If your answer contains letters, use lowercase one.The second blank is judged by string matching, Please make sure your answer don’t contain any blanks. )
答案: (1)(n)
5、 设某循环链表长度为n，并设其中一节点为p1，然后按照链表的顺序将后面的节点依次命名为p2,p3,…,pn，那么请问pn.next=____(答案为一个节点名，注意所有字母为小写且答案中不包含空格)
答案: p1
第七章 图 第七章 图测验
1、 在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。In a undirected graph, the sum of degrees of all vertices is equal to the amount of all edges times ().
A:2
B:3
C: 1
D:1/2
答案: 2
2、 在有向图G的拓扑序列中，若顶点
在顶点
之前，则下列情形不可能出现的是（ ）。In the topological order sequences of the directed graph G, if vertex Vi appears before Vj, then the impossible situation of the following is ()
A:G中有一条从
到
的路径 There is a path from Vj to Vi in the G.
B:G中有边(，) G contains edge (Vi,Vj).
C:G中有一条从到的路径 G contains a path from Vi to Vj.
D:G中没有边(，) G doesn’t contain edge(Vi,Vj)
答案: G中有一条从到的路径 There is a path from Vj to Vi in the G.
3、 当各边上的权值满足什么要求时，宽度优先搜索算法可用来解决单源最短路径问题？
What requirement do the weight of edges should satisfied to make width-first search algorithm can solve single source shortest path problem?
A:均互不相等 Each edge is not equal to each other.
B:均相等Equal
C:不一定相等 No limitation.
D:不一定相等（忽略该选项）
答案: 均相等Equal
4、 下面关于图的说法正确的有
The right statements of graphs in the following are:
A: 对于有向图，每个结点的出度必须要等于入度。As for directed graph, each vertices’ out-degree is equal to its in-degree.
B:对于一个连通图，一定存在一种给边添加方向的方案使得这个图变成强连通图。For a connected graph, there must be a way of directing all the edges of the original graph to make the graph strongly connected graph.
C:对于有向图，所有结点的入度加起来一定为奇数。For directed graph, the sum of in-degrees of all nodes must be odd number.
D:对于无向图，所有结点的度数加起来一定是偶数。As for undirected graphs, the sum of degrees of all vertices is definitely even number.
E: 将有向图的一个强连通分量中的边全部反向仍然是强连通分量。Reversion all the edges of a strongly connected component of a directed graph, then the subgraph is still a strongly connected component.
答案: 对于无向图，所有结点的度数加起来一定是偶数。As for undirected graphs, the sum of degrees of all vertices is definitely even number.;
将有向图的一个强连通分量中的边全部反向仍然是强连通分量。Reversion all the edges of a strongly connected component of a directed graph, then the subgraph is still a strongly connected component.
5、 下列关于最短路算法的说法正确的有：The right statements of the following are:
A:当图中不存在负权回路但是存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。 When the graph doesn’t contain circuit of negative weight, but contains the edge of negative weight. Dijkstra algorithm can’t guarantee the correctness of the algorithm.
B:当图中不存在负权边时，Dijkstra算法能求出每对顶点间最短路径。 When the graph doesn’t contain edge of negative weight, Dijkstra algorithm can calculate the shortest path of each pair of vertices.
C:当图中存在负权回路时，Dijkstra算法也一定能求出源点到所有点的最短路。When the graph contains the circuit of negative weight, Dijkstra algorithm can certainly calculate the shortest path form the single source to all the vertices.
D: Dijkstra算法不能用于每对顶点间最短路计算。Dijkstra algorithm can’t be applied to calculate the shortest path of each pair of vertices.
答案: 当图中不存在负权回路但是存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。 When the graph doesn’t contain circuit of negative weight, but contains the edge of negative weight. Dijkstra algorithm can’t guarantee the correctness of the algorithm.;
当图中不存在负权边时，Dijkstra算法能求出每对顶点间最短路径。 When the graph doesn’t contain edge of negative weight, Dijkstra algorithm can calculate the shortest path of each pair of vertices.
6、 下图中的强连通分量的个数为多少个？ How many strongly connected graphs in the under graph? 
答案: 3
7、 如果无向图G=(V,E)是简单图，并且|V|=n>0，那么图G最多包含多少条边？If undirected graph G = (V,E) is simple graph, and |V| = n > 0, then how many edges can graph G contains at most？（There is only one correct answer）
答案: (以下答案任选其一都对)n(n-1)/2;
(n-1)n/2
8、 有向图G如下图所示，请写出所有拓扑排序序列。所有的顶点都直接用其数字标号表示，如拓扑排序序列为
，那么请写成1234（中间没有空格）。不同的拓扑排序序列按照字典序排序，中间用一个空格隔开。Directed graph G looks like following graph, please list all the topological order sequences. All the vertices are marked by numbers directly. Like topological order sequence V1V2V3V4, we write it as 1234(with no blank space).Different topological order sequences are sorted according to alphabet order, and separated by a blank space. 
答案: 1234 1324 2134
9、 无向图G=(V, E)，其中：V={a, b, c, d, e, f}, E={(a, b), (a, e), (a, c), (b, e), (c, f), (f, d), (e, d)}，对该图进行深度优先遍历（优先访问编号小的结点），得到的顶点序列为？注意：答案中没有空格 Undirected G = (V,E), concretely: V = {a,b,c,d,e,f}, E = {(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},perform depth-first traversal(visit the vertex of small number firstly), what vertices sequence do we get?
Notice: no blank space in answer.
答案: abedfc
10、 请使用Kruskal算法求出下图的最小生成树，依次写出每次被选择的合法的合并代价最小的边的编号（如果同时存在多条边满足要求，选择编号最小的）。顶点a到顶点b (a < b)之间的边编号为ab，例如图中权值为1的边编号为02。(不同编号之间用一个空格分隔） Please use Kruskal algorithm to the following graph and find the minimum spanning tree, and write the number of the valid vertex with minimum merging cost in turn(if there are many vertices satisfy requirement, choose the vertex with minimum number ). The number of the edge connecting vertex a and vertex b is ab. Like the edge with weight 1 in the graph, its number is 02(different numbers separated by a blank space). 
答案: 02 35 14 25 12
11、 请使用Prim算法从结点0出发求下图的最小生成树，依次写出每次被加入到最小生成树中边的编号（如果同时存在多条边满足要求，选择编号最小的）。顶点a到顶点b (a < b)之间的边编号为ab，例如图中权值为1的边编号为02。(不同编号之间用一个空格分隔）Please use prim algorithm starting from vertex 0 to find the minimum spanning tree of the following graph, write the number of the edge added into the minimum spanning tree in turn((if there are many vertices satisfy requirement, choose the vertex with minimum number). The number of the edge connecting vertex a and vertex b is ab. Like the edge with weight 1 in the graph, its number is 02(different numbers separated by a blank space). 
答案: 02 25 35 12 14
12、 题图为一无向图,分别写出从顶点1出发,按深度优先搜索遍历算法得到的顶点序列,和按广度优先搜索遍历算法得到的顶点序列 
答案: 123456 123564
第三章 栈与队列 第三章 栈与队列测验
1、 设栈S 和队列Q 的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6 个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是___。Assume that the stack S and queue Q’s initial state is empty, the elements e1, e2, e3, e4, e5 and e6 followed through stack S, an element out the stack means into the queue Q. If the sequence the six elements out of the queue is e2, e4, e3, e6, e5, e1 then stack S of capacity should be at least _____. （There is only one correct answer）
A:2
B:3
C:4
D:6
答案: 3
2、 现有中缀表达式E=((100-4)/3+3(36-7))2。以下哪个是与E等价的后缀表达式？Existing infix expression E = ((100-4) / 3 + 3 * (36-7)) * 2. Which of the following is the equivalent postfix expression of E? （There is only one correct answer）
A:( ( 100 4 – ) 3 / 3 ( 36 7 – ) * + ) 2
B: + / – 100 4 3 * 3 – 36 7 2
C:100 4 – 3 / 3 36 7 – * + 2
D: ( + / ( – 100 4 ) 3 * 3 ( – 36 7 ) ) 2
答案: 100 4 – 3 / 3 36 7 – * + 2 *
3、 队列的特点包括：Queue’ features include:（There are more than one answers.）
A:后进先出Last-in first-out (LIFO)
B:先进后出First-in last-out (FILO)
C:先进先出First-in first-out (FIFO)
D:后进后出 Last-in last-out (LILO)
答案: 先进先出First-in first-out (FIFO);
后进后出 Last-in last-out (LILO)
4、 以下循环队列的实现方式中，长度为n的队列，所能容纳的元素个数也为n的有:In the following realizing ways of circular queue, the queue whose length is n can also contain the number of n elements is:（There are more than one answers.）
A:只用front和rear两个指针标记队列的头和尾，两个指针均为实指Only use front and rear as the queue’s head and tail pointers and the two pointers are actually referring to.
B:用front和rear两个指针标记队列的头和尾，并用整型变量len记录队列元素数With the queue’s head and tail pointers marked as front and rear, use the integer variable len to record the number of elements.
C:用front和rear两个指针标记队列的头和尾，并用布尔型变量empty记录队列是否为空With the queue’s head and tail pointers marked as front and rear, use Boolean variable empty record whether the queue is empty.
D:只用front和rear两个指针标记队列的头和尾，两个指针均为虚指Only use front and rear as the queue’s head and tail pointers and the two pointers are virtually referring to.
答案: 用front和rear两个指针标记队列的头和尾，并用整型变量len记录队列元素数With the queue’s head and tail pointers marked as front and rear, use the integer variable len to record the number of elements.;
用front和rear两个指针标记队列的头和尾，并用布尔型变量empty记录队列是否为空With the queue’s head and tail pointers marked as front and rear, use Boolean variable empty record whether the queue is empty.
5、 编号为1，2，3，4的四辆列车，顺序开进一个栈式结构的站台；则开出车站的顺序有__种可能。 注释：例如 1, 2, 3, 4 或 4, 3, 2，1 就是其中两种可能出站序列；而 4, 3, 1, 2 是 非法序列。Numbered 1,2,3,4 four trains, orderly entered a stack structure station. How many possible leaving sequences of that four trains ? ____ . Note: For instance, the leaving sequence could be 1,2,3,4 or 4,3,2,1 these two possibilities, but 4, 3, 1, 2 is not a possible sequence.
答案: 14
6、 双端队列可以在队列的两端进行插入和删除操作，既可在队尾进行插入/删除，又可在队头进行插入/删除。现有4个不同的元素顺序输入到双端队列，那么可以得到_种不同的排列。double-ended queue can insert and delete operations on both ends of the queue. That it can insert / delete at its tail, but also at the head. Existing 4 different elements sequentially input to the double-ended queue, you can get ___ different permutations.
答案: 8
第四章 字符串 第四章 字符串测验
1、 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为( )（单选）There are two strings p q, q is p’s substring. The algorithm to search the first time q appeared in p is called ( )（There is only one correct answer）
A:求子串 Seeking substring
B:联接 Concatenation
C:匹配 Matching
D:求串长 Seeking length
答案: 匹配 Matching
2、 下列说法正确的是：（单选） Which of the following statements is correct? （There is only one correct answer）
A:空串就是空白串“Empty string” is blank string.
B:空串是任意字符串的子串 Empty string is a substring of arbitrary string.
C:串只可以采用顺序存储，不可以采用链式存储 String only can be stored in sequential method and cannot be stored in linked method.
D:在C++标准中，char S[M]最多能表示长度为M的字符串 In C ++ standards, char S[M] can represent up to a string of length M.
答案: 空串是任意字符串的子串 Empty string is a substring of arbitrary string.
3、 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))注意：substr(S,i,j)是对字符串S的下标为i开始取j个字符，这里的下标是从0开始的(单选)If the string S1 = ‘ABCDEFG’, S2 = ‘9898’, S3 = ‘###’, S4 = ‘012345’, execute concat (replace (S1, substr (S1, length (S2), length (S3)), S3), substr (S4, index (S2, ‘8’), length (S2))) Note substr (S, i, j) is the operation to take string S’s j characters from subscript i. Subscript here is starting from 0.（There is only one correct answer）
A:ABC###G0123
B:ABCD###2345
C:ABCD###1234
D:ABC###G2345
答案: ABCD###1234
4、 下面关于串的的叙述中，哪一个是不正确的:（单选） Which of the following descriptions about string is not correct? （There is only one correct answer）
A:串是字符的有限序列 String is a finite sequence of characters.
B:模式匹配是串的一种重要运算 Pattern matching is an important operation.
C:串是一种数据对象和操作都特殊的线性表 String is a linear list whose data objects and operations both special
D:空串是由空格构成的串 Empty string is a string consisting of spaces.
答案: 空串是由空格构成的串 Empty string is a string consisting of spaces.
5、 Seek the string “BAAABBBAA” ‘s feature vector, where the feature vector is defined as follows:（There is only one correct answer）
为了方便下次阅读，建议在浏览器添加书签收藏本网页
添加书签方法：
1.电脑按键盘的Ctrl键+D键即可收藏本网页
2.手机浏览器可以添加书签收藏本网页
获取更多MOOC答案，欢迎在浏览器访问我们的网站：http://mooc.mengmianren.com
注：请切换至英文输入法输入域名，如果没有成功进入网站，请输入完整域名：http://mooc.mengmianren.com/
我们的公众号
打开手机微信，扫一扫下方二维码，关注微信公众号：萌面人APP
本公众号可查看各种网课答案，还可免费查看大学教材答案
点击这里，可查看公众号功能介绍
一键领取淘宝，天猫，京东，拼多多无门槛优惠券，让您购物省省省，点击这里，了解详情