数据结构与算法笔试题彻底整理
数据结构试题及答案
一、单项选择题
(1) 一个算法应该是（B ）。
A) 程序 B) 问题求解步骤的描述
C) 要满足五个基本属性 D) A和C
(2) 算法指的是（ D ）。
A) 计算机程序 B) 解决问题的计算方法
C) 排序算法 D) 解决问题的有限运算序列。
(3) 与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ B）。
A) 存储结构 B) 逻辑结构 C) 算法 D)操作
(4) 从逻辑上可以把数据结构分为（ C ）两大类。
A) 动态结构、静态结构 B) 顺序结构、链式结构
C) 线性结构、非线性结构 D) 初等结构、构造型结构
(5) 下列叙述中正确的是( D )。
A）一个逻辑数据结构只能有一种存储结构
B）数据的逻辑结构属于线性结构，存储结构属于非线性结构
C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率
D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率
(6) 数据的基本单位是（A ）
A) 数据项 B) 数据类型 C) 数据元素 D) 数据变量
(7) 下列程序的时间复杂度为（ ）
i=0；s=0；
while（s<n）
{ i++；s=s+i；}
A) O（） B) O（） C) O（n） D) O（n2）
(8) 下列程序段的渐进时间复杂度为（ ）。
for( int i=1;i<=n;i++)
for( int j=1;j<= m; j++)
A[i][j] = i*j ;
A）O(m2) B）O(n2) C）O(m*n) D）(m+n)
(9) 程序段如下：
sum=0；
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
sum++；
其中 n为正整数，则最后一行的语句频度在最坏情况下是（ C ）。
A）O(n） B) O(nlogn) C) O(n3) D) O(n2)
(10) 在下面的程序段中，对x的赋值语句的频度为（ C ）。
for ( i=1; i>=n ; i++)
for ( j=1; j>=n ; j++)
x:=x+1;
A) O(2n) B)O(n) C) O(n2) D) O(log2n)
(11) 程序段 for ( i:=n-1; i<=1; i--）
for ( j:=1; j>=i ; j++)
if (a[j]>a[j+1] )
{ t=a[j]; a[j]= a[j+1]; a[j+1]= t; }
其中 n为正整数，则最后一行的语句频度在最坏情况下是（D ）。
A) O(n） B) O(nlogn) C) O(n3) D) O(n2)
(12) 设有一个递归算法如下：
int fact(int n)
{ /* 大于等于0 */
if ( n<=0 ) return 1 ;
else return n*fact (n-1) ;
}
则计算fact(n)需要调用该函数的次数为（ B ）。
A) n B) n+1 C) n+2 D) n-1
(13) 下述程序段中语句①的频度是（C ）。
s=0;
for(i=1;i<m;i++)
for(j=0;j<=i;j++)
s+=j;
A) B) C) D)
(14) 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（D ）。
A)单链表 B)仅有头指针的单循环链表
C)双链表 D)仅有尾指针的单循环链表
(1) 求循环链表中当前结点的后继和前驱的时间复杂度分别是（ C ）。
A) O(n)和O(1) B) O(1)和O(1) C) O(1)和O(n) D) O(n)和O(n)
(15) 求单链表中当前结点的后继和前驱的时间复杂度分别是（）。
A) O（n）和O（1） B) O（1）和O（1）
C) O（1）和O（n） D) O(n)和O（n）
(16) 非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（A）。
A) rear->next= =head B) rear->next->next= =head
C) head->next= =rear D) head->next->next= =rear
(17) 从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（A）。
A)n-i B)n-i+1 C)n-i-1 D)i
(18) 已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，检索成功需比较的次数是（）。
A)1 B)2 C)3 D)4
(19) 假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元素占4个存储单元，则存储地址为2836的元素是（）。
A) R[3][3][3] B) R[3][3][4] C) R[4][3][5] D) R[4][3][4]
(20) 设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（）。
A) 13 B) 35 C) 17 D) 36
(21) 线性表采用链式存储时，节点的存储的地址（ B ）。
A) 必须是不连续的 B) 连续与否均可
C) 必须是连续的 D) 和头节点的存储地址相连续
(22) 用链表表示线性表的优点是（ D ）。
A) 便于随机存取 B) 花费的存储空间比顺序表少
C) 数据元素的物理顺序与逻辑顺序相同 D) 便于插入与删除
(23) 链表不具有的特点是（B ） 。
A) 插入、删除不需要移动元素 B) 可随机访问任一元素
C) 不必事先估计存储空间 D) 所需空间与线性长度成正比
(24) 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( D )。
A) n-i+1 B) i C) i+1 D) n-i
(25) 采用顺序搜索方法查找长度为n的顺序表示，搜索成功的平均搜索长度为（ D ）。
A) n B) n/2 C) (n-1)/2 D) (n+1)/2
(26) 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ B ）。
A) O(1) B) O(n) C) O(m) D) O(m+n)
(27) 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是( A )。
A) head==NULL B) head->next==NULL C) head!=NULL D) head->next==head
(28) 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。
A) 单链表 B) 仅有头指针的单循环链表
C) 双链表 D) 仅有尾指针的单循环链表
(29) 若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（ A）。
A) 栈 B) 线性表 C) 队列 D) 二叉排序树
(30) 顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（ D）。
A) s.elem［top］=e； s.top=s.top+1； B) s.elem［top+1］=e；s.top=s.top+1；
C) s.top=s.top+1； s.elem［top+1］=e； D) s.top=s.top+1；s.elem［top］=e；
(31) 循环队列sq中，用数组elem［0··25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（ C）。
A) 8 B) 16 C) 17 D) 18
(32) 链式栈与顺序栈相比，一个比较明显的优点是（ B ）。
A) 插入操作更加方便 B) 通常不会出现栈满的情况
C) 不会出现栈空的情况 D) 删除操作更加方便
(33) 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（ B ）。
A) 较快 B) 较慢 C) 相同 D) 不定
(34) 若已知一个栈的入栈序列是1,2,3,4……n，其输出序列为p1,p2,p3,……pn，若p1= =n,则pi为（ C ）。
A) i B) n= =i C) n-i+1 D) 不确定
(35) 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是( C ) 。
A) edcba B) decba C) dceab D) abcde
(36) 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( D )。
A) 2，4，3，1，5，6 B) 3，2，4，1，6，5
C) 4，3，2，1，5，6 D) 2，3，5，1，6，4
(37) 对于栈操作数据的原则是（ B ）。
A) 先进先出 B) 后进先出 C) 后进后出 D) 不分顺序
(38) 栈和队列的共同点是（ C ）。
A) 都是先进先出 B) 都是先进后出
C) 只允许在端点处插入和删除元素 D) 没有共同点
(39) 一个队列的入队序列是1，2，3，4，则队列的输出序列是（ B ）。
A) 4,3,2,1 B) 1,2,3,4 C)1,4,3,2 D) 3,2,4,1
(40) 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出对操作后其头指针front值为（D ）。
A) front=front+1 B) front=(front+1)%(m-1)
C) front=(front-1)%m D) front=(front+1)%m
(41) 引起循环队列队头位置发生变化的操作是( A )。
A) 出队 B) 入队 C) 取队头元素 D) 取队尾元素
(2) 设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。
A）(rear-front+m)%m B）rear-front+1 C）(front-rear+m)%m D）(rear-front)%m
(42) 二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且A[0][0]地址为150，则元素A[9][7]的地址为( A )。
A) 429 B) 432 C) 435 D) 438
(43) 设有一个10阶的对称矩阵A[10][10]，采用压缩方式按行将矩阵中下三角部分的元素存入一维数组B[]中，A[0][0]存入B[0]中，则A[8][5]在B[]中（ C ）位置。
A) 32 B) 33 C) 41 D) 65
(44) 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i<j）的位置k的关系为( A )。
A) i*(i-1)/2+j B) j*(j-1)/2+i C) i*(i+1)/2+j D) j*(j+1)/2+i
(45) 对稀疏矩阵进行压缩存储目的是（ C ）。
A) 便于进行矩阵运算 B) 便于输入和输出
C) 节省存储空间 D) 降低运算的时间复杂度
(46) 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( B)。
A) (e,f) B) ((e,f)) C) (f) D) ( )
(47) 设广义表L=（（a,b,c）），则L的长度和深度分别为（ C ）。
A) 1和1 B) 1和3 C) 1和2 D) 2和3
(48) 树中所有结点的度之和等于所有结点数加（ C ）。
A) 0 B)1 C) -1 D) 2
(49) 在一棵具有n个结点的二叉链表中，所有结点的空域个数等于（ C ）。
A) n B) n-1 C) n+1 D) 2*n
(50) 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是(B ）的二叉树。
A) 空或只有一个结点 B) 高度等于其节点数
C) 任一结点无左孩子 D) 任一结点无右孩子
(51) 含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（ ）
A)3 B)4 C)5 D)6
(52) 除第一层外，满二叉树中每一层结点个数是上一层结点个数的（ ）
A)1/2倍 B)1倍 C) 2倍 D) 3倍
(53) 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（ ）
A)24 B)25 C)98 D)99
(54) 可以惟一地转化成一棵一般树的二叉树的特点是（ ）
A)根结点无左孩子 B)根结点无右孩子 C)根结点有两个孩子 D)根结点没有孩子
(55) 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B ）。
A) 2h B) 2h-1 C) 2h+1 D) h+1
(56) 在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为1，则度为0的节点个数为（C ）。
A) 4 B) 5 C) 6 D) 7
(57) 设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n,森林F中第一棵 子树的结点个数是（ A ）。
A)m-n B)m-n-1 C) n+1 D) 条件不足，无法确定
(58) 将一株有100个节点的完全二叉树从上到下，从左到右依次进行编号，根节点的编号为1，则编号为49的节点的 左孩子编号为（A）。
A) 98 B) 89 C) 50 D) 没有孩子
(60) 树最适合用来表示（ C ）。
A) 有序数据元素 B) 无序数据元素
C) 元素之间具有分支层次关系的数据 D) 元素之间无联系的数据
(61) 在一个非空二叉树的中序遍历序列中，根结点的右边（ A ）。
A) 只有右子树上的所有结点 B) 只有右子树上的部分结点
C) 只有左子树的上的部分结点 D) 只有左子树上的所有结点
(62) 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中相对次序（ D ）。
A) 不发生改变 B) 发生改变 C) 不能确定 D) 以上都不对
(63) 在有n个叶子结点的哈夫曼树中，其结点总数为（ D ）。
A) 不确定 B) 2n C) 2n+1 D) 2n-1
(64) 权值为{1,2,6,8}的四个结点构成的哈夫曼树的带权路径长度是（ D ）。
A) 18 B) 28 C) 19 D) 29
(65) 对一个满二叉树，m个树叶，k个分枝结点，n个结点，则（ D ）。
A) n=m+1 B) m+1=2n C) m=k-1 D) n=2k+1
(66) 在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ D ）。
A) e B) 2e C) n2-e D) n2-2e
(67) 若采用邻接矩阵翻存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。
A) 上三角矩阵 B) 稀疏矩阵 C) 对角矩阵 D) 对称矩阵
(68) 在一个图中，所有顶点的度数之和等于所有边数的（ C ）倍。
A) 1/2 B) 1 C) 2 D) 4
(69) 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。
A) 1/2 B) 1 C) 2 D) 4
(70) 对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为（ ）。
A) O（n） B) O(e) C) O(n+e) D) O(n2)
(71) 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ ）。
A) 深度优先搜索算法 B) 广度优先搜索算法
C) 求最小生成树的prim算法 D) 拓扑排序算法
(72) n个顶点的连通图至少中含有( A )。
A) n-1 B) n C) n+1 D) 0
(73) n个顶点的完全有向图中含有( D )。
A) n-1条有向边 B) n条有向边 C) n(n-1)/2条有向边 D) n(n-1)条有向边
(74) 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除预某个顶点vi相关的所有弧的时间复杂度是（ C ）。
A) O(n) B) O(e) C) O(n+e) D) O(n*e)
(75) 在无向图中定义顶点Vi域Vj之间的路径为从Vi到达Vj的一个（ A ）。
A) 顶点序列 B) 边序列 C) 权值总和 D) 边的条数
(76) 无向图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)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ 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
(77) 下面哪一方法可以判断出一个有向图是否有环（回路）B。
A) 求节点的度 B) 拓扑排序 C) 求最短路径 D) 求关键路径
(78) 图的广度优先搜索类似于树的（ B ）次序遍历。
A) 先根 B) 中根 C) 后根 D) 层次
(79) 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( B )。
A) O(n) B) O(n+e) C) O(n2) D) O(n3)
(80) 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>, <V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（ A ）。
A) V1,V3,V4,V6,V2,V5,V7 B) V1,V3,V2,V6,V4,V5,V7
C) V1,V3,V4,V5,V2,V6,V7 D) V1,V2,V5,V3,V4,V6,V7
(81) 关键路径是事件结点网络中（ A ）。
A) 从源点到汇点的最长路径 B) 从源点到汇点的最短路径
C) 最长回路 D) 最短回路
(82) 有n个结点的有向完全图的弧数是（ C）。
A) n2 B) 2n C) n(n-1) D) 2n(n+1)
(83) 设图的邻接链表如题12图所示，则该图的边的数目是（B ）。
A) 4 B) 5 C) 10 D) 20
(84) 在一个图中，所有顶点的度数之和等于图的边数的（ A ）倍。
A) 1/2 B) 1 C) 2 D) 4
(85) 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。
A) 1/2 B) 1 C) 2 D) 4
(86) 有8个结点的无向图最多有（ B ）条边。
A) 14 B) 28 C) 56 D) 112
(87) 有8个结点的无向连通图最少有（ C ）条边。
A) 5 B) 6 C) 7 D) 8
(88) 有8个结点的有向完全图有（ C ）条边。
A) 14 B) 28 C) 56 D) 112
(89) 用邻接表表示图进行广度优先遍历时，通常是采用（B ）来实现算法的。
A) 栈 B) 队列 C) 树 D) 图
(90) 用邻接表表示图进行深度优先遍历时，通常是采用（ A ）来实现算法的。
A) 栈 B) 队列 C) 树 D) 图
(91) 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ C ）。
A) 0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C) 0 4 2 3 1 6 5 D) 0 3 6 1 5 4 2
建议：0 1 3 4 2 5 6
(92) 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（ D ）。
A) 0 2 4 3 1 5 6 B) 0 1 3 5 6 4 2 C) 0 4 2 3 1 6 5 D) 0 1 3 4 2 5 6
(93) 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（ B ）。
A) 0 2 4 3 6 5 1 B) 0 1 3 6 4 2 5 C) 0 4 2 3 1 5 6 D) 0 1 3 4 2 5 6
（建议：0 1 2 3 4 5 6）
(94) 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（ ）。
A) 0 2 4 3 1 6 5 B) 0 1 3 5 6 4 2 C) 0 1 2 3 4 6 5 D) 0 1 2 3 4 5 6
(95) 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ D ）。
A) 1 3 2 B) 0 2 3 1 C) 0 3 2 1 D) 0 1 2 3
(96) 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（ A ）。
A) 0 3 2 1 B) 0 1 2 3 C) 0 1 3 2 D) 0 3 1 2
(97) 深度优先遍历类似于二叉树的（ A ）。
A) 先序遍历 B) 中序遍历 C) 后序遍历 D) 层次遍历
(98) 广度优先遍历类似于二叉树的（ D ）。
A) 先序遍历 B) 中序遍历 C) 后序遍历 D) 层次遍历
(99) 任何一个无向连通图的最小生成树（ A ）。
A) 只有一棵 B) 一棵或多棵 C) 一定有多棵 D) 可能不存在
（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）
(100) 在分析折半查找的性能时常常加入失败节点，即外节点，从而形成扩充的二叉树。若设失败节点i所在层次为Li，那么查找失败到达失败点时所做的数据比较次数是（D ）。
A) Li+1 B) Li+2 C) Li-1 D) Li
(101) 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（B ）个元素。
A) 8 B) 63.5 C) 63 D) 7
(102) 由同一组关键字集合构造的各棵二叉排序树( B )。
A) 其形态不一定相同，但平均查找长度相同
B) 其形态不一定相同，平均查找长度也不一定相同
C) 其形态均相同，但平均查找长度不一定相同
D) 其形态均相同，平均查找长度也都相同
(103) 衡量查找算法效率的主要标准是（ C ）。
A) 元素的个数 B) 所需的存储量 C) 平均查找长度 D) 算法难易程度
(104) 适合对动态查找表进行高效率查找的组织结构是（C ）。
A) 有序表 B) 分块有序表 C) 二叉排序树 D) 快速排序
(3) 能进行二分查找的线性表,必须以（A）。
A) 顺序方式存储，且元素按关键字有序
B) 链式方式存储，且元素按关键字有序
C) 顺序方式存储，且元素按关键字分块有序
D) 链式方式存储，且元素按关键字分块有序
(105) 为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为（ ）
A) 5 B)37 C) 41 D) 62
(106) 对关键字序列(56,23,78,92,88,67,19,34)进行增量为3的一趟希尔排序的结果为 ( D )。
A) (19,23,56,34,78,67,88,92) B) 23,56,78,66,88,92,19,34)
C) (19,23,34,56,67,78,88,92) D) (19,23,67,56,34,78,92,88)
(107) 用某种排序方法对关键字序列{35,84,21,47,15,27,68,25,20}进行排序时，序列的变化情况如下：
20,15,21,25,47,27,68,35,84
15,20,21,25,35,27,47,68,84
15,20,21,25,27,35,47,68,84
则采用的方法是（D ）。
A) 直接选择排序 B) 希尔排序 C) 堆排序 D) 快速排序
(108) 一组记录的排序码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准得到的第一次划分结果为（C ）。
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
(109) 快速排序在最坏情况下的时间复杂度是（B ）
A) O(n2log2n) B) O(n2) C) O(nlog2n) D) O(log2n)
(110) 下列排序算法中不稳定的是（ D ）。
A) 直接选择排序 B) 折半插入排序 C) 冒泡排序 D) 快速排序
(111) 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列进行同样的排序操作，直到子序列为空或只剩下一个元素为止。这样的排序方法是（ C ）。
A) 直接选择排序 B) 直接插入排序 C) 快速排序 D) 冒泡排序
(112) 将5个不同的数据进行排序，至多需要比较（ C ）次。
A) 8 B) 9 C) 10 D) 25
(113) 排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ D）。
A)选择排序 B)快速排序 C)冒泡排序 D)插入排序
(114) 排序算法中，不稳定的排序是（ C）。
A)直接插入排序 B)冒泡排序 C)堆排序 D)选择排序
(115) 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ C ）.
A) 希尔排序 B) 冒泡排序 C) 插入排序 D) 选择排序
(116) 从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（ D ）。
A) 希尔排序 B) 归并排序 C) 插入排序 D) 选择排序
(117) 对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。（ B ）
A) 从小到大排列好的 B) 从大到小排列好的
C) 元素无序 D) 元素基本有序
(118) 对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为（ D ）。
A) n+1 B) n C) n-1 D) n(n-1)/2
(119) 快速排序在下列哪种情况下最易发挥其长处。（ C ）
A) 被排序的数据中含有多个相同排序码
B) 被排序的数据已基本有序
C) 被排序的数据完全无序
D) 被排序的数据中的最大值和最小值相差悬殊
(120) 对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是（ B ）。
A) O(n) B) O(n2) C) O(nlog2n) D) O(n3)
(121) 若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。
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
(122) 下列关键字序列中，（ D ）是堆。
A) 16, 72, 31, 23, 94, 53 B) 94, 23, 31, 72, 16, 53
C) 16, 53, 23, 94，31, 72 D) 16, 23, 53, 31, 94, 72
(123) 堆是一种（ B ）排序。
A) 插入 B) 选择 C) 交换 D) 归并
(124) 堆的形状是一棵（ C ）。
A) 二叉排序树 B) 满二叉树 C) 完全二叉树 D) 平衡二叉树
(125) 若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为（ B ）。
A) 79, 46, 56, 38, 40, 84 B) 84, 79, 56, 38, 40, 46
C) 84, 79, 56, 46, 40, 38 D) 84, 56, 79, 40, 46, 38
(126) 下述几种排序方法中，要求内存最大的是（ C ）。
A) 插入排序 B) 快速排序 C) 归并排序 D) 选择排序
(127) 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（ ）。
A) -1，4，8，9，20，7，15，7 B) -1，7，15，7，4，8，20，9
C) -1，4，7，8，20，15，7，9 D) A，B，C 均不对。
(128) 51．下列四个序列中，哪一个是堆（ ）。
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
(129) 以下序列不是堆的是( )。
A) (100,85,98,77,80,60,82,40,20,10,66) B) (100,98,85,82,80,77,66,60,40,20,10)
C) (10,20,40,60,66,77,80,82,85,98,100) D) (100,85,40,77,80,60,66,98,82,10,20)
(130) 快速排序方法在（ ）情况下最不利于发挥其长处。
A) 要排序的数据量太大 B) 要排序的数据中含有多个相同值
C) 要排序的数据个数为奇数 D) 要排序的数据已基本有序
(131) 对关键码序列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)
(132) 对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ ）。
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}
二、填空题
(133) 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。
(134) 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。
(135) 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。
(136) 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。
(137) 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
(138) 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。
(139) 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。
(140) 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。
(141) 数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。
(142) 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。
(143) 一个算法的效率可分为 时间 效率和 空间 效率。
(144) 对于给定的n个元素,可以构造出的逻辑结构有 集合，线性表，树，图 四种。
(145) 顺序映象的特点是借助元素在存储器中的 相对位置来表示数据元素之间的逻辑关系。非顺序映象的特点是借助是指示元素存储地址的 指针表示数据元素之间的逻辑关系。任何一个算法的设计取决于选定 逻辑结构，而算法的实现依赖于采用的 存储结构。
(146) 数据类型是一组___________性质相同的值集合以及定义在这个值集合上的一组操作的总称。
(147) 数据对象是___________性质相同的数据元素的集合，是数据的一个子集。
(148) 如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，则称该类运算为 型运算。引用
(149) 算法的 健壮特性是指做为一个好的算法，当输入的数据非法时，也能适当地做出正确反应或进行相应的处理，而不会产生一些莫名其妙的输出结果。
(150) 算法分析不是针对实际执行时间的精确的算出算法执行具体时间的分析，而是针对算法中语句的 执行次数做出估计，从中得到算法执行时间的信息。
(151) T(n)=O(f(n))，它表示随问题规模n的增大算法的执行时间的增长率和f(n)的增长率 相同，称作算法的渐进时间复杂度，简称时间复杂度。
(152) 若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法为 原地工作，辅助空间为O(1)。
(153) 在带有头结点的单链表中L中，第一个元素结点的指针是 。L->next
(154) 在一个带头节点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head= 。p->next->next
(155) 设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句: py->next=px->next; px->next=py。
(156) 对于栈操作数据的原则是 。后进先出
(157) 设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为 。(rear-front+m)%m
(158) 若已知一个栈的入栈序列是1,2,3,4……n，其输出序列为p1,p2,p3,……pn，若p1= =n,则pi为 。n-i+1
(159) 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
(160) 通常程序在调用另一个程序时，都需要使用一个 栈来保存被调用程序内分配的局部变量。形式参数的存储空间以及返回地址。
(161) 栈下溢是指在___栈空_____时进行出栈操作。
(162) 用P表示入栈操作，D表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的P和D的操作串为_______ 。PDPPDPDD
(163) 在具有n个单元的循环队列中，队满共有
上一篇：
学习C语言中的递归技巧
推荐阅读
-
数据结构与算法笔试题彻底整理
-
反传销网8月30日发布：视频区块链里的骗子，币里的韭菜，杜子建骂人了！金融大V周召说区块链！——“一小帮骗子玩一大帮小白，被割韭菜，小白还轮流被割，割的就是你！” 什么区块链，统统是骗子 作者：周召（知乎金融领域大Ｖ，毕业于上海财经大学，目前任职上海某股权投资基金合伙人） 有人问我，区块链现在这么火，到底是不是骗局？ 我的回答是： 是骗局。而且我并不是说数字货币是骗局，而是说所有搞区块链的都是骗局。 -01- 区块链是一种鸡肋技术 人类社会任何技术的发明应用，本质都是为了提高社会的生产效率。而所谓区块链技术本质不过是几种早已成熟的技术的大杂烩，冗余且十分低效，除了提高了洗钱和诈骗的效率以外，对人类社会的进步毫无贡献。 真正意义上的区块链得包含三个要素：分布式系统（包括记账和存储），无法篡改的数据结构，以及共识算法，三者互为基础和因果，就像三体世界一样。看上去挺让人不明觉厉的，而经过几年的瞎折腾，稍微懂点区块链的碰了几次壁后都已经渐渐明白区块链其实并没有什么卵用，区块链技术已经名存实亡，沦为了营销工具和传销组织的画皮。 因为符合上述定义的、以比特币为代表的原教旨区块链技术，是反效率的，从经济学角度来说，不但不是一种帕累托改进，甚至还可以说是一种帕累托倒退。 原教旨区块链技术的效率十分低下，因为要遍历所有节点，只能做非常轻量级的数据应用，一旦涉及到大量的数据传输与更新，区块链就瞎了。 一方面整条链交易速度会极慢，另一方面数据库容量极速膨胀，考虑到人手一份的存储机制，区块链其实是对存储资源和能源的一种极大的浪费。 这里还没有加上为了取得所谓的共识和挖矿消耗的巨大的能源，如果说区块链技术是屎，那么这波区块链投机浪潮可谓人类历史上最大规模的搅屎运动。 区块链也验证不了任何东西。 所谓的智能合约，即不智能，也非合约。我看有人还说，如果有了智能合约，就可以跟老板签一份放区块链上，如果明年销售业绩提升30%，就加薪10%，由于区块链不能篡改，不能抵赖，所以老板必须得执行，说得有板有眼，不懂行的愣一看，好像还真是那么回事。 但仔细一想，问题就来了。首先，在区块链上如何证明你真的达到了30%业绩提升？即便真的达到老板耍赖如何执行？ 也就是说，如果区块链真这么厉害，要法院和仲裁干什么。 人类社会真正的符合成本效益原则的是代理制度。之前有人说要用区块链改造注册会计师行业，我不知道他准备怎么设计，我猜想他思路大概是这样的，首先肯定搞去中心化，让所有会计师到链上来，然后一个新人要成为注册会计师就要所有会计师同意并记录在链上。 那我就请问了，我每天上班累死累活，为什么还要花时间去验证一个跟我无关的的人的专业能力？最优做法当然是组织一个委员会，让专门的人来负责，这不就是现在注册会师协会干的事儿吗？区块链的逻辑相当于什么事情都要拿出来公投，这个绝对是扯淡的。 当然这么说都有点抬举区块链了，区块链技术本身根本没有判断是非能力，如果这么高级的人工智能，靠一个无脑分布式记账就能实现的话，我们早就进入共产主义社会了。 虽然EOS等数字货币采用了超级节点，通过再中心化的方式提高效率，有点行业协会的意思，是对区块链原教旨主义的一种修正，但是依然无法突破区块链技术最本质的局限性。有人说，私有链和联盟链是区块链技术的未来，也是扯淡，因为区块链技术没有未来。如果有，说明他是包装成区块链的伪区块链技术。 区块链所涉及的所有底层技术，不管是分布式数据库技术，加密技术，还是点对点传输技术等，基本都是早已存在没什么秘密可言的技术。 比特币系统最重要的特性是封闭性和自洽性，他验证不了任何系统自身以外产生的信息的真实性。 所谓系统自身产生的信息，就是数据库数据的变动信息，有价值的基本上有且只有交易信息。所以说比特币最初不过是中本聪一种炫技的产物，来证明自己对几种技术的掌握，你看我多牛逼，设计出了一个像三体一样的系统。因此，数字货币很有可能是区块链从始至终唯一的杀手应用。 比特币和区块链概念从诞生到今天已经快10年了，很多人说区块链技术在爆发的前夜，但这个前夜好像是不是有点过长了啊朋友，跟三体里的长夜有一拼啊。都说区块链技术像是90年代初的互联网，可是90年代初的互联网在十年发展后，已经出现了一大批伟大的公司，阿里巴巴在99年都成立了，区块链怎么除了币还是币呢？ 正规的数字货币未来发展的形式无外乎几种，要么就是论坛币形式，或者类似股票的权益凭证等。问题是论坛币和股票之前，本来也都电子化了，区块链来了到底改变了什么呢？ 所有想把TOKEN和应用场景结合起来的人最后都很痛苦，最后他们会发现区块链技术就是脱裤子放屁，自己辛苦搞半天，干嘛不自己作为中心关心门来收钱？最后这些人都产生了价值的虚无感，最终精神崩溃，只能发币疯狂收割韭菜，一边嘴里还说着我是个好人之类的奇怪的话。 因此，之前币圈链圈还泾渭分明，互相瞧不起，但这两年链圈逐渐坐不住了，想着是不是趁着泡沫没彻底破灭之前赶快收割一波，不然可能什么都捞不着了。 前段时间和一个名校毕业的链圈朋友瞎聊天，他说他们“致力于用区块链技术解决数字版权保护问题”，我就问他一个问题，你们如何保证你链的版权所有权声明是真实的，万一盗版者抢先一步把数据放在链上怎么办。他说他们的解决方案是连入国家数字版权保护中心的数据库进行验证…… 所以说区块链技术就是个鸡肋，研究到最后都会落入效率与真实性的黑洞，很多人一头扎进链圈后才发现，真正意义上的区块链技术，其实什么都干不了。 -02- 不是蠢就是坏的区块链媒体 空气币和区块链的造富神话，让区块链自媒体也开始迎风乱扭。一群群根本不知道区块链为何物的妖魔鬼怪纷纷进驻区块链自媒体战场，开始大放厥词胡编乱造。 任何东西，但凡只要和区块，链，分，分布式，记账，加密，验证，可追溯等等这些个关键词沾到哪怕一点点，这些所谓的区块链媒体人就会像狗闻到了屎了一样疯狂地把区块链概念往上套。 这让我想起曾经一度也是热闹非凡的物联网，我曾经去看过江苏一家号称要改变世界的“物联网”企业，过去一看是生产路由器的，我黑人问号脸，对方解释说没有路由器万物怎么互联，我觉得他说得好有道理，竟无言以对。 好，下面让我们进入奇葩共赏析时间，来看看区城链媒体经常有哪些危言耸听的奇谈怪论 区块链（分布式记账）的典型应用是*？？ 正如前面所说，真正意义上的区块链分布式记账，不光包括“记”这个动作，还包括分布式存储和共识机制等。而*诞生远远早于区块链这个词的出现，勉强算是“分布式编辑”吧，就被很多区块链媒体拿来强行充当区块链技术应用的典范。 其实事实恰恰相反，*恰恰是去中心化失败的典范，现在如果没有精英和专业人士的编辑和维护，*早就没法看了。 区块链会促进社会分工？？ 罗振宇好像就说过类似的话，虽然罗振宇说过很多没有逻辑的话，但这句话绝对是最没逻辑思维的。很多区块链自媒体也常常用这句话来忽悠老百姓，说分工代表效率提高社会进步，而区块链“无疑”会促进分工，他们的理由仅仅是分工和分布式记账都共用一个“分”字，就强行把他们扯到一起。 实际情况恰恰相反，区块链是逆分工的，区块链精神是号召所有人积极地参与到他不擅长也不想掺合的事情里面去。 区块链不能像上帝一样许诺他的子民死后上天国，只能给他们许诺你们是六度人脉中的第一级，我可以赚后面五级人的钱，你处于金字塔的顶端。