算法

数据结构面试题

《林老师带你学编程》知识星球是由多个工作10年以上的一线大厂开发人员联合创建，希望通过我们的分享，帮助大家少走弯路，可以在技术的领域不断突破和发展。

🔥 具体的加入方式：

数据结构作为计算机的一门基础学科，它在面试中占有很大的比重，本科阶段，我们也学过数据结构与算法，内容比较多，也比较难，尤其是图的应用以及各类查找和排序算法，这些也都是核心内容。数据结构在实际的应用中也比较多，因此，整理一些常见的笔试、面试的数据结构常考点非常有必要，本文将对数据结构常见面试问题进行整理，以便大家查阅。

第一章 绪论

数据结构_绪论

1.数据结构的逻辑结构有哪些？物理结构有哪些？

​ 数据的逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。数据的逻辑结构分为线性结构和非线性结构，线性结构包括一般的线性表、栈、队列、串、数组，非线性结构包括集合、树、图。

​ 数据的物理结构是指数据结构在计算机中的表示（又称映像），也称存储结构。数据的物理结构主要有顺序存储、链式存储、索引存储和散列存储。

2.什么是算法?算法的五大特性是什么？一个好的算法应该具备什么样的条件？

​ 算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中的每条指令表示一个或多个操作。算法的五个特征分别是有穷性、确定性、可行性、输入、输出。一个好的算法应该达到的目标是正确性、可读性、健壮性、效率与低存储量需求。

3.什么是数据结构？数据结构在学什么？

​ 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构研究的是计算机操作对象的逻辑结构、物理结构以及数据的运算。

4.数据结构的复杂度是什么意思？

时间复杂度：算法中所有语句的频次。

空间复杂度：指算法运行过程中所使用的的辅助空间的大小。

5.常见的数据结构有哪些，说说他们之间的逻辑关系。

数据结构四种常见的逻辑结构：

1）集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；

2）线性结构：数据结构中的元素存在一对一的相互关系；

3）树形结构：数据结构中的元素存在一对多的相互关系；

4）图形结构：数据结构中的元素存在多对多的相互关系。

第二章 线性表

数据结构_线性表

1.顺序表和链表的比较

①存取（读取）方式

​ 顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。

②逻辑结构与物理结构

​ 采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来实现的。

③查找、插入和删除操作

查找：对于按值查找，顺序表无序时，两者的时间复杂度均为O（n）；顺序表有序时，可采用折半查找，此时的时间复杂度为O (log2n)。对于按序号查找，顺序表支持随机访问，时间复杂度仅为O（1），而链表的平均时间复杂度为O（n）。

插入、删除：顺序表的插入、删除操作，平均需要移动半个表长的元素；链表的插入、删除操作，只需要修改相应的结点指针域即 可。由于链表的每个结点都带有指针域，故而存储密度不够大。

④空间分配

顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新的元素，则会出现内存溢出，因此需要预先分配足够大 的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态分配存储虽然存储空间可以扩 充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。

链式存储的结点空间只在需要时申请分配，只要内存有空间就可以连续分配，操作灵活、高效。

2.解释下头指针和头结点的区别？单链表增加头结点的目的是什么？

头指针：是指向第一个结点存储位置的指针，具有标识作用，无论链表是否为空，头指针都存在。

头结点：是为了操作统一和方便设立的，放在第一个元素结点之前，头结点的数据域可以不存储任何信息，因此头结点可有可无。

单链表增加头结点可以方便运算。

3.循环链表的优点是什么？

可以从任意一个结点访问整个链表。

4.数组和链表的区别是什么？（比较经典的问题）

​ 从逻辑结构来看：数组的存储长度是固定的，即数组大小定义之后不能改变，而且在插入和删除操作需要移动大量元素，相反对于 链表，它能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。

​ 从访问方式来看：数组中的元素在内存中连续存放，可以通过数组下标进行随机访问，访问效率比较高。链表是链式存储结构，它 的存储空间不是必须连续，可以是任意的，因此访问链表必须从前往后依次进行，访问效率比较低。

5.解释一下顺序存储和链式存储

​ 顺序存储是用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率较高。

​ 链式存储是用任意的存储空间来存储数据元素，不能进行随机访问，访问效率较低。

第三章 栈和队列

数据结构_栈和队列

1.请说明栈与队列的区别

​

查看更多

常用算法面试题

《林老师带你学编程》知识星球是由多个工作10年以上的一线大厂开发人员联合创建，希望通过我们的分享，帮助大家少走弯路，可以在技术的领域不断突破和发展。

🔥 具体的加入方式：

1.字符串交换位置

时间复杂度O(n) 空间复杂度O(1)输入 \”abcde\” 输出 \”edcba\”

def jiaohuan(str1):
    s1 = list(str1)
    tmp = 0
    for i in range(0, int(len(s1) / 2)):
        tmp = s1[i]
        s1[i] = s1[len(s1) - i - 1]
        s1[len(s1) - i - 1] = tmp

    return s1


list1 = jiaohuan(\"abcde\")
print(\"\".join(list1))  # edcba

2.数组找最大值、最小值定义了一个数组a = [1,3,4,55,29] 查找数组中最大值
定义一个for循环对数组所有元素遍历一遍时间复杂度为O(n)

def max_value(l1):
    min = -1
    max = -1
    for i in range(len(l1)):
        if l1[i] > max:
            max = l1[i]
            min = i
    print(max)


max_value([1, 2, 333, 4, 5, -1])

3.降低复杂度案例、 输入数组a = [1,2,3,4,5,6,4,4,4,2] 中查找出现次数最多的数值

def max_count(l1):
    d1 = {}
    for i in l1:
        d1[i] = d1.get(i, 0) + 1
    print(d1)

    max_key = -1
    count_num = -1
    for i, v in d1.items():
        if v > count_num:
            count_num = v
            max_key = i
    print(max_key, count_num)


max_count([1, 2, 3, 4, 5, 6, 4, 4, 4, 4])

4.栈：后进先出 给定一个只包括 \'(\’，\’)\’，\'{\’，\’}\’，\'[\’，\’]\’ 的字符串，判断字符串是否有效。

class Solution:
    def isValid(self, s: str) -> bool:
        len_s = len(s)
        if len_s % 2 != 0:
            return False
        if len_s == 0:
            return True
        # 利用进栈出栈的思想
        str_dict = {\'(\': \')\', \'[\': \']\', \'{\': \'}\'}
        stacked = []
        for i in range(len_s):

            # 如果符号为左括号进行压栈
            if s[i] in str_dict.keys():
                stacked.append(s[i])

            # 如果栈不为空且符号在右括号内且左符号和最后一个元素相等
            if stacked and s[i] in str_dict.values() and s[i] == str_dict[stacked[-1]]:
                stacked.pop()
        if stacked == []:
            return True
        else:
            return False


solution = Solution()
print(solution.isValid(\"{[]}\"))  # True
print(solution.isValid(\"{[[}\"))  # False

5.为支持浏览器前进和后退功能，利用栈记录历史访问信息 后进先出

first_list = []
last_list = []


def chrome_a(url):
    if url not in last_list and url not in first_list:  # 当用户访问一个新页面
        last_list.append(url)
    elif url in last_list:  # 当用户后退一个页面
        last_list.pop()
        first_list.append(url)
    else:  # 用户前进一个页面
        first_list.pop()
        last_list.append(url)


for url in [1, 2, 3, 4, 5, 5, 4, 3, 4]:
    chrome_a(url)

print(first_list)
print(last_list)

6.队列 先进先出

def josephus2(num, k, m):
    alist = list(range(1, num + 1))
    index, step = k - 1, m  # 从1号开始报数，数到3的那个人出列
    for i in range(num - 1):
        index = (index + step - 1) % len(alist)
        print(\'出去的数：\', alist.pop(index))
    return \'最后的一个数：%s\' % alist[0]


print(josephus2(13, 1, 3))



7.数组 数组在内存中是连续存放的，数组内的数据，可以通过索引值直接取出得到
数组 [1,4,3,5,2] 去掉一个最大值和最小值求平均数 要求不允许开辟O(n)空间复杂度的数据结构

def score_avge(l1):
    max_num = -1
    max_number = -1
    min_num = -1
    min_number = 99
    for index, value in enumerate(l1):
        if value > max_number:
            max_number = value
            max_num = index

        if min_number > value:
            min_number = value
            min_num = index
    print(min_num, max_num)
    del l1[max_num]
    del l1[min_num]

    scores = 0
    for i, v in enumerate(l1):
        scores += v
    print(\"平均分:{}\".format(scores / len(l1)))


score_avge([1, 4, 3, 5, 2])

8.字符串 操作都是On

字符串替换将a替换为1aa替换为2 abaabccdaab==>1b2bccd2b 

for i in s1:
    if i == \"a\":
        count += 1
    else:
        if count != 0:
            s2 += str(count)
        count = 0
        s2 += i
print(s2)

9. 字符串 s = \”goodgoogle\”，判断字符串 t = \”google\” 在 s 中是否存在

s = \"goodgoogle1ccc\"
t = \"google\"

status = True
num = 0
for i, v in enumerate(s):
    if v == t[num]:
        status = True
        num += 1
        if len(t) == num:
            break
    else:
        status = False
        num = 0
if status:
    print(\"t字符串在s中\")
else:
    print(\"t字符串不在s中\")

 10.设置有且有两个字符串a = \”1345239\” b = \”12345\” 由于\”345\”同时出现在a和b中因此输出345

查看更多

滚动至顶部