大工20春《数据结构》在线作业1答卷

大连理工大学网络教育学院2020年春《数据结构》期末考试复习题☆注意事项：本复习题满分共：200分。

一、单项选择题1、在队列中存取数据的原则是（）。

A．先进先出B．后进先出C．先进后出D．随意进出2、在下列链表中，不能从当前结点出发访问到其余各结点的是（）。

A．单链表B．单循环链表C．双向链表D．双向循环链表3、在一棵二叉树上第5层的结点数最多为（）设树根为第1层。

A．16 B．15 C．8 D．324、一棵有124叶子结点的完全二叉树，最多有（）个结点。

A．247 B．249 C．248 D．1255、具有10个叶子结点的二叉树中有（）个度为2的结点。

A．8 B．9 C．10 D．116、若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（）。

A．gdbehfca B．bdgaechfC．gdbecfha D．gcefhabd7、对线性表进行顺序查找时，要求线性表的存储结构是（）。

A．倒排表B．索引表C．顺序表或链表D．散列表8、对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用折半查找，则查找元素26的查找长度为（）。

A．2 B．3 C．4 D．59、在所有排序方法中，关键字比较的次数与记录的初始排序次序无关的是（）。

A．希尔排序B．起泡排序C．插入排序D．选择排序10、堆的形状是一棵（）。

A．二叉排序树B．满二叉树C．完全二叉树D．平衡二叉树11、线性表采用顺序存储结构时，其地址（）。

A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以12、在栈中存取数据的原则是（）。

A．先进先出B．后进先出C．后进后出D．随意进出13、插入和删除只能在一端进行的线性表，称为（）。

A．队列B．循环队列C．栈D．数组14、一个基本线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）。

【奥鹏】-[东北师范大学]数据结构20春在线作业1试卷总分:100 得分:100第1题,数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是 ( )A、线性表B、广义表C、树形结构D、图结构正确答案:A第2题,插入、删除只能在同一端进行的线性表，称为 ( )。

A、队列B、循环队列C、栈D、循环栈正确答案:C第3题,任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序 ( )。

A、不发生改变B、发生改变C、稍有改变D、不能确定正确答案:A第4题,在k叉树中，度为0的结点称为 ( )。

A、根B、叶C、祖先D、子孙正确答案:B第5题,在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关 ()。

A、直接插入排序B、冒泡排序C、快速排序D、直接选择排序正确答案:D第6题,下面哪些方法可以判断出一个有向图是否有环（回路）? ()A、广(宽)度优先遍历B、拓扑排序C、求最短路径D、求关键路径正确答案:B第7题,串是一种特殊的线性表，其特殊性体现在 ( )。

A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符正确答案:B第8题,head指向的带表头结点的单链表为空的判定条件是 ( )。

A、head = = NULLB、head-next = = headC、head ! = NULLD、head-next = = NULL正确答案:D第9题,二叉树在线索化后，仍不能有效求解的问题是 ( )。

A、前序线索二叉树中求前序后继B、中序线索二叉树中求中序前驱C、中序线索二叉树中求中序后继D、后序线索二叉树中求后序后继正确答案:D第10题,算法分析的两个主要方面是 ( )。

A、正确性与健壮性B、可读性与可用性C、时间复杂度与空间复杂度D、数据复杂性与程序复杂性正确答案:C第11题,下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。

02272《数据结构》国开形考任务(1-4)试题答案集任务1：数据结构基础1. 数据结构是指数据元素之间的关系和操作的组织方式。

它包括数据的逻辑结构、数据的存储结构以及对数据的操作等内容。

2. 数据结构的逻辑结构包括线性结构、树形结构、图形结构等。

3. 数据结构的存储结构包括顺序存储结构和链式存储结构。

4. 数据结构的操作包括插入、删除、查找、修改等。

5. 数据结构的选择应根据具体应用需求来确定，需要考虑数据的规模、操作的效率、存储空间的利用等因素。

任务2：线性表1. 线性表是一种最基本的数据结构，它包括顺序表和链表两种存储结构。

2. 顺序表是用一段连续的存储空间存储线性表的元素，可以通过下标直接访问元素。

顺序表的插入和删除操作需要移动其他元素，效率较低。

3. 链表是通过节点之间的指针来连接元素的，可以实现灵活的插入和删除操作。

链表的缺点是访问元素需要从头节点开始遍历，效率较低。

4. 单链表是最简单的链表结构，每个节点包含数据和指向下一个节点的指针。

5. 双链表在单链表的基础上增加了一个指向前一个节点的指针，可以实现双向遍历。

任务3：树和二叉树1. 树是一种非线性的数据结构，它包括节点和边组成。

节点之间存在一对多的关系。

2. 二叉树是一种特殊的树结构，每个节点最多有两个子节点。

3. 二叉树的遍历方式包括前序遍历、中序遍历和后序遍历。

4. 前序遍历先访问根节点，然后依次访问左子树和右子树。

5. 中序遍历先访问左子树，然后访问根节点，最后访问右子树。

6. 后序遍历先访问左子树，然后访问右子树，最后访问根节点。

任务4：图的表示和遍历1. 图是一种由节点和边组成的数据结构，节点之间存在多对多的关系。

2. 图的表示方式有邻接矩阵和邻接表两种。

3. 邻接矩阵是一个二维数组，用于表示节点之间的连接关系。

4. 邻接表是由链表构成的数组，每个节点的链表存储与其相邻的节点。

5. 图的遍历方式包括深度优先搜索和广度优先搜索。

大工19秋《数据结构》在线作业1试卷总分:100 得分:100一、单选题(共10 道试题,共50 分)1.线性表采用顺序存储结构时,其地址( )。

A.部分地址必须是连续的B.连续与否均可以C.必须是连续的D.一定是不连续的答案:C2.队列操作的原则是( )。

A.后进先出B.只能插入C.只能删除D.先进先出答案:D3.下述哪一条是顺序存储结构的优点( )。

A.插入运算方便B.存储密度大C.可方便地用于各种逻辑结构的存储表示D.删除运算方便答案:B4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( )存储方式最节省时间。

A.顺序表B.带头结点的双循环链表C.双链表D.单循环链表答案:A5.链表不具有的特点是( )。

A.插入、删除不需要移动元素B.所需空间与线性长度成正比C.可随机访问任一元素D.不必事先估计存储空间答案:C6.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是( )。

A.不确定B.n-i+1C.n-iD.i答案:B7.设有三个元素X,Y,Z顺序进栈(进的过程中允许出栈),下列得不到的出栈排列是( )。

A.ZYXB.ZXYC.YZXD.XYZ答案:B8.一个递归算法必须包括( )。

A.递归部分B.迭代部分C.终止条件和递归部分D.终止条件和迭代部分答案:C9.设计一个判别表达式中左右括号是否配对出现的算法,采用( )数据结构最佳。

A.队列B.线性表的顺序存储结构C.线性表的链式存储结构D.栈答案:D10.对稀疏矩阵进行压缩存储目的是( )。

A.降低运算的时间复杂度B.节省存储空间C.便于进行矩阵运算D.便于输入和输出答案:B二、判断题(共10 道试题,共50 分)11.数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

答案:正确12.算法的有穷性是指一个算法必须总是(对任何合法的输入)在执行有穷步之后结束,且每一步都可在有穷时间内完成。

大工20春《数据库原理》在线作业1 一、单选题共10题，50分15分Access数据库属于()数据库。

我的得分：5分我的答案：C解析：暂无内容25分创建表时可以在()中进行。

我的得分：5分我的答案：C解析：暂无内容35分从关系中找出满足给定条件的操作称为()。

我的得分：5分我的答案：A解析：暂无内容45分DBS是指()。

我的得分：5分我的答案：C解析：暂无内容55分属于SQL中的数据查询的动词的是()。

我的得分：5分我的答案：A解析：暂无内容65分CHECK表示哪个完整性约束()。

我的得分：5分我的答案：D解析：暂无内容75分确定集合这个查询条件的谓词是()。

我的得分：5分我的答案：A解析：暂无内容85分()查询是最常用的连接查询。

我的得分：5分我的答案：A解析：暂无内容95分REVOKE属于SQL语言的()。

我的得分：5分我的答案：D解析：暂无内容105分在SQL查询GROUP BY 语句用于()。

我的得分：5分我的答案：D解析：暂无内容二、判断题共10题，50分15分在文件系统管理数据阶段,数据有内部结构。

我的得分：5分我的答案：A解析：暂无内容25分E-R建模方法是描述信息模型最常用的方法。

我的得分：5分我的答案：A解析：暂无内容35分在数据库中,不应存储任何冗余数据。

我的得分：5分我的答案：B解析：暂无内容45分比较运算符是辅助专门的关系运算符进行操作。

我的得分：5分我的答案：A解析：暂无内容55分如果关系模式R的每一个属性都是不可再分的数据项,则称满足第一范式。

我的得分：5分我的答案：A解析：暂无内容65分DBMS是有数据库的计算机系统的中心管理软件,一般依赖于操作系统。

我的得分：5分我的答案：A解析：暂无内容75分关系模型中实体与实体间的联系用关系来表示。

我的得分：5分我的答案：A解析：暂无内容85分数据删除不属于数据库的数据更新操作。

我的得分：5分我的答案：B解析：暂无内容95分大部分数据库管理系统是将数据库存储在大容量的外部存储器上。

大工18春《数据结构》在线作业11、A2、A3、A4、A5、B一、判断题共10题，50分1、数据的物理结构是数据的逻辑结构在计算机存储器中的实现。

A对B错正确答案是：A2、非线性结构中,至少存在一个元素不止一个直接前驱或不止一个直接后继。

A对B错正确答案是：A3、算法是对解题方法和步骤的描述。

A对B错正确答案是：A4、顺序表必须占用一片地址连续的存储单元。

A对B错正确答案是：A5、链表可以随机存取任一元素。

A对B错正确答案是：B6、顺序表中存取每一个元素的时间不同。

A对B错正确答案是：B7、插入和删除只能在表的一端进行的线性表,称为栈。

A对B错正确答案是：A8、线性表的特点是每个元素都有一个前驱和一个后继。

A对B错正确答案是：B9、链表中的头结点仅起到标识的作用。

A对B错正确答案是：B10、顺序存储方式只能用于线性结构,不能用于非线性结构。

A对B错正确答案是：B二、单选题共10题，50分1、计算机算法必须具备输入、输出、( )等5个特性。

A可行性、可移植性和可扩展性B可行性、确定性和有穷性C确定性、有穷性和稳定性D易读性、安全性和稳定性正确答案是：B2、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( )和运算等的学科。

A结构B关系C运算D算法正确答案是：B3、在数据结构中,从逻辑上可以把数据结构分成( )。

A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构正确答案是：C4、在一个顺序表的表尾插入一个元素的时间复杂度的量级为( )。

AO(n)BO(1)CO(n*n)D以上都不是正确答案是：B5、在下列链表中,不能从当前结点出发访问到其余各结点的是( )。

A单链表B单循环链表C双向链表D双向循环链表正确答案是：A6、栈操作应遵循的原则是( )。

A先进先出B后进先出C随意进出D以上都不是正确答案是：B7、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取出数据打印。

数据结构部分课后习题答案(1-3)第一章1.1数据的逻辑结构是从具体问题中抽象出来的数学模型，体现了事物的组成和事物之间的逻辑关系。

数据的存储结构主要用来解决各种逻辑结构在计算机中物理存储表示的问题。

1.2事前分析和事后统计事前分析：优点，程序不必运行，所得结果只依赖于算法本身缺点，不够精确事后统计：优点，精确缺点，必须运行程序，所得结果依赖于硬件、环境等因素1.3void func(int n){int i=1,k=100;while(i<n){k++;i+=2;}}考虑赋值、运算操作执行的次数第3行赋值2次第6行赋值执行n次，加法执行n次所以，总共2n+2次操作，算法复杂度为O(n)1.4y=y+i*j执行次数：1.5第二章2.9内存中一片连续空间（不妨假设地址从1到m）提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。

答：S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。

2.10线性表是数据项组成的一种有限且有序的序列，各元素之间呈线性关系。

从逻辑结构来说，栈和队列与线性表相同，都是典型的线性结构。

与线性表不同的是，栈和队列的操作特殊，受到一定的限制，仅允许在线性表的一端或两端进行。

栈是限定仅在一端进行插入删除的线性表，无论插入、删除还是读取都在一端进行，按后进先出的原则。

队列的元素只能从一端插入，从另一端删除，按先进先出的原则进行数据的存取。

2.11共有132种合法序列。

235641序列可以。

154623序列不可以。

对于每一个数来说，必须进栈一次、出栈一次。

我们把进栈设为状态‘1’，出栈设为状态‘0’。

n个数的所有状态对应n个1和n个0组成的2n位二进制数。

华东理工大学2020年春季数据结构（本）网上作业1华东理工大学2020年春季数据结构（本）网上作业1一、单选题1.(5分)设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好采用（）排序法。

A.冒泡排序B.快速排序C.堆排序基数排序纠错得分：5收起解析答案C解析2.(5分)具有n个顶点的有向图最多有（）条边。

A.nB.n(n-1)C.n(n+1)D.n2纠错得分：5收起解析答案B解析3.(5分)在数据结构中，从逻辑上可以把数据结构分成（）。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构纠错得分：5收起解析答案C解析4.(5分)设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≤j), 在一维数组B 中下标k的值是：( )。

A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j纠错得分：0收起解析答案A解析5.(5分)设有100个元素，用折半查找法进行查找时，最大比较次数为（）。

A.25B.50C.10D.7纠错得分：5收起解析答案D解析6.(5分)在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。

A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B.在第i个结点后插入一个新结点（1≤i≤n）C.删除第i个结点（1≤i≤n）D.将n个结点从小到大排序纠错得分：5收起解析答案A解析7.(5分)如果二叉树中某结点p->rtag=1，则在对该二叉树按照某种次序进行线索化时，该指针域指向该结点的（）。

A.左孩子B.右孩子C.遍历前驱D.遍历后继纠错得分：5收起解析答案D解析8.(5分)设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第( )次匹配成功。

数据结构期末试卷一、选择题1．组成数据的基本单位是（）。

(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。

(A) 线性结构(B) 树型结构(C) 图型结构(D) 集合3．数组的逻辑结构不同于下列（）的逻辑结构。

(A) 线性表(B) 栈(C) 队列(D) 树4．二叉树中第i(i≥1)层上的结点数最多有（）个。

(A) 2i (B) 2i(C) 2i-1(D) 2i-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。

(A) p->next=p->next->next (B) p=p->next(C) p=p->next->next (D) p->next=p6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。

(A) 6 (B) 4 (C) 3 (D) 27．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。

(A) 100 (B) 40 (C) 55 (D) 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。

(A) 3 (B) 4 (C) 5 (D) 19．根据二叉树的定义可知二叉树共有（）种不同的形态。

(A) 4 (B) 5 (C) 6 (D) 710.设有以下四种排序方法，则（）的空间复杂度最大。

(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。

大工20春《数据结构与算法》在线作业
1(参考资料)
根据您的需求，为您提供一份关于大工20春《数据结构与算法》在线作业1的参考资料。

以下是一些有用的信息和资源，希望能帮助到您完成作业。

作业要求
作业1要求学生完成以下任务：
1. 实现一个线性表的动态数组（ArrayList）类。

2. 实现数组类的增加元素、删除元素、获取元素和遍历等基本操作。

3. 设计并实现一系列针对动态数组的测试用例。

参考资料
以下是一些可能对您完成作业有帮助的参考资料：
1. 《数据结构与算法（C++语言版）》（清华大学出版社）：
该书提供了关于线性表、数组和动态数组等内容的详细说明和代码
示例。

2. 网上教程和博客：在网上搜索关于实现动态数组的教程和博客，可以找到丰富的资料和代码示例，如CSDN、博客园等。

3. 课程讲义和教学视频：回顾和参考课程讲义中关于线性表和
动态数组的知识点，结合教学视频中的示例代码，加深理解和实践。

注意事项
完成作业时，请注意以下要求：
1. 请遵循作业要求中提到的功能和操作。

2. 参考资料仅供参考，请不要直接复制粘贴代码，应自己动手
实现。

3. 如果使用了参考资料中的代码或思路，请在作业中注明出处。

4. 如果在实现过程中遇到困难或问题，请及时向助教或老师寻
求帮助。

祝您顺利完成作业！如果还有其他问题或需要进一步的帮助，请随时与我联系。

大工19春《数据结构》在线作业1
试卷总分:100 得分:0
一、单选题(共10 道试题,共50 分)
1.以下选项属于非线性结构的是( )。

A.广义表
B.队列
C.优先队列
D.栈
正确答案:A
2.在存储数据时,通常不仅需要存储数据元素的值,还要存储( )。

A.数据元素的类型
B.数据的基本运算
C.数据元素之间的关系
D.数据的存取方式
正确答案:C
3.以下选项属于逻辑结构的是( )。

A.顺序表
B.散列表
C.有序表
D.单链表
正确答案:C
4.一个递归算法必须包括( )。

A.递归部分
B.终止条件和递归部分
C.迭代部分
D.终止条件和迭代部分
正确答案:B
5.算法的时间复杂度与( )有关。

A.问题规模
B.计算机硬件的运行速度
C.源程序的长度。

数据结构作业题作业题（一）一、单项选择题1. 从逻辑上可以把数据结构分为（ c ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构2. 链表不具有的特点是（ b ）A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比3.下面程序段的时间复杂度的量级为（ d ）。

For(i=1;i<=n;i++)For(j=1;j<=I;j++)For(k=1;k<=j;k++)X=x+1;A．O(1) B．O(n)C．O(n²) D．O(n³)4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（c）个指针域的值。

A．2 B．3C．4 D．65、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（ b ）。

A．98 B．100C．102 D．1066、判定一个栈s（最多元素为m0）为空的条件是（b）。

A．s-〉top! =0 B．s-〉top= =0C．s-〉top! =m0 D．s-〉top= =m07、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（ a ）。

A．（rear-front+m）%m B．rear-front+1C．rear-front-1 D． rear-front8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（c）。

A．连接 B．求子串C．模式匹配 D．判子串9、设串S1='ABCDEFG'，S2='PQRST'，函数con（x，y）返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果是（ d ）。

《数据结构》国开02272形考任务(1-4)试题与答案汇总一、选择题（每题5分，共20分）1. 数据的逻辑结构就是数据的（A）A. 元素之间的关系B. 物理结构C. 元素的值D. 元素的数量2. 线性表的存储结构有（D）A. 顺序存储和链式存储B. 顺序存储和索引存储C. 链式存储和散列存储D. 顺序存储、链式存储和索引存储3. 下面哪个不是线性表的运算（C）A. 插入B. 删除C. 排序D. 查找4. 在长度为n的线性表中，删除第i个元素（i从1开始），需要移动（A）A. n-i个元素B. i个元素C. n个元素D. 0个元素答案：AADB二、填空题（每题5分，共20分）1. 长度为n的线性表，其元素一共有n个。

2. 线性表的顺序存储结构是利用一组地址连续的存储单元依次存储线性表的元素。

3. 在线性表中，删除第i个元素后，从第i个元素到表尾的所有元素都向前移动一个位置。

4. 栈是一种特殊的线性表，只允许在表的一端进行插入和删除操作。

答案：略三、判断题（每题5分，共20分）1. 线性表是一种最基本的数据结构，它的特点是数据元素之间是一对一的关系。

（正确）2. 顺序存储结构的特点是存取方便，但插入和删除操作需要移动大量元素。

（正确）3. 链式存储结构的特点是不需要连续的存储空间，但插入和删除操作需要修改指针。

（正确）4. 栈和队列都是线性结构，但栈的操作是后进先出，而队列的操作是先进先出。

（正确）答案：略四、简答题（每题10分，共40分）1. 简述线性表的顺序存储结构的特点。

（10分）顺序存储结构是利用一组地址连续的存储单元依次存储线性表的元素。

其特点是存取方便，时间复杂度为O(1)。

但插入和删除操作需要移动大量元素，时间复杂度为O(n)。

2. 简述线性表的链式存储结构的特点。

（10分）链式存储结构是由一系列结点组成的线性序列，每个结点包含数据域和指针域。

其特点是无需连续的存储空间，插入和删除操作只需修改指针，时间复杂度为O(1)。