第一题、单项选择题（每题1分，5道题共5分）

1、设n为正整数。确定下面程序段的时间复杂度：

k＝0;

for(i＝1;i＜＝n;i++){

for(j＝i;j＜＝n;j++)

@ k++;

}

A、n B、logn

C、nlogn D、n^2

2、设n为正整数。确定下面程序段的时间复杂度：

i＝1; k＝0;

while(i＜＝n-1){

k+＝10*i;

i++;

}

A、1 B、n

C、nlogn D、n^2

3、在线性结构中，除第一个以外的其余结点有＿＿＿＿＿＿＿＿个前驱结点。

A、0 B、1

C、任意多 D、

4、树型结构和图结构都属于＿＿＿＿＿＿＿＿。

A、线性结构 B、非线性结构

C、动态结构 D、静态结构

5、n为正整数，下列程序段的时间复杂度是＿＿＿＿＿＿＿＿。

for(i＝1,x＝0; i＜＝n; i++,x++);

A、O(1) B、O(n)

C、O(n^2) D、

第二题、多项选择题（每题2分，5道题共10分）

1、计算机算法必须具备输入、输出和＿＿＿＿＿＿＿＿等特性。

A、确定性 B、稳定性

C、可行性 D、有穷性 E、易读性 F、可扩充性

2、根据元素之间关系的不同特性，通常可有下列基本结构＿＿＿＿＿＿＿＿。

A、集合 B、线性结构

C、树结构 D、图结构

3、一个"好"的算法应达到的目标有＿＿＿＿＿＿＿＿。

A、正确性 B、健壮性

C、高时间效率 D、可读性 E、低存储率 F、输入G、输出

4、影响程序运行时间的因素包括＿＿＿＿＿＿＿＿＿＿＿＿＿＿。

A、书写程序的语言 B、问题的规模

C、编译器产生的机器代码的质量 D、计算机的运行速度 E、算法的策略 F、输出数据量

5、算法分析的主要方面是＿＿＿＿＿＿＿＿。

A、时间复杂度 B、空间复杂度

C、数据复杂性 D、程序复杂性

第三题、判断题（每题1分，5道题共5分）

1、数据元素是数据的不可分割的最小单位。

正确 错误

2、数据的物理结构是指数据和关系在计算机内的实际存储形式。

正确 错误

3、在数据结构中，从逻辑上可以把数据结构分为动态结构和静态结构两大类。

正确 错误

4、数据元素可以由很多数据项组成。

正确 错误

5、计算机算法必须具备的特性有： 输入、输出、易读性、稳定性和安全性。

正确 错误

第一题、单项选择题（每题1分，5道题共5分）

1、线性表的顺序存储结构是一种＿＿＿＿＿＿＿＿的存储结构。

A、顺序存取 B、随机存取

C、索引存取 D、散列存取

2、若在线性表的任何位置上插入元素的概率是相等的，那么在长度为n的顺序表中插入一个元素时需平均移动＿＿＿＿＿＿＿＿个元素。

A、n B、(n-1)/2

C、n/2 D、(n+1)/2

3、若L是SqList类型的顺序表，则线性表中的第i个元素是＿＿＿＿＿＿＿。

A、L.elem[i] B、L.elem[i-1]

C、L.elem[i+1] D、L.elem[i+2]

4、有头结点的单链表（head为头指针）是空表的条件是＿＿＿＿＿＿＿

A、head-＞next＝＝NULL; B、head＝＝NULL;

C、head-＞next＝＝head; D、head-＞next-＞next＝＝ NULL;

5、若在线性表的任何位置上删除元素的概率是相等的，那么在长度为n的顺序表中删除一个元素时需平均移动＿＿＿＿＿＿＿＿个元素。

A、n B、(n-1)/2

C、n/2 D、(n+1)/2

第二题、多项选择题（每题2分，5道题共10分）

1、单链表是用一组任意的存储单元来存储线性表的元素，这些存储单元之间＿＿＿＿＿＿＿＿

A、可以是连续的 B、可以是不连续的

C、必须是连续的 D、必须是不连续的

2、单链表的特点是＿＿＿＿＿＿＿＿。

A、随机存取 B、顺序存取

C、元素间的逻辑关系由指针指示 D、插入删除元素时需要移动表中元素 E、插入删除元素时不必移动元素，只须修改指针 F、数据元素在存储器内的物理位置顺序与它们的逻辑顺序不一定相同

3、顺序表的特点是＿＿＿＿＿＿＿＿。

A、随机存取 B、顺序存取

C、元素间的逻辑关系由指针指示 D、插入删除元素时需要移动表中元素 E、插入删除元素时不必移动元素，只须修改指针 F、数据元素在存储器内的物理位置顺序与它们的逻辑顺序一定相同G、元素间的逻辑关系隐含在存储位置中

4、下列链表中，能从当前结点出发访问到表中其余各结点的有＿＿＿＿＿＿＿＿。

A、带头结点的单链表 B、不带头结点的单链表

C、带头结点的循环链表 D、不带头结点的循环链表 E、双向链表

5、在双向链表中，每个结点有两个指针域，分别指向＿＿＿＿＿＿＿＿。

A、其自身 B、其直接前驱结点

C、其直接后继结点 D、头结点

第三题、判断题（每题1分，5道题共5分）

1、在单链表中插入或删除元素时是以结点的指针变化来反映逻辑关系的变化，因此不需要移动元素。

正确 错误

2、线性表的顺序存储结构优于链式存储结构。 （ ）

正确 错误

3、顺序表中第一个元素的起始存储地址为200，每个元素的长度为6，则第10个元素的起始地址是260。

正确 错误

4、顺序表中插入或删除元素时是以元素的移动来反映逻辑关系的变化的。

正确 错误

5、在双向循环链表中插入或删除元素时仅需要修改结点的指针，不需要移动元素，因此算法的时间复杂度为O(1)。

正确 错误

第一题、单项选择题（每题1分，5道题共5分）

1、栈和队列的共同点是＿＿＿＿＿＿＿＿。

A、都是后进先出 B、都是先进先出

C、都是只允许在端点处插入和删除元素 D、无共同点

2、在顺序栈中，base、top分别为栈底、栈顶指针，则＿＿＿＿＿＿＿时表明栈空。

A、base＝＝NULL B、top＝＝ NULL

C、base＝＝top D、

3、已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1,p2,p3,…pn,若p1＝n,则pi为＿＿＿＿＿＿＿＿。

A、i B、n-i

C、n-i+1 D、不确定

4、栈是限定在＿＿＿＿＿＿＿＿进行插入或删除的线性表。

A、栈底 B、栈顶

C、任意位置 D、

5、在循环队列中，设队列元素依次存放在Q[0..m]中，f、r分别指示队头元素位置和队尾元素的下一个位置，Q中存放m个元素时认为队列满，则队列满的判定方法是 ＿＿＿＿＿＿＿。

A、f==r B、(f+1) ％ (m+1)＝＝r

C、(r+1) ％ (m+1)＝＝f D、(r+1) ％ m＝＝f

第二题、多项选择题（每题2分，5道题共10分）

1、一个栈的入栈序列是{1,2,3,4,5},则栈可能的输出序列是＿＿＿＿＿＿＿。

A、{1,2,3,4,5} B、{5,4,3,2,1}

C、{2,1,4,3,5} D、{4,2,3,1,5} E、{5,1,4,3,2} F、{3,4,2,1,5}

2、循环队列中，设队列元素依次存放在Q[0..m]中，f、r分别指示队头元素位置和队尾元素的下一个位置，此时队空、队满的判断条件都是f＝＝r,为解决此矛盾，通常可采用＿＿＿＿＿＿＿。

A、附设标志位，f＝＝r时借助标志判断 B、牺牲一个元素空间，(r+1）％ m＝＝f时队满，f＝＝r时队空

C、牺牲一个元素空间，(r+1）％ (m+1)＝＝f时队满，f＝＝r时队空 D、另设表示队列长度的length域来区别队列空、满

3、队列操作的原则是＿＿＿＿＿＿＿。

A、先进先出 B、后进先出

C、可以进行插入 D、可以进行删除

4、一个队列的入队序列是{1,2,3,4},则队列不可能的输出序列是＿＿＿＿＿＿＿。

A、4321 B、1234

C、1432 D、3241

5、非空链栈（ls为栈顶指针）的出栈操作可表示为:

p＝ls; ＿＿＿＿＿＿＿; free(p);

A、ls＝ls-＞next B、ls=p

C、ls＝p-＞next D、p＝ ls-＞next

第三题、判断题（每题1分，5道题共5分）

1、若用户无法估计所用队列的最大长度，则最好采用循环队列

正确 错误

2、一个队列的入队序列是{1,2,3,4},则队列的输出序列只能是{1,2,3,4}。

正确 错误

3、循环队列也可以用动态分配的一维数组来实现。

正确 错误

4、一个栈的入栈序列是{1,2,3,4,5},则{1,2,3,4,5}是不可能的输出序列。

正确 错误

5、栈的一个重要应用是在程序设计语言中实现递归。

正确 错误

第一题、单项选择题（每题1分，5道题共5分）

1、若串S＝"abcdef"，则其非空子串数目为＿＿＿＿＿＿＿＿。

A、6 B、12

C、21 D、22

2、设串s＝"data structure",则其串长为＿＿＿＿＿＿＿＿。

A、12 B、13

C、14 D、15

3、字符串是一种特殊的线性表，其特殊性在于它的数据元素只能是＿＿＿＿＿＿＿＿。

A、字符 B、字符串

C、数字 D、字母

4、串是＿＿＿＿＿＿＿＿。

A、不少于一个字母的序列 B、任意个字母的序列

C、不少于一个字符的序列 D、有限个字符的序列

5、设串s＝"I am a student.",则s的长度为＿＿＿＿＿＿＿＿。

A、11 B、12

C、15 D、16

第二题、多项选择题（每题2分，5道题共10分）

1、构成串类型最小操作子集的操作有串赋值、求串长、串连接及＿＿＿＿＿＿＿＿＿＿。

A、串复制 B、串比较

C、求子串 D、插入串 E、删除子串

2、串的机内表示方法有＿＿＿＿＿＿＿＿＿＿。

A、定长顺序存储表示 B、堆分配存储表示

C、块链存储表示 D、散列表示

3、串用定长顺序存储方式表示时，有可能发生“截断”的操作有＿＿＿＿＿＿＿＿＿＿。

A、串连接 B、求子串

C、串替换 D、插入串 E、删除子串

4、以下关于串长的说法正确的是＿＿＿＿＿＿＿＿＿＿。

A、串长相等的两个串相等 B、括串值的引号不被计算在串长之内

C、空串的长度为0 D、空格串的长度为0

5、以下关于块链结构的说法正确的是＿＿＿＿＿＿＿＿＿＿。

A、结点大小小，则存储密度小 B、结点大小小，则存储密度大

C、结点大小小，则占用存储空间多 D、结点大小小，则占用存储空间少

第三题、判断题（每题1分，5道题共5分）

1、空串和空格串是一样的。

正确 错误

2、如果两个串含有相同的字符，则它们相等。

正确 错误

3、串也有两种存储结构：顺序结构和链式结构。

正确 错误

4、使用定长顺序结构表示串时，超出预定义长度的串值被“截断”。

正确 错误

5、串是n个字母的有限序列（n≥0）。

正确 错误

第一题、单项选择题（每题1分，5道题共5分）

1、设m，n是一棵二叉树上的两个结点，中序遍历时，n在m之前的条件是＿＿＿＿＿＿＿＿。

A、n在m右方 B、n是m祖先

C、n在m左方 D、n是m子孙

2、在线索化二叉树中，t所指结点没有左子树的充要条件是＿＿＿＿＿＿＿＿。

A、t-＞lchild＝＝NULL B、t-＞LTag＝＝1

C、t-＞LTag＝＝1 && t-＞lchild＝＝NULL D、以上都不对

3、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为＿＿＿＿＿＿＿＿。

A、2h-1 B、2h

C、2h+1 D、h+1

4、具有100个结点的完全二叉树的深度为＿＿＿＿＿＿＿＿。

A、6 B、7

C、8 D、9

5、对于表达式(a-b+c)*d/(e+f),其前缀表达式为＿＿＿＿＿＿＿＿。

A、/*+-abcd+ef B、a-b+c*d/e+f

C、/*-a+bcd+ef D、ab-c+d*ef+/

第二题、多项选择题（每题2分，5道题共10分）

1、下列关于树和二叉树的叙述中，正确的有＿＿＿＿＿＿＿＿。

A、森林和二叉树之间可以相互转换 B、树和二叉树之间可以相互转换

C、二叉树的子树有左右之分，而树的子树没有左右之分 D、二叉树结点的最大度数为2，而树的结点的最大度数没有限制

2、先序序列和中序序列相同的二叉树有＿＿＿＿＿＿＿＿。

A、空二叉树 B、左单支树

C、右单支树 D、根树

3、树型结构的特点是：任意一个结点＿＿＿＿＿＿＿＿。

A、可以有多个前驱 B、可以有多个后继

C、只有一个前驱 D、只有一个后继

4、用二叉树的＿＿＿＿＿＿＿＿序列可唯一的确定一棵二叉树。

A、先序和中序 B、先序和后序

C、后序和中序 D、层序和中序

5、树可采用的存储结构有＿＿＿＿＿＿＿＿。

A、顺序结构 B、多重链表

C、二叉链表 D、孩子链表

第三题、判断题（每题1分，5道题共5分）

1、二叉树按某种顺序线索化后，任意结点均有指向其前驱和后继的线索。

正确 错误

2、二叉树的先、中、后序遍历序列中，叶子结点的相对顺序不会发生改变。

正确 错误

3、若一棵二叉树的任意非叶子结点的度均为2，则该二叉树是满二叉树。

正确 错误

4、用树的先序遍历和中序遍历序列可以导出树的后序遍历。

正确 错误

5、在一棵非空二叉树的中序遍历序列中，根结点的右边只有其右子树上的所有结点。

正确 错误

第一题、单项选择题（每题1分，5道题共5分）

1、4个顶点的无向完全图有＿＿＿＿＿＿＿＿条边。

A、6 B、12

C、16 D、20

2、图的广度优先遍历算法类似于二叉树的＿＿＿＿＿＿＿＿。

A、先序遍历 B、中序遍历

C、后序遍历 D、层序遍历

3、一个无向连通图的生成树是含有该连通图所有顶点的＿＿＿＿＿＿＿＿。

A、极大连通子图 B、极大子图

C、极小连通子图 D、极小子图

4、图的深度优先遍历算法类似于二叉树的＿＿＿＿＿＿＿＿。

A、先序遍历 B、中序遍历

C、后序遍历 D、层序遍历

5、对＿＿＿＿＿＿＿＿，用Prim算法求最小生成树较为合适。

A、非连通图 B、连通图

C、稀疏图 D、稠密图

第二题、多项选择题（每题2分，5道题共10分）

1、下列说法中正确的是＿＿＿＿＿＿＿＿。

A、无向图中的极大连通子图称为连通分量。 B、图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。

C、图的深度优先搜索中一般要采用队列来暂存刚访问过的顶点。 D、有向图的遍历不能采用广度优先搜索方法。

2、已知一个无向图的邻接矩阵表示，计算第i个顶点的度的方法是＿＿＿＿＿＿。

A、计算邻接矩阵中第i行的元素之和 B、计算邻接矩阵中第i列的元素之和

C、计算邻接矩阵中第i行的非零元个数 D、计算邻接矩阵中第i列的非零元个数

3、对图分别进行深度优先遍历和广度优先遍历，得到的顶点访问序列＿＿＿＿＿＿＿＿。

A、一定相同 B、一定不同

C、不一定相同 D、可能相同

4、下列关于最短路径的说法中，正确的有＿＿＿＿＿＿＿＿。

A、Dijkstra算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。 B、若仅求单一源点到某一特定顶点之间的最短路径，则其算法的时间复杂度可以达到O(n)。

C、求图中每一对顶点间最短路径的Floyd算法的时间复杂度为O(n^3)。 D、求图中每一对顶点间的最短路径也可用Dijkstra算法实现。

5、已知一个无向图的邻接矩阵表示，计算第i个顶点的度的方法是＿＿＿＿＿＿。

A、计算邻接矩阵中第i行的元素之和 B、计算邻接矩阵中第i列的元素之和

C、计算邻接矩阵中第i行的非零元个数 D、计算邻接矩阵中第i列的非零元个数

第三题、判断题（每题1分，5道题共5分）

1、任何有向图的顶点都可以排成拓扑有序序列，而且拓扑序列不唯一。

正确 错误

2、对稀疏图，用Prim算法求最小生成树较为合适

正确 错误

3、利用拓扑排序，可检测一个有向图中是否存在环

正确 错误

4、在对有向无环图执行拓扑排序算法之后，入度数组中所有元素的值均为0。

正确 错误

5、若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点，则

该图一定是连通图。

正确 错误

第一题、单项选择题（每题1分，5道题共5分）

1、用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义词表的＿＿＿＿＿＿＿相同。

A、关键字 B、元素值

C、散列地址 D、含义

2、用线性探测法解决冲突问题时，所产生的一系列后继散列地址＿＿＿＿＿＿＿。

A、可以大于或小于但不能等于原散列地址 B、必须大于或等于原散列地址

C、必须小于或等于原散列地址 D、无具体限制

3、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用＿＿＿＿＿＿＿查找方法。

A、折半 B、顺序

C、分块 D、散列

4、有一个有序表{1，3，9，12，32，41，45，62，75，77，82，95，100}中折半查找值为82的结点时，＿＿＿＿＿＿＿次比较后查找成功。

A、1 B、2

C、4 D、8

5、哈希函数有一个性质：函数值应按＿＿＿＿＿＿＿取其值域的每一个值。

A、最小概率 B、最大概率

C、平均概率 D、同等概率

第二题、多项选择题（每题2分，5道题共10分）

1、平衡二叉树上结点的平衡因子可以为＿＿＿＿＿＿＿。

A、-2 B、-1

C、0 D、1 E、2

2、构造散列函数时通常考虑的因素有＿＿＿＿＿＿＿。

A、计算函数的工作量 B、关键字的长度

C、散列表长 D、关键字的分布情况

3、对于10个元素的有序表进行折半查找，须比较3次方可查找成功的元素在表中的位置有＿＿＿＿＿＿＿。

A、1 B、2

C、3 D、4 E、6 F、7G、8H、9

4、对序列{50，72，43，85，75，20，35，45，30}按顺序建二叉排序树，则在树中须比较3次方可查找成功的元素有＿＿＿＿＿＿＿。

A、50 B、43

C、85 D、75 E、20 F、35G、45H、30

5、在下列各种查找方法中，平均查找长度与表长有关的查找方法是＿＿＿＿＿＿＿。

A、散列表查找 B、顺序查找

C、折半查找 D、排序树查找

第三题、判断题（每题1分，5道题共5分）

1、散列表的装填因子越小，发生冲突的可能性越大。

正确 错误

2、在散列函数H(key)＝key mod p中，函数的好坏与p的选择没有任何关系。

正确 错误

3、给出不同的输入序列构造二叉排序树，一定得到不同的二叉排序树。

正确 错误

4、就平均查找长度而言，折半查找最小，分块查找次之，顺序查找最大。

正确 错误

5、在分块查找中，对索引表的查找既可用顺序查找法，也可用折半查找法。

正确 错误

第一题、单项选择题（每题1分，5道题共5分）

1、下列方法中，＿＿＿＿＿＿＿＿算法的时间复杂度为O(n^2)。

A、直接插入排序 B、希尔排序

C、快速排序 D、堆排序

2、下列方法中，＿＿＿＿＿＿＿＿是稳定的排序方法。

A、折半插入排序 B、希尔排序

C、快速排序 D、堆排序

3、在待排序的元素序列基本有序的前提下，效率最高的排序方法是＿＿＿＿＿＿＿。

A、直接插入排序 B、起泡排序

C、快速排序 D、堆排序

4、排序方法中，从未排序序列中挑选元素，将其依次放至已排序序列（初始为空）的一端的方法，称为＿＿＿＿＿＿＿。

A、插入排序 B、交换排序

C、选择排序 D、归并排序

5、在下列排序方法中，在待排序的数据有序时, 花费时间反而最多的是＿＿＿＿＿＿＿。

A、堆排序 B、起泡排序

C、快速排序 D、插入排序

第二题、多项选择题（每题2分，5道题共10分）

1、下列方法中，＿＿＿＿＿＿＿＿算法的时间复杂度为O(n^2)。

A、希尔排序 B、冒泡排序

C、快速排序 D、直接插入排序

2、下列方法中，＿＿＿＿＿＿＿＿算法的时间复杂度为O(nlogn)。

A、希尔排序 B、堆排序

C、快速排序 D、简单选择排序 E、直接插入排序

3、下列序列中，＿＿＿＿＿＿＿＿是堆。

A、{15,30,22,93,52,71} B、{15,22,30,52,71,93}

C、{15,52,22,93,30,71} D、{15,52,22,71,30,93}

4、下列排序方法中，在最坏情况下算法的时间复杂度为O(n^2)的有＿＿＿＿＿＿＿＿。

A、堆排序 B、快速排序

C、希尔排序 D、冒泡排序

5、下列序列中，＿＿＿＿＿＿＿＿不是堆。

A、{96,83,27,38,11,9} B、{12,36,24,85,47,30,53,91}

C、{49,38,65,97,76,13,27} D、{38，24，15，20，30，46}

第三题、判断题（每题1分，5道题共5分）

1、对一个堆按层次遍历，一定能得到一个有序序列。

正确 错误

2、由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多。

正确 错误

3、在初始数据表为逆序时，冒泡排序所执行的比较次数最多。

正确 错误

4、快速排序算法在每趟排序结束时都能找到一个元素放到其最终位置上。

正确 错误

5、在堆排序过程中，在输出一个根之后的调整过程中，“临时根”结点的值将会最终被放到“叶子结点”上。

正确 错误

。

专业承接点播、测试、网考、作业、论文等辅导，请加周老师QQ:805006590 (长期有效)