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

国家电网招聘-计算机(电网)真题库_141、单选题函数substr(“DATASTRUCTURE”，5，9)的返回值为()。A、

“STRUCTURE”B、

“DATA”C、

“DATASTR（江南博哥）UCTURE”D、

“ASTRUCTUR”正确答案：

A

参考解析：substr函数的作用是找到从第5个字符开始，长度为9的子串。2、单选题当出现拥塞时路由器会丢失报文，同时向该报文的源主机发送()类型的报文A、

TCP请求B、

TCP响应C、

ICMP请求与响应D、

ICMP源点抑制正确答案：

D

参考解析：当出现拥塞时路由器会丢失报文，同时向该报文的源主机发送ICMP源点抑制类型的报文。3、单选题二路归并排序的时间复杂度为()。A、

AB、

BC、

CD、

D正确答案：

C

参考解析：4、单选题设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是()。A、

n在m右方B、

n是m祖先C、

n在m左方D、

n是m子孙正确答案：

C

参考解析：中序遍历时，先访问左子树，再访问根结点。n在m前，则n必须在m的左子树中。5、单选题假定一棵度为3的树中结点数为50，则其最小高度应为()。A、

5B、

6C、

3D、

4正确答案：

A

参考解析：6、单选题一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是()。A、

43512B、

12345C、

54321D、

45321正确答案：

A

参考解析：此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序(指的是元素的序号)的两个元素。7、单选题在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作()型调整以使其平衡。A、

LLB、

LRC、

RLD、

RR正确答案：

C

参考解析：平衡二叉树是在构造=叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系。进行相应的旋转，使之成为新的平衡子树。具体步骤如下：(1)每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡=叉树没有失去平衡，继续插入、结点；(2)若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；(3)判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；(4)如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树。在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；(5)计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。结合上面的知识点，对于题目中的情况应该选择RL型调整。8、单选题两个字符串相等的充要条件是()。A.两个字符串中对应位置上的字符相等B.两个字符串的长度相等A、

同时具备B、

和C、

两个条件D、

两个字符串的大小相等正确答案：

C

参考解析：两个字符串相等是指两个字符串不仅长度相等，而且在对应位置上的字符也要相等。9、单选题m阶B+树中除根节点外，其他节点的关键字个数至少为()。A、

[m/2]B、

[m/2]-1C、

[m/2]+1D、

任意正确答案：

A

参考解析：这是B+树的定义。10、单选题A、

O(m×n×t)B、

O(m+n+t)C、

O(m×t+n)D、

O(m+n×t)正确答案：

A

参考解析：在程序段中，有两段循环程序，第一段是一个双层嵌套循环，另一个是三层嵌套循环，所以基本操作是c[i][j]=c[i][j]+a[i][k]×b[k][j]，此基本操作共执行m×t×n次。11、单选题下面关于图的遍历说法不正确的是()。A、

遍历图的过程实质上是对每个顶点查找其邻接点的过程B、

深度优先搜索和广度优先搜索对无向图和有向图都适用C、

深度优先搜索和广度优先搜索对顶点访问的顺序不同，它们的时间复杂度也不相同D、

深度优先搜索是一个递归的过程，广度优先搜索的过程中需附设队列正确答案：

C

参考解析：深度优先搜索和广度优先搜索的时间算杂度相同，均为O(n+e)。12、单选题对于栈操作数据的原则是()。A、

先进先出B、

后进先出C、

后进后出D、

不分顺序正确答案：

B

参考解析：栈的特点就是后进先出，入栈和出栈的操作只能在栈顸进行.而队列的特点是先进先出，这两点容易混淆，要注意区分。13、单选题在一台安装好TCP/IP协议的PC上，当网络连接不可用时，为了测试编写好的网络程序，通常使用的目的主机IP地址为()A、

B、

C、

D、

25正确答案：

B

参考解析：当网络连接不可用时，为了测试编写好的网络程序，通常使用的目的主机IP地址为（环回地址）。14、单选题广义表(a，b，(c，(d)))的表尾是()。A、

(b，(c，(d))B、

(b，(c，(d)))C、

(d)D、

(c，(d))正确答案：

B

参考解析：广义表的第一个表元素为表头，由表中除表头外的其他元素组成的表称为广义表的表尾。15、单选题若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G至少有()个顶点。A、

11B、

10C、

9D、

8正确答案：

B

参考解析：要使图的顶点数最少，应该尽量构造一个完全图，具有36条边的无向完全图的顶点数是9，又因为图示非连通的，所以再加一个孤立的顶点即可。所以至少有10个顶点。16、单选题已知二叉树的前序序列为ABCDEFG，中序序列为DBCAFEG，则后序序列为()。A、

DCBAFGEB、

DCBFGEAC、

DCBFEGAD、

DCBGFEA正确答案：

B

参考解析：本题考查的是二叉树的遍历过程。在本题中，由于前序遍历首先访问的是根结点，所以根结点是A，又由于后序遍历最后访问的是根结点，所以排除选项A；根据中序序列知道，DBC是左子树的结点，FEG是右子树的结点。17、单选题表长为n的顺序存储的线性表，当在任何位置上删除一个元素的概率相等时，删除一个元素所需移动元素的平均个数为()。A、

nB、

n/2C、

(n-1)/2D、

(n+1)/2正确答案：

C

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

(1)，(2)，(3)B、

(1)C、

(1)，(3)D、

(2)，(3)正确答案：

C

参考解析：19、单选题在一裸m阶的B+树中，每个非叶结点的儿子数S应满足()。A、

AB、

BC、

CD、

D正确答案：

A

参考解析：m阶B+树包含如下两个特点：(1)每个分支结点至多有m棵子树。(2)除根结点外的所有非终端结点每个结点至少有1(m+1)/21棵子树。20、单选题若对序列(tang，deng，an，wang，shi，bai，fang，liu)采用选择排序法按字典顺序进行排序，下面给出的四个序列中，()是第三趟的结果。A、

an.bai，deng，wang，tang，fang，shi，huB、

an，bai，deng，wang，shi，tang，fang，liuC、

an.bai，deng，wang，shi，fang，tang，liuD、

an.bai，deng，wang，shi，liu，tang，fang正确答案：

B

参考解析：选择排序是指每一趟从待排序的数据元素中选出最小(或最大)的一个元素，顺序地放在已排好序的数列的最后，直到待排序数据元素全部排完。按字典顺序排序的排序过程如下:第一趟:an,deng,tang,wang，shi,bai,fang,liu;.第二趟，an,bai,tang,wang，shi，deng,fang,liu;第三趟:an,bai，deng,wang，shi,tang,fang,liup第四趟:an,bai,deng,fang，shi,tang,wang,liu;第五趟，an,bai，deng,fang，liu,tang,wang，shi;第六趟:an,bai,deng,fang,liu,slu,wang,tang;第七趟:an.bai,deng,fang,liu,shi,tang,中ang。21、单选题有m个叶子结点的哈夫曼树所具有的结点数为()。A、

mB、

m+1C、

2mD、

2m-1正确答案：

D

参考解析：哈夫曼树中仅有度为0和2的结点，由二叉树的性质可知，具有m个叶子结点的哈夫曼树具有m-1个度为2的结点，因此，具有m个叶子结点的哈夫曼树所具有的节点数为2m-1。22、单选题二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是()。A、

先序遍历二叉树B、

判断两个指定位置的结点是否在同一层上C、

层次遍历二叉树D、

根据结点的值查找其存储位置正确答案：

B

参考解析：23、单选题设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为()。A、

AB、

BC、

CD、

D正确答案：

B

参考解析：24、单选题网络28/26的广播地址为(请作答此空)，可用主机地址数()A、

59B、

91C、

192.168.2l.224D、

55正确答案：

B

参考解析：网络28/26的广播地址为91，可用主机地址数62。25、单选题设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H(key)=keyMOD13，散列地址为1的链中有()个记录。A、

1B、

2C、

3D、

4正确答案：

D

参考解析：由散列函数H(key)=keyMOD13计算每个记录的散列地址，散列地址为1的关键字有14，1，27，79，共4个记录。26、单选题一个具有1025个结点的二叉树的高h为()。A、

11B、

10C、

11至1025之间D、

10至1024之间正确答案：

C

参考解析：在具有n个结点的二叉树中完全二叉树的树高最小，其为[logn]+1，单支二叉树，即每层只有一个结点，树高最大，其为n。因此，具有1025个结点的二叉树树高应在11至1025之间。27、单选题设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为()。A、

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

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

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

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

A

参考解析：快速排序的每趟排序在待排序列中选取一个数为基准，将序列划分为两段，一段的值比基准值小，另一段大于或等于基准值。在快速排序中通常有两个指针分别为i和j，j从后向前遍历，找第一个小于基准值的节点，将值交换，i从前向后遍历，找到第一个大于或等于基准值的节点，将值交换，重复此过程，直至i和j指向同一节点，一趟排序结束。28、单选题设一组初始记录关键字序列为(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，20，36，40，70，85D、

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

A

参考解析：归并排序的每趟排序将相邻的两个子序列合并，直至剩两个子序列，合并后产生一个序列，即为最终排序结果。29、单选题采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为()。A、

(n-1)/2B、

(n+1)/2C、

nD、

n/2正确答案：

B

参考解析：搜索的最好情况是第一个元素即想要查找的元素，最坏的情况是最后一个元素即想要查找的元素，所以平均查找长度是(n+l)/2。30、单选题某高度为k的完全二叉树中，所含叶子结点的个数最少为()。A、

AB、

BC、

CD、

D正确答案：

C

参考解析：31、单选题设二维数组A[6][0]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][0]的存储地址为860，则a[3][5]的存储地址为()。A、

1000B、

860C、

1140D、

1200正确答案：

A

参考解析：每个数组元素占用4个存储单元，按行优先顺序存放的数组元素，则a[3][5]的存储地址为860+(3×10+5)×4=1000。32、单选题可以用()、数据关系和基本操作集定义一个完整的抽象数据类型。A、

数据元素B、

数据对象C、

原子类型D、

存储结构正确答案：

B

参考解析：抽象数据类型可用(数据对象，数据关系，基本操作集)三元组来表示。33、单选题在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。A、

一定都是同义词B、

一定都不是同义词C、

不一定都是同义词D、

都相同正确答案：

C

参考解析：采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。34、单选题以下与数据的存储结构无关的术语是()。A、

循环队列B、

链表C、

哈希表D、

栈正确答案：

D

参考解析：数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构，它们是数据的两种最基本的存储结构。ABC三项，都属于链式存储结构。D项，栈则是指从应用的角度来说的一种后进先出的线性表结构，与具体的存储结构无关。35、单选题模拟信号调制为模拟信号时，由于基带信号包含许多低频信息或直流信息，而很多传输介质并不能传输这些信息，因此需要使用调制器对基带信号进行调制，下面选项中不属于模拟信号调制为模拟信号方法的是()。A、

调波B、

调幅C、

调频D、

调相正确答案：

A

参考解析：*模拟信号调制为模拟信号的方法有：调幅（AM）：依据传输的原始模拟数据信号变化来调整载波的振幅。调频（FM）：依据传输的原始模拟数据信号变化来调整载波的频率。调相（PM）：依据传输的原始模拟数据信号变化来调整载波的初始相位。36、单选题SMTP使用的端口号是()A、

21B、

23C、

25D、

110正确答案：

C

参考解析：SMTP使用的端口号是25。37、单选题设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3]存放在什么位置？脚注(10)表示用10进制表示。()A、

678B、

688C、

692D、

696正确答案：

C

参考解析：A[2][2]是A[0][0]后面的第2n+2个元素，即2n+2=676-644，解得n=15。A[3][3]是A[2][2]后面的第n+1个元素，676+n+1=692，则A[3][3]存放位置是692。38、单选题下面关于Prim算法和KruskAl算法的时间复杂度正确的是()。A、

Prim算法的时间复杂度与网中的边数有关，适合于稀疏图B、

Prim算法的时间复杂度与网中的边数无关，适合于稠密图C、

KruskAl算法的时间复杂度与网中的边数有关，适合于稠密图D、

KruskAl算法的时间复杂度与网中的边数无关，适合于稀疏图正确答案：

B

参考解析：39、单选题线性表采用链接存储时，其地址()。A、

必须是连续的B、

部分地址必须是连续的C、

一定是不连续的D、

连续与否均可以正确答案：

D

参考解析：线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。40、单选题下面几个符号串编码集合中，不是前缀编码的是()。A、

{0，10，110，1111}B、

{11，10，001，101，0001}C、

{00，010，0110，1000}D、

{b，c，aa，aba，abb，abc}正确答案：

B

参考解析：前缀编码的定义：任一个字符的编码都不是另一个字符的编码的前缀。B选项中10是101的前缀，因此其不是前缀编码。41、单选题二叉排序树中左子树上所有结点的值均()根结点的值。A、

＜B、

=C、

＞D、

！=正确答案：

A

参考解析：二叉排序树的左子树的结点的值全部小于根结点的值，并且根结点的值小于右子树左右结点的值。42、单选题以下关于查找方法的说法正确的是()。Ⅰ.顺序查找法只能在顺序存储结构上进行Ⅱ.二分查找法可以在有序的双向链表上进行Ⅲ.分块查找的效率与线性表被分为多少块有关A、

Ⅰ、ⅡB、

Ⅱ、ⅢC、

Ⅰ、ⅢD、

只有Ⅲ正确答案：

D

参考解析：顺序查找法可以在顺序存储结构和链式存储结构上进行，而二分查找只能在顺序存储的有序表上进行即可以进行随机存取的存储结构上进行。43、单选题时间复杂度不受数据初始状态影响而恒为0(nlog2n)的是()。A、

堆排序B、

快速排序C、

希尔排序D、

冒泡排序正确答案：

A

参考解析：堆排序无论是最好情况还是最坏情况，时间复杂度都是相等的。44、单选题下列排序算法中，()算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。A、

堆排序B、

冒泡排序C、

快速排序D、

插入排序正确答案：

D

参考解析：插入排序在最后一个元素被插入时，所有元素都要后移，即在最后一趟开始之前，所有元素都不在其最终的位置上。45、单选题A[N，N]是对称矩阵，将下三角(包括对角线)以行序存储到一维数组T[N(N+l)/2]q中，则对任一上三角元素A[i][j]对应T[k]的下标k是()。A、

i(1-1)/2+jB、

j(j-1)/2+iC、

i(j-i)/2+1D、

j(1-1)/2+1正确答案：

B

参考解析：将对称矩阵A[N，N]下三角以行序存储到一维数组T[N(N+1)/2]中。对应的A[i][j]啪与T[k]的下标k的关系为k=i(i-1)/2+j；但题目中是求任一上三角元素A[i][j]对应T[k]的下标k，在对称矩阵中A[i][D]=A[i][i]，即上三角中的元素的A[i][j]存储位置对应下三角A[i][j]的存储位置，所以k=j(j-1)/2+i。46、单选题如果一棵二叉树结点的先根遍历序列是A、B、C，后根遍历序列是C、B、A，则该二叉树结点的中根遍历序列()。A.必为A、B、CB.必为A、C、BA、

必为B、

C、

AD、

不能确定正确答案：

D

参考解析：47、单选题以下关于TCP/IP协议和层次对应关系的表示，正确的是()A、

AB、

BC、

CD、

D正确答案：

A

参考解析：TCP和UDP均基于IP协议协议栈中的传输层协议，其中TCP是面向连接的，UDp是无连接的。48、单选题由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)为()。A、

27B、

38C、

51D、

75正确答案：

D

参考解析：49、单选题对于一个长度为n的任惫表进行排序，至少需要进行的比较次数是()。A、

AB、

BC、

CD、

D正确答案：

D

参考解析：50、单选题向一个带头结点HS的链栈中插入一个s所指结点时需执行()。A、

HS-＞next=s；B、

s-＞next=HS-＞next；HS-＞next=s；C、

s-＞next=HS：HS=s；D、

s-＞next=HS；HS=HS-＞next；正确答案：

B

参考解析：为了将结点s插入到带头结点HS的链栈中，首先需要修改s的指针域，使得s的下一个结点为链栈中的第一个有效结点，即数据域中存放有效数据的结点，该结点可由HS的指针域获得，因此相应的语句为s-＞next=HS-＞next，之后使s结点成为链栈中的第一个有效结点，即HS的指针域指向s，相应的语句为HS-＞next=S。51、单选题A、

iB、

n-iC、

n-i+lD、

不确定正确答案：

C

参考解析：根据题中所叙述情况，栈的输出序列一定是输入序列的逆序。52、单选题以下哪一个不是栈的基本运算()。A、

删除栈顶元素B、

删除栈底元素C、

判断栈是否为空D、

将栈置为空栈正确答案：

B

参考解析：栈的基本运算有人栈、出栈(删除栈顶元素)、初始化、置空、判断是否为空或满、提取栈顶元素等，对栈元素的操作都是在栈顶进行的53、单选题假设执行语句S的时间为0(1)，则执行下列程序段的时间为()。for(i=l;k=n;it+)for(j=l;jA、

0(n)B、

0(n^2)C、

O(n×i)D、

0(n+1)正确答案：

B

参考解析：观察可知，程序段S的执行频度为T(n)=n^2，得时间复杂度T(n)=O(n^2)。54、单选题在一个单链表HL中，若要向表头插入一个由指针P指向的结点，则执行()。A、

HL=P；P—＞next=HL；B、

P—＞next=HL；HL=P；C、

P—＞next=HL；P=HL；D、

P—＞next=HL—＞next；HL—＞next=P；正确答案：

B

参考解析：根据插入运算的定义，需要修改头指针HL，令其指向结点P，同时结点P的指针域应指向原来的头结点。修改了头指针HL会影响后面操作，所以必须先将P的指针域指向头结点(P—＞next=HL)，再修改HL(即HL=P)。55、单选题快速排序最易发挥其长处的情况是()。A、

被排序的数据中含有多个相同排序码B、

被排序的数据已基本有序C、

被排序的数据完全无序D、

被排序的数据中的最大值和最小值相差悬殊正确答案：

C

参考解析：56、单选题已知有一维数组A[0.m×n-1]，若要对应为m行n列的矩阵，则下面的对应关系()，可将元素A[k](O≤＜k≤＜m×n)表示成矩阵的第i行、第j列的元素(0≤i≤m，0匀≤n)。A、

i=k/n，j=k%mB、

i=k/m，j=k%mC、

i=k/n，j=k%nD、

i=k/m，j=k%n正确答案：

C

参考解析：矩阵每一行有n个元素，则第i+l行、第j+l到的元素～在A中是第n×i+j+l个元素，对应的下标k=nXi+j(因为下标从0开始)。反过来：i=k/n，j=k%n。57、单选题A、

{(1，4)，(2，3)，(2，5)}B、

{(3，5)，(3，4)，(4，5)}C、

{(1，3)，(3，4)，(3，5)}D、

{(2，3)，(3，4)，(2，5)}正确答案：

A

参考解析：58、单选题在TCP/IP协议体系结构中，网际层的主要协议为()A、

IPB、

TCPC、

HTTPD、

SMTP正确答案：

A

参考解析：在TCP/IP协议体系结构中，网际层的主要协议为IP。59、单选题A、

21/7B、

28/7C、

15/6D、

21/6正确答案：

A

参考解析：60、单选题设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为()。A、

aedfcbB、

aedfbcC、

aebcfdD、

acfebd正确答案：

A

参考解析：61、单选题关于AVL(平衡二叉树)，下列说法错误的是()。A、

左子树与右子树高度差最多为1B、

插入操作的时间复杂度为0(logn)C、

平衡二叉树是二叉排序树中的一种D、

使用平衡二叉树的目的是为了节省空间正确答案：

D

参考解析：平衡二叉树是平衡二又排序树的简称。它或者是一棵空树，或者是具有下列性质的二叉树：①左、右子树的高度之差不超过1；②左、右子树也是平衡二叉树；平衡二叉树没有节省空间，引入其目的是防止排序二叉树左、右子树高度失衡。62、单选题A、

3B、

6C、

9D、

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

A

参考解析：邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V，E)是具有n个顶点的图，顶点序号依次为l，2，……，n，则G的邻接矩阵是n阶方阵，所以该图有3个顶点。63、单选题如果结点A有3个兄弟，B是A的双亲，则结点B的度是()A、

3B、

4C、

1D、

2正确答案：

B

参考解析：结点A有3个兄弟，B是A的双亲，则结点B的度是4。64、单选题用s表示入栈操作，*表示出栈操作，栈的初态、终态均为空，人栈和出栈的操作序列可表示成仅为由S和*组成的序列。下面的序列中合法的操作序列有()。A、

S*SS*S**B、

SSS****SC、

S**S*SS*D、

SSS*S*S*正确答案：

A

参考解析：要使栈的初态、终态均为空，入栈和出栈的操作次数应该相等，因此排除D项。而BC两项项都出现某一时刻栈已空的情况下执行出栈操作。65、单选题先序遍历序列和中序遍历序列相同的二叉树为()。A、

根结点无左子树的二叉树B、

根结点无右子树的二叉树C、

只有根结点的二叉树或非子结点只有左子树的二叉树D、

只有根结点的二叉树或非叶子结点只有右子树的二叉树正确答案：

D

参考解析：先序遍历的次序为根一左一右，而中序遍历的次序为左一根一右，树中肯定有根结点，要使先序遍历序列和中序遍历序列相同，两种遍历次序可以相同的次序为根一右。所以满足条件的树为只有根结点的二叉树或非叶子结点只有右子树的二叉树。66、单选题设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为()。A、

AB、

BC、

CD、

D正确答案：

C

参考解析：数组是随机存取的结构，所以读取第i个节点的时间复杂度为0(1)。67、单选题A、

AB、

BC、

CD、

D正确答案：

C

参考解析：68、单选题设二叉排序树中关键字由1～1000的整数构成，现要查找关键字为363的结点，下列关键字序列不可能是在二叉排序树上查找到的序列是()。A、

2，252，401，398，330，344，397，363B、

924，220，911，244，898，258，362，363C、

925，202，911，240，912，245，363D、

2，399，387，219，266，382，381，278，363正确答案：

C

参考解析：把这四个序列各插入到一个初始为空的二叉排序树中，可以发现，C序列形成的不是一条路径，而是有分支的，可见它是不可能在查找过程中访问到的序列。69、单选题可支持10公里以上传输距离的介质是()A、

同轴电缆B、

双绞线C、

多模光纤D、

单模光纤正确答案：

D

参考解析：可支持10公里以上传输距离的介质是单模光纤。70、单选题假设有k个关键字互为同义词，若用线性探查法把这k个关键字存入，至少要进行的探查次数是()。A、

k-1B、

kC、

k+1D、

k(k+1)/2正确答案：

D

参考解析：假设有k个关键字互为同义词，若用线性探查法把这k个关键字存入，探查次数最少的情况是第1个关键字通过1次比较后插入，第2个关键字通过2次比较后插入，…，第k个关键字通过k次比较后插入。总的比较次数=1+2+…+k=k(k+1)/2。71、单选题引入二叉线索树的目的是()。A、

加快查找结点的前驱或后继的速度B、

为了能在二叉树中方便地进行插入与删除C、

为了能方便地找到双亲D、

使二叉树的遍历结果唯一正确答案：

A

参考解析：当以二叉链表作为存储结构存储非线索化的二叉树时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一遍历序列中的直接前驱和直接后继的结点信息，这种信息只有在遍历的动态过程中才能得到。二叉线索树利用空链域存放结点的前驱和后继结点的信息，这样能保存遍历过程中得到的信息。可见，引入二叉线索树的目的是方便查找结点的前驱或后继结点的速度。72、单选题堆排序分为两个阶段，其中第一阶段将给定的序列建成一个堆，第二阶段逐次输出堆顶元素。设给定序列{48，62，35，77，55，14，35，98}，若在堆排序的第一阶段将该序列建成一个堆(大根堆)，那么交换元素的次数为()。A、

5B、

6C、

7D、

8正确答案：

B

参考解析：73、单选题KMP算法的特点是在模式匹配时指示主串的指针()。A、

不会变大B、

不会变小C、

都有可能D、

无法判断正确答案：

B

参考解析：在KMP算法中，模式匹配时主串不会回溯，所以主串的指针不会变小。74、单选题若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵()。A、

第i行中值为1的元素个数B、

所有值为1的元素个数C、

第i行及第i列中值为1的元素总个数D、

第i列中值为l的元素个数正确答案：

D

参考解析：对于无向图，其邻接矩阵的第i行的和即为第i个顶点的度。对于有向图，邻接矩阵的第i行元素的和即为第i个顶点的出度，而邻接矩阵的第j列元素的和即为第j个顶点的出度。75、单选题树形结构的特点是：一个结点可以有()。A、

多个直接前驱B、

多个直接后继C、

多个前驱D、

一个后继正确答案：

B

参考解析：树的唯一根节点无前驱，叶子结点可以有多个且无后继，树的其他结点可以有多个后继但只能有一个前驱。76、单选题采用开放定址法处理散列表的冲突时，其平均查找长度()。A、

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

高于二分查找C、

低于链接法处理冲突D、

高于链接法处理冲突正确答案：

D

参考解析：开放定址法处理冲突的平均查找长度高于链接法。77、单选题文件有m个初始归并段，采用k路归并时，所需的归并遍数是()。A、

AB、

BC、

CD、

D正确答案：

D

参考解析：本题考查归并排序时间复杂度相关问题。根据归并排序的特点可以得到答案。78、单选题一组记录的关键字为{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，50，35，80，85，20，36，40，70D、

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

A

参考解析：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。79、单选题二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是()A、

EB、

FC、

GD、

H正确答案：

C

参考解析：80、单选题某学校为防止网络游戏沉迷，通常采用的方式不包括()A、

安装上网行为管理软件B、

通过防火墙拦截规则进行阻断C、

端口扫描，关闭服务器端端口D、

账户管理，限制上网时长正确答案：

C

参考解析：通过端口扫描，关闭服务器端端口方法不能有效阻止代理上网，游戏。81、单选题字符串的长度是指()。A、

串中不同字母的个数B、

串中字符不同的个数C、

串中不同数字的个数D、

串中所含字符的个数正确答案：

D

参考解析：字符串的长度是指串中所含的字符的个数。82、单选题利用二叉链表存储树，则根结点的右指针为()。A、

指向最左孩子B、

指向最右孩子C、

空D、

非空正确答案：

C

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

AB、

BC、

CD、

D正确答案：

D

参考解析：考查双链表中插入操作，要注意保存后继节点。84、单选题设n阶方阵是一个上三角矩阵，则需存储的元素个数为()。A、

nB、

n×nC、

n×n/2D、

n(n+1)/2正确答案：

D

参考解析：在上三角矩阵中，第一行有1个元素，第二行有2个元素，…，第n行有n个元素，则共n(n+1)/2个。85、单选题下列程序段的时间复杂度为()。for(i=0；i＜m；i++)for(j=0；j＜t；j++)e[i][j]=0；for(i=0；i＜m；i++)for(j=0；j＜t；j++)for(k=0；k＜n；k++)c[i][j]_c[i][j]+a[i][k]×b[k][j]；A、

O(m×n×t)B、

O(m+n+t)C、

O(m×t+n)D、

O(m+n×t)正确答案：

A

参考解析：在程序段中，有两段循环程序，第一段是一个双层嵌套循环，另一个是三层嵌套循环，所以基本操作是c[i][j]=c[i][j]+a[i][k]×b[k][j]，此基本操作共执行m×t×n次。86、单选题要求内存量最大的排序算法是()。A、

插入排序B、

选择排序C、

快速排序D、

归并排序正确答案：

D

参考解析：选择排序和插入排序的空间复杂度为O(1)；快速排序中的递归所耗费的栈空间在最好情况下也为O(logn)；归并排序中，由于每一趟都要一个TR数组来复制，所以需要与待排记录等量的辅助空间为O(n)。87、单选题以下数据结构中哪一个是非线性结构？()A、

线性表B、

栈C、

队列D、

二叉树正确答案：

D

参考解析：线性表、栈、队列都是线性结构，树、图是非线性结构。88、单选题设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n.则这棵二叉中共有()个结点。A、

2n+1B、

n+1C、

2n-1D、

2n正确答案：

C

参考解析：在二叉树中度为2的结点个数为度为零的结点数减一，所以二叉树共有2n-1个结点。89、单选题由圈权值为的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为()。A、

23B、

37C、

44D、

46正确答案：

C

参考解析：90、单选题二维数组A的每个元素是由6个字符组成的串，行下标的范围从0～8，列下标的范围是从0～9，则存放A至少需要()个字节。A、

240B、

540C、

90D、

180正确答案：

B

参考解析：数组A为9行10列，共有90个元素，所以，存放A至少需要90×6=540个存储单元。91、单选题以下关于路由器和交换机的说法中，错误的是()A、

为了解决广播风暴，出现了交换机B、

三层交换机采用硬件实现报文转发，比路由器速度快C、

交换机实现网段内帧的交换，路由器实现网段之间报文转发D、

交换机工作在数据链路层，路由器工作在网络层正确答案：

A

参考解析：路由器用于解决网络风暴。92、单选题已知一算术表达式的中