考研论坛

 找回密码
 立即注册
查看: 13|回复: 0

考研专业课:北京工业大学计算机真题(2001)

[复制链接]

2万

主题

2万

帖子

8万

积分

论坛元老

Rank: 8Rank: 8

积分
87347
发表于 2016-6-26 16:26:03 | 显示全部楼层 |阅读模式
  2014 考研专业课大纲已经发布,考生要对照大纲的变化好好复习,调整自己的规划。同时要关注各高校历年真题,利用真题和大纲做好考前的强化备考。文都教育 考研专业课频道为考生提供10大高校计算机复习考题,希望考生认真利用这些真题,仔细研究,寻找突破点,及时的查漏补缺,复习好计算机专业课,下面请看。
  一.多选/填空题。
  1. 一个栈的入站元素序列是1,2,3,4,5若允许出栈操作可在任意可能的时刻进行,则下面的序列中。不可能出现的出栈序列是(),理由是()。
  A.3,4,2,5,1
  B.2,5,4,1,3
  C.2,3,1,5,4
  D.3,5,4,2,1
  2. 一棵二叉树的前序遍历序列为ABCDEFG,它的中序序列可能是()
  A. CABDEFG
  B. ABCDEFG
  C. DACEFBG
  D.BADCFEG
  3. 下面结构中最适于表示稀疏无向图的是(),适于表示有向图的是()
  A. 邻接矩阵
  B. 逆邻接表
  C. 邻接多重表
  D.十字链表
  E. 邻接表
  4. 采用败者树进行K路平衡归并时,总的(包括访外)效率与K()
  A. 有关
  B. 无关
  5. N个顶点连通无向图的邻接矩阵至少有()个非0元素,至多有()个非0元素;n个顶点的强连通有向图至少有()条弧。
  6. 含4个度为2的结点和5个叶子结点的二叉树,可有()个度为1的结点。
  二.简答题
  1. 上三角阵A(N*N)按行主序压缩存放在数组B中,其中A[I,j]=B[K].写出用I,J表示的K。
  2. 画出广义表A=(a,(b,()),(((),c)))的第一种存储结构(表结点第二指针指向余表)图,并用取首元(head())和取尾元(tail())函数表示原子c。
  3. 证明:在二叉树的三种遍历序列中,所有叶子结点间的先后关系都是相同的。要求每步论断都指出根据。
  4. 是述哈希表中不成功的平均查找长度概念,求法,和理由。
  5. 对于输入关键字序列48,70,65,33,24,56,12,92进行:
  a. 建立堆排序的初始堆(小顶堆),要求画出主要过程。
  b. 建一棵平衡二叉树,画出过程(至少每次调整有一张,标出最小不平衡子树的根)。
  三.下面程序段实现用尾指针表示,带头结点单链环的操作,请补足空缺部分。
  typeder struct node{ program ppp;
  Elemtype key; type elemtype=char;
  Struct node *next; link=^node;
  Node,*link; node=record
  Key:elemtype; next:link;
  Oid init(llink &p) } end;
  C语言
  Void ins(link &p,int I,elemtype e) {
  int j; link q,s;q=p->next; j=0;
  while (q!=p && jnext; j++;}
  if (②填空 ) exit(error)
  s=(link)malloc(sizeof(node));
  s->key=e; s->next=q->next=s; q->next=s;/*维护*/
  ③填空
  return;
  }
  void del(link &p,int I,elemtype &e) {
  int j; link q,s;
  q=p->next j=0;
  while (q!=p &&jnext; j++;}
  if (④填空 )exit(error)
  s=q->next; q->next=s->next; e=s->key;/*维护*/
  ⑤填空
  free(s); return;
  }
  find (link p,elemtype e) {
  int I; link q;
  q=p->next;⑥填空; q=q->next; I=1;
  while (⑦填空 ) {q=q->next; I++;}
  if (q=p->next) return 0;
  else return I;
  } /*循环条件中只有一次比较*/
  类PASCAL语言
  proc init(var p:link);
  begin ①填空 end;
  proc ins(var p:link; I:integer; e:elemtype);
  var j:integer; q,s:link;
  begin q:=p^.next; j:=0;
  while (qp) and (j
  [q:=q^.next;j:=j+1]
  if ②填空 then exit(error);
  new(s); s^.key=e;
  s^.next:=q^.next; q^.next:=s; /*维护*/
  ③填空
  end;
  proc del(var p:link; I:integer; var e:elemtype);
  var j:integer;q,s:link;
  begin q:=p^.next; j:=0;
  while (qp) and (j
  [q:=p^.next; j:=j+1];
  if ④填空 then exit(error);
  s:=q^.next; q^.next=s^.next; e:=s^.key; ⑤填空; /*维护*/
  dispose(s)
  end;
  func find(p:link; e:elemtype):integer:
  q:link; I:integer;
  begin q:=p^.next; ⑥填空;
  q:=q^.next; I:=1;
  while ⑦填空 do
  [q:=q^.next; I:=I+1];
  if (q=p^.next) then return (0)
  else return(i)
  end; /*循环条件中只有一次比较*/
  北京工业大学2001年研究生入学考试试题答案
  一.单选/多选和填空题,每空2分,共20分
  1.〈1〉B 〈2〉1比3先进栈,应后出栈。 A= 1, 1, 1, ^
  2.〈3〉BD
  3.〈4〉C 〈5〉BDE 0,a 1, 1, ^^ 1, ^
  4.〈6〉A
  5.〈7〉2*(n-1)〈8〉n*(n-1) 〈9〉n 0,b 1,^ 1, ^
  6.〈10〉任意多
  二.简答题25分
  1.(5分)
  用I,j表示k: k=(n+n-I-2)(I-1)/2+j-I=(2n-I)(I-1)/2+j。
  2.(5分) c=head(tail(head(head(tail(tail(A))))))
  3.(5分)取任意两个叶结点u,v,它们同属于一棵二叉树,必有共同祖先,记其中最近的为w,u,v不会是w,若是就不可能为叶子;故u,v 分属w的左右子树,设u在左,则按定义,在三种遍历序列中,u都在v前面。由u,v的任意性可知,所有叶子结点的先后关系都是相同的。
  4.(4分)哈希表中不成功的平均查找长度概念和求法指:从每个可能的哈希地址开始按算法约定的探测方法试探,直至找到空闲单元为止,其间进行比较的次数即为该地址的不成功查找长度。所有可能的哈希地址的不成功查找长度的平均值,就是哈希表的不成功平均查找长度(2分)。不成功查找对应的关键字可能是无穷的,但映射到每个哈希地址都是可能的,因此,在没有先验知识的情况下,认为它们映射到每个哈希地址的概率相等是合理的假设(2分)。
  5.(6分)
  ① 48 48 12
  / / /
  70 65 24 12 24 43
  / / / / / /
  33 24 56 12 33 70 56 65 33 70 56 65
  / / /
  92 92 92
  ② *48 65 *65 48
   / / /
  70 *43 70 33 70 *33 65
  / / / / /
  65 33 24 48 24 56 70
  / /
  24 56 12
  48
  /
  24 65
  / /
  12 33 56 70
  
  92
  三.程序填空,每空3分,共21分
  C语言
  ①p=(link)malloc(sizeof(node));
  p->next=p;
  ②I
  ③if(q==p) p=s;
  ④I
  ⑤if(s==p) p=q;
  ⑥q->key=e;
  ⑦q->key!=e
  类PASCAL语言
  ①new(p); p^.next:=p;
  ②(I
  ③if(q=p) then p:=s;
  ④(I
  ⑤⑥if(s=p) then p:=q;
  ⑥q^.key:=e;
  ⑦q^.keye
  四.程序将单链表逆置(4分),存入一个带头结点,用尾指针表示的单向循环链表(2分)。
  算法时间复杂度为0(n),每递归调用一层即进入下一结点,调用深度与表的相当,退出时
  处理插入,每层复杂度为0(1),故总的复杂度为0(n)。(2分)
  五.(10分) C语言
  ypedef char elemtype;
  type def struct node{
  elemtype key;
  struct node *f,*b;/*f为孩子指针*/
  }node,link;
  link t;
  pp(link p){
  if (!p) return 0;
  if(!pàb) {
  printf(“%c”,pàkey);
  return pp(pàf)+1;
  }
  else return pp(pàf)+pp(pàb);
  }
  main(){
  int j;
  建根指针t指出的森林的二叉树表示;
  j=pp(t);
  printf(“nNumj=%dn”,j);
  }
  类PASCAL语言
  program ppp;
  type elemtype=char;
  link=^node;
  node=record
  key:elemtype;
  f,b:link;
  end;
  var t:=link; j:=integer;
  func pp(p:link):integer;
  begin If p=nil then return(0)
  if p^.b=nil then write (p^.key);
  return (pp(p^.f)+1)
  else return (pp(p^.f)+pp(p^.b))
  end;
  begin
  建根指针t指出的森林的二叉树表示;
  j:=pp(T);
  writeln;writerln(‘Num=’,j)
  end.
  评分标准:结构定义2分,统计兄弟指针为空2分,递归算法(公共变量-过程亦可)4分,正确输出2分
  六.(16分)根据右表给出的顶点数,边数,顶点信息,弧的信息 9 11(边,权)按在链头插入的算法: ABCDEFGHI
  1. (6分)画出AOE网的邻接表结构图,并用类C(或类PASCAL) AB 3
  描述类型。 AD 2
  2. (4分)按结构图和求关键路径的算法写出顶点的拓扑排序序列, AE 4
  估算拓扑排序算法的时间复杂度。 BC 1
  3. (6分)求出各弧代表的活动的最早开始时间和最迟开始时间,指 DC 3
  出关键活动。 EH 2
  1. 0 Aà 4,4 à 3,2 à 1,3 ^ CF 1
  1 B à2,1 ^ CG 3
  2 C à 6,3 à 5,1 ^ HG 2
  3 Dà 2,3 ^ FI 5
  4 Eà 7,2 ^ GI 4
  5 F à 8,5^
  6 Gà 8,4 ^ 邻接表结构图
  7 H à 6,2^
  8 I ^
  2.ABDCFEHGI o(e+n)
  3. e ee el mark
  AB 0 1
  AD 0 0 *
  AE 0 0 *
  BC 3 4
  DC 2 2 *
  EH 4 4 *
  CF 5 6
  CG 5 5 *
  HG 6 6 *
  FI 6 7
  GI 8 8 *
  六.1类型定义
  C语言
  #define maxvnum 20
  typedef struct arctype {
  int headnum,cost;
  struct arctype *next;
  }arctype,*link;
  typedef struct {
  elemtype key;
  link firsttout;
  }vextype;
  typedef struct {
  vextype vex[maxvnum];
  int vexnum,arcnum;
  }adjlist;
  类PASCAL语言
  const maxvnum=20;
  type
  link=^arctype;
  arctype=record
  headnum,cost: integer;
  next: link
  end;
  vextype=record
  key: elemtype;
  firsttout: link
  end;
  adjlist=record
  vex: array[1..macvnum] of vextype;
  vexnum,arcnum: integer
  end;
  四.(8分)阅读下面的程序,指出过程pp完成的功能几结果数据结构的名称,并估计算法的时间复杂度0(?),说明理由。设单链表长度为n。
  C语言
  Typedef char elemtype;
  Typedef struct node{
  Elemtype key;
  Strcut node *next;
  }node,*link;
  link la ;
  void pp(link p) {
  if (p) {
  pp(p->next); p->next=la->next;
  la->next=p;la=p;
  } return;
  }
  main () {
  link q;
  建立用la指出的带头结点的单链表;
  q=la->next; la->next=la; pp(q);
  输出用la指出的链式结构的数据元素;
  return 1;
  }
  类PASCAL语言
  Program ppp;
  Tyoe elemtype=char;
  Link=^node;
  Node=record
  Key:elemtype;
  Next:link;
  End;
  Var la,q:link;
  Proc pp(p:link);
  Begin
  If (pnil) then
  Begin pp(p^.next);
  P^.next:=la^.next;
  La^.next:=p; la:=p
  End
  End;
  Begin
  建立用la指出的带头结点的单链表;
  q:=la^.next; la^.next:=la; pp(q);
  输出用la指出的链式结构的数据元素;
  end.
  五.(10分)编程打印出用孩子兄弟链表表示的森林中最小兄弟(无弟弟者) 结点并统计输出其个数。设结点数据域为字符(字母),要求描述所用结构。
  六.(16分)根据右表给出的顶点数,顶点信息,弧的信息按在链头插入的算法:
  1.(6分)画出AOE网的邻接表结构图,并用类C(或用类pascal)描述类型。
  2.(4分)按结构图和求关键路径的算法(!!)写出顶点的拓扑排序序列,
  估计拓扑排序算法的复杂度。
  3.(6分)求出各弧代表的活动的最早开始时间和最迟开始时间,指出关键活动。
  9 11
  ABCDEFGHI
  AB 3
  AD 2
  AE 4
  BC 1
  DC 3
  EH 2
  CF 1
  CG 3
  HG 2
  FI 5
  GI 4
  上面是北京工业大学2001年考研专业课 计算机的计算机组成原理真题,望考生通过做真题,考生能够发现自己的知识漏洞,及时的补充和纠正,争取精确、深度的把握专业课知识,打好专业课的基础。最后,都希望大家考研成功,加油!
  更多考研专业课信息关注 文都教育
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|新都网 ( 京ICP备09058993号 )

GMT+8, 2018-11-16 17:39 , Processed in 0.246433 second(s), 7 queries , WinCache On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表