大工2020年春《数据结构》在线作业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个元素的地址是（）。

数据结构作业答案(大连理工大学)数据结构作业答案入栈和出栈操作是栈这种数据结构最基本的操作，也是我们在日常生活中常常会用到的操作。

本文将为您介绍如何使用Python实现栈的数据结构，以及解答大连理工大学数据结构作业中与栈相关的问题。

一、栈的概念和基本操作栈是一种具有特殊限制的线性表，它只允许在表的一端进行插入和删除操作。

栈遵循先进后出（Last In First Out，LIFO）的原则。

通常，栈顶为允许插入和删除的一端，而另一端则称为栈底。

1.1 栈的初始化在Python中，我们可以使用列表(list)来实现栈的数据结构。

下面的代码演示了如何初始化一个栈：```pythonstack = []```1.2 入栈操作入栈操作是将一个元素添加到栈顶的操作。

在Python中，我们可以使用列表的append()方法来实现入栈操作。

下面的代码演示了如何进行入栈操作：```pythonstack.append(element)```1.3 出栈操作出栈操作是将栈顶元素删除并返回的操作。

在Python中，我们可以使用列表的pop()方法来实现出栈操作。

下面的代码演示了如何进行出栈操作：```pythonelement = stack.pop()```二、栈的应用举例2.1 判断括号匹配一个常见的栈的应用是判断括号是否匹配。

在这个问题中，我们需要使用栈来跟踪括号的开闭情况。

具体的算法如下：①初始化一个空栈。

②遍历字符串中的每个字符。

③如果遇到开括号（例如：'('、'{'、'['），则将其入栈。

④如果遇到闭括号（例如：')'、'}'、']'），则判断栈顶元素是否为相应的开括号，如果不匹配，则返回False。

⑤字符串遍历完成后，如果栈为空，则说明所有括号都匹配，返回True；否则，返回False。

下面是一个基于栈的括号匹配问题的示例代码：```pythondef is_valid_parentheses(s: str) -> bool:stack = []parentheses_map = {')': '(', '}': '{', ']': '['}for char in s:if char in parentheses_map.values():stack.append(char)elif char in parentheses_map.keys():if not stack or parentheses_map[char] != stack.pop():return Falsereturn not stack```2.2 栈的逆序输出另一个栈的常见应用是逆序输出。

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

数据结构习题集答案第1章绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3 设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。

解：1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

解：ADT Complex{数据对象：D={r,i|r,i 为实数}数据关系：R={<r,i>}基本操作：InitComplex(&C,re,im)操作结果：构造一个复数C ，其实部和虚部分别为re和imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e返回复数C的第k元的值Put(&C,k,e)操作结果：改变复数C的第k元的值为eIsAscending(C)操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADT ComplexADT RationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和m DestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber1.5 试画出与下列程序段等价的框图。