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 (q<>p) 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 (q<>p) 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<1; j< p>

　　③if(q==p) p=s;

　　④I<1; q==p 注意与②不同!!

　　⑤if(s==p) p=q;

　　⑥q->key=e;

　　⑦q->key!=e

　　类PASCAL语言

　　①new(p); p^.next:=p;

　　②(I<1)or(j< p>

　　③if(q=p) then p:=s;

　　④(I<1)or(q=p)

　　⑤⑥if(s=p) then p:=q;

　　⑥q^.key:=e;

　　⑦q^.key<>e

　　四.程序将单链表逆置(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 (p<>nil) 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年考研专业课 计算机的计算机组成原理真题，望考生通过做真题，考生能够发现自己的知识漏洞，及时的补充和纠正，争取、深度的把握专业课知识，打好专业课的基础。最后，都希望大家考研成功，加油!

　　更多考研专业课信息关注 文都教育