您的位置:考研教育网> >模拟试题>考研专业课 正文

数据结构工程硕士试题

   2004-08-03 00:00 【 】【我要纠错
  注:1、除第九题外,其他各题每题10分,第九题20分。

  2、所有试题的答案写在答题纸上。

  一、判断下列叙述的对错。

  (1) 线性表的逻辑顺序与物理顺序总是一致的。

  (2) 线性表的顺序存储表示优于链式存储表示。

  (3) 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

  (4) 二维数组是其数组元素为线性表的线性表。

  (5) 每种数据结构都应具备三种基本运算:插入、删除和搜索。

  二、设单链表中结点的结构为

  typedef struct node { //链表结点定义

  ElemType data; //数据

  struct node * Link; //结点后继指针

  } ListNode;

  (1) 已知指针p所指结点不是尾结点,若在*p之后插入结点*s,则应执行下列哪一个操作?

  A. s->link = p; p->link = s;

  B. s->link = p->link; p->link = s;

  C. s->link = p->link; p = s;

  D. p->link = s; s->link = p;

  (2) 非空的循环单链表first的尾结点(由p所指向)满足:

  A. p->link == NULL;

  B. p == NULL;

  C. p->link == first;

  D. p == first;

  三、设有一个顺序栈S,元素s1, s2, s3, s4, s5, s6依次进栈,如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1,则顺序栈的容量至少应为多少?

  四、一棵具有n个结点的理想平衡二叉树(即除离根最远的最底层外其他各层都是满的,最底层有若干结点)有多少层?若设根结点在第0层,则树的高度h如何用n来表示(注意n可能为0)?

  五、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句,将其编号填入相应的括号内。

  (1) 对于一个具有n个结点和e条边的无向图,若采用邻接表表示,则顶点表的大小为( A ),所有边链表中边结点的总数为( B )。

  (2) 采用邻接表存储的图的深度优先遍历算法类似于树的( C )。

  (3) 采用邻接表存储的图的广度优先遍历算法类似于树的( D )。

  (4) 判断有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用( E )。

  供选择的答案

  A:① n ② n+1 ③ n-1 ④ n+e

  B:① e/2 ② e ③ 2e ④ n+e

  C~D:① 中根遍历 ② 先根遍历 ③ 后根遍历 ④ 按层次遍历

  E:① 求关键路径的方法 ② 求最短路径的Dijkstra方法

   ③ 深度优先遍历算法 ④ 广度优先遍历算法

  六、填空题

  (1) 在用于表示有向图的邻接矩阵中, 对第i行的元素进行累加, 可得到第i 个顶点的( ① )度, 而对第j列的元素进行累加, 可得到第j个顶点的( ② )度。

  (2) 一个连通图的生成树是该图的( ③ )连通子图。若这个连通图有n个顶点, 则它的生成树有( ④ )条边。

  (3) 给定序列{100, 86, 48, 73, 35, 39, 42, 57, 66, 21}, 按堆结构的定义, 则它一定( ⑤ )堆。

  (4) 在进行直接插入排序时, 其数据比较次数与数据的初始排列( ⑥ )关;而在进行直接选择排序时,其数据比较次数与数据的初始排列( ⑦ )关。

  (5) 利用关键码分别为10, 20, 30, 40的四个结点,能构造出( ⑧ )种不同的二叉搜索树。

  七、设带表头结点的双向链表的定义为

  typedef int ElemType;

  typedef struct dnode { //双向链表结点定义

  ElemType data; //数据

  struct dnode * lLink, * rLink; //结点前驱与后继指针

  DblNode;

  typedef DblNode * DblList; //双向链表

  试设计一个算法,改造一个带表头结点的双向链表,所有结点的原有次序保持在各个结点的右链域rLink中,并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。

  八、设有一个关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 ,(1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。

  (2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。

  九、下面是求连通网络的最小生成树的Prim算法的实现,中间有5个地方缺失,请阅读程序后将它们补上。

  const int MaxInt = INT_MAX; //INT_MAX的值在中

  const int n = 6; //图的顶点数, 应由用户定义

  typedef int AdjMatrix[n>[n>; //用二维数组作为邻接矩阵表示

  typedef struct //生成树的边结点

  int fromVex, toVex; //边的起点与终点

  int weight; //边上的权值

  TreeEdgeNode;

  typedef TreeEdgeNode MST[n-1>; //最小生成树定义

  void PrimMST ( AdjMatrix G, MST T, int rt ) {

  //从顶点rt出发构造图G的最小生成树T,rt成为树的根结点

  TreeEdgeNode e; int i, k = 0, min, minpos, v;

  for ( i = 0; i < n; i++ ) //初始化最小生成树T

  if ( i != rt ) {

  T[k>.fromVex = rt;

  T[k>.toVex = I ;

  T[k++>.weight = G[rt>;

  } for ( k = 0; k < n-1; k++ ) { //依次求MST的候选边

  min = MaxInt ;

  for ( i = k; i < n-1; i++ ) //遍历当前候选边集合

  if ( T.weight < min ) //选具有最小权值的候选边

  { min = T.weight; minpos = i ; } if ( min == MaxInt ) //图不连通, 出错处理

  { cerr 《 “Graph is disconnected!” 《 endl; exit(1) ; } e = T[minpos>; T[minpos> = T[k> ; T[k> = e;

  v = T[k>.toVex;

  for ( i = k+1; i < n-1; i++ ) //修改候选边集合

  if ( G[v>[T.toVex> < T.weight )

  T.weight = G[v>[T.toVex>;

  T.fromVex = v ;

  参考答案

  一、(1) 错 (2) 错 (3) 对 (4) 错 (5) 对

  二、(1) B (2) C

  三、3

  四、h = élog2(n+1)ù -1

  五、A. ① B. ③ C. ② D. ④ E. ③

  六、① 出 ② 入 ③ 极小 ④ n-1

  ⑤ 是(最小) ⑥ 有 ⑦ 无 ⑧ 14

  七、算法如下

  void sort ( DblNode * L ) {

  DblNode * s = L->rlink;

  //指针s指向待插入结点, 初始时指向第一个结点

  while ( s != NULL ) { //处理所有结点

  pre = L; p = L->lLink;

  //指针p指向待比较的结点, pre是p的前驱指针while ( p != NULL && s->data < p->data )

  //循lLink链寻找结点 *s的插入位置{ pre = p; p = p->lLink; } pre->lLink = s; s->lLink = p; s = s->rLink;

  //结点 *s在lLink方向插入到 *pre与 *p之间}

  八、关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 }

  在等概率下查找成功的平均查找长度

  在等概率下查找不成功的平均查找长度

  九 ① T[k>.toVex = i

  ② min = MaxInt

  ③ minpos = i

  ④ exit(1)

  ⑤ T.fromVex = v
◇ 编辑推荐
·2020年医学硕士辅导
·2019年考研真题解析
·2020考研公共课网上辅导课程
·2020考研管理类联考网上辅导热招!!
·2020考研英语全程班620元
·2020考研政治全程班580元
相关热词:
 考研教育网官方微信

微信公众账号cnedu_cn

 网上辅导课程特色
  • 即报即学
  • 名师团队
  • 反复看课
  • 在线答疑
  • 移动教学
  • 讲义下载
  • 课后练习
  • 模拟测试
 24小时报名咨询
辅导课程
辅导体系 授课教师 招生方案 课时 价格 购买
考研政治
导学、基础、强化、冲刺、点题班赠19年导学、基础班 米 鹏 方案 109 580元 购买
考研英语
导学、基础、强化、冲刺、点题班赠19全程班 夏徛荣 方案 159 620元 购买
考研数学一
包含基础、强化、冲刺 赠19年特色班课程 李永乐团队 方案 210 919元 购买
考研数学二
包含基础、强化、冲刺 赠19年特色班课程 李永乐团队 方案 210 739元 购买
考研数学三
包含基础、强化、冲刺 赠19年特色班课程 李永乐团队 方案 210 919元 购买

医学硕士

基础班强化班冲刺班全程班
方案价格购买 方案价格购买方案价格购买方案价格购买
中医综合
方案 420元 购买 方案 360元 购买 方案 300元 购买 方案 880元 购买
西医综合
方案 420元 购买 方案 360元 购买 方案 300元 购买 方案 880元 购买
辅导课程
辅导体系 授课教师 招生方案 课时 价格 购买
英语二
含导学、基础、强化、冲刺班 乔老师 方案 108 1600元 购买
数学(全程班)
含导学、基础、强化、真题、冲刺班 官老师 方案 120 1600元 购买
逻辑(全程班)
导学、基础、强化、冲刺 真题班 丁老师 方案 120 1600元 购买
写作(全程班)
含导学、基础、强化、冲刺班 胡元奎 方案 30 1200元 购买
管综(全程班)
含数学、逻辑、写作三部分的基础、强化、冲刺班 名师团 方案 270 4500元 购买
管综+英语二
英语二全程班+管综全程班 比单报优惠600元 名师团 方案 386 5800元 购买