首页 - 网校 - 万题库 - 直播 - 雄鹰网校 - 团购 - 书城 - 模考 - 学习通 - 导航 -
首页网校万题库直播雄鹰网校团购书城模考论坛实用文档作文大全宝宝起名
2015中考
法律硕士
2015高考
MBA考试
2015考研
MPA考试
在职研
中科院
考研培训
专升本
自学考试 成人高考
四 六 级
GRE考试
攻硕英语
零起点日语
职称英语
口译笔译
申硕英语
零起点韩语
商务英语
日语等级
GMAT考试
公共英语
职称日语
新概念英语
专四专八
博思考试
零起点英语
托福考试
托业考试
零起点法语
雅思考试
成人英语三级
零起点德语
等级考试
华为认证
水平考试
Java认证
职称计算机 微软认证 思科认证 Oracle认证 Linux认证
公 务 员
导游考试
物 流 师
出版资格
单 证 员
报 关 员
外 销 员
价格鉴证
网络编辑
驾 驶 员
报检员
法律顾问
管理咨询
企业培训
社会工作者
银行从业
教师资格
营养师
保险从业
普 通 话
证券从业
跟 单 员
秘书资格
电子商务
期货考试
国际商务
心理咨询
营 销 师
司法考试
国际货运代理人
人力资源管理师
广告师职业水平
卫生资格 执业医师 执业药师 执业护士
会计从业资格
基金从业资格
统计从业资格
经济师
精算师
统计师
会计职称
法律顾问
ACCA考试
初级会计职称
资产评估师
高级经济师
注册会计师
高级会计师
美国注册会计师
审计师考试
国际内审师
注册税务师
理财规划师
一级建造师
安全工程师
设备监理师
公路监理师
公路造价师
二级建造师
招标师考试
物业管理师
电气工程师
建筑师考试
造价工程师
注册测绘师
质量工程师
岩土工程师
注册给排水
造价员考试
注册计量师
环保工程师
化工工程师
暖通工程师
咨询工程师
结构工程师
城市规划师
材料员考试
消防工程师
监理工程师
房地产估价
土地估价师
安全评价师
房地产经纪人
投资项目管理师
环境影响评价师
土地登记代理人
宝宝起名
缤纷校园
实用文档
入党申请
英语学习
思想汇报
作文大全
工作总结
求职招聘 论文下载 直播课堂
您现在的位置: 考试吧 > 软件水平考试 > 复习资料 > 程序员 > 正文

2015年软件水平考试程序员精选题(4)

来源:考试吧 2015-01-15 11:28:53 考试吧:中国教育培训第一门户 模拟考场
考试吧整理“2015年软件水平考试程序员精选题(4)”供考生参考,更多软件水平考试资讯和备考资料请关注考试吧软件水平考试网。

  查看汇总:2015软件水平考试程序员精选题汇总

  求二元查找树的镜像

  题目:输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。

  例如输入:

  8

  / \

  6 10

  /\ /\

  5 7 9 11

  输出:

  8

  / \

  10 6

  /\ /\

  11 9 7 5

  定义二元查找树的结点为:

  struct BSTreeNode // a node in the binary search tree (BST)

  {

  int m_nValue; // value of node

  BSTreeNode *m_pLeft; // left child of node

  BSTreeNode *m_pRight; // right child of node

  };

  分析:尽管我们可能一下子不能理解镜像是什么意思,但上面的例子给我们的直观感觉,就是交换结点的左右子树。我们试着在遍历例子中的二元查找树的同时来交换每个结点的左右子树。遍历时首先访问头结点8,我们交换它的左右子树得到:

  8

  / \

  10 6

  /\ /\

  9 11 5 7

  我们发现两个结点6和10的左右子树仍然是左结点的值小于右结点的值,我们再试着交换他们的左右子树,得到:

  8

  / \

  10 6

  /\ /\

  11 9 7 5

  刚好就是要求的输出。

  上面的分析印证了我们的直觉:在遍历二元查找树时每访问到一个结点,交换它的左右子树。这种思路用递归不难实现,将遍历二元查找树的代码稍作修改就可以了。参考代码如下:

  ///////////////////////////////////////////////////////////////////////

  // Mirror a BST (swap the left right child of each node) recursively

  // the head of BST in initial call

  ///////////////////////////////////////////////////////////////////////

  void MirrorRecursively(BSTreeNode *pNode)

  {

  if(!pNode)

  return;

  // swap the right and left child sub-tree

  BSTreeNode *pTemp = pNode->m_pLeft;

  pNode->m_pLeft = pNode->m_pRight;

  pNode->m_pRight = pTemp;

  // mirror left child sub-tree if not null

  if(pNode->m_pLeft)

  MirrorRecursively(pNode->m_pLeft);

  // mirror right child sub-tree if not null

  if(pNode->m_pRight)

  MirrorRecursively(pNode->m_pRight);

  }

  由于递归的本质是编译器生成了一个函数调用的栈,因此用循环来完成同样任务时最简单的办法就是用一个辅助栈来模拟递归。首先我们把树的头结点放入栈中。在循环中,只要栈不为空,弹出栈的栈顶结点,交换它的左右子树。如果它有左子树,把它的左子树压入栈中;如果它有右子树,把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子树了。参考代码如下:

  ///////////////////////////////////////////////////////////////////////

  // Mirror a BST (swap the left right child of each node) Iteratively

  // Input: pTreeHead: the head of BST

  ///////////////////////////////////////////////////////////////////////

  void MirrorIteratively(BSTreeNode *pTreeHead)

  {

  if(!pTreeHead)

  return;

  std::stackstackTreeNode;

  stackTreeNode.push(pTreeHead);

  while(stackTreeNode.size())

  {

  BSTreeNode *pNode = stackTreeNode.top();

  stackTreeNode.pop();

  // swap the right and left child sub-tree

  BSTreeNode *pTemp = pNode->m_pLeft;

  pNode->m_pLeft = pNode->m_pRight;

  pNode->m_pRight = pTemp;

  // push left child sub-tree into stack if not null

  if(pNode->m_pLeft)

  stackTreeNode.push(pNode->m_pLeft);

  // push right child sub-tree into stack if not null

  if(pNode->m_pRight)

  stackTreeNode.push(pNode->m_pRight);

  }

  }

  相关推荐:

  2015年软考信息技术处理员考前知识点总结汇总

  2015年软件水平考试《程序员》提高练习题汇总

  2015软件水平考试《程序员》知识点总结汇总

文章责编:wangmeng  
看了本文的网友还看了
文章搜索
软件水平考试栏目导航
版权声明:如果软件水平考试网所转载内容不慎侵犯了您的权益,请与我们联系800@exam8.com,我们将会及时处理。如转载本软件水平考试网内容,请注明出处。
Copyright © 2004- 考试吧软件水平考试网 All Rights Reserved 
中国科学院研究生院权威支持(北京)
在线模拟试题
考证通关杀器
考试最新资讯
一次通关技巧