北京邮电大学1999年考研专业课试卷数据结构

2007-05-07 22:46:10  北方邮电大学    
  • 内容显示中
    北京邮电大学1999年数据结构试题
      来自免费考研网www.freekaoyan.com
      1.；2.答案卷应字迹清楚、语义确切；3.算法应说明基本思路，应对主要数据类型、变量给出说明，所写算法应结构清晰、简明易懂，应加上必要的注释；    4.算法可用（类）PASCAL语言、C语言等你所熟悉的高级语言编写，但要注明语种。
      来自免费考研网www.freekaoyan.com
      1 （10分）    选择填空
      ① 字符串’ababaabab’的nextval为
        A．（0，1，0，1，0，4，1，0，1）      B.（0，1，0，1，0，2，1，0，1，）    C．（0，1，0，1，0，0，0，1，1，）     D.（0，1，0，1，0，1，0，1，1）
      ②广义表A=（a,b,(c,d),(e,(f,g))）,则下面式子的值为     ；    Head(Tail(Head(Tail(Tail(A)))))
        A．（g）    B.(d)    C.c    D.d
      ③ 输入序列为（A，B，C，D），不可能得到的输出序列有         ；
        A．（A，B，C，D）  B．（D，C，B，A）  C．（A，C，D，B）  D．（C，A，B，D）
      ④ 散列函数有一个共同性质，即函数值应按     取其值域的每一个值；    A.最大概率   B.最小概率   C.同等概率   D.平均概率
      ⑤ 直接插入排序在最好情况下的时间复杂度为        。    A. O(logn)   B. O(n)    C. O(n*logn)    D(n2)
      免费考研网www.freekaoyan.com
      2 （10分）    判断下列叙述是否正确  ①（101，88，46，70，34，39，45，58，66，10）是堆；     ② 将一棵树转换成二叉树后，根结点没有左子树；     ③ 用树的前序遍历和中序遍历可以导出树的后序遍历；     ④ 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同；      ⑤ 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离很较近。
      来自免费考研网www.freekaoyan.com
      3 （10分）    有一高个比他人都至少高出一头，找他的人都说“根本不用与别人比较，一眼就能找到他”，你认为此话正确吗？为什么？请简要描述两种求N个数中最大值的方法，并给出所需的最少比较次数。
      来自免费考研网www.freekaoyan.com
      4 （10分）    图1是用邻接表存储的图，画出此图，并写出从C点开始按深度优先遍历该图的结果。
    图1  题4图
      免费考研网www.freekaoyan.com
      5（10分）    下面是求无向连通图的最小代价生成 树的一种算法：    将图中所有边按权重从大到小排序为(e1,e2,…,em)    i:=1;
        While (所剩边数≥顶点数)
        Begin        从图中删去ei        若图不再连通，则恢复ei             i:=i+1    End
        试证明这个算法所得的图是原图的最小代价生成树。
      来自免费考研网www.freekaoyan.com
        6 （10分）    已知无向图G和G’互为补图（结点相同、边不重叠、两图合起来为完全图），试证明G或G’是连通的。
      免费考研网www.freekaoyan.com
        7 （10分）    用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度。
      来自免费考研网www.freekaoyan.com
    10 （10分）    试写出以带头结点单链表为存储结构实现简单选择排序的算法。

附近文章

最新文章

发表评论/ 全部评论

  • 验证码:
  • 验证码:
  • 匿名发表:

推荐文章