1. 【顺序表 】
含有n个元素的线性表用顺序存储方式时，对其运算速度最快的操作是【 】。
A. 访问第i个元素(1≤i≤n)
B. 删除第i个元素(1≤i≤n)
C. 在第i个元素(1≤i≤n)之后插入一个新元素
D. 查找与特定值相匹配的元素
【答案】A
【解析】线性表(a1,a2,…,an)采用顺序存储方式如下图所示，其逻辑上相邻的元素物理位置也是相邻的，因此，按照序号访问元素的速度是很快的。
访问第i个元素(1≤i≤n)的元素，仅需计算出a1的存储位置再进行内存的随机访问操作即可，以LOC(ai)表示线性表中第一个元素的存储位置，L表示每个元素所占存储单元的个数，则计算LOC(ai)的方式如下:
LOC(ai)=LOC(a1) (i-1)XL
再分析其他运算，不在表尾插入或删除时就需要移动其他元素，这是比较耗时的。查找与特定值相匹配的元素时，需要经过一个与表中多个元素进行比较的过程，相对于随机访问第i个元素，消耗更多时间。
2. 【链表 】
线性表采用单链表存储时的特点是【 】。
A. 插入、删除不需要移动元素
B. 可随机访问表中的任一元素
C. 必须事先估计存储空间需求量
D. 结点占用地址连续的存储空间
【答案】A
【解析】线性表采用单链表存储时，每个元素用一个结点表示，结点中的指针域指出后继元素所在结点，存取元素时只能从头指针出发顺序地查找元素，可根据需要动态申请和释放结点，也不要求结点的存储地址连续。在单链表上插入和删除元素只需要修改逻辑上相关的元素所在结点的指针域，而不需要移动元素。
3. 【栈、队列的概念 】
以下关于栈和队列的叙述中，错误的是【 】。
A. 栈和队列都是线性的数据结构
B. 栈和队列都不允许在非端口位置插入和删除元素
C. 一个序列经过一个初始为空的栈后，元素的排列次序一定不变
D. 一个序列经过一个初始为空的队列后，元素的排列次序不变
【答案】C
【解析】栈和队列是运算受限的线性表，栈的特点是后入先出，即只能在表尾插入和删除元素。队列的特点是先进先出，也就是只能在表尾插入元素，而在表头删除元素。因此，一个序列经过一个初始为空的队列后，元素的排列次序不变。在使用栈时，只要栈不空，就可以进行出栈操作，因此，一个序列经过一个初始为空的栈后，元素的排列次序可能发生变化。
4. 【栈的算法 】
对于一个初始为空的栈，其入栈序列为abc时，其出栈序列可以有【 】种。
A. 3
B. 4
C. 5
D. 6
【答案】C
【解析】入栈序列为abc时，出栈序列可以为abc、acb、bac、bca、cba，以I表示入栈、O对应出栈，原则是：每个元素仅入栈、出栈各1次；一次出栈操作的条件是栈不为空且只
能让栈顶元素出栈。
出栈序列为abc时，对应的操作序列为 IOIOIO。
出栈序列为acb时，对应的操作序列为 IOIIOO。
出栈序列为bac时，对应的操作序列为 IIOOIO。
出栈序列为bca时，对应的操作序列为IIOIOO。
出栈序列为cba时，对应的操作序列为IIIOOO。
在栈的合法操作序列中，其任何前缀部分中，出栈操作的次数都不多于入栈操作。
5. 【串的算法 】
正规式(ab|c)(0|1|2)表示的正规集合中有【 】个元素。
A. 3
B. 5
C. 6
D. 9
【答案】C
【解析】正规式(ab|c)表示的正规集为{ab，c}，正规式(0|1|2)表示的正规集为{0，1，2}，将{ab，c}与{0，1，2}进行连接运算后的正规集为{ab0，ab1，ab2，c0，c1，c2}，因此该正规集有6个元素。
6. 【串的算法 】
设有字符串S='software'，其长度为3的子串数目为【 】。
A. 8
B. 7
C. 6
D. 5
【答案】C
【解析】对于字符串S= 'software'，其长度为3的子串有“sof”“oft”“ftw”“twa”“war”“are”，共6个。
7. 【模式匹配 】
设有字符串S和P，串的模式匹配是指确定【 】。
A. P在S中首次出现的位置
B. S和P是否能连接起来
C. S和P能否互换
D. S和P是否相同
【答案】A
【解析】串的模式匹配是指模式串在主串中的定位运算，即模式串在主串中首次出现的位置。
8. 【数组的定义与实现 】
数组是程序语言提供的基本数据结构，对数组通常进行的两种基本操作是数组元素的【 】。
A. 插入和删除
B. 读取和修改
C. 插入和检索
D. 修改和删除
【答案】B
【解析】由于数组一旦被定义，就不再有元素的增减变化，因此对数组通常进行的两种基本操作为读取和修改，也就是给定一组下标，读取或修改其对应的数据元素值。
9. 【特殊矩阵 】
特殊矩阵是非零元素有规律分布的矩阵，以下关于特殊矩阵的叙述中，正确的是【 】。
A. 特殊矩阵适合采用双向链表进行压缩存储
B. 特殊矩阵适合采用单向循环链表进行压缩存储
C. 特殊矩阵的所有非零元素可以压缩存储在一维数组中
D. 特殊矩阵的所有零元素可以压缩存储在一维数组中
【答案】C
【解析】对于矩阵，压缩存储的含义是为多个值相同的元素只分配一个存储单元，对零元素不分配存储单元。如果矩阵的零元素有规律地分布，则可将其非零元素压缩存储在一维数组中，并建立起每个非零元素在矩阵中的位置与其在一维数组中的位置之间的对应关系。
10. 【二叉树 】
在数据结构中，【 】是与存储结构无关的术语。
A. 单链表
B. 二叉树
C. 哈希表
D. 循环队列
【答案】B
【解析】单链表是与存储结构有关的术语，常用于线性表的链式存储，通过在结点中设置指针域指出当前元素的直接后继(或直接前驱)元素所在结点，从而表示出元素间的顺序关系(即逻辑关系)。
哈希表既是一种存储结构也是一种查找结构，它以记录的关键字为自变量计算一个函数(称为哈希函数)得到该记录的存储地址，从而实现快速存储和查找。
循环队列是指采用顺序存储结构实现的队列。在顺序队列中，为了降低运算的复杂度，元素入队时，只修改队尾指针;元素出队时，只修改队头指针。由于顺序队列的存储空间是提前设定的，因此队尾指针会有一个上限值，当队尾指针达到其上限时，就不能只通过修改队尾指针来实现新元素的入队操作了。此时，可将顺序队列假想成一个环状结构，称之为循环队列，并仍然保持队列操作的简便性。
11. 【二叉树 】
已知某二叉树的先序遍历序列为ABCD，后序遍历序列为CDBA，则该二叉树为【 】。
A.
B.
C.
D.
【答案】A
【解析】对非空的二叉树进行先序遍历的过程是:先访问根结点，然后先序遍历左子树，最后先序遍历右子树。题中四个二又树的先序遍历序列分别为ABCD、ABCD、ABCD、ACBD。
对非空的二叉树进行后序遍历的过程是:先后序遍历左子树，接着后序遍历右子树，最后再访问根结点。题中四个二叉树的后序遍历序列分别为CDBA、BDCA、DCBA、DBCA。
12. 【完全二叉树 】
完全二叉树的特点是叶子结点分布在最后两层，且除最后一层之外，其他层的结点数都达到最大值，那么25个结点的完全二叉树的高度(即层数)为【 】。
A. 3
B. 4
C. 5
D. 6
【答案】C
【解析】若深度为k的二叉树有2k-1个结点，则称其为满二叉树。满二叉树中每层上的结点数达到最大值。可以对满二叉树中的结点进行连续编号，约定编号从根结点起，自上而下、自左至右依次进行。深度为k、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二又树中编号为1~n的结点一一对应时，称之为完全二叉树。高度为3满二叉树如下图(a)所示，具有6个结点的完全二叉树如下图(b)所示，下图(c)则不是完全二叉树。
从上图中可知，在完全二叉树中，除最后一层结点数不满以外，其余层的结点数都达到最大值。若完全二叉树有25个结点，则其前4层结点数为15(1 2 48)，第5层上就有10个结点(即25-10)，尚未超过该层最多16个结点的上限，因此该二叉树的高度为5。
13. 【图的存储 】
已知某带权图G的邻接表如下所示，其中表结点的结构为:
以下关于该图的叙述中，正确的是【 】。
A. 图G是强连通图
B. 图G具有14条弧
C. 顶点B的出度为3
D. 顶点B的入度为3
【答案】D
【解析】从题图中可知，顶点A、B、C、D、E的编号为1~5，因此顶点A的邻接表中的两个结点表示:存在顶点A至顶点B的弧且权值为5，存在顶点A至顶点D的弧且权值为8，再考查顶点B只有一个邻接顶点E，因此该图为有向图，有7条弧，如下图所示。
若在有向图中，每对顶点之间都存在路径，则是强连通图。上图不是强连通图，例如，顶点C至B有路径，反之则没有路径。在有向图中，顶点的入度是以该顶点为终点的有向边的数目，而顶点的出度指以该顶点为起点的有向边的数目。对于顶点B，其出度为1，而入度为3。
14. 【图的存储 】
对于下图，若采用邻接矩阵存储，则矩阵中的非0元素数目为【 】。
A. 7
B. 8
C. 14
D. 16
【答案】B
【解析】对于有向图，其邻接矩阵中非零元素的个数即表示图中有向弧的数目，题中的图有8条弧，因此矩阵中的非0元素数目为8。如下图所示：
15. 【图的遍历 】
对于下图，从顶点1进行深度优先遍历时，不可能得到的遍历序列是【 】
A. 1234567
B. 1523467
C. 1234675
D. 1267435
【答案】A
【解析】对题中所示的图从顶点1出发进行深度优先遍历，访问1之后接下来既可以访问顶点2，也可以访问顶点5。
若先访问顶点2，则接下来可以访问顶点3或6，此时得到的已访问顶点顺序是123或26。若选择先访问顶点3，则接下来就访问顶点4，便得到已访问的顶点顺序1234，由于从顶点4出发不存在继续前进的路径，所以需要先回溯至顶点3再回溯至顶点2。由于顶点2存在尚没有得到访问的邻接顶点6，所以接下来访间的顶点是6，然后是顶点7，从而得到已访问顶点的遍历序列123467。最后还需回溯至顶点1，再去访问顶点5，这样就完成了所有顶点的访问，从而得到深度优先遍历序列1234675。若访问完顶点2后接下来选择访问顶点6，则可得到遍历序列1263475或1267435。
若访问顶点1之后接下来选择访问顶点5，则可得到深度优先遍历序列1523467或1526347或1526734。
因此，不能得到的深度优先遍历序列是1234567。
16. 【有序表查找 】
在有13个元素构成的有序表data[1..13]中，用折半查找(即二分查找，计算时向下取整)方式查找值等于data[8]的元素时，先后与【 】等元素进行了比较。
A. data[7]、data[6]、data[8]
B. data[7]、data[8]
C. data[7]、data[10]、data[8]
D. data[7] data[10] data[9] data[8]
【答案】C
【解析】在二分查找(即折半查找)过程中，令处于中间位置记录的关键字和给定值比较，若相等，则查找成功;若不等，则缩小范围，直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时(表明查找不成功)为止。
在有13个元素构成的有序表data1.13]中进行二分查找的过程如下图所示(计算中间元素位置时向下取整，结点中的数字为元素的下标或序号)，从中可以看出，查找元素data[8]时，需与data[7]、data[10]、data[8]等元素比较。
17. 【二叉排序树 】
某二叉排序树如下所示，新的元素45应作为【 】插入该二叉树中。
A. 11的左子树
B. 17的右子树
C. 61的左子树
D. 27的右子树
【答案】C
【解析】根据二叉排序树的定义，当新来的元素大于根结点的关键码时，应将其插入根结点的右子树中，当新来的元素小于根结点的关键码时，应将其插入根结点的左子树中，在子树上同样如此。由于45大于23，因此将其插入结点31的右子树中，又由于45大于31、小于91、小于61，因此最后将其作为61的左子树加入该二叉树中。
,
