第1题
下面说法错误的是
（1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
(1)
(1),(2)
(1),(4)
(3)
第2题
以下与数据的存储结构无关的术语是
循环队列
链表
哈希表
栈
第3题
从逻辑上可以把数据结构分为（ ）两大类。
动态结构、静态结构
顺序结构、链式结构
线性结构、非线性结构
初等结构、构造型结构
第4题
以下数据结构中，哪一个是线性结构？
广义表
二叉树
稀疏矩阵
串
第5题
在下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;
O(2n)
O(n)
O(n2)
O(log2n)
第6题
下述哪一条是顺序存储结构的优点？
存储密度大
插入运算方便
删除运算方便
可方便地用于各种逻辑结构的存储表示
第7题
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
顺序表
双链表
带头结点的双循环链表
单循环链表
第8题
设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ ）最节省时间。
单链表
带尾指针的单循环链表
第9题
对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为
O(n) O(n)
O(n) O(1)
O(1) O(n)
O(1) O(1)
第10题
线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂度为
O（i）
O（1）
O（n）
O（i-1）
第11题
完成在双循环链表结点p之后插入s的操作是
p->next=s; s->prior=p; p->next->prior=s ; s->next=p->next;
p->next->prior=s; p->next=s; s->prior=p; s->next=p->next;
s->prior=p; s->next=p->next; p->next=s; p->next->prior=s ;
s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
第12题
设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是
XYZ
YZX
ZXY
ZYX
第13题
一个递归算法必须包括
递归部分
终止条件和递归部分
迭代部分
终止条件和迭代部分
第14题
循环队列存储在数组A[0...m]中，则入队时的操作为
rear=rear+1
rear=(rear+1) mod (m-1)
rear=(rear+1) mod m
rear=(rear+1) mod (m+1)
第15题
下面关于串的的叙述中，哪一个是不正确的？
串是字符的有限序列
空串是由空格构成的串
模式匹配是串的一种重要运算
串既可以采用顺序存储，也可以采用链式存储
第16题
A[N，N]是对称矩阵，将下三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是
i（i-1）/2+j
j（j-1）/2+i
i（j-i）/2+1
j（i-1）/2+1
第17题
对稀疏矩阵进行压缩存储目的是
便于进行矩阵运算
便于输入和输出
节省存储空间
降低运算的时间复杂度
第18题
广义表L=（a，（b，c）），进行Tail（L）操作后的结果为
c
b,c
（b，c）
（（b，c））
第19题
在下述结论中，正确的是
只有一个结点的二叉树的度为0
二叉树的度为2
二叉树的左右子树可任意交换
深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树
第20题
二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是
E
F
G
H
第21题
有n个叶子的哈夫曼树的结点总数为
不确定
2n
2n+1
2n-1
第22题
利用二叉链表存储树，则根结点的右指针是
指向最左孩子
指向最右孩子
空
非空
第23题
设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是
m-n
m-n-1
n+1
条件不足，无法确定
第24题
二叉树的第I层上最多含有结点数为
2^I
2^(I-1)-1
2^(I-1)
2^I -1
第25题
深度为K(K>1)的完全二叉树至少有（ ）个叶子结点
2^(K-2)
2^(K-1)
2^K
第26题
若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是
30
45
58
69
第27题
在完全二叉树中，若一个结点是叶结点，则它没
左子结点
右子结点
左子结点和右子结点
左子结点，右子结点和兄弟结点
第28题
用二叉链表存储包含n个结点的二叉树时，结点的2n个指针区域中有（ ）个空指针。
n
n-1
第29题
一个n个顶点的连通无向图，其边的个数至少为
nlogn
第30题
在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍
1/2
2
1
4
第31题
下列哪一种图的邻接矩阵是对称矩阵？
有向图
无向图
OV网
OE网
第32题
下列说法不正确的是
图的遍历是从给定的源点出发每一个顶点仅被访问一次
遍历的基本算法有两种：深度遍历和广度遍历
图的深度遍历是一个递归过程
图的深度遍历不适用于有向图
第33题
无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是
a,b,e,c,d,f
a,c,f,e,b,d
a,e,b,c,f,d
a,e,d,f,c,b
第34题
求解最短路径的Floyd算法的时间复杂度为
O（n+c）
O（n*n）
O（n*n*n）
第35题
一无向图G（V，E），其中V（G）={1,2,3,4,5,6,7}，E（G）={（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）},对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G’(V，E’）,V（G’）=V（G），E（G’）={（1,3），（3,6），（7,3），（1,2），（1,5），（2,4）}，则采用的遍历方法是
深度优先遍历
广度优先遍历
第36题
为了实现图的广度优先遍历，除了一个标志数组标志已访问的图的结点外，还需（ ）存放被访问的结点以实现遍历。
线性表
队列
第37题
顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为
N+1
2（log2（N））
logN
N/2
第38题
二分法查找只适用于查找顺序存储的有序表，平均比较次数为（ ），在此假定N为线性表中结点数，且每次查找都是成功的。
第39题
当采用分块查找时，数据的组织方式为
数据分成若干块，每块内数据有序
数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
数据分成若干块，每块（除最后一块外）中数据个数需相同
第40题
既希望较快的查找又便于线性表动态变化的查找方法是（ ）
顺序查找
折半查找
索引顺序查找
哈希法查找
第41题
设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key mod 13,散列地址为1的链中有（ ）个记录。
3
第42题
下面关于哈希(Hash，杂凑)查找的说法正确的是
哈希函数构造的越复杂越好，因为这样随机性好，冲突小
除留余数法是所有哈希函数中最好的
不存在特别好与坏的哈希函数，要视情况而定
若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
第43题
将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。
一定会
一定不会
仍可能会
第44题
内排序方法的稳定性是指
该排序算法不允许有相同的关键字记录
该排序算法允许有相同的关键字记录
平均时间为O（n log n）的排序方法
以上都不对
第45题
下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是
选择排序法
插入排序法
快速排序法
堆排序法
第46题
对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84则采用的排序是（ ）
选择
冒泡
快速
插入
第47题
一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为
(38,40,46,56,79,84)
(40,38,46,79,56,84)
(40,38,46,56,79,84)
(40,38,46,84,56,79)
第48题
如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。
冒泡排序
快速排序
希尔排序
堆排序
简单选择排序
第49题
直接插入排序在最好情况下的时间复杂度为
O(logn)
O(n*logn)
O(n^2)
第50题
下列数据中，（ ）是非线性数据结构。
完全二叉树
堆
第51题
当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。
对
错
第52题
集合与线性表的区别在于是否按关键字排序。
第53题
顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。
第54题
对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为O(1)，在给定值为x的结点后插入一个新结点的时间复杂度为O(n)。
第55题
循环单链表的最大优点是：从任一结点出发都可访问到链表中每一个元素。
第56题
第57题
栈是实现过程和函数等子程序所必需的结构。
第58题
循环队列的引入，目的是为了克服假溢出时大量移动数据元素。
第59题
数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。
第60题
稀疏矩阵的压缩存储有两种方式：三元组表和十字链表。
第61题
当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A[l...n]中时，数组中第i个结点的左孩子为2i。
第62题
哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。
第63题
对于有N个结点的二叉树，其高度为log2n。
第64题
用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。
第65题
无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。
第66题
Prim（普里姆）算法适用于求稠密网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求稀疏网的最小生成树。
第67题
Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按路径长度依次递增的次序依次产生最短路径。
第68题
折半查找法的查找速度一定比顺序查找法快 。
第69题
在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二叉排序树与原二叉排序树相同。
第70题
分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，则最省时间的是冒泡排序，最费时间的是快速排序。
选择题(1 - 70题，共计100分)