西工大考研复试-数据结构真题整理(含答案)_西北工业大学计算机考…(西工大考研复试名单)

题目来源答案为手工核对整理

第一章 绪论

1. 简述数据结构的定义和组成

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合包括逻辑结构、物理结构和数据运算。

2. 数据的存储结构有哪几种

顺序存储

特点存储空间的地址连续逻辑关系。

优点存储密度大在o(1)内查询、修改元素。

缺点表示关系能力弱。

链式存储

特点占用空间任意。

优点空间任意便于动态管理内存。

缺点空间开销大在o(n)内查找、修改元素。

索引存储

特点存储空间是多段连续空间索引表由若干索引项组成。

优点顺序和链式结合保证数据的唯一性。

缺点创建索引和维护索引需要时间对数据增删查改的同时也要对索引进行维护。

哈希存储

特点又称散列存储

优点利用数据的某一特征访问和存储在o(1)内遍历元素。

缺点好的hash很难有时会产生冲突。

3. 什么是算法的时间复杂度和空间复杂度

时间复杂度是一个函数”>定量描述了算法在运行过程中占用存储空间大小。

算法的时间复杂度通常用大o符号表述时间复杂度的极限情形称为算法的“渐近时间复杂度”。

4. 数据结构的复杂度o(1)是什么意思

常数阶的复杂度耗时/耗空间都不变。

5. 什么是抽象数据结构

抽象数据类型abstract?data type,adt是指一个数学模型以及定义在这个模型上的一组操作。抽象数据类型的定义仅仅取决于它的一组逻辑特性而与它在计算机中的表示和实现无关。

6. 数据的基本单位和最小单位分别是什么

最小单位是bit1字节等于8个比特。

7. 简述一个好的算法应该达到哪些目标

正确性算法的输出应该符合预期的结果即算法应该在给定的输入条件下能够产生正确的输出。

可读性算法应该易于阅读和理解这样可以方便其他开发人员或团队成员进行代码的维护和修改。

高效性算法应该在可接受的时间内完成任务并且在处理大量数据时也能够快速有效地运行。

可扩展性算法应该能够处理不同规模的数据和不同类型的问题并且能够轻松地进行修改和扩展。

鲁棒性算法应该具备较强的鲁棒性并且不会因为一些不可预测的情况导致程序崩溃或出错。

可重用性算法应该能够在不同的场景和项目中被重复使用这可以提高代码的可维护性和开发效率。

8. 算法的五个重要特征

输入、输出、有穷性、确定性和可行性

第二章 线性表 栈 队列 串 数组

1. 线性表和顺序表以及链表的区别

顺序表与链表均属于线性表只是在逻辑结构和存储方式上有所不同。

顺序表线性表采用顺序存储的方式存储就称之为顺序表顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

链表线性表采用指针链接的方式存储就称之为链表。

2. 顺序表和链表存储的优缺点

① 顺序表存储

优点

通过下标来直接存储。

缺点

插入和删除比较慢。

空间浪费巨大。?

时间性能查找 o(1)插入和删除o(n)。

② 链表存储

优点

存取某个元素速度慢。

保留原有的物理顺序。

没有空间限制,存储元素的个数无上限,基本只与内存空间大小有关。

缺点

占用额外的空间以存储指针

需要从开始节点一个一个节点去查找元素访问。

时间性能查找 o(n)插入和删除o(1)。

3. 头指针和头节点的区别简述链表中引入头节点带来的优点

头指针是一个指向链表第一个实际数据节点的指针头节点是链表中的一个额外的、通常不存储有效数据的辅助节点。

优点不再需要判断是否在第一个元素之前插入或删除第一个元素。

4. 头插法和尾插法的区别

头插法是每次生成的链表节点都插入到链表头部。而尾插法则是插入到链表尾部。

5. 数组与线性表的关系

数组是顺序表顺序表是线性表的一种。

6. 循环队列的顺序表中

由于入队时尾指针向前追赶头指针。

7. 栈和队列的区别

栈是后进先出队列是先进先出。

8. 怎么区分循环队列是队空还是队满

牺牲一个存储位置

队空front

计数

有元素入队时0. …

建立一个flag

9. 栈和堆的区别

1、栈区局部变量的值等。

2、堆区程序结束时可能由os回

收。

10. 串是一种特殊的线性表请从存储和运算两方面来分析它的特殊之处

从存储方面来看串通常是用字符数组来表示的。

在c语言中而在其他编程语言中也有类似的方式。

串的存储是顺序存储结构通过数组下标来访问。

此外用来表示串的结束。

从运算方面来看串常见的操作包括串的连接、子串的提取、串的比较、串的匹配等。

串的连接可以用字符串拼接的方式实现形成一个新的串。

子串的提取可以通过指定子串的起始位置和长度来实现或者是按照字典序比较两个串的大小。

串的匹配是指在一个较长的文本串中查找一个较短的模式串常用的算法包括朴素匹配算法、kmp算法、bm算法等。

11. 介绍一下字符串模式匹配算法朴素模式匹配算法和kmp算法

?????? 从主串的第一个字符起直到最后看是否匹配成功。

kmp基本思想当匹配失败后如果已匹配相等的序列中有某个后缀正好是模式串的前缀那么就可以将模式串向后滑动到与这些相等字符对齐的位置与主串无关。

第三章 树和二叉树

1. 什么是树

树的定义树是n (n≥0)个结点的有限集。当n称为空树。

在任意一棵非空树中应满足:

1有且仅有一个特定的称为根的结点。

2)当n>1时并且称为根的子树。

二叉树定义二叉树是n (n≥0个结点的有限集合:

①或者为空二叉树0。

②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树

又分别是一棵二叉树。

满二叉树概念

一个二叉树但不是满二叉树)

完全二叉树概念

一棵深度为k的有n个结点的二叉树则这棵二叉树称为完全二叉树。

2. 树的存储结构有哪些

双亲表示法:

这种存储方式采用一组连续空间来存储每个结点其伪指针域为-1。

孩子表示法:

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构叶子结点的孩子链表为空表)。

这种存储方式寻找子女的操作非常直接而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。

孩子兄弟表示法:

?????? 孩子兄弟表示法又称二叉树表示法沿此域可以找到结点的所有兄弟结点)。

3. 二叉树与度为2的有序树的区别

则这个孩子结点无需分左右。

4. 完全二叉树与满二叉树的区别

满二叉树是叶子节点那一行是满的与对应的满二叉树的序号一致。

5. 什么是平衡二叉树

?????? 任意结点左右子树高度差的绝对值不超过1的二叉树为平衡二叉树。

如何判断平衡二叉树

原始方法

1.判断以根结点的树是否为平衡二叉树。求出左右子树的高度判断它们的高度差是否超过了1

2.递归判断根的左子树是否为平衡二叉树

3.递归判断根的右子树是否为平衡二叉树

注意空树也是平衡二叉树

改进方法

1.首先判断它的左子树是否为平衡二叉树

2.然后在判断它的右子树是否为平衡二叉树

3.判断它们是否为平衡二叉树的同时记录它们的左右子树的深度

4.最后在判断以这个结点为根的树是否为平衡二叉树

6. 二叉排序树和平衡二叉树的区别

二叉排序树是左子树节点小于根节点小于右子树节点。

平衡二叉树是左右子树的高度差绝对值不超过1。

7.二叉树的遍历

二叉树的先中后序遍历:

先序遍历

若二叉树为空

1

2

3先序遍历右子树。

中序遍历

若二叉树为空否则,

1

2

3中序遍历右子树。

后序遍历

若二叉树为空

1

2

3访问根结点。

8. 什么是带权路径长度

树的带权路径长度就是树中所有的叶结点的权值乘上其到根结点的路径长度。

9. 哈夫曼树和哈夫曼编码的作用是什么

哈夫曼树又称最优二叉树是一种带权路径长度最短的二叉树。哈夫曼编码可用于压缩数据。

没有一个编码是另一个编码的前缀就叫前缀编码。

第四章 图

1. 线性表、树、图哪些可以是空的

线性表和树都可以是空的但图不得。

图的顶点v一定非空但边即e可以为空。此时图中只有顶点没有边。

2. 什么是完全图

完全图是一个简单的无向图其中每对不同的顶点之间都恰连有一条边相连。

3. 简述图的存储结构

邻接矩阵法

?????? 指用一个一维数组存储图中顶点的信息存储顶点之间邻接关系的二维数组称为邻接矩阵。

邻接表法

?????? 指对图g中的每个顶点v建立一个单链表所以在邻接表中存在两种结点:顶点表结点和边表结点

十字链表法:

十字链表是有向图的一种链式存储结构。在十字链表中对应于每个顶点也有一个结点。

弧结点中有5个域:尾域(tailvex弧尾相同的弧也在同一个链表上。

顶点结点中有3个域: data域存放顶点相关的数据信息firstin和firstout两个域分别指向以该顶点为弧头或弧尾的第一个弧结点。

邻接多重表

?????? 邻接多重表存储无向图的方式同时为了便于管理将各个首元节点存储到一个数组中。

4. 什么是极大连通子图

极大连通子图是指图的连通分量再加入任何一个不在该连通分量中的点都会导致它不再连通。

极小连通子图是指连通图的生成树删除任何一条边都会导致无法构成生成树。

5. 简述邻接表和邻接矩阵的区别

邻接表的存储空间比邻接图小。

邻接矩阵遍历图比邻接表快。

邻接表适合存储稀疏图邻接矩阵适合存储稠密图。

6. 什么是最短路径

最短路径是指图中两个节点之间之间的最短路径。常用的算法有迪杰斯特拉算法和弗洛伊德算法。

dijkstra算法

基本思想dijkstra算法设置一个集合s记录已求得的最短路径的顶点轮流将每个顶点作为源点的时间复杂度o(v^3)。

dijkstra步骤如下

初始化:集合s初始为{0}, dist[ ]的初始值dist[i]从顶点集合v-s中选出 v将其加入到v中修改从v0出发到集合v-s上任一顶点v可达的最短路径长度:若dist[j] arcs[j][k]。重复2直到所有的顶点都包含在s中。

floyd算法

7. 什么是最小生成树

生成树连通图的生成树是包含图中全部顶点的一个极小连通子图则会变成非连通图

最小生成树:生成树的定义权值之和最小的生成树称为最小生成树。

prim算法

初始时从图中任取一顶点得到的t就是最小生成树。

kruskal算法

所有的边按照权值先从小到大排列直到所有的点都属于同一个集合为止。

8. 简述下aov网、aoe网、拓扑排序以及关键路径

aov网

aoe网

在带权有向图中而aov网中的边无权值,仅表示顶点之间的前后关系。

性质

只有在某顶点所代表的事件发生后只有在进入某顶点的各有向边所代表的活动都已结束时该顶点所代表的事件才能发生。

拓扑排序拓扑排序是一种针对aov网的排序。对于每个有向无环图构成的aov网,当顶点序列满足这些条件时:1.每个顶点出现且只出现一次;2.若顶点a在序列中排在顶点b的前面,则在图中不存在从顶点b到顶点a的路径。则是针对该aov网的一个拓扑排序。拓扑排序的执行过程是:1.从aov网中选择一个没有前驱的顶点并输出;2.从网中删除该顶点和所有以它为起点的有向边;3.重复1和2直到当前aov网为空,如果中途不存在无前驱的顶点,则说明网络存在环。

寻找关键路径的基本思想整个工程才能提前完成。

最早可能开始时间 ve[i]最迟允许开始时间 vl[i]事件 vi 最迟允许的开始时间。vl[i])}关键活动0 的节点

第五章 排序

1. 什么是算法的稳定性

排序算法的稳定性是指排序算法对关键字大小相同的元素如果发生变化则说明是不稳定的排序算法。

2. 简述内部排序和外部排序的区别。

内部排序是指排序文件不大将待排序的数据一次性全部装入内存进行排序。

外部排序是当待排序文件较大,内存一次放不下时,就需要排序时把数据一部分一部分地调入内存进行排序,在排序过程中需要多次进行内外存数据交换。

一般使用归并排序法。将文件分成若千长度为|的子文件,依次读入内存使用内部排序方法进行排序,形成归并段,再对各个归并段进行逐趟归并。

3. 数据结构有哪些排序算法并比较时间复杂度。

插入排序、选择排序、冒泡排序、快速排序、堆排序、归并排序、基数排序的时间复杂度

前3个为0(n^2),快排、堆排、归并排序为0(nlogn)r))。

第六章 查找

1. 顺序查找、折半查找、分块查找的优缺点。

顺序查找

一般线性表的顺序查找

基本思想是从线性表的一端开始则返回查找失败的信息。

有序表的顺序查找

若在查找之前就已经知道表是关键字有序的从而降低顺序查找失败的平均查找长度。

优点普适性强适合多种存储结构

缺点性能较低

折半查找

折半查找的基本思想:首先将给定值key与表中中间位置的元素比较,若相等返回查找失败的信息。

时间复杂度

优点性能较顺序查找更高

缺点只适合有序表且存储结构必须支持随机访问

分块查找

分块查找的基本思想:将查找表分为若干子块。块内的元素可以无序索引表按关键字有序排列。

优点速度快而不必移动节点中的数据

缺点增加了索引表降低了存储空间的利用率

2. 什么是b树

?????? b树又称多路平衡查找树

树中每个结点至多有m棵子树即至多含有m-1个关键字。若根结点不是终端结点则至少有两棵子树。除根结点外的所有非叶结点至少有「m/2棵子树即至少含有「m/2- 1个关键字。所有的叶结点都出现在同一层次上指向这些结点的指针为空)。

b树的特点

所有键值分布在整颗树中任何一个关键字出现且只出现在一个结点中搜索有可能在非叶子结点结束在关键字全集内做一次查找,性能逼近二分查找

b

b也是一种多路搜索树, 它与 b- 树的不同之处在于:

在b1棵子树。在b不含有该关键字对应记录的存储地址。在b包含的关键字和其他结点包含的关键字是不重复的。

3. 静态查找和动态查找

静态查找就是我们平时概念中的查找是“真正的查找”。之所以说静态查找是真正的查找这就是所谓的静态查找。

动态查找它更像是一个对表进行“创建、扩充、修改、删除”的过程。动态查找的过程中对表的操作会多两个动作往往并不是那么简单。

4. 什么是哈希表

哈希表又称为散列表是根据关键字码的值直接进行访问的数据结构直接定址法除留余数法数字分析法平方取中法折叠法随机数法。哈希冲突的解决方法包括开放定址法和拉链法

直接定址法 直接取关键字的某个线性函数值为散列地址。

?????? 除留余数法这是一种最简单、最常用的方法利用以下公式把关键字转换成散列地址。

?????? 开放定址法所谓开放定址法又向它的非同义词表项开放。

?????? 1)线性探测法

?????? 2)平方探测法

?????? 3)再散列法

?????? 4)伪随机序列

?????? 拉链法

5. 什么是散列表的装填因子

装填因子是散列表的一个重要参数而过小则会浪费存储空间。