算法题库及答案

一、单项选择题

2

1某算法的时间复杂度是O(n)，表明该算法（ ）。

22

A 问题规模是n B 问题规模与n成正比

2 2

C 执行时间等于n D 执行时间与n成正比 2、关于数据结构的描述，不正确的是（ ）。 A 数据结构相同，对应的存储结构也相同。

B 数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C 数据结构操作的实现与存储结构有关。 D 定义逻辑结构时可不考虑存储结构。

3、按排序策略分来，起泡排序属于（ ）。

A 插入排序 B 选择排序 C 交换排序 D 归并排序 4、利用双向链表作线性表的存储结构的优点是（ ）。

A 便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C 节省空间 D 便于销毁结构释放空间

5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（ ）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、Dijkstra算法是按（ ）方法求出图中从某顶点到其余顶点最短路径的。 A 按长度递减的顺序求出图的某顶点到其余顶点的最短路径

B 按长度递增

算法设计与分析考试复习试卷

《算法设计与分析》试卷1

一、多项选择题（每空2分，共20分）：

1、以下关于算法设计问题的叙述中正确的是__________。

A、计算机与数值问题的求解——方程式求根、插值问题、数值积分、函数逼近等有关

B、利用计算机无法解决非数值问题

C、计算机在解决分类、语言翻译、图形识别、解决高等代数和组合分析等方面的数学问题、定理证明、公式推导乃至日常生活中各种过程的模拟等问题中，主要进行的是判断、比较，而不是算术运算

D、算法设计与分析主要研究对象是非数值问题，当然也包含某些数值问题

2、算法的特征包括_________。

A、有穷性 B、确定性

C、输入和输出 D、能行性或可行性

3、以下描述是有关算法设计的基本步骤：

①问题的陈述 ②算法分析 ③模型的拟制 ④算法的实现

⑤算法的详细设计 ⑥文档的编制，应与其它环节交织在一起

其中正确的顺序是__________。

A、①②③④⑤⑥ B、①③⑤②④⑥

C、②④①③⑤⑥ D、⑥①③⑤②④

4、以下说法正确的是__________。

A、数学归纳法可以证明算法终止性

B、良序原则是证明算法的正确性的有力工具

C、x = 小于或等于x的最大整数（x的低限）

D、x =

算法设计与分析考试复习试卷

《算法设计与分析》试卷1

一、多项选择题（每空2分，共20分）：

1、以下关于算法设计问题的叙述中正确的是__________。

A、计算机与数值问题的求解——方程式求根、插值问题、数值积分、函数逼近等有关

B、利用计算机无法解决非数值问题

C、计算机在解决分类、语言翻译、图形识别、解决高等代数和组合分析等方面的数学问题、定理证明、公式推导乃至日常生活中各种过程的模拟等问题中，主要进行的是判断、比较，而不是算术运算

D、算法设计与分析主要研究对象是非数值问题，当然也包含某些数值问题

2、算法的特征包括_________。

A、有穷性 B、确定性

C、输入和输出 D、能行性或可行性

3、以下描述是有关算法设计的基本步骤：

①问题的陈述 ②算法分析 ③模型的拟制 ④算法的实现

⑤算法的详细设计 ⑥文档的编制，应与其它环节交织在一起

其中正确的顺序是__________。

A、①②③④⑤⑥ B、①③⑤②④⑥

C、②④①③⑤⑥ D、⑥①③⑤②④

4、以下说法正确的是__________。

A、数学归纳法可以证明算法终止性

B、良序原则是证明算法的正确性的有力工具

C、x = 小于或等于x的最大整数（x的低限）

D、x =

1． 按分治策略求解棋盘覆盖问题时，对于如图所示的24×24的特殊棋盘，共需要多少个L型骨

牌；并在棋盘上填写L型骨牌的覆盖情况。

2． 假设有7个物品，给出重量和价值。若这些物品均不能被分割，且背包容量M＝140，使用回

溯方法求解此0-1背包问题。请画出状态空间搜索树。

3． 假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M

＝140，使用贪心算法求解此背包问题。请写出求解策略和求解过程。 W（35,30,50,60,40,10,25）p（10,40,30,50,35,40,30）

4． 在给出的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定

a到b的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。

5． 画出字符表的哈夫曼编码对应的二叉树。

6． 已知Ak?(aij(k))ri*ri?1，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=8，r5=5，r6=20，r7=6，求

矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。

7． 给出城市网络图，售货员要从城市1出发，经过所有城市回到城市1，画出该问题的解空间树，

描述出用优先队列

算法设计与分析

1、(1) 证明：O(f)+O(g)=O(f+g)（7分） (2) 求下列函数的渐近表达式：（6分） ① 3n2+10n; ② 21+1/n;

2、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并简述理由。（15分）

2f(n)?logn;g(n)?logn?5; (1)

2f(n)?logn;g(n)?n; (2)

2f(n)?n;g(n)?logn; (3)

3、试用分治法对数组A[n]实现快速排序。（13分） 4、试用动态规划算法实现最长公共子序列问题。（15分）

5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。（12分）

6、试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：

(1)删除一个字符。 (2)插入一个字符。

(3)将一个字符改为另一个字符。

将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个

考试课程： 班级： 姓名： 学号： 算法分析考试试卷（A卷） ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 课程名称 算法分析 编号 题号 得分 评阅人 一 二 三 四 总分 一、填空题（每小题3分，共30分） 1、一个算法的优劣可以用 空间复杂度 与 时间复杂度 来衡量。 2、这种不断回头寻找目标的方法称为 回溯法 。 3、直接或间接地调用自身的算法称为 递归算法 。 4、? 记号在算法复杂性的表示法中表示 紧致界

&

湖南科技学院二○ 年 学期期末考试

信息与计算科学专业 年级《算法设计与分析》 试题

考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟

1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。

()()log log f n n n g n n ==

2. 算法的时间复杂性为1,

1()8(3/7),

2

n f n f n n n =?=?

+≥?，则算法的时间复杂性的阶

为__________________________。

3. 快速排序算法的性能取决于______________________________。

4. 算法是_______________________________________________________。

5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的

是_________________________。

"

6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。

7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. __

第1章 绪论

习题

1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现？ 5．选择题

（1）在数据结构中，从逻辑上可以把数据结构分成（ ）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构

（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。 A．存储结构 B．存储实现 C．逻辑结构 D．运算实现

（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。 A．数据具有同一特点

B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样

D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（ ）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位

C．数据结构是带有结构的各数据项的集合

D．一些表面上很

行政管理专业社会保障学模拟试卷（05春A卷）

一、单项选择题(每题1分，共10分) 1、美国社会保障的模式是( )。

A、社会保险型 B、强制性储蓄型 C、福利国家型 D、国家保险型

2、我国自1952年对国家机关、事业单位的职工实施的医疗社会保险是（ ） A、劳保医疗 B、公费医疗C、合作医疗 D、自费医疗 3、社会救助是（ ）

A、国家或社会的基本职能和义务 B、社会个人和团体的援助 C、慈善事业的一种 D、社会保险的核心 4、社会保障待遇给付最重要的部分是（ ）

A、现金援助 B、实物援助 C、劳务服务 D、以工代赈 5、一般来说，恩格尔系数在59％以上者，被认为是（ ）。 A、绝对贫困 B、小康水平C、勉强度日 D、富裕 6、社会保障之所以被称为“减震器”，是因为它具有（ ）功能。

A、稳定功能 B、调节功能C、促进发展功能 D、互助功能 7、狭义的社会福利包括（ ）

A、教育事业B、医疗卫生事C、残疾人福利D、城市住房事业 8、最早被采用的社会保障形式是( )。

A、社会保险 B、社会福利 C、社会优抚 D、社会救助 9、（ ）养老保险

第一部分 组织和细胞的损伤与修复

一、是非题`

1．湿性坏疽属液化性坏死，而干性坏疽属凝固性坏死。( ) 2．坏死细胞核的改变为核固缩，核碎裂，核溶解。 ( ) 3．不完全再生早期常以肉芽组织代替坏死组织。 ( ) 4．纤维素样变性实质上就是纤维素样坏死。( )

5．肉芽组织及肉芽肿内均有较多的纤维母细胞。 ( ) 6．脂肪变性有时也可以见于细胞外。（ ）

7．气球样变性是脂肪变性的一种类型，制片过程中脂肪溶解，细胞呈气球样。( )

8．脑组织坏死多属凝固性坏死。( )

9．由于实质细胞数量增多而造成组织器官体积的增大称肥大。( ) 10．干酪样坏死的镜下特征是组织轮廓保持一段时间。（ ） 11．骨再生能力弱，因此骨折后须固定。( )

12．坏疽是组织坏死后继发腐败菌感染而形成的特殊形态。（ ） 13．萎缩的器官其体积均缩小。 ( )

14．变性是指细胞内出现了异常物质或正常物质数量增多。 ( ) 15．凡是组织器官的体积变小都称为萎缩。 ( )

16．气球样变，水变性、脂肪变性和纤维素样变性均属可复性的病变。（ ） 17．结缔组织