加入QQ群
关闭
设为首页收藏本站

思远福大考研论坛

 找回密码
 注册

QQ登录

只需一步,快速开始

查看: 2474|回复: 0

1998年福大应用数学考研试题(回忆版)

[复制链接]

154

主题

0

好友

0

积分

新手上路

Rank: 1

金钱
0
威望
0
花香草 发表于 2011-3-25 10:11:58 |显示全部楼层
一、选择题(20分,每小题2分)
1、递归过程或函数调用时,处理参数及返回地址,要用一种称为()的数据结构。
    (1)队列 (2)多维数组(3)栈(4)线性表
2、顺序查找,在等概率情况下,其平均查找长度为()
     (1)n (2)2n (3)n+1 (4)(n+1)/2
3、下列排序算法中,其中()是稳定的。
     (1)堆排序,冒泡排序 (2)快速排序,堆排序 (3)直接选择排序,归并排序
     (4)归并排序,冒泡排序
4、设输入序列为A,B,C,D,借助一个栈规定A 最先输出的不可能的输出序列为()
     (1)A,B,D,C  (2)A,D,C,B  (3)A,D,B,C  (4)A,C,D,B
5、设给定权值总数有n 个,其哈夫曼树的结点总数为()
     (1)不确定 (2)2n (3)2n+1 (4)2n-1
6、下列四棵二叉树中()是一个堆。

7、()遍历一棵二叉排序树所得的结点访问序列是按键值的递增序列。
     (1)先序 (2)中序 (3) 后序 (4)以上均不是
8、链表不具有的特点是()
     (1)插入删除不需要移动元素。
     (2)可随机访问任意元素。
     (3)不必要先估计存储空间   
     (4)所需空间与线性长度成正比。
9、下列序列中,()是执行第一趟快速排序后所得的序列。
     (1)[68,11,18,69]   [23,93。73]
     (2)[68,11,69,23]   [18,93,73]
     (3)[93,73]   [68,11,69,23,18]
     (4)[68,11,69,23,18]   [93,73]
10、假设以行序为主序存贮二维数组A=array[1。。100,1。。100],设每个数据元素
    占2各存贮空间,基地址为10,则LOC[5,5]=()
    (1)808 (2)818 (3)1010 (4)1020
     二、填空题(20分,每小题2分)
  1、采用散列技术时,需要考虑的两个主要问题是:
    (1)————————————————
    (2)————————————————
  2、设无向图 G 有n  个顶点和e 条边,每个顶点Vi 的度为di(1〈=i〈=n),则
     e=————————————
  3、循环链表的最大优点是:——————————————
  4、INDEX(‘DATASTRUCTERE’,‘STR’)=——————————————
  5、循环对列为满的条件————————————
  6、上三角矩阵压缩的下标对应关系为:————————————————
  7、在双链表结构中,若要求在p 指针所指的结构之前插入指针为s 所指的结点,则需
     执行下列语句:
     s^ 。next:=p; s^ 。prior:=————;p^ 。prior:=s; ————:=s;
  8、若静态查找表的类型定义如下:
      TYPE  RECTYPE=RECORD
               key:keytype;
                。。。。。
               end;
      ordlisttp=attay[1。。n]of rectype;
     请完成以下二分查找的算法:
     FUNC binsrch(r:ordlisttp;k:keytype):integer;
       BEGIN
         low:=1;hig:=n;suc:=false;
     WHILE————AND NOT(suc)DO
       [MID:=——-;
       case
       k》r[MID]。key:low:=MID+1;
       K=r[MID]。key:suc:=true;
       k《r[MID]。key:hig:=MID-1
       END;]
    IF suc  then————————
            else————————
    end;

9、对下列二叉树,其对应的顺序存贮结构为:——————————。

10、分别采用堆顺序,快速顺序,冒泡排序和归并排序,对初态为有序的表则最省时间
     为————————算法,最费时间得是————算法。
三、应用题:(30分,每小题6分)
  1、已知二叉树的后序序列为ABCDEFG 和中序序列为ACBGEDF,构造出该二叉树。
  2、应用PRIM算法,求出下列图的最小生成数。

  3、设散列函数为H(K)=K MOD 13,给定的键值序列为13,41,15,44,06,68,
      12,25,38,64,19,49,画出用链地址法处理冲突构造得的哈希表。
  4、拓扑排序的结果是否唯一,为什么?
  5、举例说明顺序队的“假溢出”现象,并给出解决方案。
四、设计题:(30分,每题10分)
  1、已知A,B,C为三个元素值递增有序的线性表,现要求对A 表作如下运算:删除那些既在B 中出现又在表C 中出现的元素,要求以链表作存贮结构,编写实现上述运算的算法。
     注:(1)结点形式为            
         (2)线性表基本运算可在接调用。
  2、 设一棵二叉以二叉链表为存贮结构,结点结构为 ,设计一个算法将二叉树中所有结点的左,右子树相互交换。
  3、设数组A[1。。n]中,  A[n-2k+1。。n]和  [n-k+1。。n]中元素各自从小到大
     排好序,试设计一个算法使A[n-2k+1。。n]按从小到大次序排好序。并分析算法
     所需的计算时间。
您需要登录后才可以回帖 登录 | 注册

关闭

站长推荐上一条 /2 下一条

Archiver|手机版|思远福大考研论坛   document.write ('');

GMT+8, 2019-5-22 11:14

Powered by Discuz! X2.5

© 2001-2012 Comsenz Inc.

回顶部