- 直接访问链接:https://t.zsxq.com/14F2uGap7
- 微信扫码下图:
数据结构作为计算机的一门基础学科,它在面试中占有很大的比重,本科阶段,我们也学过数据结构与算法,内容比较多,也比较难,尤其是图的应用以及各类查找和排序算法,这些也都是核心内容。数据结构在实际的应用中也比较多,因此,整理一些常见的笔试、面试的数据结构常考点非常有必要,本文将对数据结构常见面试问题进行整理,以便大家查阅。
第一章 绪论
1.数据结构的逻辑结构有哪些?物理结构有哪些?
数据的逻辑结构是指数据元素之间的逻辑关系,即从逻辑关系上描述数据。数据的逻辑结构分为线性结构和非线性结构,线性结构包括一般的线性表、栈、队列、串、数组,非线性结构包括集合、树、图。
数据的物理结构是指数据结构在计算机中的表示(又称映像),也称存储结构。数据的物理结构主要有顺序存储、链式存储、索引存储和散列存储。
2.什么是算法?算法的五大特性是什么?一个好的算法应该具备什么样的条件?
算法是对特定问题求解步骤的一种描述,是指令的有限序列,其中的每条指令表示一个或多个操作。算法的五个特征分别是有穷性、确定性、可行性、输入、输出。一个好的算法应该达到的目标是正确性、可读性、健壮性、效率与低存储量需求。
3.什么是数据结构?数据结构在学什么?
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构研究的是计算机操作对象的逻辑结构、物理结构以及数据的运算。
4.数据结构的复杂度是什么意思?
时间复杂度:算法中所有语句的频次。
空间复杂度:指算法运行过程中所使用的的辅助空间的大小。
5.常见的数据结构有哪些,说说他们之间的逻辑关系。
数据结构四种常见的逻辑结构:
1)集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系;
2)线性结构:数据结构中的元素存在一对一的相互关系;
3)树形结构:数据结构中的元素存在一对多的相互关系;
4)图形结构:数据结构中的元素存在多对多的相互关系。
第二章 线性表
1.顺序表和链表的比较
①存取(读取)方式
顺序表可以顺序存取,也可以随机存取,链表只能从表头顺序存取元素。
②逻辑结构与物理结构
采用顺序存储时,逻辑上相邻的元素,对应的物理存储位置也相邻。而采用链式存储时,逻辑上相邻的元素,物理存储位置不一定相邻,对应的逻辑关系是通过指针链接来实现的。
③查找、插入和删除操作
查找:对于按值查找,顺序表无序时,两者的时间复杂度均为O(n);顺序表有序时,可采用折半查找,此时的时间复杂度为O (log2n)。对于按序号查找,顺序表支持随机访问,时间复杂度仅为O(1),而链表的平均时间复杂度为O(n)。
插入、删除:顺序表的插入、删除操作,平均需要移动半个表长的元素;链表的插入、删除操作,只需要修改相应的结点指针域即 可。由于链表的每个结点都带有指针域,故而存储密度不够大。
④空间分配
顺序存储在静态存储分配情形下,一旦存储空间装满就不能扩充,若再加入新的元素,则会出现内存溢出,因此需要预先分配足够大 的存储空间。预先分配过大,可能会导致顺序表后部大量闲置;预先分配过小,又会造成溢出。动态分配存储虽然存储空间可以扩 充,但需要移动大量元素,导致操作效率降低,而且若内存中没有更大块的连续存储空间,则会导致分配失败。
链式存储的结点空间只在需要时申请分配,只要内存有空间就可以连续分配,操作灵活、高效。
2.解释下头指针和头结点的区别?单链表增加头结点的目的是什么?
头指针:是指向第一个结点存储位置的指针,具有标识作用,无论链表是否为空,头指针都存在。
头结点:是为了操作统一和方便设立的,放在第一个元素结点之前,头结点的数据域可以不存储任何信息,因此头结点可有可无。
单链表增加头结点可以方便运算。
3.循环链表的优点是什么?
可以从任意一个结点访问整个链表。
4.数组和链表的区别是什么?(比较经典的问题)
从逻辑结构来看:数组的存储长度是固定的,即数组大小定义之后不能改变,而且在插入和删除操作需要移动大量元素,相反对于 链表,它能够动态分配存储空间以适应数据动态增减的情况,并且易于进行插入和删除操作。
从访问方式来看:数组中的元素在内存中连续存放,可以通过数组下标进行随机访问,访问效率比较高。链表是链式存储结构,它 的存储空间不是必须连续,可以是任意的,因此访问链表必须从前往后依次进行,访问效率比较低。
5.解释一下顺序存储和链式存储
顺序存储是用一段连续的存储空间来存储数据元素,可以进行随机访问,访问效率较高。
链式存储是用任意的存储空间来存储数据元素,不能进行随机访问,访问效率较低。
第三章 栈和队列
1.请说明栈与队列的区别