第三章 线性结构

1、线性表有两种存储结构：一是顺序表，二是链表。试问： (1）若要给书店设计一个图书销售管理系统，书店经常会进一些新的书，也会下 架一些销量不好的书，应该采用哪种存储结构？为什么？请设计算法完成图书的 插入和删除操作。

答 : (1）应选择链式存储结构。 因为它可动态申请内存空间，不受表长度 (即 表中元素个数）的影响,插入、删除时间复杂度为 O(1）。

(2）若要设计一个学生信息管理系统，系统中学生的总数基本稳定，且很少进行 插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结 构？为什么？请设计算法实现按学号查找学生的操作。

答：应选择顺序存储结构。因为顺序表可以随机存取，时间复杂度为 O (1）。

让我用时间复杂度为 O (1）去写，感觉只能这样写了（他喵的，这个题跟弱智一样）  

2、假设有一个简单的计算器应用，它可以执行基本的算术运算，并且支持撤销 （undo）和重做（redo）功能。该计算器维护了一个操作历史记录，以便用户可 以回退到之前的操作或重新执行已撤销的操作。请问应该使用哪种数据结构来存 储这些操作历史记录？并描述在执行新操作、撤销操作和重做操作时，该数据结 构应该如何变化。

答案：

栈（Stack）

具体操作如下：

执行新操作：当用户执行一个新的算术操作时，将该操作压入栈中。这可以通过 栈的压栈操作（push）来实现。

撤销操作：当用户想要撤销最近的一次操作时，我们从栈顶弹出一个操作。这可 以通过栈的弹栈操作（pop）来实现。弹出的操作可以存储在一个“重做栈”中， 以便后续的重做操作。

重做操作：如果用户想要重做之前撤销的操作，我们从“重做栈”中弹出一个操 作，并将其重新压入主操作历史栈中。这实际上是将之前撤销的操作恢复到操作 历史中。

3、当向固定大小的线程池请求一个线程时，如果线程池中没有空闲资源，这个 时候线程池可以拒绝请求，也可以要求排队。作为软件工程师，请你用所学队列 相关知识为线程池设计一个最多允许同时有10个请求排队的算法，还有其他的可 选方案吗？对比分析，并说明采用该方案的理由。（提示：有两种方案可选 循 环队列、链式队列 ）

4、在繁忙的港口，货船需要按照到达的顺序卸货。港口有一个等待区，货船到 达后会在等待区排队。当卸货区空闲时，等待区中最早到达的货船会进入卸货区 进行卸货。请问应该使用哪种数据结构（容器）来模拟港口的等待区？并具体说 明货船到达和货船卸货时该数据结构（容器）应该进行什么样的操作？（提示：队列 货船到达入队列、货船卸货出队列 ）

5、在古代中华，诗词是文人墨客表达情感、描绘风景的重要方式。现在，我们 将这些优美的诗词存储在一个单向链表中，每一个节点都包含一句诗词。我们希 望统计链表中某个特定诗句出现的次数，以此来感受这句诗词在文人中的受欢迎 程度。请实现一个函数，该函数接受链表的头节点和一句目标诗句作为输入，返回该诗 句在链表中出现的次数。

                                                       第四章 树

1、《周易》是中国本源传统文化的精髓，是中华民族智慧与文化的结晶，集中 体现了中华民族的思维模式、价值取向等哲学思想。周易中所描述的太极两仪四 象八卦是一种什么结构？请问应该选用顺序存储结构还是链式存储结构来存储， 并说明原因？[提示：二叉树，顺序存储 完美二叉树适合采用顺序存储结构]

2、在中华优秀传统文化中，书法艺术占据重要地位。假设我们有一系列书法家 的名字和他们的师徒关系（假设每个书法家我们只关注其两个主要的弟子），请 问可以使用哪种数据结构来表示这种师徒传承关系？并说明应该采用哪种存储结构，并分析其原因。（提示：二叉树顺序存储或者链式存储皆可以，顺序存储适合完全二叉树，图中正好是完全二叉树；链式存储结构插入删除操作方便）

3、已知一个文件中出现的各字符及其对应的频率如下表所示。采用Huffman编码， 在构建Huffman树时要求同层结点权值从小到大。则（1）该文件中字符a的码长 为？（ 2）该文件中字符 c的码长为？（ 3）若采用 Huffman编码，则字序列 “110001001101” 的编码应为？

4、在电文收发等数据通讯中，常需要将传送的文字转换成由二进制字符0、1组 成的字符来传输。例如要发送由a、b、c、d、e、f六个字符组成的信息，各字符 在其文本中出现的次数为45、13、12、16、9、5，现要为这六个字符设计哈夫曼 编码，请画出对应的哈夫曼树并写出每个字符的编码。

5、在古代，中国的文人们编写了大量的诗文，形成了丰富的古典文集。这些文 集按照特定的顺序编排，既方便了文人墨客的吟咏，也体现了中华文化的博大精 深。现在，我们希望借助二叉排序树的数据结构，对这些古典文集进行高效的检 索和管理。请实现一个插入操作，能够将新的诗文标题插入到二叉排序树中的合 适位置，保持树的排序性质。

6、在古代，中国的文人们编写了大量的诗文，形成了丰富的古典文集。这些文 集按照特定的顺序编排，既方便了文人墨客的吟咏，也体现了中华文化的博大精 深。现在，我们希望借助二叉排序树的数据结构，对这些古典文集进行高效的检 索和管理。请实现一个查找操作，能够根据录入的诗文标题查找到对应的诗文。

                                                                 第六章 图

1、在古老的丝绸之路上，众多的城市和贸易站点通过复杂的交通网络连接在一 起。这些城市之间，有的通过陆路相连，有的则通过水路相通。丝绸之路不仅是 商品交易的通道，更是文化交流与融合的桥梁。现在，我们希望找到任意两个城 市之间的最短路径。请问该问题属于图的哪类问题？常见的经典算法有哪些？并 说明各自的应用场景。（提示：最短路径，常见的算法 Dijkstra 和 Floyd 算法， Dijkstra 通常求解单源点最短路径，Floyd 算法可以求解多源点最短路径）

2、“一带一路”包含：政策沟通；设施联通；资金融通；贸易畅通；民心相通。 为了加快互联互通，需要在已有道路的基础上改造一条高速公路，要求能够连通 下图中的 8 个地区且费用最少（费用和距离成正比），请问该问题是图的应用中 的哪一种问题？并给出要修建的高速公路总长度为多少？并给出具体的修建方 案。

3、在一个大型软件项目中，各个模块之间存在依赖关系。项目经理需要确定哪 些模块在其他模块之前需要被构建和测试，以确保项目可以顺利进行。这些依赖 关系可以用一个有向无环图（DAG）来表示，其中节点代表模块，有向边代表 模块之间的依赖关系。请问可以用图中学到的什么知识来帮该项目经理确定模块 构建和测试的顺序？并描述求解的过程（算法）。 （提示：拓扑排序 ） 算法思想： 1.求每个顶点的入度 2.入度为 0 的顶点入队列 3.若队列不为空，取队头元素出队列，删除该顶点及出边——即更新出边邻接点的入 度 ，重复该过程，直到队列为空。 算法（仅供参考）：

4、安阳是一个历史文化名城，有殷墟博物馆、中国文字博物馆、红旗渠纪念馆、 岳飞庙、羑里城等大批文化景点和名胜古迹。为了更方便游客出行，现在要改建 高速公路，要求能够连通每个景点，且能够使修路的成本最低。该问题是图的应 用中的哪类问题？请选用教材或其他文献上的经典算法给下图设计出修路方案， 并说明选用该算法的理由

Kruskal算法求最小生成树（最后附完整代码）-CSDN博客

                                                               第七章 排序

1、有一关键字序列（265，301，751，129，937，863，742，694，076，438）， 写出希尔排序的每趟排序结果。（取增量为 5，3，1）

答案：初始：   265，301，751，129，937，863，742，694，076，438 d=5：   265，301，694，076，438，863，742，751，129，937 d=3：   076，301，129，265，438，694，742，751，863，937 d=1：   076，129，265，301，438，694，742，751，863，937

希尔排序 （最后附完整代码）-CSDN博客

2、如何在时间复杂度为 O(n)情况下根据年龄给 200 万个用户排序，请设计出排 序方案？ （提示：桶排序）

3、在古老的中华书院中，学子们每日都需要研习经典，书院的夫子为了检验学 子们对经典的掌握，会给出一系列经典句子的编号，要求学子们按照编号顺序进 行排序。今日，夫子给出的句子编号序列为 { 11，12，13，7，8，9，23，4，5 }。 书院中的小明选择使用插入排序法对这些编号进行排序。现在，请按照插入排序 的算法，写出前五趟排序后的结果。每一趟排序都应详细列出，以便夫子检查小 明的排序是否正确。 答案：第一趟：{ 11，12，13，7，8，9，23，4，5 } 第二趟：{ 11，12，13，7，8，9，23，4，5 } 第三趟：{ 7，11，12，13，8，9，23，4，5 } 第四趟：{ 7，8，11，12，13，9，23，4，5 } 第五趟：{ 7，8，9，11，12，13，23，4，5}

插入 排序-CSDN博客

4、在古老的中华书院中，学子们每日都需要研习经典，书院的夫子为了检验学 子们对经典的掌握，会给出一系列经典句子的编号，要求学子们按照编号顺序进 行排序。今日，夫子给出的句子编号序列为 { 11，12，13，7，8，9，23，4，5 }。 书院中的小明选择使用选择排序法对这些编号进行排序,写出前五趟排序后的结果。每一趟排序都应详细列出，以便夫子检查小 明的排序是否正确。 答案：第一趟：{ 4，12，13，7，8，9，23，11，5 } 第二趟：{ 4，5，13，7，8，9，23，11，12 } 第三趟：{ 4，5，7，13，8，9，23，11，12 } 第四趟：{ 4，5，7，8，13，9，23，11，12 } 第五趟：{ 4，5，7，8，9，13，23，11，12}

                                              第五章 查找 1、假设我们有一组数据 {15, 11, 27, 8, 22}，选定散列函数为 H(key) = key % 7。 散列表存储空间是大小为 7（下标 0 到下标 6）的一维数组，采用线性探测法解 决冲突，则 15,11,27,8,22 分别存储在数组中的下标为几的位置？

答案： 15%7=1; 11%7=4; 27%7=6; 8%7=1; 冲突 （1+1）%7=2 不冲突 22%7=1; 冲突 （1+1）%7=2 冲突 （1+2）%7=3 不冲突

2、假设我们有一组数据 {15, 11, 27, 8, 22}，选定散列函数为 H(key) = key % 7。 散列表存储空间是大小为 7（下标 0 到下标 6）的一维数组，采用平方探测法解 决冲突，则 15,11,27,8,22 分别存储在数组中的下标为几的位置？

答案：   15%7=1; 11%7=4; 27%7=6; 8%7=1; 冲突 （1+12）%7=2 不冲突 22%7=1; 冲突 （1+12）%7=2 冲突 1-12）%7=0 不冲突  

4.对于互联网的搜索引擎来讲，每一个网页就是一个文献。互联网的网页数量 是巨大的，网络中所用的词也非常非常多。为了快速搜索出结果，搜索引擎需维 护一张索引表：表的每一行对应一个关键词，而每一个关键词后面跟着一组数字， 是包含该关键词的文献序号。为了网页排名方便，索引中还需存有大量附加信息， 诸如每个关键词在该文献中出现的次数、位置等等。因此这个索引是巨大的，大 约在万亿字节这个量级。 请问：如何能在极短的时间内（比如 1 秒内）在上述索引表中搜索到需要的关键 词，请简述拟采用的方法及设计相应的存储结构。

（提示：散列）