【MOOC】数据结构与算法-大连理工大学 中国大学慕课MOOC答案

【MOOC】数据结构与算法-大连理工大学中国大学慕课MOOC答案1.1随堂测验1、【单选题】在链接存储结构中，要求。本题答案：【每个结点占用一片连续的存储区域】2、【单选题】对于数据结构的描述，下列说法中不正确的是。本题答案：【相同的逻辑结构对应的存储结构也必须相同】3、【单选题】以下关于链接存储结构的叙述中，是不正确的。本题答案：【可以通过计算得到第i个节点的存储地址】4、【单选题】可以用、数据关系和基本操作定义一个完整的抽象数据类型。本题答案：【数据元素】5、【多选题】顺序存储结构中数据元素之间的逻辑关系是由表示的，链接存储结构中的数据元素之间的逻辑关系式由表示的。本题答案：【存储位置#指针】1.2随堂测验1、【单选题】算法指得是。本题答案：【对特定问题求解步骤的一种描述，是指令的有限序列。】2、【单选题】下面不是算法所必须具备的特性。本题答案：【高效性】3、【单选题】某算法的时间复杂度是O(n^2)，表明该算法。本题答案：【执行时间与n^2成正比】4、【单选题】设某算法完成对n个元素进行处理，所需的时间是T(n)=100nlgn+200n+500，则该算法的时间复杂度是。本题答案：【O(nlgn)】5、【单选题】算法的时间复杂度属于一种。本题答案：【事前分析估算的方法】绪论单元作业绪论单元测验1、【单选题】在链接存储结构中，要求。本题答案：【每个结点占用一片连续的存储区域】2、【单选题】对于数据结构的描述，下列说法中不正确的是。本题答案：【相同的逻辑结构对应的存储结构也必须相同】3、【单选题】以下关于链接存储结构的叙述中，是不正确的。本题答案：【可以通过计算得到第i个节点的存储地址】4、【单选题】可以用、数据关系和基本操作定义一个完整的抽象数据类型。本题答案：【数据元素】5、【单选题】算法指得是。本题答案：【对特定问题求解步骤的一种描述，是指令的有限序列】6、【单选题】下面不是算法所必须具备的特性。本题答案：【高效性】7、【单选题】某算法的时间复杂度是O(n^2)，表明该算法。本题答案：【执行时间与n^2成正比】8、【单选题】设某算法完成对n个元素进行处理，所需的时间是T(n)=100nlgn+200n+500，则该算法的时间复杂度是。本题答案：【O(nlgn)】9、【单选题】算法的时间复杂度属于一种。本题答案：【事前分析估算的方法】2.1随堂测验1、【单选题】将两个各有n个元素的有序顺序表归并成一个有序顺序表，其最少的比较次数是。本题答案：【n】2、【单选题】在长度为n的线性表中查找值为x的数据元素的时间复杂度为。本题答案：【O(n)】3、【单选题】线性表的顺序存储结构是一种的存储结构。本题答案：【随机存取】4、【多选题】在一个长度为n的顺序表的第i(1≤i≤n+1)个元素之前插入一个元素，需向后移动个元素，删除第i(1≤i≤n)个元素时，需向前移动个元素。本题答案：【n-i+1#n-i】2.2随堂测验1、【单选题】设线性表中有2n个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高。本题答案：【删除指定的元素】2、【单选题】如果最常用的操作是取第i个节点及其前驱，则采用存储方式最节省时间。本题答案：【顺序表】3、【单选题】与单链表相比，双链表的优点之一是。本题答案：【访问前后相邻结点更灵活】4、【单选题】带头结点的单链表L为空的判定条件是。本题答案：【L-next==NULL】5、【单选题】在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行操作。本题答案：【q-next=s;s-next=p;】6、【单选题】设指针rear指向带头结点的循环单链表的尾结点，若要删除链表的第一个元素结点，正确的操作是。本题答案：【s=rear-next-next;rear-next-next=s-next;】2.3随堂测验1、【单选题】经过以下栈运算后，x的值是。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s.x);本题答案：【a】2、【单选题】一个栈的进栈a,b,c,d,e则栈的不可能的输出序列是。本题答案：【dceab】3、【单选题】已知一个栈的进栈序列是ABC，出栈序列是CBA，经过的栈操作是。本题答案：【push,push,push,pop,pop,pop】4、【单选题】判定一个顺序栈st为（元素个数最多为MaxSize）空的条件为。本题答案：【st.top==-1】5、【单选题】链栈与顺序栈相比有一个明显的优点，即。本题答案：【通常不会出现栈满的情况】2.5随堂测验1、【单选题】设环形队列中数组的下标是0～N-1，其头、尾指针分别为f和r，则其元素个数为。本题答案：【(r-f+N)%N】2、【单选题】对于链队，在进行删除操作时，。本题答案：【头、尾指针可能都要修改】2.6随堂测验1、【单选题】两个串相等必有串长度相等且。本题答案：【串中各位置字符均对应相等】2、【单选题】对于含有n个字符的链串s，查找元素值为x的算法时间复杂度为。本题答案：【O(n)】3、【单选题】设有两个串p和q，求q在p中首次出现的位置的运算称作。本题答案：【模式匹配】2.7随堂测验1、【单选题】已知t=”abcaabbcabcaabdab”，该模式串的特征数组值为。本题答案：【-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1】线性表单元作业线性表单元测验1、【单选题】将两个各有n个元素的有序顺序表归并成一个有序顺序表，其最少的比较次数是。本题答案：【n】2、【单选题】在长度为n的线性表中查找值为x的数据元素的时间复杂度为。本题答案：【O(n)】3、【单选题】线性表的顺序存储结构是一种的存储结构。本题答案：【随机存取】4、【单选题】设线性表中有2n个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高。本题答案：【删除指定的元素】5、【单选题】如果最常用的操作是取第i个节点及其前驱，则采用存储方式最节省时间。本题答案：【顺序表】6、【单选题】与单链表相比，双链表的优点之一是。本题答案：【访问前后相邻结点更灵活】7、【单选题】带头结点的单链表L为空的判定条件是。本题答案：【L-next==NULL】8、【单选题】在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行操作。本题答案：【q-next=s;s-next=p;】9、【单选题】设指针rear指向带头结点的循环单链表的尾结点，若要删除链表的第一个元素结点，正确的操作是。本题答案：【s=rear-next-next;rear-next-next=s-next;】10、【单选题】经过以下栈运算后，x的值是。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s.x);本题答案：【a】11、【单选题】一个栈的进栈a,b,c,d,e则栈的不可能的输出序列是。本题答案：【dceab】12、【单选题】已知一个栈的进栈序列是ABC，出栈序列是CBA，经过的栈操作是。本题答案：【push,push,push,pop,pop,pop】13、【单选题】判定一个顺序栈st为（元素个数最多为MaxSize）空的条件为。本题答案：【st.top==-1】14、【单选题】链栈与顺序栈相比有一个明显的优点，即。本题答案：【通常不会出现栈满的情况】15、【单选题】设环形队列中数组的下标是0～N-1，其头、尾指针分别为f和r，则其元素个数为。本题答案：【(r-f+N)%N】16、【单选题】对于链队，在进行删除操作时，。本题答案：【头、尾指针可能都要修改】17、【单选题】对于含有n个字符的链串s，查找元素值为x的算法时间复杂度为。本题答案：【O(n)】18、【单选题】已知t=”abcaabbcabcaabdab”，该模式串的特征数组值为。本题答案：【-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1】3.1随堂测验1、【单选题】若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是本题答案：【11】2、【单选题】具有10个叶结点的二叉树中有个度为2的结点。本题答案：【9】3、【单选题】一棵完全二叉树上有1001个结点，其中叶子结点的个数是。本题答案：【501】4、【单选题】二叉树的第I（只有根结点时的层数为1）层上最多含有结点数为。本题答案：【2^(I-1)】5、【单选题】一个具有1025个结点的二叉树的高h（只有根结点时的高度为1）为本题答案：【11至1025之间】6、【单选题】一棵二叉树高度为h（只有根结点时的高度为1）,所有结点的度或为0，或为2，则这棵二叉树最少有结点本题答案：【2h-1】7、【单选题】高度为K（只有根结点时的高度为1）的二叉树最大的结点数为。本题答案：【2^k-1】8、【单选题】一棵树高为K（只有根结点时的高度为1）的完全二叉树至少有个结点本题答案：【2^(k-1)】9、【填空题】由3个结点所构成的二叉树有种形态。本题答案：【5】3.2随堂测验1、【单选题】二叉树是非线性数据结构，所以。本题答案：【顺序存储结构和链式存储结构都能存储】2、【单选题】对于任意非空二叉树，要设计出其后序遍历的非递归算法而不是用堆栈结构，最适合的方法是对该二叉树采用存储结构。本题答案：【三叉链表】3.4随堂测验1、【单选题】一直二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为。本题答案：【DEBFCA】2、【填空题】用一维数组存放的一棵完全二叉树ABCDEFGHIJKL，该二叉树的后序遍历的访问结点序列为。本题答案：【HIDJKEBLFGCA##%_YZPRLFH_%##hidjkeblfgca】3.6随堂测验1、【填空题】设字符A，B，C，D，E，F的在报文中出现的频率分别为0.25,0.2,0.06,0.14,0.28,0.07。求A的Huffman编码。本题答案：【01】2、【填空题】（续）求B的Huffman编码。本题答案：【00】3、【填空题】（续）求C的Huffman编码。本题答案：【1000】4、【填空题】（续）求D的Huffman编码。本题答案：【101】5、【填空题】（续）求E的Huffman编码。本题答案：【11】6、【填空题】（续）求F的Huffman编码。本题答案：【1001】3.7随堂测验1、【单选题】有n个叶子的哈夫曼树的结点总数为。本题答案：【2n-1】2、【单选题】下面关于Huffman树的说法，不正确的是。本题答案：【Huffman树中除了度为1的结点外，还有度为2的结点和叶结点】二叉树单元作业二叉树单元测验1、【单选题】若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是。本题答案：【11】2、【单选题】具有10个叶结点的二叉树中有个度为2的结点。本题答案：【9】3、【单选题】一棵完全二叉树上有1001个结点，其中叶子结点的个数是。本题答案：【501】4、【单选题】二叉树的第I（只有根结点时的层数为1）层上最多含有结点数为。本题答案：【2^(l-1)】5、【单选题】一个具有1025个结点的二叉树的高h（只有根结点时的高度为1）为本题答案：【11至1025之间】6、【单选题】一棵二叉树高度为h（只有根结点时的高度为1）,所有结点的度或为0，或为2，则这棵二叉树最少有结点本题答案：【2h-1】7、【单选题】高度为K（只有根结点时的高度为1）的二叉树最大的结点数为。本题答案：【2^k-1】8、【单选题】一棵树高为K（只有根结点时的高度为1）的完全二叉树至少有个结点本题答案：【2^(k-1)】9、【单选题】二叉树是非线性数据结构，所以。本题答案：【顺序存储结构和链式存储结构都能存储】10、【单选题】对于任意非空二叉树，要设计出其后序遍历的非递归算法而不是用堆栈结构，最适合的方法是对该二叉树采用存储结构。本题答案：【三叉链表】11、【单选题】一直二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为。本题答案：【DEBFCA】12、【单选题】有n个叶子的哈夫曼树的结点总数为。本题答案：【2n-1】13、【单选题】下面关于Huffman树的说法，不正确的是。本题答案：【Huffman树中除了度为1的结点外，还有度为2的结点和叶结点】14、【单选题】二叉树的先序遍历的递归实现如下：templateclassTvoidBinaryTreeT::PreOrder(BinaryTreeNodeT*root){if(root!=NULL){;}}则中间部分应为：本题答案：【Visit(root-value());PreOrder(root-leftchild());PreOrder(root-rightchild());】15、【单选题】在任何一棵二叉树中，如果结点a有左孩子b,右孩子c,则在结点的先序序列、中序序列、后序序列中，本题答案：【结点b一定在结点c的前面】16、【单选题】在二叉树的前序序列、中序序列和后序序列中，所有叶子结点的先后顺序本题答案：【完全相同】17、【单选题】设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是本题答案：【n在m左方】18、【单选题】下列序列中，不能唯一地确定一棵二叉树的是本题答案：【先序序列和后序序列】19、【单选题】设结点X和Y是二叉树中任意的两个结点．在该二叉树的先序遍历序列中X在Y之前，而在其后序遍历序列中X在Y之后，则X和Y的关系是本题答案：【X是Y的祖先】20、【单选题】一棵二叉树的前序遍历序列为1234567,它的中序遍历序列可能是本题答案：【1234567】21、【单选题】在二叉搜索树的存储结构中，关键字值最大的结点（）本题答案：【右指针一定为空】22、【单选题】对于下列关键字序列，不可能构成某二叉搜索树中的一条查找路径的序列是（）本题答案：【95，22，91，24，94，71】23、【单选题】从空树开始一次插入元素52，26，14，32，71，60，93，58，24，41后构成一个二叉搜索树。在该树中查找60要进行比较的次数是（）本题答案：【3】24、【单选题】对于二叉搜索树，下面说法正确的是（）本题答案：【用逐点插入法构造二叉搜索树，若先后插入的关键字有序，二叉搜索树的深度最大】25、【单选题】设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。?本题答案：【2m】26、【单选题】根据使用频率为五个字符设计的哈夫曼编码不可能是__。?本题答案：【100，11，10，1，0?】27、【单选题】设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（????）个。本题答案：【n+1】28、【单选题】设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中的第一棵树的结点个数是__。?本题答案：【m-n-1】29、【单选题】度为4、高度为h的树，__。?本题答案：【至少有h+3个结点】30、【单选题】设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（????）。本题答案：【M2+M3】4.1随堂测验1、【单选题】设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是。本题答案：【n(k+1)-2m】2、【单选题】设无向图的顶点个数为n，则该图最多有条边。本题答案：【n(n-1)/2】4.2随堂测验1、【单选题】下列说法正确的是。本题答案：【用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。】4.3随堂测验1、【单选题】下列说法不正确的是。本题答案：【图的深度遍历不适用于有向图】2、【单选题】无向图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)}，对该图进行深度优先遍历，得到的顶点序列正确的是。本题答案：【a,e,d,f,c,b】3、【单选题】判断一个有向图是否存在回路除了可以使用拓扑排序方法外，还可以使用方法。本题答案：【深度优先遍历】4.4随堂测验1、【单选题】在用Kruskal算法求解带权连通图的最小生成树时，通常采用一个辅助结构。本题答案：【并查集】2、【单选题】下列说法正确的是本题答案：【最小生成树的Kruskal算法是一种贪心算法。】4.5随堂测验1、【单选题】下列说法不正确的是。(1).求从指定源点到其余各顶点的Dijkstra最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2).利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3)；（图用邻接矩阵表示）(3).Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。本题答案：【(1),(2),(3)】4.6随堂测验1、【单选题】关键路径是事件结点网络中。本题答案：【从源点到汇点的最长路径】2、【单选题】下面关于求关键路径的说法不正确的是。本题答案：【一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差】图单元作业图单元测验1、【单选题】设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是。本题答案：【n(k+1)-2m】2、【单选题】设无向图的顶点个数为n，则该图最多有条边。本题答案：【n(n-1)/2】3、【单选题】下列说法正确的是。本题答案：【用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。】4、【单选题】下列说法不正确的是。本题答案：【图的深度遍历不适用于有向图】5、【单选题】无向图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)}，对该图进行深度优先遍历，得到的顶点序列正确的是。本题答案：【a,e,d,f,c,b】6、【单选题】判断一个有向图是否存在回路除了可以使用拓扑排序方法外，还可以使用方法。本题答案：【深度优先遍历】7、【单选题】在用Kruskal算法求解带权连通图的最小生成树时，通常采用一个辅助结构。本题答案：【并查集】8、【单选题】下列说法正确的是本题答案：【最小生成树的Kruskal算法是一种贪心算法】9、【单选题】下列说法不正确的是。(1).求从指定源点到其余各顶点的Dijkstra最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2).利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3)；（图用邻接矩阵表示）(3).Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。本题答案：【(1),(2),(3)】10、【单选题】关键路径是事件结点网络中。本题答案：【从源点到汇点的最长路径】11、【单选题】下面关于求关键路径的说法不正确的是。本题答案：【一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差】12、【单选题】一个有n个顶