第七章 数据库技术基础

2005.11

●在关系代数运算中，关系S、SP和R如下表所示。若先___(33)___，则可以从S和SP获得R。其对应的关系表达式为___(34)___。如下的SQL语句可以查询销售总量大于1000的部门号。
Select 部门名 From S
Where 部门号 in (Select 部门号 From SP Group by ___(35)___)

供选择的答案：
（33）A.对S进行选择运算，再与S进行自然连接运算
　　　B.对S进行选择运算，再与SP进行自然连接运算，最后进行投影运算
　　　C.对S和SP进行笛卡尔积运算，再对运算结果进行投影运算
　　　D.分别对S和SP进行投影运算，再对运算结果进行笛卡尔积运算

（34）A. 　　　　　　　　　　B.
　　 　C. 　　 　　　 D.

（35）A.部门号 where sum(销售量)>1000
　　　B.部门号 having sum(销售量)>1000
　　　C.商品号 where sum(销售量)>1000
　　　D.商品号 having sum(销售量)>1000

●给定关系R（A1，A2，A3，A4）上的函数依赖集F={A1A3->A2，A2->A3}，R候选关键字为____(36)___。分解ρ={(A1,A2)，(A1,A3)}___(37)____。
供选择的答案：
(36)A.A1A3　　　　　 B.A1A2A3 　　　　C.A1A3A4 　　　　　D.A2和A1A3
(37)A.是无损联接的　　　　　　　　　　　 B.是保持函数依赖的
　　C.既是无损联接又保持函数依赖　　　　 D.既是有损联接又不保持函数依赖

2005.5

●某数据库中有供应商关系S和零件关系P，其中；供应商关系模式S（Sno，Sname，Szip，City）中的属性分别表示：供应商代码、供应商名、邮编、供应商所在城市；零件关系模式P（Pno，Pname，Color，Weight，City）中的属性分别表示：零件号、零件名、颜色、重量、产地。要求一个供应商可以供应多种零件，而一种零件可由多个供应商供应。请将下面的SQL语句空缺部分补充完整。
CREATE TABLE SP（Sno CHAR(5)，
　　　Pno CHAR(6)，
　　　Status CHAR(8)，
　　　Qty NUMERIC(9)，
　　　__(33)__(Sno，Pno)，
　　　__(34)__(Sno)，
　　　__(35)__(Pno))；
查询供应了“红”色零件的供应商号、零件号和数量（Qty）的元组演算表达式为：

供选择的答案：
(33) A.FOREIGN KEY 　　　　　　　　　　　　　B.PRIMARY KEY
　　 C.FOREIGN KEY（Sno）REFERENCES S 　　 　D.FOREIGN KEY（Pno）PEFERENCES P
(34) A.FOREIGN KEY　　　　　　　　　　　　　 B.PRIMARY KEY
　　 C.FOREIGN KEY（Sno）REFERENCES S　　　　D.FOREIGN KEY（Pno）PEFERENCES P
(35) A.FOREIGN KEY　　　　　　　　　　　　　 B.PRIMARY KEY
　　 C.FOREIGN KEY（Sno）REFERENCES S　　　　D.FOREIGN KEY（Pno）PEFERENCES P

（36）A. 　　　　　　B.
　　　C. 　　　　　　D.

　　　　　　　
（37）A.t[1]=u[1]∧t[2]=w[2]∧t[3]=v[4] B.t[1]=v[1]∧t[2]=u[2]∧t[3]=u[4]
　　　C.t[1]=w[1]∧t[2]=u[2]∧t[3]=u[4] D.t[1]=u[1]∧t[2]=v[2]∧t[3]=v[4]

●在某个信息系统中，存在如下的业务陈述：①一个客户提交0个或多个订单；②一个订单由一个且仅由一个客户提交。系统中存在两个类：“客户”类和“订单”类。对应每个“订单”类的实例，存在___(46)___“客户”类的实例；对应每个“客户”类的实例，存在___(47)___个“订单”类的实例。
供选择的答案：
（46）A.0个　　　 B.1个 　　　C.1个或多个　　　 D.0个或多个
（47）A.0个　　　 B.1个　　　 C.1个或多个　　　 D.0个或多个

2004.11

● 假定每一车次具有唯一的始发站和终点站。如果实体“列车时刻表”属性为车次、始发站、发车时间、终点站、到达时间，该实体的主键是__(42)__；如果实体“列车运行表”属性为车次、日期、发车时间、到达时间，该实体的主键是__(43)__。通常情况下，上述“列车时刻表”和“列车运行表”两实体间__(44)__联系。
（42）A.车次　　　　　 B.始发站　　　　　　 C.发车时间　　　　　　 D.车次，始发站
（43）A.车次　　　　　 B.始发站　　　　　　 C.发车时间　　　　　　 D.车次，日期
（44）A.不存在　　　　 B.存在一对一　　　　 C.存在一对多　　　　　 D.存在多对多

● 关系模式R（U，F），其中U＝{W,X,Y,Z},F={WX→Y,W→X, X→Z,Y→W}。关系模式R的候选建是__(45)__、__(46)__是无损连接并保持函数依赖的分解。
（45）A.W和 Y　　　　　B. WY　　　　　　　　C.WX　　　　　　　　　 D.WZ
（46）A.p={R1(WY),R2(XZ)}　　　　　　　 B.p={R1(WZ),R2(XY)}
　　　C.p={R1(WXY),R2(XZ)}　　　　　　　D.p={R1(WX),R2(YZ)}

2004.5

● 已知关系R如下表所示，关系R的主属性为__（17）__，候选关键字分别为__(18)__。

R

(17)A.ABC　　　　 B.ABD 　　　　　C.ACD 　　　　　 　　D.ABCD
(18)A.ABC 　　　　B.AB 、AD 　 　 C.AC、AD和CD　　　　 D.AB、AD、BD的CD

● 设供应商零件的关系模式为SP(Sno,Pno,Qty)，其中Sno表示供应商号，Pno表示零件号，Qty表示零件数量。查询至少包含了供应商“168”所供应的全部零件的供应商号的SQL语句如下：
　　SELECT Sno
　　　　FROM SP SPX
　　　　　WHERE __ (19) __
　　　　　　(SELECT *
　　　　　　　　FROM SP SPY
　　　　　　　　WHERE __ (20) __ AND NOT EXISTS
　　　　　　　　　(SELECT *
　　　　　　　　　　　FROM SP SPZ
　　　　　　　　　　　　　　　WHERE __ (21) __));
(19) A.EXISTS 　　　　B. NOT EXISTS 　　　　　C. IN　　　　　 D. NOT IN
(20) A. SPY.Sno=’168’ 　　　　　　B. SPY Sno<>’168’
　　 C.SPY.Sno=SPX.Sno 　　 　　　　D.SPY.Sno<>SPX.Sno
(21) A.SPZ.Sno=SPY.Sno AND SPZ.Pno=SPY.Pno
　　 B. SPZ.Sno=SPX.Sno AND SPZ.Pno=SPX.Pno
　　 C. SPZ.Sno=SPX.Sno AND SPZ.Pno=SPY.Pno
　　 D. SPY.Sno=’168’ AND SPZ.Pno=SPY.Pno

● 设f表示某个二元逻辑运算符，PfQ的真值表如下表所示，则PfQ等价于__(61)__。

（61）A. 　　　　　B. 　　　　　C. 　　　　　　D.

● 设∪表示集合的并运算，∩表示集合的交运算， 表示集合A的绝对补，A-B表示集合A与B的差，则A-B =__(62)__。
（62）A. 　 　　B. 　　　　C. 　　　D.

● 设集合Z26={0，1，…，25}，乘法密码的加密函数为Ek : Z₂₆→Z₂₆ , E_k (i)=(ik)mod26，密钥k∈Z₂₆ -{0}，则加密函数E₇(i)=(7i) mod 26是一个__(63)__函数。
（63）A.单射但非满射　 　　 B.满射但非单射　　 C.非单射且非满射　 　 D.双射

2003

●在数据库逻辑结构的设计中，将E-R模型转换为关系模型应遵循相关原则。对于三个不同实体集和它们之间的多对多联系m:n:p，最少可转换为__(17)__个关系模式。
(17) A. 2 　　　B．3 　　　C. 4 　　　　D. 5

●给定关系模式R(U，F)，U={A，B，C，D，E}，F={B→A，D→A，A→E，AC→B}，其属性AD的闭包为__(18)__，其候选关键字为__(19)__。
(18) A. ADE 　　B. ABD　　 C. ABCD 　 　D. ACD
(19) A. ABD 　　B．ADE 　　C．ACD 　　　D．CD

●若有关系模式R(A，B，C)和S(C，D，E)，对于如下的关系代数表达式：
E=∏A,D(σB<'2003'∧R.C=S.C∧E='80'(R×S))
E=∏A,D(σR.C=S.C(σB<'2003'(R)×σE='80'(S)))
E=∏A,D(σB<'2003'(R) σE='80'(S))
E=∏A,D(σB<'2003'∧E='80'(R S))
正确的结论是__(20)__ ，表达式 __(21)__ 的查询效率最高。
(20) A. E₁≡E₂≡E₃≡E₄ 　　　　　　B. E₃≡E₄但E₁≠E₂
　 　C. E₁≡E₂但E₃≠E₄ 　　　　　　D. E₃≠E₄但E₂≡E₄
(21) A. E₁ 　　　B. E₂ 　　C. E₃ 　　　　D. E₄

●设集合N={0，1，2，…}，f为从N到N的函数，且

经计算f(90)=81，f(89)=81，f(49)=__(62)__。
((62)A．39 　　　　　B．49　　　　　　　 C．81　　　　　 D．92

●集合A={d．b．c}上的二元关系R为：R={<a,a>,<c,c>,<a,b>)}，则二元关系R是__(63)__。
(63)A．自反的　 　　 B．反自反的 　　　　C．对称的　　　　 D．传递的

转载请保留：本文为作者收集整理，引用请注明出处，谢谢大家支持。更多资源信息请进朱祥的BLOG

第八章 数据结构

2005.11

●在活动图中，结点表示项目中各个工作阶段的里程碑，连接各个结点的边表示活动，边上的数字表示活动持续的时间。在下面的活动图中，从A到J的关键路径是_____(16)___，关键路径长度是___(17)___，从E开始的活动启动的最早时间是____(18)____。

供选择的答案：
(16)A.ABEGJ　　　　 B.ADFHJ　　　　　 C.ACFGJ　　　　　 D.ADFIJ
(17)A.22　　　　　　B.49　　　　　　　C.19　　　　　　　D.35
(18)A.10　　　　　　B.12　　　　　　　C.13　　　　　　　D.15

●已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为___(38)___。
供选择的答案：
（38）A.BCDEAF　　　 B.ABDCEF　　　　 C.DBACEF　　　　　　D.DABECF

●在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个结点下标为k（起始下标为1）,那么___(39)___时采用顺序存储更节省空间。
供选择的答案：

　(39)A. 　　　　　　　B.

　　　　　　C. 　　　 　 　　D.

●简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个节点。若无向图G有n个节点，其邻接矩阵为A[1..n,1..n],且压缩存储在B[1..k]中，则k的值至少为____(40)____。若按行压缩存储对称矩阵的上三角元素，则当n等于10时，边(V6，V3)的信息存储在B[___(41)___]中。
供选择的答案：
(40)A. 　　　　B. 　　　　C. 　　　　D.
(41)A.18 　　　　　　　　B.19 　　　　　　　 　C.20　　　　　　　　　D.21

●在11个元素的有序表A[1..11]中进行折半查找（ ）查找元素A[11]时，被比较的元素的下标依次是___(44)___。
供选择的答案：
(44)A.6,8,10,11　　 B.6,9,10,11　　　 C.6,7,9,11　　　　　D.6,8,9,11

●由元素序列（27,16,75,38,51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为2的结点）为____(46)____。
供选择的答案：
(46)A.27　　　　　 B.38　　　　　 C.51　　　　　　 D.75

●若排序前后关键字相同的两个元素相对位置不变，则称该排序方法是稳定的。___(47)__排序是稳定的。
供选择的答案：
(47)A.归并　　　　 B.快速　　　　 C.希尔　　　　　 D.堆

●若对象A可以给对象B发送消息，那么___(48)___。
供选择的答案：
(48)A.对象B可以看见对象A　　　　　　 B.对象A可看见对象B
　　C.对象A、B相互不可见　　　　　　 D.对象A、B相互可见

●类描述了一组对象共同的特性，下列叙述中正确的是____(49)____。
供选择的答案：
(49)A.类本身不能具有变量
　　B.对象具有类定义的所有变量的一份拷贝
　　C.对象间不能共享类定义的变量
　　D.可通过类名访问静态变量(类变量)

●___(50)___反映了类间的一种层次关系，而___(51)____反映了一种整体与部分的关系。
供选择的答案：
(50)A.继承　　　　　　 B.组合　　　　　 C.封装　　　　　　 D.多态
(51)A.继承　　　　　　 B.组合　　　　　 C.封装　　　　　　 D.多态

●下列叙述中正确的是___(52)__。
供选择的答案：
(52)A.面向对象程序设计语言都不支持过程化的程序设计
　　B.面向对象系统只可采用面向对象程序设计语言实现
　　C.某些过程化程序设计语言也可实现面向对象系统
　　D.面向对象程序设计语言不支持对成员变量的直接访问

2005.5

●循环链表的主要优点是___(38)___

供选择的答案：
A.不再需要头指针了
B.已知某个结点的位置后，能很容易找到它的直接前驱结点
C.在进行删除操作后，能保证链表不断开
D.从表中任一结点出发都能遍历整个链

●表达式a*(b+c)-d的后缀表达形式为___(39)___。
供选择的答案：
A.abcd*+- 　　　　B.abc+*d- 　　　　C.abc*+d- 　　　　D.-+*abcd

●若二叉树的先序遍历序列为ABDECF，中序遍历序列DBEAFC，则其后序遍历序列为__(40)___。
供选择的答案：
A.DEBAFC 　　　　B.DEFBCA 　　　　　C.DEBCFA 　　　　　D.DEBFCA

●无向图中一个顶点的度是指图中___(41)___。
供选择的答案：
（41）A.通过该顶点的简单路径数　　　　　 B.通过该顶点的回路数
　　　C.与该顶点相邻的顶点数　　　　　　 D.与该顶点连通的顶点数

●在常用的描述二叉排序树的存储结构中，关键字值最大的结点___(48)____。
供选择的答案：
（48）A.左指针一定为空　　　　　　　　 B.右指针一定为空
　　　B.左右指针均为空　　　　　　　　 D.左右指针均不为空

●一个具有n(n>0)个顶点的连通无向图至少有___(49)____条边。
供选择的答案：　
A.n+1　　　　　 B.n 　　　　　　C.n+2　　　　　 D.n-1

●由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为__(50)__。
供选择的答案：
A.23　　　　　　B.37　　　　　　C.44　　　　　　D.46

● 在最好和最坏的情况下的时间复杂度均为O(nlogn)且稳定的排序方法是___(51)__。
供选择的答案：
A．基数排序 　　B．快速排序　　 C．堆排序 　　　D．归并排序

●已知一个线性表（38，25，74，63，52，48），假定采用散列函数h(key)=key%7计算散列地址，并散列存储在散列表A[0..6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为____(52)____。
供选择的答案：
A.1.5　　　　　 B.1.7　　　　　　C.2.0 　　　　　D.2.3

●为在状态空间树中__(53)___，可以利用LC-检索（Least Cost Search）快速找到一个答案结点。在进行LC-检索时，为避免算法过分偏向于作纵深检查，应该___(54)____。
供选择的答案：
（53）A.找出任一个答案结点 　　　　　　B.找出所有的答案结点
　　　C.找出最优的答案结点　　　　　　 D.进行遍历
（54）A.使用精确的成本函数c(.)来作LC-检索
　　　B.使用广度优先检索
　　　C.使用深度优先检索
　　　D.在成本估计函数ê(.)中考虑根结点到当前结点的成本(距离)

●以比较为基础的排序算法在最坏情况下的计算时间下界为__(55)___。
供选择的答案：
A．O(n)　　　　 B．O(n)　　　　 C．O(log₂n)　　　　 D．O(nlog₂n)

●利用动态规划方法求解每对结点之间的最短路径问题(all pairs shortest path problem)时，设有向图G=<V，E>共有n个结点，结点编号1～n，设C是G的成本邻接矩阵，用D^k(i，j)即为图G中结点i到j并且不经过编号比k还大的结点的最短路径的长度（D^k(i，j)即为图G中结点i到j的最短路径长度），则求解该问题的递推关系式为___(56)___。
供选择的答案：
A.D^k (i，j)=D^k-1(i，j)+C(i，j)
B.D^k (i，j)=min{D^k-1(i，j)，D^k-1(i，j)+C(i，j)}
C.D^k (i，j)=D^k-1(i，k)+D^k-1(k，j)
D.D^k (i，j)=min{D^k-1(i，j)，D^k-1(i，k)+D^k-1(k，j)}

2004.11

● 在一颗完全二叉树中，其根的序号为1，__(33)__可判定序号为p和q的两个接点是否在同一层。
（33）A. = 　　B. = 　　　 C. +1= 　　　D. = +1

● 堆是一种数据结构，__(34)__是堆
（34）A.(10,50,80,30,60,20,15,18) 　　　　　B.(10,18,15,20,50,80,30,60)
　　　C.(10,15,18,50,80,30,60,20)　　　　　 D.(10,30,60,20,15,18,50,80)

● __(35)__从二叉树的任一节点出发到根的路径上，所经过的节点序列必须按其关键字降序排列
（35）A.二叉排序树　　　　 B.大顶堆　　　　　 C.小顶堆　　　　　 D.平衡二叉树

● 若广义表L=((1,2,3)),则 L的长度和深度分别为__(36)__。
（36）A.1 和1　　　　　　　B.1和2　　　　　　 C.1和3　　　　　　 D.2和2

● 若对27个元素只进行三趟多路归并排序，则选取的归并路数为__(37)__。
（37）A.2　　　　　　　　　B.3 　　　　　　 　C.4　　　　　　　　D.5

2004.5

● __（4）__的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。
（4）A.形存储结构　 　　 　B.链式存储结构　　　 C.索引存储结构　　　 D.散列存储结构

● 若循环队列以数组Q[0..m-1]作为其存储结构，变量rear表示循环队列中队尾元素的实际位置，其移动按rear=(rear+1) mod m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是__（5）__。
（5） A.rear-length 　　　　　　　　　　B.(rear-length+m)mod m
　　　C.(1+rear+m-length) mod m 　　　　D.m-length

● 一个含n有个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有__（6）__个零元素。
（6）A.e 　　　　　　B.2e 　　　　　　　C. n²-e 　　　　　D. n²-2e

● 若一棵哈夫曼树共有9个顶点，则其叶子结点的个数为__（7）__。
（7）A.4 　　　　　　B.5 　　　　　　 　C. 6 　　　　　　 D.7

● 若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵__（8）__。
（8）A．第i行中值为1的元素个数　 　　　　　B.所有值为1的元素总数
　　 C.第i行及第i列中为1的元素总个数　 　　D.第i列中值为1的元素个数

● 在一棵度为3的树中，其有2个度为3的结点，有一个度为2的结点，则有__（9）__个度为0的结点。
（9）A.4　　　　　　 B.5 　　　　　　　C.6　　　　　　　 D.7

● 设结点x和y是二叉树中任意的两个结点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是__（10）__。
（10）A.x是y的左兄弟　　　　　 B.x是y的右兄弟
　　　C.x是y的祖先　 　　　　　D.x是y的后裔

● 设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找的平均查找长度为__（11）__。
（11）A.21　　　　　　　 B.23　　　　　　　　 C.41　　　　　　　　 D.62

● 已知有一维数组A[0..m*n-1]，若要对应为m行、n列的矩阵，则下面的对应关系__(14)__可将元素A[k](0≤k<m*n)表示成矩阵的第i行、第j列的元素(0≤i<m，0≤j<n)。
（14）A. i=k/n,j=k%m 　　　　B .i=k/m,j=k%m 　　　　　C. i=k/n,j=k%n　　　　 D. i=k/m,j=k%n

2003

●关键路径是指AOE(Activity On Edge)网中____(4)____。
(4) A. 最长的回路 　　　　　　　　　　　　　　B. 最短的回路
　　C. 从源点到汇点(结束顶点)的最长路径 　　　D. 从源点到汇点(结束顶点)的最短路径

●以下序列中不符合堆定义的是____(5)____。
(5)A．(102，87，100，79，82，62，84，42，22，12，68)
　 B．(102，100，87，84，82，79，68，62，42，22，12)
　 C．(12，22，42，62，68，79，82，84，87，100，102)
　 D．(102，87，42，79，82，62，68，100，84，12，22)

● 一个具有767个结点的完全二叉树，其叶子结点个数为__(6)__。
(6) A. 383　　　 B. 384 　　　　C. 385 　　　　D. 386

●若一个具有n个结点、k条边的非连通无向图是一个森林(n>k)，则该森林中必有__(7)__棵树。
(7) A. k　　　　 B. n 　　　　　C. n-k 　　　　D. n+k

●若G是—个具有36条边的非连通无向图(不含自回路和多重边)，则图G至少有__(8)_个顶点。
(8) A. 11 　　 　B. 10　　　　　C. 9 　　　　　D. 8

●将两个长度为 n 的递增有序表归并成一个长度为 2n 的递增有序表，最少需要进行关键字比较__(9)__次。
(9) A. I 　　　　B. n-1 　　　　C. n 　　　　　D. 2n

●已知AOE网中顶点v1～v7分别表示7个事件，弧al～a10分别表示10个活动，弧上的数值表示每个活动花费的时间，如下图所示。那么，该网的关键路径的长度为__(10)__，活动a6的松驰时间（活动的最迟开始时间-活动的最早开始时间）为__(11)__。
(10) A. 7 　 　　B. 9 　　　　　C. 10　　　　　D. 11
(11) A. 3 　　 　B. 2 　　　　　C. 1 　　　　　D. 0

●对n个元素进行快速排序时，最坏情况下的时间复杂度为__(64)__。
(64) A．O(1og₂n)　　 B．O(n) 　　　　　C．O(nlog₂n) 　　　D． 0(n²)

●任何一个基于“比较”的内部排序的算法，若对6今元素进行排序，则在最坏情况下所需的比较次数至少为__(65)__。
(65) A． 10　　　　　B． 1l 　　　 　　C． 21 　　　　　　D． 36

转载请保留：本文为作者收集整理，引用请注明出处，谢谢大家支持。更多资源信息请进朱祥的BLOG

第九章 常用算法设计

2005.11

●设求解某问题的递归算法如下：

求解该算法的计算时间时,仅考虑算法Move所做的计算为主要计算,且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为____(53)____；设算法Move的计算时间为k，当n=4时，算法F的计算时间为___(54)___。
供选择的答案：
（53）A.T(n)=T(n-1)+1　　　　　　　 B.T(n)=2T(n-1)
　　　C.T(n)=2T(n-1)+1　　　　　　　D.T(n)=2T(n+1)+1
（54) A.14k　　　　　 B.15k　　　　　 C.16k　　　　　　　 D.17k

●利用贪心法求解0/1背包问题时，___(55)___能够确保获得最优解。用动态规划方法求解0/1背包问题时，将“用前i个物品来装容量是X的背包”的0/1背包问题记为KNAP(1,i,X),设f_i(X)是KNAP(1,i,X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为W_j和p_j(j=1~n)。则依次求解f₀(X)、f₁(X)、...、f_n(X)的过程中使用的递推关系式为___(56)___。
供选择的答案：
(55)A.优先选取重量最小的物品　　　　　　　　　 B.优先选取效益最大的物品
　　C.优先选取单位重量效益最大的物品 　　　　　D.没有任何准则
(56)A.f_i(X)=min{f_i-1(X),f_i-1(X)+p_i}
　　B.f_i(X)=max{f_i-1(X),f_i-1(X-W_i)+p_i}
　　C.f_i(X)=min{f_i-1(X-W_i),f_i-1(X-W_i)+p_i}
　　D.f_i(X)=max{f_i-1(X-W_i),f_i-1(X)+p_i}

2004.11

● 采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是__(52)__
（52）A.当前所出的决策不会影响后面的决策
　 　 B.原问题的最优解包含其子问题的最优解
　 　 C.问题可以找到最优解，但利用贪心法不能找到最优解
　 　 D.每次决策必须是当前看来最优决策才可以找到最优解

● 下面函数中渐进时间最小的是__(53)__
(53)A.T1(n)=n+nlogn　　 B.T2(n)=2n+nLogn　　 C.T3(n)=n²-logn　　　 D.T4(n)=n+100logn

● 下面的程序段违反了算法的__(54)__原则
void sam()
　{
　　int n=2　
　　while (!odd(n)) n+=2;
　　　printf(n);
　　　}
(54) A.有穷性　　　　　 B.确定性　　　　　　 C.可行性　　　　　　　 D.健壮性

● 拉斯维加斯（Las Vegas）算法是一种常用的__(55)__算法
(55) A.确定性　　　　　 B.近似　　　　　　　 C.概率　　　　　　　　 D.加密

● 在分支-界限算法设计策略中，通常采用__(56)__搜索问题的解空间。
（56）A.深度优先　　　　B.广度优先　　　　　 C.自底向上　　　　　　 D.拓扑排序

● 在下列算法设计方法中，__(57)__在求解为题的过程中并不从整体最优上加以考虑，而是做出在当前看来是最好的选择。利用该设计方法可以解决__(58)__问题
（57）A.分治法　　　　　B.贪心法　　　　　　 C.动态规划法　　　　　 D.回溯法
（58）A.排序　　　　　　B.检索　　　　　　　 C.背包　　　　　　　　 D.0/1背包

● 以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O（nlogn）。下面的排序算法中，最坏情况下计算时间可以达到O（nlogn）的是__(59)__，该算法采用的设计方法是__(60)__。
（59）A.归并算法　　 　 B.插入算法　　　　　 C.选择算法　　　　　　 D.冒泡算法
（60）A.分治法　　　　　B.贪心法　　　　　　 C.动态规划法　　　　　 D.回溯法

2004.5

● 类比二分搜索算法，设计k分搜索（k为大于2的整数）如下：首先检查n/k处（n为被搜索集合的元素个数）的元素是否等于要搜索的值，然后检查2n/k处的元素，…，依次类推，或者找到要搜索的元素，或者把集合缩小到原来的1/k；如果未找到要搜索的元素，则继续在得到的集合上进行k分搜索；如此进行，直至找到要搜索的元素或搜索失败。此k分搜索算法在最坏情况下搜索成功的时间复杂度为__(64)__，在最好情况下搜索失败的时间复杂度为__(65)__。
(64) A. O(logn) 　　　　B. O(nlogn)　　　　 C. O(log_kn)　　　 D. O(nlog_kn)
(65) A. O(logn)　　　　 B. O(nlogn) 　　　　C. O(log_kn) D. O(nlog_kn)

 转载请保留：本文为作者收集整理，引用请注明出处，谢谢大家支持。更多资源信息请进朱祥的BLOG