当前位置：文档之家 › 复习总结资料(数据结构导论)

复习总结资料(数据结构导论)

  • 格式：docx
  • 大小：347.26 KB
  • 文档页数：13

《数据结构导论》复习资料课程代码：02142一、单项选择题1．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是A．不确定 B．n-i+1 C．i D．n-i2．具有N个结点的二叉树的二叉链表结构中，指针域为NULL的数目应为A． N B．2N C．N+1 D．2N+13．栈S最多能容纳4个元素。

现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列?A．(E、D、C、B、A、F) B．(B、C、E、F、A、D)C．(C、B、E、D、A、F) D．(A、D、F、E、B、C)4．已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？A．s->next = p； p-> next = s； B．s-> next = p->next； p-> next = s；C．s-> next = p-> next； p = s； D． p-> next = s； s-> next = p；5．设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是A．head->next==head B．head->next==NULLC．head!=NULL D．head==NULL6．一个队列的输入序列是A，B，C，D，则该队列的输出序列是A．A，B，C，D B．B，C，D，AC．D，C，B，A D．C，D，B，A7．以行序为主序的二维数组a［3］［5］中，第一个元素a［0］［0］的存储地址是100，每个元素占2个存储单元，则a［1］［2］的存储地址是A．100 B．108 C．114 D．1168．二叉树的中序遍历序列中，结点P排在结点Q之前的条件是A．在二叉树中P在Q的左边B．在二叉树中P在Q的右边C．在二叉树中P是Q的祖先D．在二叉树中P是Q的子孙9．有10个顶点的无向完全图的边数是A．11 B．45 C．55 D．9010．在带权有向图中求两个结点之间的最短路径可以采用的算法是A．迪杰斯特拉（Dijkstra）算法B．克鲁斯卡尔（Kruskal）算法C．普里姆（Prim）算法D．深度优先搜索（DFS）算法11．利用双向链表作线性表的存储结构的优点是A．便于单向进行插入和删除的操作B．便于双向进行插入和删除的操作C．节省空间D．便于销毁结构释放空间12．在闭散列表中，散列到同一个地址而引起的“堆积”问题是引起的。

A．同义词之间发生冲突 B．非同义词之间发生冲突C．同义词之间或非同义词之间发生冲突D．散列表“溢出”13．假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为A．front+1==rear B．rear+1==frontC．front==0 D．front==rear14．10阶上三角矩阵压缩存储时需存储的元素个数为A．11 B．56 C．100 D．10115．深度为k（k≥1）的二叉树，结点数最多有A．2k个 B．(2k -1)个 C．2k-1个 D．(2k+1)个16．具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为A．11 B．13 C．23 D．2517．顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值不相同。

用顺序查找法查找时，平均比较次数约为A．20000 B．30000 C．40000 D．60000 18．外存储器的主要特点是A．容量小和存取速度低B．容量大和存取速度低C．容量大和存取速度高D．容量小和存取速度高19．以下关于广义表的叙述中,正确的是A．广义表是由0个或多个单元素或子表构成的有限序列B．广义表至少有一个元素是子表C．广义表不能递归定义D．广义表不能为空表20．树形结构中，度为0的结点称为A．树根 B．叶子C．路径 D．二叉树21．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>，<V1,V3>，<V1,V4>，<V2,V5>，<V3,V5>,<V3,V6>，<V4,V6>，<V5,V7>,，<V6,V7>}，则图G的拓扑序列是A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V722．有关图中路径的定义，表述正确的是A．路径是顶点和相邻顶点偶对构成的边所形成的序列B．路径是不同顶点所形成的序列C．路径是不同边所形成的序列D．路径是不同顶点和不同边所形成的集合23．组成数据的基本单位是A．数据项 B．数据类型C．数据元素 D．数据变量24．与串的逻辑结构不同的．．．数据结构是A．线性表 B．栈C．队列 D．树25．设单链表中指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为A．p->next=p->next->next B．p=p->nextC．p=p->next->next D．p->next=p26．设字符串S1=″ABCDEFG″，S2=″PQRST″，则运算S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2))后S的结果为A．″BCQR″ B．″BCDEF″C．″BCDEFG″ D．″BCDEFEF″27．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并且A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则使其平衡的调整方法为A．LL型 B．LR型C．RL型 D．RR型28．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。

这是哪种排序方法的基本思想？A．堆排序 B．直接插入排序 C．快速排序 D．冒泡排序29．下面关于串的叙述中，是不正确的。

A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储30．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是A．edcba B． decba C．dceab D．Abcde31．有向图中，所有顶点入度和是所有顶点出度和的倍。

A．0.5 B．1 C． 2 D．432．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行A．q->next=p->next; p->next=q; B．p->next=q->next; q=p;C．p->next=p->next; q->next=q; D．p->next=q->next; q->nxet=p;33．下列描述中正确的是A．数据元素是数据的最小单位B．数据结构是具有结构的数据对象C．数据结构是指相互之间存在一种或多种特定关系的数据元素的集合D．算法和程序原则上没有区别，在讨论数据结构时两者是通用的34．归并排序的时间复杂度是A．O（n2） B．O（nlog2n） C．O（n） D．O（log2n）35．顺序存储的表中有90000个元素，已按关键字值升序排列，假设对每个元素进行查找的概率相同，且每个元素的关键字值皆不相同，用顺序查找法查找时，需平均比较的次数为A．25000 B．30000 C．45000 D．9000036．散列文件是一种A．顺序文件 B．索引文件 C．链接文件 D．计算寻址文件37．常用于函数调用的数据结构是A．栈 B．队列 C．链表 D．数组38．二维数组A［n］［m］以列优先顺序存储，数组A中每个元素占用1个字节，A［1］［1］为首元素，其地址为0，则元素A［i］［j］的地址为A．（i-1）×m+(j-1) B．(j-1)×n+(i-1)C．(j-1)×n+i D．j×n+i39．序列（21,19,37,5,2）经冒泡排序法由小到大排序，在第一次执行交换后所得结果为A．(19，21，37，5，2) B．(21，19，5，37，2)C．(21，19，37，2，5) D．(2，21，19，37，5)40．数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为A．索引存储方法B．顺序存储方法C．链式存储方法D．散列存储方法41．在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的A．直接前趋 B．直接后继 C．开始结点 D．终端结点42．一整数序列26，59，77，31，51，11，19，42，以二路归并排序从小到大排序，第一阶段的归并结果为A．31，51，11，42，26，77，59，19 B．26，59，31，77，11，51，19，42C．11，19，26，31，42，59，51，77 D．26，11，19，31，51，59，77，4243．某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为A．acbed B．becab C．deabc D．cedba44．在一个图中，所有顶点的度数之和与图的边数的比是A．1∶2 B．1∶1 C．2∶1 D．4∶145．含有n个结点的二叉树用二叉链表表示时，空指针域个数为A．n-1 B．n C．n+1 D．n+2参考答案：1-5 BCCBA 6-10 ACABA 11-15 BADBB 16-20 BBBAB 21-25 AACDA26-30 DBDBC 31-35 BDCBC 36-40 DABAD 41-45 BBDCC二、填空题46．有个10阶矩阵A，采用行序优先存储，每个元素占用1个字节的存储空间，A[0][0]的地址为1，则A[8][5]的地址为：。

47．广义表(a,(a,b),d,e,((i,j),k))的长度是。

48．若待散列的序列为(18,25,63,50,42,32,9)，散列函数为H(key)=key MOD 9，与18发生冲突的元素有个。

49．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为。

50．常用的存储表示方法有顺序存储和链式存储，其中存储表示方法插入和删除数据元素方便。

51．栈的特点是。

52．所有存储结点存放在一个连续的存储区里，利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。

合集下载

(完整版)数据结构知识点总结

(完整版)数据结构知识点总结

数据结构知识点概括第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位，可以由若干个数据项组成。

数据项是具有独立含义的最小标识单位。

数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。

·线性结构：一对一关系。

·线性结构：多对多关系。

·存储结构：是逻辑结构用计算机语言的实现。

·顺序存储结构：如数组。

·链式存储结构：如链表。

·索引存储结构：·稠密索引：每个结点都有索引项。

·稀疏索引：每组结点都有索引项。

·散列存储结构：如散列表。

·数据运算。

·对数据的操作。

定义在逻辑结构上，每种逻辑结构都有一个运算集合。

·常用的有：检索、插入、删除、更新、排序。

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

·结构类型：由用户借助于描述机制定义，是导出类型。

抽象数据类型ADT：·是抽象数据的组织和与之的操作。

相当于在概念层上描述问题。

·优点是将数据和操作封装在一起实现了信息隐藏。

程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。

算法取决于数据结构。

算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。

评价算法的好坏的因素：·算法是正确的；·执行算法的时间；·执行算法的存储空间（主要是辅助存储空间）；·算法易于理解、编码、调试。

时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。

渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。

评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。

算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。

时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。

数据结构期末复习重点知识点总结

数据结构期末复习重点知识点总结

数据结构期末复习重点知识点总结一、数据结构概述数据结构是计算机科学中一门关于数据组织、存储和管理的学科。

它涉及到各种数据类型和它们之间的关系，以及对这些数据类型进行有效操作和处理的算法。

二、基本数据结构1. 数组- 数组是一种线性数据结构，用于存储相同类型的数据元素。

- 数组的特点是随机访问和连续存储。

- 数组的插入和删除操作需要移动其他元素，时间复杂度为O(n)。

2. 链表- 链表是一种线性数据结构，通过节点之间的指针链接来组织数据。

- 链表的特点是插入和删除操作简单，时间复杂度为O(1)。

- 链表分为单链表、双向链表和循环链表等不同类型。

3. 栈- 栈是一种具有后进先出（LIFO）特性的数据结构。

- 栈的操作主要包括压栈（Push）和弹栈（Pop）两个操作。

- 栈常用于表达式求值、递归算法的实现等场景。

4. 队列- 队列是一种具有先进先出（FIFO）特性的数据结构。

- 队列的操作主要包括入队（Enqueue）和出队（Dequeue）两个操作。

- 队列常用于实现缓冲区、消息队列等场景。

5. 树- 树是一种非线性的数据结构，由节点和边组成。

- 树的节点具有层级关系，由根节点、子节点和叶节点等组成。

- 常见的树结构有二叉树、红黑树、B树等。

6. 图- 图是一种非线性的数据结构，由节点和边组成。

- 图的节点之间可以有多对多的关系。

- 图的遍历方式有深度优先搜索（DFS）和广度优先搜索（BFS）。

三、常见的数据结构算法1. 排序算法- 冒泡排序、插入排序、选择排序等简单但效率较低的排序算法。

- 快速排序、归并排序、堆排序等高效的排序算法。

- 基数排序、桶排序等适用于特定场景的排序算法。

2. 查找算法- 顺序查找、二分查找等常用的查找算法。

- 树结构相关的查找算法，如二叉搜索树、红黑树等。

- 哈希查找、索引查找等高效的查找算法。

3. 图算法- Dijkstra算法、Bellman-Ford算法等最短路径算法。

数据结构复习要点(汇总版)

数据结构复习要点(汇总版)

第一章数据结构概述基本概念与术语1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。

2.数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。

（补充：一个数据元素可由若干个数据项组成。

数据项是数据的不可分割的最小单位。

）3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

（有时候也叫做属性。

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

（1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。

数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。

依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种：1.集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。

2.线性结构：结构中的数据元素之间存在“一对一“的关系。

若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。

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

若数据为非空集，则除了第一个元素（根）之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。

4.图状结构：结构中的数据元素存在“多对多”的关系。

若结构为非空集，折每个数据可有多个（或零个）直接后继。

（2）数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。

想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。

逻辑结构可以映射为以下两种存储结构：1.顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。

2.链式存储结构：借助指针表达数据元素之间的逻辑关系。

不要求逻辑上相邻的数据元素物理位置上也相邻。

数据结构知识点总结(2023版)

数据结构知识点总结(2023版)

数据结构知识点总结数据结构知识点总结：一、数据结构概述数据结构定义及分类●线性结构●非线性结构●数组●链表●栈●队列●树●图●散列表二、线性结构⒈数组●定义●数组的操作：插入、删除、查找、更新●二维数组⒉链表●定义●特点●单链表●双链表●循环链表●链表的操作：插入、删除、查找、更新⒊栈●定义●特点●栈的顺序存储结构●栈的链式存储结构●栈的应用⒋队列●特点●队列的顺序存储结构●队列的链式存储结构●队列的应用三、非线性结构⒈树●定义●结点●树的类型：二叉树，多叉树，满二叉树，完全二叉树●二叉树的存储结构：顺序存储，链式存储●二叉树的遍历：先序遍历，中序遍历，后序遍历●二叉树的应用：赫夫曼树，二叉搜索树⒉图●定义●图的存储结构：邻接矩阵，邻接表●图的遍历：深度优先搜索，广度优先搜索●最短路径算法四、散列表（哈希表）●定义●散列函数●冲突解决方法：拉链法，开放地质法附件：无法律名词及注释：⒈数据结构：指在计算机科学中，数据组织、管理和存储的方式。

⒉线性结构：数据元素之间存在一对一关系的结构。

⒊非线性结构：数据元素之间存在一对多或多对多关系的结构。

⒋数组：一种线性结构，由相同数据类型的元素组成，通过下标进行访问。

⒌链表：一种线性结构，由一系列结点构成，每个结点中包含数据和指向下一个结点的指针。

⒍栈：一种特殊的线性结构，只能在一端进行插入和删除操作的数据结构。

⒎队列：一种特殊的线性结构，只能在一端进行插入操作，在另一端进行删除操作的数据结构。

⒏树：一种非线性结构，由结点和边组成，每个结点可以有多个子结点。

⒐图：一种非线性结构，由一组顶点和一组边组成，顶点之间可以有多种关系。

⒑散列表：一种根据关键字直接访问数据的数据结构，通过散列函数将关键字映射到相应的存储位置。