中国大学数据结构_15期末答案(mooc2023课后作业答案)
21 min read中国大学数据结构_15期末答案(mooc2023课后作业答案)
第一章 单元测试
1、中国作业数据结构中，大学答案答案与所使用的数据计算机无关的是数据的 结构。
A、结构存储
B、期末物理
C、课后逻辑
D、中国作业物理和存储
2、大学答案答案算法分析的数据目的是 。
A、结构找出数据结构的期末合理性
B、研究算法中的课后输入和输出的关系
C、分析算法的中国作业效率以求改进
D、分析算法的大学答案答案易懂性和文档性
3、算法分析的数据两个主要方面是 。
A、空间复杂性和时间复杂性
B、正确性和简明性
C、可读性和文档性
D、数据复杂性和程序复杂性
4、计算机算法指的是 。
A、计算方法
B、排序方法
C、解决问题的有限运算序列
D、调度方法
5、计算机算法必须具备输入、输出和 等5个特性。
A、可行性、可移植性和可扩充性
B、可行性、确定性和有穷性
C、确定性、有穷性和稳定性
D、易读性、稳定性和安全性
6、具有线性结构的数据结构是 。
A、图
B、树
C、广义表
D、栈
7、下面程序段的时间复杂度是 。 for(i=0; i<m; i++) for(j=0;j<n;j++) a[i][j]=i*j;
A、O(m^2)
B、O(n^2)
C、O(m*n)
D、O(m+n)
8、某算法的语句执行频度为（3n+nlog2n+n^2+8）,其时间复杂度表示为 。
A、O(n)
B、O(nlog2n)
C、O(n^2)
D、O(log2n)
9、下面程序段的时间复杂度为 。 i=1; while(i<=n) i=i*3;
A、O(n)
B、O(3n)
C、O(log3n) 注：以3为底，n的对数
D、O(n^3)
10、抽象数据类型的三个组成部分分别为 。
A、数据对象、数据关系和基本操作
B、数据元素、逻辑结构和存储结构
C、数据项、数据元素和数据类型
D、数据元素、数据结构和数据类型
11、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 。
A、数据的操作方法
B、数据元素的类型
C、数据元素之间的关系
D、数据的存取方法
12、链式存储设计时，结点内的存储单元地址 。
A、一定连续
B、一定不连续
C、不一定连续
D、部分连续，部分不连续
13、可以用 定义一个完整的数据结构。
A、数据元素
B、数据对象
C、数据关系
D、抽象数据类型
14、以下关于数据结构的说法中，正确的是 。
A、数据的逻辑结构独立于其存储结构
B、数据的存储结构独立于其逻辑结构
C、数据的逻辑结构唯一决定了其存储结构
D、数据结构仅由其逻辑结构和存储结构决定
15、某算法的时间复杂度为O(n^2)，表明该算法的 。
A、问题规模是n^2
B、执行时间等于n^2
C、执行时间与n^2成正比
D、问题规模与n^2成正比
实验1
1、实验作业需以文件附件的形式递交，文件名不能有实验者的信息。 第1题10分，其余2-7题每题15分，共100分
第二章 线性表
第二章 单元测验
1、对于顺序表的优缺点，以下说法错误的是（ ）
A、无需为表示结点间的逻辑关系而增加额外的存储空间
B、可以方便地随机存取表中的任一结点
C、插入和删除运算较方便
D、由于顺序表要求占用连续的空间，存储分配只能预先进行
2、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用( )存储方式最节省时间。
A、顺序表
B、单链表
C、双向链表
D、单循环链表
3、以下说法错误的是( ).
A、对循环链表来说，从表中任一结点出发都能扫描整个循环链表
B、对单链表来说，从表中任一结点出发都能扫描表中全部结点
C、双向链表的特点是找结点的前趋和后继都很容易
D、对向双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。
4、不带头结点的单链表head为空的判定条件是( ).
A、head＝NULL
B、Head → next＝NULL
C、Head → next＝head
D、Head!=NULL
5、带头结点的单链表head为空的判定条件是( ).
A、head＝NULL
B、Head → next＝NULL
C、Head → next＝head
D、Head!=NULL
6、非空的单循环链表head的最后一个结点*p满足( )
A、p → next＝NULL
B、p＝NULL
C、p → next=head
D、p＝head
7、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行( )
A、s→next = p→next; p→next = s;
B、p→next = s; s→next = q;
C、p→next = s→next; s→next = p;
D、q→next = s; s→next = p;
8、数据在计算机存储器内表示时，物理地址连续，数据间的逻辑关系依靠其物理地址间的连续性来表达，称之为( ).
A、存储结构
B、逻辑结构
C、顺序存储结构
D、链式存储结构
9、在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：
A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B、在第i个结点后插入一个新结点（1≤i≤n）
C、删除第i个结点（1≤i≤n）
D、将n个结点从小到大排序
10、线性表的顺序存储结构优于链表存储结构。
11、线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低。
12、对链表进行插入和删除操作时，不必移动结点 。
13、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
14、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。
15、在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素位置有关。
16、线性表的逻辑顺序与存储顺序总是一致的.
线性表理论作业
1、共7题，每题10分。
实验2顺序表
1、每题20分，共100分。
实验3链表
1、每题20分，共100分。
第三章 栈和队列
栈和队列单元测试
1、一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列（ ）。
A、a,b,c,d,e
B、d,e,c,b,a
C、d,c,e,a,b
D、e,d,c,b,a
2、设计一个判别表达式中括号是否配对的算法，采用（ ）数据结构最佳。
A、顺序表
B、链表
C、队列
D、栈
3、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。
A、1和5
B、2和4
C、4和2
D、5和1
4、循环队列的队头和队尾指针分别为front和rear，则判断循环队列为空的条件是（ ）。
A、front==rear
B、front==0
C、rear==0
D、front=rear+1
5、将递归算法转换成对应的非递归算法时，通常需要使用（ ）来保存中间结果。
A、队列
B、栈
C、链表
D、树
6、栈的插入和删除操作在（ ）。
A、栈底
B、栈顶
C、任意位置
D、指定位置
7、五节车厢以编号1，2，3，4，5顺序进入铁路调度站（栈），可以得到（ ）的编组。
A、3，4，5，1，2
B、2，4，1，3，5
C、3，5，4，2，1
D、1，3，5，2，4
8、在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（ ）。
A、front=front->next;
B、s->next=rear;rear=s;
C、rear->next=s;rear=s;
D、s->next=front;front=s;
9、一个队列的入队序列是1，2，3，4，则队列的出队序列是（ ）。
A、1，2，3，4
B、4，3，2，1
C、1，4，3，2
D、3，4，1，2
10、依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（ ）。
A、a
B、b
C、c
D、d
11、元素 a，b，c，d，e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素 d 开头的序列个数是（ ）。
A、3
B、4
C、5
D、6
12、栈和队列都是（ ）。
A、链式存储的线性结构
B、链式存储的非线性结构
C、限制存取点的线性结构
D、限制存取点的非线性结构
13、队和栈的主要区别是（ ）。
A、逻辑结构不同
B、存储结构不同
C、所包含的运算个数不同
D、限定插入和删除的位置不同
14、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。
A、i
B、n-i
C、n-i+1
D、不确定
15、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。
A、r-f
B、(n+f-r)%n
C、n+r-f
D、（n+r-f)%n
16、链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。
A、x=top->data;top=top->link；
B、top=top->link;x=top->link；
C、x=top;top=top->link；
D、x=top->link；
17、设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n<=0) return 1; else return n*fact(n-1); } 则计算fact(n)需要调用该函数的次数为（ ）。
A、n+1
B、n-1
C、n
D、n+2
18、栈在 （ ）中有所应用。
A、递归调用
B、函数调用
C、表达式求值
D、前三个选项都有
19、为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A、队列
B、栈
C、线性表
D、有序表
20、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（ ）。
A、2
B、3
C、4
D、6
21、用链接方式存储的队列，在进行删除运算时（ ）。
A、仅修改头指针
B、仅修改尾指针
C、头、尾指针都要修改
D、头、尾指针可能都要修改
22、循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A、rear=rear+1
B、rear=(rear+1)%(m-1)
C、rear=(rear+1)%m
D、rear=(rear+1)%(m+1)
23、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。
A、(rear+1)%n==front
B、rear==front
C、rear+1==front
D、(rear-l)%n==front
24、一个递归算法必须包括（ ）。
A、递归部分
B、终止条件和递归部分
C、迭代部分
D、终止条件和迭代部分
栈和队列理论练习题
1、共5题，每题20分。
实验4栈
1、每题20分，共100分。
实验5队列
1、3题，每题30分，共90分。
第六章 树和二叉树
树和二叉树单元测验
1、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ ）。
A、R[2i-1]
B、R[2i+1]
C、R[2i]
D、R[2/i]
2、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（ ）。
A、adbce
B、decab
C、debac
D、abcde
3、在一棵具有5层的满二叉树中结点总数为（ ）。
A、31
B、32
C、33
D、16
4、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ ）。
A、3
B、2
C、4
D、5
5、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（ ）。
A、98
B、99
C、50
D、48
6、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ ）。
A、DBFEAC
B、DFEBCA
C、BDFECA
D、BDEFAC
7、树最适合用来表示（ ）。
A、有序数据元素
B、无序数据元素
C、元素之间具有分支层次关系的数据
D、元素之间无联系的数据
8、任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ ）。
A、不发生改变
B、发生改变
C、不能确定
D、以上都不对
9、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（ ）个。
A、15
B、16
C、17
D、47
10、树的先根序列等同于与该树对应的二叉树的（ ）。
A、先序序列
B、中序序列
C、后序序列
D、层序序列
11、按照二叉树的定义，具有3个结点的二叉树有（ ）种。
A、3
B、4
C、5
D、6
12、由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。
A、51
B、23
C、53
D、74
13、下述编码中哪一个不是前缀码（ ）。
A、(00, 01, 10, 11)
B、(1, 0, 00, 11)
C、(0, 10, 110, 111)
D、(1, 01, 000, 001)
14、把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。
A、唯一的
B、有多种
C、有多种，但根结点都没有左孩子
D、有多种，但根结点都没有右孩子
15、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。
A、250
B、500
C、254
D、501
16、利用二叉链表存储树，则根结点的右指针是（ ）。
A、非空
B、指向最左孩子
C、指向最右孩子
D、空
17、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。
A、先序
B、中序
C、后序
D、从根开始按层次遍历
18、在下列存储形式中，（ ）不是树的存储形式。
A、双亲表示法
B、孩子链表表示法
C、孩子兄弟表示法
D、顺序存储表示法
19、设哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。
A、99
B、100
C、101
D、102
20、n（n≥2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）。
A、该树一定是一棵完全二叉树
B、树中任一非叶结点的权值一定不小于下一层任一结点的权值
C、树中一定没有度为1的结点
D、树中两个权值最小的结点一定是兄弟结点
21、引入二叉线索树的目的是（ ）。
A、加快查找结点的前驱或后继的速度
B、为了能在二叉树中方便的进行插入与删除
C、为了能方便的找到双亲
D、使二叉树的遍历结果唯一
22、将森林F转换为对应的二叉树T，F中叶结点的个数等于( )。
A、T中叶子结点的个数
B、T中度为1的结点个数
C、T中左孩子指针为空的结点个数
D、T中右孩子指针为空的结点个数
23、下列序列中，不能唯一地确定一棵二叉树的是( )。
A、层次序列和中序序列
B、先序序列和中序序列
C、后序序列和中序序列
D、先序序列和后序序列
24、n个结点的线索二叉树上含有的线索数为( )。
A、2n
B、n-1
C、n+1
D、n
实验6二叉树
1、3题，每题30分，共90分。
第七章 图
图单元测验
1、有无向图G=（V，E）和G’=（V’，E’），如G’为G的生成树，则下面不正确的说法是（ ）。
A、G’为G的子图
B、G’为G的极小连通子图，且V’=V
C、G’为G的连通分量
D、G’是G的无环子图
2、任何一个带权的无向连通图的最小生成树（ ）。
A、只有一棵
B、有一棵或多棵
C、一定有多棵
D、可能不存在
3、含n个顶点的连通图中的任意一条简单路径，其长度不可能超过（ ）。
A、1
B、n/2
C、n-1
D、n
4、在无向图中，所有顶点的度数之和是所有边数的（ ）倍。
A、0.5
B、1
C、2
D、4
5、在有向图中，所有顶点的入度之和是所有顶点出度之和的（ ）倍。
A、0.5
B、1
C、2
D、4
6、在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的（ ）。
A、先根遍历
B、中根遍历
C、后根遍历
D、按层次遍历
7、判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用（ ）。
A、求关键路径的方法
B、求最短路径的Dijkstra方法
C、广度优先遍历方法
D、深度优先遍历方法
8、设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。
A、5
B、6
C、7
D、8
9、n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（ ）个非零元素。
A、n
B、2(n-1)
C、n-1
D、n+1
10、无向图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开始进行深度优先遍历，得到的顶点序列正确的是（ ）。
A、a, b，e，c，d, f
B、a, c, f, e，b, d
C、a, e，b, c，f，d
D、a, e，d，f, c, b
11、用Prim算法和Kruskal算法构造图的最小生成树，所得到的最小生成树（ ）。
A、相同
B、不相同
C、可能相同，可能不同
D、无法比较
12、邻接多重表是（ ）的存储结构。
A、无向图
B、有向图
C、无向图和有向图
D、都不是
13、十字链表是（ ）的存储结构。
A、无向图
B、有向图
C、无向图和有向图
D、都不是
14、若邻接表中有奇数个边结点，则一定是（ ）。
A、图中有奇数个结点
B、图中有偶数个结点
C、图为无向图
D、图为有向图
15、在含有 n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ ）。
A、e
B、2e
C、n^2-e
D、n^2-2e
16、若图的邻接矩阵中主对角线上的元素皆为0，其余元素全为1，可以断定该图一定（ ）。
A、是无向图
B、是有向图
C、是完全图
D、不是带权图
17、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为( )。
A、O(n)
B、O(e)
C、O(n+e)
D、O(n的平方)
18、一个图中有n个顶点且包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用( )次深度优先遍历算法。
A、k
B、1
C、n-k
D、n
19、已知有向图G=(V,E)，其中V={ V1,V2,V3,V4,V5,V6,V7}，E={ <V1,V2>, <V1,V3>, <V1,V4>, <V2,V5>, <V3,V5>, <V3,V6>, <V4,V6>, <V5,V7>, <V6,V7>}，则G的拓扑序列是( )。
A、V1,V3,V4,V6,V2,V5,V7
B、V1,V3,V2,V6,V4,V5,V7
C、V1,V3,V4,V5,V2,V6,V7
D、V1,V2,V5,V3,V4,V6,V7
20、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是___。
A、G中有弧<Vi，Vj>
B、G中有一条从Vi到Vj的路径
C、G中没有弧<Vi,Vj>
D、G 中有一条从Vj到Vi的路径
21、关键路径是AOE网中( )。
A、从源点到汇点(即完成点)的最长路径
B、从源点到汇点的最短路径
C、最长回路
D、最短回路
22、n个顶点的无向图的邻接表最多有( )个边结点。
A、n的平方
B、n(n-1)
C、n(n+1)
D、n(n-1)/2
23、对邻接表的叙述中, ( )是正确的。
A、无向图的邻接表中，第i个顶点的度为第i个链表中边结点数的两倍
B、邻接表比邻接矩阵的操作更简便
C、邻接矩阵比邻接表的操作更简便
D、求有向图中结点的度必须遍历整个邻接表
24、无向图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、acfdeb
B、aebdfc
C、aedfcb
D、abecdf
25、图的广度优先生成树的树高比深度优先生成树的树高( )。
A、小或等于
B、小
C、大或相等
D、大
实验7图
1、每题20分，共100分。
学习通数据结构_15
数据结构是计算机科学的核心知识之一。在计算机科学中，数据结构是一种组织和存储数据的方式，以便于访问和修改。学习数据结构是每一个计算机科学学生必备的知识。在这篇文章中，我将介绍学习通数据结构_15的相关知识。
堆和堆排序
堆是一种数据结构，它是一种被完全二叉树所表示的数据结构。堆分为最小堆和最大堆。最小堆是指堆中的每个节点都比它的子节点小，而最大堆是指堆中的每个节点都比它的子节点大。
堆排序是一种排序算法，它使用堆数据结构来排序。堆排序的基本思路是先将要排序的元素构建成一个堆，然后依次将堆中的最大或最小元素取出，放在堆的末尾，再将堆的大小减一，直到堆中只剩下一个元素，这样就完成了堆排序。
平衡树
平衡树是一种特殊的二叉树，它的左子树和右子树的高度差不超过一。平衡树常用于数据存储结构中，可以快速地插入、删除和查找数据。常见的平衡树包括红黑树、AVL树等。
哈希表
哈希表是一种根据关键字直接进行访问的数据结构。哈希表通常使用数组和散列函数来实现，通过散列函数将关键字映射为数组的下标，然后将数据存储在数组中。哈希表的优点是可以快速地进行查找和修改数据，但是它也存在一些问题，如哈希冲突等。
总结
学习通数据结构_15主要介绍了堆和堆排序、平衡树和哈希表等相关知识。这些知识在计算机科学中都非常重要，对于提高程序性能和优化算法都有很大的作用。学习数据结构需要不断地实践和理解，只有掌握了数据结构的基本原理和应用，才能够在计算机科学领域中取得更好的成就。
