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

国家电网招聘-计算机(电网)真题库_241、单选题一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是()。A.edcbaA、

decbB、

C、

dcea（江南博哥）bD、

abcde正确答案：

C

参考解析：栈的特点是先进后出，所以不可能出现先进先出和后进后出的情况，选项C中a在b之前出栈是不可能发生的。2、单选题快速以太网标准100BASE-TX规定使用（）无屏蔽双绞线，其特性阻抗为（请作答此空）Ω。A、

50B、

70C、

100D、

150正确答案：

C

参考解析：根据题目所述，快速以太网标准100BASE-TX使用的是无屏蔽双绞线，而其特性阻抗为100Ω。因此，答案为C。3、单选题以下()不是队列的基本运算。A、

从队尾插入一个新元素B、

从队列中删除第i个元素C、

判断一个队列是否为空D、

读取队头元素的值正确答案：

B

参考解析：队列只允许在队头和队尾进行插入或删除操作，不允许随机删除队列中第i个元素。4、单选题为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是()A、

栈B、

队列C、

树D、

图正确答案：

B

参考解析：主机将数据依次写入，打印机依次取出，应该属于先进先出的特点，既使用的逻辑结构是队列。5、单选题将递归算法转变成对应非递归算法时，需要使用()保存中间结果。A、

栈B、

队列C、

二叉树D、

单链表正确答案：

A

参考解析：栈是一种先进后出的数据结构。系统实现递归时，本身也是用堆栈实现的，用来保存现场信息。6、单选题在单链表指针为p的结点之后插入指针为s的结点，正确的操作是()。A、

p->next=s;s->next=p->next;B、

s->next=p->next;p->next=s;C、

p->next=s;p->next=s->next;D、

p->next=s->next;p->next=s;正确答案：

B

参考解析：在单链表中插入结点，应先给将插入的结点的next指针指向插入点的下一个结点，然后再改变插入点前结点的next指针。若先改变p的next指针指向s，会导致链表断裂。7、单选题已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1，则第I个结点的地址为()A、

da1+(I-1)*mB、

da1+I*mC、

da1-I*mD、

da1+(I+1)*m正确答案：

A

参考解析：每个结点需占m个存储单元，若第一个结点的地址为da1，则第I个结点的地址为da1+(I-1)*m。8、单选题广义表A(a)，则表尾为()A.A、

B、

（（））C、

空表D、

（a）正确答案：

C

参考解析：广义表A(a)，则表尾为空表。9、单选题下列广义表是线性表的有()A.E（a，(b，c)）A、

E(a，B、

C、

E(a，b)D、

E(a，L())正确答案：

C

参考解析：四个选项中只有C选项中为线性表。10、单选题对稀疏矩阵进行压缩存储目的是()。A、

便于进行矩阵运算B、

便于输入和输出C、

节省存储空间D、

降低运算的时间复杂度正确答案：

C

参考解析：稀疏矩阵的压缩方法主要有：三元组顺序表（行下标，列下标，值）、行逻辑链接的顺序表、十字链表。目的地是为了降低运算的时间复杂度。11、单选题二叉树使用二叉链表存储，若p指针指向二叉树的一个结点，当p->lchild=NULL时，则()。A、

p结点左儿子为空B、

p结点有右儿子C、

p结点右儿子为空D、

p结点有左儿子正确答案：

A

参考解析：若一个树的左右子树为空，即以null表示。12、单选题已知某二叉树中序遍历序列是BDAEC，先序遍历序列是ABDCE，则该二叉树为()。A、

AB、

BC、

CD、

D正确答案：

C

参考解析：先序序列为ABDCE，因此A是树根结点，中序序列为BDAEC，因此BD是左子树上的结点，EC是右子树上的结点。根据先序遍历序列，可知B是左子树的根结点，C是右子树的根结点。在中序遍历序列BDAEC中，D在B之后，因此D是B的右孩子。同理，在中序遍历序列BDAEC中，E在C之前，因此E是C的左孩子。13、单选题以太网控制策略中有三种监听算法，其中一种是"一旦介质空闲就发送数据，假如介质忙，继续监听，直到介质空闲后立即发送数据"，这种算法称为（）监听算法。这种算法的主要特点是（请作答此空）。A、

介质利用率低，但冲突楷率低B、

介质利用率高，但冲突楷率也高C、

介质利用率低，但无法避免冲突D、

介质利用率高，可以有效避免冲突正确答案：

B

参考解析：该监听算法为非持续性监听算法，即发送方只在介质空闲时才发送数据，如果介质忙，则继续监听。这种算法虽然可以使介质利用率高，但由于多个发送方可能同时监听到介质空闲而同时发送数据，因此冲突率也会相应增加。因此，该算法的主要特点是介质利用率高，但冲突率也高。因此，答案为B。14、单选题设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是()。A、

空或只有一个结点B、

高度等于其结点数C、

任一结点无左孩子D、

任一结点无右孩子正确答案：

B

参考解析：先序遍历是中左右，后序遍历是左右中，若没有右孩子，则先序遍历和后序遍历的序列正好相反。15、单选题设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉树中有()个度数为0的结点。A、

5B、

6C、

7D、

8正确答案：

C

参考解析：因为三叉树中所有结点的度数均不大于3，所以结点总数(记为n)应等于0度结点数、1度结点（记为n1）、2度结点数(n2)和3度结点数(n3)之和：n=no+n1+n2+n3（式子1）另一方面，1度结点有一个孩子，2度结点有两个孩子，3度结点有三个孩子，故三叉树中孩子结点总数是：nl+2n2+3n3树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：n=n1+2n2+3n3+1（式子2）由式子1和式子2得到：no=n2+2n3+116、单选题深度为k的完全二叉树，其叶子结点必在第()层上。A、

k-1B、

kC、

k-1和kD、

1至k正确答案：

C

参考解析：二叉树的第i层至多有2^（i-1）个结点；深度为k的二叉树至多有2^k-1个结点。完全二叉树的叶子结点必然在最后一层或倒数第二层。17、单选题折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。A、

20，70，30，50B、

30，88，70，50C、

20，50D、

30，88，50正确答案：

A

参考解析：首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。18、单选题采用开放定址法处理散列表的冲突时，其平均查找长度()。A、

低于链接法处理冲突B、

高于链接法处理冲突C、

与链接法处理冲突相同D、

高于二分查找正确答案：

B

参考解析：开放定址法处理冲突的平均查找长度高于链接法。19、单选题设某散列表的长度为100，散列函数H(k)=k%P，则P通常情况下最好选择()。A、

99B、

97C、

91D、

93正确答案：

B

参考解析：选择小于100的最大素数。20、单选题已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是()。A.4B.5C.6D.742、已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是()。A、

4B、

5C、

6D、

7正确答案：

B

参考解析：用给定值k先与中间结点的关键字比较，若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行直到整个表查找完毕，返回查找失败。21、单选题设有序表中有1000个元素，则用二分查找查找元素X最多需要比较()次。A、

25B、

10C、

7D、

1正确答案：

B

参考解析：最多次数也就是查找失败的情况下需要比较多少次，有序表有1000个元素时，查找失败的情况下需要比较10次。22、单选题设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为()。A、

A[1]，A[2]，A[3]，A[4]B、

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

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

A[7]，A[5]，A[3]，A[4]正确答案：

C

参考解析：二分查找即折半查找，每一次比较都是与待比较的序列的中间元素进行比较。第一个比较的数值的位置应为（1+14）/2取整，所以第一个比较的位置应为A[7]，此时low指针的值为1，high指针的值为6，继续计算第二次比较的位置，为A[3]，以此类推，结果为C选项。23、单选题设有一组初始记录关键字序列为｛34，76，45，18，26，54，92｝，则由这组记录关键字生成的二叉排序树深度为()。A、

4B、

5C、

6D、

7正确答案：

A

参考解析：要先了解二叉排序树的生成方法，简单的说，最基本就是：1.第一个关键字做根结点；2.每个关键字都与根结点比较，如果小于根结点，就插入到左子树，否则插入到右子树。以序列（(34，76，45，18，26，54，92）为例：深度为4。24、单选题根据IPv6的地址前缀判断下面哪一个地址属于全球的单播地址。（）A.12AB:0000:0000:CD30:0000:0000:0000:005EB.20A5:0000:0000:CD30:0000:0000:0000:005EA、

FE8B、

0000:0000:CD30:0000:0000:0000:005EC、

FFAD、

0000:0000:CD30:0000:0000:0000:005E正确答案：

B

参考解析：根据IPv6的地址前缀，单播地址通常以“::”开头，中间由一系列数字或字母组成。选项B中的地址“0000:0000:CD30:0000:0000:0000:005E”符合这个特征，因此属于全球的单播地址。而其他选项中的地址不符合IPv6的地址前缀，因此不属于全球的单播地址。25、单选题设有n个关键字具有相同的hash函数值，则用线性探索法把n个关键字映射到hash中，需要做()次线性探测。A、

nB、

n*(n+1)C、

n*(n+1)/2D、

n*(n-1)/2正确答案：

C

参考解析：关键字直接插入要做1次探测。所以类推n个关键词要做1+2+...+(n-1)+n=n*(n+1)/2答案是C。26、单选题Hash表示用于数据存储的一种有效的数据结构，Hash表等查找复杂度依赖于Hash值算法的有效性，在最好的情况下，Hash表的查找复杂度为()。A、

O(nlogn)B、

O(logn)C、

O(n)D、

O(1)正确答案：

D

参考解析：O(1)，哈希表是通过计算hashcode来定位元素位置，所以在最好的情况下，即不发生冲突的情况下，只需一次即可找到。27、单选题对n个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多()。A、

从小到大排列好的B、

从大到小排列好的C、

元素无序D、

元素基本有序正确答案：

B

参考解析：当n个排序码从大到小排列好时，冒泡排序法比较的次数最多。28、单选题设一组初始关键字记录关键字为（20，15，14，18，21，36，40，10），则以20为基准记录的一趟快速排序结束后的结果是()。A、

10，15，14，18，20，36，40，21B、

10，15，14，18，20，40，36，21C、

10，15，14，20，18，40，36，21D、

15，10，14，18，20，36，40，21正确答案：

A

参考解析：一般去关键字为第一个数，这里就是取20开始：20，15，14，18，21，36，40，10第一步：10，15，14，18，21，36，40，20第二步：10，15，14，18，20，36，40，21现在第一趟快速排序完成了，小于20的都在20前面，大于20的都在20的后面。29、单选题下列四种排序中()的空间复杂度最大。A、

插入排序B、

冒泡排序C、

快速排序D、

归并排序正确答案：

D

参考解析：30、单选题对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()。A、

O（n）B、

O（n2）C、

O（nlog2n）D、

O（n3）正确答案：

B

参考解析：快速排序的平均时间复杂度为O(nlog2n)，最坏时间复杂度为O（n2）。31、单选题某内排序方法的稳定性是指()。A、

该排序算法不允许有相同的关键字记录B、

该排序算法允许有相同的关键字记录C、

平均时间为0（nlogn）的排序方法D、

以上都不对正确答案：

D

参考解析：排序的稳定性是指关键字中有相同时，排序后得到的结果中相同关键字的相对位置不变。32、单选题下列排序算法中，其中()是稳定的。A、

堆排序，冒泡排序B、

快速排序，堆排序C、

直接选择排序，归并排序D、

归并排序，冒泡排序正确答案：

D

参考解析：冒泡排序、插入排序、归并排序、基数排序是稳定的排序算法。33、单选题下面给出的四种排序法中()排序法是不稳定性排序法。A、

插入B、

冒泡C、

二路归并D、

堆积正确答案：

D

参考解析：冒泡排序、插入排序、归并排序、基数排序是稳定的排序算法。34、单选题若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选()排序为宜。A、

直接插入B、

直接选择C、

堆D、

快速正确答案：

A

参考解析：四种排序中只有直接插入排序是稳定的排序。35、单选题8位二进制补码表示整数的范围是()。A、

0~127B、

0~128C、

-128~127D、

-127~0正确答案：

C

参考解析：*若字长为n+1，则补码的表示范围为：-2^n≤x≤2^n-1,此题中n=7,则x的范围是-128≤x≤127。36、单选题SNMP协议中，管理站用来接收代理发来的Trap报文时采用的协议及缺省端口号是（）。A、

UDP161B、

TCP161C、

UDP162D、

TCP162正确答案：

C

参考解析：SNMP协议中，Trap报文是由代理向管理站发送的，用于通知管理站某些事件的发生。管理站需要接收这些Trap报文，因此需要使用一种协议和端口号来接收。根据SNMP协议的规定，管理站接收Trap报文时使用的协议是UDP，而缺省端口号是162。因此，本题的正确答案是C。其他选项中，UDP161是SNMP协议中用于管理站向代理发送请求的端口号，TCP161是SNMP协议中用于管理站向代理发送请求的协议，TCP162则不是SNMP协议中使用的任何端口号或协议。37、单选题若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是()。A、

快速排序B、

堆排序C、

归并排序D、

直接插入排序正确答案：

C

参考解析：快速、堆、归并排序的平均时间均为O(nlog2n)，但其中只有归并排序是稳定的排序。38、单选题下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是()。A、

选择排序法B、

插入排序法C、

快速排序法D、

堆积排序法正确答案：

A

参考解析：选择排序的基本思想是每一趟从待排序序列中选择最小（最大）的元素与第一个元素交换，所以，比较次数与排序方法无关。39、单选题数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的()的两趟排序后的结果。A、

选择排序B、

冒泡排序C、

插入排序D、

堆排序正确答案：

C

参考解析：选择排序、冒泡排序、堆排序的每一趟排序都可使某些元素到达其最终位置。40、单选题下列排序算法中()不能保证每趟排序至少能将一个元素放到其最终的位置上。A、

快速排序B、

shell排序C、

堆排序D、

冒泡排序正确答案：

B

参考解析：快速排序、冒泡排序和堆排序都可以在每一趟选出一个元素放到其最终位置上。41、单选题下列序列中，()是执行第一趟快速排序后所得的序列。A、

[68，11，18，69][23，93，73]B、

[68，11，69，23][18，93，73]C、

[93，73][68，11，69，23，18]D、

[68，11，69，23，18][93，73]正确答案：

C

参考解析：快速排序执行一趟后以基准为划分标志，在基准之前的元素都比基准大，基准之后的元素都比基准元素小。42、单选题有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为()（按递增序）。A.下面的B，A、

D都不对B、

9，7，8，4，-1，7，15，20C、

20，15，8，9，7，-1，4，7D、

9，4，7，8，7，-1，15，20正确答案：

A

参考解析：题干中未指明划分的基准，所以无法得知一趟排序后的结果。43、单选题一组记录的关键码为（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

参考解析：快速排序的思想是任意取待排序序列中的某个元素作为基准（一般取第一个元素），通过一次排序，将待排元素分为左右两个子序列，左子序列元素的关键值均小于或等于基准元素的关键值，右子序列的关键值则大于基准元素的关键值，然后分别对两个子序列继续进行排序，直至整个序列有序。44、单选题在下面的排序方法中，辅助空间为O(n)的是()。A、

希尔排序B、

堆排序C、

选择排序D、

归并排序正确答案：

D

参考解析：归并排序占辅助空间O(n)，希尔排序占O(1)，堆排序占O(1)，选择排序占O(1)。45、单选题设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为()。A、

15，25，35，50，20，40，80，85，36，70B、

15，25，35，50，80，20，85，40，70，36C、

15，25，35，50，80，85，20，36，40，70D、

15，25，35，50，80，20，36，40，70，85正确答案：

A

参考解析：将已经有序的五个子序列两两合并，将合并后的子序列分别进行排序，得到排序结果15，25，35，50，20，40，80，85，36，70。46、单选题时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是()。A、

堆排序B、

冒泡排序C、

希尔排序D、

快速排序正确答案：

A

参考解析：堆排序无论是在最好情况下还是最坏情况下，时间复杂度都是O(nlog2n)。47、单选题在SNMPv2中，为解决分布式网络管理的需要引入了（）。A、

上下报文和访问特权数据库B、

上下报文和管理站数据库C、

通知报文和访问特权数据库D、

通知报文和管理站数据库正确答案：

D

参考解析：SNMPv2（SimpleNetworkManagementProtocolversion2）是一种用于网络管理的协议。在SNMPv2中，为了解决分布式网络管理的需要，引入了通知报文和管理站数据库。通知报文是指代理向管理站发送的一种报文，用于通知管理站某些事件的发生，例如某个设备的状态发生了变化。管理站数据库则是指管理站中存储的设备信息和配置信息的数据库，用于管理和监控网络中的设备。因此，选项D“通知报文和管理站数据库”是正确的答案。选项A、B、C中都存在错误，因为上下报文和访问特权数据库并不是SNMPv2中为解决分布式网络管理引入的内容。48、单选题下列排序方法中，最坏情况下比较次数最少的是()。A、

冒泡排序B、

简单选择排序C、

直接插入排序D、

堆排序正确答案：

D

参考解析：在最坏情况下堆排序的时间复杂度是O(nlog2n)，其他都是O(n2)。49、单选题若用冒泡排序方法对序列{10、14、26、29、41、52}从大到小排序，需要进行几次比较()A、

3B、

10C、

15D、

25正确答案：

C

参考解析：冒泡排序法比较排序的时候，第一个10要进行5次比较，第二个要进行4次比较，一次类推，3次，2次，1次，总共是15次比较。50、单选题下列排序算法中，时间复杂度不变数据初始状态影响，恒为O（Nlog2N）的是()。A、

堆排序B、

快速排序C、

并列排序D、

直接选择排序正确答案：

A

参考解析：在堆排序和快速排序中，若原始记录接近正序或反序，则选用堆排序，若原始记录无序，则最好选用快速排序。只有A和C是O(nlog2n)的复杂度，但是快速排序在“最坏”的情况下蜕化为冒泡排序，其时间复杂度为O(n2)。51、单选题从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为()。A、

插入排序B、

选择排序C、

快速排序D、

冒泡排序正确答案：

A

参考解析：直接插入排序的思想是每趟将一个待排元素作为关键字，按照其关键字值的大小插入到已经排好的部分序列的适当位置上，直到插入完成。52、单选题从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为()A、

冒泡排序B、

归并排序C、

插入排序D、

选择排序正确答案：

D

参考解析：选择排序的基本方法是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。53、单选题设有5000个元素，希望用最快的速度挑选出前10个最大的，采用()方法最好。A、

快速排序B、

堆排序C、

希尔排序D、

归并排序正确答案：

B

参考解析：堆排序不必将整个序列排序即可确定前若干个最大（或最小）元素。54、单选题与单链表相比，双链表的优点之一是()。A、

插入、删除操作更简单B、

可以进行随机访问C、

可以省略表头指针或表尾指针D、

顺序访问相邻结点更灵活正确答案：

D

参考解析：双链表的结点里不仅有指向后继结点的指针还有指向前驱结点的指针，所以双链表在顺序访问时比单链表灵活。55、单选题下列关键字序列中，()是堆。A、

16，72，31，23，94，53B、

94，23，31，72，16，53C、

16，53，23，94，31，72D、

16，23，53，31，94，72正确答案：

D

参考解析：将所有数据序列按完全二叉树从根开始放，如果所有分支都小于或者等于孩子结点关键码，就是小顶堆，反之，如果所有分支结点的关键码大于或者等于孩子结点关键码，则为大顶堆。56、单选题堆是一种()排序。A、

插入B、

选择C、

交换D、

归并正确答案：

B

参考解析：堆是一种选择排序，选择排序有直接选择排序和堆排序。57、单选题若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为()。A、

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

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

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

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

B

参考解析：第一次，40，79，56，38，46，84；第二次：40，46，56，38，79，84；第三次：40，38，56，46，79，84；第四次：40，38，46，56，79，84。58、单选题设模拟信号的最高频率为10MHz，采样频率必须大于（）时，才能使得到的样本信号不失真，如果每个样本量化为256个等级，则信道的数据速率是（请作答此空）。A、

40Mb/sB、

80Mb/sC、

160Mb/sD、

320Mb/s正确答案：

C

参考解析：根据奈奎斯特采样定理，采样频率必须大于等于模拟信号的最高频率的两倍，即20MHz。因此，选项A和B都不符合要求。数据速率可以通过采样频率和每个样本量化的位数来计算。每个样本量化为256个等级，需要8个比特来表示。因此，每秒钟需要采样256×10^6×8个比特，即2.048Gb/s。但是，由于信号需要进行调制和编码，实际传输速率会有一定的损失。一般来说，数据速率会略低于理论值。因此，选项C的160Mb/s是最接近实际情况的答案。59、单选题某二叉树的前序和后序序列正好相反，则该二叉树一定是()的二叉树。A、

空或只有一个结点B、

高度等于其结点数C、

任一结点无左孩子D、

任一结点无右孩子正确答案：

B

参考解析：前序遍历先遍历根节点，再遍历左子树，最后遍历右子树。后序遍历先遍历左子树，再遍历右子树，最后遍历根节点。可知，任一结点无右孩子，前序和后序刚好相反。60、单选题已知一棵完全二叉数的第六层（设根为第一层）有八个叶结点，则该完全二叉树的结点个数最多为()。A、

39B、

52C、

111D、

119正确答案：

C

参考解析：8+16+8+4+2+1=39。最多是39+2*36=111个节点。61、单选题对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2，则()。A、

n0=n2+1B、

n2=n0+1C、

n0=2n2+1D、

n2=2n0+1正确答案：

A

参考解析：对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2，则n0=n2+1。62、单选题哈夫曼树是访问叶结点的带权路径长度()的二叉树。A、

最短B、

最长C、

可变D、

不定正确答案：

A

参考解析：假设n个权值{w1，w2，…，wn}构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi，则WPL最小的二叉树叫做最优二叉树。63、单选题下面的说法中，不正确的是()。A、

对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可B、

对角矩阵只须存放非零元素即可C、

稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储D、

稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储正确答案：

D

参考解析：稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。如果零元素的分布有规律，就没有必要存储非零元素的行号和列号，而需要按其压缩规律找出相应的映象函数。64、单选题设一棵完全二叉树中有65个结点，则该完全二叉树的深度为()。A、

8B、

7C、

6D、

5正确答案：

B

参考解析：1+2+4+8+16+32+2=65，深度为7。65、单选题设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为()。A.BADCA、

BCDB、

C、

CDABD、

CBDA正确答案：

A

参考解析：根据中序遍历和前序遍历可以画出二叉树，C为根结点，A、D分别为左右子树，B为A的右孩子。根据树可以知道后序遍历的序列。66、单选题设一棵二叉树的深度为k，则该二叉树中最多有()个结点。A、

AB、

BC、

CD、

D正确答案：

D

参考解析：67、单选题设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）A、

O(n)B、

O(n2)C、

O(nlog2n)D、

O(1og2n)正确答案：

D

参考解析：log2n是树高。68、单选题设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有()个。A、

4B、

5C、

6D、

7正确答案：

C

参考解析：根据题干描述可画出度数为三的树，度数为0的结点数为6。69、单选题下面的选项中，不属于网络155.80.100.0/21的地址是（）。A、

155.80.102.0B、

155.80.99.0C、

155.80.97.0D、

155.80.95.0正确答案：

D

参考解析：网络地址155.80.100.0/21表示前21位为网络地址，后11位为主机地址。因此，该网络的可用地址范围为155.80.96.1~155.80.103.254。选项中只有D的地址不在该范围内，因此D是不属于该网络的地址。因此，答案为D。70、单选题在任何图中必定有偶数个()。A、

度数为偶数的结点B、

入度为奇数的结点C、

度数为奇数的结点D、

出度为奇数的结点正确答案：

C

参考解析：定一个无向图图G=(V，E)，其中V表示顶点集合，E表示边集合。则有握手定理成立，即图中所有顶点的度数之和等于两倍的边数，换句话来说，所有顶点的度数之和一定是偶数。所以如果图中存在度数是奇数的顶点，那么为了保证所有点的度数之和为偶数，只能让这样的奇数度的点为偶数个。71、单选题无向图中一个顶点的度是指图中与该顶点相连接的顶点数。若无向图G中的顶点数为n，边数为e，则所有顶点的度数之和为()。A.n*eA、

n+B、

C、

2nD、

2e正确答案：

D

参考解析：在无向图中边没有入度出度之分，所以一条边连接两个结点，度就是2，e条边的度就有2e。72、单选题任何一个无向连通图的最小生成树()。A、

只有一棵B、

一棵或多棵C、

一定有多棵D、

可能不存在正确答案：

A

参考解析：生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一。73、单选题设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A、

5B、

6C、

7D、

8正确答案：

A

参考解析：连通图的各个结点之间是连通的，所以6个结点的无向图至少需要5条边。74、单选题下列说法不正确的是()。A、

图的深度遍历是一个递归过程B、

图的遍历是从给定的源点出发，每一个顶点仅被访问一次C、

遍历的基本算法有两种：深度遍历和广度遍历D、

图的深度遍历不适用于有向图正确答案：

D

参考解析：图的深度遍历适用于有向图。75、单选题设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为()。A.nA、

B、

C、

2nD、

2e正确答案：

D

参考解析：无向图的边都是入度，所以入度之和应该是边数的二倍，即2e。76、单选题深度优先遍历类似于二叉树的()。A、

先序遍历B、

中序遍历C、

后序遍历D、

层次遍历正确答案：

A

参考解析：深度优先遍历类似于二叉树的先序遍历，广度优先遍历类似于层次遍历。77、单选题散列技术中的冲突指的是()。A、

两个元素具有相同的序号B、

两个元素的键值不同，而其他属性相同C、

数据元素过多D、

不同键值的元素对应于相同的存储地址正确答案：

D

参考解析：散列技术中的冲突指的是不同键值的元素对应于相同的存储地址。78、单选题AOV网是一种()A、

有向图B、

无向图C、

无向无环图D、

有向无环图正确答案：

D

参考解析：AOV网是有向无环图。79、单选题对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为：（1）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是()。A、

选择B、

冒泡C、

快速D、

插入正确答案：

A

参考解析：每一趟的排序结果都是将待排序序列的最小值放在了有序序列的最后，这是选择排序的算法步骤。80、单选题关于包过滤防火墙和代理服务防火墙，以下描述正确的是（）。A、

包过滤技术实现成本较高，所以安全性能高B、

包过滤技术对应用和客户是透明的C、

代理服务技术安全性较高，可以提高网络整体性能D、

代理服务技术只能配置成用户认证后才能建立连接正确答案：

B

参考解析：本题考查的是包过滤防火墙和代理服务防火墙的特点。A选项错误，包过滤技术实现成本较低，但安全性能较低；B选项正确，包过滤技术对应用和客户是透明的；C选项错误，代理服务技术安全性较低，但可以提高网络整体性能；D选项错误，代理服务技术可以配置成用户认证后才能建立连接，但不是只能配置成这种方式。因此，本题的正确答案是B。81、单选题下面的序列中，()是堆。A、

1，2，8，4，3，9，10，5B、

1，5，10，6，7，8，9，2C、

9，8，7，6，4，8，2，1D、

9，8，7，6，5，4，3，7正确答案：

A

参考解析：按照树的层次遍历顺序将堆填满，可以判断是否属于大顶堆或小顶堆。82、单选题序列16，14，10，8，7，9，3，2，4，1的说法下面哪一个正确()。A、

大顶堆B、

小顶堆C、

不是堆D、

二叉排序树正确答案：

A

参考解析：大顶堆的根节点值在本棵树中最大，并且每棵子树也是大顶堆。83、单选题最坏情况下insertsort，quicksort，mergesort的复杂度分别是多少()。A、

O（n*n），O（nlogn），O（n*n）B、

O（n*n），O（n*n），O（nlogn）C、

O（n*n），O（nlogn），O（nlogn）D、

O（nlogn），O（nlogn），O（nlogn）正确答案：

B

参考解析：84、单选题最小堆0，3，2，5，7，4，6，8，在删除堆顶元素0之后，其结果是()。A、

3，2，5，7，4，6，8B、

2，3，5，7，4，6，8C、

2，3，4，5，7，8，6D、

2，3，4，5，6，7，8正确答案：

C

参考解析：根据堆的删除规则，删除操作只能在堆顶进行，也就是删除0元素。然后让最后一个节点放在堆顶，做向下调整工作，让剩下的数组依然满足最小堆。删除0后用8填充0的位置，为[8，3，2，5，7，4，6]，然后8和其子节点3，2比较，结果2最小，将2和8交换，为[2，3，8，5，7，4，6]，然后8的下标为2，其两个孩子节点下标分别为2*2+1=5，2*2+2=6，也就是4和6两个元素，经比较，4最小，将8与4交换，为[2，3，4，5，7，8，6]，这时候8已经没有孩子节点了，调整完成。85、单选题将整数数组（7-6-3-5-4-1-2）按照堆排序的方式进行升序排列，请问在第一轮排序结束之后，数组的顺序是()。A、

1-2-3-4-5-6-7B、

2-6-3-5-4-1-7C、

6-5-3-2-4-1-7D、

5-4-3-2-1-6-7正确答案：

C

参考解析：数组已经是一个大顶堆，可直接开始排序。（大顶堆：每个节点的值都不小于自己两个左右子节的完全二叉树）每轮输出堆顶元素后，以堆中最后一个元素代替之（由于此题要求原地排序，即不产生额外的空间，堆顶元素与最后一个元素交换）。再将新的顶点元素不断与其子节点中大于该元素的较大者交换，直到该元素大于其左右两个子节点，或成为叶子节点。此时将剩余元素调整成一个新的大顶推。由此得出，第一轮结束后的顺序是：6，5，3，2，4，1，7。86、单选题一个二叉树有100个子节点数为2的节点，100个子节点数为1的节点，那么个子节点数为0的节点（叶节点）的个数为()。A、

101B、

100C、

200D、

300正确答案：

A

参考解析：首先，假设该二叉树有n个节点，则有n-1条边，这是因为除了根节点，其余的每个节点都有且只有一个父节点，那么这n个节点恰好为树贡献了n-1条边。这是从下往上的思考，而从上往下(从树根到叶节点)的思考，容易得到每个节点的度数和0*n0+1*n1+2*n2即为边的个数。因此，我们有等式n-1=n1+2*n2，把n用n0+n1+n2替换，得到n0+n1+n2-1=n1+2*n2，于是有n0=n2+1。n0=n2+1=100+1=10187、单选题不含任何结点的空树是()。A、

是一棵树B、

是一棵二叉树C、

是一棵树也是一棵二叉树D、

既不是树也不是二叉树正确答案：

C

参考解析：不含任何结点的空树是一棵树也是一棵二叉树。88、单选题下列关于线性表，二叉平衡树，哈希表存储数据的优劣描述错误的是()。A、

哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O（1）B、

线性表实现相对比较简单C、

平衡二叉树的各项操作的时间复杂度为O（logn）D、

平衡二叉树的插入节点比较快正确答案：

D

参考解析：平衡二叉树插入结点需要做平衡调整，会影响插入效率。89、单选题如果有N个节点用二叉树结构来存储，那么二叉树的最小深度是()。A、

以2为底N+1的对数，向下取整B、

以2为底N的对数，向上取整C、

以2为底2N的对数，向下取整D、

以2为底2N+1的对数，向上取整正确答案：

B

参考解析：如果有N个节点用二叉树结构来存储，那么二叉树的最小深度是以2为底N的对数，向上取整。90、单选题对于序列（12，13，11，18，60，15，7，19，25，100），用筛选法建堆，必须从值为()的数据开始建初始堆。A、

100B、

12C、

60D、

15正确答案：

C

参考解析：共十个数，N=10，筛选法建堆，开始节点为N/2=10/2=5，第五个数为60。91、单选题使用CIDR技术把4个C类网络158.15.12.0/24、158.15.13.0/24、158.15.14.0/24和158.15.15.0/24汇聚成一个超网，得到的网址是（）。A、

158.15.8.0/22B、

158.15.12.0/22C、

158.15.8.0/21D、

158.15.12.0/2