大工20春《数据结构》在线作业3

大连理工大学网络教育学院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
一、单选题(共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.源程序的长度
D.编译后执行程序的质量
正确的答案是:A
6.静态链表与动态链表相比较,其缺点是( )。

A.插入和删除需移动较多数据
B.有可能浪费较多存储空间
C.不能随机存取
D.以上都不是
正确的答案是:B。

1.顺序查找法适合于存储结构为（）的线性表。

A.散列表B.顺序存储或链接存储C.压缩存储D.索引存储【参考答案】: B2.算法分析的两个主要方面是（）。

A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性【参考答案】: A3.对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分。

在第一趟划分过程中，元素移动次数最多的序列是()。

A.82，75，70，16，10，90，68，23B.23，10，16，70，82，75，68，90C.70，75，68，23，10，16，90，82D.70，75，82，90，23，16，10，68【参考答案】: D4.邻接表是图的一种（）。

A.顺序存储结构B.链式存储结构C.索引存储结构D.列存储结构【参考答案】: B5.链表不具有的特点是（）。

A.不必事先估计存储空间B.可随机访问任一元素C.插入删除不需要移动元素 D.所需空间与线性表长度成正比【参考答案】: B6.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是（）。

A.根结点无右子树的二叉树B.根结点无左子树的二叉树C.根结点可能有左二叉树和右二叉树D.各结点只有一个儿子的二叉树【参考答案】: C7.具有2000个节点的二叉树，其高度至少为（）。

A.9B.10C.11D.12【参考答案】: C8.线索化二叉树中某结点D，没有左孩子的主要条件是（）。

A.D-Lchild=NullB.D-ltag=1C.D-Rchild=NullD.D-ltag=0【参考答案】: B9.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。

A.edcbaB.decbaC.abcdeD.dceab【参考答案】: D10.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

A.8B.63.5C.64D.7【参考答案】: B11.以下数据结构中不属于线性数据结构的是（）。

【奥鹏】-[东北师范大学]数据结构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题,下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。

20春学期《数据结构Ⅰ》在线平时作业3
学校：奥鹏东北大学
一、单选题 (共 20 道试题,共 100 分)
1.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是
[[A.]](rear-front)%m= =m-1
[[B.]](rear-front)%m= =1
[[C.]]front= =(rear+1)%m
[[D.]]front= =rear
作答提示
√选择是:D
2.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为
[[A.]]O(n) O(n)
[[B.]]O(n) O(1)
[[C.]]O(1) O(n)
[[D.]]O(1) O(1)
作答提示
√选择是:C
3.高度为5的完全二叉树中含有的结点数至少为
[[A.]]32
[[B.]]31
[[C.]]17
[[D.]]16
作答提示
√选择是:D
4.二维数组A按行优先顺序存储，其中每个元素占1个存储单元。

若A［1］［1］的存储地址为420，
A［3］［3］的存储地址为446，则A［5］［5］的存储地址为
[[A.]]473
[[B.]]472
[[C.]]471
[[D.]]470
作答提示
√选择是:B
5.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是
[[A.]]不确定的
[[B.]]12。

大工20春《建筑制图》在线作业3满分答案
1
配在钢筋混凝土板内,与受力筋垂直,用以固定受力筋的位置,与受力筋一起构成钢筋网,使力均匀分布给受力筋,
并抵抗热胀冷缩所引起的温度变形的钢筋是()。

A 架立筋
B 钢箍
C 构造筋
D 分布筋
答案：D
2
板内直径10mm的HPB235级钢筋连续排列，相邻钢筋中心距不大于200mm的标注形式为（）。

A φ10@200
B 2φ10@200
C 2φ10
D φ10@200/10
答案：A
3
下列钢筋中，一般不用于板内的是（）。

A 受力筋
B 架立筋
C 分布筋
D 构造筋
答案：B
4
结构施工图中，构件与代号对应错误的是（）。

A 槽形板—CB
B 密肋板—MB
C 枪板—QB
D 天沟板—TB
答案：D
5
某框架柱的配筋为φ8@100/200,其含义为()。

A 箍筋为HPB235级钢筋，直径8mm，钢筋间距为200mm
B 箍筋为HPB235级钢筋，直径8mm，钢筋间距为100mm
C 箍筋为HPB235级钢筋，直径8mm，加密区间距为200mm，非加密区间距为100mm
D 箍筋为HPB235级钢筋，直径8mm，加密区间距为100mm，非加密区间距为200mm
答案：D
1
在房屋结构施工图中，构件与代号对应正确的有（）。

A 屋面板→WB。

【奥鹏】-大连理工20春《数据结构》在线作业3
提示：请认真阅读本套试卷，核对是否是您需要的题目，本套试卷只做参考学习
使用！！！
一、单选题 (共 10 道试题,共 50 分)
【题目】采用顺序查找方法查找长度为n的线性表时,成功查找时的平均查找长度为()。

[A.]n
[B.]n/2
[C.](n+1)/2
[D.](n-1)/2
正确的选择是：C
【题目】对线性表进行折半查找时,要求线性表必须()。

[A.]以顺序方式存储
[B.]以链接方式存储
[C.]以顺序方式存储，且结点按关键字有序排列
[D.]以链表方式存储，且结点按关键字有序排列
正确的选择是：C
【题目】有n个元素的数组,查找其中最大值的元素,一般需要()次元素的比较。

[A.]1
[B.]n
[C.]n+1
[D.]n-1
正确的选择是：D
【题目】查找效率最高的二叉排序树是()。

[A.]所有结点的左子树都为空的二叉排序树
[B.]所有结点的右子树都为空的二叉排序树
[C.]平衡二叉树
[D.]没有左子树的二叉排序数
正确的选择是：C
【题目】在哈希查找过程中,可用()来处理冲突。

[A.]除留余数法
[B.]数字分析法
[C.]线性探测法
[D.]关键字比较法。

大工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分大部分数据库管理系统是将数据库存储在大容量的外部存储器上。

《数据结构》填空作业题答案第1章绪论（已校对无误）1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。

2．程序包括两个内容：数据结构和算法。

3. 数据结构的形式定义为：数据结构是一个二元组： Data Structure =（D，S）。

4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。

5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。

6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。

7. 在树形结构中，数据元素之间存在一对多的关系。

8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。

9. 数据的逻辑结构包括线性结构、树形结构和图形结构 3种类型，树型结构和有向图结构合称为非线性结构。

10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。

11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。

12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。

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

14. 数据结构在物理上可分为顺序存储结构和链式存储结构。

15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。

16. 数据元素可由若干个数据项组成。

17. 算法分析的两个主要方面是时间复杂度和空间复杂度。

18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。

19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。

20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。

数据结构部分课后习题答案(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位二进制数。

20春《数据结构》作业3A:小于m的最大奇数B:小于m的最大素数C:小于m的最大偶数D:小于m的最大合数答案：B 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为___。

A:4 B:5 C:6 D:7 答案：C 设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列___方法可以达到此目的。

A:快速排序 B:堆排序 C:归并排序 D:插入排序答案：B A:A B:B C:C D:D 答案：A 设某棵二叉树中有2000个结点，则该二叉树的最小高度为___。

A:9 B:10 C:11 D:12 答案：C 设有6个结点的无向图，该图至少应有___条边才能确保是一个连通图。

A:5 B:6 C:7 D:8答案：A A:A B:B C:C D:D 答案：A 某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为___。

A:3 B:2 C:4 D:5 答案：CA:A B:B C:C D:D 答案：C 串的长度是指___。

A:串中所含不同字母的个数 B:串中所含字符的个数 C:串中所含不同字符的个数 D:串中所含非空格字符的个数答案：B 设一组初始记录关键字序列为（345,253,674,924,627），则用基数排序需要进行___趟的分配和回收才能使得初始关键字序列变成有序序列。

A:3 B:4 C:5 D:8 答案：A A:A B:B C:C D:D 答案：C 设一组初始记录关键字序列（5,2,6,3,8），以第一个记录关键字5为基准进行一趟快速排序的结果为___。

A:2,3,5,8,6 B:3,2,5,8,6 C:3,2,5,6,8 D:2,3,6,5,8 答案：CA:A B:BC:C D:D 答案：C 如果最常用的操作是取第i个结点及其前驱，则采用___存储方式最节省时间。

A:单链表 B:双链表 C:单循环链表 D:顺序表答案：D 设某有向图中有n个顶点，则该有向图对应的邻接表中有___个表头结点。

大工18春《数据结构》在线作业3
试卷总分:100 得分:100
一、判断题 (共 10 道试题,共 50 分)
1.散列文件中存放一组记录的存储单位称为桶。

A.对
B.错
正确答案:A
2.散列方法的查找性能用平均查找长度ASL来衡量。

A.对
B.错
正确答案:A
3.二分查找对线性表的存储结构无任何要求。

A.对
B.错
正确答案:B
4.折半查找只能在有序的顺序表上进行而不能在有序链表上进行。

A.对
B.错
正确答案:A
5.快速排序算法是一种不稳定的算法。

A.对
B.错
正确答案:A
6.直接选择排序属于选择类排序,是一种稳定的排序方法。

A.对
B.错
正确答案:B
7.对于一个堆,按二叉树层次进行遍历可以得到一个有序序列。

A.对
B.错
正确答案:B。

大工20春《编译原理基础》在线作业1试卷总分:100 得分:100一、判断题(共15 道试题,共75 分)1.试探与回溯是一种穷尽一切可能的办法,效率低、代价高,它只有理论意义,在实践中价值不大。

本题参考答题选项:正确2.预测分析的关键问题是在扩展一个非终结符时怎样为它选择合适的产生式。

本题参考答题选项:正确3.移进-归约分析为输入串构造分析树是从根结点开始的,朝着叶结点方向前进。

本题参考答题选项:错误4.句型的句柄是该句型中和一个产生式左部匹配的子串。

本题参考答题选项:错误5.一个文法,如果能为它构造出所有条目都唯一的LR分析表,就说它是LR文法。

本题参考答题选项:正确6.语法制导的产生式有多组语义规则。

本题参考答题选项:错误7.属性文法是指语义规则函数无副作用的语法制导定义。

本题参考答题选项:正确8.仅仅使用综合属性的语法制导定义称为S属性定义。

本题参考答题选项:正确9.每个结点的属性值都标注出来的分析树叫做注释分析树。

本题参考答题选项:正确10.过程定义是一个声明,它的最简单形式是将一个名字和一个语句联系起来,该名字是过程名,而这个语句是过程体。

本题参考答题选项:正确11.过程名出现在调用语句中则称这个过程在该点被调用。

本题参考答题选项:正确12.出现在过程定义中的某些名字是特殊的,它们被称为该过程的形式参数,简称形参。

本题参考答题选项:正确13.一个声明起作用的程序部分称为该声明的作用域。

本题参考答题选项:正确14.引用某个已被回收的存储单元就称为悬空引用。

本题参考答题选项:正确15.后缀表示是语法树的一种线性表示。

本题参考答题选项:正确二、单选题(共5 道试题,共25 分)16.对于LR(0)分析法,语法分析栈中存放的状态是识别规范句型()的DFA状态。

A.前缀B.活前缀C.LR(0)项目D.句柄本题参考答题选项:B17.同心集合并可能会产生的冲突为()。

A.二义B.移进-移进C.移进-归约D.归约-归约本题参考答题选项:D18.如果一个文法G是无二义性文法,对于任何一个句子,该句子()。

《数据结构》在线作业答案整理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．简述单链表设置头结点的主要作用。

答：1、防止单链表是空的而设的。

当链表为空的时候，带头结点的头指针就指向头结点，如果当链表为空的时候，头结点的指针域的数值为NULL。

2、为了方便单链表的特殊操作，插入在表头或者删除第一个结点。

这样就保持了单链表操作的统一性。

3、单链表加上头结点之后，无论单链表是否为空，头指针始终指向头结点，因此空表和非空表的处理统一，方便了单链表的操作，也减少了程序的复杂性和出现bug的机会。

4、对单链表的多数操作应明确对哪个结点以及该结点的前驱。

不带头结点的链表对首元结点、中间结点分别处理等；而带头结点的链表因为有头结点，首元结点、中间结点的操作相同,从而减少分支，使算法变得简单，流程清晰。

2. 简述线性表的顺序和链式两种存储结构各自的主要特点。

答:线性表的两种存储结构分别是顺序存储结构和链式存储结枃。

顺序存储结构的主要特点如下:①数据元素中只有自身的数据域，没有关联指针域。

因此，顺序存储结构的存储密度较大。

②顺序存储结构需要分配一整块比较大存储空间，所以存储空间利用率较低。

③逻辑上相邻的两个元素在物理上也是相邻的，通过元素的逻辑序号可以直接其元素值，即具有随机存取特性④插入和删除操作会引起大量元素的移动。

链式存储结构的主要特点如下①数据结点中除自身的数据域，还有表示逻辑关系的指针域。

因此，链式存储结构比顺序存储结构的存储密度小。

②链式存储结构的每个结点是单独分配的，每个结点的存储空间相对较小，所以存储空间利用率较高。

③在逻辑上相邻的结点在物理上不一定相邻，因此不具有随机存取特性。

④插入和刚除操作方便灵活，不必移动结点，只需修改结点中的指针域即可3. 说明在线性表的链式存储结构中，试述头结点,首元结点,头指针这三个概念的区别.答：在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。

头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（也可存放链表的长度、用做监视哨等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。

大工18春《数据结构》在线作业31、A2、A3、B4、A5、A一、判断题共10题，50分1、散列文件中存放一组记录的存储单位称为桶。

A对B错正确答案是：A2、散列方法的查找性能用平均查找长度ASL来衡量。

A对B错正确答案是：A3、二分查找对线性表的存储结构无任何要求。

A对B错正确答案是：B4、折半查找只能在有序的顺序表上进行而不能在有序链表上进行。

A对B错正确答案是：A5、快速排序算法是一种不稳定的算法。

A对B错正确答案是：A6、直接选择排序属于选择类排序,是一种稳定的排序方法。

A对B错正确答案是：B7、对于一个堆,按二叉树层次进行遍历可以得到一个有序序列。

A对B错正确答案是：B8、折半查找的查找速度一定比顺序查找法的查找速度快。

A对B错正确答案是：B9、堆排序是一种不稳定的排序方法。

A对B错正确答案是：A10、若待排序记录已按排序码基本有序,则应采用直接插入排序或起泡排序。

A对B错正确答案是：A二、单选题共10题，50分1、在长度为n的顺序表中进行顺序查找,查找失败时需与关键字比较次数是()。

AnB1Cn-1Dn+1正确答案是：D2、对线性表进行顺序查找时,要求线性表的存储结构是()。

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

A2B3C4D5正确答案是：C4、如果要求一个线性表既能较快地查找,又能适应动态变化的要求,则可采用的查找方法是()。

A分块B顺序C折半D哈希正确答案是：A5、排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为()。

A插入排序B冒泡排序C希尔排序D选择排序正确答案是：A6、排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端的方法,称为()。

大工20秋《数据结构原理与开发》在线作业2答卷问题一请描述数据结构的定义及其作用。

数据结构是指将数据组织起来以便有效地使用的一种方式。

它是一种组织和存储数据的方式，可以提供对数据的快速访问和操作。

数据结构的作用是在计算机程序中高效地管理和操作数据，以实现各种功能和算法。

问题二简述线性表和树的区别。

线性表是一种数据结构，其中的元素按线性顺序排列，每个元素有唯一的前驱和后继。

线性表中的元素可以是任意类型的数据。

树是一种数据结构，由节点和边组成，节点之间存在一种层次关系。

每个节点可以有多个子节点，但只能有一个父节点。

树是一种递归的数据结构，可以用于解决许多实际问题。

线性表和树的主要区别在于结构和关系的不同。

线性表的元素之间只有一种前后关系，而树的节点之间存在一对多的关系。

问题三请简述二叉树的性质。

二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，称为左子节点和右子节点。

二叉树的性质如下：1.每个节点最多有两个子节点。

2.左子节点在二叉树中的位置比右子节点靠近根节点。

3.二叉树的子树也是二叉树。

问题四请简述图的应用场景。

图是一种数据结构，由节点和边组成，用于表示多对多的关系。

图的应用场景包括：1.社交网络：用于表示用户之间的关系网络。

2.地图导航：用于表示道路和地点之间的连接关系。

3.电路设计：用于表示电路中的组件和连接关系。

4.网络拓扑：用于表示计算机网络中的节点和连接关系。

图的应用非常广泛，可以用于解决许多实际问题。

问题五请分别定义栈和队列，并描述它们的特点。

栈是一种后进先出（LIFO）的数据结构，只能在一端插入和删除元素。

插入操作称为入栈，删除操作称为出栈。

队列是一种先进先出（FIFO）的数据结构，可以在两端插入和删除元素。

插入操作称为入队，删除操作称为出队。

栈的特点是元素的插入和删除都发生在一端，最后入栈的元素会最先出栈。

队列的特点是插入和删除操作发生在两端，最先入队的元素会最先出队。

问题六请简述深度优先搜索（DFS）和广度优先搜索（BFS）的区别。

国家开放大学电大《数据结构》网络课形考任务3作业及答案形考任务3一、单项选择题（每小题2分，共38分）题目1假定一棵二叉树中，双分支结点数为15,单分支结点数为30,则叶子结点数为（）o选择一项：A. 47B. 16C. 17D. 15题目2二叉树第k层上最多有（）个结点。

选择一项：A. 2k-lB. 2k-lC. 2k-lD. 2k题目3将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1,则编号为69的结点的双亲结点的编号为（）o选择一项：A. 36B. 35C. 34D. 33题目4如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）o选择一项：A. 二叉树B. 哈夫曼树C. 完全二叉树D. 平衡二叉树在一棵度具有5层的满二叉树中结点总数为（）o选择一项：A. 16B. 32C. 31D. 33题目6一棵完全二叉树共有6层，且第6层上有6个结点，该树共有（）个结点。

选择一项：A. 31B. 37C. 38D. 72题目7利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（）。

选择一项：A. 18B. 16C. 30D. 12题目8在一棵树中，（）没有前驱结点。

选择一项：A. 树根结点B. 叶结点C. 空结点D. 分支结点题目9设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2,该树结点中共有20个指针域为空，则该树有（）个叶结点。

选择一项：C. 21D. 22题目10在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。

选择一项：A. 2B. 1C. 4D. 1/2题目11邻接表是图的一种（）o选择一项：A. 链式存储结构B. 顺序存储结构C. 散列存储结构D. 索引存储结构题目12图的深度优先遍历算法类似于二叉树的（）遍历。

选择一项：A. 先序B. 后序C. 层次D. 中序题目13已知下图所示的一个图，若从顶点VI出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。