电子科大15春 数据结构 在线作业123与答案.docx
《电子科大15春 数据结构 在线作业123与答案.docx》由会员分享，可在线阅读，更多相关《电子科大15春 数据结构 在线作业123与答案.docx（13页珍藏版）》请在冰点文库上搜索。
电子科大15春数据结构在线作业123与答案
电子科大15春数据结构在线作业123与答案----29a1c158-7162-11ec-b5c4-7cb59b590d7d
电子科大15春数据结构在线作业123与答案
电子科技大学，第十五春季和LBRACK；数据结构&rsqb；在线作业123和答案
在线作业一：
一、单选题（共16道试题，共48分。
）
1.已知指针P和Q分别指向单个链表中的第一个节点和最后一个节点。
假设指针s指向另一个单链表中的节点，则在s引用的节点之后插入上述链表时要执行的语句为（）。
a.q->next=s->next；s->next=pb.s->next=p；q->next=s->next
c、p->next=s->next；s->next=qd。
s->next=q；p->next=s->next
2.高度为5的完全二叉树中含有的结点数至少为（）。
a、16b。
17c。
31d。
32
3.设有两个串t和p，求p在t中首次出现的位置的串运算称作（）。
a、连接B.子字符串C.字符定位D.子字符串定位
正确答案：
d
4.对于哈希函数H（key）=key%13，名为synonym的关键字是（）。
a.35和41b.23和39
c、15和44d25和51
5.算法分析的目的是（）。
a、确定数据结构的合理性B.评估算法的效率
c.研究算法中输入与输出的关系d.鉴别算法的可读性
6.在头指针和表长度大于1的单循环链表中，指针P指向表中的一个节点。
如果
p->next->next=head,则（）。
a、P指头部节点，B.P指尾部节点
c.*p的直接后继是头结点d.*p的直接后继是尾结点
7.数据结构为（）
a.一种数据类型b.数据的存储结构c.一组性质相同的数据元素的集合
d、相互之间有一个或多个特定关系的数据元素的集合
8.采用两类不同存储结构的字符串可分别简称为（）。
a、主字符串和子字符串B.序列字符串和链字符串C.目标字符串和模式字符串D.变量字符串和常量字符串正确答案：
B
9.已知函数sub（s,i,j）的功能是返回串s中从第i个字符起长度为j的子串，函数scopy（s,t）的功能为复制串t到s。
若字符串s=″sciencestudy″，则调用函数scopy（p,sub（s,1,7））后得到（）。
a、p=科学b.p=研究
c.s=″science″d.s=″study″
10.在头指针和表长度大于1的单循环链表中，指针P指向表中的一个节点。
如果
p->next->next=head,则（）。
a、P指头部节点，B.P指尾部节点
c.*p的直接后继是头结点d.*p的直接后继是尾结点
11.如果一棵二叉树有11个叶节点，则二叉树中有2个节点的节点数为（）。
a.10b.11
c、12天。
模棱两可的
12.下面程序段的时间复杂度是（）。
for（i=0;i
a、o（n）b.o（m+n+1）c.o（m+n）d.o（m*n）
13.在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）。
a、插入B.删除
c.排序d.定位
正确答案：
D
14.在计算机内实现递归算法时所需的辅助数据结构是（）。
a、堆栈B.队列
c.树d.图
15.在以单链表作为存储结构的线性表中，数据元素之间的逻辑关系由（）表示。
a.数据元素的相邻地址表示b.数据元素在表中的序号表示
c、指向后续元素的指针表示D。
数据元素的值表示
正确答案：
c
16.对于只在表的开头和结尾插入的线性表，适当的存储结构是（）。
a.顺序表b.用头指针表示的单循环链表
c、由尾部指针D表示的单循环链表。
单循环链表
二、多选题（共2道试题，共8分。
）
1.该算法具有以下特点（）。
a.有穷性b.确定性c.可行性d.输入和输出
正确答案：
ABCD
2.一个好的算法有（abcd）设计要求。
a、正确性B.可读性
c.健壮性d.效率与低存储量要求
正确答案：
ABCD
三、判断题（共22道试题，共44分。
）
1.二叉树中的叶节点是二叉树中没有左右子树的节点。
a、错误B.正确
2.在队列中，允许进行删除操作的一端称为队尾。
a.错误b.正确
正确答案：
B
3.假设以s和x分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作ssxsxssxxx之后，得到的输出序列为abbccddedc。
a、错误B.正确
4.空串的长度是0a.错误b.正确
5.计算机内存中数据逻辑结构的表示称为数据逻辑结构。
a、错误B.正确
正确答案：
a
6.在深度为15的完整二叉树上，第11层有2^11个节点。
a.错误b.正确
7.如果输入顺序为1、3、5，。
。
。
，97、99，输出序列的第一个元素是99，输出序列的第30个元素是47。
a、错误B.正确
8.字符串“sgabacbadfgbacst”中存在有6个与字符串“ba”相同的子串a.错误b.正确正确答案：
a
9.假设三维数组a[5][6][7]按行优先级顺序存储，其中元素a[0][0][0]的地址为1100，每个元素占用2个存储单元，则a[4][3][2]的地址为1264。
a、错误B.正确
10.当问题的规模n趋向无穷大时，算法执行时间t（n）的数量级被称为算法的时间复杂度。
a、错误B.正确
11.一棵含999个结点的完全二叉树的深度为12a.错误b.正确
12.在队列中，允许插入的一端称为队列头。
a.错误b.正确
13.如果一棵完整的三叉戟树包含121个节点，则树的深度为6。
a、错误B.正确
正确答案：
a
14.导致冲突的两个关键字称为哈希函数的同义词。
a、错误B.正确
15.在二叉树的第i层上至多可以有2i个结点。
a.错误b.正确
16.给定不同的输入序列来构建二叉排序树，我们必须得到不同的二叉排序树。
a、正确答案：
a
17.已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是p->next->next==null。
a.错误b.正确
18.如果堆栈进入顺序为a、B和C，并且堆栈进入和堆栈退出可以穿插，则可能有6个不同的堆栈退出顺序。
。
a.错误b.正确
19.在长度为N的循环链表中，删除元素值为x的节点的时间复杂度为O（N）。
a.错误b.正确
20.在最好和最坏的情况下，时间复杂度为O（nlogn），稳定的排序方法是堆排序。
a.错误b.正确
正确答案：
a
21.二叉树中最多只有两棵子树，并且有左右之分。
a.错误b.正确
正确答案：
B
22.不含任何字符的串称为空串。
a.错误b.正确
网上作业2:
1。
单选题（共16题，共48分）
1.高度为5的完全二叉树中含有的结点数至少为（）。
a、16b。
17c。
31d。
32
二.二叉树中第5层上的结点个数最多为（）。
a、8b。
15摄氏度。
16天。
32
3.在一个具有n个顶点的有向图中，所有顶点的出度之和为dout，则所有顶点的入度之和为（）。
a、杜特布。
dout-1c。
dout+1d。
N
4.在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）。
a、数据元素的相邻地址表示B.表中数据元素的序列号表示
c.指向后继元素的指针表示d.数据元素的值表示
5.已知堆栈的最大容量为4。
如果堆栈进入顺序是1、2、3、4、5和6，并且堆栈进入和堆栈退出可以穿插，那么可能的堆栈退出顺序是（）。
a.5，4，3，2，1，6b.2，3，5，6，1，4
c、3,2,5,4,1,6d。
1，4，6，5，2，3
6.若算法中语句的最大频度为t（n）=2021n+6n㏒n+29㏒2n,则其时间复杂度为（）。
a、o（㏒n）b.o（n）c.o（n）㏒n）d.o（㏒2n）
7.下面程序段的时间复杂度为（）。
for（i=0;i
a、o（m2）b.o（n2）c.o（m*n）d.o（m+n）
8.采用两类不同存储结构的字符串可分别简称为（）。
a、主字符串和子字符串B.序列字符串和链字符串C.目标字符串和模式字符串D.变量字符串和常量字符串正确答案：
B
9.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。
a、序列表B.由标题指针表示的单循环链表
c.用尾指针表示的单循环链表d.单链表
10.具有18个节点的二叉树的高度应至少为（）。
a.3b.4c.5d.6
11.判断两个字符串大小的基本标准是（）。
a.两个串长度的大小b.两个串中首字符的大小
c、两个字符串中的大写字母数D.对应于
12.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）。
a、0b。
1c。
48d。
49
13.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若
P->next->next=头部，然后（）。
a.p指向头结点b.p指向尾结点
c、*P的直接后继节点是头节点，*P的直接后继节点是尾节点
14.与线性表相比，串的插入和删除操作的特点是（）。
a、通常，整个字符串用作操作对象。
B.需要更多的辅助空间
c.算法的时间复杂度较高d.涉及移动的元素更多
15.抽象数据类型的三个组件是（）。
a.数据对象、数据关系和基本操作b.数据元素、逻辑结构和存储结构
c、数据项、数据元素和数据类型D.数据元素、数据结构和数据类型
16.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）。
a、3,2,6,1,4,5b。
3，4，2，1，6，5
c.1，2，5，3，4，6d.5，6，4，2，3，1
二、多项选择题（共2题，共8分）
1.构造最小生成树的两个基本算法是（）。
a、Prim算法B.kruskar算法C.dijestra算法D.哈希算法
正确答案：
ab
2.由于排序过程涉及的内存不同，排序方法可分为（）。
a.稳定排序b.不稳定排序
c、内部排序D.外部排序
正确答案：
cd
三、判断题（共22题，总分44分）
1.含n个顶点的无向连通图中至少含有n条边。
a.错误b.正确
2.包含999个节点的完整二叉树的深度为6。
a、错误B.正确
3.在最好和最坏情况下的时间复杂度均为o（nlogn）且稳定的排序方法是基数排序。
a、错误B.正确
4.在含100个结点的完全二叉树中，叶子结点的个数为36。
a.错误b.正确
5.二叉树中的叶节点是二叉树中没有左右子树的节点。
a、错误B.正确
6.设s1="good"s2=""s3="book"，则s1，s2和s3依次联接后的结果是”goodbook”。
a、错误B.正确
7.假设以行优先顺序存储三维数组a[5][6][7]，其中元素a[0][0][0]的地址为1100，并且每个元素占2个存储单元，则a[4][3][2]的地址是1264。
a.错误b.正确
8.如果堆栈序列是1,3,5，。
。
。
，97，99，堆栈序列的第一个元素是99，堆栈序列的第30个元素是47。
a、错误B.正确
9.二叉树是度为2的有序树。
a.错误b.正确
10.队列的尾部位置通常随队列加入操作而变化。
a、错误B.正确
11.串s=”iamaworker″的长度是10。
a.错误b.正确
12.在文本编辑程序中找到特定单词在文本中的位置，可以使用字符串的定位操作。
a.错误b.正确
13.根据先进先出的原则修改队列。
a、错误B.正确
14.两个串相等的充分必要条件是两个串的长度相等且字母相同。
a.错误b.正确正确答案：
b
15.堆栈下溢指堆栈为空时的堆栈外操作。
A.错误B.正确
16.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。
a.错误b.正确正确答案：
a
17.如果链节点中的指针占4字节，每个字符占1字节，则节点大小为2的链的存储密度为2/6。
a、错误B.正确
18.一个具有4个顶点的无向完全图有6条边。
a.错误b.正确
19.数据的逻辑结构描述了数据元素之间的逻辑关系，与存储模式无关。
a、正确答案：
B
20.产生冲突现象的两个关键字称为该散列函数的同义字。
a.错误b.正确
21.如果已知指针P指向单个链表中的节点，则判断该节点有且只有一个后续节点的条件是P->next->next==null。
a、错误B.正确
22.假设三维数组a[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，并且首地址为100，则元素a[9][8][7]的存储地址是501。
a.错误b.正确
在线作业3:
1。
单选题（共16题，共48分）
1.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head,则（）。
a、P指头部节点，B.P指尾部节点
c.*p的直接后继是头结点d.*p的直接后继是尾结点
2.已知指针P和Q分别指向单个链表中的第一个节点和最后一个节点。
假设指针s指向另一个单链表中的节点，则在s引用的节点之后插入上述链表时要执行的语句为（）。
a.q->next=s->next；s->next=pb.s->next=p；q->next=s->next
c、p->next=s->next；s->next=qd。
s->next=q；p->next=s->next
3.对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（）。
a、求顶点的邻接点B.求顶点的阶C.深度优先遍历D.宽度优先遍历
4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）。
a、3,2,6,1,4,5b。
3，4，2，1，6，5
c.1，2，5，3，4，6d.5，6，4，2，3，1
5.以下程序段的时间复杂度为（）。
对于（i=0；i
a.o（m2）b.o（n2）c.o（m*n）d.o（m+n）
6.执行以下程序段后，字符串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〞
7.二叉树第5层上的最大节点数为（）。
a.8b.15c.16d.32
8.已知一棵有50个节点的二叉树中只有一个叶节点，那么树中有1个节点的节点数为（）。
a.0b.1c.48d.49
9.team和stack之间的主要区别是（）。
a.逻辑结构不同b.存储结构不同
c、包含的操作数量不同。
D.限制插入和删除的位置不同
10.判断两个串大小的基本准则是（）。
a、两个字符串长度的大小B.两个字符串中第一个字符的大小
c.两个串中大写字母的多少d.对应的第一个不等字符的大小
11.在有n个顶点的有向图中，如果所有顶点的向外度之和为dout，则所有顶点的向内度之和为（）。
a.doutb.dout-1c.dout+1d.n
12.如果数据结构中的每个数据元素只能有一个直接前驱体，但可以有多个直接后继体，则结构为（）。
a.栈b.队列c.树d.图
13.从序列表中删除元素时，表中删除元素后的所有元素必须为（）。
a.前移一个位置b.后移一个位置c.不动d.视情况而定
14.与线性表相比，字符串插入和删除的特点是（）。
a.通常以串整体作为操作对象b.需要更多的辅助空间
c、该算法的时间复杂度较高，涉及的运动元素较多
15.若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（）。
a、无头节点的双向链表B.带尾指针的循环链表
c.无头结点的单链表d.带头指针的循环链表
16.已知一棵完整的二叉树有64个叶节点，那么树的最大可能深度是（）。
a.7b.8c.9d.10
二、多项选择题（共2题，共8分）
一.一个好的算法有（）设计要求。
a、正确性B.可读性C.健壮性D.效率和低存储要求
正确答案：
abcd
2.由于排序过程涉及的内存不同，排序方法可分为（）。
a.稳定排序b.不稳定排序c.内部排序d.外部排序
正确答案：
CD
三、判断题（共22道试题，共44分。
）
1.给不同的输入序列建立一个二叉排序树，你会得到不同的二叉排序树。
a、正确答案：
a
2.有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。
a、错误B.正确
3.抽象数据类型是指数据逻辑结构及与之相关的操作。
a.错误b.正确
4.包含999个节点的完整二叉树的深度为12。
a、错误B.正确
5.在一个长度为100的顺序表中删除第10个元素时，需移动90个元素。
a、错误B.正确
6.字符串“sgabacbadfgbacst”中存在有6个与字符串“ba”相同的子串.a.错误b.正确正确答案：
a
7.如果链节点中的指针占4字节，每个字符占1字节，则节点大小为2的链的存储密度为2/6。
a、错误B.正确
8.二叉树中必有度为2的结点。
a.错误b.正确
9.根据先进先出的原则修改队列。
a、错误B.正确
10.在二叉树的第i层上至多可以有2i个结点。
a.错误b.正确
11.假设三维数组a[5][6][7]按行优先级顺序存储，其中元素a[0][0][0]的地址为1100，每个元素占2个存储单元，则元素a[4][3][2]的地址为1264。
a、错误B.正确
12.产生冲突现象的两个关键字称为该散列函数的同义字。
a.错误b.正确
13.如果输入序列为1、3、5、97、99，且输出序列的第一个元素为99，则输出序列的第30个元素为47。
a、错误B.正确
14.当问题的规模n趋向无穷大时，算法执行时间t（n）的数量级被称为算法的时间复杂度。
a、错误B.正确
15.一棵树可以只有1个结点。
a.错误b.正确
16.字符串s=“iamaworker”的长度为10。
a、错误B.正确
17.假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。
a、错误B.正确
18.二叉树中的叶子结点就是二叉树中没有左右子树的结点。
a.错误b.正确
19.假设为循环队列分配的向量空间为Q[20]，如果队列长度和队列头指针的值分别为13和17，则当前尾部指针的值为15。
a、错误B.正确
20.在队列中，允许进行删除操作的一端称为队尾。
a.错误b.正确
21.包含999个节点的完整二叉树的深度为6。
a、错误B.正确
22.设s1="good"s2=""s3="book"，则s1，s2和s3依次联接后的结果是”goodbook”。
a、错误B.正确
升级会员 