北航计算机软件技术基础课程作业笔记【4】

2024-04-25 02:36

本文主要是介绍北航计算机软件技术基础课程作业笔记【4】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目(好像以前没加)

二叉树与哈希表

作业

1.二叉树前序遍历结果

  • 二叉树结构为

     
  • 代码实现中序+后序推理前序表达式

    #include <iostream>
    #include <stack>
    #include <string>
    #include <vector>
    #include <deque>
    ​
    //  BDCEAFHG
    std::deque<char> mid_order = {'B','D','C','E','A','F','H','G'};
    //  DECBHGFA
    std::deque<char> back_order = {'D','E','C','B','H','G','F','A'};
    ​
    ​
    std::string mid = "BDCEAFHG";
    std::string back = "DECBHGFA";
    ​
    void get_res(std::string mid, std::string back)
    {   if(mid.empty()){return;}char root = back.back();std::cout <<root;int root_index = mid.find(root),length = mid.length();// mid , left is 0-ind, right is ind-end// back, left is 0-ind, right is ind-end-1 // left sub treeget_res(mid.substr(0,root_index),back.substr(0,root_index));// right subtree// get_res(mid.substr(root_index+1,length-1),back.substr(root_index,length-1));get_res(mid.substr(root_index+1,length-1),back.substr(root_index,length-root_index-1));
    }
    ​
    ​
    int main()
    {get_res(mid,back);return 0;
    }
  • 运行结果

    ABCDEFGH(符合推导的二叉树结构)

2.将多叉树转二叉树

 

3.线性哈希表

H(k)=INT(k/13),序列为(08, 14,23,30,68,92,42,55,76,10)

目录

二叉树与哈希表

作业

1.二叉树前序遍历结果

2.将多叉树转二叉树

3.线性哈希表

重要概念回顾

1.前序

2.前序与后序

3.后序+中序求前序思路

4.线性哈希表


序号0123456789101112
Key08142330426855927610
冲突0011102039

平均查找次数=(1*4+2*3+3*1+4*1+10*1)/10=2.7

重要概念回顾

1.前序

前是指的“更新(更子节点)”的方向,对于数组而言,i的前序位置指的i+1

2.前序与后序

前序位置的代码只能从函数参数中获取父节点传递来的数据,而后序位置的代码不仅可以获取参数数据,还可以获取到子树通过函数返回值传递回来的数据

3.后序+中序求前序思路

后序得到根节点,将中序的输出分为左右子树,再在后序的子树找根节点。依次循环

4.线性哈希表

按照key的顺序依次带入哈希函数,得到序号值,看看是否在该序号下已有其他key,若有,就让key值+1(记得取模,毕竟长度有限),直到序号下没有key为止

这篇关于北航计算机软件技术基础课程作业笔记【4】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/933493

相关文章

作业提交过程之HDFSMapReduce

作业提交全过程详解 (1)作业提交 第1步:Client调用job.waitForCompletion方法,向整个集群提交MapReduce作业。 第2步:Client向RM申请一个作业id。 第3步:RM给Client返回该job资源的提交路径和作业id。 第4步:Client提交jar包、切片信息和配置文件到指定的资源提交路径。 第5步:Client提交完资源后,向RM申请运行MrAp

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

金融业开源技术 术语

金融业开源技术  术语 1  范围 本文件界定了金融业开源技术的常用术语。 本文件适用于金融业中涉及开源技术的相关标准及规范性文件制定和信息沟通等活动。

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具,采用无代理架构(agentless),基于 SSH 连接进行管理,具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运维场景中的应用,旨在帮助运维人员快速上手并熟练运用 Ansible。 1. Ansible的核心概念

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出 在数字化时代,文本到语音(Text-to-Speech, TTS)技术已成为人机交互的关键桥梁,无论是为视障人士提供辅助阅读,还是为智能助手注入声音的灵魂,TTS 技术都扮演着至关重要的角色。从最初的拼接式方法到参数化技术,再到现今的深度学习解决方案,TTS 技术经历了一段长足的进步。这篇文章将带您穿越时

系统架构设计师: 信息安全技术

简简单单 Online zuozuo: 简简单单 Online zuozuo 简简单单 Online zuozuo 简简单单 Online zuozuo 简简单单 Online zuozuo :本心、输入输出、结果 简简单单 Online zuozuo : 文章目录 系统架构设计师: 信息安全技术前言信息安全的基本要素:信息安全的范围:安全措施的目标:访问控制技术要素:访问控制包括:等保