[北语]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个元素的地址是（）。

(单选)1：树转换成二叉树后，以下结论正确的是（）。

A：树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B：树的先根遍历序列与其对应的二叉树的中序遍历序列相同
C：树的后根遍历序列与其对应的二叉树的后序遍历序列相同
D：以上都不对
正确答案：A
(单选)2：如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用___。

A：只有表头指针没有表尾指针的循环单链表
B：只有表尾指针没有表头指针的循环单链表
C：非循环双链表
D：循环双链表
正确答案：B
(单选)3：串的长度是指___。

A：串中所含不同字母的个数
B：串中所含字符的个数
C：串中所含不同字符的个数
D：串中所含非空格字符的个数
正确答案：B
(单选)4：设某棵二叉树中有2000个结点，则该二叉树的最小高度为___。

A：9
B：10
C：11
D：12
正确答案：C
(单选)5：将一株有100个节点的完全二叉树从上到下，从左到右依次进行编号，根节点的编号为1，则编号为49的节点的左孩子编号为（）。

B：98
C：89
D：50
E：没有孩子
正确答案：B
(单选)6：在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的___倍。

A：1/2
B：1
C：2
D：4
正确答案：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.以下数据结构中不属于线性数据结构的是（）。

1.A.AB.BC.CD.D【参考答案】: D2.A.AB.BC.CD.D【参考答案】: A3.不定长文件是指___。

A.文件的长度不固定B.记录的长度不固定C.字段的长度不固定D.关键字项的长度不固定【参考答案】: B4.在一个长度为n（n>1）的单链表上，设有头和尾两个指针，执行___操作与链表的长度有关。

A.删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素【参考答案】: B5.栈的插入和删除操作在___进行。

A.栈顶B.栈底C.任意位置D.指定位置【参考答案】: A6.A.AB.BC.CD.D【参考答案】: D7.顺序查找法适合于存储结构为___的线性表。

A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储【参考答案】: B8.以下____不是队列的基本运算。

A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值【参考答案】: B9.A.AB.BC.CD.D【参考答案】: C10.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有___条有向边。

A.nB.n-1C.mD.m-1【参考答案】: C11.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为___。

A.O（0）B.O（1）C.O（n）D.O（n2）【参考答案】: C12.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为___。

A.O（1）B.O（n）C.O（m）D.O（mn）【参考答案】: C13.A.AB.BC.CD.D【参考答案】: A14.线性表（a1,a2,...,an）以链式方式存储，访问第i位置元素的时间复杂度为___。

A.O（0）B.O（1）C.O（n）D.O（n2）【参考答案】: C15.A.AB.BC.CD.D【参考答案】: B16.A.AB.BC.CD.D【参考答案】: A17.线性表采用链式存储时，结点的存储地址___。

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春《数据结构》作业_1一、单选题 ( 每题4分, 共25道小题, 总分值100分 )1.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n,森林F 中第一棵子树的结点个数是（）。

A. m-nB. m-n-1C. n+1D. 条件不足，无法确定答：A q：80–500 -92612.答：D3.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是___。

A. 单链表B. 静态链表C. 线性链表D. 顺序存储结构答：B4.求循环链表中当前结点的后继和前驱的时间复杂度分别是（）。

A. O(n)和O(1)B. O(1)和O(1)C. O(1)和O(n)D. O(n)和O(n)答：C5.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为___。

A. O（0）B. O（1）C. O（n）D. O（n2）答：C6.答：D7.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是___。

A. O（1）B. O（n）C. O（n2）D. O（nlog2n）答：B8.答：B9.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为___。

A. O（n）O（n）B. O（n）O（1）C. O（1）O（1）D. O（1）O（n）答：C10.线性表采用链式存储时，结点的存储地址___。

A. 必须是不连续的B. 连续与否均可C. 必须是连续的D. 和头结点的存储地址相连续答：B11.以下___不是队列的基本运算。

A. 从队尾插入一个新元素B. 从队列中删除第i个元素C. 判断一个队列是否为空D. 读取队头元素的值答：B12.答：A14.在一个长度为n（n>1）的单链表上，设有头和尾两个指针，执行___操作与链表的长度有关。

A. 删除单链表中的第一个元素B. 删除单链表中的最后一个元素C. 在单链表第一个元素前插入一个新元素D. 在单链表最后一个元素后插入一个新元素15.16.17.有8个结点的有向完全图有（）条边。

数据结构大作业一、大作业的性质和目的数据结构大作业是对软件设计的综合训练，包括问题分析、总体设计、用户界面设计、程序设计基本技能和技巧，以至一套软件工作规范的训练和科学作风的培养。

在数据结构实验中，完成的只是单一而“小”的算法，而本课程设计是对学生的整体编程能力的锻炼。

数据结构大作业的目的是训练学生对问题的抽象能力和算法的运用能力。

二、大作业安排每位同学独立完成，可自选题目或根据选择后面的一个参考题目来完成。

开学第一周统一提交到教学在线。

提交的内容包括：(1)设计报告文档。

该文档是评分的重要依据之一，请认真对待。

该文档包括如下内容：●需求分析： (陈述要解决的问题，要实现的功能),●详细设计：包括设计算法流程图、算法分析、使用的数据结构（要求详细论证）；●软件测试：包括测试数据和测试结果记录●总结：设计过程中遇到的问题及解决方法；尚未解决的问题及考虑应对的策略；收获和心得；(2)源代码。

要求注释清晰，编写规范，模块化。

(3)可运行的exe文件。

要求充分测试，在XP操作系统中能正常运行。

以上内容打包后提交到教学在线。

三、考核和成绩评定老师根据设计文档、源代码和可执行文件，进行判分。

对于出现以下情况的学生，要求统一进行答辩：●执行文件无法正常运行。

●源程序疑似抄袭。

如果有发现两个同学的代码相类似则需要共同出席答辩。

如果判定抄袭，则为不及格。

开发过程可以部分复用网上的开源代码，但必须体现自己的工作，如果没有自己工作的部分，同样判为抄袭。

五、题目（任选其中之一或自拟）1. 数字化校园（1）设计华南理工大学的校园平面图，至少包括10个以上的地点，每两个地点间可以有不同的路，且路长可能不同。

以图中顶点表示校内各地点，存放名称、代号、简介等信息；用边表示路径，存放路径长度等相关信息。

（2）提供图中任意地点相关信息的查询。

（3）提供图中任意地点的问路查询，即查询任意两个地点之间的一条最短路径。

（4）学校要新建一间超市，请为超市选址，实现总体最优。

数据结构（第3版）习题答案⼗⼆五普通⾼等教育国家级本科规划教材第1章绪论⾼等学校精品资源共享课程1.1什么是数据结构？【答】：数据结构是指按⼀定的逻辑结构组成的⼀批数据，使⽤某种存储结构将这批数据存储于计算机中，并在这些数据上定义了⼀个运算集合。

1.2数据结构涉及哪⼏个⽅⾯？【答】：数据结构涉及三个⽅⾯的内容，即数据的逻辑结构、数据的存储结构和数据的运算集合。

1.3两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有⼀个运算的定义不⼀样，它们是否可以认作是同⼀个数据结构？为什么？【答】：不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是不⼀样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不⼀样，所以它们是两种不同的数据结构。

1.4线性结构的特点是什么？⾮线性结构的特点是什么？【答】：线性结构元素之间的关系是⼀对⼀的，在线性结构中只有⼀个开始结点和⼀个终端结点，其他的每⼀个结点有且仅有⼀个前驱和⼀个后继结点。

⽽⾮线性结构则没有这个特点，元素之间的关系可以是⼀对多的或多对多的。

1.5数据结构的存储⽅式有哪⼏种？【答】：数据结构的存储⽅式有顺序存储、链式存储、散列存储和索引存储等四种⽅式。

1.6算法有哪些特点？它和程序的主要区别是什么？【答】：算法具有（1）有穷性（2）确定性（3）0个或多个输⼊（4）1个或多个输出（5）可⾏性等特征。

程序是算法的⼀种描述⽅式，通过程序可以在计算机上实现算法。

1.7抽象数据类型的是什么？它有什么特点？【答】：抽象数据类型是数据类型的进⼀步抽象，是⼤家熟知的基本数据类型的延伸和发展。

抽象数据类型是与表⽰⽆关的数据类型，是⼀个数据模型及定义在该模型上的⼀组运算。

对⼀个抽象数据类型进⾏定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。

⼀旦定义了⼀个抽象数据类型及具体实现，程序设计中就可以像使⽤基本数据类型那样，⼗分⽅便地使⽤抽象数据类型。

北京语言大学22春“计算机科学与技术”《数据结构》作业考核题库高频考点版（参考答案）一.综合考核(共50题)1.设计一个判别表达式中左、右括号是否配对出现的算法，采用()数据结构最佳。

A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈参考答案：D2.串是一种特殊的线性表，其特殊性体现在___。

A.数据元素是一个字符B.数据元素可以是多个字符C.可以顺序存储D.可以链式存储参考答案：A3.若有18个元素的有序表存放在一堆数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A3的比较序列的下标依次为()。

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

A.3,2,5,8,6B.3,2,5,6,8参考答案：B5.设有以下四种排序方法，则()的空间复杂度最大。

A.冒泡排序B.快速排序C.堆排序D.希尔排序参考答案：B6.设一组初始记录关键字序列为(345,253,674,924,627)，则用基数排序需要进行___趟的分配和回收才能使得初始关键字序列变成有序序列。

A.8B.5C.4D.3参考答案：D7.栈的插入和删除操作在___进行。

A.栈顶B.栈底C.指定位置D.任意位置参考答案：A8.栈和队列的共同点是()。

A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点9.设数据结果A=(D，R)，其中D={1，2，3，4}，R={r}，r={，，，}，则数据结构A是___。

A.集合B.线性结构C.树型结构D.图型结构参考答案：D10.由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为___。

A.71B.53C.48D.24参考答案：A11.稀疏矩阵压缩后，必会失去()功能。

A.顺序存储B.随机存储C.输入输出D.以上都不对参考答案：B12.线性表是具有n个()的有限序列。