国家电网招聘-计算机 (电网)真题库-11

国家电网招聘-计算机(电网)真题库_111、单选题使用图像扫描仪以300DPI的分辨率扫描一幅3英寸×3英寸的图片，可以得到()内存像素的数字图像。A、

100×100B、

300×30（江南博哥）0C、

600×600D、

900×900正确答案：

D

参考解析：一幅画是由很多像素点组成的，每一行有300*3个像素点，一共有300*3这么多行，因此总的像素点行数*每行像素点=900*9002、单选题为了攻击远程主机，通常利用()技术检测远程主机状态。A、

病毒查杀B、

端口扫描C、

QQ聊天D、

身份认证正确答案：

B

参考解析：进行攻击之前，需要了解被攻击主机的相关信息，通常采用端口扫描的方式收集数据。3、单选题如果一棵完全二叉树共有26个结点，则必定有()个结点的度为1。A、

0B、

1C、

3D、

13正确答案：

B

参考解析：26个结点，可知该二叉树有5层。由于前4层组成一棵满二叉树，共15个结点，则共有11个叶子结点，可知只有1个结点的度为1。4、单选题一个有n个结点的图，最多有()个连通分量。A、

0B、

1C、

n-1D、

n正确答案：

D

参考解析：无向图中的极大连通子图称为图的连通分量。图的连通分量的个数小于或等于图的结点数。当图的各个结点彼此都没有边相连时，连通分量数最大为n。5、单选题在有向图中，所有顶点的度数之和是所有边数的()倍A、

0.5B、

1C、

2D、

4正确答案：

C

参考解析：在有向图中，所有顶点的度数之和是所有边数的2倍，因为一条边的两个端点具有两个“度”。6、单选题已知串S=′aaab′，其next数组值为()。A、

0123B、

0213C、

0231D、

1211正确答案：

A

参考解析：7、单选题串′ababaaababaa′的next数组值为()。A、

01234567899B、

012121111212C、

011234223456D、

0123012322345正确答案：

C

参考解析：8、单选题下列的叙述不正确的个数是()。(1)9阶B-树，除根以外的任一结点的关键字个数不少于4(2)理想情况下，在散列表中查找一个元素的时间复杂度为0(1)(3)在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻(4)在索引顺序表的查找中，对索引表既可以采用顺序查找方法，也可采用=分查找方法A、

1B、

2C、

3D、

4正确答案：

A

参考解析：如果发生多次冲突，则同义词在表中就不会相邻，因此(3)是错误的，其它正确。9、单选题设有向无环图G中的有向边集合E={＜1，2＞，＜2，3＞，＜3，4＞，＜1，4＞}，则下列属于该有向图G的一种拓扑排序序列的是()。A、

1，2，3，4B、

2，3，4，1C、

1，2，4，3D、

1，4，2，3正确答案：

A

参考解析：10、单选题已知一个线性表为(38，25，74，63，52，48)，假定采用H(K)=Kmod7计算散列地址进行散列存储，若利用线性探测的开放定址法处理冲突，则在该散列表上进行查找的平均查找长度为()；若利用链地址法处理冲突，则在该散列上进行查找的平均查找长度为()。A、

1.5，1B、

1.7，3/2C、

2，4/3D、

2.3，7/6正确答案：

C

参考解析：若用开放定址法处理冲突，发生0次冲突的关键字有3个，1次冲突的1个，2次冲突的1个，3次冲突的1个，因而在该散列表上进行查找的平均查找长度为ASL-(3*1+1*2+1*3+1*4)/6=2；若用链地址法处理冲突，同一链表上有1个元素的线性链表有2个，有2个元素的线性链表有2个，因此ASL=(4*1+2*2)/6=4/3。11、单选题在一个无向图中，所有顶点的度数之和等于所有边数()倍。A、

1/2B、

2C、

1D、

4正确答案：

B

参考解析：无向图中每条边都有两个顶点，所以所有顶点的度数之和等于所有边数的2倍。12、单选题采用分块查找时.若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分()个结点最佳。A、

10B、

25C、

6D、

625正确答案：

B

参考解析：13、单选题假设用户U有2000台主机，则必须给他分配()个C类网络，如果分配给用户U的网络号为，则指定给用户U的地址掩码为（请作答此空）。A、

B、

C、

D、

正确答案：

C

参考解析：为了给用户U分配2000台主机，需要将C类网络划分为2000个网络单位。C类网络的最大网络数为2^16-2=65534，因此需要将其划分为65534/2000=32.75≈33个网络单位。考虑到实际的网络划分需要以及子网内部的可用主机数，需要分配给用户U一个连续的33位地址空间。所以分配给用户U的网络号为：/33，并且指定给用户U的地址掩码为：C类网络的默认掩码，即A选项：。14、单选题设某哈夫曼树中有199个结点，则该哈夫曼树中有()个叶子结点。A、

101B、

100C、

99D、

102正确答案：

B

参考解析：在哈夫曼树中的结点只有两种，一种是度为零的结点，另一种是度为1的结点。15、单选题下面关于m阶B-树说法正确的是()。①每个结点至少有两棵非空子树；②树中每个结点至多有m-l个关键字；③所有叶子在同一层上；④当插入一个数据项引起B树结点分裂后，树长高一层。A、

①②③B、

②③C、

②③④D、

③正确答案：

B

参考解析：16、单选题设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有()个结点。A、

13B、

12C、

26D、

25正确答案：

D

参考解析：哈夫曼树的特点：具有n个叶子结点的哈夫曼树共有2×n-1个结点。17、单选题对任意7个关键字进行排序，至少要进行()次关键字之间的两两比较。A、

13B、

14C、

15D、

16正确答案：

C

参考解析：18、单选题设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a1，1为第一元素，其存储地址为1，每个元素占一个地址空间，则a8·5的地址是()。A、

13B、

33C、

18D、

40正确答案：

B

参考解析：数组下标从1开始，只存储其下三角形元素，在A，5的前面有7行，第1行有1个元素，第2行有2个元素，…，第7行有7个元素，这7行共有(1+7)×7/2=28个元素，在第8行中，a8·5的前面有4个元素，所以a8·5前有28+4=32个元素，其地址为33。19、单选题设线性表(顺序存储方式)的每个元素占8个存储单元。第一个单元的存储地址为100，则第6个元素占用的最后一个存储单元的地址为()。A、

139B、

140C、

147D、

148正确答案：

C

参考解析：6个元素，每个元素8个存储单元.一共需要48个存储单元。第一个单元的存储地址为100，所以第6个元素占用的最后一个存储单元的地址为100+48-1=147(-1是因为地址100是第一个存储位置)。20、单选题A、

14B、

19C、

21D、

26正确答案：

C

参考解析：本题考查最小生成树算法。21、单选题设有序表中有1000个元素，则用二分查找元素X最多需要比较()次。A、

15B、

10C、

17D、

25正确答案：

B

参考解析：二分查找每趟都使用序列的中间值与关键字比较，直至查找成功或失败。22、单选题将一个a[100][100]的三对角矩阵以行主序存入一维数组B[298]中，元素a[65][64]在B数组中的位置等于()。A、

198B、

197C、

196D、

195正确答案：

D

参考解析：将三对角矩阵a[i][j]存入b[k]中，矩阵压缩地址计算公式为k=2i十j。所以a[65][64]对应的k=2×65+64=194，194是一维数组b的下标，而数组下标是从0开始计数的.所以元素的位置应该是195。23、单选题以下有关算法的说法错误的是()。Ⅰ.算法原地工作的含义是指不需要任何额外的辅助空间；Ⅱ，在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法；Ⅲ.所谓最坏时间复杂度是指最坏情况下估算算法执行时间的一个上界；Ⅳ，同一个算法，实现语言的级别越高，执行效率就越低。A、

ⅠB、

Ⅰ和ⅡC、

Ⅰ和ⅣD、

Ⅲ正确答案：

C

参考解析：算法原地工作的含义是指算法的空间复杂度为O(1)，同一个算法实现语言的级别越高执行效率并不一定越低。24、单选题动态主机配置协议(DHCP)的作用是()；DHCP客户机如果收不到服务器分配的IP地址，则（请作答此空）。A、

分配一个网段的地址B、

继续寻找可以提供服务的DHCP服务器C、

获得一个自动专用IP地址APIPAD、

获得一个私网地址正确答案：

C

参考解析：动态主机配置协议（DynamicHostConfigurationProtocol，DHCP）则是在其基础之上进行了改良的协议，是一种用于简化主机IP配置管理的IP管理标准。通过采用DHCP协议，DHCP服务器为DHCP客户端进行动态IP地址分配。同时DHCP客户端在配置时不必指明DHCP服务器的IP地址就能获得DHCP服务。当同一子网内有多台DHCP服务器时，在默认情况下，客户机采用最先到达的DHCP服务器分配的IP地址。Windows系统在处理DHCP工作失效的情况下，定义了一种自动IP机制APIPA，在dhcp失效时，自动使用169.254.X.X这个范围内的一个随机地址。25、单选题以下关于二叉排序树的说法正确的是()。Ⅰ.在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小Ⅱ.每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树Ⅲ，在二叉排序树中，新插入的关键字总是处于最底层Ⅳ.在二叉排序树中，新结点总是作为叶子结点来插入的Ⅴ.二叉排序树的查找效率和二叉排序树的高度有关A、

Ⅰ、Ⅱ、Ⅳ、ⅤB、

Ⅱ、Ⅲ、ⅣC、

Ⅰ、Ⅲ、ⅤD、

Ⅰ、Ⅳ、Ⅴ正确答案：

D

参考解析：在二叉排序树中，新插入的关键字总是作为叶子结点来插入的，但是叶子结点不一定总是处于最底层。对于二叉排序树，左子树上所有记录的关键字均小于根记录的关键字；右子树上所有记录的关键字均大于根记录的关键字。而不是仅仅与左、右孩子的关键字进行比较。26、单选题已知10个数据元素为(54，28，16，34，73，62，95，60，23，43)，按照依次插入结点的方法生成一棵二叉排序树后，查找值为62的结点所需比较的次数为()。A、

2B、

3C、

4D、

5正确答案：

B

参考解析：将这10个元素按照依次插入结点的方法生成一棵二叉排序树后，62位于这棵二叉排序树的第三层，查找值为62的结点所需要的次数恰好是从二叉排序树的根到被查结点的树的深度。27、单选题若对27个元素只进行三趟多路归并排序，则选取的归并路数为()。A、

2B、

3C、

4D、

5正确答案：

B

参考解析：28、单选题在由4棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为()。A、

20B、

29C、

30D、

35正确答案：

B

参考解析：当把森林转换成二叉树后，第二、第三和第四棵树均在第一棵树的根结点的右子树上。29、单选题一棵完全二叉树上有1001个结点.其中叶子结点的个数是()。A、

250B、

500C、

505D、

501正确答案：

D

参考解析：30、单选题设高度为H的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为()。A、

2HB、

1H-1C、

2H+1D、

H+1正确答案：

C

参考解析：由题可知该二叉树上只有度为0和度为2的结点即每个结点要么是叶子结点要么有两个子结点因此该二叉树的叶子结点数目为2的h次方又因为每个非叶子结点都有两个子结点所以非叶子结点数目为叶子结点数目减1即2的h次方减1因此该二叉树中所包含的结点数为2的h次方加上2的h次方减1即2的h+1次方减1故选项C为正确答案而选项AD都小于2的h+1次方减1不符合题意选项B为2的h次方减1不符合题意31、单选题二叉树的第k层的结点数最多为()。A、

2K-1B、

2K+1C、

2KD、

2正确答案：

A

参考解析：二叉树第k层最多有2k-1个结点。32、单选题下列叙述正确的个数是()。(1)m=2的平衡m路查找树是AVL树(2)m=3的平衡m路查找树是2-3树(3)m=2的平衡m路查找树的叶结点不一定在同一层(4)m阶B-树的叶结点必须在同一层(5)m阶B-树是平衡m路查找树(6)平衡m路查找树不一定是B-树A、

3B、

4C、

5D、

6正确答案：

D

参考解析：33、单选题按照二叉树的定义，具有3个结点的二叉树有()种。A、

3B、

4C、

5D、

6正确答案：

C

参考解析：34、单选题A、

3B、

6C、

9D、

以上答案均不正确正确答案：

A

参考解析：邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V，E)是具有n个顶点的图，顶点序号依次为1，2，……，n，则G的邻接矩阵是n阶方阵，所以该图有3个顶点。35、单选题下列服务中，传输层使用UDP的是()。A、

HTTP浏览页面B、

VoIP网络电话C、

SMTP发送邮件D、

FTP文件传输正确答案：

B

参考解析：从几个选项来看，http使用的tcp协议，端口80.SMTP也是tcp协议，端口25.FTP文件传输协议，也是使用tcp21号端口。因此只能选B。36、单选题设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行()趟的分配和回收才能使得初始关键字序列变成有序序列。A、

3B、

8C、

5D、

6正确答案：

A

参考解析：因为待排序列中最大的数为三位数，所以需要进行3次。37、单选题设循环队列的存储空间为Q(1：30)，初始状态front=rear=30，先经过一系列入队和退队运算后，front=10，rear=10，则循环队列中的元素个数为()。A、

30B、

0C、

29D、

0或30正确答案：

D

参考解析：当frontrear时，循环队列中的元素个数为N-front+rear(N为循环队列容量)。当front=rear时，循环队列中的元素个数可能为空，也可能为满。38、单选题高度为7的AVL树最少有()个结点。A、

31B、

32C、

33D、

34正确答案：

C

参考解析：39、单选题有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为()。A、

37/12B、

35/12C、

39/12D、

43/12正确答案：

A

参考解析：用二分法查找有序表，相当于在一个完全二叉树中查找元素，查找成功的比较次数相当于到查找结点的路径长度加1。12个结点的完全二叉树前三层是满二叉树，第四层有5个结点。整棵树的查找次数总和为：1+22+4×3+5×4=37。查找某个元素的概率是37/12。40、单选题若一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为()。A、

38，40，46，56，79，84B、

40，38，46，79，56，84C、

40，38，46，56，79，84D、

40，38，46，84，56，79正确答案：

C

参考解析：由于选择第一个记录为基准，第一次排序即对整个序列进行一趟快速排序。使得位于基准左侧的关键码均小于基准，位于基准右侧的关键码均大于基准。41、单选题设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过()次比较。A、

4B、

2C、

3D、

1正确答案：

C

参考解析：二分查找法的每一次查找都要与中间值进行比较，所以24第一次与35比较，因为24小于35，所以接下来在35的左半部分中进行查找，左半部分的中间值为18，4大于18，接下来去18的右半部分查找，24与24进行比较，此时，查找成功，共比较了3次。42、单选题下列叙述正确的个数是()。(1)向二叉排序树中插入一个结点，所需比较的次数可能大于此二叉排序树的高度。(2)对B-树中任一非叶子结点中的某关键字K，比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。(3)所谓平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树。(4)删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二又排序树。A、

4B、

3C、

2D、

1正确答案：

D

参考解析：只有第3项是正确的。43、单选题在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为()。A、

4B、

5C、

6D、

7正确答案：

C

参考解析：根据题干中的描述可以画出树，度为零的结点共6个。44、单选题将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为()。A、

4B、

5C、

6D、

7正确答案：

C

参考解析：45、单选题设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为()。A、

4B、

6C、

5D、

7正确答案：

A

参考解析：46、单选题在以太网标准规范中，以太网地址长度是（请作答此空）字节；数据速率达到千兆的标准是()。A、

2B、

4C、

6D、

8正确答案：

C

参考解析：以太网地址长度为48位，即6个字节（4个字节代表一个64位二进制数）。在以太网标准规范中，数据速率达到千兆的标准被称为1000BASE-T，其中的1000表示传输速率为1Gbps，而后面的字母表示使用双绞线作为传输介质。因此，选项C是正确的答案。47、单选题具有5个叶子结点的二叉树中，度为2的结点的个数为()。A、

4B、

6C、

5D、

不确定正确答案：

A

参考解析：二叉树的性质1：非空二叉树上叶结点数等于双分支结点数加1。因此度为2的结点的个数为5-1=4。48、单选题设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列表项应能够至少容纳()个表项。A、

400B、

526C、

624D、

676正确答案：

A

参考解析：采用线性探查法解决冲突查找成功时的平均查找长度S≈0.5×(1+1/(1-a))，其中a是哈希表的装填因子，定义为a=表中装入的记录数，哈希表的长度。若要求查询成功的平均查找次数不超过1.5，即S≤1.5，而且哈希表中装入的记录数为200，故哈希表长度不小于400。49、单选题设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是()。A、

42，40，45，80，85，88B、

40，42，45，55，80，85C、

42，40，45，55，80，85D、

42，40，45，85，55，80正确答案：

C

参考解析：快速排序是通过一趟排序将待排序的记录分割为独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序。本题选择第一个数为基准进行划分，分别从右边查找小于45的数和从左边找大于或等于45的数，不断进行交换，第一趟结束后，即得到第一次划分结果。50、单选题设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有()个空指针域。A、

4m-1B、

2mC、

2m-1D、

4m正确答案：

B

参考解析：因哈夫曼树的结点的度，只有0和2两种情况，所以，空指针域为2m个。51、单选题设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数是()。A、

5B、

6C、

7D、

8正确答案：

D

参考解析：52、单选题若用一个大小为6的一维数组来实现循环队列，且当前front和rear的值分别为3，0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为()。A、

5，1B、

4，2C、

2，4D、

1，5正确答案：

B

参考解析：删除front=(front+1)mod6，加入：rear=(rear+1)mod6。53、单选题设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是()。A、

51234B、

45123C、

43125D、

32154正确答案：

D

参考解析：栈的进出原则是先进后出原则，要不就是先进先出原则。A选项中5最先出，说明1234都在栈里，这样说明1是在栈低，则先不出来。BD的原因一样，所以答案选择D。54、单选题由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为()。A、

53B、

73C、

48D、

24正确答案：

B

参考解析：根据赫夫曼树的构造方法可构造出赫夫曼树，经计算可得带权路径长度为73。55、单选题有六个元素6，5，4，3，2，1的顺序进栈.下列选项中，()不是合法的出栈序列。A、

543612B、

453126C、

346521D、

234156正确答案：

C

参考解析：根据栈的后进先出的特点，对于C选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，有根据入站顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出栈。56、单选题设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为()。A、

55B、

19C、

28D、

10正确答案：

B

参考解析：最后一行的第四列有4个元素，第五行前共有5行，而每个元素占一个字节，并且存储单元共有55个。57、单选题下列隧道协议中，工作在网络层的是()。A、

L2TPB、

SSLC、

PPTPD、

IPSec正确答案：

D

参考解析：IPsec是基于网络层的安全协议。L2tp,pptp是基于数据链路层的安全协议。SSL传输层的安全协议。58、单选题A、

6B、

4C、

3D、

2正确答案：

C

参考解析：59、单选题设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，es，e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是()。A、

6B、

4C、

3D、

2正确答案：

C

参考解析：60、单选题设某棵三叉树中有40个结点，则该三叉树的最小高度为()A、

6B、

4C、

5D、

3正确答案：

B

参考解析：树高度最小时即为每一层都是满的，只有最下层不满的情况是树的高度最小的情况。61、单选题已知数据元素为(34，76，45，18，26，54，92，65)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为()。A、

6B、

7C、

4D、

5正确答案：

D

参考解析：根据二叉排序树插入结点算法，将上述8个数据元素按照依次插入结点的方法构造出一棵二叉排序树后，该树的最大层次为5，故该树的深度为5。62、单选题求解Hanoi问题时，若初始有5个圆盘，则移动圆盘的次数是()。A、

7B、

15C、

31D、

5正确答案：

C

参考解析：63、单选题对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。A、

70，75，82，90，23，16，10，68B、

70，75，68，23，10，16，90，82C、

82，75，70，16，10，90，68，23D、

23，10，16，70，82，75，68，90正确答案：

A

参考解析：快速排序第一趟划分的方法是：将第1个元素放在最终排好序列的最终位置上，则在这个位置右边小于该元素值的元素都移到其左边，则在这个位置左边小于该元素值的元素都移到其右边。64、单选题设散列表表长m=14，散列函数H(k)=kmod11。表中已有15，38，61，84四个元素，如果用线性探测法处理冲突，则元素49的存储地址是()。A、

8B、

3C、

5D、

9正确答案：

A

参考解析：元素15，38，61，84分别存储在4，5，6，7单元，而元素49的散列地址为5，发生冲突，向后探测3个单元，其存储地址为8。65、单选题设哈希表长为14，哈希函数是H(key)=key%ll，表中已有数据的关键字为15，28，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()。A、

8B、

3C、

5D、

9正确答案：

D

参考解析：66、单选题设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有()个度数为0的结点。A、

8B、

6C、

7D、

5正确答案：

C

参考解析：度为O的结点个数为1+2×1+2×2=7。67、单选题设一组初始记录关键字的长度为8，则最多经过()趟插入排序可以得到有序序列。A、

8B、

7C、

9D、

6正确答案：

B

参考解析：插入排序的每一趟在待排元素中取出第一个元素，移至有序序列的适当的位置，所以共八个关键字的序列，最多经过7趟插入排序就可以得到一个有序序列。68、单选题下列病毒中，属于脚本病毒的是()。A、

Trojan.QQ3344B、

SasserC、

VBS.HappytimeD、

Macro.Melissa正确答案：

C

参考解析：69、单选题G是一个非连通无向图，共有28条边，则该图至少有()个顶点。A、

8B、

9C、

6D、

7正确答案：

B

参考解析：n个顶点的无向图中，边数e≤n(n-l)/2，将e=28代入，有n≥8，现已知无向图非连通，则n=9。70、单选题若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为()。A、

9，5，3B、

9，5，2，3C、

1，2，3D、

9，4，2，3正确答案：

D

参考解析：二分查找的基本思想是将n个元素分成大致相等的两部分，取中间位置的节点值与关键字做比较，如果相等，则查找成功；如果关键字的值小于中间节点，则只要在数组的左半部分继续搜索，重复与中间值进行比较，直至查找成功或失败；如果关键字大于中间值，则只要在数组的右半部搜索即可。71、单选题设有广义表D(a，b，D)，其长度为3，深度为()A、

∞B、

3C、

2D、

5正确答案：

A

参考解析：长度为3，但是因第三个元素是一个广义表，所以深度为无穷。72、单选题一个队列的入队顺序是a，b，c，d，则出队顺序是()。A.a，b，C，dB.b，C，d，aA、

d，B、

b，aC、

D、

d，a，b正确答案：

A

参考解析：队列的特点是先进先出，因此出队的序列于入队的序列完全相同，这点与栈不同。73、单选题<p>无向图G=(V，E)，其中V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是()。</p>A、

a，b，e，c，d，fB、

a，c，f，e，b，dC、

a，e，b，c，f，dD、

a，e，d，f，c，b正确答案：

D

参考解析：易老师认为，假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过：然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。74、单选题已知有向图G=(V，A)，其中V={a，b，C，d，e}，A={＜a，b＞，＜a，c＞，＜d，c＞，＜d，e＞，＜b，e＞，＜c，e＞}，对该图进行拓扑排序，下面序列中()不是拓扑排序A、

a，d，c，b，eB、

d，a，b，c，eC、

a，b，d，c，eD、

a，b，c，d，e正确答案：

D

参考解析：75、单选题设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是()。A.A，D，C，R，F，Q，M，S，Y，P，H，XB.P，A，C，S，Q，D，F，X，R，H，M，YC.F，H，C，D，P，A，M，Q，R，S，Y，XD.H，A、

Q，P，B、

M，S，R，C、

D、

X，Y正确答案：

D

参考解析：每一趟冒泡排序从第一个元素开始，相邻的两个元素进行比较，若是降序则进行交换，一趟排序完成后，值最大的元素被移至序列的末尾。76、单选题一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1.n]中，则二叉树中第i个结点(i从1开始用上述方法编号)的右孩子在数组A中的位置是()。A、

A[2i](2i＜=n)B、

A[2i+1](2i+1＜=n)C、

A[i-2]D、

条件不充分，无法确定正确答案：

D

参考解析：题目并未明确所给二叉树的形状，因此不能根据第i个结点在数组A中的存储位置确定其右孩子在数组A中的位置。77、单选题设一个顺序有序表A[1：14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为()。A、

A[7]，A[5]，A[3]，A[4]B、

A[1]，A[14]，A[7]，A[4]C、

A[7]，A[3]，A[5]，A[4]D、

A[1]，A[2]，A[3]，A[4]正确答案：

C

参考解析：二分查找法的每次比较都与中间值进行比较，第一次与位置7的元素比较，依次类推。78、单选题用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1]～A[n]中，结点A[i]若有左子树，则左子树的根结点是()。A、

A[i/2]B、

A[2i]C、

A[2i-1]D、

A[2i+1]正确答案：

B

参考解析：据二叉树的性质5，对完全二叉树从上到下、从左至右给结点编号，若编号为2i的结点存在，则i的左子树一定是A[2i]。79、单选题家庭网络中，下面IP地址()能被DHCP服务器分配给终端设备。A、

1B、

C、

1D、

28正确答案：

C

参考解析：家庭网络地址，必须是私有地址，同时也不能是自动IP地址，因此只有C可以。80、单选题中缀表达式A-(B+C/D)*E的后缀形式是()。A、

AB-C+D/E*B、

ABC+D/-E*C、

ABCD/E*+-D、

ABCD/+E*-正确答案：

D

参考解析：将中缀表达式表示成二叉树的形状，则这棵二叉树的后序遍历序列即为表达式的后缀形式。81、单选题表达式a*(b+c)-d的后缀表达式是()。A、

abcd*+-B、

abc+*d-C、

abc*+d-D、

-+*abcd正确答案：

B

参考解析：根据优先级应该先算(b+c)，将其改为bc+，并将其看成新的操作数，此时中间结果为a*(bc+)-d；下一步应该算a*(bc+)，照上法改为abc+*，中间结果变为abc+*-d；最后算一，最终结果为abc+*d——a82、单选题A、

abcfdegB、

abcgfdeC、

abcdefgD、

abcfgde正确答案：

A

参考解析：本题考查深度优先算法。83、单选题假设以S和X分别表示进栈和出栈操作，则对输入序列a，B，c，d，E进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为()。A.B，c，E，d，aB.B，E，c，a，dC.E，c，A、

d，aB、

c，C、

D、

a，d正确答案：

A

参考解析：a，B进栈(SS)，B出栈(X)，输出“B”，c进栈(S)，c出栈(X)，输出“c”，d，E进栈(SS)，E，d，a出栈(XXX)，输出“E，d，a”，所以结果为B，c，E，d，a。84、单选题简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1.n，1.n]，且压缩存储在B[1.n(n-1)/2]。若按行压缩存储对称矩阵的上三角元素，则当n等于10时，边(V6，V3)的信息存储在()。A、

B[18]B、

B[19]C、

B[20]D、

B[21]正确答案：

C

参考解析：边(V6，V3)与边(V3，V6)是同一条边。原第i行第j列元素在矩阵B(上三角形式)中的下标为：(n-1)+(n-2)+…+(n-(i-1))+(j-i)。将数值代入，(10-1)+(10-2)+(6-3)=20。边(V6，V3)的信息存储在B[20]中。85、单选题下面关于B和B+树的叙述中，不正确的是()。A、

B树和B+树都是平衡的多叉树B、

B树和B+树都可用于文件的索引结构C、

B树和B+树都能有效地支持顺序检索D、

B树和B+树都能有效地支持随机检索正确答案：

C

参考解析：B-树又叫多路平衡查找树，是一种组织和维护外存文件系统非常有效的数据结构。在索引文件组织中，常使用B-树的变形——B+树，属于平衡的多叉树。两者都支持随机检索，但不能有效地支持顺序检索。86、单选题有种关系模式R=＜U，F＞，U={C，T，H，X，S}，F={C→T，(H，X)→C，(H，T)→YC，(H，S)→Y}则表示模式R的码是()。A.CB.(H，S)A、

B、

Y)C、

D、

T)正确答案：

B

参考解析：由题可得如下推导：(H，S)+R，(H，R)+C，C--4T，(H，T)--4R，故可知(H，S)为关系模式的码。87、单选题有A，B，C，D，E5个元素按次序入栈，在各种可能的出栈次序中，以元素C，D最先出栈的序列中，下列正确的一组是()。A、

CDBAECDABEB、

CDEBACDBEAC、

CDEABCDABED、

CEBAECDAEB正确答案：

B

参考解析：只有A、B、C先入栈，才能CD作为第一、二个元素出栈。C出栈，D入栈，D出栈；接着就剩下A、B在栈中，E未入栈，共3个元素，此三者序列为BAE，BEA，EBA。88、单选题在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个结点下标为k(起始下标为1)，采用顺序存储更节省空间的情况是()。A、

d＜12n/(k-n)B、

d＞12n/(k-n)C、

d＜12n/(k+n)D、

d＞12n/(k+n)正确答案：

A

参考解析：89、单选题已知输入序列为abcd，经过输出受限的双端队列后，能得到的输出序列是()。A、

dacbB、

cadbC、

dbcaD、

以上答案都不对正确答案：

B

参考解析：输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。A项，输入序列为abcd，输出序列为dacb，由输出受限性质可知以da开头的结果只有dabc。B项，输入序列为abcd，输出序列为cadb，其输入输出顺序为：先在输出端输入a，然后在非输出端输入b，这时队列中的序列为ba，再在输出端输入c，这时队列中的序列为bac；输出c，再输出a；再在输出端输入d，这时队列中的序列为bd；输出d，再输出b。最后得到输出序列为cadb。C项，输入序列为abcd，输出序列为dbca，由输出受限性质可知以db开头的结果只有dbac。90、单选题RIP协议通过路由器之间的()计算通信代价。A、

链路数据速率B、

物理距离C、

跳步计数D、

分组队列长度正确答案：

C

参考解析：RIP协议是一种典型的距离矢量协议，RIP协议的度量值是以跳数来计算的，即每经过一跳，度量值就会加1，RIP的最大跳数为15，也就是说RIP协议所能传递路由信息的最大跳数就是15跳，超过15跳就表示不可达。91、单选题已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为()。A、

DBACEFB、

DABECFC、

BCDEAFD、

ABDCEF正确答案：

D

参考解析：按照遍历左子树要在遍历右子树之前进行的原则，根据访问根节点位置的不同，可得到二叉树的前序，中序和后序3种遍历方法。层序遍历是从根节点(第1层)出发，首先访问第1层的树根节点，然后从左到右依次访问第2层上的节点，其次是第3层上的节点，依此类推，自上而下，自左向右逐层访问各层上的节点。对于二叉树来说，第n层节点最多为2m1。由层序序列可得:F是树根节点，D.E是第2层节点:结合中序序列有DBA构成F的左子树，CE构成F的右子树，进-一步有C是E的左节点、B无右节点:这样A是第4层节点，据DBA序列有B是D的右节点.A是B的右节点。易知后序序列为ABDCEF.92、单选题某二叉树中序序列为A，B，C，D，