下载文档原格式
一、单选题（每题 2 分，共20分）1. 1.对一个算法的评价，不包括如下（B ）方面的内容。
A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。
A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV网是一种（）。
A．有向图B．无向图C．无向无环图D．有向无环图6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。
A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。
A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。
A．行号B．列号C．元素值D．非零元素个数9.9.快速排序在最坏情况下的时间复杂度为（）。
A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A. O(n)B. O(1)C. O(log2n)D. O(n2)二、二、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______________。
当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。
东南大学历年编译原理考研试卷试题编号:553试题名称:编译原理一:(15分)判断下列命题的真假,并简述理由:1.文法G的一个句子对应于多个推导,则G是二义的.2.LL(1)分析必须对原有文法提取左因子和消除左递归.3.算符优先分析法采用"移近-归约"技术,其归约过程是规范的.4.文法S→aA;A→Ab;A→b是LR(0)文法(S为文法的开始符号).5.一个BASIC解释程序和编译程序的不同在于,解释程序由语法制导翻译成目标代码并立即执行之,而编译程序需产生中间代码及优化.二:(15分)设计一个最小状态有穷自动机,识别由下列子串组成的任意字符串.GO,GOTO,TOO,ON例如:GOTOONGOTOOGOON是合法字符串.三:(15分)构造一个LL(1)文法G,识别语言L:L={ω|ω为{0,1}上不包括两个相邻的1的非空串}并证明你的结论.四:(20分)设有一台单累加器计算机,并汇编语言含有通常的汇编指令LOAD,STORE,ADD和MUL.1.写一个递归下降分析程序,将如下文法所定义的赋值语句翻译成汇编语言:A→i:=EE→E+E|E*E|(E)|i2.利用加,乘法满足交换率这一性质,改进你的分析程序,以期产生比较高效的目标代码.五:(15分)C为大家熟知的程序语言.1.C的参数传递采用传值的方式,而且允许函数定义和调用时的参数个数不一致(如printf).请指出其函数调用语句:f(arg1,arg2,...,argn)翻译成的中间代码序列,并简述其含义.2.C语言中的变量具有不同的作用范围,试述C应采用的存储分配策略.六:(20分)设有一个子程序的四元式序列为:(1) I:=1(2) if I>20 GOTO (16)(3) T1:=2*J(4) T2:=20*I(5) T3:=T1+T2(6) T4:=addr(A)-22(7) T5:=2*I(8) T6:=T5*20(9) T7:=2*J(10) T8:=T6+T7(11) T9:=addr(A)-22(12) T10:=T9[T8](13) T4[T3]:=T10+J(14) I:=I+1(15) goto (2)(16) ret1.分划基本块.2.对代码施行各种可能的优化,并写出优化过程中采用了何种优化策略.试题编号:553试题名称:编译原理一:由文法G1构造LR(1)部分分析表:1.列出4个项目集I0,I1,I2,I3;(如下图)2.填写LR(1)分析表的状态0,1,2的action和goto表的内容.(如下图) G1: (0) S→T(1) T→T(T)(2) T→ε┌──────┐┌──┐┌──┐┌──┐│I0:S→·T,# │ T │I1: │ ( │I2: │ T │I3: ││ │ -→│ │-→ │ │-→ │ │└──────┘└──┘└──┘└──┘┌──┬────────┬───┐││action │ goto ││状态├──┬──┬──┼───┤││ (│ ) │ #│T │├──┼──┼──┼──┼───┤│ 0│││││├──┼──┼──┼──┼───┤│ 1│││││├──┼──┼──┼──┼───┤│ 2│││││├──┼──┴──┴──┼───┤│││││... │ ...│ ...│││││└──┴────────┴───┘二:已知文法G2,请用类pascal语言写出它的递归下降分析程序.G2: A→[BB→X]|BAX→Xa|Xb|a|b三:已知文法G3,要求:1.写出各非终极符的首终极符集合和尾终极符集合;2.填写opt表:│+ │* │@ │ ↑ │i │# │──┼──┼──┼──┼──┼──┼──┤+ │││││││──┼──┼──┼──┼──┼──┼──┤* │││││││──┼──┼──┼──┼──┼──┼──┤@ │││││││──┼──┼──┼──┼──┼──┼──┤↑ │││││││──┼──┼──┼──┼──┼──┼──┤i │││││││──┼──┼──┼──┼──┼──┼──┤# │││││││──┼──┼──┼──┼──┼──┼──┤│││││││G3: E→E+T|T|@TT→T*F|FF→p↑F|Pp→i四:请写出产生下列语言的文法.1. L1={a^ib^j|i>j>=1}2. L2={ω1|ω1∈{0,1}*&ω1中包含0,1个数相等的任意串}3. L3={ω2|ω2∈{a,b}*&ω2中a之后必定跟b}4. L4={ω3+ω3|ω3∈{0,1}*}五:简要回答问题.1.对编译程序而言,模块,遍,子程序这三个概念的主要区别?2.静态存储分配与动态存储分配的主要区别?3.何谓自适应线性表?六:翻译如下布尔表达式成四元式序列,结果留待填的真假链的四元式序号. A∧B-C<D+E∨┐F试题编号:553试题名称:编译原理一:按算法构造文法G1:S→#M#M→(L|aL→M,a)的算符优先矩阵.(即填写下列矩阵)│ a │, │( │ ) │# │──┼──┼──┼──┼──┼──┼a ││││││──┼──┼──┼──┼──┼──┼, ││││││──┼──┼──┼──┼──┼──┼( ││││││──┼──┼──┼──┼──┼──┼) ││││││──┼──┼──┼──┼──┼──┼# ││││││──┼──┼──┼──┼──┼──┼二:将下列cfg文法修改成正规文法.S→ABA→M|N|PB→aB|aM→bM|bN→cN|cP→αP|ε三:已知文法G2:(1) S'→S(2) S→AAA(3) S→1A(4) S→01.列出LR(0)项目集族;2.构造SLR分析表;3.试给处语句01100#的LR分析过程.四:1.构造由下列三型文法G3所对应的FA.2.将构造的FA确定化和最小化.3.写出该DFA所识别的语言.G3: S→aA|bS|dCA→dEC→aD|bC|bD→bE|bE→aD|bE|b五:设有源语句A[I+1,J+2]:=A[B[K+2],5]1.列出计算两个数组的下标地址(按行存放)A[I+1,J+2]的地址D1=?B[K+2]的地址D2=?2.按语法制导翻译该语句成四元式序列.(设数组首地址分别为a,b;数组按行存放,每个元素占一字编址.数组说明:A:array[1..10,-5..5],B:array[-5..5])六:求文法G4:A→BCc|gDBB→bcDE|εC→Dab|caD→dD|εE→gAf|c的各非终结符的随符集.七:1.简述由基本块寻找循环结点的算法.2.对于如下一段程序,若参数传递分别采用:(a)传名(b)传结果(c)传地址试问程序执行结果,Y值是什么?proc Q(B,C)beginB:=B+2;B:=B*Cend;beginY:=2;Q(Y,2*Y);print(Y)end;3.文法G5:E→P↑E|PP→P*Q|QQ→Q+R|RR→(E)|aa→整常数试给出下列表达式计值结果(语法制导).3+2*5↑2*2+32+(2↑2↑3)*2+3试题编号:553试题名称:编译原理一:1.试写一正规文法,使其定义的语言是不以0打头的偶整数集合.其中数字可以用简名表示,比如α1→0|2|4|6|8,并把α1看作是终结符.2.试写一上下文无关文法,它能产生下列语言:L={ω|ω∈{a,b}*,且ω中a的个数是b的两倍,例如aab等}二:请写出由下列文法所确定的语言.1. G1: S→10S01S→aAA→bAA→a2. G2: S→aSSS→a三:已知NFA的状态转换图如下,试对它确定化并化简,并写出该FA接受的语言.∩b a→S──────→Ad│ │c↓ a b ↓b＜C──→D──→E＞b│b│←──│b│↓ a │b└─→T ←──┘四:已知文法G4:S'→SS→ASS→bA→SAA→a1.试求closure({(S'→·S,#)})和GO(closur e({(S'→·S,#)}),S)2.文法是LR(1)吗?为什么?五:试将下面语句按语法制导翻译成四元式序列.while (a<c) and (b<d) doif a=1 then c:=c+1else while a<=d do a:=a+2;六:1.试对如下四元式序列划分成基本块,并化出程序流图;2.写出源语句.(1) I:=1(2) if I>M goto (19)(3) J:=1(4) if J>N goto (17)(5) T1:=I*N(6) T2:=T1+J(7) T3:=addr(A)-C(8) T4:=I*2(9) T5:=J+2(10) T6:=T4*N(11) T7:=T6+T5(12) T8:=addr(A)-C(13) T9:=T8[T7](14) T3[T2]:=T9(15) J:=J+1(16) goto (4)(17) I:=I+1(18) goto (2)(19) ...七:1.求文法G7的各非终结符的终结首符集First和随符集Follow.2.判定该文法是LL(1)吗?G7: A→BCc|gDBB→bCDE|εC→DaB|caD→dD|εE→gAf|c试题编号:553试题名称:编译原理一:文法G1:E→ET+|TT→TF*|FF→FP↑|PP→E|i1.试证明符号串TET+*i↑是G1的一个句型(要求画出语法树).2.写出该句型的所有短语,简单短句和句柄.二:1.给出下图FA的正规式.a b──→ ──→ ②→◎①a↑↓ε←── ←── ③ε b2.已知正规文法G2:S→aS|AA→bBB→aB|ε试构造一确定有限自动机DFA(要求化简),使得它接受的语言正是该文法产生的语言,要求画出状态图.三:1.试写出一个上下文无关文法G3,它能产生配对的圆括号串(例如,(),(()),()(())等,甚至包含0对括号).2.使用文法G3给出输入串(())()#的自上而下分析过程.四:已知文法G4:S→aAb|Sc|εA→aAb|ε1.给出G4文法的LR(0)项目集规范族;2.构造SLR分析表;3.G4文法所定义的语言;4.已知有如下文法及相应的LR分析表,试给出语句01001#的LR分析过程(填写下表). S→AAAA→1AA→0LR分析表:───┬──┬──┬──┰──┬──状态│ 1│ 0│ #┃S│ A───┼──┼──┼──╂──┼──0 │ S3 │ S4 │ ┃1│ 2───┼──┼──┼──╂──┼──1 │││acc ┃│───┼──┼──┼──╂──┼──2 │ S3 │ S4 │┃│ 5───┼──┼──┼──╂──┼──3 │ S3 │ S4 │┃│ 6───┼──┼──┼──╂──┼──4 │ r3 │ r3 │ r3 ┃│───┼──┼──┼──╂──┼──5 │ S3 │ S4 │┃│ 7───┼──┼──┼──╂──┼──6 │ r2 │ r2 │ r2 ┃│───┼──┼──┼──╂──┼──7 │││ r1 ┃│───┴──┴──┴──┸──┴──分析过程:──────┬──────┬──────状态栈│符号栈│ 输入串──────┼──────┼──────││││││││││││││──────┴──────┴──────五:1.翻译下面语句成四元式中间代码序列和后缀式(逆波兰式);while x+y>a doif a<10 then a:=a+1 else x:=x-1;2.翻译布尔表达式(a>b) or (c=d) and not (e<f)成转移四元式序列(即四元式中仅包含(zθ,-,-,-)和(j,-,-,-)两类语句,其中θ为关系运算符.)六:1.有如下Fortran说明语句,试借助符号表登记等价环链EQ和相对数OFFSET,即填写下表的EQ栏和OFFSET栏.设每个整型量占1子编址.integer a,b,c(10,10),d(10)equivalence (a,d(8),c(5,5))equivalence (b,c(5,8))符号表┌───┬──────┬───┬───┐│ name │ ... │ EQ│OFFSET│├───┼──────┼───┼───┤1│ a │ ... │ │ │├───┼──────┼───┼───┤2│ b │ ... │ │ │├───┼──────┼───┼───┤3│ c │ ... │ │ │├───┼──────┼───┼───┤4│ d │ ... │ │ │└───┴──────┴───┴───┘2.有如下pascal语言的程序轮廓,当运行该程序且第一次递归调用Q过程(即在过程Q中又调用了Q)时,数据区建立情况.假定各数据区首址用SP(i)(i=0,1,……)表示,试给出P,Q数据区的display表.┌ main│┌ P││┌ Q│││ Call Q││└││ Call Q│└│┌ R││ Call P│└│┌ S││ Call R│└│ Call S└七:已知如下流图,试给出回边与循环.↓┌─→①←┐│/ \/│ ↓↓/\ ②③\ \ /↑\↓↓/┌→④──┐│ │ ↓│ │┌→⑤│ ↓/ │└─⑥←─┘试题编号:553试题名称:编译原理一:已知文法G1:S→aB|εB→bC|bDC→cB|cD→d1.试构造一个最小DFA,画出状态转换图.2.由该DFA给出它所识别的语言(用正规式表示).二:已知正规式α=ab*c*d,1.试构造一个DFAM,其接受的语言为此α(画出图);2.由该DFAM写出对应的正规文法(古线性).三:文法G3:S→A[B]A→[B]|AaB→a1.求出各非终结符N的Firstvt(N)和Lastvt(N),构造包括语句括号'#'在内的算符优先表;2.给出语句#[a][a]#的算符优先分析过程,即填写如下格式的表:步骤│ 栈内│ 输入串│ 动作────┼────┼────┼─────0 │# │[a][a]# │... │││四:已知文法G4:T→T*F|FF→(T)|i1.试给出语句(i*i)#的自上而下分析过程(填下表);2.画出对应的语法树,指出每一步归纳的句柄.步骤│ 栈内│ 输入│ 动作────┼────┼────┼─────0 │#T │ (i*i)# │... │││五:已知文法G5:0. E'→E1. E→E+T2. E→T3. T→i列出LR(0)项目集规范族,求出各非终结符N的Follow集合,构造SLR分析表.六:翻译如下语句成四元式序列(由语法制导生成).while a>b and a<d doif a=5 then b:=b+1 elserepeata:=a+1until a>=d;七:按语法制导翻译下段程序成四元式序列(不要优化),设数组A: array[1..10,1..10]of int;每个下标变量占1字编址,数组按行存放,Z为函数名.beginA[i,j]:=A[i,j]+2;B:=Z(A[i,j])*5end八:将如下一段四元式序列进行块内优化和循环优化(强度减弱及删除基本归纳变量),写出优化后的四元式序列.(要求先划分基本块)(1) i:=1(2) if i>100 goto (10)(3) T1:=20*i(4) M:=J+T1(5) T2:=20*i(6) N:=K+T2(7) O:=M+N(8) i:=i+1(9) goto (2)(10) ...九:已知如下一段程序,试给出运行时整个数据区结构.假定num初值为2,每个数据区的活动记录包含内容如下图所示,数据区从k单元开始编址.┌─────┐ program factoral;│函数返回值│ var num,fact:int;├─────┤ function f(n:int):int│ 变量单元│if n>0 then f:=n*f(n-1)├─────┤ else f:=1;│display 表│ begin├─────┤ read(num);│ 形参单元│ fact:=f(num)├─────┤ end│ 返回地址│├─────┤│基SP │└─────┘试题编号:553试题名称:编译原理一:已知正规文法中的左线性文法G1:S→Sa|Sb|c试构造无ε产生式的等价右线性文法,并构造相应的确定有限自动机DFA,画出状态转换图即可.二:已知正规文法(X为开始符号)G2: X→0Y|1Z|0Y→0X|1Y|1Z→1X1.该文法产生语言是什么?请用正规式表示.2.构造最简的确定有限自动机DFA,并画出状态转换图.三:已知上下文无关文法(E为开始符号)G3: E→ET+|TT→TF*|FF→E|i1.消除文法左递归,并给出改写后的文法产生式;2.给出文法改写以后的各非终结符X的First(X)与Follow(X)集合,并由此判定它是否是L L(1)文法(按下表填).V(N) │ First(X) │ Follow(X)────┼──────┼───────X ││...││││四:已知表达式文法(已拓广)G4: E'→EE→E+E|i1.试构造文法G4的LR(0)项目集规范族;2.若'+'服从右结合率,请给出LR分析表.五:已知文法(Z为开始符号)G5: Z→bMbM→(Ma)|a1.试构造算符优先分析表(即填下表);│ a │ b │( │ ) │# │──┼──┼──┼──┼──┼──┼a ││││││──┼──┼──┼──┼──┼──┼b ││││││──┼──┼──┼──┼──┼──┼( ││││││──┼──┼──┼──┼──┼──┼) ││││││──┼──┼──┼──┼──┼──┼# ││││││──┼──┼──┼──┼──┼──┼2.若某相邻的终结符a,b间存在a<=b两种关系,那么在进行算符优先分析做归约动作时,在寻找栈顶的素短语符号串时要察看它与哪个产生式右部的符号串匹配.例如栈顶串...aAbα(a,b∈VT,A∈(VA∪ε),a<=b,α∈V*)为已知可归约,而现有产生式X→aAbα,则取素短语aAbα,若只有产生式Y→Abα,那么就取Abα进行归约.试按此规定的算法给出语句b((aa)a)b的算符优先分析过程.六:翻译成中间代码.1.将如下程序段翻译成后缀式(逆波兰式),填在一维数组POST中,设i初值=1.t:=15;b:=20;while t<>b doif t>b then t:=t-belse b:=b-t;2.翻译布尔表达式成转移四元式序列,并指出待填真假链序号.(a>b+1) and not (c+2<d) or f(x)注:f(x)为布尔函数.七:有如下一个计算m*2^n的C语言程序,试给出运行时整个栈或数据区的结构.数据区的活动记录结构如图所示.┌──────┐┌─────┐│函数f返回值││返回结果值│├──────┤├─────┤│ 局部变量区││局部变量区│├──────┤├─────┤│ 全程变量区││形参单元区│├──────┤├─────┤│主程序mai n │ │ 返回地址││ 数据区│├─────┤└──────┘│ 基SP │├─────┤│函数数据区│└─────┘int m;f(n)int n;{ int c;if (n==0) c=m;else c=f(n-1)*2;return (c);}main(){ int n=2;m=5;printf("%d\n",f(n));}八:已知如下程序段a:=1;while a<=10 dobeginif a<>b thenA[a,b]:=A[a,b]+2;a:=a+1;end;1.按语法制导生成四元式中间代码序列;2.将中间代码序列划分成基本块,画出程序流图,并指出循环结点集;3.执行循环中代码外提,强度减弱优化和基本块内删除公共子表达式优化,最后画出包含优化后的中间代码的程序流图.注:数组A: array[1..10,1..10] of int;按行存放,每个下标变量占1字编址,首地址为a ddrA.东南大学历年数据结构考研试卷数据结构考研试卷94试题编号:451试题名称:数据结构一: 回答下列问题(共32分)1.最近最少使用(Least-Recently-Used)页替换是虚拟存储系统中常用的策略,试说明如何利用一页链接表时刻跟踪最近最少使用页?(8分)2.已知无向图G,V(G)={1,2,3,4},E(G)={(1,2),(1,3),(2,3),(2,4),(3,4)},试画出G的邻接多表(Adjacency Multilists),并说明,若已知点i,如何根据邻接多表找到与i相邻的点j?(8分)3.欲求前k个最大元素,用什么分类(sorting)方法好?为什么?什么是稳定分类?分别指出下列算法是否稳定分类算法,或易于改成稳定分类算法?(a) 插入分类(b) 快速分类(c) 合并分类(d) 堆(heap)分类(e) 基数分类(radix sort) (8分)4.构造最佳二叉检索树的前提条件是什么?在动态情况下,一般AVL树的查询性能不如完全二叉检索树的,为什么人们却采用AVL树呢?(8分)二:下列算法对一n位二进制数加1,假设无溢出,该算法的最坏时间复杂度是什么?并分析它的平均时间复杂性.(15分)type Num=array[1..n] of [0..1];procedure Inc(var A:Num);var j: integer;begin i:=n;while A=1 doA:=0;i:=i-1;end;A:=1;end Inc;三:给定n*m矩阵A[a..b,c..d],并设A[i,j]<=A[i,j+1](a<=i<=b,c<=j<=d-1)和A[i,j]<=A[i+1,j](a<=i<=b-1,c<=j<=d),设计一算法以比O(n*m)小的时间复杂度判定值x是否在A中.(17分)四:设图G有n个点,利用从某个源点到其余各点最短路径算法思想,设计一产生G的最小生成树的算法.(18分)五:字符序列的子序列由删除该序列任意位置的任意个元素而得.序列x和y的最长公共子序列记为Lcs(x,y),是x和y的公共子序列,且长度最大.例如,adcbcb是x=abdcbcbb和y=ad acbcb的最长公共子序列.设x长度为n,y长度为m,设计一算法计算x和y的最长公共子序列的长度,尽可能改进你的算法,使它的时间复杂性为O(n*m).(18分)数据结构考研试卷95试题编号:451试题名称:数据结构1.在磁带文件上进行二分查找行吗?为什么?(6分)2.分析确定下列程序中语句k:=k+1执行次数与n所成的数量级关系(即表示为O(f(n))的形式).(6分)k:=1; i:=k;while i<n dobegin k:=k+1; i=i+k; end;3.外排序中为什么采用k-路合并而不采用2-路合并?这种技术用于内排序有意义吗?为什么?(8分)4.索引顺序存取方法(ISAM)中,主文件已按主关键字(primary key)排序,为什么还需要主关键字索引?(6分)5.满二叉检索树(full binary search tree)符合B树定义吗?B树的插入(insetb)和删除(deleteb)算法适用于满二叉检索树吗?为什么?(10分)6.设无向图G有n个点e条边,写一算法建立G的邻接多表(adjacency multilists),要求该算法的时间复杂性为O(n+e),且除邻接多表本身所占空间外只用O(1)辅助空间.(16分)7.写一改进的递归快速排序算法,要求对于n个记录,该算法的递归深度<=1+log2(n),并说明你的算法满足这一要求.(17分)8.定义前序排列(preorder permutation)为1,2,……n的全部二叉树的中序排列(inorder permutation)集合为IP;再定义将1,2,……n从右到左经过一个栈可得到的全部排列集合为SP.例如,当n=3,SP={123,132,213,231,321}.问:IP包含于SP成立否?证明你的结论. (16分)9.设记录R的关键字为R.key(1<=i<=k),树结点T(1<=i<=k-1)指向败者记录,T�为全胜记录下标.写一算法产生对应上述R(1<=i<=k)的败者树(tree of loser),要求除R[1..k]和T[0..k-1]以外,只用O(1)辅助空间.(15分)96试题编号:451试题名称:数据结构一:回答下列问题(共46分)1.线性表(a(1),a(2),……a(n))用顺序映射表示时,a(i)与a(i+1)(1<=i<n)的物理位置相邻吗?链接表示时呢?(5分)2.一棵前序序列为1,2,3,4的二叉树,其中序序列可能是4,1,2,3吗?设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该二叉树.(7分)3.在模式匹配KMP(Knuth,Morris and Pratt)算法中所用失败函数f的定义中,为什么要求p(1)p(2)……p(f(j))为p(1)p(2)……p(j)两头匹配的真子串?且为最大真子串?(7分)4.在union-find问题中,控制union操作的权重(weighting)规则是何含义, 有何效果?控制find操作的倒塌(collapsing)规则是何含义,有何效果?(7分)5.堆排序(heap sort)是稳定排序吗?举例说明.(6分)6.给定输入文件:101,48,19,65,3,74,33,17,21,20,99,53,24,并设记录缓冲区个数k=4,写出基于败者树的外排序顺串生成算法runs输出的顺串.(6分)7.m阶B树中,m大小的确定与什么因素有关?(8分)二:设结点结构为:| data | link |,试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队和出队deleteq过程,要求它们的时间复杂性都是O(1)(不计new 和dispose时间).(10分)三:设有向图G有n个点(用1,2,……n表示),e条边,写一算法根据G的邻接表生成反向邻接表,要求时间复杂性为O(n+e).(13分)四:设二叉树结点结构为:| left | data | bf | right |,定义二叉树结点T的平衡因子bf(T)=h(左)-h(右),写一递归算法确定二叉树tree中所有节点的平衡因子bf,同时返回二叉树tree中非叶结点个数.(15分)五:设符号表T重的标识符x满足1<=x<=m,且n为对T表的最大插入次数.设计符号表T的表示结构,允许使用O(m+n)空间,并写出T的初始化(init),查找(search),插入(insert)和删除(delete)算法,要求它们的时间复杂性都是O(1).(16分)试题编号:451试题名称:数据结构一:简要回答下列问题(共32分)1.在表达式中,有的运算符要求从右到左运算,如A^B^C的计算次序应为(A^(B^C)),这在由中缀生成后缀的算法中是怎样实现的?(8分)2.给出KMP算法中失败函数f的定义,并说明利用f进行串模式匹配的规则,该算法的技术特点是什么?(8分)3.Fibonacci查找算法(fibsrch)中为什么要求m<F(a-1),试用图示说明.(8分)4.为什么在倒排文件(inverted files)组织中,实际记录中的关键字域(key fields)可删除以节约空间?而在多表(multilists)结构中这样做为什么要牺牲性能?(8分)二:试写一算法,建立无向图G的邻接多表(adjacency multilists),要求说明算法中主要数据结构和变量的意义.(15分)三:给出中序线索树的结点结构并画出一个具有头结点的中序线索树,使其树结点至少应有6个,写一算法在不使用栈和递归的情况下前序遍历一中序线索树,并分析其时间复杂性.(18分)四:若S是n个元素的集合,则S的幂集P(S)定义为S的所有子集的集合.例如,S=(a,b,c),P(S)={(),(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}.给定S,写一递归算法求P(S).(15分)五:已知在llink-rlink存储法表示的二叉树中,指针t指向该二叉树的根结点,指针p,q分别指向树中的二个结点,试写一算法,求距离这两个结点最近的共同的祖先结点.(20分)试题编号:451试题名称:数据结构一:简要回答下列问题(共40分)1.设胜者树(selection tree)由k个记录缓冲区和k-1个非叶结点构成.概念上非叶结点表示其两个子女中关键字较小者,而实际上非叶结点存放的是什么?(5分)2.索引顺序存取方法(ISAM)中,主文件已按主关键字(primary key)排序,为什么还需要主关键字索引?(6分)3.一棵前序序列为1,2,3,4的二叉树,其中序序列可能是4,1,2,3吗?设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该二叉树.(7分)4.构造最佳二叉检索树的前提条件是什么?在动态情况下,一般AVL树的查询性能不如完全二叉检索树的,为什么人们却采用AVL树呢?(8分)5.将两个栈存入数组V[1..m]中应如何安排最好?这时栈空栈满的条件是什么?(6分)6.已知无向图G,V(G)={1,2,3,4},E(G)={(1,2),(1,3),(2,3),(2,4),(3,4)},试画出G的邻接多表(Adjacency Multilists),并说明,若已知点i,如何根据邻接多表找到与i相邻的点j?(8分)二:写出用堆排序(heap sort)算法对文件F=(12,3,15,30,9,28)进行排序时,初始堆及以后每挑好一个元素重新调整后堆的状态,并指出这里的堆和败者树(tree of loser)的一个主要区别.(8分)三:设数组A存放一n位二进制数,试说明下列算法X的功能.假设无溢出,算法X的最坏时间复杂度是什么?分析它的平均时间复杂性.(8分)type Num=array[1..n] of [0..1];procedure X(var A:Num);var j: integer;begin i:=n;while A=1 dobeginA:=0;i:=i-1;end;A:=1;end;四:下面是一改进了的快速分类算法:1 procedure qsort1(var list:afile;m,n:integer);2 (设list[m].key<list[n+1].key)3 var i,j,k:integer;4 begin5 while m<n do6 begin7 i:=m;j:=n+1;k:=list[m].key;8 repeat9 repeat i:=i+1 until list.key>=k;10 repeat j:=j-1 until list[j].key<=k;11 if i<j then interchange(list,list[j]);12 until i>=j;13 interchange(list[m],list[j]);14 if n-j>=j-m15 then begin qsort1(list,m,j-1);m:=j+1;end16 else begin qsort1(list,j+1,n);n:=j-1;end17 end;(of while)18 end;问: (共20分)1.将第9,10行中的>=,<=分别改成>,<行吗?为什么?(5分)2.该排序算法稳定否,举例说明.(5分)3.对输入文件(22,3,30,4,60,11,58,18,40,16),列表表示该文件在每次调用qsort1时的状态及相应m,n的值.(5分)4.若输入文件有n个记录,简要说明支持qsort1递归所需最大栈空间用量(设一层递归用一个单位栈空间).(5分)五:给定AOE网络各事件(标号1..n)的ee,le值和邻接表,写一算法求该AOE的所有活动(用相应边的两端点表示)的关键度(criticality).(10分)六:给出中序线索树的结点结构,并画出一个具有头结点和六个树结点的中序线索树,试写一算法在不使用栈和递归的情况下前序遍历一中序线索树,并分析它的时间复杂性.(18分)试题编号:451试题名称:数据结构注意事项:(1) 答卷上需写清题号,不必抄题;回答问题字迹工整,卷面清洁.(2) 编程中所用的数据结构及主要变量需加以说明,必要时程序中加以注释.一:简要回答下列问题(共40分)1.利用两个栈s1,s2模拟一个队列时,如何用栈的运算实现队列的插入,删除以及判队空运算.请简述算法思想.(7分)2.二叉树有n个顶点,编号为1,2,3,……n,设:T中任一顶点V的编号等于左子树中最小编号减一;T中任一顶点V的右子树中最小编号等于其左子树中最大编号加一;试描绘该二叉树.(7分)3.设某文件经内排序后得到100个初始归并段(初始顺串),若使用多路归并排序算法,并要求三趟归并完成排序,归并路数最少为多少?(5分)4.若一棵树中有度数为1至m的各种结点数分别为n1,n2,...nm(nm表示度数为m的结点个数),请推导出该树中共有多少个叶结点n0的公式.(8分)5.试举例分析,堆排序法是否稳定.(5分)6.试利用KMP算法和改进算法分别求p1='abcabaa'和p2='aabbaab'的NEXT函数和NEX TVAL函数.(8分)二:阅读下列算法,指出算法A的功能和时间复杂性.(10分)procedure A(h,g: pointer);(h,g分别为单循环链表(single linked circular list)中两个结点指针)procedure B(s,q: pointer);var p: pointer;beginp:=s;while p^.next<>q do p:=p^.next;p^.next:=s;end; (of B)beginB(h,g);B(g,h);end; (of A)三:已知无向图采用邻接表存储方式,试写出删除边(i,j)的算法.(10分)四:线性表中有n个元素,每个元素是一个字符,存在向量R[1..n]中,试写一个算法,使R中的字符按字母字符,数字字符和其它字符的顺序排列.要求利用原空间,且元素移动次数最少.(15分)五:四阶B树中(如图所示),插入关键字87,试画出插入调整后树的形状.(10分)|30 60 80|/ / \ \|20 25| |35 50| |60 70 75| |82 85 90|六:试编写一算法对二叉树按前序线索化.(15分)科目编号:451科目名称:数据结构一:简要回答下列问题(共40分)1.假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树.(6分)2.简单比较文件的多重表和倒排表组织方式各自的特点.(6分)3.画出对算术表达式A-B*C/D+E^F求值时操作数栈和运算符栈的变化过程.(6分)4.找出所有满足下列条件的二叉树6分)a)它们在先序遍历和中序遍历时,得到的结点访问序列相同;b)它们在后序遍历和中序遍历时,得到的结点访问序列相同;c)它们在先序遍历和后序遍历时,得到的结点访问序列相同.5.对一个由n个关键字不同的记录构成的序列,能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏情况下至少进行多少次比较?(8分)6.已知某文件经过置换选择排序后,得到长度分别为47,9,31,18,4,12,23,7的8个初始归并段.试为3路平衡归并设计读写外存次数最少的归并方案,并求出读写外存的次数.(8分)二:已知L是无表头结点的单链表,其中P结点既不是首元结点,也不是尾元结点,(10分)a)在P结点后插入S结点的语句序列是______b)在P结点前插入S结点的语句序列是______c)在表首插入S结点的语句序列是______d)在表尾插入S结点的语句序列是______(1) P^.next:=S;(2) P^.next:=P^.next^.next;(3) P^.next:=S^.next;(4) S^.next:=P^.next;(5) S^.next:=L;(6) S^.next:=NIL;(7) Q:=P;(8) WHILE P^.next<>Q DO P:=P^.next;(9) WHILE P^.next<>NIL DO P:=P^.next;(10) P:=Q;(11) P:=L;(12) L:=S;(13) L:=P;三:设计一个符号表的表示方法,编写算法使得在该表中进行查询,插入和删除任何一个标识符X的操作在O(1)的时间内.假设1<=x<=m,n为要插入的个数,所需空间为m+n.(10分)四:试利用Dijkstra算法求下图中从顶点a到其它各顶点的最短路径,写出执行算法过程中各步的状态.(10分)____________/ 4 \↓ 6 \b------→e___9 \15↑ ↑ \ // 2 /8 ↓/a------→c g (和严蔚敏习题集上题目相同)\ \4 ↑↑12↓ 5 ↓ 10/ /d←------f__/ /\___________/3五:以顺序存储结构表示串,设计算法,求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度.(15分)六:写出按后序序列遍历中序线索树的算法.(15分)一:1.设胜者树(selection tree)由k个记录缓冲区和k-1个非叶结点构成.概念上非叶结点表示其两个子女中关键字较小者,而实际上非叶结点存放的是什么?3.给出KMP算法中失败函数f的定义,并说明利用f进行串模式匹配的规则,该算法的技术特点是什么?5.是一道关于Huffman树中叶子结点和非叶结点数量关系的计算题,具体题目记不得了.6.求有向图中任意一对顶点之间最短路径的弗洛伊德算法(allcosts-Floyd)中,要求有向图满足什么前提条件?二:在二叉树的结点结构中增加一个域:leftsize,t^.leftsize表示t结点的左子树中结点的总个数,试编写算法alloc(k),在二叉树中查找中序序号为k的结点,要求时间复杂度为O(log2(n)).三:编写算法输出从n个自然数中取k个(k<=n)的所有组合.例如,当n=5,k=3时,你的算法应该输出:543,542,541,532,531,521,432,431,421,321.四:设有向图G用邻接表的方式存储,u,v是G中的任意两个结点,写一算法,求出G中从u到v的所有简单路径.五:下面是一改进了的快速分类算法,试补充其中的空白语句,并分析该算法所需的最大递归空间是多少?procedure qsort1(var list:afile;m,n:integer);(设list[m].key<list[n+1].key)var i,j,k:integer;beginwhile m<n dobegini:=m;j:=n+1;k:=list[m].key;repeatrepeat i:=i+1 until list.key>=k;repeat j:=j-1 until list[j].key<=k;if i<j then interchange(list,list[j]);until i>=j;interchange(list[m],list[j]);if n-j>=j-mthen begin qsort1(list,m,___);______;endelse begin qsort1(list,___,n);______;endend;(of while)end;六:给定n*m矩阵A[a..b,c..d],并设A[i,j]<=A[i,j+1](a<=i<=b,c<=j<=d-1)和A[i,j]<=A[i+1,j](a<=i<=b-1,c<=j<=d),设计一算法以O(n+m)的时间复杂度判定值x是否在A中数据结构：三、简要回答下列问题：（30）1．一棵二叉树的先序、中序和后序序列如下：其中一部分为标出，请构造出该二叉树先序：CDE GHI K中序：CB FA JKIG后序：EFDB JIH A2．将下面数据表建成一个堆（70，12，20，31，1，5，44，66，61，200，30，80，1 50，4，28）3．试写出取出广义表A=（（a,x,y,z）,(b,c)）中的c的复合函数4．设目标串为S="abcaabbabcabaacbacba"，模式为P="abcabaa"，手工计算P的next val值，并写出利用nextval值按KMP算法对目标S进行模式匹配的过程5．已知下面二叉排序树各结点值依次为1-9，请标出各结点的值。
东南⼤学数值分析上机题答案数值分析上机题第⼀章17.（上机题）舍⼊误差与有效数设∑=-=Nj N j S 2211，其精确值为）111-23（21+-N N 。
（1）编制按从⼤到⼩的顺序1-1···1-311-21222N S N +++=，计算N S 的通⽤程序；（2）编制按从⼩到⼤的顺序121···1)1(111222-++--+-=N N S N ，计算NS 的通⽤程序；（3）按两种顺序分别计算210S ,410S ,610S ,并指出有效位数（编制程序时⽤单精度）；（4）通过本上机题，你明⽩了什么？解：程序：（1）从⼤到⼩的顺序计算1-1···1-311-21222N S N +++=：function sn1=fromlarge(n) %从⼤到⼩计算sn1format long ; sn1=single(0); for m=2:1:nsn1=sn1+1/(m^2-1); end end（2）从⼩到⼤计算121···1)1(111222-++--+-=N N S N function sn2=fromsmall(n) %从⼩到⼤计算sn2format long ; sn2=single(0); for m=n:-1:2sn2=sn2+1/(m^2-1); end end（3）总的编程程序为： function p203()clear allformat long;n=input('please enter a number as the n:') sn=1/2*(3/2-1/n-1/(n+1));%精确值为sn fprintf('精确值为%f\n',sn);sn1=fromlarge(n);fprintf('从⼤到⼩计算的值为%f\n',sn1);sn2=fromsmall(n);fprintf('从⼩到⼤计算的值为%f\n',sn2);function sn1=fromlarge(n) %从⼤到⼩计算sn1 format long;sn1=single(0);for m=2:1:nsn1=sn1+1/(m^2-1);endendfunction sn2=fromsmall(n) %从⼩到⼤计算sn2 format long;sn2=single(0);for m=n:-1:2sn2=sn2+1/(m^2-1);endendend运⾏结果：从⽽可以得到N值真值顺序值有效位数2 100.740050 从⼤到⼩0.740049 5从⼩到⼤0.740050 64 100.749900 从⼤到⼩0.749852 3从⼩到⼤0.749900 66 100.749999 从⼤到⼩0.749852 3从⼩到⼤0.749999 6（4）感想：通过本上机题，我明⽩了，从⼩到⼤计算数值的精确位数⽐较⾼⽽且与真值较为接近，⽽从⼤到⼩计算数值的精确位数⽐较低。
东南大学算法设计与分析课程考试复习试题题库及答案1什么是基本运算？答：基本运算是解决问题时占支配地位的运算（一般1种，偶尔两种）；讨论一个算法优劣时，只讨论基本运算的执行次数。
2什么是算法的时间复杂性（度）？答：算法的时间复杂性（度）是指用输入规模的某个函数来表示算法的基本运算量。
T(n)=4n33什么是算法的渐近时间复杂性？答：当输入规模趋向于极限情形时（相当大）的时间复杂性。
4表示渐进时间复杂性的三个记号的具体定义是什么？答：1. T(n)= O(f(n))：若存在c > 0，和正整数n0≣1，使得当n≣n0时，总有T(n)≢c*f(n)。
（给出了算法时间复杂度的上界，不可能比c*f(n)更大）2. T(n)=Ω(f(n))：若存在c > 0，和正整数n0≣1，使得当n≣n0时，存在无穷多个n ，使得T(n)≣c*f(n)成立。
（给出了算法时间复杂度的下界，复杂度不可能比c*f(n)更小）3. T(n)= Θ(f(n))：若存在c1,c2>0，和正整数n0≣1，使得当n≣n0时，总有T(n)≢c1*f(n)，且有无穷多个n，使得T(n)≣c2*f(n)成立，即：T(n)= O(f(n))与T(n)=Ω(f(n))都成立。
（既给出了算法时间复杂度的上界，也给出了下界）5什么是最坏情况时间复杂性？什么是平均情况时间复杂性？答：最坏情况时间复杂性是规模为n的所有输入中，基本运算执行次数为最多的时间复杂性。
平均情况时间复杂性是规模为n的所有输入的算法时间复杂度的平均值（一般均假设每种输入情况以等概率出现）。
6一般认为什么是算法？什么是计算过程？答：一般认为，算法是由若干条指令组成的有穷序列，有五个特性a.确定性（无二义）b.能行性（每条指令能够执行）c.输入 d.输出 e.有穷性（每条指令执行的次数有穷）只满足前4条而不满足第5条的有穷指令序列通常称之为计算过程。
7算法研究有哪几个主要步骤？主要从哪几个方面评价算法？答：算法研究的主要步骤是1)设计2）表示 3）确认，合法输入和不合法输入的处理 4）分析 5）测试评价算法的标准有1）正确性 2）健壮性 3）简单性 4）高效性 5）最优性8关于多项式时间与指数时间有什么样的结论？答：1. 多项式时间的算法互相之间虽有差距，一般可以接受。
数据结构C语言版第版习题答案—严蔚敏GE GROUP system office room 【GEIHUA16H-GEIHUA GEIHUA8Q8-数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论............................................. 第2章线性表 ........................................... 第3章栈和队列 ......................................... 第4章串、数组和广义表.................................. 第5章树和二叉树 ....................................... 第6章图................................................ 第7章查找 ............................................. 第8章排序.............................................第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据结构部分课后习题答案(1-3)第一章1.1数据的逻辑结构是从具体问题中抽象出来的数学模型，体现了事物的组成和事物之间的逻辑关系。
数据的存储结构主要用来解决各种逻辑结构在计算机中物理存储表示的问题。
1.2事前分析和事后统计事前分析：优点，程序不必运行，所得结果只依赖于算法本身缺点，不够精确事后统计：优点，精确缺点，必须运行程序，所得结果依赖于硬件、环境等因素1.3void func(int n){int i=1,k=100;while(i<n){k++;i+=2;}}考虑赋值、运算操作执行的次数第3行赋值2次第6行赋值执行n次，加法执行n次所以，总共2n+2次操作，算法复杂度为O(n)1.4y=y+i*j执行次数：1.5第二章2.9内存中一片连续空间（不妨假设地址从1到m）提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。
答：S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。
2.10线性表是数据项组成的一种有限且有序的序列，各元素之间呈线性关系。
从逻辑结构来说，栈和队列与线性表相同，都是典型的线性结构。
与线性表不同的是，栈和队列的操作特殊，受到一定的限制，仅允许在线性表的一端或两端进行。
栈是限定仅在一端进行插入删除的线性表，无论插入、删除还是读取都在一端进行，按后进先出的原则。
队列的元素只能从一端插入，从另一端删除，按先进先出的原则进行数据的存取。
2.11共有132种合法序列。
235641序列可以。
154623序列不可以。
对于每一个数来说，必须进栈一次、出栈一次。
我们把进栈设为状态‘1’，出栈设为状态‘0’。
n个数的所有状态对应n个1和n个0组成的2n位二进制数。
