大工18秋《数据结构》在线作业123标准答案

一、单选题(50分)1.下列不属于数据库管理系统管理数据的特点的是()。

A.数据结构化B.数据共享性高C.实现并发操作D.数据不可恢复性正确答案：D2.下列不属于实体间对应关系的是()。

A.一对一联系B.一对多联系C.多对一联系D.多对多联系正确答案：C3.下列不属于集合运算符的是()。

A.并运算符B.差运算符C.与运算符D.广义笛卡尔积正确答案：C4.()是约束外码取值的规则。

A.实体完整性B.结构完整性C.参照完整性D.用户定义完整性正确答案：C5.下列属于SQL语言中的数据查询的动词的是()。

A.selectB.insertC.createD.grant6.CHECK是指下列哪个完整性约束()。

A.主码约束B.指定默认值C.参照完整性约束D.限制取值范围7.确定集合这个查询条件所使用的谓词是()。

A.IN或者NOT INB.LIKE或者NOT LIKEC.ANDD.BETWEEN AND8.()是最常用的连接查询。

A.内连接查询B.外连接查询C.交叉连接查询D.并列连接查询9.动词REVOKE属于SQL语言的()。

A.数据查询B.数据操纵C.数据定义D.数据控制10.下列集函数表示统计列值平均值的是()。

A.COUNT(*)B.COUNT(列名)C.SUM(列名)D.AVG(列名)二、判断题(50分)11.文件系统管理数据阶段,数据有了内部结构。

T.对F.错12.E-R方法是描述信息模型最常用的方法。

T.对F.错13.模式是数据库的物理结构。

T.对F.错14.比较运算符是用来辅助专门的关系运算符进行操作。

T.对F.错15.如果关系模式R的每一个属性都是不可再分的数据项,则称关系模式R满足第一范式。

T.对F.错16.连接有两种类型:非等值连接和等值连接。

T.对F.错17.在关系模型中实体与实体间的联系用关系表示。

T.对18.数据删除不属于数据更新。

T.对F.错19.绝大部分数据库管理系统将数据库存储在大容量的外部存储器上。

数据结构习题和答案及解析数据结构是计算机科学中非常重要的一个领域，它关注数据的存储、组织和管理方式。

在学习数据结构的过程中，遇到习题是必不可少的，通过解答这些习题可以更好地理解和掌握数据结构的概念和应用。

以下是一些常见的数据结构习题及其答案和解析，希望可以帮助读者更好地学习和理解数据结构。

习题一：栈的应用题目描述：设计一个栈，使其具有获取栈中最小元素的操作。

解答及解析：可以通过两个栈来实现，一个栈用于存储数据，另一个栈用于存储当前最小元素。

在入栈时，如果新的元素比当前最小元素小，则将新元素同时入栈到数据栈和最小栈；在出栈时，如果当前出栈元素与最小栈的栈顶元素相同，则同时出栈。

这样，最小栈的栈顶元素始终为当前栈的最小元素。

习题二：队列的应用题目描述：设计一个队列，使其具有获取队列中最大元素的操作。

解答及解析：可以通过两个队列来实现，一个队列用于存储数据，另一个队列用于存储当前最大元素。

在入队时，如果新的元素比当前最大元素大，则将新元素同时入队到数据队列和最大队列；在出队时，如果当前出队元素与最大队列的队首元素相同，则同时出队。

这样，最大队列的队首元素始终为当前队列的最大元素。

习题三：链表的操作题目描述：给定一个链表，删除链表中倒数第n个节点，并返回链表的头节点。

解答及解析：使用双指针法来解决该问题。

首先让一个指针从链表的头节点向前移动n+1步，然后再让另一个指针从链表的头节点开始移动。

这样两个指针之间的间隔为n，当第一个指针到达链表末尾时，第二个指针指向的节点就是倒数第n个节点的前一个节点。

接着，将第二个指针指向的节点的next指针指向下下个节点，完成删除操作。

习题四：树的遍历题目描述：给定一个二叉树，按照中序遍历的顺序返回其节点值的集合。

解答及解析：采用递归的方式进行中序遍历，先遍历左子树，然后访问根节点，最后遍历右子树。

对于任意一个节点，递归遍历其左子树，将节点值添加到集合中。

然后访问该节点，并将节点值添加到集合中。

(单选题) 1: 设给定权值总数有n 个，其哈夫曼树的结点总数为( )A: 不确定B: 2nC: 2n+1D: 2n-1正确答案:(单选题) 2: 下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。

A: 堆排序B: 冒泡排序C: 快速排序D: 插入排序正确答案:(单选题) 3: 已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）。

A: head（tail（tail（L）））B: tail（head（head（tail（L））））C: head（tail（head（tail（L））））D: head（tail(head（tail（tail（L）））)）正确答案:(单选题) 4: 线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A: O（i）B: O（1）C: O（n）D: O（i-1）正确答案:(单选题) 5: 动态存储管理系统中，通常可有（）种不同的分配策略。

A: 1B: 2C: 3D: 4正确答案:(单选题) 6: 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。

( )A: 选择排序法B: 插入排序法C: 快速排序法D: 堆积排序法正确答案:(单选题) 7: 串的长度是指（）A: 串中所含不同字母的个数B: 串中所含字符的个数C: 串中所含不同字符的个数D: 串中所含非空格字符的个数正确答案:(单选题) 8: 栈在（）中应用。

A: 递归调用B: 子程序调用C: 表达式求值D: A，Ｂ，Ｃ正确答案:(单选题) 9: 就平均性能而言，目前最好的内部排序方法是（）排序法。

A: 冒泡B: 希尔插入C: 交换D: 快速正确答案:(单选题) 10: 下述文件中适合于磁带存储的是（）。

A: 顺序文件B: 索引文件C: 散列文件D: 多关键字文件正确答案:(单选题) 11: 关系数据库中，实现实体之间的联系是通过表与表之间的？A: 公共索引B: 公共存储C: 公共元组D: 公共属性正确答案:(单选题) 12: 下列表达式中结果不是日期型的是?A: CTOD("2000/10/01")B: {^99/10/01}+365C: VAL("2000/10/01")D: DATE()正确答案:(单选题) 13: 一个算法应该是（）。

数据结构习题参考答案一、栈和队列1. 栈是一种具有后进先出（Last In First Out）特性的线性数据结构。

常用方法：- push(x): 将元素x压入栈顶；- pop(): 弹出栈顶元素；- top(): 返回栈顶元素；- isEmpty(): 判断栈是否为空；例题解答：（1）题目描述：使用栈实现队列的功能。

解答：使用两个栈，一个用于入队操作，一个用于出队操作。

入队操作：直接将元素压入入队栈中；出队操作：如果出队栈为空，则将入队栈的元素逐个弹出并压入出队栈，此时出队栈的栈顶元素即为要弹出的元素。

复杂度分析：入队操作的时间复杂度为O(1)，出队操作的平均时间复杂度为O(1)。

（2）题目描述：判断括号序列是否合法，即括号是否完全匹配。

解答：使用栈来处理括号序列，遇到左括号则入栈，遇到右括号则与栈顶元素进行匹配，如果匹配成功则继续处理剩余字符，如果不匹配则判定为非法序列。

算法步骤：- 初始化一个空栈；- 从左到右遍历括号序列，对于每个字符执行以下操作：- 如果是左括号，则将其入栈；- 如果是右括号，则将其与栈顶元素进行匹配：- 如果栈为空，则判定为非法序列；- 如果栈顶元素与当前字符匹配，则将栈顶元素出栈，继续处理剩余字符；- 如果栈顶元素与当前字符不匹配，则判定为非法序列。

- 遍历结束后，如果栈为空，则括号序列合法；否则，括号序列非法。

复杂度分析：时间复杂度为O(n)，其中n为括号序列的长度。

2. 队列是一种具有先进先出（First In First Out）特性的线性数据结构。

常用方法：- enqueue(x): 将元素x入队；- dequeue(): 出队并返回队首元素；- getFront(): 返回队首元素；- isEmpty(): 判断队列是否为空；例题解答：（1）题目描述：使用队列实现栈的功能。

解答：使用两个队列，一个用于入栈操作，一个用于出栈操作。

入栈操作：直接将元素入队入栈队列中；出栈操作：如果出栈队列为空，则将入栈队列的元素逐个出队并入队出栈队列，此时出栈队列的队首元素即为要出栈的元素。

大工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.算法的有穷性是指一个算法必须总是(对任何合法的输入)在执行有穷步之后结束,且每一步都可在有穷时间内完成。

数据结构第1～3章作业参考答案【1.4】【解法一】⑴抽象数据类型复数：ADT Complex{数据对象：D={ci|ci∈R, i=1,2, 其中R为实数集}数据关系：R={<c1,c2>| ci∈D, i=1,2, 其中c1为复数实部, c2为复数虚部}基本操作：InitComplex (&C,v1,v2)操作结果：构造一个复数C，元素c1, c2分别被赋以参数v1, v2的值。

DestroyComplex(&C)初始条件：复数C已存在。

操作结果：销毁复数C。

GetReal(C, &e)初始条件：复数C已存在。

操作结果：用e返回复数C实部的值。

Get Imaginary(C, &e)初始条件：复数C已存在。

操作结果：用e返回复数C虚部的值。

SetReal(&C, e)初始条件：复数C已存在。

操作结果：用e更新复数C实部的值。

Set Imaginary(&C, e)初始条件：复数C已存在。

操作结果：用e更新复数C虚部的值。

AdditionComplex (&C, C1, C2)初始条件：复数C1，C2已存在。

操作结果：复数C1与复数C2相加，用复数C返回其和。

SubstractComplex(&C, C1, C2)初始条件：复数C1，C2已存在。

操作结果：复数C1减去复数C2，用复数C返回其差。

MultipleComplex(&C, C1, C2 )初始条件：复数C1，C2已存在。

操作结果：复数C1与复数C2相乘，用复数C返回其积。

DividedComplex(&C, C1, C2)初始条件：复数C1，C2已存在，且C2≠0。

操作结果：复数C1除以复数C2，用复数C返回其商。

ModulusComplex(C, &e)初始条件：复数C已存在。

操作结果：求复数C的模，用e返回。

ConjugateComplex(&C, C1)初始条件：复数C1已存在。

《数据结构》各章课后作业答案 第一章 绪论课后作业答案1. 简述线性结构与非线性结构的不同点。

答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。

2．分析下面各程序段的时间复杂度（每小题5分，共20分）解：1.第一个for 循环执行n+1次，第二个for 循环执行n(m+1)次，A[i][j]=0;语句执行n*m 次，此程序段总的执行次数为n+1+n*(m+1)+n*m=2nm+2n+1次。

故时间复杂度为O(n*m)。

2.算法的时间复杂度是由嵌套最深层语句的执行次数决定的，本程序段嵌套最深层语句为：s+=B[i][j];它的执行次数为n 2，所以本程序段的时间复杂度是O(n 2)。

3. 该算法的基本操作是语句x++, 其语句频度为：1111n n i i j --==∑∑=10()n i n i -=-∑=(1)2n n - 所以本程序段的时间复杂度是O(n 2)。

4.设语句执行m 次，则有3m≤n ⇒m ≤log 3n所以本程序段的时间复杂度为O(log 3n)。

第二章 线性表课后作业答案1. 填空题。

（1）在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。

（2）线性表中结点的集合是 有限 的，结点间的关系是 一对一的。

（2）s=0;for （i=0; i<n; i++)for(j=0; j<n; j++) s+=B[i][j]; sum=s; 答：O （n 2）（1） for (i=0; i<n; i++) for (j=0; j<m; j++) A[i][j]=0;(3) x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;(4)i=1;while(i<=n)i=i*3;（3）向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。

数据结构习题参考答案第一章答案一、填空题1．数据元素，数据项2． O(1)，O(n)，O(log 2n)，O(n 2)3．线性结构，非线性结构，顺序结构，链式结构4．无，一，无，一5．前驱，一，无，任意6．任意7． O(n 1/2)8.O(1)<o(2n<="") 第二章答案一、填空题1． n/2，(n-1)/2分析：当在顺序线性表中的第i （1<=i<=n+1）个位置之前插入一个新元素时，从第i 个元素起向后的n+1-i 个元素均要向后移动一个位置。

因此在等概率情况下，插入操作中元素的平均移动次数为∑+==-++=112)1(11)(n i ni n n n f ；当在顺序线性表中删除第i （1<=i<=n ）个位置上的元素，从第i+1个元素起向后的n-i 个元素均要向前移动一个位置。

因此在等概率情况下，删除操作中元素的平均移动次数为∑=-=-= n i n i n n n f 121)(1)(。

2．向后3．向前4．指针域5．一定，不一定6． O(n)7． O(n)8．消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。

9．前驱，后继10．O(n)二、填空题1． (1)2． (1)3． (4)4． (2)5． (2)6． (4)7． (4)8． (1)9． (4)10．(1)11．(2)12．(3)第三章参考答案一、填空题1．线性，任何，栈顶，队尾，队头2．先进后出（FILO ），队尾，队头，先进先出（FIFO ）3． top==0，top==m4． 235415．前一个位置，所在位置，m-1分析：在顺序循环队列中约定头指针front 和尾指针rear 所指向的位置，是牺牲掉一个存储单元而方便表示队列空和队列满的条件，因此顺序循环队列中实际可用的存储单元只有m-1个。

6． (rear+1)%m==front ，rear==front7． O(1)8．返回地址，返回地址二、选择题1.(3) 2.(3) 3.(3) 4. (2)5. (2)6. (3)7. (1)8. (4)因为：顺序循环队列中的元素个数=??<+-≥-front rear m front rear front rear front rear ，整理合并可写成(rear-front+m)%m 。

大工秋数据结构在线作业标准化管理部编码-[99968T-6889628-J68568-1689N]大工17秋《数据结构》在线作业1总分：100分95分一、单选题共10题，50分15分下面关于串的概念的叙述中错误的是()。

学生答案：C 得分:5分25分一个有n个结点的有序单链表中,删除一个结点并仍然使链表有序的时间复杂度是()。

学生答案：B 得分:5分35分序列{a,b,c,d}顺序进栈,其出栈的顺序不可能为()。

学生答案：B 得分:5分45分以下四种数据结构中()不是线性结构。

学生答案：D 得分:5分55分最适合用做链式队列的链表是()。

学生答案：B 得分:5分65分栈的插入与删除操作均在()进行。

学生答案：A 得分:0分75分线性表在()情况下最适合采用链表表示。

学生答案：B 得分:5分85分以下算法的时间复杂度为（）：for(i=0;i<n;i++){for(j=1,sum=a[0];j<=i;j++){sum+=a[j];}cout<<"sumforsubarray0through"学生答案：C 得分:5分95分线性表采用链式存储结构时,其地址()。

学生答案：C 得分:5分105分栈是一种具有()特性的线性表。

学生答案：A 得分:5分二、判断题共10题，50分15分若顺序表中第一个元素的存储地址是100,每个元素长度为2,则第5个元素的地址是110。

学生答案：B 得分:5分25分取线性表第k个元素的时间代价同k的大小无关。

学生答案：A 得分:5分35分栈结构是一种限定只能在一端进行插入,在另一端进行删除的线性表。

学生答案：B 得分:5分45分线性表的每个元素都必须有一个前驱和一个后继。

学生答案：B 得分:5分55分串的长度是指串中所含字符的个数学生答案：A 得分:5分65分顺序存储的线性表不可以进行随机存取操作。

学生答案：B 得分:5分75分在队列的任意位置均可以实现插入元素操作。

数据结构课后习题标准答案————————————————————————————————作者：————————————————————————————————日期：7_1对于图题7.1（P235）的无向图，给出：（1）表示该图的邻接矩阵。

（2）表示该图的邻接表。

（3）图中每个顶点的度。

解：（1）邻接矩阵：0111000100110010010101110111010100100110010001110（2）邻接表：1：2----3----4----NULL;2: 1----4----5----NULL;3: 1----4----6----NULL;4: 1----2----3----5----6----7----NULL;5: 2----4----7----NULL;6: 3----4----7----NULL;7: 4----5----6----NULL;（3）图中每个顶点的度分别为：3，3，3，6，3，3，3。

7_2对于图题7.1的无向图，给出：（1）从顶点1出发，按深度优先搜索法遍历图时所得到的顶点序（2）从顶点1出发，按广度优先法搜索法遍历图时所得到的顶点序列。

（1）DFS法：存储结构：本题采用邻接表作为图的存储结构，邻接表中的各个链表的结点形式由类型L_NODE规定，而各个链表的头指针存放在数组head中。

数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边，e中结点形式由类型E_NODE规定。

visit[i]数组用来表示顶点i是否被访问过。

遍历前置visit各元素为0，若顶点i被访问过,则置visit[i]为1.算法分析：首先访问出发顶点v.接着，选择一个与v相邻接且未被访问过的的顶点w访问之，再从w 开始进行深度优先搜索。

每当到达一个其所有相邻接的顶点都被访问过的顶点，就从最后访问的顶点开始，依次退回到尚有邻接顶点未曾访问过的顶点u,并从u开始进行深度优先搜索。

这个过程进行到所有顶点都被访问过，或从任何一个已访问过的顶点出发，再也无法到达未曾访问过的顶点，则搜索过程就结束。

《数据结构》课后参考答案第一题：1. 什么是数据结构？数据结构是一种组织和存储数据的方式，它涉及到数据的逻辑关系、数据元素之间的操作和存储方式等。

数据结构可以帮助我们更有效地组织和管理数据，提高程序的运行效率。

第二题：2. 请简述线性表和链表的区别。

线性表是一种线性结构，其中的数据元素按照线性的顺序排列。

线性表可以使用数组实现，也可以使用链表实现。

链表是一种动态数据结构，它通过节点之间的指针连接来存储数据元素。

主要区别：- 存储方式：线性表使用静态的连续内存空间存储，而链表使用动态的节点存储，并通过指针连接节点。

- 插入和删除操作：线性表需要移动数组中的元素，而链表只需要修改指针指向即可。

- 访问效率：线性表可以通过下标直接访问元素，访问效率高；链表需要从头节点开始逐个遍历，访问效率较低。

第三题：3. 请描述栈和队列的特点及其应用场景。

栈和队列都是常用的线性数据结构，它们在不同的场景中有着不同的特点和应用。

栈的特点：- 先进后出（LIFO）的数据结构。

- 只能在栈顶进行插入和删除操作。

- 用途广泛，如函数调用、表达式求值、计算机内存的管理等。

队列的特点：- 先进先出（FIFO）的数据结构。

- 可以在队尾插入元素，在队头删除元素。

- 用途广泛，如任务调度、消息传递、广度优先搜索等。

第四题：4. 请简述树和图的区别以及它们的应用场景。

树和图都是常用的非线性数据结构，它们之间有着一些区别和各自的应用场景。

树的特点：- 由节点和边组成的层次结构。

- 每个节点最多有一个父节点和多个子节点。

- 常用的树结构有二叉树、平衡二叉树、B树等。

- 应用场景包括文件系统、数据库索引等。

图的特点：- 由节点和边组成的非线性结构。

- 节点之间的关系可以是任意的。

- 常用的图结构有有向图、无向图、加权图等。

- 应用场景包括社交网络、路由算法、拓扑排序等。

综上所述，数据结构是计算机科学的重要基础，它为我们解决实际问题提供了有力的工具和方法。

《数据结构》在线作业答案整理1.单选题1.无向图的邻接矩阵是一个()。

A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵2.串的长度是（）。

A.串中不同字符的个数B.串中不同字母的个数C.串中所含字符的个数且字符个数大于0D.串中所含字符的个数3.对n个记录的文件进行堆排序，最坏情况下的执行时间为()。

A.O(log2n)B.O(nlogn)C.O(n)D.O(n*n)4.为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用()方式。

A.顺序存储B.链式存储C.索引存储D.散列存储5.算法分析的目的是（）。

A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易读性和文档性6.在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。

A.HL=p;p->next=HL;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.p->next=HL->next;HL->next=p;7.在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（）。

A.行号B.列号C.元素值D.地址8.设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（）。

A.3700B.4376C.3900D.46209.以下关于数据的存储结构的叙述哪一条是正确的（）。

A.数据的存储结构是数据间关系的抽象描述B.数据的存储结构是逻辑结构在计算机存储器中的实现C.数据的存储结构分为线性结构和非线性结构D.数据的存储结构对数据运算的具体实现没有影响10.设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（）。

A.3，2，5，6，4，1B.1，5，4，6，2，3C.2，4，3，5，1，6D.4，5，3，6，2，111.下列数据组织形式中，（）的各个结点可以任意邻接。

数据结构参考答案数据结构是计算机科学中的一个重要概念，它用于组织和存储数据，以便于快速访问和操作。

在计算机科学的发展过程中，数据结构一直扮演着重要的角色，它不仅为算法的设计和优化提供了基础，还为各种应用程序的开发提供了支持。

一、数据结构的分类数据结构可以分为线性结构和非线性结构。

线性结构是指数据元素之间存在一对一的关系，如数组和链表；非线性结构是指数据元素之间存在一对多或多对多的关系，如树和图。

线性结构适合于顺序访问和搜索，而非线性结构适合于递归和分治等操作。

二、常见的数据结构1. 数组：数组是一种最简单的数据结构，它将相同类型的数据元素按照一定的顺序存储在连续的内存空间中。

数组的优点是可以通过下标快速访问元素，但是插入和删除操作比较慢。

2. 链表：链表是一种动态数据结构，它通过指针将数据元素按照一定的顺序连接起来。

链表的优点是插入和删除操作比较快，但是访问元素需要遍历链表。

3. 栈：栈是一种后进先出（LIFO）的数据结构，它只允许在栈顶进行插入和删除操作。

栈的应用场景包括函数调用、表达式求值和括号匹配等。

4. 队列：队列是一种先进先出（FIFO）的数据结构，它只允许在队尾插入元素，在队头删除元素。

队列的应用场景包括任务调度、消息传递和缓冲区管理等。

5. 树：树是一种非线性的数据结构，它由节点和边组成，每个节点可以有多个子节点。

树的应用场景包括文件系统、数据库索引和网络路由等。

6. 图：图是一种包含节点和边的数据结构，节点表示实体，边表示实体之间的关系。

图的应用场景包括社交网络、地图导航和网络拓扑等。

三、数据结构的应用数据结构在计算机科学中有着广泛的应用。

例如，在搜索引擎中，数据结构被用于构建倒排索引，以实现快速的关键词搜索。

在数据库系统中，数据结构被用于索引和排序，以提高查询和排序的效率。

在人工智能领域，数据结构被用于构建决策树和神经网络，以实现机器学习和深度学习。

此外，数据结构还被广泛应用于算法设计和优化。

19春学期《数据结构Ⅰ》在线作业1一棵完全二叉树上有1001个结点，其中叶子结点的个数是A.250B.500C.254D.以上答案都不对正确答案:D顺序存储设计时，存储单元的地址A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续正确答案:A若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为A.f,c,bB.f,d,bC.g,c,bD.g,d,b正确答案:A在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为A.iB.i+1C.n-iD.n-i+1正确答案:C在长度为n的顺序表中删除第i个元素(1in)时，元素移动的次数为A.n-i+1B.iC.i+1D.n-i正确答案:D在线性表的下列运算中，不改变数据元素之间结构关系的运算是A.插入B.删除C.排序D.查找正确答案:D队列和栈的主要区别是A.逻辑结构不同B.存储结构不同C.所包含的运算个数不同D.限定插入和删除的位置不同正确答案:D数组A[1..5，1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为A.1140B.1145C.1120D.1125正确答案:A通常将链串的结点大小设置为大于1是为了A.提高串匹配效率B.提高存储密度C.便于插入操作D.便于删除操作正确答案:B高度为5的完全二叉树中含有的结点数至少为A.16B.17C.31D.32正确答案:A在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为A.4，4，3B.4，3，3C.3，4，4D.3，3，4正确答案:B倒排文件的主要优点是A.便于进行插入和删除运算B.便于进行文件的恢复C.便于进行多关键字查询D.节省存储空间正确答案:C某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则该二叉树对应的森林包括的树的棵树是A.1B.2C.3D.概念上是错误的正确答案:B如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法正确答案:B已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为A.ABCDEFB.ABCEFDC.ABFCDED.ABCDFE正确答案:D数据元素及其关系在计算机存储器内的表示，称为数据的A.逻辑结构B.存储结构C.线性结构D.非线性结构正确答案:B判断两个串大小的基本准则是A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小正确答案:D若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是A.1234B.4132C.4231D.4213正确答案:C一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是A.不确定B.0C.1D.2正确答案:D无向图中一个顶点的度是指图中A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数C.通过该顶点的回路数D.与该顶点连通的顶点数正确答案:D19春学期《数据结构Ⅰ》在线作业2设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是A.A，B，C，DB.D，C，B，AC.A，C，D，BD.D，A，B，C正确答案:D算法的时间复杂度主要取决于A.问题的规模B.待处理数据的初态C.难度D.A和B正确答案:A文件中，主关键字能唯一标识A.一个记录B.一组记录C.一个类型D.一个文件正确答案:A下列程序段for(i=1;i=n;i++)A[i,j]=0;的时间复杂度是A.O(1)B.O(0)C.O(1+n)D.O(n)正确答案:D二叉树中第5层上的结点个数最多为A.8B.15C.16D.32正确答案:C有关二叉树下列说法正确的是A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2正确答案:B抽象数据类型的三个组成部分分别为A.数据对象、数据关系和基本操作B.数据元素、逻辑结构和存储结构C.数据项、数据元素和数据类型D.数据元素、数据结构和数据类型正确答案:A对n个关键字的序列进行快速排序，平均情况下的空间复杂度为A.O(1)B.O(logn)C.O(n)D.O(nlogn)正确答案:D用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为A.5B.6C.8正确答案:A十字链表的三元组表是稀疏矩阵的一种A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构正确答案:B在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是A.G中有弧Vi，VjB.G中有一条从Vi到Vj的路径C.G中没有弧Vi,VjD.G中有一条从Vj到Vi的路径正确答案:D如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为A.插入排序B.归并排序C.冒泡排序D.堆排序正确答案:A在待排关键字序列基本有序的前提下，效率最高的排序方法是A.直接插入排序B.快速排序C.直接选择排序D.归并排序正确答案:A下面关于线性表的叙述中，错误的是A.线性表采用顺序存储，必须占用一片连续的存储单元。