文档内容
数据结构与算法
即刻题库 www.jike.vip
1 、 单选题
非空的循环单链表head的尾结点P满足的条件是()。
A ： P.link=head
B ： p.link=NIL
C ： p=NIL，
D ： p=head
正确答案： A
解析：
对于循环单链表来说尾结点的指针指向第一个元素。
2 、 单选题
下列()是一个堆。
A ： 19，75，34，26，97，56
B ： 97，26，34，75，19，56
C ： 19，56，26，97，34，75
D ： 19，34，26，97，56，75
正确答案： D
解析：
3 、 单选题设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进
入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是()。
A ： 1
B ： 2
C ： 3
D ： 4
正确答案： C
解析：
出队的顺序也是出栈的顺序，由此顺序可以推出栈的容量最小值。
4 、 单选题
下面的说法中，不正确的是()。
A ： 广义表是一种共享结构
B ： 广义表是一种递归
C ： 广义表是一种多层次的结构
D ： 广义表是一种非线性结构
正确答案： D
解析：
从各层元素各自具有的线性关系讲，广义表属于线性结构。
5 、 单选题
下列与数据元素有关的叙述中，哪一项是不正确的()。
A ： 数据元素是数据的基本单位，即数据集合中的个体
B ： 数据元素是由独立含义的数据最小单位
C ： 数据元素又称为节点
D ： 数据元素又称为记录
正确答案： B
解析：
数据元素是数据的基本单位，即数据集合中的个体。有些情况下也把数据元素称为节点、
记录、表目等。一个数据元素可由一个或多个数据项组成，数据项是由独立含义的数据
最小单位。
6 、 单选题
设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为()。
A ： s-＞next=rear；rear=s；
B ： front-＞next=s；front=s；
C ： rear-＞next=s；rear=s；
D ： s-＞next=front；front=s；
正确答案： C
解析：
向队列插入元素，即入队操作，应该在队尾进行，所以需要修改尾指针，实现新结点的
人队。
7 、 单选题
A ： 3
B ： 6
C ： 9
D ： 以上答案均不正确
正确答案： A
解析：
邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V，E)是具有n个顶点的图，顶点序号
依次为1，2，……，n，则G的邻接矩阵是n阶方阵，所以该图有3个顶点。
8 、 单选题
设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，
则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为()。
A ： aedfcb
B ： aedfbc
C ： aebcfd
D ： acfebd
正确答案： A
解析：9 、 单选题
设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是()。
A ： n在m右方
B ： n是m祖先
C ： n在m左方
D ： n是m子孙
正确答案： C
解析：
中序遍历时，先访问左子树，再访问根结点。n在m前，则n必须在m的左子树中。
10 、 单选题
假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点v相关的所有弧
的时间复杂度是()。
A ： O(n)
B ： O(e)
C ： O(n+e)
D ： O(n×e)
正确答案： C
解析：
由有向图的邻接表存储结构可知，每个顶点v链接的顶点只包含从v发出的弧所指向的顶
点，不包含指向v的弧所对应的尾结点。又因为邻接表的结点数是边数与顶点数的总和，
所以要删除与某个顶点相关的所有弧时间复杂度为O(n+e)。
11 、 单选题
对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是()。
A ： head==NUL1
B ： head→next==NULL
C ： head→next==headD ： head！=NULL
正确答案： B
解析：
带头结点的单链表为空的条件就是头结点的指针域为空，用语句表示就
是head→next==NULL。
12 、 单选题
下列的叙述不正确的个数是()。(1)9阶B-树，除根以外的任一结点的关键字个数不少
于4(2)理想情况下，在散列表中查找一个元素的时间复杂度为0(1)(3)在采用线性探测法
处理冲突的散列表中，所有同义词在表中相邻(4)在索引顺序表的查找中，对索引表既可
以采用顺序查找方法，也可采用=分查找方法
A ： 1
B ： 2
C ： 3
D ： 4
正确答案： A
解析：
如果发生多次冲突，则同义词在表中就不会相邻，因此(3)是错误的，其它正确。
13 、 单选题
设一棵二叉树的深度为k，则该二叉树中最多有()个结点。
A ： 1
B ： 2k-1
C ： 2
D ： k-1
正确答案： B
解析：
一棵深度为k的二叉树，结点最多为2k-1个。
14 、 单选题
下列程序段的时间复杂度为()。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次。
15 、 单选题
设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为()。
A ： 第i列0元素的个数之和
B ： 第i列非0元素的个数之和
C ： 第i行0元素的个数之和
D ： 第i行非0元素的个数之和
正确答案： B
解析：
考察图的邻接矩阵的特点，在有向图的邻接矩阵中，第i列非0元素的个数之和即为第i个
节点的入度。
16 、 单选题
设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找
长度为()。
A ： 5
B ： 11
C ： 7
D ： 6.5
正确答案： D
解析：
分块查找是先在索引下进行查找，找到该元素可能存在的块号，然后在块中顺序查找。
则本题的平均查找长度为(5+1)/2+(6+1)/2=6.5。
17 、 单选题
在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机
将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区
应该是一个()结构。A ： 栈
B ： 队列
C ： 数组
D ： 线性表
正确答案： B
解析：
对于请求打印机的任务，应该满足先请求先处理，即先进先出，满足队列的性质。
18 、 单选题
线索化的二叉树中，某结点*P没有孩子的充要条件是()。
A ： p-＞lchild=NULL
B ： p-＞ltag=l&&p-＞rtag=1
C ： p-＞ltag=0
D ： p-＞lchild=NULL&&p-＞ltag=1
正确答案： B
解析：
考查线索二叉树。
19 、 单选题
下面关于求关键路径的说法不正确的是()。
A ： 求关键路径是以拓扑排序为基础的
B ： 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C ： 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续
时间的差
D ： 关键活动一一定位于关键路径上
正确答案： C
解析：
最迟开始时间应等于本工作的最迟完成时间与其持续时间之差。
20 、 单选题
在一个具有n个顶点的无向图中，要连通全部顶点至少需要()条边。
A ： n
B ： n+lC ： n-l
D ： n/2
正确答案： C
解析：
假设每顶点都和其他顶点有边，则至少需要n-l条边将所有顶点连通。
21 、 单选题
对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的
子孙的最大层次为()。
A ： h或h+1
B ： 任意
C ： h
D ： h+1
正确答案： A
解析：
叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下子孙的最大层次
为l，则其左分支下子孙的最大层次必为1或1+1满二叉树：一棵深度为k.且有2的(k)次方
－1个节点的二叉树特点：每一层上的结点数都是最大结点数。
22 、 单选题
设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为()。
正确答案： C
解析：
数组是随机存取的结构，所以读取第i个节点的时间复杂度为0(1)。
23 、 单选题
在一个无向图中，所有顶点的度数之和等于所有边数()倍。
A ： 1/2
B ： 2C ： 1
D ： 4
正确答案： B
解析：
无向图中每条边都有两个顶点，所以所有顶点的度数之和等于所有边数的2倍。
24 、 单选题
求解Hanoi问题时，若初始有5个圆盘，则移动圆盘的次数是()。
A ： 7
B ： 15
C ： 31
D ： 5
正确答案： C
解析：
25 、 单选题
以下关于查找方法的说法正确的是()。Ⅰ.顺序查找法只能在顺序存储结构上进行Ⅱ.二分
查找法可以在有序的双向链表上进行Ⅲ.分块查找的效率与线性表被分为多少块有关
A ： Ⅰ、Ⅱ
B ： Ⅱ、Ⅲ
C ： Ⅰ、Ⅲ
D ： 只有Ⅲ
正确答案： D
解析：
顺序查找法可以在顺序存储结构和链式存储结构上进行，而二分查找只能在顺序存储的
有序表上进行即可以进行随机存取的存储结构上进行。
26 、 单选题
设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升
序的第一趟冒泡排序结束后的结果是()。
A ： D，C，R，F，Q，M，S，Y，P，H，X
B ： P，A，C，S，Q，D，F，X，R，H，M，YC ： F，H，C，D，P，A，M，Q，R，S，Y，X
D ： H，C，Q，P，A，M，S，R，D，F，X，Y
正确答案： D
解析：
每一趟冒泡排序从第一个元素开始，相邻的两个元素进行比较，若是降序则进行交换，
一趟排序完成后，值最大的元素被移至序列的末尾。
27 、 单选题
对于具有n个顶点、6条边的图()。
A ： 采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2)
B ： 进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关
C ： 采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)
D ： 进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关
正确答案： A
解析：
28 、 单选题
字符串的长度是指()。
A ： 串中不同字母的个数
B ： 串中字符不同的个数C ： 串中不同数字的个数
D ： 串中所含字符的个数
正确答案： D
解析：
字符串的长度是指串中所含的字符的个数。
29 、 单选题
若一个栈的输入序列为1，2，3…，n，输出序列的第一个元素是i，则第j个输出元素是()。
A ： i-j-1
B ： i-j
C ： j-i+l
D ： 不确定
正确答案： D
解析：
栈是一种后进先出的线性表结构，但本题无法确定输入和输出的时间顺序，即不一定是
在所有元素输入栈后再进行输出。
30 、 单选题
设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链
地址法构造散列表，散列函数为H(key)=keyMOD13，散列地址为1的链中有()个记录。
A ： 1
B ： 2
C ： 3
D ： 4
正确答案： D
解析：
由散列函数H(key)=keyMOD13计算每个记录的散列地址，散列地址为1的关键字
有14，1，27，79，共4个记录。
31 、 单选题
与单链表相比，双链表的优点之一是()。
A ： 插入、删除操作更简单
B ： 可以进行随机访问
C ： 可以省略表头指针或表尾指针D ： 访问前后相邻结点更灵活
正确答案： D
解析：
对于插入、删除操作单链表更简单，因为需要改动的指针域少，而随机访问是顺序表的
特点。无论是单链表还是双链表都要有表头指针或表尾指针，在双链表中可以访问任一
结点的前后相邻结点，而单链表中只能访问任意结点的后继结点。
32 、 单选题
正确答案： D
解析：
33 、 单选题
在散列函数H(k)=kmodm中，一般来讲，m应取()。
A ： 素数
B ： 充分大的数
C ： 奇数
D ： 偶数
正确答案： A
解析：
一般建议m取素数。34 、 单选题
在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在
一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有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
解析：
35 、 单选题
下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位亘上的是()。
A ： 堆排序
B ： 冒泡排序
C ： 快速排序
D ： 直接插入排序
正确答案： D
解析：
起泡排序和堆排序一趟排序后，在序列两端应该有最大或最小值。快速排序一趟排序后，
用来划分的元素位置不变。直接插人排序在已经排序好的序列的适当位置上插入关键字，
因此可能需要移动元素。
36 、 单选题
采用开放定址法处理散列表的冲突时，其平均查找长度()。
A ： 与链接法处理冲突相同
B ： 高于二分查找
C ： 低于链接法处理冲突
D ： 高于链接法处理冲突
正确答案： D
解析：开放定址法处理冲突的平均查找长度高于链接法。
37 、 单选题
设二维数组A[6][0]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元
素，a[0][0]的存储地址为860，则a[3][5]的存储地址为()。
A ： 1000
B ： 860
C ： 1140
D ： 1200
正确答案： A
解析：
每个数组元素占用4个存储单元，按行优先顺序存放的数组元素，则a[3][5]的存储地址
为860+(3×10+5)×4=1000。
38 、 单选题
顺序查找法适合于()结构的线性表。
A ： 哈希存储
B ： 顺序存储或链式存储
C ： 压缩存储
D ： 索引存储
正确答案： B
解析：
顺序查找法适合于线性表(不论线性表采用顺序存储还是链式存储)。而哈希存储查找是
根据哈希函数值直接查找。压缩存储是通过对应关系进行查找。索引存储是通过索引表
进行查找。
39 、 单选题
在循环队列中用数组A[0.m-1]存放队列元素，其队头和队尾指针分别为front和rear，则
当前队列中的元素个数是()。
A ： (front-rear+1)%m
B ： (rear-front+1)%m
C ： (front-rear+m)%m
D ： (rear-front+m)%m
正确答案： D解析：
D选项即为计算当前队列元素个数的公式。
40 、 单选题
设顺序循环队列Q[M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的当
前位置，尾指针R总是指向队尾元素的前一位置，则该循环队列中的元素个数为()。
A ： (F-R+M)%M
B ： F-R
C ： (R-F+M)%M
D ： R-F
正确答案： C
解析：
(R-F+M)%M是计算顺序循环队列元素个数的公式。
41 、 单选题
在长度为n(Il＞1)的()上，删除第一个元素.其时间复杂度为O(n)。
A ： 只有首结点指针的不带头结点的循环单链表
B ： 只有尾结点指针的不带头结点的循环单链表
C ： 只有尾结点指针的带头结点的循环单链表
D ： 只有头结点的循环单链表
正确答案： A
解析：
只有首结点指针的不带头结点的循环单链表删除第一个元素，需要遍历整个链表，因
此A项的时间复杂度为O(n)，BCD三项的时间复杂度都为O(1)。
42 、 单选题
散列技术中的冲突指的是()。
A ： 两个元素具有相同的序号
B ： 数据元素过多
C ： 两个元素的键值不同，而其他属性相同
D ： 不同键值的元素对应于相同的存储地址
正确答案： D
解析：
散列技术中的冲突指的是不同键值的元素对应于相同的存储地址。43 、 单选题
正确答案： C
解析：
44 、 单选题
设顺序表的长度为n，则顺序查找的平均比较次数为()。
A ： (n-1)/2n
B ： n/2
C ： (n+1)/2
D ： n
正确答案： C
解析：
顺序查找是顺序遍历查找表，直至找到或查找失败，所以最好的情况是第一个节点即想
找的元素，最坏的情况是查找失败，所以平均查找次数为(n+1)/2。
45 、 单选题
设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过
()。正确答案： C
解析：
利用二分查找法最多log2n+1次。
46 、 单选题
在单链表中，指针p指向结点A，若要删除A之后的结点(存在)，则指针的操作方式为()。
A ： p—＞next=p—＞next—＞next
B ： p=p—＞next
C ： p=p—＞next—＞next
D ： p-＞next-p
正确答案： A
解析：
要在单链表中删除p指向的结点的后继结点，需要将后继结点的后继交给p所指结点的指
铲域。具体实现语句为p—＞next=p—＞next—＞next。
47 、 单选题
对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是()。
正确答案： D
解析：
若采用邻接矩阵存储，则该矩阵的大小是n的平方。
48 、 单选题分别以下列序列构造=叉排序树，与用其他三个序列所构造的结果不同的是()。
A ： (100，80，90，60，120，110，130)
B ： (100，120，110，130，80，60，90)
C ： (100，60，80，90，120，110，130)
D ： (100，80，60，90，120，130，110)
正确答案： C
解析：
二叉排序树的特点：左子树的结点小于根结点，右子树的结点大于根结点。由其特点
得C得到的结果与其他三个序列构造的结果不同。
49 、 单选题
下面关于m阶B-树说法正确的是()。①每个结点至少有两棵非空子树；②树中每个结点至
多有m-l个关键字；③所有叶子在同一层上；④当插入一个数据项引起B树结点分裂后，
树长高一层。
A ： ①②③
B ： ②③
C ： ②③④
D ： ③
正确答案： B
解析：
50 、 单选题
深度为k的完全二叉树中最少有()个结点。
A ： k-1
B ： 2
C ： k+1D ： 2-1
正确答案： B
解析：
最少有两个结点，一个为根结点，另一个为根结点的左子树。
51 、 单选题
以数组Q[0…m-1]存放循环队列中的元素，若变量front和qulen分别指示循环队列中队头
元素的实际位置和当前队列的长度，则队尾元素的实际位置是()。
A ： front+qulen-1
B ： (front+qulen)modm
C ： (front+qulen-1)modm
D ： front+qulen
正确答案： C
解析：
循环队列的元素顺序存储在数组Q中，已知循环队列中队头元素的存储位置为front。当
前队列的长度为qulen，队尾元素的位置要在front上加上qulen，然后减l(第一个元素存
储在front的位置上)，对于循环队列求队尾的位置还要对总长度求余，所以队尾元素的
实际位置为(front+qulen-1)modm。
52 、 单选题
设计一个判别表达式中左右括号是否配对出现的算法，采用()数据结构最佳。
A ： 线性表的顺序存储结构
B ： 队列
C ： 线性表的链式存储结构
D ： 栈
正确答案： D
解析：
使用栈解决此问题的方法是：把表达式依次压入栈，当压入的是右括号时，就退栈直到
退出一个左括号，若最终栈空，则表示配对出现。
53 、 单选题
利用直接插入排序法的思想建立一个有序线性表的时间复杂度为()。正确答案： D
解析：
54 、 单选题
若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G至少有()个顶点。
A ： 11
B ： 10
C ： 9
D ： 8
正确答案： B
解析：
要使图的顶点数最少，应该尽量构造一个完全图，具有36条边的无向完全图的顶点数
是9，又因为图示非连通的，所以再加一个孤立的顶点即可。所以至少有10个顶点。
55 、 单选题
对任意7个关键字进行排序，至少要进行()次关键字之间的两两比较。
A ： 13
B ： 14
C ： 15
D ： 16
正确答案： C
解析：
56 、 单选题
用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为()。
正确答案： D
解析：
57 、 单选题
在顺序表(3，6，8，10，12，15，16，18，21，25，30)中，用二分法查找关键值11，
所需的关键码比较次数为()。
A ： 2
B ： 3
C ： 4
D ： 5
正确答案： C
解析：
用二分法查找关键值11比较的元素依次是15，12，10，8，共比较4次。
58 、 单选题
下列四个序列中，()是堆。
A ： 75，65，30，15，25，45，20，10
B ： 75，65，45，10，30，25，20，15
C ： 75，45，65，30，15，25，20，10
D ： 75，45，65，10，25，30，20，15
正确答案： C
解析：59 、 单选题
引入二叉线索树的目的是()。
A ： 加快查找结点的前驱或后继的速度
B ： 为了能在二叉树中方便地进行插入与删除
C ： 为了能方便地找到双亲
D ： 使二叉树的遍历结果唯一
正确答案： A
解析：
当以二叉链表作为存储结构存储非线索化的二叉树时，只能找到结点的左、右孩子信息，
而不能直接得到结点在任一遍历序列中的直接前驱和直接后继的结点信息，这种信息只
有在遍历的动态过程中才能得到。二叉线索树利用空链域存放结点的前驱和后继结点的
信息，这样能保存遍历过程中得到的信息。可见，引入二叉线索树的目的是方便查找结
点的前驱或后继结点的速度。
60 、 单选题
A ： (1)，(2)，(3)
B ： (1)
C ： (1)，(3)
D ： (2)，(3)
正确答案： C
解析：61 、 单选题
已知一个线性表为(38，25，74，63，52，48)，假定采用H(K)=Kmod7计算散列地址进
行散列存储，若利用线性探测的开放定址法处理冲突，则在该散列表上进行查找的平均
查找长度为()；若利用链地址法处理冲突，则在该散列上进行查找的平均查找长度为()。
A ： 1.5，1
B ： 1.7，3/2
C ： 2，4/3
D ： 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。
62 、 单选题
可以用()、数据关系和基本操作集定义一个完整的抽象数据类型。
A ： 数据元素
B ： 数据对象
C ： 原子类型
D ： 存储结构
正确答案： B
解析：抽象数据类型可用(数据对象，数据关系，基本操作集)三元组来表示。
63 、 单选题
正确答案： D
解析：
i的变化范围是从1到n，对于每个已确定值的i，j的变化范围是从1到i，相当于求一个公
差为1的等差数列l，2，…，n的前n项和，即为n(n+1)/2。
64 、 单选题
设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三
叉链权中有()个度数为0的结点。
A ： 8
B ： 6
C ： 7
D ： 5
正确答案： C
解析：
度为O的结点个数为1+2×1+2×2=7。
65 、 单选题
在平衡二叉树中，()。
A ： 任意结点的左右子树结点数目相同
B ： 任意结点的左右子树高度相同
C ： 任意结点的左右子树高度之差的绝对值不大于1
D ： 不存在度为1的结点正确答案： C
解析：
该题考查考生对平衡二叉树的理解，形态匀称的二叉树称为平衡二叉树，其严格定义是：
一棵空树是平衡二叉树；T是一棵非空二叉树，其左、右子树为TL和TR，令h1和hr分别
为左、右子树的深度，当且仅当TL、TR都是平衡=叉树且丨h1-hr丨≤1时，T是平衡二叉
树
66 、 单选题
下列叙述中，不符合m阶B树定义要求的是()。
A ： 根节点最多有m棵子树
B ： 所有叶结点都在同一层上
C ： 各结点内关键字均升序或降序排列
D ： 叶结点之间通过指针链接
正确答案： D
解析：
B树的定义。
67 、 单选题
采用分块查找时.若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序
查找来确定结点所在的块时，每块应分()个结点最佳。
A ： 10
B ： 25
C ： 6
D ： 625
正确答案： B
解析：
68 、 单选题
由圈权值为9.2.5.7的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为()。A ： 23
B ： 37
C ： 44
D ： 46
正确答案： C
解析：
69 、 单选题
队列是一种()的线性表。
A ： 先进先出
B ： 只能插入
C ： 先进后出
D ： 只能删除
正确答案： A
解析：
队列的特点是先进先出、后进后出。
70 、 单选题
表长为n的顺序存储的线性表，当在任何位置上删除一个元素的概率相等时，删除一个
元素所需移动元素的平均个数为()。
A ： n
B ： n/2
C ： (n-1)/2
D ： (n+1)/2
正确答案： C
解析：71 、 单选题
当采用分块查找时，数据的组织方式为()。
A ： 数据分成若干块，每块内数据有序
B ： 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的
数据组成索引块
C ： 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块
D ： 数据分成若干块，每块(除最后一块外)中数据个数需相同
正确答案： B
解析：
分块查找要求按如下的索引方式来存储线性表，其分块方法如下：将表R[O..n-l]均分为b
块，前b-l块中记录个数为s=s[n/b]，最后一块即第b块的记录数小于等于s；每一块中的
关键字不一定有序；但前一块中的最大关键字必须小于后一块中的最小关键字，即要求
表是分块有序的；抽取各块中的最大关键字及其起始位置构成一个索引表IDX[O..b-1]，
即IDX[i](O＜i＜b-1)中存放着第i块的最大关键字及该块在表R中的起始位置。由于表R是
分块有序的，因此索引表是一个递增有序表。
72 、 单选题
以下哪一个不是栈的基本运算()。
A ： 删除栈顶元素
B ： 删除栈底元素
C ： 判断栈是否为空
D ： 将栈置为空栈
正确答案： B
解析：
栈的基本运算有人栈、出栈(删除栈顶元素)、初始化、置空、判断是否为空或满、提取
栈顶元素等，对栈元素的操作都是在栈顶进行的
73 、 单选题
某二叉树的先序和后序序列正好相反，则该二叉树一定是()。
A ： 空或只有一个结点B ： 高度等于其结点数
C ： 任一结点无左孩子
D ： 任一结点无右孩子
正确答案： B
解析：
若某二叉树的先序和后序序列正好相反，由于先序遍历是“根—一左子树——右子树”，
而后序遍历是“左子树——右子树——根”，则该二叉树每层左、右子树只能有1个，
即则该二叉树一定是高度等于其结点数。
74 、 单选题
表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为()，其中^为乘幂。
正确答案： D
解析：
75 、 单选题
若线性表最常用的运算是查找第i个元素及其前驱的值，则下列存储方式最节省时间的
是()。
A ： 单链表
B ： 双链表
C ： 单循环链表
D ： 顺序表
正确答案： D
解析：在顺序表中查找第i个元素的前驱很方便。双链表虽然能快速查找第i个元素的前驱，但
不能实现随机存取。单链表和单循环链表既不能实现随机存取，查找第i个元素的前驱也
不方便。
76 、 单选题
设有广义表D(a，b，D)，其长度为3，深度为()
A ： ∞
B ： 3
C ： 2
D ： 5
正确答案： A
解析：
长度为3，但是因第三个元素是一个广义表，所以深度为无穷。
77 、 单选题
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则
利用()存储方式最节省时间。
A ： 顺序表
B ： 双链表
C ： 带头结点的双循环链表
D ： 单循环链表
正确答案： A
解析：
在线性表的顺序存储中，可以存取任一指定序号的元素。当插入和删除运算是在最后操
作时，顺序表的实现也非常方便。BCD三项都不同时具备这两个特点。
78 、 单选题
一组记录的关键字为{25，50，15，35，80，85，20，40，36，70}，其中含有5个长度
为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。
A ： 15，25，35，50，20，40，80，85，36，70
B ： 15，25，35，50，80，20，85，40，70，36
C ： 15，25，50，35，80，85，20，36，40，70
D ： 15，25，35，50，80，20，36，40，70，85
正确答案： A解析：
归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直
接将两个有序的子表合并成一个有序的表。
79 、 单选题
下面关于图的存储的叙述中，正确的是()。
A ： 用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
B ： 用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
C ： 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
D ： 用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
正确答案： A
解析：
对于n个节点的图来说，用邻接矩阵法存储图，需要n×n个存储单元，只与图中结点个数
有关，与边数无关；用邻接表法存储图，与图的结点个数和边数都有关。
80 、 单选题
简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻
接矩阵为A[1.n，1.n]，且压缩存储在B[1.n(n-1)/2]。若按行压缩存储对称矩阵的上三角
元素，则当n等于10时，边(V6，V3)的信息存储在()。
A ： B[18]
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]中。
81 、 单选题
设哈希表长为14，哈希函数是H(key)=key%ll，表中已有数据的关键字
为15，28，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法
解决冲突，则放入的位置是()。
A ： 8
B ： 3
C ： 5D ： 9
正确答案： D
解析：
82 、 单选题
在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是()。
A ： 希尔排序
B ： 起泡排序
C ： 插入排序
D ： 选择排序
正确答案： D
解析：
每一趟从待排序的数据元素中选出最小(或最大)的一个元素，顺序放在已排好序的数列
的最后，直到全部待排序的数据元素排完。
83 、 单选题
外排序是指()。
A ： 在外存上进行的排序方法。
B ： 不需要使用内存的排序方法。
C ： 数据量大，需要人工干预的排序方法。
D ： 排序前后数据在外存，排序时数据调入内存的排序方法
正确答案： D
解析：
本题考查外部排序基本概念。AB两项，CPU不能直接操作外存，因此外排序还需奥使用
到内存。C项，需要人工干预不对。
84 、 单选题
设某棵二叉树中有2000个结点，则该二叉树的最小高度为()。
A ： 12
B ： 10
C ： 11
D ： 9正确答案： C
解析：
想使二叉树的高度最小，即为完全二叉树的时候，所以高度最小为11。
85 、 单选题
设某哈夫曼树中有199个结点，则该哈夫曼树中有()个叶子结点。
A ： 101
B ： 100
C ： 99
D ： 102
正确答案： B
解析：
在哈夫曼树中的结点只有两种，一种是度为零的结点，另一种是度为1的结点。
86 、 单选题
在一个具有n个顶点的有向图中，若所有顶点的出度数之和为S，则所有顶点的入度数之
和为()。
A ： S
B ： S-1
C ： S+1
D ： n
正确答案： A
解析：
图的所有顶点的出度数之和等于所有顶点的入度数之和。故本题选A。
87 、 单选题正确答案： D
解析：
88 、 单选题
G是一个非连通无向图，共有28条边，则该图至少有()个顶点。
A ： 8
B ： 9
C ： 6
D ： 7
正确答案： B
解析：
n个顶点的无向图中，边数e≤n(n-l)/2，将e=28代入，有n≥8，现已知无向图非连通，
则n=9。
89 、 单选题
用链接方式存储的队列，在进行删除运算时()。
A ： 仅修改头指针
B ： 仅修改尾指针
C ： 头、尾指针都要修改
D ： 头、尾指针可能都要修改
正确答案： D
解析：链接方式存储队列的删除运算仍要保持链式队列结构。当队列中仅包含一个元素结点时，
头尾指针均指向该结点，删除该结点后头尾指针均要修改；当队列中有多个结点时，队
列的删除运算仅针对头结点，修改头指针即可。
90 、 单选题
设某完全无向图中有n个顶点，则该完全无向图中有()条边。
A ： n(n-1)/2
B ： n(n-1)
C ： n+1
D ： n
正确答案： A
解析：
因为无向图的边是没有方向的，所以完全无向图有n(n-l)/2条边。
91 、 单选题
如果以链表作为栈的存储结构，则退链栈操作时()
A ： 必须判断链栈是否满
B ： 判断链栈元素的类型
C ： 必须判断链栈是否空
D ： 对链栈不做任何判断
正确答案： C
解析：
在链表的退链栈操作时，如果栈已空.就没有元素可供退栈，返回退栈失败信息，所以必
须判断链栈是否空。
92 、 单选题
A ： 3
B ： 6
C ： 9
D ： 以上答案均不正确
正确答案： A解析：
邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V，E)是具有n个顶点的图，顶点序号
依次为l，2，……，n，则G的邻接矩阵是n阶方阵，所以该图有3个顶点。
93 、 单选题
将10个元素散列到100000个单元的哈希表中，()产生冲突？
A ： 一定会
B ： 一定不会
C ： 仍可能会
D ： 可能不会
正确答案： C
解析：
94 、 单选题
若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉
树是()。
A ： 二叉排序树
B ： 哈夫曼树
C ： 堆
D ： AVL树
正确答案： C
解析：
根据堆排序的定义，所有结点的孩子结点的值要么都大于该结点的值，要么都小于该结
点的值，所以从堆的任一结点出发到根的路径上所经过的结点序列按其关键字有序。
95 、 单选题
头指针为head的带头结点的循环链表为空的判定条件是()。
A ： head=null
B ： head—＞next=null
C ： head—＞next=headD ： head—＞null
正确答案： C
解析：
循环链表为空，即头结点的后继结点是头结点本身，具体的操作语句为head—
＞next=head。
96 、 单选题
以下各种存储结构中，最适合用作链队的链表是()。
A ： 带队首指针和队尾指针的循环单链表
B ： 带队首指针和队尾指针的非循环单链表
C ： 只带队首指针的非循环单链表
D ： 只带队首指针的循环单链表
正确答案： B
解析：
因为队列的入队和出队操作都在端点进行。即在队首和队尾进行。所以带队首指针和队
尾指针的非循环单链表最适合用作链队的链表。
97 、 单选题
用P代表入栈，O代表出栈。栈的初始状态和最终状态都为空，则下列栈操作正确的是()。
A ： POOPOOPP
B ： POPOPOOP
C ： PPPOOOPP
D ： PPPOOPOO
正确答案： D
解析：
AB两项，均会出现下溢，即出栈时栈为空。C项，导致出现最终状态不为空。
98 、 单选题
在一个顺序表的表尾插入一个元素的时间复杂性的量级为()。正确答案： C
解析：
在一个顺序表的表尾插入一个元素移动次数为1次。
99 、 单选题
A ： 堆排序
B ： 快速排序
C ： 希尔排序
D ： 冒泡排序
正确答案： A
解析：
堆排序无论是最好情况还是最坏情况，时间复杂度都是相等的。
100 、 单选题
以下数据结构中哪一个是非线性结构？()
A ： 线性表
B ： 栈
C ： 队列
D ： 二叉树
正确答案： D
解析：
线性表、栈、队列都是线性结构，树、图是非线性结构。
101 、 单选题正确答案： A
解析：
102 、 单选题
设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵
哈夫曼树，则这棵哈夫曼树的带权路径长度为()。
A ： 219
B ： 129
C ： 189
D ： 229
正确答案： D
解析：
103 、 单选题
下面给出的四种排序方法中，辅助空间为O(n)的是()。A ： 希尔选择
B ： 冒泡排序
C ： 归并排序
D ： 堆排序
正确答案： C
解析：
希尔选择、冒泡排序、堆排序的辅助空间都为0(1)；而归并排序中，由于每一趟都要一
个TR数组来复制，因此需要与待排记录等量的辅助空间O(n)。
104 、 单选题
(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的
时间与i无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能
增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错
误的是()。
A ： (1)，(2)
B ： (1)
C ： (1)，(2)，(3)
D ： (2)
正确答案： B
解析：
静态链表借用一维数组来描述线性链表。数组中的一个分量表示一个结点，同时使用游标
(指示器cur)代替指针以指示结点在数组中的相对位置。这种存储结构仍然需要预先分配
一个较大空间，但是在进行线性表的插入和删除操作时不需要移动元素，仅需要修
改“指针”，因此仍然具有链式存储结构的主要优点，(2)，(3)是正确的，但它不具备直
接存取数据的特性，所以只有(1)是错误的。
105 、 单选题
下列关于AOE网的叙述中，不正确的是()。
A ： 关键活动不按期完成就会影响整个工程的完成时间
B ： 任何一个关键活动提前完成。那么整个工程将会提前完成
C ： 所有的关键活动提前完成，那么整个工程将会提前完成
D ： 某些关键活动提前完成，那么整个工程将会提前完成
正确答案： B
解析：
关键路径是指从有向图的源点到汇点的最长路径。某些关键活动提前完成，那么整个工
程将会提前完成，但不是任何一个关键活动提前完成，就能保证整个工程将会提前完咸。106 、 单选题
输入序列为ABC，可以变为CBA时。经过的栈操作为()。
A ： push，pop，push，pop，push，pop
B ： push，push，push，pop，pop，pop
C ： push，push，pop，pop，push，pop
D ： push，pop，push，push，pop，pop
正确答案： B
解析：
栈的特点是后进先出，可以实现序列的倒置，具体操作就
是push，push，push，pop，pop，pop。
107 、 单选题
使用双链表存储线性表，其优点是()。Ⅰ.提高查找速度Ⅱ.更方便数据的插入和删除Ⅲ，
节约存储空间Ⅳ.很快回收存储空间
A ： Ⅰ、Ⅱ
B ： Ⅰ、Ⅳ
C ： 仅Ⅱ
D ： Ⅱ、Ⅲ、Ⅳ
正确答案： C
解析：
在链表中一般只能进行顺序查找，所以双链表并不能提高查找速度，因为双链表中有两
个指针域，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，
其插入和删除操作更加方便。
108 、 单选题
正确答案： A解析：
由森林转换为二叉树，利用的是树转为二叉树时，二叉树的右子树始终为空的特点，所
以，从第二棵树开始，每棵树都成为了B的右子树，即B的左子树的结点个数为N1-1个。
109 、 单选题
若一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个
记录为基准得到的一次划分结果为()。
A ： 38，40，46，56，79，84
B ： 40，38，46，79，56，84
C ： 40，38，46，56，79，84
D ： 40，38，46，84，56，79
正确答案： C
解析：
由于选择第一个记录为基准，第一次排序即对整个序列进行一趟快速排序。使得位于基
准左侧的关键码均小于基准，位于基准右侧的关键码均大于基准。
110 、 单选题
设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为()。
A ： e，n
B ： n.e
C ： 2n，e
D ： n.2e
正确答案： D
解析：
使用邻接表存储图，图有多少结点，邻接表就有多少个表头，无向图的表结点个数为2e。
111 、 单选题
设无向图G=(V，E)和G′=(V′，E′)，如果G′是G的生成树，则下面的说法中错误的是()。
A ： G′为G的极小连通子图且V=V′
B ： G′是G的一个无环子图
C ： G′为G的子图
D ： G′为G的连通分量
正确答案： D
解析：连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有
边都加上，所以，连通分量中可能存在回路。
112 、 单选题
设有n个元素进栈序列是P1，P2，P3，…，Pn，其输出序列是1，2，3，…，n，
若P3=3，则P1的值()。
A ： 可能是2
B ： 一定是2
C ： 不可能是1
D ： 一定是1
正确答案： A
解析：
进栈序列是P1，P2，P3，…，Pn，当P3=3时，由输出序列可知，只有以下两种情
况：P1进栈后出栈，P2进栈后出栈，或P1、P2都进栈然后出栈，因此P1的值可能为1，
也可能为2。
113 、 单选题
正确答案： B
解析：
114 、 单选题
下面几个符号串编码集合中，不是前缀编码的是()。
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
的前缀，因此其不是前缀编码。
115 、 单选题
()不是算法的基本特性。
A ： 可行性
B ： 长度有限
C ： 在规定的时间内完成
D ： 确定性
正确答案： B
解析：
算法的5个重要特性：①确定性；②有穷性；③可行性；④输入；⑤输出。C项指的是有
穷性，而有穷性并不是指长度有限，而是指执行的时间是有限的。
116 、 单选题
如果结点A有3个兄弟，B是A的双亲，则结点B的度是()
A ： 3
B ： 4
C ： 1
D ： 2
正确答案： B
解析：
结点A有3个兄弟，B是A的双亲，则结点B的度是4。
117 、 单选题
在一个单链表中，若p所指的结点不是最后结点，则删除p所指的结点的后继结点的正确
操作是()。
A ： p=p-＞next
B ： p-＞next=p-＞next
C ： p-＞next=p-＞next-＞next
D ： p-＞next=p正确答案： C
解析：
本题考查的是单链表的删除操作。在已知链表中元素插入或删除确切位置的情况下，在
单链表中插入或删除一个结点时，仅需修改指针而无须移动元素。
118 、 单选题
在用邻接表表示图时，拓扑排序算法时间复杂度为()。
A ： O(n)
B ： O(n+e)
C ： On×n
D ： O(n×n×n)
正确答案： B
解析：
拓扑排序中每个顶点都需要出入栈(当用邻接表表示图时的执行次数为n)，然后把入度
减1(当用邻接表表示图时的执行次数为e)，所以拓扑排序的时间复杂度为O(n+e)。
119 、 单选题
快速排序最易发挥其长处的情况是()。
A ： 被排序的数据中含有多个相同排序码
B ： 被排序的数据已基本有序
C ： 被排序的数据完全无序
D ： 被排序的数据中的最大值和最小值相差悬殊
正确答案： C
解析：
120 、 单选题
最好情况下的算法时间复杂度为O(n)的是()。
A ： 插入排序
B ： 归并排序
C ： 快速排序
D ： 堆排序正确答案： A
解析：
121 、 单选题
若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找
一个记录，其平均查找长度ASL为()。
A ： (n-1)/2
B ： n/2
C ： (n+1)/2
D ： n
正确答案： C
解析：
在查找每个记录概率均等的情况下，顺序查找的平均查找长
度ASL=(1+2+…+n)，n=(n+1)/2。
122 、 单选题
在有11个元素的有序表A[1.11]中进行折半查找，查找元素A[11]时，被比较的元素的下
标依次是()。
A ： 6，8，10，11
B ： 6，9，10，11
C ： 6，7，9，11
D ： 6，8，9，11
正确答案： B
解析：
123 、 单选题下面叙述正确的是()。
A ： 二叉树是特殊的树
B ： 二叉树等价于度为2的树
C ： 完全二叉树必为满二叉树
D ： 二叉树的左右子树有次序之分
正确答案： D
解析：
二叉树是一类与树不同的数据结构。两者的区别在于：二叉树可以是空集；二叉树的任
一结点都有两棵子树，并且这两棵子树之间有次序关系，也就是说，它们的位置不能交
换。
124 、 单选题
若一个程序语言可以提供链表的定义和运算，则其运行时的()。
A ： 数据空间必须采用堆存储分配策略
B ： 指令空间需要采用栈结构
C ： 指令代码必须放入堆区
D ： 数据空间适合采用静态存储分配策略
正确答案： A
解析：
链表中的结点空间需要程序员根据需要申请和释放，因此，数据空间应采用堆存储分配
策略
125 、 单选题
下列文件的物理结构中，不利于文件长度动态增长的文件物理结构是()。
A ： 顺序结构
B ： 链式结构
C ： 索引结构
D ： Hash结构
正确答案： A
解析：
顺序结构又称连续结构。这是一种最简单的物理结构，它把逻辑上连续的文件信息依次
存放在连续编号的物理块中，只要知道文件在存储设备上的起始地址(首块号)和文件长度
(总块数)，就能很快地进行存取。这种结构的优点是访问速度快，缺点是文件长度增加
困难。因此，顺序结构的磁盘空间利用率不高，不利于文件长度动态增长。126 、 单选题
一个队列的入队顺序是a，b，c，d，则出队顺序是()。
A ： a，b，C，d
B ： b，C，d，a
C ： d，C，b，a
D ： C，d，a，b
正确答案： A
解析：
队列的特点是先进先出，因此出队的序列于入队的序列完全相同，这点与栈不同。
127 、 单选题
如果S是由有序树T转换的二叉树，则T中的结点的后序遍历顺序是S结点的()。
A ： 先序遍历
B ： 中序遍历
C ： 后序遍历
D ： 层次遍历
正确答案： B
解析：
树转换成二叉树的过程：将结点的最左边的孩子作为该节点的左孩子，下一个兄弟结点
作为右孩子。所以树的后序遍历恰好对应于二叉树的中序遍历。
128 、 单选题
设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有
()个空指针域。
A ： 4m-1
B ： 2m
C ： 2m-1
D ： 4m
正确答案： B
解析：
因哈夫曼树的结点的度，只有0和2两种情况，所以，空指针域为2m个。
129 、 单选题在最好和最坏情况下的时间复杂度均为0(nlogn)且稳定的排序方法是()。
A ： 基数排序
B ： 归并排序
C ： 快速排序
D ： 堆排序
正确答案： B
解析：
快速排序和堆排序是不稳定的，基数排序和归并排序是稳定的。基数排序的平均时间
为O(d(n+rd))，最坏情况下时间复杂度为O(d(n+rd))；归并排序是一种稳定的排序方法，
其最好和最坏情况下的时间复杂度为O(nlogn)。
130 、 单选题
对于含有n个顶点的带权连通图，它的最小生成树是指()。
A ： 图中任意一个由n-l条权值最小的边构成的子图
B ： 图中任意一个由n-1条权值之和最小的边构成的子图
C ： 图中任意一个由n-1条权值之和最小的边构成的连通子图
D ： 图中任意一个由n个顶点构成的边的权值之和最小的连通子图
正确答案： D
解析：
一个连通图的生成树(连通无回路图)是一个极小连通子图。它含有图中全部n个项点，但
只有构成一棵树的(n-1)条边。如果小于(n-1)条边，则是非连通图；如果多于(n-1)条边，
则一定有回路，因为这条边使得它依附的那两个顶点之间有了第二条路径。但是，
有(n-1)条边的图不一定都是生成树。带权连通无向图的所有生成树中具有边上的权值之
和最小的树称为图的最小生成树。总之，含有n个顶点的带权连通图，它的最小生成树
是指图中任意一个由n个顶点构成的边的权值之和最小的连通子图。
131 、 单选题
从一个具有N个结点的单链表中查找其值等于X结点时，查找成功的情况下，需平均比
较()结点。
A ： N
B ： N/2
C ： (N-1)/2
D ： (N+1)/2
正确答案： D
解析：132 、 单选题
适用于折半查找的表的存储方式及元素排列要求为()。
A ： 链接方式存储，元素无序
B ： 链接方式存储，元素有序
C ： 顺序方式存储，元素无序
D ： 顺序方式存储，元素有序
正确答案： D
解析：
折半查找的线性表中的结点必须已按关键字值的递增或递减顺序排列，而且为顺序存储。
133 、 单选题
A ： 14
B ： 19
C ： 21
D ： 26
正确答案： C
解析：
本题考查最小生成树算法。
134 、 单选题
某高度为k的完全二叉树中，所含叶子结点的个数最少为()。正确答案： C
解析：
135 、 单选题
下列排序算法中，()排序在某趟结束后不一定选出一个元素放到其最终的位置上。
A ： 选择
B ： 冒泡
C ： 归并
D ： 堆
正确答案： C
解析：
根据归并排序的思想，在归并排序工程中，某趟排序结束后，某个元素只在它的子序列
中找到了最终的位置。
136 、 单选题
若要求尽可能快地对序列进行稳定的排序，则应选()
A ： 快速排序
B ： 归并排序
C ： 冒泡排序
D ： 堆排序
正确答案： B
解析：
137 、 单选题用s表示入栈操作，*表示出栈操作，栈的初态、终态均为空，人栈和出栈的操作序列可
表示成仅为由S和*组成的序列。下面的序列中合法的操作序列有()。
A ： S*SS*S**
B ： SSS****S
C ： S**S*SS*
D ： SSS*S*S*
正确答案： A
解析：
要使栈的初态、终态均为空，入栈和出栈的操作次数应该相等，因此排除D项。而BC两
项项都出现某一时刻栈已空的情况下执行出栈操作。
138 、 单选题
下列四种排序中()的空间复杂度最大。
A ： 堆排序
B ： 冒泡排序
C ： 插入排序
D ： 归并排序
正确答案： D
解析：
在题干中的四种排序中归并排序的空间复杂度最大，为O(n)。
139 、 单选题
有n个记录的文件，若关键字位数为d，基数为r，则基数排序共需进行()遍分配与收集。
A ： n
B ： r
C ： d
D ： d+r
正确答案： C
解析：140 、 单选题
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
解析：
141 、 单选题
设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作()。
A ： 求子串
B ： 判断是否相等
C ： 模式匹配
D ： 连接
正确答案： C
解析：
A项，求子串操作是从字符串S中截取第i个字符开始后的长度1的子串。BD明显不对。
142 、 单选题
执行一趟快速排序能够得到的序列是()。
A ： [41，12，34，45，27]55[72，63]B ： [12，27，45，41]55[34，63，72]
C ： [63，12，34，45，27]55[41，72]
D ： [45，34，12，41]55[72，63，27]
正确答案： A
解析：
一趟快速排序的结果为基准值的左边节点的值全部小于基准值，基准右边的节点的值全
部不小于基准值。
143 、 单选题
将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原
来的森林中，u和v可能具有的关系是()。Ⅰ.父子关系Ⅱ.兄弟关系Ⅲ.u的父结点与v的父
结点是兄弟关系
A ： 只有Ⅱ
B ： Ⅰ和Ⅱ
C ： Ⅰ和Ⅲ
D ： Ⅰ、Ⅱ和Ⅲ
正确答案： B
解析：
144 、 单选题
设有向无环图G中的有向边集合E={＜1，2＞，＜2，3＞，＜3，4＞，＜1，4＞}，则下
列属于该有向图G的一种拓扑排序序列的是()。
A ： 1，2，3，4
B ： 2，3，4，1
C ： 1，2，4，3D ： 1，4，2，3
正确答案： A
解析：
145 、 单选题
如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用的查找法
是()。
A ： 分块查找
B ： 顺序查找
C ： 折半查找
D ： 基于属性
正确答案： A
解析：
分块查找又称索引顺序查找，是一种性能介于顺序查找和二分查找之间的查找方法。其
基本思想是：(1)首先查找索引表：索引表是有序表，可采用二分查找或顺序查找，以确
定待查的结点在哪一块。(2)然后在已确定的块中进行顺序查找：由于块内无序，只能用
顺序查找。分块查找既能较快的查找，又能适应动态变化的要求。
146 、 单选题
在一个具有n个单元的顺序栈中，假定以地址低端(即下标为0的单元)作为栈底，以top作
为栈顶指针，当出栈时，top的变化为()。
A ： top=top-1；
B ： top=top+1；
C ： 不变
D ： top=0；
正确答案： A
解析：
以top作为栈顶指针，当出栈时，top的变化为top=top-1。147 、 单选题
对一个算法的评价，不包括如下()方面的内容。
A ： 健壮性和可读性
B ： 并行性
C ： 正确性
D ： 时空复杂度
正确答案： B
解析：
对一个算法的评价，不包括并行性方面的内容。
148 、 单选题
A ： 21/7
B ： 28/7
C ： 15/6
D ： 21/6
正确答案： B
解析：
149 、 单选题
设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有()个结点。A ： 13
B ： 12
C ： 26
D ： 25
正确答案： D
解析：
哈夫曼树的特点：具有n个叶子结点的哈夫曼树共有2×n-1个结点。
150 、 单选题
假定一棵度为3的树中结点数为50，则其最小高度应为()。
A ： 5
B ： 6
C ： 3
D ： 4
正确答案： A
解析：
151 、 单选题
设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含
有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的
结果为()。
A ： 15，25，35，50，20，40，80，85，36，70
B ： 15，25，35，50，80，20，85，40，70，36
C ： 15，25，35，50，80，20，36，40，70，85
D ： 15，25，35，50，80，85，20，36，40，70
正确答案： A
解析：
归并排序的每趟排序将相邻的两个子序列合并，直至剩两个子序列，合并后产生一个序
列，即为最终排序结果。152 、 单选题
指出在顺序表F={2，5，7，10，14，15，18，23，35，41，52}中，用二分查找法查
找12需要进行多少次比较()。
A ： 2
B ： 3
C ： 4
D ： 5
正确答案： C
解析：
折半查找又称二分查找，其基本思想：首先用要查找的关键字k与中间位置的结点的关
键字相比较，这个中间结点把线性表分成了两个子表，若比较结果相等则查找完成；若
不相等，再根据k与该中问结点关键字的比较大小确定下一步查找哪个子表，这样递归
进行下去，直到找到满足条件的结点或者该线性表中没有这样的结点。
153 、 单选题
以数组Data[m+1]作为循环队列SQ的存储空间，front为头指针，rear为队尾指针，则执
行出队操作的语句是()。
A ： front=front+1
B ： front=(front+1)%m
C ： front=(front+1)%(m+1)
D ： rear=(rear+1)%m
正确答案： C
解析：
循环队列的出队操作是：front=(front+1)%(m+l)。
154 、 单选题
先序遍历序列和中序遍历序列相同的二叉树为()。
A ： 根结点无左子树的二叉树
B ： 根结点无右子树的二叉树
C ： 只有根结点的二叉树或非子结点只有左子树的二叉树
D ： 只有根结点的二叉树或非叶子结点只有右子树的二叉树
正确答案： D
解析：
先序遍历的次序为根一左一右，而中序遍历的次序为左一根一右，树中肯定有根结点，要使先序遍历序列和中序遍历序列相同，两种遍历次序可以相同的次序为根一右。所以
满足条件的树为只有根结点的二叉树或非叶子结点只有右子树的二叉树。
155 、 单选题
对于一个满二叉树，共有n个结点和m个叶子结点，深度为h，则()。
正确答案： D
解析：
156 、 单选题
设有向图G=(V，E)和G′-(V′，E′).如(G′)是G生成树，下面说法中不正确的是()
A ： G′为G的连通分量
B ： G′为G的无环子图
C ： G′为G的子图
D ： G′为G的极小连通子图且V′=V
正确答案： A
解析：
B项、D项都是生成树的特点，而A项为概念错误：G′为连通图而非连通分量，图的连通
分量是指无向图中的极大连通子图。
157 、 单选题
A ： 45
B ： 46
C ： 55
D ： 56正确答案： D
解析：
题目甲对角线以下均为-3，个与共他元素里复，可知这45个元素只需用一个但米表示，
故该矩阵只需用(100-45)+1=56个元素来表示。
158 、 单选题
在顺序表中删除一个元素的时间复杂度为()。
正确答案： C
解析：
删除顺序表中第i个元素，将顺序表第i个元素以后元素均向前移动一个位置，因此时间
复杂度为0(n)。
159 、 单选题
设链式栈中节点的结构为(data，link)，且top是指向栈顶的指针。若想摘除链式栈的栈
顶节点，并将被摘除节点的值保存到x中，则应执行下列()操作。
A ： x=top-＞data；top=top-＞link；
B ： top=top-＞link；x=top-＞data；
C ： x=top；top=top-＞link；
D ： x=top-＞data；
正确答案： A
解析：
若想摘除链式栈的栈顶节点，并将被摘除节点的值保存到x中，则应执行x=top-
＞data；top=top-＞link.
160 、 单选题
可以用()定义一个完整的数据结构。
A ： 数据元素
B ： 数据对象
C ： 数据关系D ： 抽象数据类型
正确答案： D
解析：
抽象数据类型描述了数据的逻辑结构和抽象运算，构成了一个完整的数据结构定义。
161 、 单选题
假设以S和X分别表示进栈和出栈操作，则对输入序列a，B，c，d，E进行一系列栈操
作SSXSXSSXXX之后，得到的输出序列为()。
A ： B，c，E，d，a
B ： E，c，a，d
C ： E，c，B，d，a
D ： c，E，B，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。
162 、 单选题
若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二
趟排序后的结果，则该排序算法只能是()。
A ： 起泡排序
B ： 插入排序
C ： 选择排序
D ： 二路归并排序
正确答案： B
解析：
插入排序基本思想：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好
序的子表的最后，直到全部记录排序完毕。
163 、 单选题
在一棵具有n个结点的二叉树中，所有结点的空子树个数等于()。
A ： n
B ： n-1
C ： n+1D ： 2×n
正确答案： C
解析：
164 、 单选题
设线性表(顺序存储方式)的每个元素占8个存储单元。第一个单元的存储地址为100，则
第6个元素占用的最后一个存储单元的地址为()。
A ： 139
B ： 140
C ： 147
D ： 148
正确答案： C
解析：
6个元素，每个元素8个存储单元.一共需要48个存储单元。第一个单元的存储地址为100，
所以第6个元素占用的最后一个存储单元的地址为100+48-1=147(-1是因为地址100是第
一个存储位置)。
165 、 单选题
下列说法不正确的是()。
A ： 图的遍历是从给定的源点出发每一个顶点仅被访问一次
B ： 遍历的基本算法有两种：深度遍历和广度遍历
C ： 图的深度遍历不适用于有向图
D ： 图的深度遍历是一个递归过程
正确答案： C
解析：
图的遍历是指从给定图中任意指定的顶点出发，按照某种搜索方法沿着图的边访问图中
的所有顶点，便每个丁贞点仅被访问一次。遍历的基本算法有两种：深度遍历和厂度遍
历。图的深度遍历是一个递归过程，既适用于无向图，也适用于有向图。
166 、 单选题串′ababaaababaa′的next数组值为()。
A ： 01234567899
B ： 012121111212
C ： 011234223456
D ： 0123012322345
正确答案： C
解析：
167 、 单选题
下列有关散列查找的叙述正确的是()。
A ： 散列存储法只能存储数据元素的值，不能存储数据元素之间的关系
B ： 散列冲突是指同一个关键字对应多个不同的散列地址
C ： 用线性探测法解决冲突的散列表中，散列函数值相同的关键字总是存放在一片连续
的存储单元中
D ： 若散列表的装填因于a＜＜l，则可免冲突的严生
正确答案： A
解析：
A项，在散列表中，每个元素的存储位置通过散列函数和解决冲突的方法得到，散列存
储法只存储数据元素的值，不能存储数据元素之间的关系；B项，散列冲突是指多个不
同关键字对应相同的散列地址；C项，用线性探测法解决冲突的散列表中，散列函数值相同的关键字不一定总是存放在一片连续的存储单元中；D项，装填因子a越小，发生冲
突的概率越小，但仍有可能发生冲突。
168 、 单选题
下列各种排序算法中平均时间复杂度为O(n)是()。
A ： 快速排序
B ： 堆排序
C ： 归并排序
D ： 冒泡排序
正确答案： D
解析：
169 、 单选题
以下叙述不正确的是()。
A ： 后序线索二叉树是不完善的，要对它进行遍历，不需使用栈
B ： 任何一棵二叉树的后序线索树进行后序遍历时都必须使用栈
C ： 任何一棵二叉树都可以不用栈实现先序线索树的先序遍历
D ： 任何一棵二叉树都可以不用栈实现中序线索树的中序遍历
正确答案： B
解析：
遍历后序线索二叉树不需要使用栈。
170 、 单选题
在AOE网络中关键路径叙述正确的是()。
A ： 从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需
的最短时间
B ： 从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需
的最短时间
C ： 从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需
的最长时间
D ： 从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需
的最长时间
正确答案： A解析：
关键路径是指从有向图的源点到汇点的最长路径。某些关键活动提前完成，那么整个工
程将会提前完成，但不是任何一个关键活动提前完成，就能保证整个工程将会提前完成。
171 、 单选题
链表不具有的特点是()。
A ： 不必事先估计存储空间
B ： 可随机访问任一元素
C ： 插入删除不需要移动元素
D ： 所需空间与线性表长度成正比
正确答案： B
解析：
链表采用的是链式存储结构，它克服了顺序存储结构的缺点：①它的结点空间可以动态
申请和释放；②它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。
但是链式存储结构也有不足之处：①每个结点中的指针域需额外占用存储空间；②链式
存储结构是一种非随机存储结构。
172 、 单选题
算法指的是()。
A ： 计算机程序
B ： 解决问题的计算方法
C ： 排序算法
D ： 解决问题的有限运算序列
正确答案： D
解析：
算法是精确定义的一系列规则，它指出怎样从给定的输入信息经过有限步骤产生所求的
输出信息。它既不是计算机程序，也不是某种算术运算。
173 、 单选题
设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择()。
A ： 小于等于m的最大偶数
B ： 小于等于m的最大合数
C ： 小于等于m的最大奇数
D ： 小于等于m的最大素数
正确答案： D解析：
p最好选择小于等于m的最大素数。
174 、 单选题
顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为()。
正确答案： B
解析：
无论是顺序存储还是链式存储，使用顺序查找法的时间复杂度相同。
175 、 单选题
在平衡二叉树中()。
A ： 不存在度为1的节点
B ： 任意节点的左、右子树节点数目相同
C ： 任意节点的左、右子树高度相同
D ： 任意节点的左右子树高度之差的绝对值不大于1
正确答案： D
解析：
平衡二叉树又称AVL树，它或者是一棵空树，或具有下列性质的二叉树：(1)左子树和右
子树都是平衡二叉树：(2)左子树和右子树的高度之差的绝对值不超过1。二叉树上节点
的平衡因子定义为该节点的右子树的高度减去它的左子树的高度。可见，平衡二叉树上
所有节点的平衡因子只可能是-1，0，1。只要二叉树上有一个节点的平衡因子的绝对值
大于1，则该二叉树就是不平衡的。
176 、 单选题
利用二叉链表存储树，则根结点的右指针为()。
A ： 指向最左孩子
B ： 指向最右孩子
C ： 空
D ： 非空正确答案： C
解析：
177 、 单选题
如果一棵二叉树结点的先根遍历序列是A、B、C，后根遍历序列是C、B、A，则该二叉
树结点的中根遍历序列()。
A ： 必为A、B、C
B ： 必为A、C、B
C ： 必为B、C、A
D ： 不能确定
正确答案： D
解析：
178 、 单选题
已知有一维数组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%m
B ： i=k/m，j=k%m
C ： i=k/n，j=k%n
D ： 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。
179 、 单选题
函数substr(“DATASTRUCTURE”，5，9)的返回值为()。
A ： “STRUCTURE”
B ： “DATA”
C ： “DATASTRUCTURE”
D ： “ASTRUCTUR”
正确答案： A
解析：
substr函数的作用是找到从第5个字符开始，长度为9的子串。
180 、 单选题
栈在()中应用。
A ： 递归调用
B ： 子程序调用
C ： 表达式求值
D ： A，B，C
正确答案： D
解析：
栈的特点是先入后出。A项，递归调用的特点是最外层的调用最后执行，最内层的调用
最先执行，递归调用符合栈的特点，即先将外层的调用依次入栈，然后从最内层调用出
栈执行；B项，子程序的调用与递归调用的特点类似；C项，表达式求值将数据入栈，遇
到运算符时与栈顶的运算符比较优先级，级别高则数据出栈，进行运算。
181 、 单选题
设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准
记录的一趟快速排序结束后的结果为()。
A ： 10，15，14，18，20，36，40，21
B ： 15，10，14，18，20，36，40，21
C ： 10，15，14，20，18，40，36，21
D ： 10，15，14，18，20，40，36，21
正确答案： A解析：
快速排序的每趟排序在待排序列中选取一个数为基准，将序列划分为两段，一段的值比
基准值小，另一段大于或等于基准值。在快速排序中通常有两个指针分别为i和j，j从后
向前遍历，找第一个小于基准值的节点，将值交换，i从前向后遍历，找到第一个大于或
等于基准值的节点，将值交换，重复此过程，直至i和j指向同一节点，一趟排序结束。
182 、 单选题
在向下生成的堆栈中，如果入栈指令PUSHX的操作定义为：SP←(SP)+1，M(SP)←M(X)，
则出栈指令POPX应定义为()。
A ： SP←(SP)-1，M(X)←M(SP)
B ： SP←(SP)+1，M(X)←M(SP)
C ： M(X)←M(SP)，SP←(SP)-1
D ： M(X)←M(SP)，SP←(SP)+1
正确答案： C
解析：
入栈是先定位栈顶指针然后存储数据，出栈是先出数据，然后再定位栈顶指针。
183 、 单选题
A ： n-i
B ： n-i+l
C ： n-i-l
D ： i
正确答案： A
解析：
顺序表中的删除操作是通过将当前结点用后面结点的值覆盖来实现的，因此删除第i个元
素主要是前移第i个元素后的所有的元素，即n-i个元素。
184 、 单选题
静态链表中指针表示的是()。
A ： 内存地址
B ： 数组下标
C ： 下一元素地址
D ： 数组地址正确答案： B
解析：
静态链表借用一维数组来描述线性链表。数组中的一个分量表示一个结点，同时使用游标
(指示器cur)代替指针以指示结点在数组中的相对位置。
185 、 单选题
在计算机的存储器中表示时，各元素的物理地址和逻辑地址的相对顺序相同并且是连续
的称之为()。
A ： 逻辑结构
B ： 顺序存储结构
C ： 链式存储结构
D ： 以上都对
正确答案： B
解析：
顺序存储结构是一种直接映射。这种结构把逻辑上相邻的元素存储在物理位置上相邻的
存储单元里，直接反映数据元素之间的逻辑关系。
186 、 单选题
在具有n个结点的顺序表，算法的时间复杂度是O(1)的操作是()。
正确答案： A
解析：
187 、 单选题
在常用的描述二叉排序树的存储结构中，关键字值最大的结点的()。
A ： 左指针一定为空B ： 右指针一定为空
C ： 左右指针均为空
D ： 左右指针均不为空
正确答案： B
解析：
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：①若它的左子树不空，则
左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有
结点的值均大于它的根结点的值；③它的左右子树也分别为二叉排序树。由上述特征可
以知道二叉排序树中关键值最大的结点的右指针一定为空，左指针却不一定为空。
188 、 单选题
设指针变量p指向双向链表中节点A，指针变量s指向被插入的节点X，则在节点A的后面
插入节点X的操作序列为()
A ： p-＞right=s；s-＞left=p；p-＞right-＞left=s；s-＞right=p-＞right；
B ： p-＞right=s；p-＞right-＞left=s；s-＞left=p；s-＞right=p-＞right；
C ： s-＞left=p；s-＞right=p-＞right；p-＞right=s；p-＞right-＞left=s；
D ： s-＞left=p；s-＞right=p-＞right；p-＞right-＞left=s；p-＞right=s；
正确答案： D
解析：
为了防止在插入节点时链表断裂，在修改指针时，需要先使s的后继指针指向p原来的后
继节点，然后修改p的后继指针。
189 、 单选题
下面的说法中正确的是()。(1)任何一棵二叉树的叶子结点在三种遍历中的相对次序不变：
(2)按二叉树定义，具有三个结点的二叉树共有6种。
A ： (1)(2)
B ： (1)
C ： (2)
D ： (1)、(2)都错
正确答案： B
解析：190 、 单选题
设二叉排序树中关键字由1～1000的整数构成，现要查找关键字为363的结点，下列关键
字序列不可能是在二叉排序树上查找到的序列是()。
A ： 2，252，401，398，330，344，397，363
B ： 924，220，911，244，898，258，362，363
C ： 925，202，911，240，912，245，363
D ： 2，399，387，219，266，382，381，278，363
正确答案： C
解析：
把这四个序列各插入到一个初始为空的二叉排序树中，可以发现，C序列形成的不是一
条路径，而是有分支的，可见它是不可能在查找过程中访问到的序列。
191 、 单选题
循环队列qu的队空条件是()。
A ： (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize
B ： (qu.rear+1)%MaxSize-=qu.front+1
C ： (qu.rear+1)%MaxSize==qu.front
D ： qu.rear==qu.front
正确答案： D
解析：
循环队列为空，当且仅当队尾指针等于队尾指针.具体的操作语句为qu.rear==qu.front。
192 、 单选题
完全二叉树高度为h，则最左边的叶子结点序号为()。
正确答案： B
解析：193 、 单选题
用直接选择排序方法分别对序列S1=(1，2，3，4，5，6，7)和序列S2=(7，5，3，2，4，
1，6)进行排序，关键字比较次数()。
A ： 相同
B ： 前者大于后者
C ： 前者小于后者
D ： 无法比较
正确答案： A
解析：
直接选择排序的比较次数与序列的初始状态无关，因此，对于给定两个序列进行排序的
关键字比较次数是相同的。
194 、 单选题
对于只在表的首尾两端进行插入操作的线性表，宜采用的存储结构是()。
A ： 顺序表
B ： 用头指针表示的单循环链表
C ： 用尾指针表示的单循环链表
D ： 单链表
正确答案： C
解析：
本题考查的是线性表的插入与删除操作。当线性表用尾指针表示的单循环链表存储时，
很容易找到线性表的首、尾元素。此时，尾指针的后继即是线性表的首端。
195 、 单选题
堆排序分为两个阶段，其中第一阶段将给定的序列建成一个堆，第二阶段逐次输出堆顶
元素。设给定序列{48，62，35，77，55，14，35，98}，若在堆排序的第一阶段将该
序列建成一个堆(大根堆)，那么交换元素的次数为()。
A ： 5
B ： 6
C ： 7
D ： 8
正确答案： B
解析：196 、 单选题
占用的额外空间的空间复杂度为0(1)的排序算法是()。
A ： 堆排序算法
B ： 归并排序算法
C ： 快速排序算法
D ： 以上答案都不对
正确答案： A
解析：
归并排序中，由于每一趟都要一个TR数组来复制，因此需要与待排记录等量的辅助空
间O(n)；而快速排序中的递归所耗费的栈空间最好情况下也要O(logn)；堆排序仅在交换
是需要一个记录的辅助空间。
197 、 单选题
在一个长度为n(n＞1)的带头结点单链表h上，另设有尾指针r(指向尾结点)。与链表的长
度有关的操作是()。
A ： 删除单链表中的第一个元素
B ： 删除单链表中的最后一个元素
C ： 在单链表第一个元素前插入一个新元素
D ： 在单链表最后一个元素后插入一个新元素
正确答案： B
解析：
在单链表中要删除最后一个元素必须找到尾结点的前驱结点的指针。由于单链表只能访
问结点的下一个结点，所以根据尾指针不能够直接找到它的前驱结点，只有从头开始依
次向下找到尾结点的前驱结点。所以删除单链表中的最后一个元素与链表的长度有关。198 、 单选题
设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出
序列中第i个输出元素是()
A ： n-1-i
B ： n-i
C ： n+1-i
D ： 不能确定
正确答案： C
解析：
经过栈后的输出序列中第一个元素为n，代表从1至n是一次性全部人栈的，所以出栈序
列刚好是入栈序列的倒序。
199 、 单选题
双向链表中有两个指针域llink和rlink，分别指向前驱和后继，设β指向表中的一个结
点，q指向一待插入结点，现要求在p前插入q，则正确的插人为()。
正确答案： D
解析：
p→llink→rlink=q；q→rlink=p；q→llink=p→llink；p→llink=q
200 、 单选题
下列排序算法中，不能保证每趟排序至少能将一个元素放到其最终的位置上的是()。
A ： 快速排序
B ： shell排序
C ： 堆排序
D ： 冒泡排序
正确答案： B
解析：
shell排序每次使待排序记录基本有序，但不能保证每趟排序至少能将一个元素放到其最终的位置上。
201 、 单选题
在一个单链表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)。
202 、 单选题
正确答案： B
解析：
203 、 单选题
下列不属于内部排序的算法是()。
A ： 归并排序
B ： 拓扑排序
C ： 树型排序
D ： 折半插入排序正确答案： B
解析：
归并排序、树型排序、折半插入排序属于内部排序算法，拓扑排序不属于内部排序算法。
204 、 单选题
设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a1，1为第一元
素，其存储地址为1，每个元素占一个地址空间，则a8·5的地址是()。
A ： 13
B ： 33
C ： 18
D ： 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。
205 、 单选题
前序遍历和中序遍历结果相同的二叉树是()。
A ： 所有节点只有左子树的二叉树
B ： 所有节点只有右子树的二叉树
C ： 根节点无左孩子的二叉树
D ： 根节点无右孩子的二叉树
正确答案： B
解析：
前序遍历是首先访问根节点，然后前序遍历左子树，最后前序遍历右子树。中序遍历是
首先中序遍历左子树，然后访问根节点，最后中序遍历右子树。当所有节点都没有左子
树时，前序遍历和中序遍历的遍历结果相同。
206 、 单选题
一趟排序结束后不一定能够选出一个元素放在其最终位置上的是()。
A ： 冒泡排序
B ： 堆排序
C ： 快速排序
D ： 希尔排序正确答案： D
解析：
冒泡排序每趟选出一个最值移至序列的一端。快速排序的一趟排序可以使选出的基准值
移至最终位置。
207 、 单选题
在含有n个关键字的小根堆(堆顶元素最小)中，关键字最大的记录有可能存储的位置是()。
正确答案： D
解析：
208 、 单选题
采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为()。
A ： (n-1)/2
B ： (n+1)/2
C ： n
D ： n/2
正确答案： B
解析：
搜索的最好情况是第一个元素即想要查找的元素，最坏的情况是最后一个元素即想要查
找的元素，所以平均查找长度是(n+l)/2。
209 、 单选题
快速排序在最坏情况下的时间复杂度为()。正确答案： D
解析：
210 、 单选题
将数组称为随机存取结构是因为()。
A ： 数组的存储结构是不定的
B ： 数组元素是随机的
C ： 对数组任一元素的存取时间是相等的
D ： 随时可以对数组进行访问
正确答案： C
解析：
将数组称为随机存取结构是因为对数组任一元素的存取时间是相等的。
211 、 单选题
由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为()。
A ： 53
B ： 73
C ： 48
D ： 24
正确答案： B
解析：
根据赫夫曼树的构造方法可构造出赫夫曼树，经计算可得带权路径长度为73。
212 、 单选题
设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F
对应的二叉树根结点的右子树上的结点个数是()。A ： M1
B ： M1+M2
C ： M3
D ： M2+M3
正确答案： D
解析：
森林转换成二叉树的原则：将第一棵树的根结点作为根结点，所有结点的第一个左孩子
作为左孩子，下一个兄弟结点作为右孩子，其它树作为第一棵树的右孩子。所以森林F
对应的二叉树根结点的右子树上的结点个数是M2+M3。
213 、 单选题
由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的
根(即离插入结点最近且平衡因子的绝对值为2的结点)为()。
A ： 27
B ： 38
C ： 51
D ： 75
正确答案： D
解析：
214 、 单选题
在有向图中，所有顶点的度数之和是所有边数的()倍
A ： 0.5
B ： 1
C ： 2
D ： 4
正确答案： C解析：
在有向图中，所有顶点的度数之和是所有边数的2倍，因为一条边的两个端点具有两
个“度”。
215 、 单选题
设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有()条有向边。
A ： n-1
B ： n
C ： m-1
D ： m
正确答案： B
解析：
邻接表的表头结点个数即为图中结点的个数。
216 、 单选题
设有n个待排序的记录关键字，则在堆排序中需要()个辅助记录单元。
正确答案： A
解析：
堆排序的辅助空间为0(1)。
217 、 单选题
二叉排序树中，最小值结点的()。
A ： 左、右指针均为空
B ： 左、右指针均不为空
C ： 左指针一定为空
D ： 右指针一定为空
正确答案： C
解析：在二叉排序树中，值最小的结点一定是中序遍历序列中第一个被访问的结点，即二叉树
的最左下结点。
218 、 单选题
设某棵三叉树中有40个结点，则该三叉树的最小高度为()
A ： 6
B ： 4
C ： 5
D ： 3
正确答案： B
解析：
树高度最小时即为每一层都是满的，只有最下层不满的情况是树的高度最小的情况。
219 、 单选题
判定一个栈ST(最多元素为m0)为满的条件是()。
A ： ST-＞top=m0-1
B ： ST-＞top=0
C ： ST-＞top＜＞m0
D ： ST-＞top＜＞0
正确答案： A
解析：
如果一个栈的栈顶指针为m0-1，则该栈为满。
220 、 单选题
设有5000个元素，希望用最快的速度挑选出前10个最大的，采用()方法最好。
A ： 希尔排序
B ： 归并排序
C ： 快速排序
D ： 堆排序
正确答案： D
解析：
堆排序不必将整个序列排序即可确定前若干个最大(或最小)元素。221 、 单选题
正确答案： A
解析：
222 、 单选题
已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为()。
A ： -A+B*C/DE
B ： -A+B*CD/E
C ： -+*ABC/DE
D ： -+A*BC/DE
正确答案： D
解析：
将算术表达式的前缀形式、中缀形式和后缀形式分别看成二叉树的前序遍历、中序遍历
和后序遍历，本题可转化成已知二叉树的中序遍历和后序遍历序列，如何求出其前序遍
历序列。前序遍历的顺序是根结点，左子树，右子树；中序遍历的顺序是左子树，根结
点，右子树；后序遍历的顺序是左子树，右子树，根结点；因此后序遍历中最后访问的
结点是根结点，该结点将中序遍历分成两个子序列，分别为其左右子树的中序序列，之
后递归应用这个过程，构造出一个二叉树，前序遍历该序列，即可得到表达式的前缀形
式。
223 、 单选题
在二叉排序树中插入一个关键字值的平均时间复杂度为()。正确答案： B
解析：
在二叉排序树中插入节点的时间复杂度等于查找失败的时间复杂度，即在查找失败的位
置插入节点，时间复杂度为0(1og2n)。
224 、 单选题
在单链表指针为P的结点之后插入指针为s的结点，正确的操作是()。
正确答案： B
解析：
在单链表结点P后插入结点s，要先改变s结点的指针域，指向p的后继结点。然后将s的
地址赋给P的指针域。具体的操作语句为s—＞next=P—＞next；p—＞next=s。
225 、 单选题
如下陈述中正确的是()。
A ： 串是一种特殊的线性表
B ： 串的长度必须大于零
C ： 串中元素只能是字母
D ： 空串就是空白串
正确答案： A
解析：
串的长度可以等于0，等于0时叫作空串。空串和空白串是不同的，例如：Strings=“”，
是空串；Strings=NULL，是空白串。串中的元素只能是字符，但不仅仅是字母。226 、 单选题
下面关于哈希查找的说法正确的是()。
A ： 哈希函数构造的越复杂越好，因为这样随机性好、冲突小
B ： 除留余数法是所有哈希函数中最好的
C ： 不存在特别好与坏的哈希函数，要视情况而定
D ： 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删
去即可
正确答案： C
解析：
AB两项，哈希函数的构造要视具体情况而定，对于不同的序列，选择不同的哈希函数，
采用不同的解决冲突的方法，没有绝对的好坏。D项，当删除元素时，如果删除元素的
位置刚好发生了冲突，需要将因发生冲突而移动的元素重新计算哈希值进行存储，要找
到这些元素现在的位置就需要看解决冲突的方法。
227 、 单选题
正确答案： C
解析：
228 、 单选题
线索二叉树中某结点R没有左孩子的充要条件是()。
A ： R.ltag=1
B ： R.rchild=NULL
C ： R.lchild=NULL
D ： R.ltag=0正确答案： D
解析：
线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标
志是否为0。
229 、 单选题
A ： LRN
B ： NRL
C ： RLN
D ： RNL
正确答案： D
解析：
由7，5，6的顺序可知遍历顺序为RNL。
230 、 单选题
下列命题正确的是()。
A ： 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一
B ： 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一
C ： 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一
D ： 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一
正确答案： C
解析：
一个图的邻接矩阵表示是唯一的，邻接表表示不唯一。
231 、 单选题
一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1.n]
中，则二叉树中第i个结点(i从1开始用上述方法编号)的右孩子在数组A中的位置是()。A ： [2i](2i＜=n)
B ： A[2i+1](2i+1＜=n)
C ： A[i-2]
D ： 条件不充分，无法确定
正确答案： D
解析：
题目并未明确所给二叉树的形状，因此不能根据第i个结点在数组A中的存储位置确定其
右孩子在数组A中的位置。
232 、 单选题
设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度
之和为()。
A ： 20
B ： 40
C ： 30
D ： 45
正确答案： D
解析：
构造赫夫曼树时，每次从结点中选取权值最小的两个，构成一棵新的树，直至所有结点
都并入同一棵树中。
233 、 单选题
二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是()。
A ： 先序遍历二叉树
B ： 判断两个指定位置的结点是否在同一层上
C ： 层次遍历二叉树
D ： 根据结点的值查找其存储位置
正确答案： B
解析：
234 、 单选题
在下列排序方法中不需要对排序码进行比较就能进行排序的是()。A ： 基数排序
B ： 快速排序
C ： 直接插入排序
D ： 堆排序
正确答案： A
解析：
235 、 单选题
关于AVL(平衡二叉树)，下列说法错误的是()。
A ： 左子树与右子树高度差最多为1
B ： 插入操作的时间复杂度为0(logn)
C ： 平衡二叉树是二叉排序树中的一种
D ： 使用平衡二叉树的目的是为了节省空间
正确答案： D
解析：
平衡二叉树是平衡二又排序树的简称。它或者是一棵空树，或者是具有下列性质的二叉
树：①左、右子树的高度之差不超过1；②左、右子树也是平衡二叉树；平衡二叉树没
有节省空间，引入其目的是防止排序二叉树左、右子树高度失衡。
236 、 单选题
对于长度为m(m＞1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述
是()。
A ： 入栈序列与出栈序列关系为1：1，而入队序列与出队序列关系是1：n(n≥1)
B ： 若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序
C ： 入队序列与出队序列关系为1：1，而人栈序列与出栈序列关系是1：n(n≥1)
D ： 若入栈和人队的序列相同，则出栈序列和出队序列可能相同
正确答案： A
解析：
队列的元素按特点是先进先出。对于队列，元素的进入次序和出队的次序相同，例如，入队的序列为a、b、c，则出队的序列也为a、b、c。对于栈则不同，栈的运算特点是后
进先出。若入栈序列为a、b、c，则出栈序列可能为a、b、c，a、c、b，b、a、c，b、c、
a或者c、b、a，而c、a、b则不行，因此，入栈序列与出栈序列关系为1：1，而人队序
列与出队序列关系为1：n(n≥1)。
237 、 单选题
已知有向图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，e
B ： d，a，b，c，e
C ： a，b，d，c，e
D ： a，b，c，d，e
正确答案： D
解析：
238 、 单选题
A ： i
B ： n-i
C ： n-i+l
D ： 不确定
正确答案： C
解析：
根据题中所叙述情况，栈的输出序列一定是输入序列的逆序。
239 、 单选题
下面()不属于特殊矩阵。A ： 对角矩阵
B ： 三角矩阵
C ： 稀疏矩阵
D ： 对称矩阵
正确答案： C
解析：
稀疏矩阵不属于特殊矩阵。
240 、 单选题
栈和队列的共同点是()。
A ： 都是先进先出
B ： 都是先进后出
C ： 只允许在端点处插入和删除元素
D ： 没有共同点
正确答案： C
解析：
栈和队列都是运算受限的线性表，只允许在表端点处进行操作。
241 、 单选题
文件有m个初始归并段，采用k路归并时，所需的归并遍数是()。
正确答案： D
解析：
本题考查归并排序时间复杂度相关问题。根据归并排序的特点可以得到答案。
242 、 单选题
若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，
则查找A[3]的比较序列的下标依次为()。
A ： 9，5，3B ： 9，5，2，3
C ： 1，2，3
D ： 9，4，2，3
正确答案： D
解析：
二分查找的基本思想是将n个元素分成大致相等的两部分，取中间位置的节点值与关键
字做比较，如果相等，则查找成功；如果关键字的值小于中间节点，则只要在数组的左
半部分继续搜索，重复与中间值进行比较，直至查找成功或失败；如果关键字大于中间
值，则只要在数组的右半部搜索即可。
243 、 单选题
表达式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——a
244 、 单选题
在有n个结点的二叉链表中，值为非空的链域的个数为()。
A ： n-1
B ： 2n-1
C ： n+1
D ： 2n+1
正确答案： A
解析：
本题考查的是二叉树的链式存储。由于在有n个结点的二叉链表中，值为空的链域的个
数为n+1个，而总的链域为2n(在二叉树中每个结点头2个链域)。所以，非空的链域的个
数为2n-(n+1)=n-1。
245 、 单选题时间复杂度不受数据初始状态影响而恒为0(nlog2n)的是( )。
A ： 堆排序
B ： 快速排序
C ： 希尔排序
D ： 冒泡排序
正确答案： A
解析：
堆排序无论是最好情况还是最坏情况，时间复杂度都是相等的。
246 、 单选题
静态查找与动态查找的根本区别在于()。
A ： 所包含的数据元素的类型不一样
B ： 存储实现不一样
C ： 它们的逻辑结构不一样
D ： 施加在其上的操作不同
正确答案： D
解析：
静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。
247 、 单选题
设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，es，e6依次通过栈S，一个元素
出栈后即进入队列Q，若6个元素出队的顺序是e2，e4，e3，e6，e5，e1，则栈S的容量
至少应该是()。
A ： 6
B ： 4
C ： 3
D ： 2
正确答案： C
解析：
248 、 单选题设某强连通图中有n个顶点，则该强连通图中至少有()条边。
A ： n+1
B ： n(n-1)
C ： n
D ： n(n+1)
正确答案： C
解析：
强连通图是指在一个有向图中，若从节点i到节点j有路径，并且节点j到i有路径，那么为
强连通图。
249 、 单选题
已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则完全二叉树的结点个数最多是
()。
A ： 39
B ： 52
C ： 111
D ： 119
正确答案： C
解析：
根据完全二查处定义，前6层应该是满二叉树，共有2^6-1=63个结点。第6层有8个叶节
点。说明有32-8=24个结点不是叶节点，因此最多时共有63+24*2=111个。
250 、 单选题
每个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明
存储位置的表，该存储方式是()存储方式。
A ： 顺序
B ： 链接
C ： 索引
D ： 散列
正确答案： C
解析：
根据索引的定义，除表本身以外，还需建立一个“索引表”，这个表指明存储位置加快
结点的查找过程。251 、 单选题
讨论树、森林和二叉树的关系，目的是为了()。
A ： 借助二叉树上的运算方法去实现对树的一些运算
B ： 将树、森林转换成二叉树
C ： 体现一种技巧，没有什么实际意义
D ： 将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题
正确答案： D
解析：
讨论树、森林和二叉树的关系，目的是为了将树、森林按二叉树的存储方式进行存储并
利用二叉树的算法解决树的有关问题。
252 、 单选题
正确答案： C
解析：
253 、 单选题
在求边稠密的图的最小代价生成树时，()算法比较合适。
A ： 普里姆(Prim)
B ： 克鲁斯卡尔(Kruskal)
C ： 迪杰斯特拉(Dijkstra)
D ： 其他
正确答案： A
解析：254 、 单选题
设循环队列的存储空间为Q(1：30)，初始状态front=rear=30，先经过一系列入队和退队
运算后，front=10，rear=10，则循环队列中的元素个数为()。
A ： 30
B ： 0
C ： 29
D ： 0或30
正确答案： D
解析：
当frontrear时，循环队列中的元素个数为N-front+rear(N为循环队列容量)。
当front=rear时，循环队列中的元素个数可能为空，也可能为满。
255 、 单选题
设单循环链表中结点的结构为(data，link)，且rear是指向非空的带表头结点的单循环链
表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作()。
A ： s=rear；rear=rear-＞link；deletes；
B ： rear=rear-＞link；deleterear；
C ： rear=rear-＞link-＞link；deleterear；
D ： s=rear-＞link-＞link；rear-＞link-＞link=s-＞link；deletes；s为第一个结点硫
正确答案： D
解析：
若要删除结点需要改变尾指针的指向。
256 、 单选题
下列排序方法中，属于不稳定的排序方法的是()。
A ： 直接插入排序法
B ： 冒泡排序法
C ： 基数排序法
D ： 堆排序法
正确答案： D解析：
本题选项所述的四种排序方法中，只有堆排序是不稳定的。
257 、 单选题
广义表(a，b，(c，(d)))的表尾是()。
A ： (b，(c，(d))
B ： (b，(c，(d)))
C ： (d)
D ： (c，(d))
正确答案： B
解析：
广义表的第一个表元素为表头，由表中除表头外的其他元素组成的表称为广义表的表尾。
258 、 单选题
下面关于线性表的叙述中，错误的是()。
A ： 线性表采用顺序存储，必须占用一片连续的存储单元
B ： 线性表采用顺序存储，便于进行插入和删除操作
C ： 线性表采用链接存储，不必占用一片连续的存储单元
D ： 线性表采用链接存储，便于插入和删除操作
正确答案： B
解析：
线性表的顺序存储称为顺序表。顺序表就是把线性表中的所有元素按照其逻辑顺序。依
次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中，不便于插入和
删除；线性表的链式存储称为链表。在链式存储中，存储结点之间通过指针链接到下一
个结点，不必占用一片连续的存储单元，而且便于插入和删除操作。
259 、 单选题
下面术语中，与数据的存储结构无关的是()。
A ： 循环队列
B ： 栈
C ： 散列表
D ： 单链表
正确答案： B
解析：只有栈是逻辑结构，其他选项都是存储结构(或物理结构)。
260 、 单选题
正确答案： A
解析：
261 、 单选题
要连通具有n个顶点的有向图，至少需要()条边。
A ： n-1
B ： n
C ： n+1
D ： 2n
正确答案： B
解析：
n个顶点的有向图若连通，至少保证每个项点都有一条边连通它，所以至少需要n条边
262 、 单选题
将一个a[100][100]的三对角矩阵以行主序存入一维数组B[298]中，元素a[65][64]在B数
组中的位置等于()。
A ： 198
B ： 197
C ： 196
D ： 195
正确答案： D解析：
将三对角矩阵a[i][j]存入b[k]中，矩阵压缩地址计算公式为k=2i十j。所以a[65][64]对应
的k=2×65+64=194，194是一维数组b的下标，而数组下标是从0开始计数的.所以元素的
位置应该是195。
263 、 单选题
线性表是()。
A ： 一个有限序列，可以为空
B ： 一个有限序列，不可以为空
C ： 一个无限序列，可以为空
D ： 一个无限序列，不可以为空
正确答案： A
解析：
线性表是具有相同特性的数据元素的一个有限序列，可以为空。
264 、 单选题
栈S最多只能容纳4个元素，现在6个元素按A，B，C，D，E，F的顺序进栈，下列哪一个
序列是可能的出栈序列()。
A ： EDCBAF
B ： CEFAD
C ： BEDAF
D ： ADFEBC
正确答案： C
解析：
一次进栈最多4个，即ABCD同时在栈中，则EDCBAF不可能，A项中，E和F还没有进栈就
已经出栈；B项中，D元素不可能出栈在A的后面；D项中，最后两个元素出栈顺序也有
误。
265 、 单选题
下面的说法中，不正确的是()。
A ： 对角矩阵只需存放非零元素即可
B ： 稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储
C ： 稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储
D ： 对称矩阵只需存放包括主对角线元素在内的下(或上)三角的元素即可
正确答案： C解析：
稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。如果零元素的分
布有规律，就没有必要存储非零元素的行号和列号，而需要按其压缩规律找出相应的映
象函数。
266 、 单选题
在一个双链表中，删除P结点之后的一个结点的操作是()。
正确答案： C
解析：
考查双链表中插入操作，要注意保存后继节点。
267 、 单选题
KMP算法的特点是在模式匹配时指示主串的指针()。
A ： 不会变大
B ： 不会变小
C ： 都有可能
D ： 无法判断
正确答案： B
解析：
在KMP算法中，模式匹配时主串不会回溯，所以主串的指针不会变小。
268 、 单选题
在()存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。
A ： 树形存储结构
B ： 链式存储结构
C ： 索引存储结构
D ： 散列存储结构
正确答案： D解析：
散列存储结构中是根据设定的哈希函数和处理冲突的方法将一组关键字映像到一个连续
的地址集上，并以关键字在地址集中的象作为记录在表中的存储位置。而树形存储结构、
链式存储结构和索引存储结构中关键字在结构中的相对位置是随机的。
269 、 单选题
循环队列用数组A[o…m-1]存放其元素值，已知其头尾指针分别为front和rear，则当前
元素个数为()。
A ： (rear-front+m)modm
B ： rear-front+l
C ： rear-front-1
D ： rear-front
正确答案： A
解析：
循环队列中rear和front分别指向队尾和队头，当rear＞front时，元素的个数为rear-
front，根据循环队列的性质，当插入点已经插入到数组A的最后位置且有新的元素插入
时，会继续从数组的开始位置执行插入操作，此时rear＜front，数组元素的个数为rear-
front+m。综合两种情况，循环队列中当前元素的个数计算方法为：(rear-
front+m)modm。
270 、 单选题
建立一个长度为n的有序单链表的时间复杂度为()
正确答案： C
解析：
建立有序单链表的时间复杂度是O(n)，对单链表插入节点时，先遍历单链表，找到插入
位置，将节点插入。
271 、 单选题
若对n阶对称矩阵A[1...n, 1...n]以行序为主序方式将其下三角的元素(包括主对角线上的
所有元素)依次存放于-维数组B[1...fl (n+1)/2]中，则在B中确定ass (i
A ： i×(1-1)/2+jB ： j×(j-1)/2+i
C ： i×(1+1)/2+j
D ： j×(j+1)/2+i
正确答案： B
解析：
272 、 单选题
m阶B-树是一棵()。
A ： m叉排序树
B ： m叉平衡排序树
C ： m-l叉平衡排序树
D ： m+l叉平衡排序树
正确答案： B
解析：
B-树又叫多路平衡查找树，是一种组织和维护外存文件系统非常有效的数据结构。B-树
中每个结点之多有m棵子树，m就是B-树的阶。m阶B-树就是一棵m叉平衡排序树。
273 、 单选题
含n个顶点的连通图中的任意一条简单路径，其长度不可能超过()。
A ： n-1
B ： n
C ： 1
D ： n/2
正确答案： A
解析：
若超过n-l，则路径中必存在重复的顶点。
274 、 单选题
已知一个有序表为(12，18，24，35，47，50，62，83，90，115，134)，当折半查找
值为90的元素时，经过()次比较后查找成功。A ： 2
B ： 3
C ： 4
D ： 5
正确答案： A
解析：
根据二分法查找的查找过程，首先将90与表中中间的元素50进行比较，由于90大于50，
所以在线性表的后半部分查找。第二次与比较的元素是后半部分的中间元素，即90，这
时两者相等，即查找成功。
275 、 单选题
有种关系模式R=＜U，F
＞，U={C，T，H，X，S}，F={C→T，(H，X)→C，(H，T)→YC，(H，S)→Y}则表示模式R
的码是()。
A ： C
B ： (H，S)
C ： (H，Y)
D ： (H，T)
正确答案： B
解析：
由题可得如下推导：(H，S)+R，(H，R)+C，C--4T，(H，T)--4R，故可知(H，S)为关系模
式的码。
276 、 单选题
在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。
正确答案： B
解析：
Prim算法的时间复杂度：当图采用邻接矩阵存储时，时间复杂度为0(r12)，采用邻接表
存储时，时间复杂度为O(n+e)。277 、 单选题
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。
A ： 求关键路径的方法
B ： 求最短路径的Dijkstra方法
C ： 广度优先遍历算法
D ： 深入度优先遍历算法
正确答案： D
解析：
判断一个图是否存在回路的方法包括：(1)设图G是n个顶点的无向图，若G的边数e＞=n，
则图G中一定有回路存在。(2)设图G是n个顶点的无向连通图，若G的每个顶点的度＞=2，
则图G中一定有回路存在。(3)利用拓扑排序算法可以判断图中是否存在回路。即在拓扑
排序输出结束后所余下的顶点均有前驱，则说明只得到了部分顶点的拓扑有序序列，图
中存在有回路。(4)利用深度优先遍历算法可以判定图G中是否存在回路。对于无向图来
说，若深度优先遍历过程中遇到了回边则必定存在环；对于有向图来说，这条回边可能
是指向深度优先森林中另一棵生成树上顶点的弧；但是，如果从有向图上的某个项点v
出发进行深度优先遍历，若在dfs(v)结束之前出现一条认顶点v到顶点v的回边，因u在生
成树上是v的孙子，则有向图必定存在半含顶点u和顶点v的环。
278 、 单选题
快速排序最不利于发挥其长处的情况是()。
A ： 待排序的数据中含有多个相同值
B ： 待排序的数据已基本有序
C ： 待排序的数据量太大
D ： 被排序的数据数量为奇数
正确答案： B
解析：
各种排序方法对待排序的数据中是否含有多个相同值、被排序的数据数量为奇数或偶数
都没有影响。快速排序等改进的排序方法均适用于待排序数据量较大的情况。
279 、 单选题
对包含n个关键码的散列表进行检索，平均检索长度为()。
A ： O(logn)
B ： O(n)
C ： O(nlogn)
D ： 不直接依赖于n
正确答案： D解析：
散列表的平均检索长度仅与装填因子a有关，而与关键字个数n无关。
280 、 单选题
在一棵完全二叉树中，其根的序号为1，()可判定序号为p和q的两个结点是否在同一层。
正确答案： A
解析：
281 、 单选题
链表不具备的特点是()。
A ： 可随机访问任一结点
B ： 插入、删除不需要移动元素
C ： 不必事先估计存储空间
D ： 所需空间与其长度成正比
正确答案： A
解析：
链式存储结点间通过指针连接.存储位置比较灵活，不必事先估计存储空间。根据表长来
确定存储空间即可；插入和删除不需要移动元素，只要改变指针域值；但链表不具备随
机访问任一结点的特点，这是顺序表的特点。
282 、 单选题
设结点x和y是二叉树中任意的两个结点，在该二叉树的前序遍历序列中x在y之前，而在
其后序遍历序列中x在y之后，则x和y的关系是()。
A ： x是y的左兄弟
B ： x是y的右兄弟
C ： x是y的祖先
D ： x是y的后裔正确答案： C
解析：
前序遍历序列中x在y之前，有两种情况，即x是y的祖先，或者x、y有某个共同祖先，并
且x在其左子树中，y在其右子树中。而第二种情况在后序遍历序列中，x必定在y之前，
所以只能是x是y的祖先。
283 、 单选题
AOV网是一种()。
A ： 有向图
B ： 无向无环图
C ： 无向图
D ： 有向无环图
正确答案： D
解析：
AOV网是一种有向无环图，即没有回路。
284 、 单选题
二维数组A的每个元素是由6个字符组成的串，其行下标i=O，1，…，8，列下
标j=1，2，…，10。设每个字符占一个字节。若A按行先存储，元素A[8，5]的起始地址
与当A按列先存储时起始地址相同的元素是()。
A ： [8，5]
B ： A[3，10]
C ： A[5，8]
D ： A[0，9]
正确答案： B
解析：
元素A[8，5]的起始地址与当A按列先存储时的A[i，j]元素的起始地址相同，
即8×10+5-1=(j-1)×9+i，将四个答案代入可得正确答案。
285 、 单选题
设一个有序的单链表中有n个节点，现要求插入一个新节点后使得单链表仍然保持有序，
则该操作的时间复杂度为()。正确答案： C
解析：
对单链表进行插入节点的操作，就是对单链表进行查找，找到节点需要插入的位置，然
后修改指针，将节点插入单链表。
286 、 单选题
下列排序算法中，在待排序数据已有序时，花费时间反而最多的排序是()。
A ： 冒泡
B ： 希尔
C ： 快速
D ： 堆
正确答案： C
解析：
在待排序数据已有序时，快速排序会退化为冒泡排序，时间复杂度为O(n)。
287 、 单选题
以下与数据的存储结构无关的术语是()。
A ： 循环队列
B ： 链表
C ： 哈希表
D ： 栈
正确答案： D
解析：
数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种
不同的存储结构：顺序存储结构和链式存储结构，它们是数据的两种最基本的存储结构。
ABC三项，都属于链式存储结构。D项，栈则是指从应用的角度来说的一种后进先出的
线性表结构，与具体的存储结构无关。
288 、 单选题二路归并排序的时间复杂度为()。
正确答案： C
解析：
289 、 单选题
算法分析的目的是()。
A ： 找出数据结构的合理性
B ： 研究算法中输入和输出的关系
C ： 分析算法的效率以求改进
D ： 分析算法的易懂性和文档性
正确答案： C
解析：
算法分析的目的是分析算法的效率以求改进。
290 、 单选题
设高度为H的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为
()。
A ： 2H
B ： 1H-1
C ： 2H+1
D ： H+1
正确答案： B
解析：291 、 单选题
在双向循环链表中，在p所指的结点之后插入指针f所指的新结点，其操作步骤是()。
正确答案： D
解析：
在双向循环链表中。在p所指的结点之后插入指针f所指的新结点的操作步骤为：改变f的
前驱指针域，使其指向p；然后改变f的后继指针域，使其指向p的后继；接下来修改p的
后继结点得前驱指针域，指向f，最后将f的地址付给p的后继指针。具体操作为：f—
＞pnor=p；f—＞next=p—＞next；p—＞next—＞prior=f；P—＞next=f。
292 、 单选题
下列二叉排序树中，满足平衡二叉树定义的是()。O
正确答案： B解析：
平衡二叉树是平衡二又排序树的简称。它或者是一棵空树，或者是具有下列性质的二叉
树：①左、右子树的高度之差不超过1；②左、右子树也是平衡二叉树。
293 、 单选题
对下列关键字序列用快速排序法进行排序时，速度最快的是()。
A ： {21，25，5，17，9，23，30}
B ： {25，23，30，17，21，5，9}
C ： {21，9，17，30，25，23，5}
D ： {5，9，17，21，23，25，30}
正确答案： A
解析：
对于快速排序，若数据初始特性能够使每趟排序划分的两块大小相当，则排序效率会比
较高。在A中，第一个元素21刚好是序列中7个元素的中间元素，将序列分成的两个部分
大小相等，第一次划分后的结构为(9，17，5)21(25，23，30)；第二次划分，左右两部
分的第一个元素也刚好是所在块序列的中间元素，同样将所在块分成均等的两部分。在
这种情况下排序的速度最快。
294 、 单选题
数据的最小单位是()。
A ： 数据项
B ： 数据类型
C ： 数据元素
D ： 数据变量
正确答案： A
解析：
数据的最小单位是数据项。
295 、 单选题
若将数据结构中的数据元素称为结点，则一般没有开始结点和终端结点的数据结构是()。
A ： 树
B ： 图
C ： 多维数组
D ： 线性表
正确答案： B解析：
图G由两个集合V和E组成，记为G=(V，E)。其中V是顶点的有限集合，记为V((G)；E是连
接V中两个不同顶点(顶点对)的边的有限集合，记为E(G)。图是由有限集合的顶点和边构
成，没有开始结点和终端结点。
296 、 单选题
下列说法正确的是()。
A ： 任何有向网络(AOV-网)拓扑排序的结果是唯一的
B ： 有回路的图不能进行拓扑排序
C ： 在AOE网中一定只有一条关键路径
D ： 一个正常的AOE网中只能有一个源点、一小汇点和一条关键路径
正确答案： B
解析：
拓扑排序的结果不一定是唯一的；在AOE网中，关键路径不止一条。
297 、 单选题
数据的存储结构是指()。
A ： 数组类型
B ： 指针类型
C ： 数据之间的逻辑关系
D ： 数据之间的物理关系
正确答案： D
解析：
数据的存储结构就是物理结构，指数据之间的物理关系。
298 、 单选题
若对27个元素只进行三趟多路归并排序，则选取的归并路数为()。
A ： 2
B ： 3
C ： 4
D ： 5
正确答案： B
解析：299 、 单选题
若用单链表来表示队列，则应该选用()。
A ： 带尾指针的非循环链表
B ： 带尾指针的循环链表
C ： 带头指针的非循环链表
D ： 带头指针的循环链表
正确答案： B
解析：
假设尾指针为TAIL，则通过TAIL可访问队尾，通过TAIL—＞next可访问队头。
300 、 单选题
具有5个叶子结点的二叉树中，度为2的结点的个数为()。
A ： 4
B ： 6
C ： 5
D ： 不确定
正确答案： A
解析：
二叉树的性质1：非空二叉树上叶结点数等于双分支结点数加1。因此度为2的结点的个
数为5-1=4。
301 、 单选题
在含有n个关键字的大顶堆中，关键字最小的记录有可能存储在()位置上。
A ： n/2
B ： n/2-1
C ： 1
D ： n/2+2
正确答案： D
解析：302 、 单选题
有六个元素6，5，4，3，2，1的顺序进栈.下列选项中，()不是合法的出栈序列。
A ： 543612
B ： 453126
C ： 346521
D ： 234156
正确答案： C
解析：
根据栈的后进先出的特点，对于C选项中前两个元素得出栈顺序可以看出，4在5和6前先
出栈，有根据入站顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，
所以出栈时5要比6先出栈。
303 、 单选题
下列序列中，满足堆定义的是()。
A ： (100，86，48，73，35，39，42，57，66，21)
B ： (12，70，33，65，24，56，48，92，86，33)
C ： (103，97，56，38，66，23，42，12，30，52，6，26)
D ： (5，56，20，23，40，38，29，61，36，76，28，100)
正确答案： A
解析：
n个元素的序列{K1，K2，…，Kn}当且仅当满足下面关系：Ki＜=K2i和Ki＜=K(2i+1)或
者Ki＞=K2i和Ki＞K(2i+1)时，称之为堆。B项，其构成的是小顶堆，70和24之间不满足
小顶堆性质；C项，其构成的是大顶堆，23和26不满足大顶堆性质；D项，其构成的是
小顶堆，56和23，40和28不满足小顶堆性质。A项对应的是大顶堆，满足大顶堆性质。
304 、 单选题
设数组ta[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行
出队操作后其头指针front的值为()。
A ： front=front+1
B ： front=(front+1)%(m-1)C ： front=(front-1)%m
D ： front=(front+1)%M
正确答案： D
解析：
对于循环队列出队的操作就是队头指针后移，即+1。但对于循环队列要对队列长度求余
才能得到指针的位置。具体的操作语句为front=(front+1)%m。
305 、 单选题
—棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则先序遍历序列为()。
A ： CBED
B ： DECAB
C ： DEABC
D ： CEDBA
正确答案： D
解析：
由后序序列必定最后一个访问根结点，故C为根结点。在先序遍历中首先访问根结点C。
306 、 单选题
在线索化二叉树中，t所指结点没有左子树的充要条件是()。
A ： t-＞left=NUL1
B ： t-＞ltag=1
C ： t-＞ltag=1且t-＞left=NUL1
D ： 以上都不对
正确答案： B
解析：
由线索二叉树的定义得知，若结点没有左子树，则左标志域为1，该指针域中存放的是
线索，而非左子树信息，此时左指针指向前驱结点；若结点的左标志域为1，则结点没
有左子树。
307 、 单选题
下列排序方法中，()是稳定的排序方法。
A ： 直接插入排序和快速排序
B ： 折半插入排序和起泡排序
C ： 简单选择排序和四路归并排序D ： 树形选择排序和shell排序
正确答案： B
解析：
直接插入排序、四路归并排序、起泡排序、树形选择排序和折半插入排序是稳定的排序。
快速排序、shell排序、简单选择排序是不稳定的排序。
308 、 单选题
正确答案： D
解析：
当n足够大时，T(n)→3n/10=O(n)。
309 、 单选题
A ： (1)
B ： (1)、(2)
C ： (1)、(4)
D ： (3)
正确答案： C
解析：
(1)项，原地工作不是不需要额外空间，而是额外空间相对于问题的规模(输入数据量)来
说是个常数，那么我们就称之为原地工作。(4)项，这个结论不是绝对的，要看具体情况
而定，一般情况下是这样的。310 、 单选题
算法的时间复杂度取决于()。
A ： 问题的规模
B ： 待处理数据的初态
C ： A和B
D ： 与A和B无关
正确答案： C
解析：
算法的时间复杂度是问题规模n的函数，它既取决于待处理数据的多少，即问题的规模；
又取决于待处理数据的存储状态和存储形式等，即待处理数据的初态。
311 、 单选题
设散列表表长m=14，散列函数H(k)=kmod11。表中已有15，38，61，84四个元素，如
果用线性探测法处理冲突，则元素49的存储地址是()。
A ： 8
B ： 3
C ： 5
D ： 9
正确答案： A
解析：
元素15，38，61，84分别存储在4，5，6，7单元，而元素49的散列地址为5，发生冲突，
向后探测3个单元，其存储地址为8。
312 、 单选题
数据结构是具有()的数据元素的集合。
A ： 性质相同
B ： 特定关系
C ： 相同运算
D ： 数据项
正确答案： B
解析：
数据结构由数据元素集合和数据元素关系两部分组成。313 、 单选题
若用冒泡排序方法对序列{10、14、26、29、41、52}从大到小排序，需要进行几次比
较()。
A ： 3
B ： 10
C ： 15
D ： 25
正确答案： C
解析：
冒泡排序法比较排序的时候，第一个10要进行5次比较，第二个要进行4次比较，依次类
推，3次，2次，1次，总共是15次比较。
314 、 单选题
采用简单选择排序，比较次数与移动次数分别为()。
正确答案： C
解析：
简单排序的思想：第i趟排序开始时，当前有序区和无序区分别为R[0..i-1]和R[i..n-1](0≤i
＜n-1)，该趟排序则是从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1
个记录R[i]交换，使R[0..i]和R[i+1..n-1]分别变为新的有序区和新的无序区。所以比较的
次数为0(n×n)，移动的次数则为0(n)。
315 、 单选题
以下有关算法的说法错误的是()。Ⅰ.算法原地工作的含义是指不需要任何额外的辅助空
间；Ⅱ，在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算
法；Ⅲ.所谓最坏时间复杂度是指最坏情况下估算算法执行时间的一个上界；Ⅳ，同一个
算法，实现语言的级别越高，执行效率就越低。
A ： Ⅰ
B ： Ⅰ和Ⅱ
C ： Ⅰ和Ⅳ
D ： Ⅲ正确答案： C
解析：
算法原地工作的含义是指算法的空间复杂度为O(1)，同一个算法实现语言的级别越高执
行效率并不一定越低。
316 、 单选题
下列排序算法中，()每一趟都能选出一个元素放在最终位置上，并且是不稳定的
A ： 冒泡排序
B ： 希尔排序
C ： 直接选择排序
D ： 直接插入排序
正确答案： C
解析：
起泡排序和选择排序一趟排序后，在序列两端应该有最大或最小值。直接选择排序是不
稳定的。
317 、 单选题
若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵()。
A ： 第i行中值为1的元素个数
B ： 所有值为1的元素个数
C ： 第i行及第i列中值为1的元素总个数
D ： 第i列中值为l的元素个数
正确答案： D
解析：
对于无向图，其邻接矩阵的第i行的和即为第i个顶点的度。对于有向图，邻接矩阵的第i
行元素的和即为第i个顶点的出度，而邻接矩阵的第j列元素的和即为第j个顶点的出度。
318 、 单选题
对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，
同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实
现编号。
A ： 先序
B ： 中序
C ： 后序
D ： 从根开始按层次遍历正确答案： C
解析：
每个结点编号大于其左右孩子的编号，因此，需要在左右孩子访问完毕后才访问该结点，
同一结点中左孩子的编号小右孩子的编号，故左孩子先于右孩子被访问。这些符合后序
遍历的特点。
319 、 单选题
向一个带头结点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。
320 、 单选题
有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，
查找成功所需的平均比较次数为()。
A ： 37/12
B ： 35/12
C ： 39/12
D ： 43/12
正确答案： A
解析：
用二分法查找有序表，相当于在一个完全二叉树中查找元素，查找成功的比较次数相当
于到查找结点的路径长度加1。12个结点的完全二叉树前三层是满二叉树，第四层有5个
结点。整棵树的查找次数总和为：1+22+4×3+5×4=37。查找某个元素的概率是37/12。
321 、 单选题
()的邻接矩阵是对称矩阵。
A ： 有向图
B ： 无向图C ： AOV网
D ： AOF网
正确答案： B
解析：
无向图的邻接矩阵一定是一个对称矩阵。
322 、 单选题
正确答案： C
解析：
323 、 单选题
一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是()。
A ： 43512
B ： 12345
C ： 54321
D ： 45321
正确答案： A
解析：
此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序(指的是元
素的序号)的两个元素。
324 、 单选题
下列排序算法中，()算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在
其最终的位置上。
A ： 堆排序B ： 冒泡排序
C ： 快速排序
D ： 插入排序
正确答案： D
解析：
插入排序在最后一个元素被插入时，所有元素都要后移，即在最后一趟开始之前，所有
元素都不在其最终的位置上。
325 、 单选题
某二叉树中序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E，则前
序序列是()。
A ： E，G，F，A，C，D，B
B ： E，A，
C ： B，D，G，F
D ： 以上都不对
正确答案： B
解析：
由后序序列知E为根节点，再由中序序列知A，B，C，D为E的左子树1，F，G，E为右子
树1；由后序序列知A为左子树l的根节点，B，C，D为A的右子树2。依次类推可得到该
数，其前序序列也可自然而然的得到。
326 、 单选题
设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表
项的平均探查次数不超过1.5，则散列表项应能够至少容纳()个表项。
A ： 400
B ： 526
C ： 624
D ： 676
正确答案： A
解析：
采用线性探查法解决冲突查找成功时的平均查找长度S≈0.5×(1+1/(1-a))，其中a是哈希表
的装填因子，定义为a=表中装入的记录数，哈希表的长度。若要求查询成功的平均查找
次数不超过1.5，即S≤1.5，而且哈希表中装入的记录数为200，故哈希表长度不小于400。
327 、 单选题关于哈夫曼树，下列说法正确的是()。
A ： 在哈夫曼树中，权值相同的叶子结点都在同一层上
B ： 在哈夫曼树中，权值较大的叶子结点一般离根结点较远
C ： 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近
D ： 在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作
特殊外理
正确答案： C
解析：
哈弗曼编码中不允许出现两个字符编码相同的情况。
328 、 单选题
下面关于图的遍历说法不正确的是()。
A ： 遍历图的过程实质上是对每个顶点查找其邻接点的过程
B ： 深度优先搜索和广度优先搜索对无向图和有向图都适用
C ： 深度优先搜索和广度优先搜索对顶点访问的顺序不同，它们的时间复杂度也不相同
D ： 深度优先搜索是一个递归的过程，广度优先搜索的过程中需附设队列
正确答案： C
解析：
深度优先搜索和广度优先搜索的时间算杂度相同，均为O(n+e)。
329 、 单选题
对于一个长度为n的任惫表进行排序，至少需要进行的比较次数是()。
正确答案： D
解析：330 、 单选题
一棵完全二叉树上有1001个结点.其中叶子结点的个数是()。
A ： 250
B ： 500
C ： 505
D ： 501
正确答案： D
解析：
331 、 单选题
设线性表有n个元素，以下操作中，在顺序表上实现比在链表上实现效率更高的是()。
A ： 输出第i个元素值
B ： 交换第1个元素与第2个元素的值
C ： 顺序输出这n个元素的值
D ： 输出与给定值x相等的元素存线性表中的序号
正确答案： A
解析：
顺序表的一个主要特点就是可以直接存取任一指定序号的元素，输出第i个元素值时间复
杂度为O(1)。B项需要开辟临时空间，CD两项的时间复杂度均为O(n)；
332 、 单选题
要求内存量最大的排序算法是()。
A ： 插入排序
B ： 选择排序
C ： 快速排序
D ： 归并排序
正确答案： D
解析：
选择排序和插入排序的空间复杂度为O(1)；快速排序中的递归所耗费的栈空间在最好情
况下也为O(logn)；归并排序中，由于每一趟都要一个TR数组来复制，所以需要与待排记
录等量的辅助空间为O(n)。333 、 单选题
一个循环队列Q最多可存储m个元素，已知其头尾指针分别是front和rear，则判定该循
环队列为满的条件是()。
A ： Q.rear-Q.front==m
B ： Q.real！==Q.front
C ： Q.front==(Q.real+1)%m
D ： Q.front==Q.rear%m+1
正确答案： C
解析：
少用一个元素空间和空队区别开：每次入队前测试入队后头尾指针是否会重合，如果会
重合就认为队列已满，这种情况下队满的条件是：(Q.rear+1)%MAXSIZE==Q.front。
334 、 单选题
有m个叶子结点的哈夫曼树所具有的结点数为()。
A ： m
B ： m+1
C ： 2m
D ： 2m-1
正确答案： D
解析：
哈夫曼树中仅有度为0和2的结点，由二叉树的性质可知，具有m个叶子结点的哈夫曼树
具有m-1个度为2的结点，因此，具有m个叶子结点的哈夫曼树所具有的节点数为2m-1。
335 、 单选题
二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉
树根的右子树的根是()
A ： E
B ： F
C ： G
D ： H
正确答案： C
解析：336 、 单选题
下述排序方法中，比较次数与待排序记录的初始状态无关的是()。
A ： 选择排序和归并排序
B ： 插入排序和归并排序
C ： 插入排序和快速排序
D ： 归并排序和快速排序
正确答案： A
解析：
337 、 单选题
线性表采用链接存储时，其地址()。
A ： 必须是连续的
B ： 部分地址必须是连续的
C ： 一定是不连续的
D ： 连续与否均可以
正确答案： D
解析：
线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以
连续，也可以不连续，甚至可以零散分布在内存中任意位置。
338 、 单选题
下面关于Prim算法和KruskAl算法的时间复杂度正确的是()。
A ： Prim算法的时间复杂度与网中的边数有关，适合于稀疏图
B ： Prim算法的时间复杂度与网中的边数无关，适合于稠密图C ： KruskAl算法的时间复杂度与网中的边数有关，适合于稠密图
D ： KruskAl算法的时间复杂度与网中的边数无关，适合于稀疏图
正确答案： B
解析：
339 、 单选题
对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的
平均搜索长度为()。
A ： n/2
B ： (n+1)/2
C ： (n-1)/2
D ： n/4
正确答案： B
解析：
所有元素的搜索长度之和为1+2+…+n=n(n+1)/2。搜索每个元素的概率都是1/n，所以平
均搜索长度为：n(n+1)，2×(1/n)=(n+1)/2。
340 、 单选题
已知10个元素(54，28，16，34，73，62，95，60，26，43)，按照依次插入的方法生
成一棵二叉排序树，查找值为62的节点所需比较次数为()。
A ： 2
B ： 3
C ： 4
D ： 5
正确答案： B
解析：
查找值为62的节点所需比较次数为3。
341 、 单选题
设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字
生成的二叉排序树的深度为()。
A ： 4B ： 6
C ： 5
D ： 7
正确答案： A
解析：
342 、 单选题
n个结点的线索二叉树上含有的线索数为()。
A ： n
B ： 2n
C ： n-1
D ： n+1
正确答案： D
解析：
对于有n个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有2n
个指针域，由于只有n-1个结点被有效指针所指向.则共有2n-(n-1)=n+1个空链域。用这
些空链域存放指向结点的前驱和后继结点的指针，这些指针称作线索。
343 、 单选题
下面关于B和B+树的叙述中，不正确的是()。
A ： B树和B+树都是平衡的多叉树
B ： 树和B+树都可用于文件的索引结构
C ： B树和B+树都能有效地支持顺序检索
D ： B树和B+树都能有效地支持随机检索
正确答案： C
解析：
B-树又叫多路平衡查找树，是一种组织和维护外存文件系统非常有效的数据结构。在索
引文件组织中，常使用B-树的变形——B+树，属于平衡的多叉树。两者都支持随机检索，
但不能有效地支持顺序检索。344 、 单选题
无向图中一个顶点的度是指图中()。
A ： 通过该顶点的简单路径数
B ： 通过该顶点的回路数
C ： 与该顶点相邻接的顶点数
D ： 与该顶点连通的顶点数
正确答案： C
解析：
无向图中一个顶点的度是指和该顶点关联的边的数目，一条边连接两个顶点，因此，无
向图中一个顶点的度也是和该顶点项邻接的顶点数。
345 、 单选题
按照二叉树的定义，具有3个结点的二叉树有()种。
A ： 3
B ： 4
C ： 5
D ： 6
正确答案： C
解析：
346 、 单选题
将两个长度为N的有序表归并到一个长度为2N的有序表，最少需要比较的次数是()，最
多需要比较的次数是()。
A ： N，2N-1
B ： N-l，2N
C ： N，2N
D ： N-l，2N-1
正确答案： A
解析：
对于此题而言最少的比较次数是，其中一个有序表的最后一个数小于另一表的的第一个
数，那么直接合并即可。当一个表递增一个表递减且递减表时，需要比较ZN-1次。347 、 单选题
以下属于逻辑结构的是()。
A ： 顺序表
B ： 哈希表
C ： 有序表
D ： 单链表
正确答案： C
解析：
数据结构分别为逻辑结构、存储结构(物理结构)和数据的运算。数据的逻辑结构是对数
据之间关系的描述，与数据元素本身的形式、内容、相对位置、所含结点个数都无关。
顺序表、哈希表、单链表都涉及到数据的存储结构，有序表是指表中数据有序，与逻辑
结构无关。
348 、 单选题
以比较为基础的排序算法在最坏情况下的计算时间下界为()。
正确答案： D
解析：
349 、 单选题
下列叙述正确的个数是()。(1)向二叉排序树中插入一个结点，所需比较的次数可能大于
此二叉排序树的高度。(2)对B-树中任一非叶子结点中的某关键字K，比K小的最大关键字
和比K大的最小关键字一定都在叶子结点中。(3)所谓平衡二叉树是指左、右子树的高度
差的绝对值不大于1的二叉树。(4)删除二叉排序树中的一个结点，再重新插入，一定能
得到原来的二又排序树。
A ： 4
B ： 3
C ： 2
D ： 1正确答案： D
解析：
只有第3项是正确的。
350 、 单选题
已知输入序列为abcd，经过输出受限的双端队列后，能得到的输出序列是()。
A ： dacb
B ： cadb
C ： dbca
D ： 以上答案都不对
正确答案： 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。
351 、 单选题
设n阶方阵是一个上三角矩阵，则需存储的元素个数为()。
A ： n
B ： n×n
C ： n×n/2
D ： n(n+1)/2
正确答案： D
解析：
在上三角矩阵中，第一行有1个元素，第二行有2个元素，…，第n行有n个元素，则
共n(n+1)/2个。
352 、 单选题
若一个具有n个结点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有()棵树。
A ： k
B ： nC ： n-k
D ： n+k
正确答案： C
解析：
一个具有n个结点的树有n-l条边，结点数比边数多1，则若一个森林中有m棵树，其结点
数比边数多m。反过来，森林中树的个数等于结点数减去边数。
353 、 单选题
设某数据结构的二元组形式表示
为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R=|r|，r={＜01，02＞，
＜01，03＞，＜01，04＞，＜02，05＞，＜02，06＞，＜03，07＞，＜03，08＞，
＜03，09＞}，则数据结构A是()。
A ： 图型结构
B ： 树型结构
C ： 物理结构
D ： 线性结构
正确答案： B
解析：
D中是数据结构中的结点，R为结点之间的关系，通过结点之间的关系可发现，此数据结
构是一个图结构，并且是有向图。
354 、 单选题
假设执行语句S的时间为0(1)，则执行下列程序段的时间为( )。
for(i=l; k=n; it+)
for(j=l;j S;
A ： 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)。
355 、 单选题
在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为()。
A ： 4
B ： 5
C ： 6
D ： 7
正确答案： C
解析：
根据题干中的描述可以画出树，度为零的结点共6个。
356 、 单选题
在一裸m阶的B+树中，每个非叶结点的儿子数S应满足()。
正确答案： A
解析：
m阶B+树包含如下两个特点：(1)每个分支结点至多有m棵子树。(2)除根结点外的所有非
终端结点每个结点至少有1(m+1)/21棵子树。
357 、 单选题
循环链表的主要优点是()。
A ： 不再需要头指针
B ： 已知某个结点的位置后，能很容易找到它的直接前驱结点
C ： 在进行删除操作后，能保证链表不断开
D ： 从表中任一结点出发都能遍历整个链表
正确答案： D
解析：
A项，头指针不能省略，因为没有头指针就没有办法引用该链表了；B项，循环链表还是
单链表，要找到直接前驱结点，必须至少循环遍历整个链表一次才行；C项，无论链表
是不是循环的，都能保证在删除时链表不断开；D项，因为循环链表首尾相接，形成一
个环，从循环链表中任何一个结点开始都能遍历整个链表。358 、 单选题
设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n.则这棵二叉中共有
()个结点。
A ： 2n+1
B ： n+1
C ： 2n-1
D ： 2n
正确答案： C
解析：
在二叉树中度为2的结点个数为度为零的结点数减一，所以二叉树共有2n-1个结点。
359 、 单选题
树形结构的特点是：一个结点可以有()。
A ： 多个直接前驱
B ： 多个直接后继
C ： 多个前驱
D ： 一个后继
正确答案： B
解析：
树的唯一根节点无前驱，叶子结点可以有多个且无后继，树的其他结点可以有多个后继
但只能有一个前驱。
360 、 单选题
Hash表是用于数据存储的一种有效的数据结构，Hash表的查找复杂度依赖于Hash值算
法的有效性，在最好的情况下，Hash表的查找复杂度为()。
A ： O(nlogn)
B ： O(logn)
C ： O(n)
D ： O(1)
正确答案： D
解析：
0(1)，哈希表是通过计算hashcode来定位元素位置，所以只需一次即可。361 、 单选题
在一棵高度为h的理想平衡二叉树中，最少含有()个结点，最多含有()个结点。
正确答案： D
解析：
362 、 单选题
在具有n个结点的单链表中，实现()的操作，其算法的时间复杂度都是O(n)。
A ： 遍历链表和求链表的第i个结点
B ： 在地址为P的结点之后插入一个结点
C ： 删除开始结点
D ： 删除地址为P的结点的后继结点
正确答案： A
解析：
A项，由于单链表是非随机存取的存储结构，遍历链表和求链表的第i个结点都必须从头
指针出发寻找，其时间复杂度为0(n)；B项，由于已知待插入结点的前驱结点，可以直接
实现插入，其时间复杂度为0(1)；CD两项，可以直接实现删除操作，其时间复杂度
为O(1)。
363 、 单选题正确答案： A
解析：
364 、 单选题
A ： 6
B ： 4
C ： 3
D ： 2
正确答案： C
解析：
365 、 单选题
将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为()。
A ： 4
B ： 5
C ： 6
D ： 7
正确答案： C
解析：
366 、 单选题一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足()。
A ： 所有的结点均无左孩子
B ： 所有的结点均无右孩子
C ： 只有一个叶子结点
D ： 是任意一棵二叉树
正确答案： C
解析：
先序遍历的次序为根一左一右，而后序遍历的次序为左一右一根，，先序遍历与后序遍
历相对次序可以相反的部分为根一左(对后序的左一根)，或者是根一右(对后序的右一根)，
所以满足条件的二叉树只有一个叶子结点。
367 、 单选题
一棵m阶非空B-树，每个结点最多有()棵子树。
A ： m/2
B ： m-1
C ： m
D ： m+1
正确答案： C
解析：
B-树中每个结点之多有m棵子树，m就是B-树的阶。
368 、 单选题
一个具有1025个结点的二叉树的高h为()。
A ： 11
B ： 10
C ： 11至1025之间
D ： 10至1024之间
正确答案： C
解析：
在具有n个结点的二叉树中完全二叉树的树高最小，其为[logn]+1，单支二叉树，即每层
只有一个结点，树高最大，其为n。因此，具有1025个结点的二叉树树高应在11至1025
之间。
369 、 单选题设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快
速排序的结果为()
A ： 3，2，5，8，6
B ： 2，3，5，8，6
C ： 3，2，5，6，8
D ： 2，3，6，5，8
正确答案： C
解析：
快速排序的每趟排序在待排序列中选取一个数为基准，将序列划分为两段，一段的值比
基准值小，另一段大于或等于基准值。
370 、 单选题
正确答案： D
解析：
考查双链表中插入操作，要注意保存后继节点。
371 、 单选题
设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为
()。
A ： q=p-＞next；p-＞data=q-＞data；p-＞next=q-＞next；free(q)；
B ： q=p-＞next；p-＞data=q-＞data；free(q)；
C ： q=p-＞next；p-＞next=q-＞next；free(q)；
D ： q=p-＞next；q-＞data=p-＞data；p-＞next=q-＞next；free(q)；
正确答案： A
解析：
应先使指针q指向结点A之后的结点，以防链表断裂，然后删除结点q，最后将删除的结
点q的存储空间释放。372 、 单选题
如果节点A有3个兄弟，B是A的双亲，则节点B的度是()。
A ： 3
B ： 4
C ： 1
D ： 2
正确答案： B
解析：
节点A有3个兄弟，B是A的双亲，则节点B的度是4。
373 、 单选题
若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，
则下面最合适的存储方式是()。
A ： 单链表
B ： 循环双链表
C ： 单循环链表
D ： 带有尾指针的单循环链表
正确答案： B
解析：
在链表中的最后一个结点之后插入个结点要知道终端结点的地址，所以，单链表、单循
环链表都不合适，删除最后一个结点要知道终端结点的前驱结点的地址，所以，带有尾
指针的单循环链表不合适，而循环双链表满足条件。
374 、 单选题
树最适合用来表示()。
A ： 元素之间无联系的数据
B ： 无序数据元素
C ： 元素之间具有分支层次关系的数据
D ： 有序数据元素
正确答案： C
解析：
树是一种具有层次结构的非线性结构，所以树适合用来存储元素之间具有分支层次关系
的数据。375 、 单选题
如果一棵完全二叉树共有26个结点，则必定有()个结点的度为1。
A ： 0
B ： 1
C ： 3
D ： 13
正确答案： B
解析：
26个结点，可知该二叉树有5层。由于前4层组成一棵满二叉树，共15个结点，则共有11
个叶子结点，可知只有1个结点的度为1。
376 、 单选题
若一个栈以向量V[1.n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是()。
A ： top=top+1；V[top]=x
B ： V[top]=x；top=top+1
C ： top=top-1；V[top]=x
D ： V[top]=x；top=top-1
正确答案： C
解析：
栈是运算受限的线性表，只允许在栈顶进行插入和删除操作。本题中栈顶指针为n+1，
该数组将栈顶放在了下标大的一端，所以在进行人栈操作时top指针应该进行减1操作。
通常元素进栈的操作为：先移动栈顶指针后存入元素。
377 、 单选题
在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的()倍：
A ： 1/2
B ： 2
C ： 1
D ： 4
正确答案： C
解析：
在有向图中每个顶点的入度就是另外一个顶点的出度，因此所有顶点的入度之和等于所
有顶点出度之和，等于有向图中所有的边数。378 、 单选题
二维数组A的每个元素是由6个字符组成的串，行下标的范围从0～8，列下标的范围是
从0～9，则存放A至少需要()个字节。
A ： 240
B ： 540
C ： 90
D ： 180
正确答案： B
解析：
数组A为9行10列，共有90个元素，所以，存放A至少需要90×6=540个存储单元。
379 、 单选题
以下说法正确的是()。
A ： 数据结构的逻辑结构是指数据的各数据项之间的逻辑关系。
B ： 数据元素是数据结构的最小单位。
C ： 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。
D ： 判断某个算法是否容易阅读是算法分析的任务之一。
正确答案： C
解析：
A项，数据结构的逻辑结构是指数据的各数据元素之间的逻辑关系，而不是数据项之间
的逻辑关系。B项，数据元素是数据结构的基本单位，数据结构的最小单位是数据项。D
项，算法分析是一个软件的验证确认任务，用于保证选择的算法是正确的、合适的和稳
定的，并且满足所有精确性、规模和时间方面的要求，保证产品高质量高效率的运行。
容易阅读是增加算法的可读性，不是算法分析的任务。
380 、 单选题
假设有k个关键字互为同义词，若用线性探查法把这k个关键字存入，至少要进行的探查
次数是()。
A ： k-1
B ： k
C ： k+1
D ： k(k+1)/2
正确答案： D
解析：假设有k个关键字互为同义词，若用线性探查法把这k个关键字存入，探查次数最少的情
况是第1个关键字通过1次比较后插入，第2个关键字通过2次比较后插入，…，第k个关
键字通过k次比较后插入。总的比较次数=1+2+…+k=k(k+1)/2。
381 、 单选题
已知串S=′aaab′，其next数组值为()。
A ： 0123
B ： 0213
C ： 0231
D ： 1211
正确答案： A
解析：
382 、 单选题
线性表的静态链表存储结构与顺序存储结构相比优点是()。
A ： 所有的操作算法实现简单
B ： 便于随机存取
C ： 便于插入与删除
D ： 便于利用零散的存储器空间
正确答案： C
解析：基础题。静态链表具有链表的插入和删除方便的优点，也不需要移动较多的元素。
383 、 单选题
判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用()。
A ： 广度优先遍历算法
B ： 深度优先遍历算法
C ： 求关键路径的方法
D ： 求最短路径的方法
正确答案： B
解析：
当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序(退
出DFSTraverse算法)即为逆向的拓扑序列。
384 、 单选题
用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是()。
A ： 94，32，40，90，80，46，21，69
B ： 32，40，21，46，69，94，90，80
C ： 21，32，46，40，80，69，90，94
D ： 90，69，80，46，21，32，94，40
正确答案： C
解析：
直接插入排序对于基本有序的序列进行排序效率最高。
385 、 单选题
设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为
基准而得到一趟快速排序的结果是()。
A ： 42，40，45，80，85，88
B ： 40，42，45，55，80，85
C ： 42，40，45，55，80，85
D ： 42，40，45，85，55，80
正确答案： C
解析：
快速排序是通过一趟排序将待排序的记录分割为独立的两部分，其中一部分记录的关键
字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序。本题选择第一个数为基准进行划分，分别从右边查找小于45的数和从左边
找大于或等于45的数，不断进行交换，第一趟结束后，即得到第一次划分结果。
386 、 单选题
设有关键字序列F={Q，G，M，Z，A，N，P，X，H}，下面()序列是从上述序列出发建堆
的结果。
A ： G，H，M，N，P，Q，X，Z
B ： A，G，M，H，Q，N，P，X，Z
C ： G，M，Q，A，N，P，X，H，Z
D ： H，0，M，P，A，N，Q.X.Z
正确答案： B
解析：
本题考查堆建立算法。
387 、 单选题
A ： 顶点序列
B ： 边序列
C ： 权值总和
D ： 边的条数
正确答案： A
解析：
388 、 单选题
下列排序算法中，时间复杂度不受数据初始状态影响恒为O(nlogn)的是()。
A ： 堆排序
B ： 冒泡排序
C ： 快速排序
D ： 直接插入排序
正确答案： A解析：
堆排序和快速排序是O(nlogn)的复杂度，但是快速排序在数据初始状态有序的情况下蜕
化为冒泡排序。
389 、 单选题
设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入
的结点X，则在结点A和结点B插入结点X的操作序列为()。
A ： p-＞next=s；s-＞next=q；
B ： q-＞next=s；s-＞next=p；
C ： p-＞next=s-＞next；s-＞next=p；
D ： s-＞next=p-＞next；p-＞next=-s；
正确答案： B
解析：
插入s结点，应使s的next指针指向p结点，使q结点的next指针指向s。
390 、 单选题
设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行()趟
的分配和回收才能使得初始关键字序列变成有序序列。
A ： 3
B ： 8
C ： 5
D ： 6
正确答案： A
解析：
因为待排序列中最大的数为三位数，所以需要进行3次。
391 、 单选题
设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续
的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地
址之差为()。
A ： 55
B ： 19
C ： 28
D ： 10
正确答案： B解析：
最后一行的第四列有4个元素，第五行前共有5行，而每个元素占一个字节，并且存储单
元共有55个。
392 、 单选题
A ： abcfdeg
B ： abcgfde
C ： abcdefg
D ： abcfgde
正确答案： A
解析：
本题考查深度优先算法。
393 、 单选题
已知10个数据元素为(54，28，16，34，73，62，95，60，23，43)，按照依次插入结
点的方法生成一棵二叉排序树后，查找值为62的结点所需比较的次数为()。
A ： 2
B ： 3
C ： 4
D ： 5
正确答案： B
解析：
将这10个元素按照依次插入结点的方法生成一棵二叉排序树后，62位于这棵二叉排序树
的第三层，查找值为62的结点所需要的次数恰好是从二叉排序树的根到被查结点的树的
深度。
394 、 单选题
对于序列(49，38，65，97，76，13，27，50)按由小到大进行排序，初始步长d-4的希
尔排序法第一趟的结果的是()。A ： 49，76，65，13，27，50，97，38
B ： 13，27，38，49，50，65，76，97
C ： 97，76，65，50，49，38，27，13
D ： 49，13，27，50，76，38，65，97
正确答案： D
解析：
根据希尔排序的规则，d-4的第一趟排序过程为第n个位置和第n+4个元素比较，并将较
小的元素换到前面，49和76不用互换、38和13互换、65和27互换，……，第一趟排序
后的结果为49，13，27，50，76，38，65，97。
395 、 单选题
设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选择()
方法。
A ： 冒泡排序
B ： 快速排序
C ： 堆排序
D ： 基数排序
正确答案： C
解析：
堆排序一趟排好一个记录，按大根堆建堆，排序10题挑选前10个最大的元素。
396 、 单选题
有关二叉树下列说法正确的是()。
A ： 二叉树的度为2
B ： 一棵二树的度可以小于2
C ： 二叉树中至少有一个结点的度为2
D ： 二叉树中任何一个结点的度都为2
正确答案： B
解析：
二叉树的特点是每个结点至多有两棵子树，即不存在度大于2的结点。B项是说可以小
于2，符合二叉树的特点。
397 、 单选题
将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为()。A ： O(n)
B ： 0(1)
C ： O(m)
D ： O(m+n)
正确答案： C
解析：
要将长度为n的单链表接在长度为m的单链表之后，必须从单链表的头结点沿链找到长
度为m的单链表的最后一个结点，所以时间复杂度为O(m)。
398 、 单选题
用二分(对半)查找表的元素的速度比用顺序法的速度要()。
A ： 必然快
B ： 必然慢
C ： 相等
D ： 不能确定
正确答案： D
解析：
两者的查找速度要看元素是否有序以及所找元素所在的位置。比如：如果要查找的元素
是表的第一个元素，则顺序查找速度要快。如果要查找的元素刚好位于顺序表的中间位
置，则二分查找更快。
399 、 单选题
设有序表中有1000个元素，则用二分查找元素X最多需要比较()次。
A ： 15
B ： 10
C ： 17
D ： 25
正确答案： B
解析：
二分查找每趟都使用序列的中间值与关键字比较，直至查找成功或失败。
400 、 单选题
高度为5(除叶子层之外)的三阶B-树至少有()个结点。
A ： 30B ： 31
C ： 32
D ： 33
正确答案： B
解析：
401 、 单选题
采用邻接表存储的图的广度优先遍历算法类似于树的()。
A ： 中根遍历
B ： 先根遍历
C ： 后根遍历
D ： 按层次遍历
正确答案： D
解析：
图的广度优先遍历算法思想是，对于某个结点，首先遍历该结点，而后遍历其相邻的所
有结点，而树的层次遍历中，对于某个结点，首先遍历该结点，然后遍历其所有的子结
点。
402 、 单选题
设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，
每个元素占一个空间，问A[3][3]存放在什么位置？脚注(10)表示用10进制表示。()
A ： 678
B ： 688
C ： 692
D ： 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。
403 、 单选题以下排序方法中，在初始序列已基本有序的情况下，排序效率最高的是()。
A ： 归并排序
B ： 直接插入排序
C ： 快速排序
D ： 堆排序
正确答案： B
解析：
直接插入排序对于基本有序的序列进行排序效率最高。
404 、 单选题
二叉排序树中左子树上所有结点的值均()根结点的值。
A ：
B ： =
C ：
D ： =
正确答案： A
解析：
二叉排序树的左子树的结点的值全部小于根结点的值，并且根结点的值小于右子树左右
结点的值。
405 、 单选题
设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表
中需要做()次线性探测。
A ： n(n+1)
B ： n
C ： n(n+1)/2
D ： n(n-1)/2
正确答案： D
解析：
线性探测解决冲突的办法指一旦目标空间被占有，则探测相邻的下一个空间，如果空闲
则插入，否则继续向下一个探测，如果到了队列末尾则返回队列头探测，一旦全部空间
都被占据则无法插入。
406 、 单选题在数据结构中，与所使用的计算机无关的是数据的()结构。
A ： 逻辑
B ： 存储
C ： 逻辑和存储
D ： 物理
正确答案： A
解析：
物理结构又称存储结构。逻辑结构描述的是数据元素之间的关系，与所使用的计算机无
关，而存储结构是逻辑结构在计算机中的表示，与具体使用的计算机有关。
407 、 单选题
设用数组A[1，n]作为两个栈S1、S2的共用存储空间，对任一个栈，只有当数组A[1，n]
全满时才不作入栈操作，则分配这两个栈空间的最佳方案是()。
A ： S1的栈底位置设为1，S2的栈底位置设为n
B ： S1的栈底位置设为n/2，S2的栈底位置设为n/2+1
C ： S1的栈底位置设为1，S2的栈底位置设为n/2
D ： S1的栈底位置设为n/2，S2的栈底位置设为1
正确答案： A
解析：
由于栈中元素个数不固定，因此如果将栈底设在中间位置，固定了栈中元素的个数，不
能满足只有当数组全满时才不作入栈操作的要求。
408 、 单选题
在含有12个结点的平衡二叉树上，查找关键字为35(存在该结点)的结点，则依次比较的
关键字有可能是()。
A ： 46，36，18，20，28，35
B ： 47，37，18，27，36
C ： 27，48，39，43，37
D ： 15，45，55，35
正确答案： D
解析：409 、 单选题
对于栈操作数据的原则是()。
A ： 先进先出
B ： 后进先出
C ： 后进后出
D ： 不分顺序
正确答案： B
解析：
栈的特点就是后进先出，入栈和出栈的操作只能在栈顸进行.而队列的特点是先进先出，
这两点容易混淆，要注意区分。
410 、 单选题
数据序列{8，9，10，4，5，6，20，1，2}只能是()算法的两趟排序后的结果。
A ： 直接选择排序
B ： 冒泡排序
C ： 直接插入排序
D ： 堆排序
正确答案： C
解析：
直接选择排序基本思想：第i趟排序开始时，当前有序区和无序区分别为R[0..i-1]
和R[i..n-1](0≤j＜n-1)，该趟排序则是从当前无序区中选出关键字最小的记录R[k]，将它
与无序区的第1个记录R[i]交换，使R[0..i]和R[i+1..n-1]分别变为新的有序区和新的无序区。
冒泡排序基本思想：起泡排序也叫冒泡排序，通过无序区中相邻记录关键字间的比较和
位置的交换，使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。直接插
入排序基本思想：将当前无序区的第1个记录R[i]插入到有序区R[0..i-1]适当的位置上，
使R[0..i]变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。
堆排序基本思想：堆排序是一种树形选择排序，它的特点是：在排序过程中，将R[1..n]
看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的
内在关系，在当前无序区中选择关键字最大(或最小)的记录。前两个数据有序且不是全
局有序，与直接插入排序的过程吻合。解此题要熟知各种排序方法的基本思想。411 、 单选题
正确答案： C
解析：
412 、 单选题
无向图G=(V，E)，其中V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，
f)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是()。
A ： a，b，e，c，d，f
B ： a，c，f，e，b，d
C ： a，e，b，c，f，d
D ： a，e，d，f，c，b
正确答案： C
解析：
假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，
则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过：然后依次从v
出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍
历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。
若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，
直至图中所有顶点均已被访问为止。
413 、 单选题
在线索二叉树中，一个结点是叶子结点的充要条件为()。
A ： 左、右线索标志均为0
B ： 左、右线索标志均为1
C ： 左线索标志为0，右线索标志为1
D ： 左线索标志为1，右线索标志为O正确答案： A
解析：
一个结点是叶子结点的充要条件是没有左孩子，并且没有右孩子。
414 、 单选题
求最短路径常用的算法有()。
A ： Prim算法和Kruskal算法
B ： 深度优先遍历算法和广度优先遍历算法
C ： Dijkstra算法和Floyd算法
D ： 拓扑排序算法
正确答案： C
解析：
A项是最小生成树的算法，B项是图的遍历算法，D项中的回溯法是求解递归过程的一种
重要方法。
415 、 单选题
下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数
据初始特性影响的是()。
A ： 直接插入排序
B ： 快速排序
C ： 直接选择排序
D ： 堆排序
正确答案： B
解析：
对于快速排序，一趟扫描完成关键记录所放的位置就是该元素的最终位置。若数据初始
情况就基本有序，则快速排序会退化为冒泡排序；若数据初始特性能够使每趟排序划分
的两块大小相当，则排序效率会比较高。
416 、 单选题
对关键码序列28，16，32，12，60，2，5，72快速排序.从小到大一次划分结果为()。
A ： (2，5，12，16)26(60，32，72)
B ： (5，16，2，12)28(60，32，72)
C ： (2，16，12，5)28(60，32，72)
D ： (5，16，2，12)28(32，60，72)正确答案： B
解析：
根据快速排序的思想，容易得到序列28，16，32，12，60，2，5，72一次排序后的结果
(5，16，2，12)28(60，32，72)。
417 、 单选题
设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是()。
A ： 51234
B ： 45123
C ： 43125
D ： 32154
正确答案： D
解析：
栈的进出原则是先进后出原则，要不就是先进先出原则。A选项中5最先出，说明1234都
在栈里，这样说明1是在栈低，则先不出来。BD的原因一样，所以答案选择D。
418 、 单选题
在向图的邻接矩阵表示中，计算第i个顶点八度的方法是()。
A ： 第i行非零元素个数
B ： 第i列非零元素个数
C ： 第i行零元素个数
D ： 第i列零元素个数
正确答案： B
解析：
先用一个二维数组Edge存储表示邻接矩阵，输入文件中顶点的序号是从1开始，当输入
一条有向边＜u，v＞时，将Edge[u-1][v-1]=1即可；第i+1个顶点的出度等于邻接矩阵中
第i行所有元素中元素值为1的个数，把第i行所有元素值累加起来，得到的结果也是该顶
点的出度，同理，在计算第i+1个顶点的入度时，也只需要将第i列所有元素值累加起来
即可。
419 、 单选题
以下关于二叉排序树的说法正确的是()。Ⅰ.在二叉排序树中，每个结点的关键字都比左
孩子关键字大，比右孩子关键字小Ⅱ.每个结点的关键字都比左孩子关键字大，比右孩子
关键字小，这样的二叉树都是二叉排序树Ⅲ，在二叉排序树中，新插入的关键字总是处
于最底层Ⅳ.在二叉排序树中，新结点总是作为叶子结点来插入的Ⅴ.二叉排序树的查找
效率和二叉排序树的高度有关A ： Ⅰ、Ⅱ、Ⅳ、Ⅴ
B ： Ⅱ、Ⅲ、Ⅳ
C ： Ⅰ、Ⅲ、Ⅴ
D ： Ⅰ、Ⅳ、Ⅴ
正确答案： D
解析：
在二叉排序树中，新插入的关键字总是作为叶子结点来插入的，但是叶子结点不一定总
是处于最底层。对于二叉排序树，左子树上所有记录的关键字均小于根记录的关键字；
右子树上所有记录的关键字均大于根记录的关键字。而不是仅仅与左、右孩子的关键字
进行比较。
420 、 单选题
已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为()。
A ： DBACEF
B ： DABECF
C ： BCDEAF
D ： 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.
421 、 单选题
由同一关键字集合构造的各棵二叉排序树()。
A ： 其形态不一定相同，但平均查找长度相同
B ： 其形态不一定相同，平均查找长度也不一定相同
C ： 其形态均相同，但平均查找长度不一定相同
D ： 其形态均相同，平均查找长度也都相同
正确答案： B
解析：
由同一关键字集合构造的各棵二叉排序树，其形态不一定相同，平均查找长度也不一定相同。
422 、 单选题
若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常
选用的辅助结构是()。
A ： 栈
B ： 线性表
C ： 队列
D ： 二叉排序树
正确答案： A
解析：
栈(stack)又称为堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插
入和删除运算，这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素
称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
从一个栈删除元素称作出栈或退栈，它是把栈顶元素删除，使其相邻的元素成为新的栈
顶元素。
423 、 单选题
用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1]～A[n]中，结点A[i]若
有左子树，则左子树的根结点是()。
A ： [i/2]
B ： A[2i]
C ： A[2i-1]
D ： A[2i+1]
正确答案： B
解析：
据二叉树的性质5，对完全二叉树从上到下、从左至右给结点编号，若编号为2i的结点存
在，则i的左子树一定是A[2i]。
424 、 单选题
有A，B，C，D，E5个元素按次序入栈，在各种可能的出栈次序中，以元素C，D最先出
栈的序列中，下列正确的一组是()。
A ： CDBAECDABE
B ： CDEBACDBEA
C ： DEABCDABE
D ： CEBAECDAEB正确答案： B
解析：
只有A、B、C先入栈，才能CD作为第一、二个元素出栈。C出栈，D入栈，D出栈；接着
就剩下A、B在栈中，E未入栈，共3个元素，此三者序列为BAE，BEA，EBA。
425 、 单选题
下列叙述正确的个数是()。(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 ： 3
B ： 4
C ： 5
D ： 6
正确答案： D
解析：
426 、 单选题
查找效率最高的二叉排序树是()。
A ： 所有结点的左子树都为空的二叉排序树
B ： 所有结点的右子树都为空的二叉排序树
C ： 平衡二叉排序树
D ： 没有左子树的二叉排序树
正确答案： C
解析：
对于结点个数相同的二叉排序树，平衡二叉排序树的深度最小。而二叉排序树的查找效
率取决于二叉排序树的深度。427 、 单选题
设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24
的元素需要经过()次比较。
A ： 4
B ： 2
C ： 3
D ： 1
正确答案： C
解析：
二分查找法的每一次查找都要与中间值进行比较，所以24第一次与35比较，因为24小
于35，所以接下来在35的左半部分中进行查找，左半部分的中间值为18，4大于18，接
下来去18的右半部分查找，24与24进行比较，此时，查找成功，共比较了3次。
428 、 单选题
在存储数据时，通常不仅要存储各数据元素的值，而且还要存储()。
A ： 数据的处理方法
B ： 数据元素的类型
C ： 数据元素之间的关系
D ： 数据的存储方法
正确答案： C
解析：
在存储数据时，需要存储数据元素的值和数据元素之间的关系。
429 、 单选题
含有n个叶子结点的最优二叉树中共有分支结点数是()。
A ： n-2
B ： n-1
C ： 2n-1
D ： 2n+1
正确答案： B
解析：
最优二叉树，又叫哈夫曼树.根据哈夫曼树的构造方法.可以得出非叶子节点都有双分支，
分支结点数等于叶子结点减1。这样，n个叶子结点的最优二叉树中共有分支结点数是n-l。430 、 单选题
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次。
431 、 单选题
若对序列(tang，deng，an，wang，shi，bai，fang，liu)采用选择排序法按字典顺序进
行排序，下面给出的四个序列中，()是第三趟的结果。
A ： an.bai，deng，wang，tang，fang，shi，hu
B ： an，bai，deng，wang，shi，tang，fang，liu
C ： an.bai，deng，wang，shi，fang，tang，liu
D ： 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。
432 、 单选题
下面关于工程计划的AOE网的叙述中，不正确的是()。
A ： 某些关键活动若提前完成，那么整个工程将会提前完B ： 关键活动不按期完成就会影响整个工程的完成时间
C ： 任何一个关键活动提前完成，那么整个工程将会提前完成
D ： 所有的关键活动都提前完成，那么整个工程将会提前完成
正确答案： C
解析：
AOE网中的关键路径可能不止一条，如果某一个关键活动提前完成，还不能提前整个工
程，则必须同时提高在几条关键路径上的关键活动。
433 、 单选题
正确答案： C
解析：
434 、 单选题
用邻接矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度m路径相连，则只要检
查()的第i行和第j列的元素是否为零即可。
A ： mA
B ： A
C ： Am
D ： Am-1
正确答案： C解析：
要判断相邻矩阵A中任意两个顶点Vi和Vj之间是否有长度为m的路径相连，只要检查Am
的第i行第j的元素是否为0即可，若为0则无，否则就存在。
435 、 单选题
单向链表中往往含有一个头结点，该结点不存储数据元素，一般令链表的头指针指向该
结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，
错误的是()。
A ： 若在头结点中存入链表长度值，则求链表长度运算的时间复杂度为O(1)
B ： 在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理
C ： 加入头结点后，在链表中进行查找运算的时间复杂度为O(1)
D ： 加入头结点后，代表链表的头指针不因为链表为空而改变
正确答案： C
解析：
在链表中加入头结点后，查找表中某一元素仍然要从头指针出发，顺序找到目标元素或
失败时找到表尾为止，时间复杂度与表长成正比。故D项错误。
436 、 单选题
在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找
成功的情况下，所探测的这些位置的键值()。
A ： 一定都是同义词
B ： 一定都不是同义词
C ： 不一定都是同义词
D ： 都相同
正确答案： C
解析：
采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。
437 、 单选题
对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1
趟划分过程中，元素移动次数最多的是()。
A ： 70，75，82，90，23，16，10，68
B ： 70，75，68，23，10，16，90，82
C ： 82，75，70，16，10，90，68，23
D ： 23，10，16，70，82，75，68，90正确答案： A
解析：
快速排序第一趟划分的方法是：将第1个元素放在最终排好序列的最终位置上，则在这
个位置右边小于该元素值的元素都移到其左边，则在这个位置左边小于该元素值的元素
都移到其右边。
438 、 单选题
设一组初始记录关键字的长度为8，则最多经过()趟插入排序可以得到有序序列。
A ： 8
B ： 7
C ： 9
D ： 6
正确答案： B
解析：
插入排序的每一趟在待排元素中取出第一个元素，移至有序序列的适当的位置，所以共
八个关键字的序列，最多经过7趟插入排序就可以得到一个有序序列。
439 、 单选题
设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为()。
正确答案： B
解析：
440 、 单选题
n个顶点的连通图至少有多少条边()。
A ： n-1
B ： n
C ： n+1D ： 0
正确答案： A
解析：
至少要有(n-1)条边(也就是树)才能保证图为连通图。
441 、 单选题
A[N，N]是对称矩阵，将下三角(包括对角线)以行序存储到一维数组T[N(N+l)/2]q中，则
对任一上三角元素A[i][j]对应T[k]的下标k是()。
A ： i(1-1)/2+j
B ： j(j-1)/2+i
C ： i(j-i)/2+1
D ： 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。
442 、 单选题
在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。
A ： 顺序查找
B ： 二分法
C ： 利用二叉搜索树
D ： 利用哈希(hash)表
正确答案： D
解析：
利用哈希(hash)表与结点个数n无关。
443 、 单选题
以下数据结构中，属于非线性数据结构的是()，
A ： 树
B ： 队列
C ： 栈D ： 字符串
正确答案： A
解析：
线性结构是一个数据元素的有序(次序)集合。它有四个基本特征：(1)集合中必存在唯一
的一个“第一个元素”；(2)集合中必存在唯一的一个“最后的元素”；(3)除最后元素之
外，其它数据元素均有唯一的“后继”；(4)除第一元素之外，其它数据元素均有唯一
的“前扑”。数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的
数据结构。线性结构包括线性表(如结构体数组，结构体链表)、一维数组、字符串、堆
栈、队列。
444 、 单选题
设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数
是()。
A ： 5
B ： 6
C ： 7
D ： 8
正确答案： D
解析：
445 、 单选题
根据使用频率，构造的5个字符的哈夫曼编码不可能是()。
A ： 111，110，10，01，00
B ： 000，001，010，011，1
C ： 100，11，10，1，0
D ： 001，000，01，11，10
正确答案： C
解析：
C项中100和10冲突，即一个结点既是叶子结点又是内部结点，哈夫曼树中不可能出现这
种情况。
446 、 单选题一个有n个结点的图，最多有()个连通分量。
A ： 0
B ： 1
C ： n-1
D ： n
正确答案： D
解析：
无向图中的极大连通子图称为图的连通分量。图的连通分量的个数小于或等于图的结点
数。当图的各个结点彼此都没有边相连时，连通分量数最大为n。
447 、 单选题
设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F
中，第一棵树的结点个数是()。
A ： m-n
B ： m-n-1
C ： n+1
D ： 条件不足，无法确定
正确答案： A
解析：
森林转换成二叉树的原则：将第一棵树的根结点作为根结点，所有结点的第一个左孩子
作为左孩子，下一个兄弟结点作为右孩子，其它树作为第一棵树的右孩子。所以森林F
中第一棵树的结点个数是m-n。
448 、 单选题
设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为()。
正确答案： D
解析：449 、 单选题
在由4棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别
为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点
个数为()。
A ： 20
B ： 29
C ： 30
D ： 35
正确答案： B
解析：
当把森林转换成二叉树后，第二、第三和第四棵树均在第一棵树的根结点的右子树上。
450 、 单选题
若用一个大小为6的一维数组来实现循环队列，且当前front和rear的值分别为3，0，当
从队列中删除一个元素，再加入两个元素后，front和rear的值分别为()。
A ： 5，1
B ： 4，2
C ： 2，4
D ： 1，5
正确答案： B
解析：
删除front=(front+1)mod6，加入：rear=(rear+1)mod6。
451 、 单选题
对特殊矩阵采用压缩存储的目的主要是为了()。
A ： 去掉矩阵中的多余元素
B ： 减少不必要的存储空间
C ： 表达变得简单
D ： 对矩阵元素的存取变得简单
正确答案： B
解析：
在特殊矩阵中，有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素
重复存储。452 、 单选题
对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()。
正确答案： C
解析：
453 、 单选题
当各边上的权值满足()的条件时，BFS算法可用来解决单源最短路径问题。
A ： 均相等
B ： 均互不相等
C ： 不一定相等
D ： 其他
正确答案： A
解析：
单源最短路径问题是指：从已知图G=(V，E)中找出某给定的源结点S∈V到V中的每个结
点的最短路径。当各边上的权值均相等时，BFS算法可用来解决单源最短路径问题。
454 、 单选题
无向图的邻接矩阵是一个()。
A ： 对称矩阵
B ： 无规律
C ： 上三角矩阵
D ： 下三角矩阵
正确答案： A
解析：
两个顶点邻接是相互的，1和2邻接，2和1也就邻接了。455 、 单选题
两个字符串相等的充要条件是()。
A ： 两个字符串中对应位置上的字符相等
B ： 两个字符串的长度相等
C ： 同时具备(A)和(B)两个条件
D ： 两个字符串的大小相等
正确答案： C
解析：
两个字符串相等是指两个字符串不仅长度相等，而且在对应位置上的字符也要相等。
456 、 单选题
()在其最好情况下的算法时间复杂度为O(n)。
A ： 插入排序
B ： 归并排序
C ： 快速排序
D ： 堆排序
正确答案： A
解析：
457 、 单选题
中缀表达式A-(B+C/D)*E的后缀形式是()。
A ： B-C+D/E*
B ： ABC+D/-E*
C ： ABCD/E*+-
D ： ABCD/+E*-
正确答案： D
解析：
将中缀表达式表示成二叉树的形状，则这棵二叉树的后序遍历序列即为表达式的后缀形
式。458 、 单选题
已知二叉树的前序序列为ABCDEFG，中序序列为DBCAFEG，则后序序列为()。
A ： DCBAFGE
B ： DCBFGEA
C ： DCBFEGA
D ： CBGFEA
正确答案： B
解析：
本题考查的是二叉树的遍历过程。在本题中，由于前序遍历首先访问的是根结点，所以
根结点是A，又由于后序遍历最后访问的是根结点，所以排除选项A；根据中序序列知道，
DBC是左子树的结点，FEG是右子树的结点。
459 、 单选题
设无向图的顶点个数为n，则该图最多有()条边。
正确答案： B
解析：
460 、 单选题
某二叉树的前序遍历序列为UKLMNO，中序遍历序列为JLKINMO，则后序遍历序列为()。
A ： JLKMNOI
B ： LKNJOMI
C ： LKJNOMI
D ： LKNoMI
正确答案： C
解析：461 、 单选题
A ： 中序
B ： 前序
C ： 后序
D ： 层次
正确答案： B
解析：
根据Process(p)；Traverse(P^.left)；Travrse(P^.right)语句的顺序可知其遍历的顺序是根
一左一右次序，所以为先序遍历算法。
462 、 单选题A ： 4
B ： 5
C ： 6
D ： 7
正确答案： C
解析：
右节点均为原来森林的树。将T2还原为森林T1，其中有6棵树：C、D、F、G，I和J是叶
子结点。
463 、 单选题
设顺序循环队列Q[O：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的
前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为()。
A ： (F-R+M)%M
B ： F-R
C ： (R-F+M)%M
D ： R-F
正确答案： C
解析：
(R-F+M)%M是计算顺序循环队列元素个数的公式。
464 、 单选题
下列说法中不正确的是()。
A ： 图的遍历过程中每一顶点仅被访问一次
B ： 遍历图的基本方法有深度优先搜索和广度优先搜索两种
C ： 图的深度优先搜索的方法不适用于有向图
D ： 图的深度优先搜索是一个递归过程
正确答案： C
解析：图的深度优先搜索的方法对于有向图和无向图都适用。
465 、 单选题
设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是()。
A ： head==0
B ： head-＞next==0
C ： head！=0
D ： head-＞next==head
正确答案： A
解析：
因为单链表没有头结点，所以当头指针为空时证明链表为空。
466 、 单选题
设一个顺序有序表A[1：14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元
素的顺序为()。
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的元素比较，依次类推。
467 、 单选题
非空的循环单链表FIRST的尾结点(由P所指向)满足：()。
A ： P—＞EXT=NULL；
B ： P=NULL；
C ： P—NEXT-FIRST；
D ： P=FIRST；
正确答案： C
解析：
循环单链表是单链表的一种特殊形式，其结构特点是链表中最后一个结点的指针域不再
是结束标记(NULL)，而是指向链表中的第一个结点，从而使链表形成一个环。在本题中，
FIRST指向循环单链表的首结点，P指向尾结点，可知P—＞NEXI=FIRST。468 、 单选题
若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为()。
A ： BCAGFED
B ： DAEBCFG
C ： ABCDEFG
D ： BCAEFGD
正确答案： B
解析：
由前序序列和中序序列先构造出二叉树，然后按层次序列进行访问。
469 、 单选题
m阶B+树中除根节点外，其他节点的关键字个数至少为()。
A ： [m/2]
B ： [m/2]-1
C ： [m/2]+1
D ： 任意
正确答案： A
解析：
这是B+树的定义。
470 、 单选题
已知数据元素为(34，76，45，18，26，54，92，65)，按照依次插入结点的方法生成一
棵二叉排序树，则该树的深度为()。
A ： 6
B ： 7
C ： 4
D ： 5
正确答案： D
解析：
根据二叉排序树插入结点算法，将上述8个数据元素按照依次插入结点的方法构造出一
棵二叉排序树后，该树的最大层次为5，故该树的深度为5。471 、 单选题
以下不是栈的基本运算的是()。
A ： 删除栈顶元素
B ： 删除栈底元素
C ： 判断栈是否为空
D ： 将栈置为空栈
正确答案： B
解析：
栈的基本运算有入栈、出栈(删除栈顶元素)、初始化、置空、判断栈是否为空或满、提
取栈顶元素等，对栈的操作都是在栈顶进行的。
472 、 单选题
高度为7的AVL树最少有()个结点。
A ： 31
B ： 32
C ： 33
D ： 34
正确答案： C
解析：
473 、 单选题
散列函数有一个共同的性质，即函数值应当以()概率取其值域的每个值。
A ： 最大概率
B ： 最小概率
C ： 平均概率
D ： 同等概率
正确答案： D
解析：
散列函数的构造万痃有很多，每种构造方法的目的都是尽量减少冲突。为了减少冲突计算出的结果应以同等概率分布到值域的各个部分。
474 、 单选题
设一条单链表的头指针为head且该链表没有头节点，则其判空条件是()。
A ： head==NULL
B ： head-＞next==NULL
C ： head！=NULL
D ： head-＞next==head
正确答案： A
解析：
因为单链表没有头节点，所以当头指针为空时证明链表为空。
475 、 单选题
将5个字母“ooops”按此顺序入栈，则有()种不同的出栈顺序可以仍然得到“ooops”。
A ： 1
B ： 3
C ： 5
D ： 6
正确答案： C
解析：
此题可以首先列出所有可能的出栈顺序，然后列出各个出战顺序的结果，计数即可。
476 、 单选题
关键路径是AOE网中()。
A ： 最长的回路
B ： 最短的回路
C ： 从源点到终点的最长路径
D ： 从源点到终点的最短路径
正确答案： C
解析：
关键路径是指从开始顶点到结束顶点的最短路径，路径的长度也是工程完成的最少时间。
关键活动是指关键路径上的所有活动，关键活动的最大特征是该活动的最早开始时间等
于该活动所允许的最迟开始时间。477 、 单选题
二叉树的第k层的结点数最多为()。
A ： 2K-1
B ： 2K+1
C ： 2K
D ： 2
正确答案： A
解析：
二叉树第k层最多有2k-1个结点。
478 、 单选题
在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左
孩子的平衡因子为0，右孩子的平衡因子为1，则应作()型调整以使其平衡。
A ： LL
B ： LR
C ： RL
D ： RR
正确答案： C
解析：
平衡二叉树是在构造=叉排序树的过程中，每当插入一个新结点时，首先检查是否因插
入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持
二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系。进行相应的
旋转，使之成为新的平衡子树。具体步骤如下：(1)每当插入一个新结点，从该结点开始
向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结
点的平衡因子的绝对值均不超过1，则平衡=叉树没有失去平衡，继续插入、结点；(2)若
插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结
点；(3)判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调
整；(4)如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，
应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次
最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子
树。在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；(5)计算调整后的平衡
二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整
后的平衡二叉树中是否存在平衡因子大于1的结点。结合上面的知识点，对于题目中的
情况应该选择RL型调整。
479 、 单选题
在二叉排序树中插入一个结点的时间复杂度为()。正确答案： B
解析：
在二叉排序树中进行插入时最坏情况下时间复杂度是O(n)。
480 、 多选题
以下关于线性结构特点的描述，正确的是()。
A ： 除第一个之外，集合中的每个数据元素均只有一个前驱
B ： 存在唯一的一个被称作“第二个”的数据元素
C ： 存在唯一的一个被称作“第一个”的数据元素
D ： 它是最原始的一种数据结构
正确答案： A，C
解析：
线性表具有唯一的第一个节点和唯一的最后一个节点。
481 、 多选题
下列说法正确的是()。
A ： 边界标识法是操作系统中用以进行动态分区分配的一种存储管理方法
B ： 存储紧缩的优点是算法简单、速度快
C ： 伙伴系统是一种动态存储管理方法
D ： 存储紧缩是一种动态存储管理方法
正确答案： A，C，D
解析：
边界标识法是操作系统中用以进行动态分区分配的一种存储管理方法，一般把空闲块链
接成一个双重循环链表；伙伴系统是操作系统中用到的另一种动态存储管理方法，在伙
伴算法中，无论是占用块或空闲块，其大小均为2的k次幂。伙伴系统和边界标识法是操
作系统中用以进行动态分区分配的存储管理方法。“存储紧缩”是“堆”结构的动态存
储管理方法。482 、 多选题
下列数据结构中，属于线性数据结构的是()。
A ： 栈
B ： 队列
C ： 图
D ： 树
正确答案： A，B
解析：
从数据结构角度看，树形结构是一类重要的非线性数据结构；栈和队列是线性表，其特
殊性在于它们是操作受限的线性表；图是一种较线性表和树更为复杂的数据结构，在图
形结构中，节点之间的关系可以是任意的，所以不是线性结构。
483 、 多选题
线性表的特点正确的()。
A ： 存在唯一的一个被称作“第一个”的数据元素
B ： 存在唯一的一个被称作“最后一个”的数据元素
C ： 不存在唯一的一个被称作“第一个”的数据元素
D ： 不存在唯一的一个被称作“最后一个”的数据元素
正确答案： A，B
解析：
线性表存在唯一一个第一个元素和最后一个元素。
484 、 多选题
以下数据结构中属于线性数据结构的是()。
A ： 线性表
B ： 队列
C ： 二叉树
D ： 栈
正确答案： A，B，D
解析：
树和二叉树都是非线性结构。
485 、 多选题
抽象数据类型按其值的不同特性可分为()。A ： 分子类型
B ： 固定聚合类型
C ： 离子类型
D ： 可变聚合类型
E ： 原子类型
正确答案： B，D，E
解析：
抽象数据类型按其值的不同特性可分为固定聚合类型、可变聚合类型、原子类型。
486 、 多选题
下列说法正确的是()。
A ： 在图形结构中节点之间的关系可以是任意的
B ： 线性表中数据元素之间仅有线性关系
C ： 简单路径中序列中顶点可以重复出现
D ： 邻接表是图的一种链式存储结构
正确答案： A，B，D
解析：
图结构中节点的关系是任意的，邻接表和邻接矩阵都是图的存储结构。
487 、 多选题
下面属于常用的表示树的链表结构的有()。
A ： 双亲表示法
B ： 孩子兄弟表示法
C ： 孩子表示法
D ： 姐姐表示法
正确答案： A，B，C
解析：
树的存储结构没有姐姐表示法。
488 、 多选题
数据结构中()。
A ： 有四类基本结构
B ： 数据元素是孤立存在的C ： 数据结构是一个二元组
D ： 数据结构是相互之间存在一种或多种特定关系的数据元素的组合
正确答案： A，C，D
解析：
在数据结构中，数据元素之间是有关系的。
489 、 多选题
以下()属于设计一个“好”的算法应考虑达到的目标
A ： 效率与低存储量要求
B ： 可读性
C ： 健壮性
D ： 正确性
正确答案： A，B，C，D
解析：
好的算法应具有高效、低存储量、健壮性、可读性和正确性。
490 、 多选题
完全二叉树()。
A ： 某些节点有右子树则必有左子树
B ： 不一定适合顺序结构存储
C ： 叶子节点可在任一层出现
D ： 适合于顺序结构存储
正确答案： A，D
解析：
完全二叉树除了最下面一层，其余层的节点都是满的。
491 、 多选题
下列不属于数组的主要操作的是()。
A ： 检索(查找)
B ： 修改
C ： 插入
D ： 删除
E ： 存取正确答案： C，D
解析：
数组的主要操作时存取。
492 、 多选题
下列说法正确的是()。
A ： 在线性表中，数据元素之间仅有线性关系
B ： 在树形结构中，数据元素之间仅有线性关系
C ： 在图形结构中，节点之间的关系可以是任意的
D ： 在树形结构中，数据元素之间没有明显的层次关系
正确答案： A，C
解析：
线性表中的数据元素只有线性关系，在树形结构中，元素之间有层次关系。
493 、 多选题
下列存储形式中，()是树的存储形式。
A ： 双亲表示法
B ： 顺序表示法
C ： 广义表表示法
D ： 左子女右兄弟表示法
正确答案： A，B，D
解析：
树的存储形式有双亲表示法、左子女右兄弟表示法和顺序表示法。
494 、 多选题
有向图的连通包括()。
A ： 弱连通
B ： 多侧连通
C ： 强连通
D ： 单侧连通
正确答案： A，B，C
解析：
有向图的连通包括弱连通、强连通、多侧连通。495 、 多选题
下面的叙述不正确的是()。
A ： 线性表在顺序存储时，查找第i元素的时间同i值无关
B ： 线性表在链式存储时，查找第i个元素的时间同i值无关
C ： 线性表在链式存储时，查找第i个元素的时间同i值成正比
D ： 线性表在顺序存储时，查找第i个元素的时间同i值成正比
正确答案： B，D
解析：
在使用链式存储时，查找需要对链表进行遍历，所以和i的值有关。而使用顺序存储时，
则不需要遍历，和i的值无关。
496 、 多选题
下列说法错误的是()。
A ： 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈也
称为顺序栈
B ： top=0时为空栈，元素进栈时指针top不断地减1
C ： 栈不能对输入序列部分或全局起求逆作用
D ： 当top等于数组的最大下标值时则栈满
正确答案： B，C
解析：
top=0时代表栈空，则入栈时top应不断加1。
497 、 多选题
便于插入和删除操作的是()。
A ： 顺序表
B ： 单链表
C ： 静态链表
D ： 双链表
E ： 循环链表
正确答案： B，C，D，E
解析：
链式存储结构便于进行插入和删除操作。498 、 多选题
对一个算法的评价，包括如下()方面的内容。
A ： 正确性
B ： 并行性
C ： 可读性
D ： 空间复杂度
正确答案： A，C，D
解析：
对算法的评价包括正确性、可读性和空间复杂度和时间复杂度。
499 、 多选题
串是一种特殊的线性表，下列不能体现其特殊性的是()。
A ： 可以顺序存储
B ： 数据元素可以是多个字符
C ： 数据元素是一个字符
D ： 可以链式存储
正确答案： A，B，D
解析：
串即是一个字符数组，其中存储的元素都是字符。
500 、 多选题
图的四种存储结构()。
A ： 邻接矩阵
B ： 邻接表
C ： 十字链表
D ： 邻接多重表
正确答案： A，B，C，D
解析：
图的存储结构包括邻接矩阵、邻接表、邻接多重表和十字链表。
501 、 多选题
下列说法正确的有()。A ： 所谓数据的逻辑结构是指数据元素之间的逻辑关系
B ： 数据的逻辑结构与数据元素本身的内容和形式无关
C ： 算法和程序原则上没有区别，在讨论数据结构时二者通用
D ： 数据结构是指相互之间存在一种或多种关系的数据元素的全体
E ： 从逻辑关系上讲，数据结构分为线性结构和非线性结构两大类
F ： 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据
项的个数相等
正确答案： A，B，E
解析：
程序和算法不相同，算法指的是一种求解步骤。
502 、 多选题
计算机算法必须具备()等特性。
A ： 可行性、可移植性
B ： 易读性
C ： 可行性、确定性
D ： 有穷性
E ： 输入、输出
F ： 稳定性
正确答案： C，D，E
解析：
算法的特征包括确定性、可行性、有穷性、输入和输出。
503 、 多选题
图的应用算法有()。
A ： 拓扑排序算法
B ： 哈夫曼算法
C ： 迪杰斯特拉算法
D ： 克鲁斯卡尔算法
正确答案： A，C，D
解析：
图的应用算法包括遍历算法、最短路径和求解最小生成树。哈夫曼是最小生成树的算法。
504 、 多选题下面关于线性表的叙述正确的是()。
A ： 线性表采用链式存储便于插入和删除操作的实现
B ： 线性表采用顺序存储便于插入和删除操作的实现
C ： 线性表采用顺序存储必须占用一片连续的存储空间
D ： 线性表采用链式存储不必占用一片连续的存储空间
正确答案： A，C，D
解析：
顺序存储结构是随机存取，不便于进行随机的插入和删除操作。
505 、 多选题
树的表示方法有以下哪几种()。
A ： 直观表示法
B ： 广义表表示法
C ： 凹入表示法
D ： 嵌套集合表示法
正确答案： A，B，C，D
解析：
树的表示法包括直观表示法、凹入表示法、嵌套集合表示法、广义表表示法。
506 、 多选题
下列哪一条不是顺序存储结构的优点()。
A ： 存储密度大
B ： 插入运算方便
C ： 删除运算方便
D ： 可方便地用于各种逻辑结构的存储表示
正确答案： B，C，D
解析：
顺序存储不便于频繁地进行插入和删除操作。
507 、 多选题
如下陈述中错误的是()。
A ： 串的长度必须大于零
B ： 串是一种特殊的线性表C ： 串中元素只能是字母
D ： 空串就是空白串
正确答案： A，C，D
解析：
串的长度可以为0，此时是空串，空串和空白串是不同的。
508 、 多选题
依据所有数据成员之间的逻辑关系的不同，数据结构分为()。
A ： 非线性结构
B ： 逻辑结构
C ： 线性结构
D ： 物理结构
正确答案： A，C
解析：
根据数据结构的逻辑结构的不同，分为线性结构和非线性结构，其中非线性结构包括图、
树等。
509 、 多选题
从表中任一结点出发都能扫描整个表的是()。
A ： 单链表
B ： 静态链表
C ： 顺序表
D ： 循环链表
E ： 双链表
正确答案： D，E
解析：
单链表只能单向扫描表，当从中间某个结点出发时，不能扫描到整个表。
510 、 多选题
下列哪些是图的遍历()。
A ： 中根遍历
B ： 广度优先搜索
C ： 先根遍历
D ： 深度优先搜索正确答案： B，D
解析：
图的遍历算法有深度优先遍历算法和广度优先遍历算法两种。
511 、 多选题
线性表的顺序存储结构是一种()的存储结构。
A ： 散列存取
B ： 顺序存取
C ： 索引存取
D ： 随机存取
正确答案： B，D
解析：
线性表的顺序存储结构是一种顺序存储的存储结构，顺序存储结构又称为随机存取结构。
512 、 多选题
下列说法正确的是()。
A ： 队列被称为“先进后出”表
B ： 栈是一种操作不受限的线性表
C ： 当队列中无数据元素时，称为空队列
D ： 栈是一种只允许在一端进行插入和删除的线性表
正确答案： C，D
解析：
队列的特点是先进先出、后进后出，栈和队列都是一种操作受限的线性表。
513 、 多选题
算法设计的要求包括()。
A ： 健壮性
B ： 确定性
C ： 正确性
D ： 可读性
正确答案： A，C，D
解析：
“确定性”属于算法特性而非要求。514 、 多选题
()属于特殊矩阵。
A ： 对角矩阵
B ： 上三角矩阵
C ： 稀疏矩阵
D ： 下三角矩阵
E ： 对称矩阵
正确答案： A，B，D，E
解析：
稀疏矩阵不属于特殊矩阵。特殊矩阵指的是具有一定特点或规律的矩阵。
515 、 多选题
线性结构的特点是()。
A ： 除最后元素在外，均有唯一的后继
B ： 除第一元素之外，均有唯一的前驱
C ： 集合中必存在唯一的一个“第一元素”
D ： 集合中必存在唯一的一个“最后元素”
正确答案： A，B，C，D
解析：
在线性结构中必存在一个第一元素和最后元素，除第一个元素外，都有一个直接前驱，
除最后元素外，都有直接后继。
516 、 多选题
对广义表来说，下面哪些是正确的()。
A ： 广义表是一种多层次的结构
B ： 广义表是一种共享结构
C ： 广义表是一种非线性结构
D ： 广义表是一种单链表结构
E ： 广义表是一种递归表
正确答案： A，B，C，D，E
解析：
广义表是一种多层次的结构，并且是一种递归表。517 、 多选题
操作系统中动态存储管理方法包括()。
A ： 伙伴系统
B ： 边界标识法
C ： 朋友系统
D ： 中央标识法
正确答案： A，B
解析：
操作系统中常用来管理内存的动态分配和回收的方法有边界标识法和伙伴系统。
518 、 多选题
二叉树是有()基本单元构成。
A ： 右子树
B ： 叶子节点
C ： 左子树
D ： 根节点
正确答案： A，C，D
解析：
二叉树由左子树、右子树和根节点构成。
519 、 多选题
下列属于算法的重要特征的是()。
A ： 输入和输出
B ： 确定性
C ： 可行性
D ： 有穷性
正确答案： A，B，C，D
解析：
算法的特征包括确定性、可行性、有穷性、输入和输出。
520 、 多选题
以下哪些是线性表()。A ： 二叉树
B ： 栈
C ： 队列
D ： 集合
正确答案： B，C
解析：
二叉树、图、树和集合都是非线性结构，栈、队列、线性表都是线性结构。
521 、 多选题
以下说法正确的是()。
A ： 树的节点包含一个数据元素及若干指向其子树的分支
B ： 二叉树只能进行链式存储
C ： 二叉树的子树无左右之分
D ： 二叉树的特点是每个节点至多只有两棵子树
正确答案： A，D
解析：
二叉树可以使用顺序存储也可以使用链式存储，
522 、 多选题
在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数
据元素相互之间的关系称为结构。根据数据元素之间关系的不同特性，下面的选项
中，()属于其基本结构。
A ： 图状结构
B ： 线性结构
C ： 树形结构
D ： 集合
正确答案： A，B，C，D
解析：
数据结构的基本结构有集合、线性结构、图状结构和树形结构。
523 、 判断题
顺序表和一维数组一样，都可以按下标随机(或直接)访问。()
A ： 正确
B ： 错误正确答案： 对
解析：
顺序表和一维数组一样，都可以通过下标随机(或直接)访问。
524 、 判断题
数据结构中顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()
A ： 正确
B ： 错误
正确答案： 错
解析：
数据结构中顺序存储方式的优点是存储密度大，进行插入、删除操作时需要移动大量节
点，运算效率低。
525 、 判断题
中序遍历二叉排序树可以得到一个有序的序列。()
A ： 正确
B ： 错误
正确答案： 对
解析：
二叉排序树的左子树一定小于根节点，右子树一定大于根节点，中序遍历的顺序是首先
中序遍历左子树，然后访问根节点，最后中序遍历右子树，所以中序遍历二叉排序树可
以得到一个有序序列。
526 、 判断题
不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。()
A ： 正确
B ： 错误
正确答案： 对
解析：
无论是入队列还是入栈操作，都要考虑是否“溢出”。出队列或出栈操作都要考虑是否
栈空或队空。527 、 判断题
若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序
遍历序列中的最后一个结点。()
A ： 正确
B ： 错误
正确答案： 对
解析：
二叉树的中序遍历是左子树、根结点、右子树，先序遍历的顺序是根结点、左子树、右
子树，这两种遍历最后遍历的都是右子树，所以，中序遍历的最后一个结点必是先序遍
历的最后一个结点。
528 、 判断题
用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图
中的顶点个数有关，而与图的边数无关。()
A ： 正确
B ： 错误
正确答案： 对
解析：
用邻接矩阵存储一个图时，矩阵的大小与图的顶点个数有关，与边的条数无关。
529 、 判断题
给定一棵树，可以找到唯一的一颗二叉树与之对应。()
A ： 正确
B ： 错误
正确答案： 对
解析：
二叉树的做成是按照规则来的，按照规则，树的某一个节点作为另一个节点的父节点，
或者兄弟节点，或者子节点，这个都是按照逻辑来做成的。
530 、 判断题
线性表的顺序存储优于链式存储。()
A ： 正确
B ： 错误正确答案： 错
解析：
线性表的顺序存储和链式存储各有优缺点。顺序存储在查找上具有很大的方便，链式存
储在插入、删除上有很大的优势。
531 、 判断题
由树转化成二叉树，该二叉树根节点的右子树不一定为空。()
A ： 正确
B ： 错误
正确答案： 错
解析：
由树转化为二叉树，该二叉树根节点的右子树一定为空。
532 、 判断题
用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边
数有关。()
A ： 正确
B ： 错误
正确答案： 错
解析：
图的顶点数越多，邻接矩阵所占的存储空间越大。
533 、 判断题
如果有向图中各个顶点的度都大于2，则该图中必有回路。()
A ： 正确
B ： 错误
正确答案： 错
解析：
若有向图中各个顶点的度都大于2不一定代表有回路。
534 、 判断题
任何一棵二叉树的叶结点在三种遍历中的相对次序是不变的。()A ： 正确
B ： 错误
正确答案： 对
解析：
无论使用哪种遍历算法，都是先左子树后右子树，所以结点的相对位置是不变得。
535 、 判断题
数据结构的线性表中每个元素都有一个前驱与后继。()
A ： 正确
B ： 错误
正确答案： 错
解析：
在数据结构中线性表的第一个结点没有前驱，最后一个结点没有后继。
536 、 判断题
内部排序是指排序过程在内存中进行的排序。()
A ： 正确
B ： 错误
正确答案： 对
解析：
内部排序的排序过程在内存中实现，而外部排序指的是大文件的排序，即待排序的记录
存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进
行多次数据交换，以达到排序整个文件的目的。
537 、 判断题
栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
()
A ： 正确
B ： 错误
正确答案： 对
解析：
栈的特点是先进后出、后进先出。538 、 判断题
栈和队列是一种非线性数据结构。()
A ： 正确
B ： 错误
正确答案： 错
解析：
栈和队列都是线性数据结构，它们其实是特殊的线性表，对运算的定义略有不同而已。
539 、 判断题
当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整
到堆顶位置为止。()
A ： 正确
B ： 错误
正确答案： 对
解析：
小顶堆的根节点应为本树中值最小的元素，插入最小的元素，元素需逐层向上移动至根
节点。
540 、 判断题
循环队列也存在空间溢出问题。()
A ： 正确
B ： 错误
正确答案： 错
解析：
循环队列存储对于同一存储空间可以循环覆盖使用，所以不存在溢出现象。
541 、 判断题
在图G点最小生成树G1中，可能会有某条边的权值超过未选边的权值。()
A ： 正确
B ： 错误
正确答案： 对解析：
最小生成树其实是最小权重生成树的简称，只保证了所以权值之和最小，不好找每条路
径都有最小权重。
542 、 判断题
数据结构中，串长度是指串中不同字符的个数。()
A ： 正确
B ： 错误
正确答案： 错
解析：
串长度是指串中字符的个数。
543 、 判断题
数据结构中，深度为2的权值就是二叉树。()
A ： 正确
B ： 错误
正确答案： 错
解析：
二叉树是结点度数最多为2的树。
544 、 判断题
若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相
反。()
A ： 正确
B ： 错误
正确答案： 错
解析：
中根(序)遍历的遍历方式为若该二叉树不为空，则先中根遍历左子树，遍历根节点，中
跟遍历右子树。后根(序)遍历的遍历方式为若该二叉树不为空，则后根遍历左子树，后
根遍历右子树，遍历根节点。根据遍历方式可发现，若二叉树中任一结点都无右子树不
能使两种遍历的结果刚好相反。
545 、 判断题顺序表查找指的是在顺序存储结构上进行查找。()
A ： 正确
B ： 错误
正确答案： 对
解析：
顺序表是用顺序存储方式实现的线性表，因此顺序表查找一定是在顺序存储结构上进行
查找。
546 、 判断题
若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点.则它一定是
该子树的中序遍历结果序列的最后一个结点。()
A ： 正确
B ： 错误
正确答案： 错
解析：
反例：若最后一个叶子节点是左节点即可知道。
547 、 判断题
队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。()
A ： 正确
B ： 错误
正确答案： 错
解析：
队列是一种先进先出型结构。
548 、 判断题
栈和队列的存储方式既可以是顺序存储，也可以是链式存储。()
A ： 正确
B ： 错误
正确答案： 对
解析：
栈和队列的存储方式都有顺序存储和链式存储两种。549 、 判断题
当待排序序列初始有序时，简单选择排序的时间复杂性为O(n)。()
A ： 正确
B ： 错误
正确答案： 错
解析：
550 、 判断题
一个栈的输入序列是12345，则栈的输出序列不可能是12345。()
A ： 正确
B ： 错误
正确答案： 错
解析：
出栈序列有可能是12345。
551 、 判断题
对平衡二叉树进行中根遍历，可得到结点的有序排列。()
A ： 正确
B ： 错误
正确答案： 对
解析：
若想得到有序序列需进行先序遍历。
552 、 判断题
用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。()
A ： 正确
B ： 错误
正确答案： 错
解析：邻接矩阵只和点数有关。
553 、 判断题
在一个顺序存储的循环队列中，队头指针指向队头元素的后一个位置。()
A ： 正确
B ： 错误
正确答案： 错
解析：
队头指针应指向队头元素。
554 、 判断题
对稀疏矩阵进行压缩存储是为了节省存储空间。()
A ： 正确
B ： 错误
正确答案： 对
解析：
稀疏矩阵中非零元素的个数非常少，若全部存储会浪费大量的存储空间，将稀疏矩阵压
缩会减少使用存储空间。
555 、 判断题
数据结构中，在栈满情况下不能作进栈操作。()
A ： 正确
B ： 错误
正确答案： 对
解析：
在数据结构中，若栈满后再进行进栈操作，则会发生溢出。
556 、 判断题
分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。()
A ： 正确
B ： 错误
正确答案： 对解析：
分块查找先根据索引找到查找的块，然后在块内进行顺序查找，所以平均查找长度不仅
与索引表的长度有关，还与块的长度有关。
557 、 判断题
调用一次深度优先遍历可以访问到图中的所有顶点。()
A ： 正确
B ： 错误
正确答案： 错
解析：
调用一次深度优先遍历不一定能访问到图中的所有顶点。
558 、 判断题
线性表的逻辑顺序总是与其物理顺序一致。()
A ： 正确
B ： 错误
正确答案： 错
解析：
线性表包括顺序存储和链式存储两种形式。其中，顺序存储中逻辑上相邻的元素在物理
上也相邻；而在链式存储中，逻辑上相邻的元素在物理上不一定相邻。
559 、 判断题
图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问
过。()
A ： 正确
B ： 错误
正确答案： 对
解析：
深度优先遍历算法需设置一个数组，用来标志顶点是否被访问过。
560 、 判断题
在长度为n的顺序表中，求第i个元素的直接前驱，算法的时间复杂度为0(1)。()
A ： 正确B ： 错误
正确答案： 对
解析：
顺序存储的特点就是查找方便，所以在查找使用顺序存储方式的线性表时，不需要对整
个线性表进行遍历，通过下标就可访问相应节点，时间复杂度为0(1)。
561 、 判断题
线性表的唯一存储形式是链表。()
A ： 正确
B ： 错误
正确答案： 错
解析：
线性表既可以采用顺序存储形式，也可以采用链式。
562 、 判断题
链表中的头结点仅起到标识的作用。()
A ： 正确
B ： 错误
正确答案： 错
解析：
对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是
修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元
素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些，其作用不仅仅是
标识作用。
563 、 判断题
分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块
号，然后再在相应的块内进行顺序查找。()
A ： 正确
B ： 错误
正确答案： 对
解析：
分块查找的基本思想是先在索引表中进行查找，确定一个关键字可能存在的块号，然后再在相应的块内进行顺序查找。
564 、 判断题
由树转化成二叉树，该二叉树的右子树不一定为空。()
A ： 正确
B ： 错误
正确答案： 对
解析：
由树转化为二叉树，二叉树的右子树不一定为空。
