文档库 最新最全的文档下载
当前位置:文档库 › 数据结构试题库答案

数据结构试题库答案

数据结构试题库答案
数据结构试题库答案

数据结构试题及答案

一、单项选择题

(1)一个算法应该是()。

A) 程序B) 问题求解步骤的描述

C) 要满足五个基本属性D) A和C

(2)算法指的是()。

A) 计算机程序B) 解决问题的计算方法

C) 排序算法D) 解决问题的有限运算序列。

(3)与数据元素本身的形式、内容、相对位置、个数无关的是数据的()。

A) 存储结构B) 逻辑结构C) 算法D)操作

(4)从逻辑上可以把数据结构分为()两大类。

A) 动态结构、静态结构B) 顺序结构、链式结构

C) 线性结构、非线性结构D) 初等结构、构造型结构

(5)下列叙述中正确的是( )。

A)一个逻辑数据结构只能有一种存储结构

B)数据的逻辑结构属于线性结构,存储结构属于非线性结构

C)一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理的效率D)一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理的效率

(6)数据的基本单位是()

A) 数据项B) 数据类型C) 数据元素D) 数据变量

(7)下列程序的时间复杂度为()

i=0;s=0;

while(s

{ i++;s=s+i;}

A) O(n)B) O(n2)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为正整数,则最后一行的语句频度在最坏情况下是()。

A)O(n)B) O(nlogn) C) O(n3) D) O(n2) (10)在下面的程序段中,对x的赋值语句的频度为()。

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为正整数,则最后一行的语句频度在最坏情况下是()。

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)需要调用该函数的次数为()。

A) n B) n+1 C) n+2 D) n-1

(13)下述程序段中语句①的频度是()。

s=0;

for(i=1;i

for(j=0;j<=i;j++)

s+=j;

A)

21

1)

m

)(

m

(-

+

B)

21)

m

(

m-

C)

21

2)

m

)(

m

(-

+

D)

21)

m

(

m+

(14)若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则最节

省运算时间的存储方式是()。

A)单链表B)仅有头指针的单循环链表

C)双链表D)仅有尾指针的单循环链表

(1)求循环链表中当前结点的后继和前驱的时间复杂度分别是()。

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) rear->next= =head B) rear->next->next= =head

C) head->next= =rear D) head->next->next= =rear

(17)从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动的元素的个数是

()。

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)线性表采用链式存储时,节点的存储的地址()。

A) 必须是不连续的B) 连续与否均可

C) 必须是连续的D) 和头节点的存储地址相连续

(22)用链表表示线性表的优点是()。

A) 便于随机存取B) 花费的存储空间比顺序表少

C) 数据元素的物理顺序与逻辑顺序相同D) 便于插入与删除

(23)链表不具有的特点是()。

A) 插入、删除不需要移动元素B) 可随机访问任一元素

C) 不必事先估计存储空间D) 所需空间与线性长度成正比

(24)在长度为n的顺序表中删除第i个元素(1≤i≤n)时,元素移动的次数为( )。

A) n-i+1 B) i C) i+1 D) n-i

(25)采用顺序搜索方法查找长度为n的顺序表示,搜索成功的平均搜索长度为()。

A) n B) n/2C) (n-1)/2 D) (n+1)/2

(26)将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为()。

A) O(1) B) O(n) C) O(m) D) O(m+n)

(27)若不带头结点的单链表的头指针为head,则该链表为空的判定条件是( )。

A) head==NULL B) head->next==NULL C) head!=NULL D) head->next==head

(28)某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用

()存储方式最节省运算时间。

A) 单链表B) 仅有头指针的单循环链表

C) 双链表D) 仅有尾指针的单循环链表

(29)若允许表达式内多种括号混合嵌套,则为检查表达式中括号是否正确配对的算法,通常选用

的辅助结构是()。

A) 栈B) 线性表C) 队列D) 二叉排序树

(30)顺序栈S中top为栈顶指针,指向栈顶元素所在的位置,elem为存放栈的数组,则元素e

进栈操作的主要语句为()。

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,则当前队列中的元素个数为()。

A) 8 B) 16 C) 17 D) 18

(32)链式栈与顺序栈相比,一个比较明显的优点是()。

A) 插入操作更加方便B) 通常不会出现栈满的情况

C) 不会出现栈空的情况D) 删除操作更加方便

(33)一个递归的定义可以用递归过程求解,也可以用非递归过程求解,但单从运行时间来看,通

常递归过程比非递归过程()。

A) 较快B) 较慢C) 相同D) 不定

(34)若已知一个栈的入栈序列是1,2,3,4……n,其输出序列为p1,p2,p3,……pn,若p1= =n,则pi

为()。

A) i B) n= =i C) n-i+1 D) 不确定

(35)一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是( ) 。

A) edcba B) decba C) dceab D) abcde

(36)若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则不可能出现的出栈序列

是( )。

A) 2,4,3,1,5,6B) 3,2,4,1,6,5

C) 4,3,2,1,5,6 D) 2,3,5,1,6,4

(37)对于栈操作数据的原则是()。

A) 先进先出B) 后进先出C) 后进后出D) 不分顺序

(38)栈和队列的共同点是()。

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

C) 只允许在端点处插入和删除元素D) 没有共同点

(39)一个队列的入队序列是1,2,3,4,则队列的输出序列是()。

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值为()。

A) front=front+1 B) front=(front+1)%(m-1)

C) front=(front-1)%m D) front=(front+1)%m

(41)引起循环队列队头位置发生变化的操作是( )。

A) 出队B) 入队C) 取队头元素D) 取队尾元素

(2)设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的元素

个数为()。

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) 429B) 432C) 435 D) 438

(43)设有一个10阶的对称矩阵A[10][10],采用压缩方式按行将矩阵中下三角部分的元素存入一

维数组B[]中,A[0][0]存入B[0]中,则A[8][5]在B[]中()位置。

A) 32 B) 33C) 41 D) 65

(44)若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次

存放于一维数组B[1..(n(n+1))/2]中,则在B中确定aij(i

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)对稀疏矩阵进行压缩存储目的是()。

A) 便于进行矩阵运算B) 便于输入和输出

C) 节省存储空间D) 降低运算的时间复杂度

(46)对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( )。

A) (e,f) B) ((e,f))C) (f) D) ( )

(47)设广义表L=((a,b,c)),则L的长度和深度分别为()。

A) 1和1 B) 1和3 C) 1和2 D) 2和3

(48)树中所有结点的度之和等于所有结点数加()。

A) 0 B)1 C) -1 D) 2

(49)在一棵具有n个结点的二叉链表中,所有结点的空域个数等于()。

A) n B) n-1 C) n+1 D) 2*n

(50)某二叉树的先序序列和后序序列正好相反,则该二叉树一定是()的二叉树。

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的结点,则此类二叉树中所包含的结点数至少为

()。

A) 2h B) 2h-1 C) 2h+1 D) h+1

(56)在一棵度为3的树中,度为3的节点个数为2,度为2的节点个数为1,则度为0的节点个

数为()。

A) 4 B) 5 C) 6 D) 7

(57)设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F

中第一棵子树的结点个数是()。

A)m-n B)m-n-1 C) n+1 D) 条件不足,无法确定

(58)将一株有100个节点的完全二叉树从上到下,从左到右依次进行编号,根节点的编号为1,

则编号为49的节点的左孩子编号为()。

A) 98B) 89 C) 50 D) 没有孩子

(59)下列图示的顺序存储结构表示的二叉树是(A )

(60)树最适合用来表示()。

A) 有序数据元素B) 无序数据元素

C) 元素之间具有分支层次关系的数据D) 元素之间无联系的数据

(61)在一个非空二叉树的中序遍历序列中,根结点的右边()。

A) 只有右子树上的所有结点B) 只有右子树上的部分结点

C) 只有左子树的上的部分结点D) 只有左子树上的所有结点

(62)任何一棵二叉树的叶结点在先序、中序和后序遍历序列中相对次序()。

A) 不发生改变B) 发生改变C) 不能确定D) 以上都不对

(63)在有n个叶子结点的哈夫曼树中,其结点总数为()。

A) 不确定B) 2n C) 2n+1 D) 2n-1

(64)权值为{1,2,6,8}的四个结点构成的哈夫曼树的带权路径长度是()。

A) 18 B) 28 C) 19 D) 29

(65)对一个满二叉树,m个树叶,k个分枝结点,n个结点,则()。

A) n=m+1 B) m+1=2n C) m=k-1 D) n=2k+1

(66)在含有n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为()。

A) e B) 2e C) n2-e D) n2-2e

(67)若采用邻接矩阵翻存储一个n个顶点的无向图,则该邻接矩阵是一个()。

A) 上三角矩阵B) 稀疏矩阵C) 对角矩阵D) 对称矩阵

(68)在一个图中,所有顶点的度数之和等于所有边数的()倍。

A) 1/2 B) 1 C) 2 D) 4

(69)在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍。

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) n-1 B) n C) n+1 D) 0

(73)n个顶点的完全有向图中含有( )。

A) n-1条有向边B) n条有向边C) n(n-1)/2条有向边D) n(n-1)条有向边

(74)假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除预某个顶点vi相关的所有弧

的时间复杂度是()。

A) O(n) B) O(e) C) O(n+e) D) O(n*e)

(75)在无向图中定义顶点V i域Vj之间的路径为从V i到达Vj的一个()。

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)},对该图进行

深度优先遍历,得到的顶点序列正确的是()。

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)下面哪一方法可以判断出一个有向图是否有环(回路)。

A) 求节点的度B) 拓扑排序C) 求最短路径D) 求关键路径

(78)图的广度优先搜索类似于树的()次序遍历。

A) 先根B) 中根C) 后根D) 层次

(79)在图采用邻接表存储时,求最小生成树的Prim 算法的时间复杂度为( )。

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={,,,

,,,,,},G的拓扑序列是()。

A) V1,V3,V4,V6,V2,V5,V7B) V1,V3,V2,V6,V4,V5,V7

C) V1,V3,V4,V5,V2,V6,V7D) V1,V2,V5,V3,V4,V6,V7

(81)关键路径是事件结点网络中()。

A) 从源点到汇点的最长路径B) 从源点到汇点的最短路径

C) 最长回路D) 最短回路

(82)有n个结点的有向完全图的弧数是()。

A) n2B) 2n C) n(n-1) D) 2n(n+1)

(83)设图的邻接链表如题12图所示,则该图的边的数目是()。

83题图

A) 4 B) 5 C) 10 D) 20

(84)在一个图中,所有顶点的度数之和等于图的边数的()倍。

A) 1/2 B) 1 C) 2 D) 4

(85)在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍。

A) 1/2 B) 1 C) 2 D) 4

(86) 有8个结点的无向图最多有( )条边。

A) 14

B) 28 C) 56 D) 112

(87) 有8个结点的无向连通图最少有( )条边。

A) 5

B) 6 C) 7 D) 8

(88) 有8个结点的有向完全图有( )条边。

A) 14

B) 28 C) 56 D) 112

(89) 用邻接表表示图进行广度优先遍历时,通常是采用( )来实现算法的。

A) 栈

B) 队列 C) 树 D) 图

(90) 用邻接表表示图进行深度优先遍历时,通常是采用( )来实现算法的。

A) 栈

B) 队列 C) 树 D) 图

(91) 已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是( )。

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出发,按深度优先遍历的结点序列是

( )。

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出发,按广度优先遍历的结点序列是

( )。

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出发按深度优先遍历的结点序列是( )。

??????????

?

???????????01

1

1

10110000101101011001100100011001001101111

A) 1 3 2 B) 0 2 3 1 C) 0 3 2 1 D) 0 1 2 3

(96)已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优先遍历的结点序列是()。

A) 0 3 2 1 B) 0 1 2 3 C) 0 1 3 2 D) 0 3 1 2

(97)深度优先遍历类似于二叉树的()。

A) 先序遍历B) 中序遍历C) 后序遍历D) 层次遍历

(98)广度优先遍历类似于二叉树的()。

A) 先序遍历B) 中序遍历C) 后序遍历D) 层次遍历

(99)任何一个无向连通图的最小生成树()。

A) 只有一棵B) 一棵或多棵C) 一定有多棵D) 可能不存在

(注,生成树不唯一,但最小生成树唯一,即边权之和或树权最小的情况唯一)(100)在分析折半查找的性能时常常加入失败节点,即外节点,从而形成扩充的二叉树。若设失败节点i所在层次为Li,那么查找失败到达失败点时所做的数据比较次数是()。

A) Li+1 B) Li+2 C) Li-1 D) Li

(101)向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变,平均要移动()个元素。

A) 8 B) 63.5 C) 63 D) 7

(102)由同一组关键字集合构造的各棵二叉排序树( )。

A) 其形态不一定相同,但平均查找长度相同

B) 其形态不一定相同,平均查找长度也不一定相同

C) 其形态均相同,但平均查找长度不一定相同

D) 其形态均相同,平均查找长度也都相同

(103)衡量查找算法效率的主要标准是()。

A) 元素的个数B) 所需的存储量C) 平均查找长度D) 算法难易程度(104)适合对动态查找表进行高效率查找的组织结构是()。

A) 有序表B) 分块有序表C) 二叉排序树D) 快速排序

(3)能进行二分查找的线性表,必须以()。

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的一趟希尔排序的结果为( )。

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

则采用的方法是()。

A) 直接选择排序B) 希尔排序C) 堆排序D) 快速排序

(108)一组记录的排序码为(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 (109)快速排序在最坏情况下的时间复杂度是()

A) O(n2log2n) B) O(n2) C) O(nlog2n) D) O(log2n)

(110)下列排序算法中不稳定的是()。

A) 直接选择排序B) 折半插入排序C) 冒泡排序D) 快速排序

(111)对待排序的元素序列进行划分,将其分为左、右两个子序列,再对两个子序列进行同样的排序操作,直到子序列为空或只剩下一个元素为止。这样的排序方法是()。

A) 直接选择排序B) 直接插入排序C) 快速排序D) 冒泡排序

(112)将5个不同的数据进行排序,至多需要比较()次。

A) 8 B) 9 C) 10 D) 25

(113)排序算法中,第一趟排序后,任一元素都不能确定其最终位置的算法是()。

A)选择排序B)快速排序C)冒泡排序D)插入排序

(114)排序算法中,不稳定的排序是()。

A)直接插入排序B)冒泡排序C)堆排序D)选择排序

(115)排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为().

A) 希尔排序B) 冒泡排序C) 插入排序D) 选择排序

(116)从未排序序列中挑选元素,并将其依次插入已排序序列(初始时为空)的一端的方法,称为()。

A) 希尔排序B) 归并排序C) 插入排序D) 选择排序

(117)对n个不同的排序码进行冒泡排序,在下列哪种情况下比较的次数最多。()

A) 从小到大排列好的B) 从大到小排列好的

C) 元素无序D) 元素基本有序

(118)对n个不同的排序码进行冒泡排序,在元素无序的情况下比较的次数为()。

A) n+1 B) n C) n-1 D) n(n-1)/2

(119)快速排序在下列哪种情况下最易发挥其长处。()

A) 被排序的数据中含有多个相同排序码

B) 被排序的数据已基本有序

C) 被排序的数据完全无序

D) 被排序的数据中的最大值和最小值相差悬殊

(120)对有n个记录的表作快速排序,在最坏情况下,算法的时间复杂度是()。

A) O(n) B) O(n2) C) O(nlog2n) D) O(n3)

(121)若一组记录的排序码为(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

(122)下列关键字序列中,()是堆。

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)堆是一种()排序。

A) 插入B) 选择C) 交换D) 归并

(124)堆的形状是一棵()。

A) 二叉排序树B) 满二叉树C) 完全二叉树D) 平衡二叉树(125)若一组记录的排序码为(46, 79, 56, 38, 40, 84),则利用堆排序的方法建立的初始堆为()。

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)下述几种排序方法中,要求内存最大的是()。

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个单元的循环队列中,队满共有n-1个元素。

(164)队列是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。

(165)循环队列的引入,目的是为了克服_______假溢出。

(166)所谓稀疏矩阵指的是_______非零元很少(t<

(167)在稀疏矩阵表示所对应的三元组线性表中,每个三元组元素按行为主序,列号为辅序的次序排列。

(168)二位数组A m×n按行优先顺序存储在内存中,元素a00地址为loc(a00),每个元素在内存中占d个字节,元素a ij的地址计算公式为loc(a ij)= loc(a00)+(i*n+j)*d 。

(169)去除广义表LS=(a1,a2,a3,……,an)中第1个元素,由其余元素构成的广义表称为LS的____表尾_____。

(170)树内个结点的度最大值称为树的度。

(171)一个二叉树第5层节点最多有16个。

(172)已知完全二叉树T的第5层只有7个结点,则该树共有____11____个叶子结点。

(173)在一棵二叉树中,度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0

=______N2+1。

(174)假设用于通信的电文由8个字母组成,其频率分别为7,19,2,6,32,3,27,10。设计哈夫曼编码,其中字母的编码长度最大是5位。

(175)一棵具有257个结点的完全二叉树,它的深度为。9

(176)图的深度优先遍历序列不是惟一的。

(177)在图中,任何两个结点之间都可能存在关系,因此图的数据元素之间时一种多对多的关系。

(178)在有向图中,以顶点v为终点的边的数目称为v的___入度_____。

(179)一个无向图有n个顶点,e条边,则所以顶点的度数之和为2e。

(180)图有邻接矩阵、邻接表等存储结构,遍历图有

深度优先遍历、广度优先遍历等方法。

(181)

(182)有向图G用邻接表矩阵存储,其第i行的所有非零元素之和等于顶点i的。出度

(183)如果n个顶点的图是一个环,则它有棵生成树。n (以任意一顶点为起点,得到n-1条边)

(184)n个顶点e条边的图,若采用邻接矩阵存储,则空间复杂度为。O(n2)

(185)n个顶点e条边的图,若采用邻接表存储,则空间复杂度为。O(n+e)

(186)设有一稀疏图G,则G采用邻接表存储较省空间。

(187)设有一稠密图G,则G采用邻接矩阵存储较省空间。

(188)图的逆邻接表存储结构只适用于有向图。

(189)已知一个图的邻接矩阵表示,删除所有从第i个顶点出发的方法是将邻接矩阵的第i行全部置0 。

(190)图的深度优先遍历序列不是惟一的。

(191)n个顶点e条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为

O(n2) ;若采用邻接表存储时,该算法的时间复杂度为O(n+e) 。

(192)n个顶点e条边的图采用邻接矩阵存储,广度优先遍历算法的时间复杂度为O(n2);若采用邻接表存储,该算法的时间复杂度为O(n+e) 。

(193)图的BFS生成树的树高比DFS生成树的树高小或相等。

(194)用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为O(n2);用克鲁斯卡尔(Kruskal)算法的时间复杂度是O(elog2e) 。

(195)若要求一个稀疏图G的最小生成树,最好用克鲁斯卡尔(Kruskal) 算法来求解。

(196)若要求一个稠密图G的最小生成树,最好用普里姆(Prim) 算法来求解。

(197)用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度

递增的次序来得到最短路径的。

(198)拓扑排序算法是通过重复选择具有0 个前驱顶点的过程来完成的。

(199)在各种查找方法中,平均查找长度与结点个数n无关的查找方法是

散列查找。

(200)散列法存储的基本思想是由关键字的值决定数据的存储地址。

(201)大多数排序算法都有两个基本的操作:。比较和移动(202)由于查找算法的基本运算是关键字之间的比较操作,所以可用平均查找长度来衡量查找算法的性能。

(203)查找有静态查找和动态查找,当查找不成功时动态查找会将查找关键字插入在表中。

(204)顺序查找法中设置监视哨,可以起到防止越界的作用。

(205)假设列表长度为n,那么查找第i个数据元素时需进行n-i+1次比较。

(206)假设查找每个数据元素的概率相等,即Pi=1/n,则顺序查找算法的平均查找长度为:

ASL=(n+1)/2。

(207)折半查找法又称为二分法查找法,这种方法要求待查找的列表必须是

按关键字大小有序排列的顺序表。

(208)假定将长度为n的表分成b块,且每块含s个元素,则b=n/s。又假定表中每个元素的查找概率相等,

(209)在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为2。

(210)折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,它将依次与表中元素28,6,12,20 比较大小。

(211)在各种查找方法中,平均查找长度与结点个数n无关的查找方法是散列查找。

(212)散列法存储的基本思想是由关键字的值决定数据的存储地址。

(213)当关键字集合很大时,关键字值不同的元素可能会映象到哈希表的同一地址上,即k1≠k2 ,但H(k1)=H(k2),这种现象称为冲突.

(214)产生冲突现象的两个关键字称为该散列函数的____同义词________ 。

(215)在散列函数H(key)=key MOD p 中,p应取素数。

(216)设哈希表长m=14, 哈希函数H(key)=key MOD11.表中已有4个结点;addr(15)=4,

addr(38)=5, addr(61)=6, addr(84)=7, 其余地址为空。如用二次探测再散列处理冲突,关键字为49的结点的地址是。9

(217)希尔排序是属于插入排序的改进方法。

(218)给出一组关键字T=(20,4,34,5,16,33,18,29,2,40,7),要求从下到大进行排序,试给出快速排序(选一个记录为枢纽)第一趟排序结果。7,4,2,85,16,18,20,,29,33,40,34 (219)大多数排序算法都有两个基本的操作:比较和移动。

(220)在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时,当把第7个记录60插入到有序表时,为寻找插入位置至少需比较次。6。

(221)在插入和选择排序中,若初始数据基本正序,则选用插入;若初始数据基本反序,则选用选择。

(222)在堆排序和快速排序中,若初始记录接近正序或反序,则选用堆排序;若初始记录基本无序,则最好选用快速排序。

(223)对于n个记录的集合进行冒泡排序,在最坏的情况下所需要的时间是O(n2) 。若对其进行快速排序,在最坏的情况下所需要的时间是O(n2)

(234)对于n个记录的集合进行归并排序,所需要的平均时间是O(nlog2n),所需要的附加空间是O(n) 。

7.对于n个记录的表进行2路归并排序,整个归并排序需进行┌log2n┐趟(遍)。

8. 设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键码按字母序的升序重新排列,则:

冒泡排序一趟扫描的结果是H C Q P A M S R D F X Y;

初始步长为4的希尔(shell)排序一趟的结果是P A C S Q H F X R D M Y;

二路归并排序一趟扫描的结果是H Q C Y A P M S D R F X;

快速排序一趟扫描的结果是 F H C D P A M Q R S Y X;

堆排序初始建堆的结果是A D C R F Q M S Y P H X。

9. 在堆排序、快速排序和归并排序中,

若只从存储空间考虑,则应首先选取方法,其次选取快速排序方法,最后选取归并排序方法;若只从排序结果的稳定性考虑,则应选取归并排序方法;

若只从平均情况下最快考虑,则应选取堆排序、快速排序和归并排序方法;

若只从最坏情况下最快并且要节省内存考虑,则应选取堆排序方法。

三、程序填空题

(235)以下程序的功能是实现带附加头结点的单链表数据结点逆序连接,请填空完善之。

void reverse(pointer h)

/* h为附加头结点指针;*/

{ pointer p,q;

p=h->next; h->next=NULL;

while((1)________)

{q=p; p=p->next; q->next=h->next; h->next=(2)________; }

}

(1)p!=null ∥链表未到尾就一直作

(2)q ∥将当前结点作为头结点后的第一元素结点插入

(236)下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法,该算法用L返回逆置后的链表的头指针,试在空缺处填入适当的语句。

void reverse(linklist &L){

p=null;q=L;

while(q!=null)

{ (1) ; q->next=p;p=q;(2)___ ; }

(3)_____;

}

(1) L=L->next; ∥暂存后继

(2)q=L; ∥待逆置结点

(3)L=p; ∥头指针仍为L

(237)以下算法的功能是用头插法建立单链表的算法,请填空完善之。

Linklist CreateFromHead( )

{ LinkList L;

Node *s;

char c;

L=(Linklist)malloc(sizeof(Node)); /*为头结点分配存储空间*/

L->next=NULL;

While( ( c=getchar()) !=?*?)

{ s=(Node*)malloc(sizeof(Node)); /*为读入的字符分配存储空间*/ s->data=c;

s->next=L->next ;

L->next=s ;

}

return L;

}

(238)以下算法的功能是尾插法创建链表,请填空完善之。

typedef struct Node /*结点类型定义*/

{ char data;

struct Node * next;

} Node, *LinkList; /* LinkList为结构指针类型*/

Linklist CreateFromTail( ) /*将新增的字符追加到链表的末尾*/ { LinkList L;

Node *r, *s;

char c;

L=(Node * )malloc(sizeof(Node)); /*为头结点分配存储空间*/

L->next=NULL;

r=L; /*r指针指向链表的当前表尾,以便于做尾插入,其初值指向头结点*/

while( ( c=g etchar()) !=?$? ) /*当输入…$?时,建表结束*/

{ s=(Node*)malloc(sizeof(Node)); s->data=c;

;r->next=s; r=s;

}

;r->next=NULL/*将最后一个结点的next链域置为空,表示链表的结束*/

return L;

} /*CreateFromTail*/

(239)下列算法在顺序表L中依次存放着线性表中的元素,在表中查找与e相等的元素,若L.elem[i]=e,则找到该元素,并返回i+1,若找不到,则返回“-1”,请填空完善之。

int Locate(SeqList L,int e)

{ i=0 ; /*i为扫描计数器,初值为0,即从第一个元素开始比较*/ while ((i<=https://www.wendangku.net/doc/f314244867.html,st)&&(L.elem[i]!=e) ) i++;

/*顺序扫描表,直到找到值为key的元素,或扫描到表尾而没找到*/ if ( i<=https://www.wendangku.net/doc/f314244867.html,st) return(i+1); /*若找到值为e的元素,则返回其序号*/

else return(-1); /*若没找到,则返回空序号*/ }

(240)下列算法在顺序表L中第i个数据元素之前插入一个元素e。插入前表长n=L->last+1,i的合法取值范围是1≤i≤L->last+2,请填空完善之。

void InsList(SeqList *L, int i, int e)

{ int k;

if((i<1) || (i>L->last+2)) printf(“插入位置i值不合法”);

if(L->last>=maxsize-1) printf(“表已满无法插入”);

for(k=L->last;k>=i-1;k--) /*为插入元素而移动位置*/

L->elem[k+1]=L->elem[k] ;

L->elem[i-1]=e ; /*在C语言数组中,第i个元素的下标为i-1*/

L->last++ ;

}

(241)下列算法是在顺序表L中删除第i个数据元素,并用指针参数e返回其值。i的合法取值为1≤i≤https://www.wendangku.net/doc/f314244867.html,st+1,请填空完善之。

int DelList(SeqList *L, int i, int *e)

{ int k;

if((i<1)||(i> L->last+1)) printf(“删除位置不合法!”);

数据结构试题及答案(免费)

一、单选题(每题 2 分,共20分) 1. 1.对一个算法的评价,不包括如下(B )方面的内容。 A.健壮性和可读性B.并行性C.正确性D.时空复杂度 2. 2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结 点,则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表,在下列哪种情况下应当采用链表表示?( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种()。 A.有向图B.无向图C.无向无环图D.有向无环图 6. 6.采用开放定址法处理散列表的冲突时,其平均查找长度()。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同D.高于二分查找 7.7.若需要利用形参直接访问实参时,应将形参变量说明为()参数。 A.值B.函数C.指针D.引用 8.8.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具 有相同的()。 A.行号B.列号C.元素值D.非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为()。 A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2) 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题(每题 6 分,共24分) 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N(M:N)的联系时,称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行,删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度 为_________,在表尾插入元素的时间复杂度为____________。

数据结构试题库答案

数据结构试题及答案 一、单项选择题 (1)一个算法应该就是()。 A)程序???B)问题求解步骤得描述 C)要满足五个基本属性??D) A与C (2)算法指得就是()。 A)计算机程序???B)解决问题得计算方法 C)排序算法???D)解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得()。 A) 存储结构B) 逻辑结构C)算法D)操作 (4)从逻辑上可以把数据结构分为( )两大类。 A)动态结构、静态结构??B) 顺序结构、链式结构 C)线性结构、非线性结构???D)初等结构、构造型结构 (5)下列叙述中正确得就是()。 A)一个逻辑数据结构只能有一种存储结构 B)数据得逻辑结构属于线性结构,存储结构属于非线性结构 C)一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D)一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是() ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为() i=0;s=0; while(s

《数据结构》题库及答案

《数据结构》题库及答案 一、选择题 1.线性表的顺序存储结构是一种 的存储结构,线性表的链式存储结构是一种 的存储结构。 a. 随机存储; b.顺序存储; c. 索引存取; d. HASH 存取 2.一个栈的入栈序列是a,b,c,d,e ,则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3.一个队列的入队序列是1,2,3,4,则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4.在一个单链表中,已知p 结点是q 结点的直接前驱结点,若在p 和q 之间插入结点s ,则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5.设有两个串p,q ,求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6.二维数组M 的成员是6个字符(每个字符占一个存储单元)组成的串,行下标i 的范围从0到8,列下标j 的范围从1到10,则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7.在线索二叉树中,结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8.在栈操作中,输入序列为(A ,B ,C ,D ),不可能得到的输出序列为:______ A 、(A , B , C , D ) B 、(D ,C ,B ,A ) C 、(A ,C ,D ,B ) D 、(C ,A ,B ,D ) 9.已知某二叉树的后序序列是dabec ,中序序列是debac ,则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10.设矩阵A 是一个对称矩阵,为了节省存储空间,将其下三角部分(见下图)按行序存放在一维数组B[1..n(n-1)/2]中,对任一上三角部分元素)(j i a ij ,在一维数组B 的存放位置是 。

数据结构试题(含答案)

一.是非题 (正确的打“√”,错误的打“×”。) 1. 数据结构可用三元式表示(D,S,P)。其中:D是数据对象,S是D上的关系, P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5.邻接多重表可以用以表示无向图,也可用以表示有向图。× 6.可从任意有向图中得到关于所有顶点的拓扑次序。× 7.一棵无向连通图的生成树是其极大的连通子图。× 8.二叉排序树的查找长度至多为log2n。× 9.对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10.对于目前所知的排序方法,快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点,而对一般的树,则无此限制,所以,二叉树是树的特殊情形。× 20. 算法的时间复杂性越好,可读性就越差;反之,算法的可读性越好,则时间复杂性就越差。× 二.选择题 1. 若对编号为1,2,3的列车车厢依次通过扳道栈进行调度,不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出(FIFO)特性, ( b )具有先进后出(FILO)特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’)

数据结构试题及答案(10套最新)

单选题(每题2分,共20分) 1. 1. 对一个算法的评价,不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中,要向表头插入一个由指针 p 指向 的结点,则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时,其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分,共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时,称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行,删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时,假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表,在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3, 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时,其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时,应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点 9. .0(n 2) (C )。 2 )

数据结构考试题库含答案

数据结构习题集含答案 目录

选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的(A ) A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是(D ) A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录,其中数据结构考了90分,那 么下面关于数据对象、数据元素、数据项描述正确的是(C ) A、某班级的学生成绩表是数据元素,90分是数据项 B、某班级的学生成绩表是数据对象,90分是数据元素 C、某班级的学生成绩表是数据对象,90分是数据项 D、某班级的学生成绩表是数据元素,90分是数据元素 4.*数据结构是指(A )。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时,物理地址与逻辑地址不相同,称之为(C )。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是(C ) A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性

7.算法分析的主要方法(A )。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是(B ) A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式,在存储空间使用的灵活性上,链式存储 比顺序存储要(B )。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于( C ) A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构,又研究物理结构,这种观点(B )。 A、正确 B、错误 C、前半句对,后半句错 D、前半句错,后半句对 12.在数据结构中,从逻辑上可以把数据结构分成( C ) A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构,线性表的链式存储结构是一种( A ) 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是(A ) for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0;

数据结构习题与答案

第 1 章绪论 课后习题讲解 1. 填空 ⑴()是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵()是数据的最小单位,()是讨论数据结构时涉及的最小数据单位。 【解答】数据项,数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲,数据结构主要分为()、()、()和()。 【解答】集合,线性结构,树结构,图结构 ⑷数据的存储结构主要有()和()两种基本方法,不论哪种存储结构,都要存储两方面的内容:()和()。 【解答】顺序存储结构,链接存储结构,数据元素,数据元素之间的关系 ⑸算法具有五个特性,分别是()、()、()、()、()。 【解答】有零个或多个输入,有一个或多个输出,有穷性,确定性,可行性 ⑹算法的描述方法通常有()、()、()和()四种,其中,()被称为算法语言。 【解答】自然语言,程序设计语言,流程图,伪代码,伪代码 ⑺在一般情况下,一个算法的时间复杂度是()的函数。 【解答】问题规模 ⑻设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为(),若为n*log25n,则表示成数量级的形式为()。 【解答】Ο(1),Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由()表示的,链接存储结构中的数据元素之间的逻辑关系是由()表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C,D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素,其逻辑关系由存储位置(即元素在数组中的下标)表示;链接存储结构中一个数据元素对应链表中的一个结点,元素之间的逻辑关系由结点中的指针表示。

算法与数据结构题库与答案

一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ,表明该算法()。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述,不正确的是()。 A数据结构相同,对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来,起泡排序属于()。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是()。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4,则该队列可能的输出序列是()。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按()方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n( n≥ 0)个字符的有限()。其中,n是字符串的长度,表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中,每个数组元素占用 3 个存储单元,从首地址SA 开始按行连续存放。在这种情况下,元素A[8][5]的起始地址为()。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h)),则它的长度是()。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图,其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A.动态结构、静态结构B.顺序结构、链式结构 C.线性结构、非线性结构D.初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为()。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时,在等概率情况下,搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点(由p 所指向)满足()。 A p->link==NULL; B P==NULL;

数据结构试题及答案

第一章概论 一、选择题 1、研究数据结构就是研究(D)。 A. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D.数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中,计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是(A)。 A.空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D.数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。(线性结构就是:在非空有限集合中,存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素,集合中每一个元素均只有一个前驱,除了最后一个元素有唯一后继)(链表、栈、队列、数组、串) A. 图B. 树??C.广义表(线性表的推广) D.栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A.可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 for(i=0;i

数据结构试题库与答案

数据结构试题库及答案 第一章 概论 一、选择题 1 、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2 、算法分析的两个主要方面是( A )。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3 、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4 、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、 ( B )等 5 个 特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D.易读性、稳定性和确定性 5 、下面程序段的时间复杂度是( C )。 for(i=0;i

数据结构试题及答案

一、判断题: 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算:插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构,数据在计算机中的存储方式和数据的运算三个 方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。() 8、线性的数据结构可以顺序存储,也可以链接存储。非线性的数据结构只能链接存储。() 9、栈和队列逻辑上都是线性表。() 10、单链表从任何一个结点出发,都能访问到所有结点() 11、删除二叉排序树中一个结点,再重新插入上去,一定能得到原来的二叉排序树。() 12、快速排序是排序算法中最快的一种。() 13、多维数组是向量的推广。() 14、一般树和二叉树的结点数目都可以为0。() 15、直接选择排序是一种不稳定的排序方法。() 16、98、对一个堆按层次遍历,不一定能得到一个有序序列。() 17、在只有度为0和度为k的结点的k叉树中,设度为0的结点有n0个,度为k的结点有nk个,则有n0=nk+1。() 18、折半搜索只适用与有序表,包括有序的顺序表和有序的链表。() 19、堆栈在数据中的存储原则是先进先出。() 20、队列在数据中的存储原则是后进先出。() 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。() 22、哈夫曼树一定是满二叉树。() 23、程序是用计算机语言表述的算法。() 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。() 25、用一组地址连续的存储单元存放的元素一定构成线性表。() 26、堆栈、队列和数组的逻辑结构都是线性表结构。() 27、给定一组权值,可以唯一构造出一棵哈夫曼树。() 28、只有在初始数据为逆序时,冒泡排序所执行的比较次数最多。()

数据结构考试试题库含答案解析

数据结构习题集含答案 目录 目录 (1) 选择题 (2) 第一章绪论 (2) 第二章线性表 (4) 第三章栈和队列 (6) 第四章串 (7) 第五章数组和广义表 (8) 第六章树和二叉树 (8) 第七章图 (11) 第八章查找 (13) 第九章排序 (14) 简答题 (19) 第一章绪论 (19) 第二章线性表 (24) 第三章栈和队列 (26) 第四章串 (28) 第五章数组和广义表 (29) 第六章树和二叉树 (31) 第七章图 (36) 第八章查找 (38) 第九章排序 (39) 编程题 (41) 第一章绪论 (41) 第二章线性表 (41) 第三章栈和队列 (52) 第四章串 (52) 第五章数组和广义表 (52) 第六章树和二叉树 (52) 第七章图 (52) 第八章查找 (52) 第九章排序 (57)

选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的?(A ) A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是(D ) A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录,其中数据结构考了90 分,那么下面关于数据对象、数据元素、数据项描述正确的是(C ) A、某班级的学生成绩表是数据元素,90分是数据项 B、某班级的学生成绩表是数据对象,90分是数据元素 C、某班级的学生成绩表是数据对象,90分是数据项 D、某班级的学生成绩表是数据元素,90分是数据元素 4.*数据结构是指(A )。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时,物理地址与逻辑地址不相同,称之为(C )。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是(C ) A、找出数据的合理性 B、研究算法中的输入和输出关系

数据结构试题及答案

好风光好感动1、线性表的逻辑顺序与物理顺序总是一致的。( x ) 2、线性表的顺序存储表示优于链式存储表示。( X ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( v ) 4、二维数组是其数组元素为线性表的线性表。( v ) 5、每种数据结构都应具备三种基本运算:插入、删除和搜索。( x ) 6、数据结构概念包括数据之间的逻辑结构,数据在计算机中的存储方式和数据的运算三个 方面。( v ) 7、线性表中的每个结点最多只有一个前驱和一个后继。(x ) 8、线性的数据结构可以顺序存储,也可以存储。非线性的数据结构只能存储。(x ) 9、栈和队列逻辑上都是线性表。(v ) 10、单链表从任何一个结点出发,都能访问到所有结点(v ) 11、删除二叉排序树中一个结点,再重新插入上去,一定能得到原来的二叉排序树。(x ) 12、快速排序是排序算法中最快的一种。(x ) 13、多维数组是向量的推广。(x) 14、一般树和二叉树的结点数目都可以为0。(v) 15、直接选择排序是一种不稳定的排序方法。(x ) 16、98、对一个堆按层次遍历,不一定能得到一个有序序列。(v ) 17、在只有度为0和度为k的结点的k叉树中,设度为0的结点有n0个,度为k的结点有nk个,则有n0=nk+1。(x ) 18、折半搜索只适用与有序表,包括有序的顺序表和有序的链表。(x ) 19、堆栈在数据中的存储原则是先进先出。(x ) 20、队列在数据中的存储原则是后进先出。(x ) 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。(x ) 22、哈夫曼树一定是满二叉树。(x ) 23、程序是用计算机语言表述的算法。(v) 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。(v ) 25、用一组地址连续的存储单元存放的元素一定构成线性表。(v ) 26、堆栈、队列和数组的逻辑结构都是线性表结构。(v ) 27、给定一组权值,可以唯一构造出一棵哈夫曼树。(x ) 28、只有在初始数据为逆序时,冒泡排序所执行的比较次数最多。(v ) 29、希尔排序在较率上较直接接入排序有较大的改进。但是不稳定的。(v )

数据结构试题及答案.docx

数据结构试题及答案 一、选择题(每小题2分,共20分),每个题的备选答案中,只有一个是正确的,请将答案填写在试题的括号中。 1、对顺序存储的线性表,设其长度为20,在任何位置上插入或删除操作都是 等概率的。插入一个元素时平均要移动表中的( A )个元素。 A.10 B.9 C.11 D.12 2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( D )存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表 3、当利用大小为n的数组顺序存储一个栈时,假定用top==n表示栈空,则向这个栈插入一个元素时,首先应执行( B )语句修改top指针。 A.top++ B.top-- C.top = 0 D.top 4、设入栈顺序为A,B,C,D,E,则出栈序列不可能是( C )。A.EDCBA B.ABCDE C.ADEBC D.ABDEC 5、已知关键字序列(46, 79, 56, 38, 40, 84),采用快速排序(以位于最左位 置的关键字为基准)得到的第一次划分结果为:( A ) A.{ 40, 38, 46, 56, 79, 84 } B.{ 38, 46, 79, 56, 40, 84 } C.{ 38, 46, 56, 79, 40, 84 } D.{ 40, 38, 46, 79, 56, 84 } 6、一个有n个顶点和n条边的无向图一定是( C )。 A.不连通的 B.连通的 C.有环的 D.无环的 7、在一棵具有n个结点的二叉树的第i层上,最多具有( B )个结点。 A.2i B.2i-1 C.2i+1 D.2n 8、对线性表采用折半查找法,该线性表必须( B )。 A.采用顺序存储结构B.采用顺序存储结构,且元素按值有序 C.采用链式存储结构 D.采用链式存储结构,且元素按值有序 9、在一棵具有n个结点的完全二叉树中,分支结点的最大编号为( C )。A.?(n-1)/2? B.?n/2? C.?n/2? D.?n/2? -1 10、在一个无向图中,所有顶点的度数之和等于所有边数的 ( D ) 倍。 A.3 B.1/2 C.1 D.2 二、填空题(每小题2分,共20分),请将正确的结果,填写在试题的横线上。 1、带头结点的循环链表L为空的条件是。 2、序列A={12, 70, 33, 65, 24, 56}给出对应于序列A的大顶堆HA(以线性数 组表示)。 3、每次使两个相邻的有序表合并成一个有序表,这种排序方法叫做________ 排序。 4、设循环队列Q的队头和队尾指针分别为front和rear,队列的最大容量为MaxSize,且规定判断队空的条件为Q.front = = Q.rear,则队列的长度 为。 5、已知数组A[0..11][0..8]按行优先存储,每个元素占有5个存储单元,且 A[0][0]的地址为1000(十进制),则A[6][7]的地址为________________。 6、已知广义表A=(a,(),(b,(c))),则其深度为。 7、在一棵二叉树中,假定度为2的结点个数为5个,度为1的结点个数为6 个,则叶子结点数为__ ____个。

数据结构试卷及答案压缩版

《数据结构》试卷及答案 1.算法分析的目的是( )。 A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2.()是具有相同特性数据元素的集合,是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构 3.用链表表示线性表的优点是( )。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4.输入序列为(A,B,C,D)不可能的输出有()。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D) 5.在数组表示的循环队列中,front、rear分别为队列的头、尾指针,maxSize为数组的最大长度,队满的条件是( )。 A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front 6.设有串t='I am a good student ',那么Substr(t,6,6)=()。 A. student B. a good s C. good D. a good 7.设有一个对称矩阵A,采用压缩存储方式,以行序为主序存储a11为第一个元素,其存储地址为1,每个元素占一个地址空间,则a85地址为()。 A.23 B.33 C.18 D. 40 8.已知广义表LS=(A,(B,C,D),E)运用head和tail函数,取出LS中原子b的运算()。 A. Gethead(Gethead(LS)) B. Gettail(Gethead(LS)) C. Gethead(Gethead(Gettail(LS))) D. Gethead(Gettail(LS)) 9.若已知一棵二叉树先序序列为ABCDEFG,中序序列为CBDAEGF,则其后序序列为( ) A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10.下列存储形式中,( ) 不是树的存储形式。 A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 11.对待排序的元素序列进行划分,将其分为左、右两个子序列,再对两个子序列施加同样的排序操作,直到子序列为空或只剩一个元素为止。这样的排序方法是( )。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12.采用折半查找方法进行查找,数据文件应为(),且限于()。

数据结构习题及答案

第一章 1.在数据结构中,从逻辑上可以把数据结构分为(C ) A.动态结构和静态结构 B. 紧凑结构和非紧凑结构 C.线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O(mn)_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是(A) A 可以随机访问任一结点(顺序) B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为(A ),带头结点的单链表head为空的判定条件为(B ) A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中,读取元素花费时间最少的是(D) A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表,宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点,并保持链表元素仍然有序, 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上,设有头和尾两个指针,执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比,双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针,则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针,则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续,这句话正确吗? (不正确) 11. 某线性表采用顺序存储结构,元素长度为4,首地址为100,则下标为12的(第13个)元素的存储地址为148。V 100+4*12=148 11.在顺序表的(最后一个结点之后)插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除,则该线性表宜采用(顺序)存储结构,若频繁地对线性表进行插入和删除操作,则该线性表宜采用( 链 )存储结构。

(完整版)数据结构期末考试试题及答案

数据结构期末考试试题及答案 期末样卷参考答案 一.是非题(每题1分共10分) 1. 线性表的链式存储结构优于顺序存储结构。F 2. 栈和队列也是线性表。如果需要,可对它们中的任一元素进行操作。F 3.字符串是数据对象特定的线性表。T 4.在单链表P指针所指结点之后插入S结点的操作是:P->next= S ; S-> next = P->next; F 5.一个无向图的连通分量是其极大的连通子图。T 6.邻接表可以表示有向图,也可以表示无向图。T 7.假设B是一棵树,B′是对应的二叉树。则B的后根遍历相当于B′的中序遍历。T 8.通常,二叉树的第i层上有2i-1个结点。F 9.对于一棵m阶的B-树,树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有ém/2ù个关键字。F 10.对于任何待排序序列来说,快速排序均快于起泡排序。F 二.选择题(每题2分共28分) 1.在下列排序方法中,(c )方法平均时间复杂度为0(nlogn),最坏情况下时间复杂度为0(n2);(d )方法所有情况下时间复杂度均为0(nlogn)。 a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序 2. 在有n个结点的二叉树的二叉链表表示中,空指针数为( b )。 a.不定 b.n+1 c.n d.n-1 3. 下列二叉树中,(a )可用于实现符号不等长高效编码。 a.最优二叉树 b.次优查找树 c.二叉平衡树 d.二叉排序树 4. 下列查找方法中,(a )适用于查找有序单链表。 a.顺序查找 b.二分查找 c.分块查找 d.哈希查找 5. 在顺序表查找中,为避免查找过程中每一步都检测整个表是否查找完毕,可采用( a )方法。 a.设置监视哨 b.链表存贮 c.二分查找 d.快速查找 6. 在下列数据结构中,(c )具有先进先出特性,(b )具有先进后出特性。 a.线性表b.栈c.队列d.广义表 7.具有m个结点的二叉排序树,其最大深度为(f ),最小深度为( b )。 a. log 2 m b. └log2 m ┘+1 c. m/2 d .┌m/2 ┐-1 e. ┌m/2 ┐ f. m 8.已知一组待排序的记录关键字初始排列如下:56,34,58,26,79,52,64,37,28,84,57。 下列选择中( c )是快速排序一趟排序的结果。 ( b )是希尔排序(初始步长为4)一趟排序的结果。( d )是基数排序一趟排序的结果。 ( a )是初始堆(大堆顶)。 a. 84,79,64,37,57,52,58,26,28,34,56。 b. 28,34,57,26,56,52,58,37,79,84,64。 c. 28,34,37,26,52,56,64,79,58,84,57。 d. 52,34,64,84,56,26,37,57,58,28,79。 e. 34,56,26,58,52,64,37,28,79,57,84。 f. 34,56,26,58,52,79,37,64,28,84,57。三.填空题(每题2分共20分) 1.有向图的存储结构有(邻接矩阵)、(邻接表)、(十字链表)等方法。 2.已知某二叉树的先序遍历次序为afbcdeg,中序遍历次序为cedbgfa。 其后序遍历次序为(edcgbfa)。层次遍历次序为(afbcgde)。 3.设有二维数组A 5 x 7 ,每一元素用相邻的4个字节存储,存储器按字节编址。已知A00的存储地址为100。则按行存储时,元素A14的第一个字节的地址是(144);按列存储时,元素A14的第一个字节的地址是(184)。 4.请在下划线上填入适当的语句,完成以下法算。Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)){ //先序非递归遍历二叉树。 Initstack ( S ); Push ( S,T ); While ( !stackempty( S ) ) { While ( gettop( S, p )&& p ) { visit (p->data ) ; push(S, p->lchild ;} Pop ( S , p ); If ( !stackempty(s) ) { pop(S, p) ; push( S, p->rchild ); } } return ok; 四.简答题(每题5分共25分) 1.将图示森林转换为二叉树,并对该二叉树中序全序线索化。 2.已知Hash函数为H(K)=K mod 13 ,散列地址为0 --14, 用二次探测再散列处理冲突,给出关键字(23,34,56,24,75,12,49, 52,36,92,06,55)在散列 地址的分布。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

相关文档
相关文档 最新文档