新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『 计算机考研交流 』 → [DS]两道俺认为有可能考的题目 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 13284 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： [DS]两道俺认为有可能考的题目 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     Smilingface 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(要不要学学XML呢?)
      文章：84
      积分：577
      门派：XML.ORG.CN
      注册：2006/3/31

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Smilingface发送一个短消息 把Smilingface加入好友 查看Smilingface的个人资料 搜索Smilingface在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Smilingface的博客楼主
    发贴心情 [DS]两道俺认为有可能考的题目

    1.这是一道04级的作业题目，题目看起来很简单，可是限定了苛刻的时空限制。具体题目如下：
       设计算法，将数组A(0....n-1)中的元素循环右移k位，要求只用一个元素大小的附加存储空间，元素移动或交换次数为O(n).
       可能的思路：(1)每次移一位，移k次。False,时间代价O(n^2)
                         (2)从第一个元素开始，将A(0)保存在辅助存储空间中，将A(0)位用正确的值(A(n-k))填好，此时A(n-k)位空出，再将正确的值填进来，一直进行下去，直到某一次正确的值是保存在辅助空间里的A(0)为止。这种算法可以确保O(n)的时间开销，但是存在一个问题，那就是算法结束时，不一定所有的位都一定填上了正确的值，也就是说在全部完成之前陷入了循环。比方说n=4,k=2.我曾经想过的解决的办法是陷入循环后用线性探测法从下一位开始重新调用算法，
    但是由此带来的问题是:(1)是否能够确定下一位一定是没有填入正确值的(比方说A(0)陷入循环以后从A(1)开始，能够说明A(1)一定是没有填入正确位的吗)  以及(2)在以后算法运行当中是否能确保不会重复访问（关系到时间代价的问题）.
    当然可以采用添加标志位的方法来回避上面的问题，但是这又违背了只能有一个元素大小的附加存储空间的要求.:-(
    大家讨论讨论，还请高手不吝赐教啊。

    2.表达式树以中缀形式输出。这个应该是很重要的考点吧，习题解析上有具体的算法P76-77页,可是觉着那个算法写的有点问题啊，case *,和case /的情况的讨论中，对其右孩子的符号的讨论上面是当为“+”或“-”的时候才打印括号，显然是错的吧，应该只要是运算符就打印才对啊。


       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/15 20:48:00
     
     carroty 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(GRE考了1600分!)
      文章：153
      积分：1257
      门派：IEEE.ORG.CN
      注册：2006/4/4

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给carroty发送一个短消息 把carroty加入好友 查看carroty的个人资料 搜索carroty在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看carroty的博客第2楼
    发贴心情 
    第一个问题,应该发掘问题的更多条件:

    一种可能的解法是把数组先逆置,然后将前k个数再逆置,然后将后n-k个数也逆置.这样应该再0(n)的时间内就可以实现了.

    习题书上好像还又一种方法,我忘记了,你可以去查一下.

    :)

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/15 21:34:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第3楼
    发贴心情 
    提示：
    （1）海豚算法。

    （2）直接中序周游就可以了，算法一处小的修改：判断子树的符号优先级是否高于当前节点，如果低于，子树的输出需要加个括号。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/15 22:25:00
     
     Smilingface 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(要不要学学XML呢?)
      文章：84
      积分：577
      门派：XML.ORG.CN
      注册：2006/3/31

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Smilingface发送一个短消息 把Smilingface加入好友 查看Smilingface的个人资料 搜索Smilingface在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Smilingface的博客第4楼
    发贴心情 
    今天在习题集上看到了，觉得这个用三个逆置来做的算法真是很巧妙啊。Thank you!!
    以下是引用carroty在2006-12-15 21:34:00的发言：
    第一个问题,应该发掘问题的更多条件:

    一种可能的解法是把数组先逆置,然后将前k个数再逆置,然后将后n-k个数也逆置.这样应该再0(n)的时间内就可以实现了.

    习题书上好像还又一种方法,我忘记了,你可以去查一下.

    :)


    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/16 18:54:00
     
     Smilingface 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(要不要学学XML呢?)
      文章：84
      积分：577
      门派：XML.ORG.CN
      注册：2006/3/31

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Smilingface发送一个短消息 把Smilingface加入好友 查看Smilingface的个人资料 搜索Smilingface在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Smilingface的博客第5楼
    发贴心情 
    以下是引用Supremgoooo在2006-12-15 22:25:00的发言：
    提示：
    （2）直接中序周游就可以了，算法一处小的修改：判断子树的符号优先级是否高于当前节点，如果低于，子树的输出需要加个括号。


    当父结点为*或/时，对其右子树，不论其符号是+，-还是*，/都应该加括号。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/16 19:02:00
     
     teng_t1986 帅哥哟，离线，有人找我吗？天秤座1986-10-22
      
      
      威望：1
      头衔：智能缔造者
      等级：计算机学士学位(版主)
      文章：368
      积分：2273
      门派：IEEE.ORG.CN
      注册：2006/4/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给teng_t1986发送一个短消息 把teng_t1986加入好友 查看teng_t1986的个人资料 搜索teng_t1986在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给teng_t1986 访问teng_t1986的主页 引用回复这个贴子 回复这个贴子 查看teng_t1986的博客第6楼
    发贴心情 
    2题递归很容易的，非递归就麻烦了……
    PS:c++中string可以很方便的使用+运算。

    ----------------------------------------------
    书山奋战不觉难，
    一刻光阴莫等闲。
    长路遥遥飞浩志，
    前尘洗却作泥丸。
    粗茶薄被心灯暖，
    明月清窗几案寒。
    欲待桂枝香万里，
    海阔天空俱欢颜。

    My blog:http://hi.baidu.com/tengteng2007

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/16 20:15:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第7楼
    发贴心情 
    the left just need inforior condition,right needs not superior condition.

    here's my answer:
    void disinfix(infixtreenode *r)
    {
        if(!r) return;
        
        if(sign(r->l())&&inforior(r->l(),r))
        {
            cout<<"(";
            disinfix(r->l());
            cout<<")";
        }
        else disinfix(r->l());
        
        cout<<r->v();
        
        if(sign(r->r())&&!superior(r->r(),r))
        {
            cout<<"(";
            disinfix(r->r());
            cout<<")";
       
        }
        else disinfix(r->r());   
    }


    [此贴子已经被作者于2006-12-16 22:51:16编辑过]
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/16 20:55:00
     
     Smilingface 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(要不要学学XML呢?)
      文章：84
      积分：577
      门派：XML.ORG.CN
      注册：2006/3/31

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Smilingface发送一个短消息 把Smilingface加入好友 查看Smilingface的个人资料 搜索Smilingface在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Smilingface的博客第8楼
    发贴心情 
    恩，这样写是对的。所以我说书上的那个算法有点问题，它用的case语句分别讨论的，结果讨论"*"和“/”的右孩子的时候只是在其右孩子为“+”，“-”的时候加了括号。
    以下是引用Supremgoooo在2006-12-16 20:55:00的发言：
    the left just need inforior condition,right needs not superior condition.

    here's my answer:
    void disinfix(infixtreenode *r)
    {
         if(!r) return;
         
         if(sign(r->l())&&inforior(r->l(),r))
         {
             cout<<"(";
             disinfix(r->l());
             cout<<")";
         }
         else disinfix(r->l());
         
         cout<<r->v();
         
         if(sign(r->r())&&!superior(r->r(),r))
         {
             cout<<"(";
             disinfix(r->r());
             cout<<")";
        
         }
         else disinfix(r->r());   
    }


    [此贴子已经被作者于2006-12-16 22:51:16编辑过]


    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/17 19:33:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/5/3 9:14:30

    本主题贴数8，分页： [1]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 8,218.750ms