【2011年数据结构真题】
41题

41题解答:
(1)图 G 的邻接矩阵 A 如下所示:
由题意得,A为上三角矩阵,在上三角矩阵A[6][6]中,第1行至第5行主对角线上方的元素个数分别为5, 4, 3, 2, 1
用 “ 平移” 的思想,将题目中前5个、后4个、后3个、后2个、后1个元素,分别移动到矩阵对角线 (“O”) 右边的行上,可得下图

(2)根据上面的邻接矩阵,画出有向带权图G

(3)按照算法,先计算各个事件的最早发生时间,计算过程如下:



关键路径为 0->1->2->3->5(如下图所示粗线表示),长度为 4+5+4+3=16。

42题

暴力解1:将两个数组合并成一个,然后找中位数即可
int merge(Sqlist A,Sqlist B) {int i=0,j=0,count=0;while(1){if(A.data[i]<B.data[i]){if(++count==(A.length+B.length)/2){return A.data[i];}++i;}else{if(++count==(A.length+B.length)/2){return B.data[i];}++j;}}
}
暴力解2:
- 新建一个数组C
- 合并到数组C
- 排序

- 要求找到两个等长有序序列合并后的中位数,暴力解就直接合并
- 但你会发现并不需要合并全部,我们只需要中间位置的一个值即可
- 所以 mid 就是 len-1,我们按照常规合并有序序列的方法,只移动指针即可
int serach_mid(int A[], int B[], int len) {int i = 0, j = 0;while (i + j < len - 1) {if (A[i] <= B[j]) {i++;} else {j++;}return A[i] <= B[j] ? A[i] : B[j];}
}
最优解:
思路:
1)求两个序列A和B的中位数最简单的办法就是将两个升序序列进行归并排序,然后求其中位数。这种解法虽可求解,但在时间和空间两方面都不大符合高效的要求,但也能获得部分分值。
根据题目分析,分别求两个升序序列A和B的中位数,设为a和b。
① 若a=b,则a或b即为所求的中位数。
原因:容易验证,如果将两个序列归并排序,则最终序列中,排在子序列ab前边的元素为先前两个序列中排在a和b前边的元素;排在子序列ab后边的元素为先前两个序列中排在a和b后边的元素。所以子序列ab一定位于最终序列的中间,又因为a=b,显然a就是中位数。
② 否则(假设a<b),中位数只能出现(a,b)范围内。
原因:同样可以用归并排序后的序列来验证,归并排序后必然有形如…a…b…的序列出现,中位数必出现在(a,b)之间。因此可以做如下处理:舍弃a所在序列A的较小一半,同时舍弃b所在序列B的较大一半。在保留两个升序序列中求出新的中位数a和b,重复上述过程,直到两个序列中只含一个元素时为止,则较小者即为所求的中位数。每次总的元素个数变为原来的一半。
算法的基本设计思想如下。
分别求出序列A和B的中位数,设为a和b,求序列A和B的中位数过程如下:
① 若a=b,则a或b即为所求中位数,算法结束。
② 若a<b,则舍弃序列A中较小的一半,同时舍弃序列B中较大的一半,要求舍弃的长度相等。
③ 若a>b,则舍弃序列A中较大的一半,同时舍弃序列B中较小的一半,要求舍弃的长度相等。
在保留的两个升序序列中,重复过程①、②、③,直到两个序列中只含一个元素时为止,较小者即为所求的中位数。
int M_Search(int A[], int B[], int n) {int s1 = 0, d1 = n - 1, m1, s2 = 1, d2 = n - 1, m2;//分别表示序列A和B的首位数、末位数和中位数while (s1 != d1 || s2 != d2) {m1 = (s1 + d1) / 2;m2 = (s2 + d2) / 2;if (A[m1] == B[m2])return A[m1]; //满足条件1)if (A[m1] < B[m2]) { //满足条件2)if ((s1 + d1) % 2 == 0) { //若元素个数为奇数s1 = m1; //舍弃A中间点以前的部分,且保留中间点d2 = m2; //舍弃B中间点以后的部分,且保留中间点} else { //元素个数为偶数s1 = m1 + 1; //舍弃A中间点及中间点以前部分d2 = m2; //舍弃B中间点以后部分且保留中间点}} else { //满足条件3)if ((s1 + d1) % 2 == 0) { //若元素个数为奇数d1 = m1; //舍弃A中间点以后的部分,且保留中间点s2 = m2; //舍弃B中间点以前的部分,且保留中间点}else { //元素个数为偶数d1 = m1 + 1; //舍弃A中间点以后部分,且保留中间点s2 = m2; //舍弃B中间点及中间点以前部分}}}return A[s1] < B[s2] ? A[s1] : B[s2];
}相关文章:
【2011年数据结构真题】
41题 41题解答: (1)图 G 的邻接矩阵 A 如下所示: 由题意得,A为上三角矩阵,在上三角矩阵A[6][6]中,第1行至第5行主对角线上方的元素个数分别为5, 4, 3, 2, 1 用 “ 平移” 的思想,…...
【科研绘图】MacOS上的LaTeX公式插入工具——LaTeXiT
在Mac上经常用OmniGraffle绘图,但是有个致命缺点是没办法插入LaTeX公式,很头疼。之前有尝试用Pages文稿插入公式,但是调字体和颜色很麻烦。并且,PPT中的公式插入感觉也不太好看。 偶然机会了解到了LaTeXiT这个工具,可…...
仓库自动化中的RFID技术的应用浅谈
仓库自动化与RFID技术的结合代表着现代供应链管理的一个重要革新。这两者的协同作用能够显著提升仓储效率、降低成本、增强库存管理、提高货物跟踪的准确性,并且使仓库操作更加智能化。 仓库自动化是一种通过应用自动化技术和系统来管理和优化仓库操作的方法。这种…...
容器网络-Underlay和Overlay
一、主机网络 前面讲了容器内部网络,但是容器最终是要部署在主机上,跨主机间的网络访问又是怎么样的,跨主机网络主要有两种方案。 二、 Underlay 使用现有底层网络,为每一个容器配置可路由的网络IP。也就是说容器网络和主机网络…...
基于FPGA的PCIe-Aurora 8/10音频数据协议转换系统设计阅读笔记
文章可知网下载阅读,该论文设计了一种 PC 到光纤模块(基于Aurora的光纤传输)的数据通路,成功完成了Aurora 以及 DDR 等模块的功能验证。 学习内容: 本次主要学习了Pcie高速串行总线协议、Aurora高速串行总线协议、DDR相…...
stm32控制舵机sg90
一、sg90简介 首先介绍说一下什么是舵机。舵机是一种位置(角度)伺服的驱动器。适用于一些需要角度不断变化的,可以保持的控制系统。sg90就是舵机的一种。 舵机的工作原理比较简单。舵机内部有一个基准电压,单片机产生的PWM信号通…...
state 和 props 有什么区别?
一、state 一个组件的显示形态可以由数据状态和外部参数所决定,而数据状态就是 state,一般在 constructor 中初始化 当需要修改里面的值的状态需要通过调用 setState 来改变,从而达到更新组件内部数据的作用,并且重新调用组件 r…...
Unity 获取桌面路径的方法
在Unity中,当我们碰到以下一些情况时,可能需要桌面的路径。 1、文件操作:如果我们想在游戏中保存或读取文件到桌面,就可以使用桌面路径来指定文件的位置。 2、调试信息:在开发过程中,我们往往会将一些调试…...
基于SSM的考研图书电子商务平台的设计与实现
末尾获取源码 开发语言:Java Java开发工具:JDK1.8 后端框架:SSM 前端:Vue 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件:IDEA / Eclipse 是否Maven项目:是 目录…...
信息系统“好用”的标准探讨
数字化转型建设的关键不在建设信息系统。这是为了避免走信息化建设的老路——业务和信息化两张皮,寄希望信息系统解决业务问题。在数字化转型建设中,信息系统仍然是重要抓手和显性成果,是企业业务和数据的承载平台,也是IT厂商向客…...
vue elementui 实现从excel从复制多行多列后粘贴到前端界面el-table
1、效果图 可以全部复制粘贴,也可以单独对某行、某列进行复制粘贴 从excel复制粘贴到前端页面的table上 2、实现代码 html部分: <template><div><el-table:data"tableData"borderstyle"width: 100%":cell-class-…...
C++学习 --类和对象之友元
目录 1, 全局函数做友元 2, 类做友元 3, 成员函数做友元 友元可以让函数、成员函数、类, 访问另外一个类的私有变量 1, 全局函数做友元 在类中, 通过friend 数据类型 函数名()方式,将函数当…...
Flutter笔记:使用Flutter构建响应式PC客户端/Web页面-案例
Flutter笔记 使用Flutter构建响应式PC客户端/Web页面-案例 作者:李俊才 (jcLee95):https://blog.csdn.net/qq_28550263 邮箱 :291148484163.com 本文地址:https://blog.csdn.net/qq_28550263/article/detai…...
聊聊LogbackMDCAdapter
序 本文主要研究一下LogbackMDCAdapter MDCAdapter org/slf4j/spi/MDCAdapter.java public interface MDCAdapter {/*** Put a context value (the <code>val</code> parameter) as identified with* the <code>key</code> parameter into the cur…...
spring命名空间注入和XML自动装配、引入外部配置文件
Spring p命名空间注入util命名空间注入基于XML的自动装配根据名称自动装配 Spring引入外部属性配置文件 p命名空间注入 作用:简化配置。 使用p命名空间注入的前提条件包括两个: ● 第一:在XML头部信息中添加p命名空间的配置信息:…...
【2024年11月份--2024精灵云校招C++笔试题】
考试形式 笔试考了三道算法题,笔试形式为阅读题目,然后用中文给出算法思路,最后给出算法例程,分数各占一半,简单,中等,复杂各一道题。我看9月份有人也是考这3道题,一模一样。 第…...
Visual Studio 2019下编译OpenCV 4.7 与OpenCV 4.7 contrib
一、环境 使用的环境是Win10,Visual Studio 2019,Cmake3.28,cdua 11.7,cudnn 8.5,如果只是在CPU环境下使用,则不用安装CUDA。要使用GPU处理,安装好CUDA之后,要测试安装的CUDA是否能用。不能正常使用的话,添加一下系统…...
【Linux网络】系统调优之聚合链路bonding,可以实现高可用和负载均衡
一、什么是多网卡绑定 二、聚合链路的工作模式 三、实操创建bonding设备(mode1) 1、实验 2、配置文件解读 3、查看bonding状态,验证bonding的高可用效果 三、nmcli实现bonding 一、什么是多网卡绑定 将多块网卡绑定同一IP地址对外提供服务…...
k8s持久化存储PV、PVC
容器磁盘上的文件的生命周期是短暂的,这就使得在容器中运行重要应用时会出现一些问题。首先,当容器崩溃时,kubelet 会重启它,但是容器中的文件将丢失——容器以干净的状态(镜像最初的状态)重新启动。其次&a…...
CocosCreator3.8原生引擎源码研究
1. Cocos Creator引擎架构图 2. 原始引擎源码流程图 下图中包含Android native层引擎到js适配层的启动和主循环的启用流程和必要说明,本猿比较懒,暂时不细述了,各位看官直接看图吧,还在细化扩充,后续逐渐更新。。。 版…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
