1、中级软件设计师上午试题-11 (1)及答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：50，分数：100.00)1.以下关于线性表采用链式存储时删除结点运算的描述，正确的是_。 A.带头结点的线性链表删除结点时，不需要更改头指针 B.带头结点的线性链表删除第一个结点时，需要更改头指针 C.不带头结点的线性链表删除结点时，需要更改头指针 D.不带头结点的线性链表删除第一个结点时，不需要更改头指针（分数：2.00）A.B.C.D.2.给定一个有玎个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动_个元素。 A B C （分数：
2、2.00）A.B.C.D.3.下列叙述中，不正确的是_。 A.线性表在链式存储时，查找第 i个元素的时间与 i的值成正比 B.线性表在链式存储时，查找第 i个元素的时间与 i的值有关 C.线性表在顺序存储时，查找第 i个元素的时间与 i的值成正比 D.线性表在顺序存储时，查找第 i个元素的时间与 i的值无关（分数：2.00）A.B.C.D.4.双向循环链表中，在 p所指向的结点之后插入 s指向的结点，其修改指针的操作是_，其中 p指向的不是最后一个结点。 A.p-next=s;s-prey=p;p-next-prev=s;s-next=p-next; B.p-next-prev=s;p-nex
3、t=s;s-prev=p;s-next=p-next; C.s-prev=p;s-next=p-next;p-next=s;p-next-prev=s; D.s-prev=p;s-next=p-next;p-next-prev=s;p-next=s;（分数：2.00）A.B.C.D.5.若元素 a，b，c，d，e，f 依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是_。 A.dcebfa B.cbdaef C.bcaefd D.afedcb（分数：2.00）A.B.C.D.6.一个栈的入栈元素序列是 1、2、3、4、5，若允许出栈操作可在任意可能的时
4、刻进行，则下面的序列中，不可能出现的出栈序列是_。 A.3、4、2、5、1 B.2、5、4、1、3 C.2、3、1、5、4 D.3、5、4、2、1（分数：2.00）A.B.C.D.7.下面二叉树中一定是完全二叉树的是_。 A.平衡二叉树 B.满二叉树 C.单枝二叉树 D.二叉排序树（分数：2.00）A.B.C.D.8.在一棵度为 4的树 T中，若有 20个度为 4的结点，10 个度为 3的结点，1 个度为 2的结点，10 个度为1的结点，则树 T的叶子结点的个数是_。 A.41 B.82 C.113 D.122（分数：2.00）A.B.C.D.9.已知某二叉树的先序序列为 abcde，它可能的
5、中序序列为_。 A.bdaec B.bcade C.ecadb D.beacd（分数：2.00）A.B.C.D.10.一棵度为 3的树中，有 3度结点 100个，有 2度结点 200个，有叶子结点_个。 A.399 B.400 C.401 D.402（分数：2.00）A.B.C.D.11.在查找算法中，可用平均查找长度(记为 ASL)来衡量一个查找算法的优劣，其定义为：（分数：2.00）A.B.C.D.12.根据使用频率，为 5个字符设计哈夫曼编码不可能是_。 A.111,110,10,01,00 B.000,001,010,011,1 C.001,000,10,01,11 D.110,100
6、,101,11,1（分数：2.00）A.B.C.D.13.二叉树在线索化后，仍不能有效解决的问题是_。 A.先序线索二叉树中求先序后继 B.中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前驱 D.后序线索二又树中求后序后继（分数：2.00）A.B.C.D.14.由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为 2的结点)为_。 A.27 B.38 C.51 D.75（分数：2.00）A.B.C.D.15.若 G是一个具有 36条边的非连通无向图(不含自回路和多重边)，则图 G至少有_个顶点。 A.11 B.1
7、0 C.9 D.8（分数：2.00）A.B.C.D.16.有向图的所有拓扑排序序列有_个。（分数：2.00）A.B.C.D.17.设下三角矩阵(上三角部分的元素值都为 0)A0n,0n如图所示，将该三角矩阵的所有非零元素(即行下标不小于列下标的元素)按行优先压缩存储在容量足够大的数组 M中(下标从 1开始)，则元素 Ai,j(0in，ji)存储在数组 M的_中。 A B C D （分数：2.00）A.B.C.D.18.在内排序的过程中，通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法，会产生不同的排序中间结果。设要将序列Q,H,C,Y,P,A,M,S,R,D,F,X中的关键码按字母的
8、升序重新排列，则_是冒泡排序一趟扫描的结果。 A.F,H,C,D,P,A,M,Q,R,S,Y,X B.P,A,C,S,Q,D,F,X,R,H,M,Y C.A,D,C,R,F,Q,M,S,Y,P,H,X D.H,C,Q,P,A,M,S,R,D,F,X,Y（分数：2.00）A.B.C.D.19.用插入排序和归并排序算法对数组3,1,4,1,5,9,6,5进行从小到大排序，则分别需要进行_次数组元素之间的比较。 A.12，14 B.10，14 C.12，16 D.10，16（分数：2.00）A.B.C.D.20.递归算法的执行过程，一般来说，可先后分成_两个阶段。 A.试探和回归 B.递推和回归 C
9、.试探和返回 D.递推和返回（分数：2.00）A.B.C.D.21.若有数组声明 a03,02,14，设编译时为 a分配的存储空间首地址为 base_a，且每个数组元素占据一个存储单元。当元素以行为序存放(即按 a0,0,1，a0,0,2，a0,0,3，a0,0,4，a0,1,1，a0,1,2，a3,2,4顺序存储)，则数组元素 a2,2,2在其存储空间中相对 base a的偏移量是_。 A.8 B.12 C.33 D.48（分数：2.00）A.B.C.D.22.一个具有 967个结点的完全二叉树，其叶子结点个数为_。 A.483 B.484 C.485 D.486（分数：2.00）A.B.C
10、.D.23.若循环队列以数组 Q0,m-1作为其存储结构，变量 rear表示循环队列中队尾元素的实际位置，其移动按 rear=(rear+1)mod m进行，变量 length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是_。 A.rear-length B.(rear-length+m)mod m C.(1+rear+m-length)mod m D.m-length（分数：2.00）A.B.C.D.24.若一棵哈夫曼树共有 13个顶点，则其叶子结点的个数为_。 A.5 B.6 C.7 D.8（分数：2.00）A.B.C.D.25.若广义表 L=(a,b,c),e)，则 L的
11、长度和深度分别为_。 A.2和 1 B.2和 2 C.4和 2 D.4和 1（分数：2.00）A.B.C.D.26.若二叉树的先序遍历序列为 ABDECF，中序遍历序列为 DBEAFC，则其后序遍历序列为_。 A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA（分数：2.00）A.B.C.D.27.已知一个线性表(38,25,74,63,52,48)，假定采用散列函数 h(key)=key%7计算散列地址，并散列存储在散列表 A0,6中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为_。 A.1.5 B.1.7 C.2.0 D.2.3（分数：2
12、.00）A.B.C.D.28.设某算法的计算时间可用递推关系式 T(n)=2T(n/2)+n表示，则该算法的时间复杂度为_。 A.O(lgn) B.O(nlgn) C.O(n) D.O(n2)（分数：2.00）A.B.C.D.29._算法策略与递归技术的联系最弱。 A.分治 B.动态规划 C.贪心 D.回溯（分数：2.00）A.B.C.D.30.对于具有 n个元素的一个数据序列，若只需得到其中第 k个元素之前的部分排序，最好采用_。 A.直接插入排序 B.希尔排序 C.快速排序 D.堆排序（分数：2.00）A.B.C.D.31.下面关于编程语言的各种说法中，_是不正确的。 A.逻辑型语言适用于
13、书写自动定理证明 B.Smalltalk、C+、Java、C#都是面向对象语言 C.函数型语言适用于人工智能领域 D.由于 C语言程序是由函数构成的，因此它是一种函数型语言（分数：2.00）A.B.C.D.32.序言性注释是指在每个程序或模块开头的一段说明，起辅助理解程序的作用，一般包括：程序的表示、名称和版本号，程序功能描述，接口与界面描述，输入/输出数据说明，开发历史，与运行环境有关的信息等。下列叙述中不属于序言性注释功能的是_。 A.程序对硬件、软件资源的要求 B.重要变量和参数说明 C.嵌入在程序中的 SQL语句 D.程序开发的原作者、审查者、修改者、编程日期等（分数：2.00）A.B
14、.C.D.33.传值调用和引用调用是常用的函数调用方式，下列描述中正确的是_。 A.在传值调用方式下，是将形参的值传给实参 B.在传值调用方式下，形参可以是任意形式的表达式 C.在引用调用方式下，是将实参的地址传给形参 D.在引用调用方式下，实参可以是任意形式的表达式（分数：2.00）A.B.C.D.34.编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等几个阶段，其中，_并不是每种编译器都必需的。 A.语法分析和语义分析 B.中间代码生成和目标代码生成 C.中间代码生成和代码优化 D.代码优化和目标代码生成（分数：2.00）A.B.
15、C.D.35.高级语言程序编译的过程可以分成干个阶段，其中把单词符号分解成句子属于_阶段的工作。 A.词法分析 B.语法分析 C.语义分析 D.代码生成（分数：2.00）A.B.C.D.36.有限自动机可分为确定的有限自动机和不确定的有限自动机。那么确定的有限自动机 A与不确定的有限自动机 B等价，则_。 A.A与 B的状态个数相等 B.A与 B可识别的记号完全相同 C.B能识别的正规集是 A所识别正规集的真子集 D.A能识别的正规集是 B所识别正规集的真子集（分数：2.00）A.B.C.D.37.以下关于编译和解释程序的描述，正确的是_。 A.解释程序不需要进行词法和语法分析，而是直接分析源
16、程序的语义并产生目标代码 B.编译程序不需要进行词法和语法分析，而是直接分析源程序的语义并产生目标代码 C.编译程序不生成源程序的目标代码，而解释程序则产生源程序的目标代码 D.编译程序生成源程序的目标代码，而解释程序则不产生源程序的目标代码（分数：2.00）A.B.C.D.38.某确定性有限自动机(DFA)的状态转换图如图所示，令 d=0|1|2|.|9，则以下字符串中，能被该 DFA接受的是_。（分数：2.00）A.B.C.D.39.关于以下描述错误的是_。 A.高级语言都是用接近人们习惯的自然语言和数学语言作为语言的表达形式 B.计算机只能处理由 0和 1的代码构成的二进制指令或数据 C
17、.每一种高级语言都有它对应的编译程序 D.C语言源程序经过 C语言编译程序编译之后生成一个后缀为 EXE的二进制文件（分数：2.00）A.B.C.D.40.下列关于编译系统对某高级语言进行翻译的叙述中，错误的是_。 A.不同的高级程序语言可以产生同一种中间代码 B.在机器上运行的目标程序完全独立于源程序 C.目标代码生成阶段的工作与目标机器的体系结构相关 D.经过反编译，可以将目标代码还原成源代码（分数：2.00）A.B.C.D.41.对于以下编号为、的正则式，正确的说法是_。(a*b*)*b (a|b)*b (b*|a*)*b A.正则式、等价 B.正则式、等价 C.正则式、等价 D.正则式
18、、，等价（分数：2.00）A.B.C.D.42.集合 L=ambm|m0_。 A.可用正规式“a *b*”表示 B.不能用正规式表示，但可用非确定的有限自动机识别 C.可用正规式“a mbm”表示 D.不能用正规式表示，但可用上下文无关文法表示（分数：2.00）A.B.C.D.43.程序语言的大多数语法现象可用上下文无关文法描述。对于一个上下文无关文法 G=(N，T，P，S)，其中 N是非终结符号的集合，T 是终结符号的集合，P 是产生式集合，S 是开始符号。令集合 V=NT，那么G所描述的语言是_的集合。 A.从 S出发推导出的包含 V和 T中所有符号的串 B.从 S出发推导出的只包含 V中
19、所有符号的串 C.从 S出发推导出的只包含 T中符号的串 D.T中所有符号组成的串（分数：2.00）A.B.C.D.44.某一确定有限自动机(DFA)的状态转换图如图所示，与该 DFA等价的正规式是_。（分数：2.00）A.B.C.D.45.图所示为一确定有限自动机的状态转换图，图中的_是可以合并的状态。（分数：2.00）A.B.C.D.46.已知函数 f1()、f2()的定义如下所示，设调用函数 f1时传递给形参 x的值是 10，若函数调用 f2(a)以引用调用(Call By Reference)方式传递信息和以值调用(Call By Value)方式传递信息，则函数 f1的返回值分别为_
20、。（分数：2.00）A.B.C.D.47.序设计语言一般都提供多种循环语句，有先判断循环条件再执行循环体的 while语句，也有先执行循环体再判断循环条件的 do-while语句，那么下列描述中正确的是_。 A.while循环语句能够实现的功能 do-while不一定能实现 B.循环条件相同时，while 语句的执行效率更高 C.while语句的循环体执行次数比循环条件的判断次数少 1，而 do-while语句的循环体执行次数等于循环条件的判断次数 D.while语句的循环体执行次数比循环条件的判断次数少 1，而 do-while语句的循环体执行次数比循环条件的判断次数多 1（分数：2.00）
21、A.B.C.D.48.某一确定性有限自动机(DFA)的状态转换如图所示，则以下字符串中，不能被该 DFA接受的是_。0010 0001 0101（分数：2.00）A.B.C.D.49.设某程序中定义了全局整型变量 x和 y，且函数 f()的定义如下所示，则在语句“x=3*y+1;”中_。int f(int y) int x;x=3*y+1;return x; A.x和 y均是全局变量 B.x是全局变量、y 是局部变量 C.x是局部变量、y 是局部变量 D.x是局部变量、y 是全局变量（分数：2.00）A.B.C.D.50.下列叙述中正确的是_。 A.算法的时间、空间复杂性与实现该算法所采用的程
22、序设计语言相关 B.面向对象程序设计语言不支持对一个对象的成员变量进行直接访问 C.与汇编语言相比，采用脚本语言编程可获得更高的运行效率 D.面向对象程序设计语言不支持过程化的程序设计，只支持面向对象程序设计（分数：2.00）A.B.C.D.中级软件设计师上午试题-11 (1)答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：50，分数：100.00)1.以下关于线性表采用链式存储时删除结点运算的描述，正确的是_。 A.带头结点的线性链表删除结点时，不需要更改头指针 B.带头结点的线性链表删除第一个结点时，需要更改头指针 C.不带头结点的线性链表删除结点时，需要
23、更改头指针 D.不带头结点的线性链表删除第一个结点时，不需要更改头指针（分数：2.00）A. B.C.D.解析：解析 带头结点的线性链表的头指针指向其头结点，而该头结点是不能被删除的，所以头指针的值不需要更改。不带头结点的线性链表在删除第一个结点后，需要将头指针指向新的第一个结点，而如果删除其他结点，则不需要更改头指针。2.给定一个有玎个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动_个元素。 A B C （分数：2.00）A.B.C. D.解析：解析 题目要求计算进行删除操作时平均移动元素个数，如图所示，若要删除 f，则无须移动任何元素，直接删除即可；
24、若要删除 e，则需要移动 1个元素，即把 f移至 e位置；若要删除 d，则需要移动 2个元素，把 e移至 d位置，再把 f移至 e位置；依此类推，要删除第 1个元素，则需要移动 n-1个元素。 * 由于每个元素被删除的概率是相等的，所以平均需要移动的元素个数为： * 所以此题答案为C。3.下列叙述中，不正确的是_。 A.线性表在链式存储时，查找第 i个元素的时间与 i的值成正比 B.线性表在链式存储时，查找第 i个元素的时间与 i的值有关 C.线性表在顺序存储时，查找第 i个元素的时间与 i的值成正比 D.线性表在顺序存储时，查找第 i个元素的时间与 i的值无关（分数：2.00）A.B.C.
25、D.解析：解析 顺序存储结构的特点是“顺序存储，随机存取”，也就是说，线性表在顺序存储时，查找第 i个元素的时间与 i的值无关。 链式存储结构的特点则是“随机存储，顺序存取”，也就是说，链式存储结构的数据元素可以随机地存储在内存单元中，但访问其中的任意一个数据元素时，都必须从其头指针开始逐个进行访问。4.双向循环链表中，在 p所指向的结点之后插入 s指向的结点，其修改指针的操作是_，其中 p指向的不是最后一个结点。 A.p-next=s;s-prey=p;p-next-prev=s;s-next=p-next; B.p-next-prev=s;p-next=s;s-prev=p;s-next=
26、p-next; C.s-prev=p;s-next=p-next;p-next=s;p-next-prev=s; D.s-prev=p;s-next=p-next;p-next-prev=s;p-next=s;（分数：2.00）A.B.C.D. 解析：解析 其插入方法如图所示。 一般情况下，做此类题的一个捷径是判断代码“p-next=s”后是否还有通过指针“p-next”访问 p以前的直接后继的引用，有则错误。因为一旦执行完代码“p-next=s”，p 的直接后继就更改为 s，此后“p-next”不再是 p以前的直接后继。例如，试题中 A、B和 C选项均在“p-next=s”之后使用了“p-n
27、ext”，所以选项 A、B 和 C错误，根据排除法，选项 D正确。另外，建议考生在编写插入代码时，将“p-next=s”写成插入算法的最后一步。 *5.若元素 a，b，c，d，e，f 依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是_。 A.dcebfa B.cbdaef C.bcaefd D.afedcb（分数：2.00）A.B.C.D. 解析：解析 栈按照后进先出的原则操作数据。 选项 A可以按照 a入栈、b 入栈、c 入栈、d 入栈、d 出栈、c 出栈、e 入栈、e 出栈、b 出栈、f 入栈、f 出栈、a 出栈的方式得到。只有连续 2次出栈操作
28、，符合试题要求。 选项 B可以按照 a入栈、b 入栈、c 入栈、c 出栈、b 出栈、d 入栈、d 出栈、a 出栈、e 入栈、e 出栈、f 入栈、f 出栈的方式得到。只有连续 2次出栈操作，符合试题要求。 选项 C可以按照 a入栈、b 入栈、b 出栈、c 入栈、c 出栈、a 出栈、d 入栈、e 入栈、e 出栈、f 入栈、f 出栈、d 出栈的方式得到。只有连续 2次出栈操作，符合试题要求。 选项 D可以按照 a入栈、a 出栈、b 入栈、c 入栈、d 入栈、e 入栈、f 入栈、f 出栈、e 出栈、d 出栈、c 出栈、b 出栈的方式得到，但这个顺序不符合题目中不允许连续三次进行退栈的要求。6.一个栈的
29、入栈元素序列是 1、2、3、4、5，若允许出栈操作可在任意可能的时刻进行，则下面的序列中，不可能出现的出栈序列是_。 A.3、4、2、5、1 B.2、5、4、1、3 C.2、3、1、5、4 D.3、5、4、2、1（分数：2.00）A.B. C.D.解析：解析 栈的特点是先进后出，按照以下步骤可以很快找到答案： (1)选择出栈序列的第一个元素a，入栈序列中在 a之前的元素必须按照逆序出现在出栈序列中，如果不按照逆序出栈，则此出栈序列不合法，否则执行下一步。 (2)从入栈序列和出栈序列中将元素 a删除，如果删除 a后出栈序列为空，则说明此出栈序列合法，否则回到上一步继续执行。 在本题中，B 选项的
30、第一个出栈元素为 2，在 2之前入栈的元素的为 1，由于只有一个元素，故无论如何将会逆序出栈；在序列中剔除 2，则入栈序列为1、3、4、5，出栈序列变为 5、4、1、3。分析元素 5，在新的入栈序列中，5 之前的元素入栈序列为1、3、4，而出栈序列为 4、1、3，不满足逆序出栈的条件，所以选项 B是不可能出现的出栈序列。7.下面二叉树中一定是完全二叉树的是_。 A.平衡二叉树 B.满二叉树 C.单枝二叉树 D.二叉排序树（分数：2.00）A.B. C.D.解析：解析 满二叉树除最后一层外，每一层上的所有结点都有两个子结点，满二叉树中每一层上的结点的数都达到最大，即在满二叉的第 k层上有 2k-
31、1个结点，否则就不是满二叉树。深度为 m的满二叉树有2m-1个结点。完全二叉树除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。满二叉树也是完全二叉树，反之完全二叉树不一定是满二叉树。平衡二叉树，单支二叉树和二叉排序树既不一定是满二叉树，也不一定是完全二叉树。8.在一棵度为 4的树 T中，若有 20个度为 4的结点，10 个度为 3的结点，1 个度为 2的结点，10 个度为1的结点，则树 T的叶子结点的个数是_。 A.41 B.82 C.113 D.122（分数：2.00）A.B. C.D.解析：解析 在树中，除根结点外，其余所有结点都是由其双亲结点引出的。一个度为
32、 n的结点表示由该结点引出 n个孩子结点，因此，树 T的结点个数为 204+103+12+101+1=123，其中最后的 1为根结点，则叶子结点数为 123-(20+10+1+10)=82个。9.已知某二叉树的先序序列为 abcde，它可能的中序序列为_。 A.bdaec B.bcade C.ecadb D.beacd（分数：2.00）A.B. C.D.解析：解析 二叉树的先序序列可以分为连续的 3个部分：根结点、左子树部分、右子树部分。中序遍历也可以分为 3个部分：左子树部分、根结点、右子树部分。题目给出的先序序列为 abcde，可知 a为根结点。 在 A选项中，给出的中序序列 bdaec表
33、示 bd是左子树部分，ec 是右子树部分，这与先序序列abcde矛盾(在先序序列中，bd 不在一起，ec 也不在一起)，因此，不是可能的中序序列。 在 B选项中，给出的序列 bcade表示 bc是左子树部分，de 是右子树部分，这与先序序列 abcde不矛盾，是可能的中序序列。对左子树部分而言，在先序序列中的顺序是 bc，说明 b是根结点；在中序序列中的顺序也是 bc，说明 c是 b的右孩子。对右子树而言，在先序序列中的顺序是 de，说明 d是根结点；在中序序列中的顺序也是 de，说明 e是 d的右孩子。因此，B 选项符合要求。 在 C选项中，给出的中序序列 ecadb表示 ec是左子树部分，
34、db 是右子树部分，这与先序序列 abcde矛盾(在先序序列中，ec 不在一起，db 也不在一起)，因此不是可能的中序序列。 在 D选项中，给出的中序序列 beacd表示 be是左子树部分，cd 是右子树部分，这与先序序列 abcde矛盾(在先序序列中，be 不在一起)，因此，不是可能的中序序列。10.一棵度为 3的树中，有 3度结点 100个，有 2度结点 200个，有叶子结点_个。 A.399 B.400 C.401 D.402（分数：2.00）A.B.C. D.解析：解析 先推导这种题目的一般解法得到结论，然后再将已知条件代入。首先，统计树中结点的总数 n。设树中度为 0的结点个数为 n
35、0，度为 1的结点个数为 n1，度为 2的结点个数为 n2，度为 3的结点个数为 n3，则树的结点总数为 n=n0+n1+n2+3。因为树的根结点没有双亲结点，进入它的边数为 0，其他每个结点都有一个且仅有一个双亲结点，进入它们的边数各为 1，故树中总的边数为e=n-1=n0+n1+n2+n3-1。又由于每个度为 0的结点发出 0条边，每个度为 1的结点发出 1条边，每个度为 2的结点发出 2条边，每个度为 3的结点发出 3条边，因此，总的边数可以表示为 e=n1+2*n2+3*n3。将 e的等式等同起来，有 n0+n1+n2+n3-1=n1+2*n2+3*n3，则有 n0=n2+2*n3+1
36、。在本题中，由题意可知，n 2=200，n 3=100，则 n0=401。11.在查找算法中，可用平均查找长度(记为 ASL)来衡量一个查找算法的优劣，其定义为：（分数：2.00）A.B. C.D.解析：解析 顺序查找的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值 k相比较。若当前扫描到的结点关键字与 k相等，则查找成功；若扫描结束后，仍未找到关键字等于 k的结点，则查找失败。顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。成功的顺序查找的平均查找长度如下：*在等概率情况下，p i=1/n(1in)，故成功的平均查找长度为(n+2+1)/
37、n=(n+1)/2，即查找成功时的平均比较次数约为表长的一半。若 k值不在表中，则需进行 n+1次比较之后才能确定查找失败。查找时间复杂度为 O(n)。若事先知道表中各结点的查找概率不相等，以及它们的分布情况，则应将表中结点按查找概率由小到大的顺序存放，以便提高顺序查找的效率。顺序查找的优点是算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。其缺点是查找效率低，因此，当 n较大时不宜采用顺序查找。二分法查找又称折半查找，是一种效率较高的查找方法。二分法查找要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。二
38、分法查找的基本思想是(设 Rlow,.,high是当前的查找区间)：(1)确定该区间的中点位置：mid=(low+high)/2。(2)将待查的 k值与 Rmid.key比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下：若 Rmid.keyk，则由表的有序性可知 Rmid,.,n.key均大于 k，因此若表中存在关键字等于 k的结点，则该结点必定是在位置 mid左边的子表 Rlow,.,mid-1中。因此，新的查找区间是左子表Rlow,.,high，其中 high=mid-1。若 Rmid.keyk，则要查找的 k必在 mid的右子表 Rmid+1,.,
39、high中，即新的查找区间是右子表Rlow,.,high，其中 low=mid+1。若尺mid.key=k，则查找成功，算法结束。(3)下一次查找针对新的查找区间进行，重复步骤(1)和(2)。(4)在查找过程中，low 逐步增加，而 high逐步减少。如果 highlow，则查找失败，算法结束。因此，从初始的查找区间 R1,.,n开始，每经过一次与当前查找区间中点位置上结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。重复这一过程，直至找到关键字为 k的结点，或直至当前的查找区间为空(即查找失败)时为止。查找的时间复杂度为：O(log 2n)。12.根据使用频率，为 5
40、个字符设计哈夫曼编码不可能是_。 A.111,110,10,01,00 B.000,001,010,011,1 C.001,000,10,01,11 D.110,100,101,11,1（分数：2.00）A.B.C.D. 解析：解析 哈夫曼编码属于前缀编码，根据前缀编码的定义，任一字符的编码都不是另一字符编码的前缀。而在选项 D中，1 是前面 4个字符的前缀，明显违反了这一原则，所以不属于哈夫曼编码。13.二叉树在线索化后，仍不能有效解决的问题是_。 A.先序线索二叉树中求先序后继 B.中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前驱 D.后序线索二又树中求后序后继（分数：2.00）
41、A.B.C.D. 解析：解析 在中序线索二叉树中，查找结点 P的中序后继分为以下两种情况。 (1)若结点 P的右子树为空，则直接得到中序后继。 (2)若结点 P的右子树非空，则中序后继是 P的右子树中最左下的结点。 在中序线索二叉树中，查找结点 P的中序前驱也有两种情况。 (1)若结点 P的左子树为空，则直接得到中序前驱。 (2)若结点 P的左子树非空，则中序前驱是 P的左子树中最右下的结点。 因此，在中序线索二叉树中，查找中序前驱和中序后继都可以有效解决。 在先序线索二叉树中，查找结点先序后继很简单，仅从 P出发就可以找到，但是找其先序前驱必须要知道 P的双亲结点。 在后序线索二叉树中，仅从
42、 P出发就可以找到结点后序前驱，但是找其后序后继也必须要知道 P的双亲结点。14.由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为 2的结点)为_。 A.27 B.38 C.51 D.75（分数：2.00）A.B.C.D. 解析：解析 平衡二叉树的构造过程如图所示。 * 根据题中要求，首次出现最小不平衡子树的根就是75。15.若 G是一个具有 36条边的非连通无向图(不含自回路和多重边)，则图 G至少有_个顶点。 A.11 B.10 C.9 D.8（分数：2.00）A.B. C.D.解析：解析 因为 G为非连通图，所
43、以 G中至少含有两个连通子图，而且该图不含有回路和多重边。题目问的是至少有多少个顶点，因此一个连通图可看成是只有 1个顶点，另一个连通图可看成是一个完全图(因为完全图在最少顶点的情况下能得到的边数最多)，这样，该问题就转化为“36 条边的完全图有多少个顶点”，因为具有 n个顶点的无向完全图的边的条数为 n(n-1)/2，可以算出 n=9满足条件。再加上另一个连通图(只有一个点)，则图 G至少有 10个顶点。16.有向图的所有拓扑排序序列有_个。（分数：2.00）A. B.C.D.解析：解析 在图中，其拓扑排序序列有如下规定： A 必须是序列的第一个元素，E 必须是序列的最后一个元素，D 必须是
44、序列的倒数第二个元素。即序列形如 A*DE，其中“*”为 B或 C，所以共两种拓扑排序序列。17.设下三角矩阵(上三角部分的元素值都为 0)A0n,0n如图所示，将该三角矩阵的所有非零元素(即行下标不小于列下标的元素)按行优先压缩存储在容量足够大的数组 M中(下标从 1开始)，则元素 Ai,j(0in，ji)存储在数组 M的_中。 A B C D （分数：2.00）A. B.C.D.解析：解析 对于这个题目，可以这样理解，题目要求按行优先，其含义就是存储第一行后，开始存储第二行，然后再存储第三行的非 0元素，依次类推。这样可以发现了一个规律，第 1行只有一个元素，第二行 2个元素，第三行 3个
45、元素，第 n行 n个元素。 显然，这个规律是一个递增数列。那么元素 Ai,j是第几行第几列就变得明显了。由于下标是从 0开始的(这个要特别注意)，那么下标为 i的应该就是第i+1行，因此在存储下标为 i的这行之前，应该存放了 i行元素，其中第 i行的元素个数为 i个，那么在存放第 i+1行之前，应该存放的元素个数总和为 i(i+1)/2,。那么当存放到第 i+1行时，在存放下标为 j的元素前，同样的道理应该存放了 j个元素，因此在存放元素 Ai,j之前，总共存放了的元素个数总和为 i(i+1)/2+j，因此元素 Ai,j应该是第 i(i+1)/2+j+1个要存放的元素，由于存放的数组 M是从下
46、标为1开始的。因此元素 Ai,j存储在数组 M的 Mi(i+1)/2+j+1中。18.在内排序的过程中，通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法，会产生不同的排序中间结果。设要将序列Q,H,C,Y,P,A,M,S,R,D,F,X中的关键码按字母的升序重新排列，则_是冒泡排序一趟扫描的结果。 A.F,H,C,D,P,A,M,Q,R,S,Y,X B.P,A,C,S,Q,D,F,X,R,H,M,Y C.A,D,C,R,F,Q,M,S,Y,P,H,X D.H,C,Q,P,A,M,S,R,D,F,X,Y（分数：2.00）A.B.C.D. 解析：解析 此题比较容易，但从历年试题看来，考的几率是比较高的，这里只将一些考生有疑问的地方提出来讲一讲。以前有考生提出疑问：“冒泡排序一趟扫描的结果标准答案为：H，C，Q，P，A，M，S，R，D，F，X，Y。如果按照冒泡排序的基本思想是先比较 An-1和 An-2一直到A0，那么冒泡排序一趟扫描的结果得到应该是：A，Q，H，C，Y，P，
