08-21 16:21 李群 山东航空学院 在数据结构课程中提问：

在线性表中查找数据可以有多快？

如果有一线性表，我们要在其中查找一个与给定值相同的元素，时间复杂度是多少？你认为最快能有多快呢？

• 12-14 20:18 姚丁意

  普遍情况下复杂度为n最快情况下为logn

查看全部(16条)

09-01 07:54 李群 山东航空学院 在数据结构课程中提问：

这是哪种排序方法？

打扑克牌时，每抓一张牌，插入到合适位置，直到抓完牌为止，即可得到一个有序的序列，这个过程使用的是哪一种排序算法，请描述该算法的算法思想。

• 12-13 22:55 曹舒然

  该过程使用的是直接插入排序算法。
  算法思想：将待排序元素分为“已排序区”和“未排序区”，每次从“未排序区”取一个元素，插入“已排序区”的合适位置，使“已排序区”始终有序，重复此过程直至所有元素插入完毕。

查看全部(7条)

09-01 07:54 李群 山东航空学院 在数据结构课程中提问：

生活中的排序

生活中你遇到过排序问题吗，你是怎么处理的？你使用的APP中有没有排序，能否举例说明。

• 12-13 22:54 曹舒然

  生活中排序很常见，APP里也有大量排序功能，具体举例如下：
  1. 生活中的排序及处理：整理书架时按书籍编号从小到大摆；收拾衣柜会先分上衣、裤子等类别，再把同类衣物按颜色深浅排序；超市结账时大家按先来后到的顺序排队，都是直观的排序处理。
  2. APP中的排序实例：盒马等生鲜APP可按价格、销量给商品排序；iPhone的照片APP能按拍摄时间新旧排序；音乐APP可按歌曲时长、专辑名给歌单排序。

查看全部(7条)

09-01 07:54 李群 山东航空学院 在数据结构课程中提问：

快速排序一定比其他的排序算法快吗？

快速排序是基于关键字比较的排序算法中效率最好的算法，但在实际应用中它一定比其他排序快吗，并请说明你的理由。

• 12-13 22:52 曹舒然

  不一定。快速排序最坏情况（如有序序列）时间复杂度为O(n^2)，此时不如堆排序、归并排序的O(n\log_2n)快。

查看全部(8条)

09-01 07:55 李群 山东航空学院 在数据结构课程中提问：

哈希表性能与哪些因素相关？

哈希表是查找效率极高的查找结构，你知道它的查找效率与什么有关吗？可以通过具体的哈希表进行讨论

• 12-13 22:49 曹舒然

  哈希表的查找性能（平均查找长度）主要与哈希函数的优劣、冲突处理方法、装填因子大小三个核心因素相关，具体结合实例可清晰理解：
  理解：
  1. 哈希函数的优劣：决定关键字能否均匀映射到哈希表地址，减少冲突基础。
  2. 冲突处理方法：决定冲突发生后如何存储关键字，直接影响后续查找步骤。
  3. 装填因子的大小：装填因子α=表中关键字个数/哈希表长度，反映表的“拥挤程度”。

查看全部(3条)

09-01 07:55 李群 山东航空学院 在数据结构课程中提问：

哈希表中的同义词是否一定相邻存储？

在构建哈希表时，若采用线性探测方法处理冲突，则所有同义词（具有相同哈希函数值的关键字）记录在表中一定相邻吗？

• 12-13 22:47 曹舒然

  采用线性探测处理冲突时，哈希表中的同义词不一定相邻存储。
  核心原因是线性探测的“冲突连锁效应”：当某同义词插入时，若其哈希地址已被占用（可能是其他关键字，也可能是更早插入的同义词），会按“哈希地址+1、+2……”的顺序向后寻找空位置。若中间位置被其他关键字占据，后续插入的同义词会被“隔开”，导致同义词分布在不连续的位置。

查看全部(3条)

09-01 20:48 李群 山东航空学院 在数据结构课程中提问：

带负权值边图的最短路径问题

如果在一个图中的边有负的权值出现，那最短路径求解时是否各种算法策略都可以？比如：Floyd、Dijkstra算法能否得到正确解，为什么呢？

• 12-13 22:46 曹舒然

  带负权值边的图中，并非所有最短路径算法都适用，Floyd算法在特定条件下可正确求解，而Dijkstra算法通常无法得到正确解，核心差异在于算法对负权边的处理逻辑不同。1. Dijkstra算法：不能正确求解含负权边的图
  2. Floyd算法：在无负权回路的前提下，可正确求解

查看全部(6条)

09-01 20:48 李群 山东航空学院 在数据结构课程中提问：

生活中的图

你能列举出生活中利用图解决的问题吗？比如你用的app……

• 12-13 22:45 曹舒然

  1. 导航出行类APP：像高德地图、百度地图，把路口当作节点，道路当作带权重（如距离、拥堵时长）的边。用Dijkstra算法或A*算法规划最短、最快路线，比如早晚高峰时会避开拥堵路段，给用户推荐更优出行路径。
  2. 社交类APP：微信、微博等平台中，每个用户是节点，关注、好友关系是边。一方面靠社区发现算法划分兴趣圈子，比如把频繁互动的摄影爱好者归为一个社区；另一方面还能依据用户关系图做好友推荐，比如给你推荐好友的共同好友。
  3. 电商购物类APP：淘宝、京东等会把用户、商品当作节点，用户的浏览、下单、收藏行为当作边。通过图算法挖掘用户兴趣，比如你常买健身器材，就给你推送运动护具；同时也能做商品关联推荐，像买手机时搭配推荐耳机、手机壳。

查看全部(5条)

09-01 20:48 李群 山东航空学院 在数据结构课程中提问：

以下算法能否得到连通网的最小生成树？

现有如下算法： 设连通网G有n个顶点，m条边，先将所有边按权值由大到小排序为：e1,e2,e3,……,em . 设 i 初值为1. while(剩余边数>=n){ 从图中删去边ei，若图不连通则将边ei再加入图中 i++ } 循环结束后所得图即是G的一棵最小生成树。 你认为

• 12-13 22:44 曹舒然

  该算法正确，本质是Kruskal算法的“反向版本”，通过“去重边（大权重边）”保留最小生成树的必要边，最终得到最小生成树。
  简要证明：
  1. 最小生成树的性质：连通网的最小生成树有且仅有n-1条边，且删除其中任意一条边都会使树不连通；反之，在最小生成树外添加任意一条边，都会形成一个包含该边的环，且环中该边的权重是最大的（否则可替换边得到更小的生成树）。
  2. 算法逻辑匹配性质：
  算法先将边按权值从大到小排序，优先删除大权重边。
  若删除某条边后图仍连通，说明该边是“冗余边”（属于某个环的最大权重边，不影响连通性），可永久删除；若删除后图不连通，说明该边是“必要边”（是当前连通分量的唯一连接边，对应最小生成树的边），需重新加入。
  3. 终止条件验证：当剩余边数为n-1时，循环终止。此时图保持连通且边数为n-1，完全符合最小生成树“连通、无环、边数最少”的定义，故所得图为最小生成树。

查看全部(5条)

09-01 20:50 李群 山东航空学院 在数据结构课程中提问：

如何打印二叉树中所有的路径？

从根结点到叶子结点的点的集合称之为该叶子结点的路径。请思考，如何设计算法，能打印一棵二叉树中的所有路径？

• 12-13 22:41 曹舒然

  核心思路：用深度优先遍历（DFS）+ 路径回溯，记录当前路径，遇到叶子节点时打印路径，未到叶子则递归遍历子树并回溯路径。1. 特殊判断：若二叉树为空，直接返回。
  2. 路径记录：用数组/列表存储当前路径，将根节点值加入路径。
  3. 叶子判断：若当前节点是叶子节点（无左右子树），打印路径。
  4. 递归遍历：若有左子树，递归遍历左子树，遍历后回溯（删除路径中最后一个节点）。
  若有右子树，递归遍历右子树，遍历后回溯（删除路径中最后一个节点）。

查看全部(3条)

查看更多