|
|
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年考研专业课 计算机的计算机组成原理真题，望考生通过做真题，考生能够发现自己的知识漏洞，及时的补充和纠正，争取精确、深度的把握专业课知识，打好专业课的基础。最后，都希望大家考研成功，加油!
更多考研专业课信息关注 文都教育 |
|
发表于 2016-6-26 16:26:03