中级软件设计师题库_计算机软件水平考试题库

单项选择题

某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为，若问题的规模增加了16倍，则运行时间增加倍。

A.O(n)
B.O(nlgn)
C.O(n²)
D.O(n²lgn)

单项选择题

某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为，若问题的规模增加了16倍，则运行时间增加倍。

A．16
B．64
C．256
D．1024

单项选择题

Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一个顶点开始，每次从剩余的顶点中加入一个顶点，该顶点与当前的生成树中的顶点的连边权重最小，直到得到一颗最小生成树；Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点中选择权重最小的边加入，直到得到一棵最小生成树，这两个算法都采用了设计策略，且。

A．分治
B．贪心
C．动态规划
D．回溯

单项选择题

Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一个顶点开始，每次从剩余的顶点中加入一个顶点，该顶点与当前的生成树中的顶点的连边权重最小，直到得到一颗最小生成树；Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点中选择权重最小的边加入，直到得到一棵最小生成树，这两个算法都采用了设计策略，且。

A．若网较稠密，则Prim算法更好
B．两个算法得到的最小生成树是一样的
C．Prim算法比Kruscal算法效率更高
D．Kruscal算法比Prim算法效率更高

单项选择题

给定n个整数构成的数组A={a ₁ ，a ₂ ，…，a _n }和整数x，判断A中是否存在两个元素a _i 和a _j ，使的a _i +a _j =x。为了求解问题，首先用归并排序算法对数组A进行从大到小排序；然后判断是否存在a _i +a _j =x，具体的方法如下列伪代码所示。则求解该问题时排序算法应用了算法设计策略，整个算法的时间复杂度为。
…
i=1;j=n
While i＜j
If a _i +a _j =x return true
Else if a _i +a _j ＞x
J--;
Else
I++;
Return false;

A．分治
B．贪心
C．动态规划
D．回溯

单项选择题

给定n个整数构成的数组A={a ₁ ，a ₂ ，…，a _n }和整数x，判断A中是否存在两个元素a _i 和a _j ，使的a _i +a _j =x。为了求解问题，首先用归并排序算法对数组A进行从大到小排序；然后判断是否存在a _i +a _j =x，具体的方法如下列伪代码所示。则求解该问题时排序算法应用了算法设计策略，整个算法的时间复杂度为。
…
i=1;j=n
While i＜j
If a _i +a _j =x return true
Else if a _i +a _j ＞x
J--;
Else
I++;
Return false;

A.O(n)
B.O(nlgn)
C.O(n²)
D.O(nlog₂n)

单项选择题

在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用算法设计策略；若定义问题的解空间，以深度优先的方式搜索解空间，则采用算法设计策略。

A．分治
B．动态规划
C．贪心
D．回溯

单项选择题

在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用算法设计策略；若定义问题的解空间，以深度优先的方式搜索解空间，则采用算法设计策略。

A．动态规划
B．贪心
C．回溯
D．分支限界

单项选择题

哈夫曼编码将频繁出现的字符采用短编码，出现频率较低的字符采用长编码。具体的操作过程为：ⅰ)以每个字符的出现频率作为关键字构建最小优先级队列；ⅱ)取出关键字最小的两个节点生成子树，根节点的关键字为孩子节点关键字之和，并将根节点插入到最小优先级队列中，直至得到一棵最优编码树。哈夫曼编码方案是基于策略的，用该方案对包含a到f六个字符的文件进行编码，文件包含100000个字符，每个字符的出现频率(用百分比表示)如下表所示，则与固定长度编码相比，该编码方案节省了存储空间。

字符 a b c d e f

出现频率 18 32 4 8 12 26

A．分治
B．贪心
C．动态规划
D．回溯

单项选择题

哈夫曼编码将频繁出现的字符采用短编码，出现频率较低的字符采用长编码。具体的操作过程为：ⅰ)以每个字符的出现频率作为关键字构建最小优先级队列；ⅱ)取出关键字最小的两个节点生成子树，根节点的关键字为孩子节点关键字之和，并将根节点插入到最小优先级队列中，直至得到一棵最优编码树。哈夫曼编码方案是基于策略的，用该方案对包含a到f六个字符的文件进行编码，文件包含100000个字符，每个字符的出现频率(用百分比表示)如下表所示，则与固定长度编码相比，该编码方案节省了存储空间。

字符 a b c d e f

出现频率 18 32 4 8 12 26

A．21%
B．27%
C．18%
D．36%

单项选择题

以下关于渐近符号的表示中，不正确的是______。

A.n²=O(n²)
B.n=O(n²)
C.n²=O(n)
D.n²=O(n³)

单项选择题

考虑下述背包问题的实例。有5件物品，背包容量为100，每件物品的价值和重量如下图所示，并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中，则采用了设计策略。考虑0/1背包问题(每件物品或者全部装入背包或者不装入背包)和部分背包问题(物品可以部分装入背包)，求解该实例得到的最大价值分别为。

A．分治
B．贪心
C．动态规划
D．回溯

单项选择题

考虑下述背包问题的实例。有5件物品，背包容量为100，每件物品的价值和重量如下图所示，并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中，则采用了设计策略。考虑0/1背包问题(每件物品或者全部装入背包或者不装入背包)和部分背包问题(物品可以部分装入背包)，求解该实例得到的最大价值分别为。

A．605和630
B．605和605
C．430和630
D．630和430

单项选择题

某货车运输公司有一个中央仓库和n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点i和j之间运输货物存在费用C _ij ，为求解旅行费用总和最小的运输路径，设计如下算法：首先选择离中央仓库最近的运输目的地1，然后选择离运输目的地1最近的运输目的地2……每次在访问过的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中央仓库。则该算法采用了算法设计策略，其时间复杂度为。

A．分治
B．动态规划
C．贪心
D．回溯

单项选择题

现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下，则该算法的时间和空间复杂度为______。
i=0;j=n-1
while i＜j do
while A[i]＜0 do
i=i+1;
while A[j]＞0 do
j=j-1;
if i＜j do
交换A[i]和A[j]

A．O(n)和O(n)
B．O(1)和O(n)
C．O(n)和O(1)
D．O(1)和O(1)

单项选择题

某货车运输公司有一个中央仓库和n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点i和j之间运输货物存在费用C _ij ，为求解旅行费用总和最小的运输路径，设计如下算法：首先选择离中央仓库最近的运输目的地1，然后选择离运输目的地1最近的运输目的地2……每次在访问过的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中央仓库。则该算法采用了算法设计策略，其时间复杂度为。

A.O(n²)
B.O(n)
C.O(nlgn)
D.O(1)

单项选择题

迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于______策略的算法。

A．分治
B．动态规划
C．贪心
D．回溯

单项选择题

在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下：任意取一个元素r，用划分操作确定其在数组中的位置，假设元素r为第k小的数。若i等于k，则返回该元素值；若i小于k，则在划分的前半部分递归进行划分操作查找第i小的数；否则在划分的后半部分递归进行划分操作查找第k-i小的数。该算法是一种基于______策略的算法。

A．分治
B．动态规划
C．贪心
D．回溯

单项选择题

用动态规划策略求解矩阵连乘问题M1×M2×M3×M4，其中M ₁ (20×5)、M ₂ (5×35)、M ₃ (35×4)和M ₄ (4×25)，则最优的计算次序为______。

A．((M1×M2)×M3)×M
B．(M1×M2)×(M3×M4)
C．(M1×(M2×M3))×M4
D．M1×(M2×(M3×M4))

单项选择题

______不能保证求得0-1背包问题的最优解。

A．分支限界法
B．贪心算法
C．回溯法
D．动态规划策略

单项选择题

类______之间存在着一般和特殊的关系。

A．汽车与轮船
B．交通工具与飞机
C．轮船与飞机
D．汽车与飞机

单项选择题

多态分为参数多态、包含多态、过载多态和强制多态共4种不同形式，其中______多态在许多语言中都存在，最常见的例子就是子类型化。

A．参数
B．包含
C．过载
D．强制

单项选择题

在面向对象程序设计语言中，对象之间通过方式进行通信。以下关于好的面向对象程序设计语言的叙述中，不正确的是。

A．消息传递
B．继承
C．引用
D．多态

单项选择题

在面向对象程序设计语言中，对象之间通过方式进行通信。以下关于好的面向对象程序设计语言的叙述中，不正确的是。

A．应该支持被封装的对象
B．应该支持类写实例的概念
C．应该支持通过指针进行引用
D．应该支持继承和多态

单项选择题

______是一个类与它的一个或多个细化类之间的关系，即一般与特殊的关系。

A．泛化
B．关联
C．聚集
D．组合

单项选择题

在某些程序设计语言中，在运行过程中当一个对象发送消息请求服务时，根据接收对象的具体情况将请求的操作与实现的方法进行连接，称为______。

A．静态绑定
B．通用绑定
C．动态绑定
D．过载绑定

单项选择题

在面向对象技术中，不同的对象在收到同一消息时可以产生完全不同的结果，这一现象称为，它由机制来支持。利用类的层次关系，把具有通用功能的消息存放在高层次，而实现这一功能的行为放在较低层次，在这些低层次上生成的对象能够给通用消息以不同的响应。

A．绑定
B．继承
C．消息
D．多态

单项选择题

在面向对象技术中，不同的对象在收到同一消息时可以产生完全不同的结果，这一现象称为，它由机制来支持。利用类的层次关系，把具有通用功能的消息存放在高层次，而实现这一功能的行为放在较低层次，在这些低层次上生成的对象能够给通用消息以不同的响应。

A．绑定
B．继承
C．消息
D．多态

单项选择题

在多态的几种不同形式中，______多态是一种特定的多态，指同一个名字在不同上下文中可代表不同的含义。

A．参数
B．包含
C．过载
D．强制

单项选择题

继承是父类和子类之间共享数据和方法的机制。以下关于继承的叙述中，不正确的是。有关下图中doIt()方法的叙述中，正确的是。

A．一个父类可以有多个子类，这些子类都是父类的特例
B．父类描述了这些子类的公共属性和操作
C．子类可以继承它的父类(或祖先类)中的属性和操作而不必自己定义
D．子类中可以定义自己的新操作而不能定义和父类同名的操作

单项选择题

继承是父类和子类之间共享数据和方法的机制。以下关于继承的叙述中，不正确的是。有关下图中doIt()方法的叙述中，正确的是。

A．doIt()必须由Thing3实现，同时可能由Thing4实现
B．doIt()必须由Thing5实现
C．doIt()必须由Thing2、Thing3、Thing4和Thing5实现
D．doIt()已经由Thing1实现，因此无需其他类实现

单项选择题

在面向对象技术中，定义了超类和子类之间的关系，子类中以更具体的方式实现从父类继承来的方法称为，不同类的对象通过__相互通信。

A．覆盖
B．继承
C．消息
D．多态

单项选择题

在面向对象技术中，定义了超类和子类之间的关系，子类中以更具体的方式实现从父类继承来的方法称为，不同类的对象通过__相互通信。

A．覆盖
B．继承
C．消息
D．多态

单项选择题

在面向对象技术中，定义了超类和子类之间的关系，子类中以更具体的方式实现从父类继承来的方法称为，不同类的对象通过__相互通信。

A．覆盖
B．继承
C．消息
D．多态

单项选择题

在面向对象技术中，对象具有以下特性：______。
①清晰的边界 ②良好定义的行为 ③确定的位置和数量 ④可扩展性

A．②④
B．①②③④
C．①②④
D．①②

单项选择题

在面向对象技术中，说明一个对象具有多种形态，定义超类与子类之间的关系。

A．继承
B．组合
C．封装
D．多态

单项选择题

在面向对象技术中，说明一个对象具有多种形态，定义超类与子类之间的关系。

A．继承
B．组合
C．封装
D．多态

单项选择题

以下关于封装在软件复用中所充当的角色的叙述，正确的是______。

A．封装使得其他开发人员不需要知道一个软件组织内部是如何工作
B．封装使得软件组织更有效地工作
C．封装使得软件开发人员不需要编制开发文档
D．封装使得软件组件开发更加容易

单项选择题

在有些程序设计语言中，过程调用和响应调用需执行的代码的绑定直到运行时才进行，这种绑定称为______。

A．静态绑定
B．动态绑定
C．过载绑定
D．强制绑定

单项选择题

在面向对象软件开发中，封装是一种______技术，其目的是使对象的使用者和生产者分离。

A．接口管理
B．信息隐藏
C．多态
D．聚合

单项选择题

一个类是。在定义类时，将属性声明为private的目的是。

A．一组对象的封装
B．表示一组对象的层次关系
C．一组对象的实例
D．一组对象的抽象定义

单项选择题

面向对象分析的第一步是______

A．定义服务
B．确定附加的系统约束
C．确定问题域
D．定义类和对象

单项选择题

一个类是。在定义类时，将属性声明为private的目的是。

A．实现数据隐藏，以免意外更改
B．操作符重载
C．实现属性值不可更改
D．实现属性值对类的所有对象共享

单项选择题

下列关于一个类的静态成员的描述中，不正确的是______。

A．类的静态方法只能访问该类的静态数据成员
B．静态数据成员可被该类的所有方法访问
C．该类的对象共享其静态数据成员的值
D．该类的静态数据成员的值不可修改

单项选择题

属于面向对象、解释型程序设计语言的是______。

A．XML
B．Python
C．Prolog
D．C++

单项选择题

以下程序设计语言中，______更适合用来进行动态网页处理。

A．HTML
B．LISP
C．PHP
D．Java/C++

单项选择题

某程序设计语言规定在源程序中的数据都必须具有类型，然而，______并不是做出此规定的理由。

A．为数据合理分配存储单元
B．可以定义和使用动态数据结构
C．可以规定数据对象的取值范围及能够进行的运算
D．对参与表达式求值的数据对象可以进行合法性检查

单项选择题

采用面向对象开发方法时，对象是系统运行的基本实体。以下关于对象的叙述中，正确的是______。

A．对象只能包括数据(属性)
B．对象只能包括操作(行为)
C．对象一定有相同的属性和行为
D．对象通常由对象名、属性和操作三个部分组成

单项选择题

UML中有4种事物：结构事物、行为事物、分组事物和注释事物。类、接口、构建属于事物；依附于一个元素或一组元素之上，对其进行约束或解释的简单符号为事物。

A．结构
B．行为
C．分组
D．注释

单项选择题

UML中有4种事物：结构事物、行为事物、分组事物和注释事物。类、接口、构建属于事物；依附于一个元素或一组元素之上，对其进行约束或解释的简单符号为事物。

A．结构
B．行为
C．分组
D．注释

在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用______算法设计策略；若定义问题的解空间，以深度优先的方式搜索解空间，则采用______算法设计策略。

你可能感兴趣的试题

某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为______，若问题的规模增加了16倍，则运行时间增加______倍。

某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为______，若问题的规模增加了16倍，则运行时间增加______倍。

在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用______算法设计策略；若定义问题的解空间，以深度优先的方式搜索解空间，则采用______算法设计策略。

在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用______算法设计策略；若定义问题的解空间，以深度优先的方式搜索解空间，则采用______算法设计策略。

以下关于渐近符号的表示中，不正确的是______。

迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于______策略的算法。

要在8×8的棋盘上摆放8个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能再同一行、同一列和相同的对角线上，则一般采用______来实现。

分治算法设计技术______。

某算法的时间复杂度可用递归式 表示，若由Θ表示，则正确的是______。

设算法A的时间复杂度可用递归式表示，算法B的时间复杂度可用递归式表示，若要使得算法B渐进地快于算法A，则a的最大整数为______。

用动态规划策略求解矩阵连乘问题M1×M2×M3×M4，其中M 1 (20×5)、M 2 (5×35)、M 3 (35×4)和M 4 (4×25)，则最优的计算次序为______。

______不能保证求得0-1背包问题的最优解。

类______之间存在着一般和特殊的关系。

多态分为参数多态、包含多态、过载多态和强制多态共4种不同形式，其中______多态在许多语言中都存在，最常见的例子就是子类型化。

在面向对象程序设计语言中，对象之间通过______方式进行通信。以下关于好的面向对象程序设计语言的叙述中，不正确的是______。

在面向对象程序设计语言中，对象之间通过______方式进行通信。以下关于好的面向对象程序设计语言的叙述中，不正确的是______。

______是一个类与它的一个或多个细化类之间的关系，即一般与特殊的关系。

在某些程序设计语言中，在运行过程中当一个对象发送消息请求服务时，根据接收对象的具体情况将请求的操作与实现的方法进行连接，称为______。

在多态的几种不同形式中，______多态是一种特定的多态，指同一个名字在不同上下文中可代表不同的含义。

继承是父类和子类之间共享数据和方法的机制。以下关于继承的叙述中，不正确的是______。有关下图中doIt()方法的叙述中，正确的是______。

继承是父类和子类之间共享数据和方法的机制。以下关于继承的叙述中，不正确的是______。有关下图中doIt()方法的叙述中，正确的是______。

在面向对象技术中，______定义了超类和子类之间的关系，子类中以更具体的方式实现从父类继承来的方法称为______，不同类的对象通过______相互通信。

在面向对象技术中，______定义了超类和子类之间的关系，子类中以更具体的方式实现从父类继承来的方法称为______，不同类的对象通过______相互通信。

在面向对象技术中，______定义了超类和子类之间的关系，子类中以更具体的方式实现从父类继承来的方法称为______，不同类的对象通过______相互通信。

在面向对象技术中，对象具有以下特性：______。 ①清晰的边界 ②良好定义的行为 ③确定的位置和数量 ④可扩展性

在面向对象技术中，______说明一个对象具有多种形态，______定义超类与子类之间的关系。

在面向对象技术中，______说明一个对象具有多种形态，______定义超类与子类之间的关系。

以下关于封装在软件复用中所充当的角色的叙述，正确的是______。

在有些程序设计语言中，过程调用和响应调用需执行的代码的绑定直到运行时才进行，这种绑定称为______。

在面向对象软件开发中，封装是一种______技术，其目的是使对象的使用者和生产者分离。

一个类是______。在定义类时，将属性声明为private的目的是______。

面向对象分析的第一步是______

一个类是______。在定义类时，将属性声明为private的目的是______。

下列关于一个类的静态成员的描述中，不正确的是______。

属于面向对象、解释型程序设计语言的是______。

以下程序设计语言中，______更适合用来进行动态网页处理。

某程序设计语言规定在源程序中的数据都必须具有类型，然而，______并不是做出此规定的理由。

采用面向对象开发方法时，对象是系统运行的基本实体。以下关于对象的叙述中，正确的是______。

UML中有4种事物：结构事物、行为事物、分组事物和注释事物。类、接口、构建属于______事物；依附于一个元素或一组元素之上，对其进行约束或解释的简单符号为______事物。

UML中有4种事物：结构事物、行为事物、分组事物和注释事物。类、接口、构建属于______事物；依附于一个元素或一组元素之上，对其进行约束或解释的简单符号为______事物。

在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用算法设计策略；若定义问题的解空间，以深度优先的方式搜索解空间，则采用算法设计策略。

某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为，若问题的规模增加了16倍，则运行时间增加倍。

某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为，若问题的规模增加了16倍，则运行时间增加倍。

在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用算法设计策略；若定义问题的解空间，以深度优先的方式搜索解空间，则采用算法设计策略。

在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用算法设计策略；若定义问题的解空间，以深度优先的方式搜索解空间，则采用算法设计策略。

某算法的时间复杂度可用递归式
表示，若由Θ表示，则正确的是______。

设算法A的时间复杂度可用递归式
表示，算法B的时间复杂度可用递归式
表示，若要使得算法B渐进地快于算法A，则a的最大整数为______。

用动态规划策略求解矩阵连乘问题M1×M2×M3×M4，其中M ₁ (20×5)、M ₂ (5×35)、M ₃ (35×4)和M ₄ (4×25)，则最优的计算次序为______。

在面向对象程序设计语言中，对象之间通过方式进行通信。以下关于好的面向对象程序设计语言的叙述中，不正确的是。

在面向对象程序设计语言中，对象之间通过方式进行通信。以下关于好的面向对象程序设计语言的叙述中，不正确的是。

继承是父类和子类之间共享数据和方法的机制。以下关于继承的叙述中，不正确的是。有关下图中doIt()方法的叙述中，正确的是。

继承是父类和子类之间共享数据和方法的机制。以下关于继承的叙述中，不正确的是。有关下图中doIt()方法的叙述中，正确的是。

在面向对象技术中，定义了超类和子类之间的关系，子类中以更具体的方式实现从父类继承来的方法称为，不同类的对象通过__相互通信。

在面向对象技术中，定义了超类和子类之间的关系，子类中以更具体的方式实现从父类继承来的方法称为，不同类的对象通过__相互通信。

在面向对象技术中，定义了超类和子类之间的关系，子类中以更具体的方式实现从父类继承来的方法称为，不同类的对象通过__相互通信。

在面向对象技术中，对象具有以下特性：______。
①清晰的边界 ②良好定义的行为 ③确定的位置和数量 ④可扩展性

在面向对象技术中，说明一个对象具有多种形态，定义超类与子类之间的关系。

在面向对象技术中，说明一个对象具有多种形态，定义超类与子类之间的关系。

一个类是。在定义类时，将属性声明为private的目的是。

一个类是。在定义类时，将属性声明为private的目的是。

UML中有4种事物：结构事物、行为事物、分组事物和注释事物。类、接口、构建属于事物；依附于一个元素或一组元素之上，对其进行约束或解释的简单符号为事物。

UML中有4种事物：结构事物、行为事物、分组事物和注释事物。类、接口、构建属于事物；依附于一个元素或一组元素之上，对其进行约束或解释的简单符号为事物。