一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1356|回复: 11
收起左侧

[树/链表/图] 半自学CS中几个数据结构题求解

[复制链接] |试试Instant~ |关注本帖
peizhongxu 发表于 2016-1-7 23:31:32 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
有两个问题请教大家,可能看起来很蠢。。

1、请分析两个人握手的数据结构描述。。
。。。什么鬼 是用队列吗
====================================================================================
2、有一个家长想在最短时间内走完学校所有建筑物并且每个建筑物只访问一次,请给他一个方案并说明理由?
原来感觉是最小生成树问题,但是发现不能保证是一条路径走完。。后来百度了一下是tsp问题,但是tsp问题应该是要回到起点的,这里感觉不需要

灰溜溜溜溜 发表于 2016-1-7 23:47:52 | 显示全部楼层
hamiltonian path?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

nwzqx0815 发表于 2016-1-7 23:51:26 | 显示全部楼层
1. 听不懂题目
2. Hamiltonian path https://en.wikipedia.org/wiki/Hamiltonian_path 是数学(图论)问题

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| peizhongxu 发表于 2016-1-7 23:51:29 | 显示全部楼层

额 应该是的 想知道求最优解的方法
回复 支持 反对

使用道具 举报

 楼主| peizhongxu 发表于 2016-1-7 23:52:28 | 显示全部楼层
nwzqx0815 发表于 2016-1-7 23:51
1. 听不懂题目
2. Hamiltonian path https://en.wikipedia.org/wiki/Hamiltonian_path 是数学(图论)问题

同表示第一题看不懂题目 老师比较奇葩 可能希望你自己找到适用的数据结构 第二个应该是Hamiltonian path 谢谢!
回复 支持 反对

使用道具 举报

nwzqx0815 发表于 2016-1-8 00:03:16 | 显示全部楼层
peizhongxu 发表于 2016-1-7 23:52
同表示第一题看不懂题目 老师比较奇葩 可能希望你自己找到适用的数据结构 第二个应该是Hamiltonian path  ...

2应该没有简单的快速解法
Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

wiki页面里给了一些Hamiltonian path存在的充分条件,但应该没有一个是充要条件,你找到你就牛逼了。。。
回复 支持 反对

使用道具 举报

163 发表于 2016-1-8 00:10:33 | 显示全部楼层
从哪弄的破题?赶紧换个老师吧,什么玩意,误人子弟。
回复 支持 反对

使用道具 举报

 楼主| peizhongxu 发表于 2016-1-8 00:14:10 | 显示全部楼层
本帖最后由 peizhongxu 于 2016-1-8 00:18 编辑
163 发表于 2016-1-8 00:10
从哪弄的破题?赶紧换个老师吧,什么玩意,误人子弟。

一个特别装逼的老师 在一所财经院校里这学期唯一的数据结构老师
如果我不是为了成绩单上有这个课早就退了
找到了他以往的卷子
真的是心塞
毕竟期末前我还是不说哪个财经学校了。。
其实大部分题还比较常规。。
非要弄几个简答题让你题都看不懂
回复 支持 反对

使用道具 举报

stellari 发表于 2016-1-9 18:16:13 | 显示全部楼层
是不是西南财经大学?说出来也没啥吧
回复 支持 反对

使用道具 举报

vesalius 发表于 2016-1-9 18:19:07 | 显示全部楼层
俩人握手莫非是想让你搞OOD
回复 支持 反对

使用道具 举报

stellari 发表于 2016-1-9 22:38:35 | 显示全部楼层
第一题题干表述得有点问题,看后面括号里的话的意思,我想应该是“分析两个人握手这一过程,并用合适的数据结构加以描述。”
你可以把一个人想象成一个图上的节点,这个节点可以通过指针和其他节点进行链接。只是要注意,
1. 人有两只手,所以一个节点会有两个指向其他节点的指针。
2. 一般一方伸出右手时,另一方会伸同一只手,所以链接时应保证这一点,即如果A->right == B,那么必有B->right == A。
然后建立一个struct Person,再写个handshake函数,让两个Person建立链接,差不多分数应该就到手了。

第二题是明确问了你“走完XX校区内的建筑物”的方案,所以就不要泛泛而谈。可以实际画一张学校主要建筑物的图出来,然后将说明你如何将其抽象为一张图,然后给出一个实际的走法,并且说明你这种走法有何种理论依据即可。不需要写程序,甚至不需要实际描述算法。

回复 支持 反对

使用道具 举报

dangertrip 发表于 2016-1-9 22:45:49 | 显示全部楼层
第一题不会,第二题状态压缩动态规划搞一下
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 05:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表