【免费】计算机考研/保研复试-数据结构面试题及参考答案资源-CSDN文库

需积分: 0 48 浏览量 2024-08-09 09:14:28 上传评论收藏 209KB DOCX 举报

资源推荐

资源详情

资源评论

数据结构

1、数组和链表的区别。

从逻辑结构上来看，数组必须实现定于固定的长度，不能适应数据动态增减

的情况，即数组的大小一旦定义就不能改变。当数据增加是，可能超过原先定义

的元素的个数；当数据减少时，造成内存浪费；链表动态进行存储分配，可以适

应数据动态地增减的情况，且可以方便地插入、删除数据项。

从内存存储的角度看；数组从栈中分配空间（用 new 则在堆上创建），对程

序员方便快速，但是自由度小；链表从堆中分配空间，自由度大但是申请管理比

较麻烦。

从访问方式类看，数组在内存中是连续的存储，因此可以利用下标索引进行

访问；链表是链式存储结构，在访问元素时候只能够通过线性方式由前到后顺序

的访问，所以访问效率比数组要低。

2、顺序结构和链式结构的区别？

顺序结构是指内存连续的存储单元进行存储，而链式结构是指内存不连续的

结构，通过一个节点指向另外一个节点的地址。

1、顺序存储和链式存储优缺点比较

① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求

内存中可用存储单元的地址必须是连续的。

优点：存储密度大（＝1），易于查找和修改。

缺点：插入或删除元素时不方便；存储空间利用率低，预先分配内存可能造

成存储空间浪费。

②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部

分存放结点值，另一部分存放表示结点间关系的指针

优点：插入或删除元素时很方便，使用灵活，存储空间利用率高。

缺点：存储密度小（<1），查找和修改需要遍历整个链表。

3、数据结构的存储结构(4 个)和对应的存储模式(1 对 1 1 对多多对多)

4 种逻辑结构:

（1.集合结构:数据元素之间没有任何关系.

（2.线性结构:数据元素之间定义了线性关系.1 对 1

（3.树形结构:数据元素之间定义了层次关系 1 对多.

（4.图状结构:数据元素之间定义了网状关系多对多.

4 种数据存储结构:

插入排序有直接插入和折半插入。都是在有序表里插入进去的。

交换排序：冒泡，快速排序：以一个数字划分两个区域，然后分别对两个区

域继续划分，直到区间为一。注意：快排是不稳定。

选择排序：简单的选择排序，堆排序

归并排序：将两个有序表归并到一个有序表。将两个有序表放到一起进行各

个比较，比较完之后放回原来数组内。

14、简述快速排序过程

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,

2）通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的

元素值均比基准元素值小。另一部分记录的元素值比基准值大。

3）此时基准元素在其排好序后的正确位置

4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有

序。

15、快速排序的改进

只对长度大于 k 的子序列递归调用快速排序,让原序列基本有序，然后再对

整个基本有序序列用插入排序算法排序。实践证明，改进后的算法时间复杂度有

所降低，且当 k 取值为 8 左右时,改进算法的性能最佳。

16、选择基准元的方式

对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么

分治算法效率会达到最大。也就是说，基准的选择是很重要的。选择基准的方式

决定了两个分割后两个子序列的长度，进而对整个算法的效率产生决定性影响。

最理想的方法是，选择的基准恰好能把待排序序列分成两个等长的子序列。

方法 1 固定基准元

如果输入序列是随机的，处理时间是可以接受的。如果数组已经有序时，此

时的分割就是一个非常不好的分割。

方法 2 随机基准元

这是一种相对安全的策略。由于基准元的位置是随机的，那么产生的分割也

不会总是会出现劣质的分割。在整个数组数字全相等时，仍然是最坏情况，时间

复杂度是 O(n^2）。实际上，随机化快速排序得到理论最坏情况的可能性仅为

1/(2^n）。所以随机化快速排序可以对于绝大多数输入数据达到 O(nlogn）的期

望时间复杂度。

方法 3 三数取中

引入的原因：虽然随机选取基准时，减少出现不好分割的几率，但是还是最

坏情况下还是 O(n^2），要缓解这种情况，就引入了三数取中选取基准。

分析：最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可

剩余12页未读，继续阅读

内容反馈

背着雨水上山

粉丝: 66
资源: 1

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip