数据结构习题-带答案-12-13-2讲解

习题课填空1、对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为，双亲结点的编号为。

2、向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。

3、在一棵二叉树中，若双分支结点数为5个，单分支结点数为6个，则叶子结点数为个。

4、为了实现折半查找，线性表必须采用方法存储。

顺序5、一种抽象数据类型包括数据对象和。

6、在以L为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为__________和_______。

7、数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。

8、队列的插入操作在进行，删除操作在进行。

9、二叉搜索树的中序遍历得到的结点序列为____ ____。

10、在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。

11、栈的特点是。

12、在单链表中，除了首元结点外，任一结点的存储位置由。

13、在一个具有n个顶点的无向图中，要连通所有顶点则至少需要条边。

14、深度为k（设根的层数为1）的完全二叉树至少有个结点，至多有个结点。

15、一棵深度为6的满二叉树有个分支结点和个叶子结点。

16、一个算法的效率可分为效率和效率。

17、队列的特点是。

18、一棵深度为5的满二叉树中的结点数为个。

19、在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。

简答题1、已知一组元素为（38，26，62，94，35，50，28，55），画出按元素排列顺序输入生成的一棵二叉搜索树。

答:2、假设有二维数组A[0..5,0..7]，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000，计算：（1）末尾元素A57的第一个字节地址为；（2）若按列存储时，元素A47的第一个字节地址为。

(3) 数组A的体积（存储量）；(4) 若按行存储时，元素A14的第一个字节地址为。

第一章1．在数据结构中，从逻辑上可以把数据结构分为(C )A．动态结构和静态结构B。

紧凑结构和非紧凑结构C．线性结构和非线性结构D。

内部结构和外部结构● 2.在数据结构中，与所使用的计算机无关的是( A )A。

逻辑结构 B. 存储结构C。

逻辑和存储结构 D. 物理结构3。

下面程序的时间复杂度为____O(mn）_______。

for (int i=1；i〈=m; i++）for （int j=1；j〈=n；j++ ）S+=i第二章线性表●链表不具备的特点是（A)A 可以随机访问任一结点（顺序）B 插入删除不需要移动元素C 不必事先估计空间D 所需空间与其长度成正比2。

不带头结点的单链表head为空的判定条件为（A )，带头结点的单链表head为空的判定条件为（B ）A head==nullB head—〉next==nullC head-〉next==headD head！=null●3.在线性表的下列存储结构中,读取元素花费时间最少的是（D)A 单链表B 双链表C 循环链表D 顺序表● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为（C）A 顺序表B 用头指针表示的单循环链表C 用尾指针表示的单循环链表D 单链表●5。

在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序，则操作的时间复杂度为（ D ）A O(1）B O(log2n)C O(n2)D O(n）● 6.在一个长度为n （n〉1）的单链表上，设有头和尾两个指针，执行（B）操作与链表的长度有关A 删除单链表中第一个元素B 删除单链表中最后一个元素C 在第一个元素之前插入一个新元素D 在最后一个元素之后插入一个新元素●7。

与单链表相比，双向链表的优点之一是（D)A 插入删除操作更简单B 可以进行随机访问C 可以省略表头指针或表尾指针D 顺序访问相邻结点更容易●8。

若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域（头结点的地址）中存放的是（ B )A list的地址B list的内容C list指的链结点的值D 链表第一个链结点的地址●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针,则（ B )A list2比list1占用更多的存储单元B list1与list2占用相同的存储单元C list1和list2应该是相同类型的指针变量D 双向链表比单链表占用更多的存储单元10。

数据结构习题及参考答案一、概述在计算机科学领域，数据结构是指组织和存储数据的方式，以便于有效地访问和操作。

它是计算机算法和程序设计的基础。

下面将介绍一些常见的数据结构习题，并提供相应的参考答案，帮助读者更好地理解和掌握数据结构。

二、数组1. 习题：给定一个数组，编写一个函数来计算数组中元素的和。

【参考答案】```pythondef sum_array(arr):sum = 0for num in arr:sum += numreturn sum```三、链表1. 习题：给定一个链表，反转链表，并返回反转后的头节点。

【参考答案】```pythonclass ListNode:def __init__(self, val=0, next=None): self.val = valself.next = nextdef reverse_linked_list(head):prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prev```四、栈和队列1. 习题：使用栈实现队列的功能。

【参考答案】```pythonclass MyQueue:def __init__(self):self.stack1 = []self.stack2 = []def push(self, x):self.stack1.append(x)def pop(self):if not self.stack2:while self.stack1:self.stack2.append(self.stack1.pop())return self.stack2.pop()def peek(self):if not self.stack2:while self.stack1:self.stack2.append(self.stack1.pop())return self.stack2[-1]def empty(self):return len(self.stack1) == 0 and len(self.stack2) == 0 ```五、树1. 习题：给定一个二叉树，判断它是否是高度平衡的。

习题1 参考答案1至8题答案略。

9.（1）【解】该逻辑结构为线性结构，其图形表示如下：（2）【解】该逻辑结构为树型结构，其图形表示如下：（3）【解】该逻辑结构为图型结构，其图形表示如下：（4）【解】该逻辑结构为线性结构，其图形表示如下：10.【解】该图书库存管理系统所要处理的数据对象为图书，所以该问题中涉及的数据元素为图书，设数据元素类型为bookType 类型。

每个数据元素应包含的数据项有图书编号、书名、作者、出版社、出版日期等。

可用一个表格（如下表）的形式表示图书间的逻辑关系，即该问题数学模型可采用简单的线性结构来表示。

根据问题需求功能目标，此模型的所需的主要处理操作有插入、删除、查找和修改等基本操作。

所以，现用抽象数据类型bookList 表示问题模型，其逻辑结构与基本操作的定义如下： （1）逻辑结构bookList=( D, {r} )D={b i | b i 为bookType 类型的元素，i=1,2,3, ....., n ，n ≥0} r ={ <bk i ,b i+1>| i=1,2,…, n -1, n ≥0 } （2）基本操作 ①初始化操作函数：InitBookList(&BL)。

……初始条件：图书表BL 不存在。

操作结果：构造一个空的图书表BL 。

②求图书表长度操作函数：bookListLength(BL)。

初始条件：图书表BL 已存在。

操作结果：返回图书表BL 中所包含的数据元素（图书）的个数。

③取图书表中元素操作函数：getBook(BL, i, &b)。

初始条件：图书表BL 已存在，且1≤i ≤bookListLength(BL)。

操作结果：用b 返回图书表BL 中的第i 个数据元素的值。

④按编号查找操作函数：locateById(BL, id)。

初始条件：图书表BL 已存在，id 是给定的一个图书编号。

操作结果：返回图书表BL 中图书编号为id 的数据元素的位序，若这样的数据元素不存在，则返回0。

数据结构习题及解答第1章概述【例1-1】分析以下程序段的时间复杂度。

for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;解：该程序段的时间复杂度为O(m*n)。

【例1-2】分析以下程序段的时间复杂度。

i=s=0; ①while(s<n){ i++; ②s+=i; ③}解：语句①为赋值语句，其执行次数为1次，所以其时间复杂度为O(1)。

语句②和语句③构成while循环语句的循环体，它们的执行次数由循环控制条件中s与n的值确定。

假定循环重复执行x次后结束，则语句②和语句③各重复执行了x次。

其时间复杂度按线性累加规则为O(x)。

此时s与n满足关系式：s≥n，而s=1+2+3+…+x。

所以有：1+2+3+…+x ≥n，可以推出：x=x与n之间满足x=f(），所以循环体的时间复杂度为O()，语句①与循环体由线性累加规则得到该程序段的时间复杂度为O(）。

【例1-3】分析以下程序段的时间复杂度。

i=1; ①while(i<=n)i=2*i; ②解：其中语句①的执行次数是1，设语句②的执行次数为f(n)，则有：。

得：T（n）=O()【例1-4】有如下递归函数fact(n)，分析其时间复杂度。

fact(int n){ if(n<=1)return(1); ①elsereturn(n*fact(n-1)); ②}解：设fact（n）的运行时间函数是T(n)。

该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+ O(1)，其中O(1)为常量运行时间。

由此可得fact（n）的时间复杂度为 O(n)。

习题1一、单项选择题1. 数据结构是指（1. A ）。

A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2. C ）。

A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3. 树形结构是数据元素之间存在一种（3. D ）。

数据结构练习题第一部分绪论一、单选题1. 一个数组元素a[i]与________的表示等价。

A、 *(a+i)B、 a+iC、 *a+iD、 &a+i2. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。

A、参数类型B、参数个数C、函数类型3. 若需要利用形参直接访问实参，则应把形参变量说明为________参数A、指针B、引用C、值4. 下面程序段的时间复杂度为____________。

for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A、 O(m2)B、 O(n2)C、 O(m*n)D、 O(m+n)5. 执行下面程序段时，执行S语句的次数为____________。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/26. 下面算法的时间复杂度为____________。

int f( unsigned int n ) {if ( n==0 || n==1 ) return 1; else return n*f(n-1);}A、 O(1)B、 O(n)C、 O(n2)D、 O(n!)二、填空题1. 数据的逻辑结构被分为__________、_________、__________和__________四种。

2. 数据的存储结构被分为__________、_________、__________和__________四种。

3. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。

4. 一种抽象数据类型包括__________和__________两个部分。

5. 当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。

1 第一章概论 一、填空题

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

2、一个算法具有5个特性: 有穷性 、确定性、可行性，有零个或多个输入、有一个或多个输出 。 3、 数据结构包括数据的 逻辑结构 、存储结构 和 运算（或基本操作）这三个方面的内容。 4、数据结构中评价算法的两个重要指标是 时间 效率和 空间 效率。

5、一个数据结构在计算机中的表示称为 存储结构 。 6、从逻辑上可以把数据结构分为线性结构、非线性结构两大类 7、数据逻辑结构除了集合以外，还包括线性结构、树形结构和 图形结构 。 8、数据的存储结构形式包括顺序存储、链式存储、索引存储和 散列存储。 9、数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的内容。 10、算法效率的度量可以分为事先估算和 事后统计法 。

二、单项选择题 1、 数据结构中，与所使用的计算机无关的是数据的是（ C ）； A、 存储结构 B、 物理结构 C、逻辑结构 D、 物理和逻辑结构 2、算法分析的目的是（ C ） A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 3、 计算机算法指的是（ C ） A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 4、 计算机算法必须具备输入、输出和（ B ）等5个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 5、从逻辑上可以把数据结构分为（ C ）两大类。 A）动态结构、静态结构 B）顺序结构、链式结构 C）线性结构、非线性结构 D）初等结构、构造型结构 6、下列数据中，（ C ）是非线性数据结构。 A．栈 B. 队列 C. 完全二叉树 D. 堆 7、算法分析的两个主要方面是（ A ）。 A) 空间复杂性和时间复杂性 B) 正确性和简明性 2

数据结构习题及参考答案部门： xxx时间： xxx整理范文，仅供参考，可下载自行编辑数据结构习题及参考答案一、判断下列叙述的对错。

<1）线性表的逻辑顺序与物理顺序总是一致的。

<2）线性表的顺序存储表示优于链式存储表示。

<3）线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

<4）二维数组是其数组元素为线性表的线性表。

<5）每种数据结构都应具备三种基本运算：插入、删除和搜索。

二、设单链表中结点的结构为typedef struct node { file://链表结点定义ElemType data； file://数据struct node * Link； file://结点后继指针} ListNode；<1）已知指针p所指结点不是尾结点，若在*p之后插入结点* s，则应执行下列哪一个操作？A. s->link = p； p->link = s；B. s->link = p->link； p->link = s；C. s->link = p->link； p = s；D. p->link = s； s->link = p；<2）非空的循环单链表first的尾结点<由p所指向）满足：A. p->link == NULL；B. p == NULL；C. p->link == first；D. p == first；三、设有一个顺序栈S，元素s1， s2， s3， s4， s5， s6依次进栈，如果6个元素的出栈顺序为s2， s3， s4， s6， s5， s1，则顺序栈的容量至少应为多少？b5E2RGbCAP四、一棵具有n个结点的理想平衡二叉树<即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度h如何用n来表示<注意n可能为0）？p1 EanqFDPw五、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相应的括号内。

专业资料 word完美格式 习题1 一、单项选择题 1. 数据结构是指（ ）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（ ）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（ ）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++;

A.O(1) B.O(2n) C.O(n) D.O(3n) 5. 算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ ）。 A.低 B.高 C.相同 D.不好说 8. 数据结构作为一门独立的课程出现是在（ ）年。 A.1946 B.1953 C.1964 D.1968 9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（ ）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 10. 计算机内部数据处理的基本单位是（ ）。 A.数据 B.数据元素 C.数据项 D.数据库

数据结构习题及标准答案一、栈和队列1. 栈（Stack）是一种后进先出（Last-In-First-Out，LIFO）的数据结构。

栈的简单实现可以使用数组或链表，下面是一个使用数组实现的栈的示例代码：```pythonclass Stack:def __init__(self):self.stack = []def is_empty(self):return len(self.stack) == 0def push(self, item):self.stack.append(item)def pop(self):if self.is_empty():return Nonereturn self.stack.pop()def peek(self):if self.is_empty():return Nonereturn self.stack[-1]```2. 队列（Queue）是一种先进先出（First-In-First-Out，FIFO）的数据结构。

队列的简单实现也可以使用数组或链表，下面是一个使用链表实现的队列的示例代码：```pythonclass Queue:def __init__(self):self.queue = []def is_empty(self):return len(self.queue) == 0def enqueue(self, item):self.queue.append(item)def dequeue(self):if self.is_empty():return Nonereturn self.queue.pop(0)def peek(self):if self.is_empty():return Nonereturn self.queue[0]```二、链表1. 链表（Linked List）是一种常见的线性数据结构。

链表由节点组成，每个节点包含数据和指向下一个节点的指针。

数据结构习题课（2012）复习重点1.数据结构的概念，逻辑结构、物理结构的概念及各⾃包含的内容2.算法的特性、设计要求，如何度量算法的时间效率。

3.线性表的顺序/链式存储结构的特点，插⼊、删除算法。

4.栈和队列的逻辑特性，顺序栈的⼊栈/出栈、循环队列的⼊队/出队算法。

5.以三元组顺序表存放的稀疏矩阵的转置算法。

6.⼆叉树的性质及其四种遍历算法。

7.森林与⼆叉树的相互转换。

8.WPL、前缀编码的概念，哈夫曼树的构造算法。

9.图的相关概念，邻接矩阵及邻接表的存储结构。

10.图的深度优先/⼴度优先遍历算法。

11.最⼩⽣成树的两种算法。

12.拓扑排序的意义和算法。

13.最短路径算法。

14.顺序表、有序表的查找算法。

15.⼆叉排序树的性质、插⼊/删除算法、平衡⼆叉树的性质、插⼊算法。

16.哈希表的相关概念，常⽤的冲突处理⽅法。

17.直接插⼊排序、希尔排序、快速排序、堆排序、归并排序的算法。

注意：1.上述每个知识点可能会以任何题型出现，复习的时候别把它们当做“简答题”来复习。

2.红⾊（下划线）标识的知识点或算法，只要求对给出的初始数据，能画出结果则可。

其他的算法则可能会出现在“算法题”中。

⾃测题第1章绪论⼀、判断1.顺序存储⽅式只能⽤于存储线性结构。

（错）2.顺序查找法适⽤于存储结构为顺序或链式存储的线性表。

（对）⼆、选择1.计算机算法必须具备输⼊、输出、（ B ）等5个特性。

A.可⾏性、可移植性和可扩展性B.可⾏性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、安全性和稳定性2.算法在发⽣⾮法操作时可以作出处理的特性称为（C ）。

A.正确性B.易读性C.健壮性D.可靠性3.数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的（A ）以及它们之间的（ B ）和运算的学科。

A.操作对象B.计算⽅法C.逻辑存储D.数据映像A.结构B.关系C.运算D.算法4.在数据结构中，逻辑上数据结构可分为：（B ）A.动态结构和静态结构B.线性结构和⾮线性结构C.紧凑结构和⾮紧凑结构D.内部结构和外部结构5.数据结构主要研究数据的（D ）A.逻辑结构B.存储结构C.逻辑结构和存储结构D.逻辑结构和存储结构及其运算的实现6.为了描述n个⼈之间的同学关系，可⽤（C ）结构表⽰A.线性表B.树C.图D.队列7.下⾯的程序段违反了算法的（A ）原则void sam(){ int n=2;while (!odd(n)) n+=2;printf(n);}A.有穷性B.确定性C.可⾏性D.健壮性三、问答1.什么是逻辑结构和物理结构？各⾃包含哪⼏种？2.线性结构和树型结构的特点分别是什么？3.简述顺序存储结构与链式存储结构在表⽰数据元素之间关系上的只要区别。

数据结构第二章参考答案习题21. 填空题（1）在一个单链表中，已知每个结点包含data和next两个域，q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（___________）和（___________）操作。

答案：q->next = s; s->next = p; 或 s->next=q->next; q->next = s; （2）表长为n的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（___________），删除一个元素需要移动元素的平均个数为（___________）。

答案：n/2 (n-1)/2（3）表长为0的线性表称为（___________）。

答案：空表（4）动态内存管理是操作系统的基本功能之一，其作用是响应用户程序对内存的（___________）和（___________）请求。

答案：申请释放（5）顺序表多采用（___________）实现的，是一种随机存取结构，对表中任意结点存取操作的时间复杂度为（___________）。

而查找链表中的结节，需要从头指针起顺着链扫描才能得到，平均时间复杂度为（___________）。

因此，若线性表的操作主要是进行查找，很少进行插入或删除操作时，采用（___________）表比较合适。

答案：数组 O(1) O(n) 顺序（6）在链表某个位置上进行插入和删除操作，只需要修改（___________）即可，而无须移动大量元素，操作的时间复杂度为（___________）。

而在顺序表中进行插入和删除操作，往往要移动大量元素，平均移动元素的数目为（___________），平均时间复杂度为（___________）。

因此，若对线性表进行频繁的插入和删除操作时，采用（___________）表相对合适。

若插入和删除主要发生在表头和表尾，则采用（___________）表更为合适。

数据结构试题及答案1. 描述一个求解问题的抽象数据类型由？两部分组成。

[填空题] *_________________________________(答案：数据逻辑结构和抽象运算)2. 算法具有？5个重要特征 [填空题] *_________________________________(答案：有穷性、确定性、可行性、输入和输出)3. 一个数据结构在计算机中的？称为存储结构 [填空题] *_________________________________(答案：映像)4. 通常从四个方面评价算法的质量？ [填空题] *_________________________________(答案：正确性、易读性、强壮性、高效率(正确易读,强壮高效))5. 算法的时间复杂度取决于？ [填空题] *_________________________________(答案：问题的规模和待处理数据的初态)6. 在分析算法的时间复杂度时，通常认为算法的执行时间是？的函数 [填空题] *_________________________________(答案：问题规模)7. 数据结构是一门研究程序设计中数据的元素以及他们之间的？等的学科 [填空题] *_________________________________(答案：关系和运算)8. 算法分析的主要任务之一是？ [填空题] *_________________________________(答案：算法的执行时间和问题规模之间的关系)9. 算法分析的目的是？ [填空题] *_________________________________(答案：分析算法的效率以求改进)10. 数据逻辑结构、数据元素、数据项在计算机中的映像分别称为？ [填空题] *_________________________________(答案：存储结构、结点和数据域)11. 在一个长度为n的顺序表(1<=i)中插入第i个元素时需向后移动？个元素，删除第i个元素需向前移动？个元素，时间复杂度都为？。

数据结构习题附答案第一题：给定一个数组arr，编写一个函数，将数组中的所有奇数移动到数组的前半部分，偶数移动到数组的后半部分，并返回修改后的数组。

解答：```pythondef move_odd_even(arr):left = 0right = len(arr) - 1while left < right:if arr[left] % 2 == 0 and arr[right] % 2 == 1:arr[left], arr[right] = arr[right], arr[left]if arr[left] % 2 == 1:left += 1if arr[right] % 2 == 0:right -= 1return arr```第二题：给定一个字符串s，编写一个函数，判断其是否为有效的括号字符串。

只包含'('、')'、'{'、'}'、'['、']'，字符串中的括号必须按照合法的顺序闭合。

解答：```pythondef is_valid_parentheses(s):stack = []parentheses = {')': '(', ']': '[', '}': '{'}for char in s:if char in parentheses.values():stack.append(char)elif char in parentheses.keys():if not stack or parentheses[char] != stack.pop():return Falsereturn not stack```第三题：给定一个二叉树的根节点root，编写一个函数，判断该二叉树是否是对称的。

第1章绪论练习题答案判断题1. 数据元素是数据的最小单位。

( × )2. 记录是数据处理的最小单位。

(× )3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。

(× )4．算法的优劣与算法描述语言无关，但与所用计算机有关。

(× )5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。

(√)6．数据的物理结构是指数据在计算机内的实际存储形式。

(√ )7. 数据结构的抽象操作的定义与具体实现有关。

(× )第2章线性表练习题答案一、填空1. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。

2. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。

3. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。

4. 在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。

5．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1)，在给定值为x的结点后插入一个新结点的时间复杂度为O(n)。

二、判断正误（×）1. 链表的每个结点中都恰好包含一个指针。

答：错误。

链表中的结点可含多个指针域，分别存放多个指针。

例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（×）2. 链表的物理存储结构具有同链表一样的顺序。

错，链表的存储结构特点是无序，而链表的示意图有序。

（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

错，链表的结点不会移动，只是指针内容改变。

（×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。

数据结构试题及答案⼀、判断1.带表头节点的双向循环链表为空时，表头的前驱和后继指针指向HEAD。

2.带表头结点的双向链表为空时，表头的前趋和后继指针分别指向NULL。

3.带表头结点的双向循环链表为空时，表头的前驱和后继指针分别指向NULL4.环形链表是线性结构，⾸尾相连，使⽤连续地址储存。

5.环形队列是线性结构，但它不是环形，利⽤特殊的循环算法解决“假溢出”。

6.环形队列是线性结构，象循环链表⼀样头尾相连接，它能解决“假溢出”。

7.环形队列是线性结构，能利⽤特殊的循环算法解决“假溢出”。

8.⼴义表E（a ，E）的表长是2，表深度是⽆穷⼤。

9.⼴义表E（a ，E）的表深度是2，表长是2。

10.⼴义表G（a ，G）的表深度是2，表长是2。

11.⼴义表G（a ，G）的深度是2，表长是2。

12.满BT是特殊的BT树，它的定义是递归的。

13.BT是特殊的树，它的定义是递归的。

14.平衡树是特殊的BT树，它的定义是递归的。

15..若已知BT的先根序和中根序、后根序和中根序，可唯⼀确定⼀个BT。

16.若已知BT的先根序遍历和后根序遍历，可唯⼀确定⼀个BT。

17.平衡BT是特殊的BT，它的定义是递归的。

18.BST是特殊的BT，它的中序遍历是有序的。

19.何时使⽤PRIM法，何时使⽤KRUSKAL法取决于图是稀疏还是稠密20.PRIM和KRUSKAL均可以对图求MST，但是PRIM法⽅便。

21.希尔排序是插⼊排序的变型，插⼊排序是稳定的，但希尔排序是不稳定的。

22.希尔排序是插⼊排序的变型。

插⼊排序是稳定的，所以希尔排序是稳定的。

23.快速排序的稳定性取决于枢轴的选择。

24.快速排序的枢轴有多种选择⽅法，取⾸尾节点是较简单的做法。

25.冒泡排序不但稳定，⽽且速度很快。

⼆、名词解释与问答26.线性结构:唯⼀的⾸节点，唯⼀的尾节点，除⾸尾外其它节点既有前驱也有后继，⾸⽆前驱，尾⽆后继。

27.线性结构中端操作受限的含义是什么？操作仅在指定的位置。

数据结构习题标准答案————————————————————————————————作者：————————————————————————————————日期：计算机科学与工程学院二OO五年三月目录第一章绪论 (5)第二章线性表 (7)第三章栈和队列 (11)第三章串 (12)第五章数组与广义表 (14)第六章树和二叉树 (16)第七章图 (20)第八章查找 (24)第九章内部排序 (26)第一章绪论1.2.3 综合题 14、设n 为正整数。

试确定下列各程序段中前置以记号@的语句的频度：(1)i = 1; k = 0;While(i<=n - 1) {@ k + = 10 * I ;i ++;}答：n-1(2)i = 1; k = 0;do {@ k + = 10 * I ;i ++;} while (I< = n - 1);答：n-1(3)i = 1; k = 0;While (i<=n - 1) {i ++;@ k + = 10 * i ;}答：n-1(4)k = 0;for ( i = 1;i<=n ;i++) {for ( j = i;j<=n ;j++)@ k + +;}答：(n+1)*n/2(5)for( i = 1;i<=n ;i++) {for( j = i;j<=n ;j++) {for( k = 1;k<=j ;k++)@ x + = delta;}答：1/6*n*(n+1)*( n+2)(6)i=1;j=0;While (i+j<= n){@ if (i>j) j++;else i++;}答：n(7)x= n; y= o;while (x>=(y+1) * (y + 1)){@ y ++;}答：⎣√ n ⎦(8)x= 91; y= 100;while (y>0){@ if (x>100){x-=10; y - -; }else x ++ ;}答：11001.2.3 综合题20、void print_descending(int x,int y,int z)//按从大到小顺序输出三个数{scanf("%d,%d,%d",&x,&y,&z);if(x<y) x<->y; //<->为表示交换的双目运算符,以下同if(y<z) y<->z;if(x<y) x<->y; //冒泡排序printf("%d %d %d",x,y,z);}//print_descending1.2.3 综合题22试编写算法，计算i !. 2i的值并存入数组a[0…arrsize - 1] 的第i- 1个分量中（I= 1,2,….,n）。