武汉大学计算机考研专业试题(有答案),内部笔记
武汉[wiki]大学[/wiki]计算机[wiki]考研[/wiki]专业试题(有答案),内部笔记[free]**** 回复后可显示 *****[/free]
武汉大学1997年研究生入学考试编译原理试题（共55分）
$ B" E5 y) n5 r) Y2 q6 C
" V8 r k$ l: l- p; H8 p1. (4分)
7 L/ ?4 O8 o! j' e" }[size=0px]8 P& X) R& o/ Q6 U1 d[/size]
设有语言L(G)={adaR | aÎ(a,b)*, aR 为a之逆}，试构造产生此语言的上下文无[size=0px]# n. x1 ]; f/ F( C; L# {' y' x( V[/size]
关文法G。
& t# m9 D' R/ F! g( q! [. J
' i1 P$ C a4 ~* D! m) p- D. ^7 N2. (10分)[size=0px]3 u: g+ ?. z5 h$ ~' x* y4 z[/size]
[size=0px]- k2 |. S; g" H1 B: o$ w; A! I[/size]
设有语言L(G)={a2nb2n+1a2n | n30}
* w; w9 s) e d& w9 N8 a% _' N) ?
( r3 ^' C4 y& T5 \1 I2 F' Q① 给出描述语言的正则表达式R；[size=0px]# v& Z3 b8 O4 t7 H* u[/size]
) q$ `2 t1 J: r4 a% `6 i& X" B② 直接画出识别该语言的状态转换图。
7 a- @$ G2 P* V
5 t8 O3 X! ]2 _3 w3. (8分)[size=0px]& k% ]$ t3 d1 M- K. T7 u# w7 z, j[/size]
) X& S- p) _+ d- pLR分析器与优先分析器在识别句柄时的主要异同是什么？
+ D- W% i2 q8 D) `[size=0px]0 W) Q: e5 [1 ^% A! v: ~0 z1 r[/size]
4. (6分)
* k; p L' j3 Y5 i4 G& O
. d5 n* m7 ?# L7 n/ A/ ]. n) W什么是规范句型的活前缀？引进它的意义何在？
& u7 ^( D8 H1 Y' `8 B4 b; T[size=0px]1 ?6 G1 t8 K; ][/size]
5. (9分)
. |9 w8 M+ k2 i[size=0px]: a7 n4 f t' H1 @( N) T6 ~[/size]
(简答下列问题)
' D: H2 E0 Q8 E! n6 p/ G9 l
8 v1 v' C9 m& j0 @( o1 k① 批处理、分时和实时操作系统各有什么特点？
) u9 I1 O( W9 h
- d3 Z' |* s, V: {② 文件有那几种逻辑结构？有哪几种物理结构？[size=0px]) }% j. s2 T; ]5 f[/size]
[size=0px]! `5 f$ o# P8 P- L[/size]
③ 产生死锁的必要条件是什么？[size=0px]8 p4 @* x r! e/ a[/size]
0 R( h3 ?+ x, ?9 a# X. v* E6 S6. (9分)
- S; a. o% ]- R* Z6 i" F[size=0px]# F p+ V j- J! D$ [[/size]
某系统的进程状态图如下所示：[size=0px]3 |0 h4 z; _2 ^[/size]
7 J0 W2 ^* B5 g' p
& Y9 [5 F* P6 y' S[size=0px]: t7 f" G( @3 }+ H7 a& c' R: x[/size]
图1 进程状态图
6 f- S L) d% v. P: C0 L
" E& u; I/ p+ _7 o, P+ s① 说明一个进程发生变迁3、4、6的原因；
* f/ ?+ F# f- E4 r8 F$ _ j) U" C* J[size=0px]7 O% M3 f2 N, D, L4 X- H[/size]
② 下述因果变迁是否会发生？若会，在什么情况下发生？
3 S; V2 s' V4 r4 X6 \2 C# V[size=0px]6 U. K, v% a+ j2 ^) L[/size]
(a) 3®5; (b) 6®4; (c) 6®7;
1 j/ S: B7 B0 u( y[size=0px]) U7 Q0 m2 Y; [[/size]
③ 根据此进程状态图，说明该系统的 CPU调度策略和调度效果。
% s6 U' m `, W+ I7 L4 A
3 ^0 n" _5 s2 v0 _7. (9分)[size=0px]/ ]- x4 h$ r7 N, }' H- _3 I[/size]
[size=0px]$ p( ~$ s2 \. U' u[/size]
某一系统采用请求分页式虚存管理，页面淘汰[wiki]算法[/wiki]为LRU(最近最少使用)法。每个作业[size=0px]3 B6 B! T( ]5 U" q/ R0 j, d: U[/size]
占15页主存，其中一页用来存放程序，每一页存放200个整型变量。考虑下列程序：
$ m% Y/ e$ @2 S& t; C[size=0px]# p8 h2 o- K% k1 C/ j' W- D/ j[/size]
var A,B:array[1..20,1..100] of integer;
7 d( B) L% `$ F1 \$ S[size=0px]3 s$ S9 p0 C% B. C) o7 X[/size]
i,j:integer;
, L5 ^4 M: h4 C. E! [& p! ~" k( [
/ I, U, z0 M- a0 vbegin
$ r: s2 _ r1 E- E$ ^! J' l
$ P7 D% l5 z" w) k! U9 lfor i:=1 to 20 do
1 ?) M) N) @& x5 n7 E[size=0px]* X {' g( L2 K5 z8 v[/size]
for j:=1 to 100 do [size=0px]! `0 I4 m3 m1 ?2 E[/size]
( w' o2 S7 F0 e! b4 R7 [A[i,j]:=0;[size=0px]! N9 K& h% e/ P' T+ n3 R- b' ][/size]
/ Y: p- j# i3 G. v0 o4 Ofor i:=1 to 20 do
8 L0 e7 C* i0 m n4 w
# }- ~8 _5 Z- Z& w1 U3 O' o: Afor j:=1 to 100 do
5 P. R1 S6 ?5 ~( P4 }
9 M2 _7 V3 {8 C% cB[i,j]=A[i,j];[size=0px]: T+ [+ G* v4 w# O; E6 X[/size]
* _+ u4 h, ]6 O9 M" fend;
0 z: ?( i) }! A3 @/ q3 e$ Z
3 |# v# m c- E设数组A,B均按行存储，程序页已调入主存，变量i,j存放在程序页中。问此程序会产
: \4 x" s2 |2 h+ }3 F3 ^生多少次缺页中断？运行结束后，留在内存中有哪些页？
武汉大学1998年研究生入学考试 编译原理试题（共60分）[size=0px]5 d4 x/ J6 R5 }) \2 Z3 q7 `[/size]
$ d6 @) j" ]1 l% Z1 k 以下内容需要回复才能看到
1. (10分)
}2 x% {( R! L8 m% I5 V. V[size=0px]2 L& A3 q% b* _% q0 O+ o[/size]
简述“循环中数组元素地址计算的优化”的主要思想，并举例说明。
5 ^% y. y/ g9 E2 s[size=0px]1 \/ [; ~1 k( D1 }+ N1 h* E[/size]
2. (8分)[size=0px]$ A9 q2 s' k1 U( b: n[/size]
[size=0px]/ y$ z% Z( n n8 D! O1 f+ n7 N- q[/size]
通常称赋值语句、条件语句和转移语句为基本语句，试先给出翻译基本语句的处理流
+ O* q% `& N0 A# w" y* D程，再给出翻译复合和循环语句的处理流程。
' P: F+ v# ?" Z; N/ O/ L3 j[size=0px]1 \/ k; X0 `* `. z. g$ |2 |* o: S[/size]
3. (12分)[size=0px]9 f9 J7 F: C& j$ T1 q. Y; m[/size]
[size=0px]+ v' ]( {# o& M8 ^1 t. f[/size]
参数传递有换名(call by name)、传值(call by value)、传地址(call by referenc
+ w7 c9 d: l: N/ \: Q; h! ?e)和传结果(call by result)等方式，试叙编译程序处理“传值”和“传地址”方式时的
% F' _9 V6 X, j+ X6 {5 J/ S; B要点，并指明处理“换名”与“传地址”，以及“传值”与“传结果”方式之间的主要差[size=0px] h& a. L6 U- C, X[/size]
别。
/ P8 X$ R( W7 v, A
`5 S1 M/ \1 _$ L: Y) f8 i4. (8分)
! Z4 q- ?! [/ t7 ]" B* N' D( d" r( }
8 S; V( }- d8 O& Y, l回答下列问题
" J. z+ T, |/ S, H; T
0 ~# a+ t8 W( F. D5 I2 D① 什么叫抢占式处理机调度和非抢占式处理机调度？先来先服务法(FCFS)、短作业优[size=0px]# e# K" ^) h3 V$ T4 r* q P! [[/size]
先法(SJF)、轮转法(RR)和优先法(HPF)各属于哪种调度？
7 n) S# ~0 K' t+ c" s( t) \. a[size=0px]7 g3 L+ l( b% E; p: I! q t[/size]
② 什么叫碎片？内碎片和外碎片的区别是什么？
9 y5 p/ I& o2 L* g3 _[size=0px]8 _# Z& v$ X1 x/ ~- C[/size]
5. (10分)
9 V: w# o; V& e0 f[size=0px]( ` g8 \' e. f3 X! B7 {: D$ ?[/size]
设某移动头磁盘有200道，编号为0~199，磁头当前正处在130道上，且正向0磁道方向[size=0px]5 P- w4 {' b/ `% ^- M+ s[/size]
移动，对于如下访盘请求序列(磁道号)：[size=0px]1 h8 ~2 |- \# }6 l9 C1 U7 X[/size]
2 D' W, h6 o. L/ X1 E70, 120, 80, 160, 60, 150
6 B5 u/ s. g$ |5 l$ V
2 C, L4 q% D- y: z) {# }求在FCFS、SSTF (最短寻道时间优先)及SCAN调度算法下的磁头移动顺序及移动总量(
0 @/ L* A, d- L8 }% B以磁道数计)。[size=0px]9 J: ~6 T: O, D3 D9 K& x4 k: I# Z4 S[/size]
2 n9 \$ |" ]) _% C$ s+ X* I/ K6. (12分)
. c z9 G+ s, ?, u[size=0px]! v9 ~; m T+ G+ M0 q[/size]
设有八个进程M1, M2, ..., M8, 它们有如下图所示的优先关系，试用P、V操作实现这[size=0px]; S+ n9 J+ q3 b5 ~4 B* K[/size]
些进程间的同步。[size=0px]) g$ v8 g% V' B[/size]
[size=0px]5 c: D! O! _" V2 @0 l[/size]
6 @: c% Y+ z' }5 A% @# E8 ?! U[size=0px]9 Q) S, t5 s' g7 f7 I2 M[/size]
图2 进程同步互斥图
武汉大学1999年研究生入学考试 编译原理试题（共60分）[size=0px]0 R+ u2 ]$ k. q: b2 h4 c& `[/size]
[size=0px]! {6 s& X6 X" ^( u[/size]
以下内容需要回复才能看到
1. (5分)[size=0px]2 f- |; w7 P9 K: j! E[/size]
) F: ~ w; i7 P% M计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？[size=0px]" g2 r" t) {& l# ]" L9 s& J[/size]
. m# P, p9 p. I! Z6 _2. (7分)[size=0px]8 F$ H+ m3 F: N+ g! |' w[/size]
[size=0px]9 z' k2 F5 M6 [5 @ |[/size]
Chomsky将文法分成四类。指明这四类文法与自动机的对应关系。指出右线性文法、左[size=0px]3 v, ?) V: c, E, _9 }( I: W[/size]
线性文法、正规文法之间的主要区别。
# {8 i, T* b! K3 R: z$ s: T' I- ][size=0px]7 l( H+ ^9 z- V S) T9 }3 p% c/ q[/size]
3. (8分)[size=0px]# y& m; C* e" v, K* g% a: A[/size]
[size=0px]! d, z! X( R, |2 Y: \0 O0 L[/size]
何谓“语法制导翻译(SDTS)”?试给出用SDTS生成中间代码的要点，并用一简例予以说
) Y. a7 b; y4 ?6 Q. t9 V" @6 q明。[size=0px]" V% o9 P" J. E8 i$ z/ n[/size]
[size=0px]& K2 f& c. j' y) s[/size]
4. (10分)
' y) X. `4 X5 ?[size=0px]/ u5 a1 S7 P! x4 O; \' ^[/size]
设有L(G)={a2n+1b2ma2p+1| n≥0,p≥0,m≥1}。
8 F' c0 t% \# W% Y4 }( c
2 w A) R* N+ H6 p2 E! s( o① 给出描述该语言的正规表达式；
( R1 Z) W z; u' g9 E P4 z3 Q# [[size=0px]3 _, W, g: r. o[/size]
② 构造识别该语言的确定的有穷自动机(可直接用状态图形式给出)。[size=0px]& v& D3 c8 B9 F[/size]
[size=0px]7 o( Z& y; ~7 U5 Y' G; Y[/size]
5. (10分)[size=0px]2 B; O7 m4 V2 A[/size]
8 T2 d, _& S3 v/ {, J8 ?2 k区别下列概念：[size=0px]) ~6 C: x9 {, V* W5 r9 b: ^[/size]
[size=0px] B) f0 p' l; U& `! R[/size]
① 原语与特权指令；[size=0px]5 [: _7 _8 g- D* D[/size]
3 a, z% K1 G) T② 顺序进程与并发进程；[size=0px]7 [5 r/ c, E& W' j+ ], i6 W8 v! @2 Q[/size]
- u5 K; q6 U- r2 e! m# }5 `7 K- J③ 死锁与饥饿；
6 u3 }7 j. i! N$ |9 F3 I
$ y, ?( N, U- V A/ h1 i" [ i④ 多用户OS与多道程序设计；[size=0px]1 R! L3 t/ h1 P6 e4 {3 t[/size]
[size=0px]) { F6 R( d6 m5 n' W[/size]
⑤ 存贮设备与存贮介质。
/ h) N5 V8 `3 u[size=0px]5 { Q) X3 s) @7 w[/size]
6. (5分)[size=0px]' r' ?. p& K! z5 q1 C; w2 r[/size]
[size=0px]$ V8 b1 k9 F. |. t[/size]
从宏观结构上看，OS有哪几种结构设计方法？你认为哪种方法较好？为什么？
1999硕士入学离散[wiki]数学[/wiki]试题[size=0px]2 n. |, B9 Z' b/ N7 g( n5 @, Z[/size]
以下内容需要回复才能看到
1 (6分)
) X0 ?! |9 o/ Q/ F0 W% N% V[size=0px]% N& s3 x7 T2 u[/size]
设A={a,b,c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性(要求画出R的关系图)。[size=0px]" G: j/ r# T4 _9 F! {[/size]
! H3 s) W$ ^7 N+ F) s4 i 2 (14分，每小题7分)
, Z- L8 `8 S% a U[size=0px]4 v' V) I6 I+ x+ |[/size]
① 证明：$x(P(x)→Q(x))«("xP(x)→$xQ(x))是永真式。[size=0px]6 l9 S. e1 } R6 m0 q[/size]
[size=0px]$ N- G* M# ^) F6 M0 O h& G[/size]
② 构造解释I使得"x(P(x)→Q(x))«($xP(x)→"xQ(x))在其解释I下的真值为假(假设I的论域DI={a,b})。[size=0px]5 g9 r/ x3 B. _$ R" Z8 z[/size]
[size=0px]2 P! M, c, g5 a[/size]
3 (10分)
: S' J4 M b0 e1 O: Q
) b4 F. z5 V+ B2 H: Y 设A、B、C、D是任意集合，f是A到B的双射，g是C到D的双射，[size=0px]$ Z. {3 `2 j0 Z- L2 j+ l[/size]
[size=0px]* R+ b) d- M1 r5 A& S$ N[/size]
令h：A´C→B´D且"ÎA´C，h()=。那么h是双射吗？并证明你的判断。
* Z& T* z) T6 w: v' w. z[size=0px]+ Q; @. {- g5 R[/size]
4 (10分)
( T2 U* V% K( I6 o5 ]
4 Y/ x1 k7 j# t) J! q2 k 设f是群到的满同态映射，是的正规子群，
# U; j% d1 W- ^" z[size=0px]; @: v% u1 M' a[/size]
H={x|xÎGÙf(x)ÎH'}。[size=0px]* ~( q* F4 R: ?, \' K: l0 t+ G[/size]
[size=0px]; b6 R" u4 _+ l9 q0 c- w: D$ T4 R[/size]
令f：G®G'/H'，"gÎG,f(g)=f(g)H'。[size=0px]) ]3 w, K" Q0 h[/size]
, [* V; @4 a: `. [ 证明：是的正规子群，且f是满同态。
武 汉 大 学
! p. O1 F6 i) e# Z G, D2001年攻读硕士学位研究生入学考试试题[size=0px]# R8 F9 g) e( c* O$ B[/size]
考试科目：程序设计（含pascal或c语言：小、数据结构） 科目代号：462[size=0px]7 ^6 A: y* ~; x0 Z/ L# K[/size]
一单项选择填空（每小题1分，共10分）[size=0px]3 F* n8 y( d, Q. C' K[/size]
1． 下面关于数据结构的叙述中，正确的是_______.[size=0px]$ M! @. E" A* v* F: V* \% l2 Q2 N1 o" ~% v# m[/size]
A数组是同类形值的集合。[size=0px]8 Q# p9 ]0 O& K: J! }8 m" L[/size]
B递归算法的程序结构比选代算法的程序结构更为精练。
# f2 z3 N5 |6 S. ZC广义表是一种线形结构。 [size=0px], _: [ N+ b3 G( Z6 `: U" Q[/size]
D用一维数组存储二叉树，总是以先（前）序遍历顺序存储的各结点。
V& ]6 i+ C ]; t- X# {2． 设去序列中的第一关键字作为划分快速排序子文件的基准，下面的序列用快速排序，其速度最快的是________.[size=0px]# p+ V3 S. V4 S; ^7 p- E k1 i[/size]
A．{10，20，30，40，50，60，70}[size=0px]2 `/ e t/ Q* [# A[/size]
B．{30，40，70，60，10，50，10}[size=0px]2 m$ @8 J. L/ z# n8 t0 ?[/size]
C．{40，50，30，70，10，20，60}[size=0px]' E- w5 w8 ^+ Q/ O! m8 s[/size]
D．{40，70，50，60，30，10，20}
3 _$ ]$ y. |. E" Z8 e# l E4 }3． 设矩阵A是对称矩阵，为了节省存储空间，将其下三角部分按行为主序存放在一维数组B[1..n(n+1)/2]中，对任意一下三角元素aij(i>=j),在一维数组B的下标位置K的值是_______.
7 v3 ]) Z% z8 j+ N1 TA i(i-1)/2+j-2 B i(i+1)/2+j-1[size=0px]$ [, M9 V* V% T, P, ]' b8 o) q- e[/size]
C i(i-1)/2+j D i(i+1)/2+j
$ D2 i/ ?" m) t0 T. t4 B树和B+树______.[size=0px]; {3 g% v$ B1 a. o[/size]
A 都能有效地支持顺序检索。
' ~: e5 X$ |- Q5 y, f3 O4 [0 _9 w6 oB 都不是平衡的多分树。[size=0px]9 E3 E: W: r) ^1 e. G* k[/size]
C 都不能用文件的索引结构。
0 y5 b v! {" }+ f2 Y6 yD 都能有效地支持随机索引。[size=0px]+ c8 ^ F! s3 k5 ~* D" i! H[/size]
5 设二叉树根结点为O层，深度（高度）为K的满二叉树和同样深度的完全二叉树各有n个结点和m个结点，下面关系不正确的是______[size=0px]% L* \- l& T- ^$ E[/size]
A．n>=m B. m>n C. n=2k+1-1 D. m>2k-1
2 Z/ I; S& T$ B9 ]6 设树中有一结点x，在先根遍历序列中的序号为P(X)，后根遍历序列中的序号为S(X)。若树中结点x是结点y的祖先，则有_______[size=0px], Q5 |- N6 z' J, ^5 ^[/size]
A p(x)>p(y)和s(x)
! c# i) e& y1 gC p(x)
A 5 B 4 C 3 D 2[size=0px]2 R$ y8 v$ P( m* P. u# t$ k[/size]
8 指针类型不可以作为________.
* @+ i- E* d2 u% p+ r0 jA数组的基类型 B集合的基类型 [size=0px]! E6 [) Z+ k+ H: m0 [0 }[/size]
C函数的类型 D 形式参数的类型
( i$ c4 B' n* ?' K9 ________不是算法的基本特征。
0 k# f: j) p9 u; SA正确性 B长度有限[size=0px]2 t; S$ i1 v' C) }& f[/size]
C 在规定的时间内完成 D 确是性[size=0px]4 i5 s1 S8 ^# W, c- d[/size]
10 动态数据类型是指_________.
5 B; e* r1 C, ]" e1 kA数据的存储大小可变。[size=0px]9 P" X) t. G9 q* K D9 z' h2 ?[/size]
B指针类型。
3 e% b2 Z! I7 MC数据的值可变。
3 z# j" t) `% dD数据的变量名称可变。
2 K6 C* i" j+ ^4 n m二填空（没小题1分，共六分）
4 @/ H/ T( Z6 ^1 b4 x3 I. C1对于具有144个记录的文件，若采用分块查找，且每块长度味，则平均查找长度为__________.
. w) _2 n1 F* ? I' Q6 L2当线形表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存储线形表中的元素时，应采用________存储结构。
3 v1 L4 }1 w' q8 v9 [5 T( E3、设森林Ｆ由n棵树组成，其中第一棵树有t１个结点、．．．第n棵树有tn个结点，则与Ｆ对应的二叉树中，根结点的右子树共有＿＿＿个结点．[size=0px]0 A4 X) I3 P+ k[/size]
４、字符串’abcd’中共有＿＿＿＿个长度大于０的子串．
$ k5 E- J( E8 \& `, B6 G5 ^５、设栈Ｓ和队列Ｑ初始均为空，若６个元素入栈的顺序为a1,a2,a3,a4,a5,a6。一个元素出栈之后立即入队列Ｑ，若第６个元素出队的顺序为a2,a4,a3,a6,a5,a1,则栈的容量至少为————。
+ G) y& F$ z7 P d6、设无向连通图G的顶点数与边数和一立方体相同，即有8个顶点和12条边。任意一棵G的生成树共有————条边。
, O( c2 s! H+ g6 h9 a; a; b三、简答证明题[size=0px]/ Q: T3 @; h d d% ^& S[/size]
１、 设有一个带权的连通网络中共有100个顶点，现仅需求出编号为v1,v2,…v10的顶点到其余各顶点的最短路径。请问采用何种求最短路径的算法较为合适？并说明理由。[size=0px]4 n& A0 j. t! X8 Y9 A[/size]
２、 利用两个栈S1和S2模拟一个队列时，如何用栈的运算实现入队和出队的运算，以及判队列空的运算？（不要求写算法）[size=0px]5 S$ v3 Z% K8 v) D, D" m3 W' L[/size]
３、 证明：为合并两个含有n个元素的已排序表，在最坏情况下，２n-1次比较是必不可少的。[size=0px]; B( G3 R4 ]1 |5 Y8 F8 W[/size]
４、 证明：二叉排序树中结点Ｕ是Ｖ的祖先，当且仅当在前（先）序序列中Ｕ在Ｖ之前，且在后序序列中Ｕ在Ｖ之后。[size=0px]+ a% d8 ^/ e" I" Y9 m( D- Q) M; @[/size]
四、已知一组关键字为（26,36,41,38,44,15,68,12,06,51,25）用线性探查法解决冲突，设装填因子α＝０.75。
' J; n6 z8 G2 m" m' o１、 用除留余数法构造这组关键字的散列表。[size=0px]+ t: D* [/ C0 z1 [2 C4 @3 ^ J# M[/size]
２、 求平均查找长度。[size=0px]7 `8 e" F5 ]3 ]/ }[/size]
五、回答下面问题[size=0px]' g9 A P7 O. U# `! o- [% n* `[/size]
１、有一正文件test.txt存储了若干行[wiki]信息[/wiki]，每行信息包含职工号（8位），姓名（8位），工资（4位），在程序中用一个单链表表示这些信息，请定义这个单链表，并说明如何从test.txt中生成这个链表（不要求写算法）。
, F; `! \4 ]- G3 L4 B２、有人用程序对上题中全部员工的工资求总和，但程序产生的结果为298。而这个结果显然是错的，因为每个职工的工资都大于320。经检查可以肯定：（1）、数据文件正确无误；（2）、构成链表后的结点数据准确无误；（3）、程序逻辑正确；请分析一下这种现象，给出合理的解释。[size=0px]/ N+ E" T, B" s( O# \4 J7 m9 s7 ^[/size]
六、算法设计[size=0px]7 J3 m* U5 g$ \4 C+ [/ K[/size]
１、 试写出一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结构，且树中的结点关键字均不同。[size=0px]5 [1 o% q! p e$ d9 @& e, }1 O[/size]
２、 设有向图用邻接矩阵adj表示，每个顶点的入度用数组nodein存储，已知adj和nodein存储，已知adj和nodein。请写出对该图进行拓扑排序的算法。[size=0px]' U; S( O1 i- [[/size]
七、程序设计题
* S- G8 x: Q' U5 Q6 x' K１、 任给出一个正整数n，输出0,1,…,n-1的所有排列。例如：给定n＝３，则输出：[size=0px]9 ^' b( F/ x' J[/size]
0,1,2 ; 0,2,1 ; 1,0,2 ; 1,2,0 ; 2,0,1, ; 2,1,0.[size=0px]1 X$ W$ G- Z: P* X[/size]
2、如果一个数列中的任意一段（至少是两个元素）各个元素都相同，则称为等值数列段，等值数列段中的元素的个数叫做数列段长度。现有由n个元素组成的整数数列Ａ，求Ａ中长度最大的所有等值数列段的首末位置，如果没有等值数列段，则输出特殊标志。
武汉大学1999年数据结构试题!
) j# C; U- q$ F, a
* ^3 D) j! y: o% @5 [$ Z武汉大学一九九年攻读硕士学位硕士生入学考试试题 编号：02A
! e) ]- P% t5 \' q; v- X4 o一．前空（每小题2分，共16分）[size=0px]4 `: I) g0 c+ D! i7 n[/size]
1． 将中缀表达式转换成等价的后缀表达式，需要使用________这种数据结构存放表达式中的开括号和暂时不能确定计算次数的运算符。[size=0px]& {: x: |3 o9 a[/size]
2． 广义表L=（（），（））的长度为___________。[size=0px]0 f" c- \& d! O' R8 b[/size]
3． 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶子结点，B中右指针域为空的结点有_______个。[size=0px], `, o8 N I p2 B[/size]
4． 据有n个结点的无向图的生成树，有_______条边。[size=0px]0 c4 x# x* i' t$ I5 Q[/size]
5． 一棵m阶的B-树，若在某结点中插入一个关键字而引起结点分裂，则此结点中原有______个关键字。
* g3 P8 w3 D7 O3 n6． 设数据结构(D,R)由数据结点集合D={di|1≤1≤8}即其上的关系R{
& a( c. t- _3 ~3 _% ^这个数据结构对应于___________。[size=0px]0 Q0 I1 d; X6 T4 ~[/size]
7． 直接存取文件是采用_______组织起来的的文件。
' B, e3 O3 _1 C0 o8． 在外部排序中，可以使用________________产生初始归并段。
$ @) Z2 `1 f. w3 `0 D; ^" E- k( }二．选择前空（只选一个答案，每小题2分，共16分）。
7 \8 b2 t% ^' j3 Y+ T0 E2 s/ ~1． 在程序设计语言中，过程一般函数和子程序，他们都不能通过对__________的赋值来返回值。
! Q% l Q4 @- d- ~/ |9 ^A 值参数B变量参数C实在参数D形式参数[size=0px]- ^+ s9 Q- i0 D- P+ Y, B[/size]
2． 在通常的程序设计中，应将程序的__________作为首要考虑的问题。[size=0px]0 m4 |; ^( d: h4 ]' G C- P j[/size]
A执行效率B占用空间C长度D结构
7 I% H$ _( j6 P2 R3． 局部变量的[wiki]作用[/wiki]范围为_________________。
, H% X7 I2 [; ^7 l: e. x, wA定义点开始至本层程序结束为止B定义点开始至程序尾C定义点开始至上层程序结束[size=0px]6 e: b* ?6 N1 p4 ~+ ^) a# V[/size]
D视具体程序才能确定[size=0px]& F& G2 M8 P" g b3 `# L[/size]
4． 下面的程序段[size=0px]" }: y! i0 {* E: T3 U* N/ W3 `4 g- H& s[/size]
for i:=1 to n do[size=0px]/ D0 @+ f4 ?' V+ }9 M" I[/size]
for j:=1 to i do
+ v& I/ b4 i9 Y+ [3 C for k:=1 to j do[size=0px]+ ]+ B6 }* b9 L, x( r3 R[/size]
x:=x+1; [size=0px]8 Q+ z1 @, p, _7 K F4 c[/size]
的时间复杂度为__________________。[size=0px], V: i7 ]) ?5 j$ k U+ A @[/size]
A O(n) B O(n3|2) C O(n2) D O(n3)
: y. f$ y2 `0 ]1 G. f. X5． 设单链表中指针P指着结点A之后的结点（若存在），则修改指针的操作为_____________。[size=0px]/ K2 i5 ~- m3 A z[/size]
A p^.link:=(p^.link)^.link B p:=p^.link
/ O( e7 E, l$ ^; aCp:= (p^.link)^.link D p^.link:=p
- b* [3 O+ A- P/ |2 j6． 最佳二叉排序数的结构特点是______________。[size=0px]7 \3 J q7 X3 ^ q' Y3 m[/size]
A除最下两层可以不满外，其余都是满的
5 P* N5 T9 x- j% WB除最下一层可以不满外，其余都是满的
& \4 Y( Y b% QC每个结点的左右子树的高度之差的绝对值不大于1[size=0px]- L2 W" \ m6 ~3 j5 S( b' O, ?# Z[/size]
D最下层的叶子结点必须在最左边
4 z$ f2 m7 V2 u7 D7． 堆排序的时间复杂度和需附加的存储空间分别是_______________。
/ t, @5 A# h* s% `5 H A+ }; j; \A O(n2) 和O(1) B O(nlog2n)和O(1)
4 |. e4 f5 }6 l' j$ {C O(nlog2n)和O(n) D O(n2)和O(n)
; {7 s) @7 R! b0 `% q% n 8．设二叉排序树中的关键字由100至1000的整数构成，现要查找关键字为360的结点，下述关键字序列_____不可能是二叉排序树上搜索到的序列。
+ s( N0 c7 T, D+ E- |A. 200, 252, 401, 398, 330, 344, 397, 360[size=0px]7 _6 J% n- z# {% |# p5 u( x+ |[/size]
B. 920, 220, 900, 250, 890, 260, 300, 360[size=0px]! _. d' x3 P% T) c& O6 n[/size]
C. 450, 400, 220, 370, 385, 390, 386, 360[size=0px]5 d! I* b" f) ^! {7 ^0 ^/ l[/size]
D. 150, 400, 380, 230, 270, 370, 365, 360[size=0px]2 l4 a( d$ }3 N1 p) N: ]* L[/size]
三．回答或证明下列问题（24分）[size=0px]. e2 F" P6 O/ R [8 m, z[/size]
1．（8分）用相邻矩阵表示有相图，其主对角线以下的元素均为零。
+ S- W U! {) C# O（1） 试问此图是否存在回路？（2分）
+ W! `7 l8 ^0 q ]! A" o（2） 证明你的结论．（６分）[size=0px]+ i6 d5 ^( b$ D[/size]
２（８分）在１６位字长的操作系统中，有人编写了一段pascal程序，如下所示：
- U2 C. o$ j9 I' v% P．．．[size=0px]+ u2 S! {4 H( ]5 l[/size]
i:=2;[size=0px]% C# k( u- X! n7 Y& z/ T9 d* W/ L[/size]
Repeat
4 i2 X+ u+ J' S( H$ H/ s/ ~X:=sqrt(x)+1;
; z7 Q2 a4 b ~3 s9 E$ B0 Oi:=i +1[size=0px]8 _5 F8 |8 ]/ l* [! t6 t0 u H* W[/size]
until (x<=1) and(I<2)
/ Y1 I9 l2 U3 N…
# e, x+ a y- @6 N& o9 s其中，i 为integer类型;x为 real类型;sqrt为 平方根函数.如果程序循环执行两遍后,程序继续运行下去能否正常终止?[size=0px] M" ?% n0 ^! U[/size]
3.(8分)试举例说明,对于同一种数据结构的同一种运算(操作),因存储结构的不同,其算法的时间复杂度有时也不一样.
8 N6 k( v8 g" ~8 t四.(10分)设数组A[1..2n]中存放有n个负数和n 个[wiki]正数[/wiki],且随机存放.现要求按负数正数相间存放.请写出实现此要求的算法.算法要求:不能使用额外的存储空间,但可使用少量工作单元,算法的时间复杂度应为O(n).
1 w& e; X+ Y3 P( N, S4 C五.(10分)写出在对称穿线(中序线索)树里找指定结点在后序下的前驱的算法
8 Q2 q* O/ Q6 i六.(12分)图的存储结构常采用相邻矩阵或邻接表表示法,在求解不同的有关图的问题的算法设计时,往往需要根据情况而使用不同的结构.试写出将相邻矩阵转换成相应的邻接表结构的算法.
& _3 l; A" S7 n. {七.(12分)在一维字符树组A中存储了一棵高度为d的二叉树,其结点个数为n=2d-1,存储方式是按中序逐个结点(字符类型)值存入树组A.请写出算法将该二叉树的前序遍历结果存储在数组B中.
[[i] 本帖最后由 牛哥 于 2008-1-25 02:05 PM 编辑 [/i]]
达到
赌东道的怎么下载啊
在哪下载啊 gfhfghgfhfghfgh来啦
亏损的后方空降师地方 看看！ sdsdsdsds ？？？ 看看hao
haokan
see yun ding yig e ok henhao 谢谢 谢谢回复 楼主 的帖子
谢谢 先谢了真好
楼主辛苦了！~~ wo kan kan 只有3个能下，不过先谢谢拉 dddd 顶一下，看看，谢谢 xieixiehao
hao nan a??
怎么下载啊 谢谢，楼主 都有什么 呵呵ding
顶顶顶顶 xiexie回复
谢谢！回得
谢谢啦！ 谢喽！ :) 顶一下 只有3个能下，不过先谢谢拉 zan:lol 先看一下 谢谢楼主了 好东西啊。想看哦！ dingding ding ding ding xiexiele姐姐
风光好回复 楼主 baiduwen3 的帖子
:victory: 哎哎哎~~~~~~`多少分个人
我二个月的师傅 顶dddddddddd
ddddddddddddddddddddd 顶回复 楼主 baiduwen3 的帖子
顶呀好 先看看~~ hao回复 30楼 wang441700 的帖子
好东西，谢谢楼主！！！:) 要认真看看哦 顶顶顶顶查看详情:[url]http://bbs.vipkaoyan.com/thread-3146-1-1.html[/url]