软件设计师级模拟试题

软件设计师级上午试题分析与解答

试题1

Shell排序、快速排序、堆排序的稳定性如何 （ 1 ） ；

若要尽可能的完成对实数数组的排序，且要求排序是稳定的，则应选（ 2 ） ；

若用插入排序算法对n个记录进行排序，最佳情况下，对关键字进行的比较次数为

（ 3 ） ；

对于多关键字而言，（ 4 ） 是一种方便而又高效的文件组织方式；

若用冒泡排序对关键字序列{19，16，11，8，5，3}从小到大进行排序，则需要交换

（4） A. 顺序文件 B. 索引文件 C. 散列文件 D. 倒排文件

（5） A. 3 B. 6 C. 15 D. 12

试题1分析：

（1）、（2）快速排序和堆排序是不稳定的,不符合要求；基数排序不能对实数排序；归并排

序是稳定的，且可以对实数排序，所以答案为C。基数排序、归并排序是稳定的排序方法，所

有时间复杂度为O(n²)的简单排序方法也是稳定的；快速排序、堆排序和Shell排序等时间性能

较好的排序方法都是不稳定的。

（4）顺序文件是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，就是顺序文件中

物理记录的顺序和逻辑记录的顺序是一致的。

除了文件本身外，另外建立一张逻辑记录和物理记录之间一一对应的表－索引表。这类包括文

试题1答案：

（1）D （2）C （3）B （4）D （5）C

试题2

算法分析的目的是 （ 6 ） ；

下列数据中哪些是非线性结构（ 7 ） ；

设n为3的倍数，分析以下程序段中第②、③、④语句的语句频度（语句重复执行的次

数）。

①for i:=1 to n do

②if 3*i<=n then

③ for j:=3*i to n do

（8） A. n-1 B. n-2 C. n

2

D. n

（9） A. (n+1)n/6 B. (n-1)n/6 C. n

2

/6 D. (n-1)(n+1)/6

（10）A. (n+1)n/6 B. (n-1)n/6 C. n

2

/6 D. (n-1)(n+1)/6

试题2分析：

{k1,k2,…,kn},当且仅当满足下列关系时，称之为堆。

K i<=k2i 且k i<=k2i＋1

一次用于判断是否结束。

试题2答案：

试题3

语言。

描述所有文法产生的语言。

等。应用式语言，也称为函数式语言，如LISP、ML等。基于规则的语言，也称为逻辑程序设

计语言，如Prolog。

（14）、（15）0型文法又称为短语文法，1型文法又称为上下相关文法，2型文法又成为上

下无关文法，3型文法又称为正规文法。其包含关系是3型文法∈2型文法∈1型文法∈0型文法。

试题3答案：

试题4

已知程序：

program main（input，output）

End

Begin

B[1]:=1;B[2]:=2;I:=1;Q(B[I]);

Writeln(B[1],B[2]);

End.

为传值，则执行程序完毕后B[1]= （ 18 ） 、B[2]= （ 19 ） ；

供选择的答案：

（16） A. 10 B. 12 C. 2 D. NULL

（16）～（19）分析程序，主程序中定义了整型变量I和整型数组B，子程序Q只有一个局部

变量，也就是形式参数x ,另外，其中还引用了两个变量I和B，根据作用域原则，I和B在子程

序中没有定义，顺序查找它的外层程序，即主程序，在主程序中，我们找到了 I和B的定义，因

此，子程序Q中引用的I和B实际上是主程序中所定义的变量。

(1) 当为传地址调用时，主程序中对x的引用能改变实参的值，在函数调用Q(B[I])之前，I的值

为1，B[I]的值为B[1]。进入子程序Q后，由于是传地址调用，将B[1]的地址传递个形式参数

x，然后程序中对x的引用都是通过B[1]的地址访问到B[I]的值。则子程序中的语句：

I:=1;x:=x+2;B[I]:=10;

I:=2;x:=x+2;

实际上相当于

I:=1; B[I]:=10;

(20) C语言为编译型语言，且因为每个类型的大小是静态确定的，所以在编译时就已经计算。

试题4答案：

允许多个用户以交互方式使用计算机的操作系统称为 （ 21 ） ；允许多个用户将多个作

业提交给计算机集中处理的操作系统称为 （ 22 ） ；计算机系统能及时处理过程控制数据并做

出响应的操作系统为 （ 23 ） 。

进程管理是操作系统的核心，如果设计不妥，会出现一种尴尬的局面－死锁。处于死锁

状态的进程不能继续运行又占用了系统资源，从而会阻碍其它进程的运行。对待死锁，一般应

该考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法是属于 （ 24 ） ，

破坏环路等待条件属于 （ 25 ） ，而剥夺资源是 （ 26 ） 的基本方法。

供选择的答案：

了系统资源，从而会阻碍其他进程的运行。对待死锁，一般，应考虑下列四个问题：

全部资源，这破坏了保持和等待条件；又如可以把资源分成若干层次，记为L1，L2，…Lm，

规定一进程获得Li层资源以后，只可再请求获得Lj（j＞i）层资源，这个方法破坏了环路等待

条件。

用户进程的推进加以限制，在进程申请资源时先判断这次分配安全否（安全意味着全部进程都

可完成），安全才实施分配，典型的算法是银行家算法。

的化简判断是不发生了不安全状态。资源请求分配图是一种有向图，表示进程与资源之间的关