电子科大13秋《数据结构》在线作业答案
电子科大《数据结构》13秋在线作业1试卷总分：100 测试时间：--
一、单选题（共16道试题，共48分。）
1.在数据结构中，数据的逻辑结构可以分成（ ）。
A. 内部结构和外部结构
B. 线性结构和非线性结构
C. 紧凑结构和非紧揍结构
D. 动态结构和静态结构
满分：3分
2.设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（ ）。
A. 15
B. 16
C. 17
D. 18
满分：3分
3.高度为5的完全二叉树中含有的结点数至少为（ ）。
A. 16
B. 17
C. 31
D. 32
满分：3分
4.判断两个串大小的基本准则是（ ）。
A. 两个串长度的大小
B. 两个串中首字符的大小
C. 两个串中大写字母的多少
D. 对应的第一个不等字符的大小
满分：3分
5.在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ ）。
A. 数据元素的相邻地址表示
B. 数据元素在表中的序号表示
C. 指向后继元素的指针表示
D. 数据元素的值表示
满分：3分
6.逻辑上通常可以将数据结构分为（ ）。
A. 动态结构和静态结构
B. 顺序结构和链式结构
C. 线性结构和非线性结构
D. 初等结构和组合结构
满分：3分
7.散列文件也称为（ ）。
A. 顺序文件
B. 索引文件
C. 直接存取文件
D. 间接存取文件
满分：3分
8.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需（ ）。
A. 前移一个位置
B. 后移一个位置
C. 不动
D. 视情况而定
满分：3分
9.栈和队列都是（ ）。
A. 限制存取位置的线性结构
B. 顺序存储的线性结构
C. 链式存储的线性结构
D. 限制存取位置的非线性结构
满分：3分
10.已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（ ）。
A. 7
B. 8
C. 9
D. 10
满分：3分
11.无向图中一个顶点的度是指图中（ ）。
A. 通过该顶点的简单路径数
B. 与该顶点相邻接的顶点数
C. 通过该顶点的回路数
D. 与该顶点连通的顶点数
满分：3分
12.栈是一种操作受限的线性结构，其操作的主要特征是（ ）。
A. 先进先出
B. 后进先出
C. 进优于出
D. 出优于进
满分：3分
13.采用两类不同存储结构的字符串可分别简称为（ ）。
A. 主串和子串
B. 顺序串和链串
C. 目标串和模式串
D. 变量串和常量串
满分：3分
14.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ ）。
A. 顺序表
B. 用头指针表示的单循环链表
C. 用尾指针表示的单循环链表
D. 单链表
满分：3分
15.与线性表相比，串的插入和删除操作的特点是（ ）。
A. 通常以串整体作为操作对象
B. 需要更多的辅助空间
C. 算法的时间复杂度较高
D. 涉及移动的元素更多
满分：3分
16.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（ ）。
A. q->next=s->next；s->next=p
B. s->next=p；q->next=s->next
C. p->next=s->next；s->next=q
D. s->next=q；p->next=s->next
满分：3分
二、多选题（共2道试题，共8分。）
1.由于排序过程中涉及的存储器不同，可以将排序方法分为（ ）。
A. 稳定排序
B. 不稳定排序
C. 内部排序
D. 外部排序
满分：4分
2.构造最小生成树的两个基本算法是（ ）。
A. 普里姆算法
B. 克鲁斯卡尔算法
C. 迪杰斯特拉算法
D. 哈希算法
满分：4分
三、判断题（共22道试题，共44分。）
1.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。
A. 错误
B. 正确
满分：2分
2.假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。
A. 错误
B. 正确
满分：2分
3.在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。
A. 错误
B. 正确
满分：2分
4.数据的逻辑结构在计算机存储器内的表示，称为数据的逻辑结构。
A. 错误
B. 正确
满分：2分
5.二叉树中结点只有一个孩子时无左右之分。
A. 错误
B. 正确
满分：2分
6.若一棵满三叉树中含有121个结点，则该树的深度为6。
A. 错误
B. 正确
满分：2分
7.在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为 O(n)。
A. 错误
B. 正确
满分：2分
8.二叉树中必有度为2的结点。
A. 错误
B. 正确
满分：2分
9.当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的时间复杂度。
A. 错误
B. 正确
满分：2分
10.假设以行优先顺序存储三维数组A，其中元素A的地址为1100，且每个元素占2个存储单元，则A的地址是1264。
A. 错误
B. 正确
满分：2分
11.抽象数据类型是指数据逻辑结构及与之相关的操作。
A. 错误
B. 正确
满分：2分
12.假设三维数组A按行优先顺序存储，若每个元素占3个存储单元，并且首地址为100，则元素A的存储地址是501。
A. 错误
B. 正确
满分：2分
13.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。
A. 错误
B. 正确
满分：2分
14.深度为k的二叉树至多有2k-1个结点。
A. 错误
B. 正确
满分：2分
15.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为k。
A. 错误
B. 正确
满分：2分
16.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。
A. 错误
B. 正确
满分：2分
17.深度为15的满二叉树上，第11层有2^11个结点。
A. 错误
B. 正确
满分：2分
18.二叉树中的叶子结点就是二叉树中没有左右子树的结点。
A. 错误
B. 正确
满分：2分
19.假设为循环队列分配的向量空间为Q，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为15。
A. 错误
B. 正确
满分：2分
20.在有向图中，以顶点v为终点的边的数目称为v的入度。
A. 错误
B. 正确
满分：2分
21.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为 O(n)。
A. 错误
B. 正确
满分：2分
22.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是基数排序。
A. 错误
B. 正确
电子科大《数据结构》13秋在线作业2试卷总分：100 测试时间：--一、单选题（共16道试题，共48分。）1.对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（ ）。A. 求一个顶点的邻接点B. 求一个顶点的度C. 深度优先遍历D. 广度优先遍历满分：3分2.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（ ）。A. 10B. 11C. 12D. 不确定的满分：3分3.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需（ ）。A. 前移一个位置B. 后移一个位置C. 不动D. 视情况而定满分：3分4.无向图中一个顶点的度是指图中（ ）。A. 通过该顶点的简单路径数B. 与该顶点相邻接的顶点数C. 通过该顶点的回路数D. 与该顶点连通的顶点数满分：3分5.队和栈的主要区别是（ ）。A. 逻辑结构不同B. 存储结构不同C. 所包含的运算个数不同D. 限定插入和删除的位置不同满分：3分6.在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。A. 插入B. 删除C. 排序D. 定位满分：3分7.执行下列程序段后，串X的值为（ ）。 S=〞abcdefgh〞; T=〞xyzw〞; substr (X,S,2,strlen(T)); substr (Y,S, stelen(T),2); strcat (X,Y);A. 〞cdefgh〞B. 〞cdxyzw〞C. 〞cdefxy〞D. 〞cdefef〞满分：3分8.已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（ ）。A. 7B. 8C. 9D. 10满分：3分9.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为（ ）。A. 4B. 5C. 6#7满分：3分10.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（ ）。A. q->next=s->next；s->next=pB. s->next=p；q->next=s->nextC. p->next=s->next；s->next=qD. s->next=q；p->next=s->next满分：3分11.栈是一种操作受限的线性结构，其操作的主要特征是（ ）。A. 先进先出B. 后进先出C. 进优于出D. 出优于进满分：3分12.在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ ）。A. 数据元素的相邻地址表示B. 数据元素在表中的序号表示C. 指向后继元素的指针表示D. 数据元素的值表示满分：3分13.计算机识别、存储和加工处理的对象被统称为（ ）。A. 数据B. 数据元素C. 数据结构D. 数据类型满分：3分14.抽象数据类型的三个组成部分分别为（ ）。A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型满分：3分15.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为（ ）。A. n-i+1B. n-iC. iD. i-1满分：3分16.n个顶点的有向完全图中含有向边的数目最多为（ ）。A. n-1B. nC. n(n-1)/2D. n(n-1)满分：3分二、多选题（共2道试题，共8分。）1.数据的逻辑结构通常包括（ ）。A. 集合B. 线性C. 树D. 图满分：4分2.算法以下几种特性（ ）。A. 有穷性B. 确定性C. 可行性D. 输入和输出满分：4分三、判断题（共22道试题，共44分。）1.在对链队列作出队操作时，不会改变front指针的值。A. 错误B. 正确满分：2分2.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。A. 错误B. 正确满分：2分3.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为 O(n)。A. 错误B. 正确满分：2分4.二叉树中必有度为2的结点。A. 错误B. 正确满分：2分5.队列的修改是按先进先出的原则进行的。A. 错误B. 正确满分：2分6.产生冲突现象的两个关键字称为该散列函数的同义字。A. 错误B. 正确满分：2分7.在含100个结点的完全二叉树中，叶子结点的个数为36。A. 错误B. 正确满分：2分8.数据的逻辑结构在计算机存储器内的表示，称为数据的逻辑结构。A. 错误B. 正确满分：2分9.在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的定位操作。A. 错误B. 正确满分：2分10.假设三维数组A按行优先顺序存储，若每个元素占3个存储单元，并且首地址为100，则元素A的存储地址是501。A. 错误B. 正确满分：2分11.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 a b b c c d d e d c 。A. 错误B. 正确满分：2分12.两个串相等的充分必要条件是两个串的长度相等且字母相同。A. 错误B. 正确满分：2分13.抽象数据类型是指数据逻辑结构及与之相关的操作。A. 错误B. 正确满分：2分14.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。A. 错误B. 正确满分：2分15.若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为2/6。A. 错误B. 正确满分：2分16.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为k。A. 错误B. 正确满分：2分17.结点数为20的二叉树可能的最大高度为4。A. 错误B. 正确满分：2分18.串S=”I am a worker″的长度是10。A. 错误B. 正确满分：2分19.空格串的长度是空格的个数。A. 错误B. 正确满分：2分20.在无向图中，若从顶点a到顶点b存在通路，则称a与b之间是连通的。A. 错误B. 正确满分：2分21.一个具有4个顶点的无向完全图有6条边。A. 错误B. 正确满分：2分22.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序。A. 错误B. 正确电子科大《数据结构》13秋在线作业3试卷总分：100 测试时间：--一、单选题（共16道试题，共48分。）1.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（ ）。A. q->next=s->next；s->next=pB. s->next=p；q->next=s->nextC. p->next=s->next；s->next=qD. s->next=q；p->next=s->next满分：3分2.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为（ ）。A. 4B. 5C. 6#7满分：3分3.下面程序段的时间复杂度是（ ）。 for(i=0;i<n;i++) for(j=1;j<m;j++) A=0；A. O(n)B. O(m+n+1)C. O(m+n)D. O(m*n)满分：3分4.一棵含18个结点的二叉树的高度至少为（ ）。A. 3B. 4C. 5D. 6满分：3分5.在计算机内实现递归算法时所需的辅助数据结构是（ ）。A. 栈B. 队列C. 树D. 图满分：3分6.高度为5的完全二叉树中含有的结点数至少为（ ）。A. 16B. 17C. 31D. 32满分：3分7.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head,则（ ）。A. p指向头结点B. p指向尾结点C. *p的直接后继是头结点D. *P的直接后继是尾结点满分：3分8.执行下列程序段后，串X的值为（ ）。 S=〞abcdefgh〞; T=〞xyzw〞; substr (X,S,2,strlen(T)); substr (Y,S, stelen(T),2); strcat (X,Y);A. 〞cdefgh〞B. 〞cdxyzw〞C. 〞cdefxy〞D. 〞cdefef〞满分：3分9.无向图中一个顶点的度是指图中（ ）。A. 通过该顶点的简单路径数B. 与该顶点相邻接的顶点数C. 通过该顶点的回路数D. 与该顶点连通的顶点数满分：3分10.已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（ ）。A. 7B. 8C. 9D. 10满分：3分11.通常将链串的结点大小设置为大于1是为了（ ）。A. 提高串匹配效率B. 提高存储密度C. 便于插入操作D. 便于删除操作满分：3分12.与线性表相比，串的插入和删除操作的特点是（ ）。A. 通常以串整体作为操作对象B. 需要更多的辅助空间C. 算法的时间复杂度较高D. 涉及移动的元素更多满分：3分13.下面程序段的时间复杂度为（ ）。 for (i=0; i<m; i++) for (j=0; j<n; j++) A=i*j;A. O (m2)B. O (n2)C. O (m*n)D. O (m+n)满分：3分14.二叉树中第5层上的结点个数最多为（ ）。A. 8B. 15C. 16D. 32满分：3分15.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（ ）。A. 10B. 11C. 12D. 不确定的满分：3分16.逻辑上通常可以将数据结构分为（ ）。A. 动态结构和静态结构B. 顺序结构和链式结构C. 线性结构和非线性结构D. 初等结构和组合结构满分：3分二、多选题（共2道试题，共8分。）1.一个好的算法有（ ）设计要求。A. 正确性B. 可读性C. 健壮性D. 效率与低存储量要求满分：4分2.由于排序过程中涉及的存储器不同，可以将排序方法分为（ ）。A. 稳定排序B. 不稳定排序C. 内部排序D. 外部排序满分：4分三、判断题（共22道试题，共44分。）1.在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的定位操作。A. 错误B. 正确满分：2分2.假设三维数组A按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A的存储地址是501。A. 错误B. 正确满分：2分3.有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。A. 错误B. 正确满分：2分4.如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为47。A. 错误B. 正确满分：2分5.深度为15的满二叉树上，第11层有2^11个结点。A. 错误B. 正确满分：2分6.一棵含999个结点的完全二叉树的深度为6。A. 错误B. 正确满分：2分7.两个串相等的充分必要条件是两个串的长度相等且字母相同。A. 错误B. 正确满分：2分8.在无向图中，若从顶点a到顶点b存在通路，则称a与b之间是连通的。A. 错误B. 正确满分：2分9.设S1="good",S2=" ",S3="book"，则S1，S2和S3依次联接后的结果是”good book” 。A. 错误B. 正确满分：2分10.在有向图中，以顶点v为终点的边的数目称为v的入度。A. 错误B. 正确满分：2分11.二叉树是度为2的有序树。A. 错误B. 正确满分：2分12.当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的时间复杂度。A. 错误B. 正确满分：2分13.一个具有4个顶点的无向完全图有6条边。A. 错误B. 正确满分：2分14.在含100个结点的完全二叉树中，叶子结点的个数为36。A. 错误B. 正确满分：2分15.数据的逻辑结构描述数据元素之间的逻辑关系，与存储方式无关。A. 错误B. 正确满分：2分16.数据的逻辑结构在计算机存储器内的表示，称为数据的逻辑结构。A. 错误B. 正确满分：2分17.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是基数排序。A. 错误B. 正确满分：2分18.在一个长度为100的顺序表中删除第10个元素时，需移动90个元素。A. 错误B. 正确满分：2分19.一棵含999个结点的完全二叉树的深度为12。A. 错误B. 正确满分：2分20.在二叉树的第i层上至多可以有2i个结点。A. 错误B. 正确满分：2分21.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。A. 错误B. 正确满分：2分22.已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是p->next->next==null。A. 错误B. 正确满分：2分
页:
[1]