文档介绍：该【数据结构试题及 】是由【春天资料屋】上传分享，文档一共【20】页，该文档可以免费在线阅读，需要了解更多关于【数据结构试题及 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。一、判断题:
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、只有在初始数据为逆序时,冒泡排序所执行的比较次数最多。()
29、希尔排序在较率上较直接接入排序有较大的改进。可是不牢固的。()
30、在平均情况下,快速排序法最快,齐集排序法最节约空间。()
31、快速排序法是一种牢固性排序法。()
32、算法必定要有输入和输出。()
33、算法剖析的目的旨在剖析算法的效率以求改进算法。()
34、非空线性表中随意一个数据元素都有且仅有一个直接后继元素。()
35、数据的积蓄构造不仅有次序积蓄构造和链式积蓄构造,还有索引构造与散列构造。()
36、若频频地对线性表进行插入和删除操作,该线性表采用次序积蓄构造更合适。()
37、若线性表采用次序积蓄构造,每个数据元素占用
4个积蓄单元,第
12个数据元素的积蓄地址为
144,则第
1个
数据元素的积蓄地址是101。(
)
38、若长度为n的线性表采用次序积蓄构造,删除表的第
i个元素从前需要搬动表中
n-i+1个元素。(
)
39、符号p->next出现在表达式中表示p所指的那个结点的内容。(
)
40、要将指针p移到它所指的结点的下一个结点是执行语句
p←p->next。(
)
41、若某货仓的输入序列为1,2,3,4
,则4,3,1,2
不能够能是货仓的输出序列之一。
(
)
42、线性链表中各个链结点之间的地址不用然要连续。
(
)
43、程序就是算法,但算法不用然是程序。(
)
44、线性表只能采用次序积蓄构造也许链式积蓄构造。
(
)
45、线性表的链式积蓄构造是经过指针来间接反响数据元素之间逻辑关系的。
(
)
46、除插入和删除操作外,数组的主要操作还有存取、更正、检索和排序等。
(
)
47、稀有矩阵中0元素的分布有规律,因此能够采用三元组方法进行压缩积蓄。
(
)
48、无论货仓采用何种积蓄构造,只要货仓不空,能够随意删除一个元素。
(
)
49、确定串T在串S中首次出现的地址的操作称为串的模式般配。
(
)
50、深度为h的非空二叉树的第i层最多有2i-1
个结点。(
)
51、满二叉树也是圆满二叉树。(
)
52、已知一棵二叉树的前序序列和后序序列能够唯一地构造出该二叉树。
(
)
53、非空二叉排序树的随意一棵子树也是二叉排序树。
(
)
54、对一棵二叉排序树进行前序遍历必定能够获取一个按值有序的序列。
(
)
55、一个广义表的深度是指该广义表张开后所含括号的层数。
(
)
56、散列表的查找效率主要取决于所选择的散列函数与办理矛盾的方法。
(
)
57、序列初始为逆序时,冒泡排序法所进行的元素之间的比较次数最多。
(
)
58、已知指针P指向键表L中的某结点,执行语句
P=P-〉next
不会删除该链表中的结点。
(
)
59、在链队列中,即使不设置尾指针也能进行入队操作。
(
)
60、若是一个串中的全部字符均在另一串中出现,则说前者是后者的子串。
(
)
61、设与一棵树T所对应的二叉树为
BT,则与T中的叶子结点所对应的
BT中的结点也必定是叶子结点。(
)
62、若图G的最小生成树不唯一,则G的边数必定多于
n-1,并且权值最小的边有多条(其中n为G的极点数)。(
)
63、给出不一样样的输入序列建筑二叉排序树,必定获取不一样样的二叉排序树。
(
)
64、由于希尔排序的最后一趟与直接插入排序过程相同,所从前者必定比后者开销的时间多。
(
)
65、程序越短,程序运行的时间就越少。
(
)
66、采用循环链表作为积蓄构造的队列就是循环队列。
(
)
67、货仓是一种插入和删除操作在表的一端进行的线性表。
(
)
68、一个随意串是其自己的子串。
(
)
69、哈夫曼树必定是圆满二叉树。
(
)
70、带权连通图中某一极点到图中另必定点的最短路径不用然唯一。
(
)
71、折半查找方法能够用于按值有序的线性链表的查找。
(
)
72、稀有矩阵压缩积蓄后,必会无效掉随机存取功能。(
)
73、由一棵二叉树的前序序列和后序序列能够唯一确定它。
(
)
74、在n个结点的元向图中,若边数在于n-1,则该图必是连通图。(
)
75、在圆满二叉树中,若某结点元左孩子
,则它必是叶结点。(
)
76、若一个有向图的毗邻矩阵中
,对角线以下元素均为
0,则该图的拓扑有序序列必定存在。
(
)
77、树的带权路径长度最小的二叉树中必定没有度为
1的结点。(
)
78、二叉树能够用0≤度≤2的有序树来表示。(
)
79、一组权值,能够唯一构造出一棵哈夫曼树。
( )
80、101,88,46,70,34,39,45,58,66,10)是堆;(
)
81、将一棵树变换成二叉树后,根结点没有左子树;
(
)
82、用树的前序遍历和中序遍历能够导出树的后序遍历;
(
)
83、在非空线性链表中由p所指的结点后边插入一个由q所指的结点的过程是依次执行语句:
q->next=p->next;p->next=q。()
84、非空双向循环链表中由q所指的结点后边插入一个由p指的结点的动作依次为:p->prior=q,
p->next=q->next,q->next=p,q->prior->next
←p。(
)
85、删除非空链式积蓄构造的货仓
(设栈顶指针为
top)
的一个元素的过程是依次执行
:p=top,top=
p->next,free
(p)。
( )
86、哈希的查找无需进行要点字的比较。
(
)
87、一个好的哈希函数应使函数值平均的分布在积蓄空间的有效地址范围内,以尽可能减少矛盾。()
88、排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的随意序列,重新排列成一
个按要点字有序的序列。()
89、队列是一种能够在表头和表尾都能进行插入和删除操作的线性表。()
90、在索引次序表上实现分块查找,在等概率查找情况下,其平均查找长度不与表的个数有关,而与每一块中的元
素个数有关。()
91、关于有向图,极点的度分为入度和出度,入度是以该极点为终点的入边数目;出度是以该极点为起点的出边数
目,该极点的度等于其入度和出度之和。()
92、无向图的毗邻矩阵是对称的有向图的毗邻矩阵是不对称的。()
93、拥有n个极点的连通图的生成树拥有n-1条边()
二、填空题:
1、《数据构造》课程议论的主要内容是数据的逻辑构造、积蓄构造和
______________。
2、数据构造算法中,平时用时间复杂度和
__________________两种方法衡量其效率。
3、一个算法一该拥有______,______,____,______
和____这五种特点。
4、若频频地对线性表进行插入与删除操作,该线性表应采用
____________积蓄构造。
5、在非空线性表中除第一个元素外,会集中每个数据元素只有一个
_______;除最后一个元素之外,会集中每个数
据元素均只有一个_________。
6、线性表中的每个结点最多有
________前驱和____________后继。
7、______链表从任何一个结点出发,都能接见到全部结点。
8、链式积蓄构造中的结点包括
____________域,_______________域。
9、在双向链表中,每个结点含有两个指针域,一个指向
______结点,另一个指向________结点。
10、某带头结点的单链表的头指针
head,判断该单链表非空的条件
______________。
11、在双向链表中,每个结点含有两个指针域,一个指向
_______结点,另一个指向_____结点。
12、已知指针p指向单链表中某个结点,则语句
p->next=p->next->next
的作用__删除p的后继结点_。
13、已知在结点个数大于1的单链表中,指针p指向某个结点,则以下程序段结束时,指针q指向*p的_____________
结点。
q=p;
while(q->next!=p)
q=q->next;
14、若要在单链表结点*P后插入一结点*S,执行的语句_______________。
15、线性表的链式积蓄构造地址空间能够
_________,而向量积蓄必定是地址空间___________。
16、栈构造同意进行删除操作的一端为_____________。
17、在栈的次序实现中,栈顶指针
top,栈为空条件______________。
18、关于单链表形式的队列,其空队列的
F指针和R指针都等于__________________。
19、若数组s[0..n-1]为两个栈
s1
和s2
的共用积蓄空间,仅当
s[0..n-1]全满时,各栈才不能够进行栈操作,则为这
两个栈分配空间的最正确方案是:
s1
和s2
的栈顶指针的初值分别为
_________。
20、同意在线性表的一端插入
,另一端进行删除操作的线性表称为
_______。插入的一端为
______,删除的一端为
______。
21、设数组
A[m]为循环队列
Q的储藏空间,font
为头指针,rear
为尾指针,判断
Q为空队列的条件
____________________。
22、关于次序积蓄的队列,积蓄空间大小为
n,头指针为
F,尾指针为
R。若在逻辑上看一个环,则队列中元素的个
数为___________。
23、已知循环队列的积蓄空间为数组
data[21]
,且头指针和尾指针分别为
8和
3,则该队列的当前长度
__________。
24、一个串的随意个连续的字符组成的子序列称为该串的
________,包括该子串的串称为
________。
25、求串
T在主串
S中首次出现的地址的操作是
________________。
26、在初始为空的队列中插入元素
A,B,C,D
今后,紧接着作了两次删除操作,此时的队尾元素是
__________。
27、在长度为
n的循环队列中,删除其节点为
x的时间复杂度为
_______________。
28、已知广义表
L为空,其深度为
___________。
29、已知一次序积蓄的线性表,每个结点占用
k个单元,若第一个结点的地址为
DA1,则第
i
个结点的地址为
______________。
30、设一行优先次序积蓄的数组
A[5][6]
,A[0][0]
的地址为
1100,且每个元素占
2个积蓄单元,则
A[2][3]
的地址
_____________。
31、设有二维数组A[9][19],其每个元素占两个字节,第一个元素的积蓄地址为100,若按行优先次序积蓄,则元
A[6,6]的积蓄地址为______________,按列优次序积蓄,元素A[6,6]的积蓄地址为______________。
32、在进行直接插入排序时
,其数据比较次数与数据的初始排列
________关;而在进行直接选择排序时,其数据比
较次数与数据的初始排列
__________关。
33、假设以行为优先积蓄的三维数组
A[5][6][7]
,A[0][0][0]的地址为1100,每个元素占两个积蓄单元,则A[4][3][2]
的地址为_______。
34、设二维数组A[m][n]按列优先积蓄,每个元素占
1个积蓄单元,元素A00的积蓄地址loc(A00),则Aij的积蓄地址
loc(Aij)=____________________。
35、稀有矩阵一般采用__________方法进行压缩积蓄。
36、稀有矩阵可用_________进行压缩积蓄,积蓄时需积蓄非零元的
________、________、________。
37、若矩阵中全部非零元素都集中在以主对角线为中心的带状地域中,地域外的值全为
0,则称为__________。
38、若一个n阶矩阵A中的元素满足:Aij=Aji
(0<=I,j<=n-1)则称A为____________矩阵;若主对角线上方(或下方)
的全部元素均为零时,称该矩阵为______________。
39、关于上三角形和下三角形矩阵,分别以按行积蓄和按列积蓄原则进行压缩积蓄到数组
M[k]中,若矩阵中非0元
素为Aij,则k对应为________和__________。
40、设有一上三角形矩阵
A[5][5]
按行压缩积蓄到数组
B中,B[0]的地址为100,每个元素占2个单元,则A[3][2]
地址为____________。
41、广义表(A,(a,b),d,e,((i,j),k)
),则广义表的长度为___________,深度为___________。
42、已知广义表A=((a,b,c),(d,e,f)),
则运算head(head(tail
(A))))=___________。
43、已知广义表ls=(a,(b,c,d),e),
运用head和tail函数取出ls中的原子b的运算是_____。
44、在树构造里,有且仅有一个结点没有前驱,称为根。非根结点有且仅有一个
___________,且存在一条从根到该
结点的_______________。
45、度数为0的结点,即没有子树的结点叫作__________结点或_________结点。同一个结点的儿子结点之间互称为
___________结点。
46、假设一棵树的广义表为A(B(e),C(F(h,i,j),g),D),则该树的度为___________,树的深度为_________,终端结
点为______,单分支结点为,双分支结点个数为_______,三分支结点为_______,C结点的双亲结点是______,孩
子结点是______。
、圆满二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中,与数据的积蓄构造有关系的是
_____________。
47、有三个结点的二叉树,最多有
________种形状。
48、每一趟排序时从排好序的元素中挑出一个值最小的元素与这些未排小序的元素的第一个元素交换地址,这种排
序方法成为_____________排序法。
49、高度为k的二叉树拥有的结点数目,最少为
_____,最多为_____。
50、对任何一棵二叉树,若
n0,n1,n2分别是度为
0,1,2的结点的个数,则n0=_______。
51、在含100个结点的圆满二叉树,叶子结点的个数为
_______。
52、将一个数据元素(或记录)的随意序列,重新排列成一个按要点字有序的序列叫
_____。
53、若一棵满二叉树含有
121个结点,则该树的深度为_________。
54、一个拥有767个结点的圆满二叉树,其叶子结点个数为________。
55、深度为90的满二叉树,第11
层有________个结点。
56、有100个结点的圆满二叉树,深度为
________。
57、设一棵二叉树中度为
2的结点10个,则该树的叶子个数为________。
58、若待散列的序列为(18,25,63,50,42,32,9)
,散列函数为H(key)=keyMOD9,与18发生矛盾的元素有_____________
个。
59、含有3个2度结点和
4个叶结点的二叉树可含__________个1度结点。
60、一棵拥有5层满二叉树中节点总数为
___________。
61、一棵含有16个结点的圆满二叉树,对他按层编号,关于编号为
7的结点,他的双亲结点及左右结点编号为
______、
______、_______。
62、深度为k(设根的层数为1)的圆满二叉树最稀有
_______个结点,至多有_______个结点。
63、若要对某二叉排序树进行遍历,保证输出全部结点的值序列按增序排列,对付该二叉排序树采用
________遍历
法。
64、在序列(2,5,8,11,15,16,22,24,27,35,50)
中采用折半查找(二分查找)方法查找元素
24,需要进行
______________次元素之间的比较。
65、设有10个值,组成哈夫曼树,则该哈夫曼树共有
______个结点。
66、从树中一个结点到另一个结点之间的分支组成这两个结点之间的
____________。
67、要点字自己作为哈希函数,即
H(k)=k,也可自己加上一个常数作为哈希函数,即
H(k)=k+C这种构造哈希函数
的方式叫____________。
68、关于一个图G,若边会集E(G)为无向边的会集,则称该图为
____________。
69、关于一个图G,若边会集E(G)为有向边的会集,则称该图为
____________。
70、关于有向图,极点的度分为入度和出度,以该极点为终点的边数目叫
________;以该极点为起点的边数目叫
_________。
71、一个无向图采用毗邻矩阵积蓄方法,其毗邻矩阵必定是一个
______________。
72、有一个n个极点的有向圆满图的弧数
_____________。
73、在无向图中,若从极点
A到极点B存在_________,则称A与B之间是连通的。
74、在一个无向图中,全部极点的度数之和等于全部边数的
___________倍。
75、一个连通图的生成树是该图的
____________连通子图。若这个连通图有
n个极点,则它的生成树有__________
条边。
76、无向图的毗邻矩阵是一个
_____________矩阵。
77、若是从一无向图的随意极点出发进行一次深度优先找寻即可接见全部极点,则该图必定是
____________。
78、若采用毗邻表的积蓄构造,则图的广度优先找寻近似于二叉树的
____________遍历。
79、若图的毗邻矩阵是对称矩阵,则该图必定是
________________。
80、从以以下列图的临接矩阵能够看出,该图共有
______个极点。若是是有向图,该图共有
______条弧;若是是无向
图,则共有________条边。
A
B
C
81、若是从一个极点出发又回到该极点,则此路径叫做___________。
0
1
1
A
82、一个拥有个n极点的无向图中,要连通全部极点最少需要
________条边。
B0
0
1
B
83、给定序列{100,86,48,73,35,39,42,57,66,21},
按堆构造的定义,则它必定
0
1
0
C
_________堆。
84、从未排序序列中选择一个元素,该元素将当前参加排序的那些元素分成前后两个部分,前一部分中全部元素都
小于等于所选元素,后一部分中全部元素都大于或等于所选元素,而此时所选元素处在排序的最后地址。这种排序
法称为_____________排序法。
85、折半找寻只适适用于___________________。
86、结点要点字变换为该结点积蓄单元地址的函数
H称为_____________或叫__________。
87、在索引查找中,第一查找
________,今后查找相应的_________,整个索引查找的平均查找长度等于查找索引表
的平均长度与查找相应子表的平均查找长度的
_______。
三、选择题:
(
)
及它们之间的联系。
A积蓄和逻辑构造
B积蓄和抽象
C理想和抽象
D理想与逻辑
(
)
。
A先进先出
B后进先出
C先进后出
D随意进出
(
),从左到右依次对结点进行编号,根结点的编号为
1,则编号
为49的结点的左孩子的编号为______。
( ),正确的遍历序列应为( )
(),用折半查找法进行查找时,最大比较次数是_____。
()。
(
)
______。
A减少存取时间,降低下溢发生的机率
B节约积蓄空间,降低上溢发生的机率
C减少存取时间,降低上溢发生的机率
D节约积蓄空间,降低下溢发生的机率
(
),则该二叉树必定是
_____的二叉树
A空也许只有一个结点
B高度等于其结点数
C任一结点无左孩子
D任一结点无右孩子
(
)9.
设散列表长m=14,散列函数H(K)=K%11,已知表中已有
4个结点:r(15)=4;r(38)=5;r(61)=6;r(84)=7
,
其他地址为空,如用二次探测再散列办理矛盾,要点字为
49的结点地址是________。
A8
B3
C5
D9
(
)10.
在含有n个项点有e条边的无向图的毗邻矩阵中,零元素的个数为________。
()
_______。
()
n的链队列用单循环链表表示,若只设头指针,则入队操作的时间复杂度为
_______。
(1)
(log2n)
(n)
(n2)
()
_______。
B.
满二叉树
D.
平衡二叉树
()
_______。
()
10000个元素,若只想获取其中前
10个最小元素,最好采用
_______方法
(
)
typedefstructnode{
ElemTypedata;
structnode*Link
;
}ListNode;
已知指针p所指结点不是尾结点,若在*p今后插入结点*s,则应执行以下哪一个操作
______。
->link=p
;p->link=s
;->link=p->link
;p->link=s
;
->link=p->link
;p=s
;->link=s
;s->link=p
;
(
)
typedefstructnode
{data;node*Link
;ListNode
;
非空的循环单链表
first
的尾结点(由p所指向)满足:______
->link==NULL
;
==NULL
;
->link==first
;
==first
;
(
)、积蓄和加工办理的对象被统称为
_________
B.
数据元素
D.
数据种类
(
)
________
(1)
(n)
(nlogn)
(n2)
(
)
________
B.
积蓄构造不一样样
D.
限制插入和删除的地址不一样样
(
),比较明显的长处是
________
B.
删除操作更加方便
D.
不会出现上溢的情况
(
)[0n-1]=”xwxxyxy”中,对模式串p[0m-1]=”xy”进行子串定位操作的结果_______
().(A,(B,C))
A,表尾为(B,C)
B.(A,B,C)
,则此广义表为
________
C.(A,B,C)
D.((A,B,C))
(
),其中每个元素占
1个积蓄单元。若
A[1][1]的积蓄地址为
420,A[3][3]
的存
储地址为
446,则A[5][5]的积蓄地址为_______
(
)
5层上的结点个数最多为________
(
),则此图是
_______
(
),平均情况下的空间复杂度为
_______
(1)
(logn)
(n)
(nlogn)
(
)
H(key)=key%13,被称为同义词的要点字是_______
和39
和44
和51
(
)
3,8,6,2,5
的叶子结点生成一棵哈夫曼树,它的带权路径长度为
A、24
B
、48
C、72
D
、53
(
),平均检索长度________
A、为o(log2N)
B
、为o(N)
__