[计算机类试卷]软件水平考试（初级）程序员上午（基础知识）章节练习试卷3及答案与解析.doc

《[计算机类试卷]软件水平考试（初级）程序员上午（基础知识）章节练习试卷3及答案与解析.doc》由会员分享，可在线阅读，更多相关《[计算机类试卷]软件水平考试（初级）程序员上午（基础知识）章节练习试卷3及答案与解析.doc（40页珍藏版）》请在麦多课文档分享上搜索。

1、软件水平考试（初级）程序员上午（基础知识）章节练习试卷 3及答案与解析 1 下面程序段的时间复杂度是 (9)。 for(i=0， k=0； n； 1+) k+=Aij； for(j=1； j m； j+) Aij=1 （ A） O(n) （ B） O(m+n+1) （ C） O(m+n) （ D） O(m*n) 2 在单链表中，指针 P指向元素为 x的结点，语句 (10)现 “删除 x的后继 ” （ A） p=pmext ； （ B） pnext=pnextnext ； （ C） pnext=p ； （ D） p=pnextnext ； 3 某单循环链表头指针为 head且表长大于 1，指针

2、p指向表中某个结点，若pnextnext= head，则 (11)。 （ A） p指向头结点 （ B） p指向尾结点 （ C） *p的直接后继是头结点 （ D） *P的直接后继是尾结点 4 判定 “带头结点的链队列为空 ”的条件是 (12)。 （ A） Q.front= =NULL （ B） Q.rear= =NULL （ C） Q.front =Q.rear （ D） Q.front!=Q.rear 5 在一个单链表 HL中，若要向表头 插入一个由指针 P指向的结点，则执行 (13)。 （ A） HL=p； pnext=HL ； （ B） pnext=HL ； HL=p； （ C） pnex

3、t=HL ； p=HL； （ D） Pnext=HLnext ； HLnext=p ； 6 n个顶点的强连通图中至少含有 (14)。 （ A） n-1条的向边 （ B） n条有向边 （ C） n(n-1)/2条有向边 （ D） n(n-1)条有向边 7 广义表 A=(a， (h)， ()， (c， (d)， e)的深度为 (15)。 （ A） 4 （ B） 5 （ C） 6 （ D） 7 8 一棵含 28个结点的：二叉树的高度至少为 (16)。 （ A） 3 （ B） 4 （ C） 5 （ D） 6 9 已知二叉树的中序序列为 DBEACPC，先序序列为 ABDECPC，则后序序列为(17)。

4、 （ A） DEBACFC （ B） DEFCBCA （ C） DEBCFCA （ D） DEBCFCA 10 从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为 (18)。 （ A） O(1) （ B） O(n) （ C） （ D） O(n2) 11 由权值分别为 3， 8， 6， 2， 5的叶子结点生成一棵哈夫曼树，它的 带权路径长度为 (21)。 （ A） 24 （ B） 48 （ C） 72 （ D） 53 12 无向图中一个顶点的度是指图中 (22)。 （ A）通过该顶点的简单路径数 （ B）与该顶点相邻接的顶点数 （ C）通过该顶点的回路数 （ D）与该顶点连通的顶点数 13 已

5、知一个图如图 1.1所示，从顶点 b出发进行广度优先遍历可能得到的序列为(23)。 （ A） b a c e d f （ B） b a c d f e （ C） b a c e f d （ D） b a c e f d 14 当一个作为实际传递的对象占用 的存储空间较大并可能需要修改时，应最好把它说明为 (24)参数，以节省参数值的传输时间和存储参数的空间。 （ A）整形 （ B）引用型 （ C）指针型 （ D）常值引用型 15 向一个长度为 N的顺序表中插入 个新元素的平均时间复杂度为 (25)。 （ A） O(N) （ B） O(1) （ C） O(logN) （ D） O(N2) 16

6、下面的排序方法中，平均时间性能为 O(nlogn)且空间性能最好的是 (26)。 （ A）基数排序 （ B）堆排序 （ C）归并排序 （ D）快速排序 17 已知一组关键字为 18， 48， 36， 72， 79， 82， 23， 40， 16， 35，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是 (27)。 （ A） 18， 36， 48， 72， 23， 40， 79， 82， 16， 35 （ B） 18， 36， 48， 72， 16， 23， 40， 79， 82， 35 （ C） 18， 36， 48， 72， 16， 23， 35， 40， 79， 82 （

7、D） 16， 23， 18， 35， 36， 40， 48， 72， 79， 82 18 设顺序存储的线性表共有 287个元素，按分块查找的要求等分成 7块。若对索引表 采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为 (28)。 （ A） 41 （ B） 25 （ C） 45 （ D） 62 19 在一个单链表中， q结点是 p结点的前驱结点，若在 q与 p之间插入结点 s，则执行 (29)。 （ A） slink=plink ； plink=s ； （ B） plink=s ； slink=q ； （ C） plink=slink

8、； slink=p ； （ D） qlink=s ； slink=p ； 20 一个栈的人栈序列为 a， b， c，则出栈序列不可能的是 (30)。 （ A） c， b， a （ B） b， a， c （ C） c， a， b （ D） a， c， b 21 栈的数组表示中， top为栈顶指针，栈空的条件是 (31)。 （ A） top=0 （ B） top=maxSize （ C） top=maxSize （ D） top=-1 22 栈和队列的共同特点是 (32)。 （ A）都是先进后出 （ B）都是先进先出 （ C）只允许在端点处插入和删除 （ D）没有共同点 23 当利用大小为 n的数

9、组顺序存储一个队列时，该队列的最大长度为 (33)。 （ A） n-2 （ B） n-1 （ C） n （ D） n+1 24 当利用大小为 n的数组顺序存储一个栈时，假定用 top= =n表示栈空，则向这个栈插入一个元素时，首先应执行 (34)语句修改 top指针。 （ A） top+； （ B） top-； （ C） top=0； （ D） top=0； 25 一棵二叉树的中序遍历序列为 DBGEUJOCIF，后序遍历序列为DCJHEBIPCO，则其前序遍历序列为 (87)。 （ A） OBCDEFGHIJ （ B） OBDEGHJCFI （ C） OBDEGHJPIC （ D） OBDE

10、CJHCFI 26 有一颗二叉树有如下特点；不存在子树数目是 1个的结点。这样的一棵二叉树中有 m(m 0)个子树为。的结点时，该二又树上的结点总数为 (91)。 （ A） 2m+1 （ B） 2m-1 （ C） 2(m-1) （ D） 2(m+1) 27 等式 x补 +Y补 =x+Y补在满足条件 (92)时成立，其中 X、 Y是用 n个二进制位表示的带符号纯整数。 （ A） -2n(X+Y)2n-1 （ B） -2n-1(X+Y) 2n-1 （ C） -2n-1-1(X+Y)2n-1 （ D） -2n-1(X+Y) 2n 28 (XYZ+XYZ+XYZ+XYZ+XYZ+XYZ)=(97)。

11、（ A） YZ （ B） Y+Z （ C） YZ （ D） Y+Z 29 三对角矩阵是一类特殊的矩阵，存储方式也比较特殊。现在将一个三对角矩阵A1 100， 1100中的元素按行存储在一维数组 B1.298中，矩阵 A中的元素A66， 67在数组 B中的下标为 (101)。 （ A） 195 （ B） 196 （ C） 197 （ D） 198 30 在等概率前提下，向一个采用顺序存储结构的 n个元素线性表插入一个元 素需要移动的元素个数平均为 (102)。 （ A） n+1 （ B） n/2 （ C） (n+1)/2 （ D） n 31 下列数据结构中属于线性结构的是 (103)。 （ A）

12、双端队列 （ B）高维数组 （ C）列表 （ D）二叉树 32 下列结论中正确的是 (104)。 （ A）二叉树的度不为 2 （ B）二叉树中任何一个结点的度都为 2 （ C）二义树中至少有一个结点的度为 2 （ D）树中结点的度可以小于 2 33 不问的存储结构适用于不同的应用场合。某线性表最常用的运算是插入和删除，删除运算是指删除表头第一 个元素，插入运算是指在表尾插入一个新元素，那么采用 (105)存储方式最好。 （ A）仅有头指针的单向循环链表 （ B）仅有尾指针的单向循环链表 （ C）单向链表 （ D）双向链表 34 设数组 a520， 316的元素以行为主序存放，每个元素占用两个存

13、储单元，则数组元素 ai， j(5i20， 3j16)的地址计算公式为 (108)。 （ A） a-146+28i+2j （ B） a-116+28i+2j （ C） a-144+28i+2i （ D） a-118+28i+2j 35 若正规表达式 s=(x y z)(1 0)*，则 L(s)小有 (109)过个元素。 （ A） 6 （ B） 12 （ C） 18 （ D）无穷 36 若单精度浮点数用 32位二进制数表示，其中最高位为符号位，后面跟 8位经偏移的阶码移码，偏移量为 +127。尾数用原码表示，且把尾数规格化为 1.xxx.x(x为0或 1)，并将 1去掉，尾数用 23位表示。根据

14、该标准，十进制数 -178.125的规格化表示形式为 (110)。 （ A） 110000110 01100100010000000000000 （ B） 110000111 01100100010000000000000 （ C） 0 10000100 01100100010000000000000 （ D） 1 10000110 11100100010000000000000 37 将十进制数 126化为二进制数是 (111)。 （ A） 1111110 （ B） 1101111 （ C） 1111011 （ D） 1101110 38 无符号数 X减去无符号数 Y，结果的进位标志为 0表

15、明 (112)。 （ A） XY （ B） X Y （ C） X=Y （ D） X Y 39 下列关于链表的说法错误 的是 (113)。 （ A）可随机访问任何一个元素 （ B）插入、删除操作不需要移动元素 （ C）无需事先估计存储空间大小 （ D）所需存储空间与线性表长度成正比 40 我们对矩阵压缩存储，是为了 (115)。 （ A）提高运算速度 （ B）节省存储空间 （ C）降低计算复杂度 （ D）方便运算 41 当 (116)时， “链式队列为空 ”(front为头指针， rear为尾指针 )。 （ A） rear=NULL （ B） front= NULL （ C） front= =r

16、ear （ D） front!=rear 42 字符串的特点是 (117)。 （ A）字符串是 种特殊的线性表 （ B）串的长度必须大于零 （ C）字符申不属于线性表的一种 （ D）空格字符组成的串就是空串 43 在具有 200个结点的树中，其边的数目为 (118)。 （ A） 201 （ B） 200 （ C） 199 （ D） 198 44 在程序的执行过程中，实现嵌套调用函数正确返回可以用 (119)结构。 （ A）队列 （ B）栈 （ C）树 （ D）图 45 假设有一维数组 TO.m*n-1，其中 m n。从数组 T的第一个元素 (T0)开始，每隔 n个元素取出一个元素依次存入数组

17、B1.m)中，即 B1=T0，B2=Tn，依此类推，那么放入 Bk(1kn)的元素是 (120)。 （ A） T(K-1)*m （ B） TK*n) （ C） T(K-1)*n （ D） TK*m 46 原码乘法中，乘积的符号位是由被乘数的符号位和乘数的符号位通过 (123)运算来获得的。 （ A）异或 （ B）与 （ C）或 （ D）分别取反后再进行或 47 在串行同步方式传送数据块中，经常采用的差错校验方法是 (124)。 （ A）偶校验 （ B）奇校验 （ C）海明码校验 （ D） CRC校验 48 多媒体计算机中处理活动图像的适配器称为 (62)。 PAL制电视信号速率为 25帧 /秒

18、，已知某一帧彩色静态图像 (RCB)的分辨率为 600400，每一种颜色用 16bit表示，则该视频每秒钟的数据量为 (63)。 （ A）视频卡 （ B）图形加速卡 （ C）电影卡 （ D）视频捕获卡 （ A） 6004003825bps （ B） 8006003825bps （ C） 60040031625bps （ D） 80060031625 bps 50 在 word等常用的文件处理软件中，按下 Alt键再拖动鼠标选择文本，可以(71)；按下 Ctrl键再用鼠标拖动已选定的文本，可以 (72)。 （ A）选中光标所在的文本行 （ B）选中一个段落 （ C）选中光标后的文本行 （ D）选

19、中一个矩形区域中的文本块 （ A）移动选中的文本插入到光标新位置 （ B）移动选中的文本粘贴到光标新位置的行未 （ C）复制选中的文本插入到光标新位置 （ D）复制选中的文本插入到光标新位置的行头 52 通常，文件的逻辑结构可以分为两 大类：无结构的流式文件和有结构的 (164)。(165)组 织方式，既适合于交互方式应用，也适合于批处理方式应用。 （ A）堆文件 （ B）记录式文件 （ C）索引文件 （ D）直接 (Hash)文件 （ A）堆文件 （ B）顺序文件 （ C）索引顺序文件 （ D）流式文件 54 某机器的 IP 地址是 46.52.74.99，则它的二进制 IP 地址为 (18

20、1)，这是一个属于(182)的 IP 地址。 （ A） 0111 1000 0101 0010 1000 0110 1001 1001 （ B） 0000 0011 1100 1010 1010 0110 1001 1001 （ C） 0000 0010 010l 0110 1001 0111 0110 0011 （ D） 0010 1110 0011 0100 0100 1010 0110 0011 （ A） A类 （ B） B类 （ C） C类 （ D） D类 56 关系 R和 S如下表所示，关系代数表达式 1， 4(R(下标 )R.C S.B S)的结果为 (201)，与该表达式等价的

21、SQL语句为 (202)。 R关系 S关系 A B C A B E 1 2 3 2 1 4 2 1 4 4 6 7 3 4 5 3 4 11 4 6 7 8 3 12 （ A） (1， 2)、 (2， 1)、 (3， 4)、 (4， 6) （ B） (1， 1)、 (2， 6)、 (3， 2)、 (4， 3) （ C） (1， 6)、 (1， 4)、 (2， 6)、 (3， 6) （ D） 1(2， 1)、 (4， 6)、 (3， 4)、 (8， 3) （ A） SELECTA， B FROM R， SWHERE C B （ B） SELECT R A， S B From R， S WHERE

22、 R.C S.B （ C） SELECT A， B FROM RWHERE C (SELECTB FROM S) （ D） SELECT 1， 5 FROM RWHERE C (SELECTB FROM S) 58 在黑白图像中，表示灰度级为 4的像素点最少需 (204)位。彩色图像可以用 (205)三基色表示。 （ A） 1 （ B） 2 （ C） 3 （ D） 4 （ A）红黄蓝 （ B）红绿蓝 （ C）绿黄蓝 （ D）红绿黄 60 计算机指令系统中有多种寻址方式，这样做主要目的是 (208)。在下列寻址方式中取得操作数速度最慢的是 (209)。 （ A）简化指令的设计 （ B）可直接访问

23、内存或外存 （ C）提供扩展操作码并降低指令译码难度 （ D）缩短指令长度，扩大寻址空间，提高编程灵活性 （ A）变址寻址 （ B）基址寻址 （ C）寄存器间接寻址 （ D）存储器间接寻址 62 某硬盘中共有 5个盘片， 8个记录面，每个记 录面上有 2100个磁道，每个磁道分为 128个扇区，每扇区为 512字节，则该硬盘的存储容量为 (210)。磁盘的位密度随着磁道从外向内而 (211)1。 （ A） 590 6MB （ B） 9225MB （ C） 1050MB （ D） 1101MB （ A）减少 （ B）不变 （ C）增加 （ D）视磁盘而定 64 选择填入流程图 2.2的合适的语句

24、，它们都完成计算 “1+2+3+4+5”的功能。（ A） i 5 （ B） i 5 （ C） i 5 （ D） i 5 （ A） i 5 （ B） i 5 （ C） i 5 （ D） i 5 66 现在有两个关系模式：供应商 S(Sno， Sname， Status， City)和供应情况SPJ(Sno， Pno， Jno， Qty)。对于查询 “查询零件号 Pno等于 P3的供应商名Sname”SQL语句 (221)是错误的，而关系代数表达式 (222)是正确的。 （ A） SELECTSname FROM S WHERE EXIST5(SELECT * FROM SPJ WHERE S.S

25、no SPJ.Sno AND SPJ.Pno P3) （ B） SELECT Sname FROM S,SPJ WHERE S.Sno SPJ.Sno AND SPJ.Pno P3) CROUP BY Sname （ C） SELECT DISTINCT Sname FROM S WHERE EXISTS(SELECT * FROM SPJ WHERE S.Sno SPJ.Sno AND SPJ.Pno P3) （ D） SELECT DISTINCT Sname FROM S WHERERE 0(SELECTCOUNT(， ) FROM SPJ WHERE S.Sno SPJ.Sno AND

26、 SPJ.Pnn P3) （ A） sname(S)-sname(PnoP3(S(SPJ) （ B） sname(S)nsname(SPnoP3(SPJ) （ C） sname(S)DPno P3(SPJ) （ D） sname(SDPno P3(SPJ) 68 UNIX用户可在 Shell命令级使用管道 “|”，命令 “Proutput.cllp”与 (226)命令组等价。两者相比，前者 (227)。 （ A） proutput.c ternpfilc， lp ternpfile， rm tempfile （ B） pr output.c ternphle， 1p ternphle， ril

27、l tempnle （ C） pr output.c remphle， ternp61e lp （ D） Pr output.c ternpfilc， lp tempfile （ A）可以节省时间 （ B）可以节省空间 （ C）可以减少操作的复杂度 （ D）不需要中间文件 70 操作系统通常采用 (228)解决进程间合作和资源共享所带来的同步与互斥问题。若在系统中有若干个互斥资源 R， 5个并发进程，每个进程都需 要 5个资源 R，那么使系统不发生死锁的资源 R的最少数日为 (229)。 （ A）调度 （ B）共享资源 （ C）信号量 （ D）通讯 （ A） 21 （ B） 25 （ C） 1

28、0 （ D） 5 72 VCD的图像序列由帧内图像， (232)和插补图像构成，其中 (233)采用 JPEC压缩方法来去掉冗余信息。 （ A）视频图像 （ B）动态图像 （ C）预测图像 （ D）静止图像 （ A）视频图像 （ B）动态图像 （ C）插补图像 （ D）帧内图像 74 当手动设置 TCP/IP协议的属性时，需要指定 3个 IP 地址， 即本机地址， (248)地址和 (249)的地址。 （ A）远程服务器 （ B）交换机 （ C） TCP服务器 （ D）默认网关 （ A） DNS服务器 （ B）文件服务器 （ C）邮件服务器 （ D） Web服务器 76 从广义的角度看，数据库

29、系统应该由 (252)组成。 (253)存放在数据字典中，数据库管理系统对应用程序的操作都要通过数据字典来进行。 （ A）数据库、软件和人员 （ B）数据库、硬件、软件和人员 （ C）数据库、数据库管理系统和人员 （ D）数据库、硬件、数据库管理系统和软件 （ A）数据库管理 系统软件 （ B）数据定义语言 DDL （ C）数据操纵语言 DML （ D）数据库体系结构的描述 78 在关系 Student(学号，姓名，系名，课程号，成绩 )中，查询至少选修了四门课程的学生学号、姓名及平均成绩的 SElECT语句应该是： SELECT学号，姓名， AVC(254)AS平均成绩 FROM Stude

30、nt CROUP BY学号 HAVING (255) （ A）成绩 （ B）姓名 （ C）系名 （ D）课程号 （ A） COUNT(DISTINCT学号 ) 3 （ B） COUNT(课程号 ) 3 （ C） COUNT(DISTINCT学号 ) 3 （ D） COUNT(课程号 ) 3 80 内存地址从 7000H到 73PPH，共有 (268)个内存单元。若该内存每个存贮单元可存储 16位二进制数，并用 4片存储器芯片构成，则芯片的容量是 (269)。 （ A） 256 （ B） 512 （ C） 1024 （ D） 2048 （ A） 51216bit （ B） 25616bit （

31、C） 2568bit （ D） 10248bit 82 构成 4M8bit的存储器，若采用 128K16bit的芯片，需 (274)片：若采用512K1bit的芯片，需 (275)片。 （ A） 8 （ B） 16 （ C） 32 （ D） 64 （ A） 8 （ B） 16 （ C） 32 （ D） 64 84 在 CPU执行一段程序的过程中， Cache的存取次数为 1900次，由主存完成的存取次数为 100次。若 Cache的存取厨期为 5ns，主存的存取周期为 25ns，则Cache的命中率为 (276)CPU的平均访问时间为 (277)ns。 （ A） 0.93 （ B） 0.95

32、（ C） 0.97 （ D） 0.99 （ A） 5 （ B） 6 （ C） 7 （ D） 8 86 ADSL对应的中文是 (280)，它有两种 Intenet接入方式，即 (281)。 （ A）分析数字系统层 （ B）非对称数字线 （ C）非对称数字用户线 （ D）异步数字系统层 （ A）固定接入和虚拟拨号接入 （ B）专线接入和 VLAN接入 （ C）固定接入和 VLAN接入 （ D）专线接入和虚拟拨号接入 （ A） ANSI （ B） ISO （ C） ITU-T （ D） IDC （ A）会话 （ B）网络 （ C）物 理 （ D）应用 （ A）传输 （ B）物理 （ C）网络 （ D

33、）数据链路 （ A）传输 （ B）会话 （ C）表示 （ D）应用 92 发布 X.200建议的国际标准化组织是 (5)。制定开放系统互连七层参考模型 (OSI)的国际标准化组织是 (6)。作为最简单的防火墙 分组过滤器在该模型的 (7)层检查出入地址；网桥是在该模型 (8)层进行网络间中继的互连设备； TCP则是 Internet中常用的 (9)层协议之一。 （ A） ANSI （ B） ISO （ C） ITU-T （ D） IDC 软件水平考试（初级） 程序员上午（基础知识）章节练习试卷 3答案与解析 1 【正确答案】 D 【试题解析】 时间复杂度是解决问题的时间和问题的规模之间的关系，

34、即解决问题所耗费的时间随问题规模增长成怎样的增长对应关系。本题中最内部的循环的执行次数为 m*n，所以整段程序的复杂度为 O(m*n)。 2 【正确答案】 B 【试题解析】 “删除 x的后继 ”只需使 x的指针指向后继的下一个结点。 3 【正确答案】 D 【试题解析】 因为 pnextnext=head ，所以 pnext 是尾结点，即 *P的直接后继是尾结点。 4 【正确答案】 C 【试题解析】 带头结点的链队列的头指针和尾指针都不会为空，当它们都指向头结点时表示对列为空，即 Q. front= =Q.rear 5 【正确答案】 C 【试题解析】 单链表头结点为 HL，向表头插入一个由指针

35、P指向的结点时，可以先让 p 指向 HL，然后再将 p 赋给 HL即可。 6 【正确答案】 B 【试题解析】 n 个顶点的强连通图中边最少的情况是，从一个顶点开始顺序连接各点，最后回到该点，它们整体上恰好构成一个圆环。此时有 n条有向边。 7 【正确答案】 A 【试题解析】 广义表的深度定义为广义表中括弧的重数，是广义表的一种量度。本题中 d 处的括弧深度最大为 4。 8 【正确答案】 C 【试题解析】 对于给定的结点数，当二叉树是满二叉树时，高度最少，为大于(n 为结点数 )的最小整数。本题中， ，所以高度至少为 5。 9 【正确答案】 D 【试题解析】 二叉树的先序序列为 ABDECPG，

36、所以根结点为 A，于是根据中序序列为 DDEAGPC可知， A前面的 DBE元素是左于树的，右面的 FC 是右子树上的，于是可以得到左右子树的中序序列和先序序列。按照此方法进行下 去，最终得到树的结构。对树进行后序遍历可得 DEBGPCA。 10 【正确答案】 C 【试题解析】 从一棵二叉搜索树中查找一个元素时，大约需要树的寓度次比较，即时间复杂度大致为 。 11 【正确答案】 D 【试题解析】 构造哈夫曼树后可得 5， 6， 8的编码长度为 2， 2和 3的编码长度为 3，所以带权路径长度为 (5+6+8) 2+(2+3)3=53。 12 【正确答案】 B 【试题解析】 无向图中一个顶点的度

37、是指与该顶点相连的边的数目，也就是与该顶点相邻接的顶点数。 13 【正确答案 】 C 【试题解析】 广度优先遍历可以定义为：首先访问出发点 v，接着依次访问 v的所有邻接点 w1， w2， ， wt，然后再依次访问与 w1， w2， ， wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点 v有路径相通的顶点都已访问到为止。此时从 v开始的搜索过程结束。 14 【正确答案】 B 【试题解析】 把对象说明为引用型参数时，参数值的传输时间和存储参数的空间都比较小。 15 【正确答案】 A 【试题解析】 向一个长度为 N的顺序表中插入一个新元素的平均比较次数为N/2，所以平均时 间复杂度为

38、O(N)。 16 【正确答案】 B 【试题解析】 快速排序、堆排序、归并排序的平均时间性能均为 O(nlogn)，但是堆排序的空间性能最好。 17 【正确答案】 A 【试题解析】 一趟两两归并是每两组进行一次归并排序，第一组为 18， 48，36， 72，排序后得到 18， 36， 48， 72；第二组为 79， 82， 23， 40排序后得到23， 40,79， 82：第三组不变。所以最终结果为 18， 36， 48， 72， 23， 40， 79，82， 16， 35。 18 【正确答案】 B 【试题解析】 287个元素，按分块查找的要求等分成 7块，则每块有 41个元素。于是查找概率相等的情况下，查找确定块需要 4次比较，块中进行顺序查找需要 21次比较，所以查找成功时的平均查找长度为 25。 19 【正确答案】 D 【试题解析】 q 结点是 p 结点的前驱结点，若在 q与 p 之间插入结点 s，只需先将 q 的指针指向 s，然后再将 s指向 p 即可。 20 【正确答案】 C 【试题解析】 a， b， c顺序入栈，然后按照先进后出出栈，使得到序列 c， b，a。 a， b先入栈，然后 b， a出栈，最后 c入栈再出栈便得 到序列 b， a， c。 a入栈即出栈，接着 b 和 c入栈，然后按照 c， b 出栈使得到序列 a， c， b。