数据结构导论练习题.docx
《数据结构导论练习题.docx》由会员分享，可在线阅读，更多相关《数据结构导论练习题.docx（13页珍藏版）》请在冰点文库上搜索。
数据结构导论练习题
一、选择题
1.在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行。
A．q一）next＝p一）next；p一）next＝q；
B．p一）next＝q一）next；q＝p；
C．q一）next＝p一）next；p一）next＝q；
D．p一）next＝q一）next；q一）next＝p；
2.在一个顺序队列中，队首指针指向队首元素的位置：
A．前一个B．后一个C．当前
3.下列数据组织形式中，（ ）的结点按逻辑关系依次排列形成一个“锁链”。
A.集合 B.树形结构C.线性结构 D.图状结构
4.数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（ ）
A.S上的算法 B.S的存储结构C.在S上的一个基本运算集
D.在S上的所有数据元素
5.下列说法正确的是（ ）
A.线性表的逻辑顺序与存储顺序总是一致的
B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续
C.线性表的线性存储结构优于链式存储结构
D.每种数据结构都具有插入、删除和查找三种基本运算
6.设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i个结点，下列算法段能正确完成上述要求的是（ ）
A.s->next=p->next;p->next=s；B.p->next=s;s->next=p->next；
C.s->next=p->next;p->next=s;交换p->data和s->data；D.p=s;s->next=p；
7.将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点（ ）
A.无左、右孩子 B.有左孩子，无右孩子C.有右孩子，无左孩子
D.有左、右孩子
8.采用线性探测法解决冲突问题，所产生的一系列后继散列地址（ ）
A.必须大于等于原散列地址B.必须小于等于原散列地址
C.可以大于或小于但不能等于原散列地址D.地址大小没有具体限制
9.用快速排序方法对包含有n个关键字的序列进行排序，最坏情况下执行的时间复杂度为（ ）
A.O（n） B.O（log2n）C.O（nlog2n） D.O（n2）
10.下列数据结构中，（ ）不都是线性结构。
A.栈和队列 B.队列和数组C.数组和串 D.文件和队列
11.为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用（ ）方式。
A.顺序存储 B.链式存储C.索引存储 D.散列存储
12.具有100个结点的完全二叉树的深度为（ ）
A.6 B.7 C.8 D.9
13.顺序查找法与二分查找法对存储结构的要求是（ ）
A.顺序查找与二分查找均只适用于顺序表
B.顺序查找与二分查找既适用于顺序表，也适用于链表
C.顺序查找只适用于顺序表
D.二分查找只适用于顺序表
14.在开散列表上，每个地址单元所链接的同义词表（ ）
A.其键值相同 B.其元素值相同C.其散列地址相同 D.其含义相同
15.一组记录的关键码为（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
16.下列说法正确的是（ ）
A．数据是数据元素的基本单位B．数据元素是数据项中不可分割的最小标识单位
C．数据可由若干个数据元素构成D．数据项可由若干个数据元素构成
17.数据结构的基本任务是（ ）
A．逻辑结构和存储结构的设计 B．数据结构的运算实现
C．数据结构的评价与选择 D．数据结构的设计与实现
18.在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（ ）
A．O
（1） B．O（n）C．O（nlog2n） D．O（n2）
19.顺序存储的线性表（a1,a2,…,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（ ）
A．n B．n/2C．n+1 D．（n+1）/2
20.下列数据组织形式中，（ ）的各个结点可以任意邻接。
A．集合 B．树形结构C．线性结构 D．图状结构
21.在线性表的下列存储结构中，读取元素花费时间最少的是（ ）
A．单链表 B．双链表C．循环链表 D．顺序表
22.除根结点外，树上每个结点（ ）
A．可有任意多个孩子、任意多个双亲B．可有任意多个孩子、一个双亲
C．可有一个孩子、任意多个双亲D．只有一个孩子、一个双亲
23.若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常（ ）
A.对数阶量级复杂性大于线性阶量级B.对数阶量级复杂性小于线性阶量级
C.对数阶量级复杂性等于线性阶量级D.两者之间无法比较
24.下列查找中，效率最高的查找方法是（ ）
A.顺序查找 B.折半查找C.索引顺序查找 D.分块查找
25.直接插入排序算法，其时间复杂性为（ ）
A.O
（1） B.O（n）C.O（nlog2n） D.O（n2）
26.数据的四种基本逻辑结构是指（ ）
A.数组、链表、树、图形结构 B.线性表、链表、栈队列、数组广义表
C.线性结构、链表、树、图形结构 D.集合、线性结构、树、图形结构
27.数据结构中，通常采用两种方法衡量算法的时间复杂性，即（ ）
A.最大时间复杂性和最小时间复杂性 B.最好时间复杂性和最坏时间复杂性
C.部分时间复杂性和总体时间复杂性D.平均时间复杂性和最坏时间复杂性
28.下列关于线性表的叙述中，不正确的是（ ）
A.线性表是n个结点的有穷序列B.线性表可以为空表
C.线性表的每一个结点有且仅有一个前趋和一个后继
D.线性表结点间的逻辑关系是1:
1的联系
29.在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是（ ）
A.p=p->next B.p->next=p->nextC.p->next=p->next->next D.p->next=p
30.栈和队列（ ）
A.共同之处在于二者都是先进先出的特殊的线性表
B.共同之处在于二者都是先进后出的特殊的线性表
C.共同之处在于二者都只允许在顶端执行删除操作
D.没有共同之处
31.要解决散列引起的冲突问题，常采用的方法有（ ）
A.数字分析法、平方取中法 B.数字分析法、线性探测法
C.二次探测法、平方取中法D.二次探测法、链地址法
32.若在长度为n的顺序表中插入一个结点，则其结点的移动次数（ ）
A.最少为0，最多为n B.最少为1，最多为n
C.最少为0，最多为n+1 D.最少为1，最多为n+1
33.在一个单链表中，若p所指结点是q所指结点的前驱结点，则在结点p、q之间插入结点s的正确操作是（ ）
A.s->next=q；p->next=s->nextB.p->next=q；p->next=s
C.s->next=q->next；p->next=sD.s->next=q->next；p->next=s->next
34.若有一串数字5、6、7、8入栈，则其不可能的输出序列为（ ）
A.5、6、7、8 B.8、7、6、5C.8、7、5、6 D.5、6、8、7
35.数据的四种基本存储结构是指（ ）
A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构
B．顺序存储结构、索引存储结构、链式存储结构、散列存储结构
C．顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构
D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构
36.有关栈的描述，正确的是（ ）
A.栈是一种先进先出的特殊的线性表B.只能从栈顶执行插入、删除操作
C.只能从栈顶执行插入、栈底执行删除D.栈顶和栈底均可执行插入、删除操作
37.关于二叉树性质的描述，正确的是（ ）
A.二叉树结点的个数可以为0
B.二叉树至少含有一个根结点
C.二叉树若存在两个结点，则必有一个为根，另一个为左孩子
D.二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子
38.具有4个结点的二叉树可有（ ）
A.4种形态 B.7种形态C.10种形态 D.11种形态
39.下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是（ ）
A.集合 B.线性结构C.树形结构D.图形结构
40.计算机算法指的是（ ）。
A.计算方法 B.排序方法 C.解决某一问题的有限运算序列 D.调度方法
41.循环队列用数组A［0..m-1］存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（ ）。
A.（rear-front+m）MODm B.rear-front+1C.rear-front-1 D.rear-front
42.栈和队列的共同特点是（ ）。
A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素
D.没有共同点
43.深度为n的二叉树中所含叶子结点的个数最多为（ ）个。
A.2n B.n C.2n-1 D.2n-1
44.对线性表进行二分查找时，要求线性表必须（ ）。
A.以顺序方式存储 B.以链接方式存储
C.以顺序方式存储，且结点按关键字有序排序
D.以链接方式存储，且结点按关键字有序排序
――――――――――――――――――――――――――――――――――――
2008-12-5添加
1．下列关于数据结构的叙述中，错误的是（）
A、数据结构是相关数据元素的集合B、数据元素是由若干数据项构成的
C、数据结构就是文件D、数据结构分逻辑结构和物理结构
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．下列关于查找的说法中，正确的是（）
A、只要给定了查找值，就一定能找到一个结点
B、如果给定值是关于查找表主关键字的，就一定能找到一个结点
C、查找表可以是关于关键字的有序表，或无序表
D、查找过程是对结点进行比较和交换的过程
8．栈是一种特殊的（）表，其插入、删除操作在表的同一端进行
A、链表B、顺序表C、线性表D、循环链表
9．判断一个顺序栈是否为空栈的依据是（）
A、栈顶指针＝栈底指针B、栈顶指针<栈底指针C、栈顶指针>栈底指针
D、测试栈的每一个元素是否都是空栈
10．出栈操作的结果是（）
A、取出并返回栈顶元素值B、将栈顶元素清空
C、移动栈顶指针指向下一个元素D、向栈顶方向依次移动一个元素
11．设一个栈存储在一维数组stack[m]中，并设栈底为第m个数组元素，栈顶指针为top。
在执行压栈操作中，首先执行（）
A、top=top+1B、top=top-1C、top=mD、top=m-1
12．对于一个用一维数组存储一个顺序队列的情况，当（）时队列为空
A、队头指针＝队尾指针B、队头指针＝队尾指针＝0
C、队尾指针＝0D、队头指针＝0
13．下列关于子串的的说法中，错误的是（）
A、一个串是自身的子串B、空串是任何串的子串
C、子串的长度一定小于主串的长度D、子串是包含在主串中的串
14．若树的度为3，则（）
A、每个结点都有3个分支B、根结点有3个分支
C、每个结点有不超过3个分支D、树最多有3层
15．已知一棵二叉树的（），就可画出这棵二叉树
A、先根遍历和后根遍历序列B、先根遍历序列C、后根遍历序列
D、先根遍历和中根遍历序列
16．下列关于树的说法中，错误的是（）
A、树的叶子结点没有后继结点B、树的任何一个结点必在一个层子上
C、一棵非空树必有一个根结点，它没有前驱结点，但有多个后继结点
D、一般树都是无序树
17．对一个具有n个顶点和e条边的无向图，若采用邻接表表示，则邻接表中所用结点个数为（）
A、e/2B、eC、2eD、n＋e
18．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍
A、1/2B、1C、2D、4
19．具有5个顶点的无向图至少应有（）条边，才能确保图是一个连通的
A、5B、6C、4D、8
20．存储在散列表中的结点的顺序是（）的
A、时间顺序B、关键字顺序C、随机顺序D、不可预测顺序
21．散列的查找效率与（）有关
A、结点个数B、散列表大小C、散列函数D、散列函数和解决冲突的方法
――――――――――――――――――――――――――――――――――――
二、填空题
1．数据的逻辑结构被分为___________、____________、___________和___________四种。
2．对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度___________为，在表尾插入元素的时间复杂度为____________。
3．在广义表的存储结构中，每个结点均包含有________个域。
4．当用长度为N的数组顺序存储一个栈时，假定角top＝＝N表示栈空，则表示栈满的条件为____________。
5.在一棵二叉树中，第5层上的结点数最多为_________。
6.在线性表的散列存储中，处理冲突有________和________两种方法。
7.快速排序在平均情况下的空间复杂度为_______________，在最坏情况下的空间复杂度为________________。
8.线性表（a0,a1,a2,…,an）（n≥1）中，每个元素占c个存储单元，m为a0的首地址，则按顺序存储方式存储线性表，an的存储地址是________。
9.在栈的顺序实现中，设栈顶指针为top，栈空的条件为_______。
10.队列中允许进行插入的一端称为_______。
11.深度为90的满二叉树上，第11层有_____个结点。
12.通常采用拉链法、线性探测法、多重散列法、二次探测法、公共溢出区法等解决散列地址冲突问题，若要避免“堆积”现象发生应采用____。
13.对有序表（25,30,32,38,47,54,62,68,90,95）用二分查找法查找32，则所需的比较次数为 _______。
14.树型结构结点间通过“父子”关系相互关联，这种相互关联构成了数据间的_____关系。
15.下列程序段的时间复杂性的量级为_________。
for（i=1;i for（j=i;j t=t+1
16.设某非空单链表，其结点形式为 ，若要删除指针q所指结点的直接后继结点，则需执行下列语句序列：
p=q->next;________;free（p）;
17.队列可以看成是一种运算受限制的线性表，也称为______线性表。
18.表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、_______________和散列存储方式。
19.队列中允许进行删除的一端为________________。
20.在顺序存储的线性表（a1,a2…，an）中的第i（1≤i≤n）个元素之前插入一个元素，则需向后移动_____________个元素。
21.在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现：
_____________；sq->data[sq->top]=x；
22.对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有序表中的位置可能是______________。
23.快速排序法在待排序数据_____________的情况下最不利于发挥其长处。
24.从数据结构的观点，数据通常可分为三个层次，即：
数据、数据元素和___________。
25.对顺序表执行插入操作，其插入算法的平均时间复杂性为___________。
26.在具有n个单元、且采用顺序存储的循环队列中，队满时共有___________个元素。
27.若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则循环队列为空的条件是___________。
28.树的遍历主要有先根遍历、后根遍历和___________三种。
29.在最好的情况下，对于具有n个元素的有序序列，若采用冒泡排序，所需的比较次数为___________次。
30.判断带头结点head的单链表为空的条件是___________。
31.若顺序表每个元素长度均为5，其中第一个元素的存储地址为30，则第6个元素的存储地址为___________。
32．若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则判断循环队列为满的条件是___________。
33.若某二叉树的先根遍历序列为CEDBA，中根遍历序列为DEBAC，则其后根遍历序列为___________。
34.图主要采用___________两种存储结构存放。
35.对顺序表执行删除操作，其删除算法的平均时间复杂性为__________。
36.若head表示循环链表的头指针，t表示尾结点，则头指针head与尾结点t之间的关系可表示为__________。
37.一个算法通常可从正确性、易读性、健壮性和________________等四个方面评价、分析。
38.对于具有n个元素的有序序列，若采用冒泡排序，最多需要进行________________趟起泡。
39.通常从四个方面评价算法的质量：
_________、_________、_________和_________。
40.设head为单链表的头结点，则判断单链表为空的条件是：
_________。
41.直接插入排序需要_________个记录的辅助空间。
42.在插入和选择排序中，若初始数据基本正序，则选用_________；若初始数据基本反序，则选用_________。
43.
三、算法阅读
1．VoidAA（List&L）
{
InitList（L）;
InsertRear（L,30）;
InsertFront（L,50）;
Inta[4]={5,8,12,15};
For（intI=0;i<4;i++）InsertRear（L,a[i]）;
}
该算法被调用执行后，得到的线性表L为：
_________________。
四、应用题
1．设有字符串为3*-y-a/y^2，试利用栈写出将其转换为3y-*ay2^/-的操作步骤。
假定用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一字符加入到新字符串尾的出栈操作。
例如，ABC变为BCA的操作步骤XXSXSS。
2.现有某二叉树，按先根遍历的序列为ABDEFCGH，按中根遍历的序列为DEFBGHCA，试画出此二叉树。
3.设有一顺序队列sq，容量为5，初始状态时sq.front=sq.rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。
（1）d,e,b入队
（2） d,e出队（3）i,j入队（4）b出队（5）n,o,p入队
4.输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序列。
5.已知一组键值序列（28，47，35，42，53，60，34，22），试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。
6.已知一组键值序列（3，6，8，9，2，7，4，3），试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。
7.已知某二叉树的顺序存储结构如图所示，试画出该二叉树。
A
B
C
D
E
F
G
8.给定二叉树的中序遍历结果为abc，请画出能得到此中序遍历结果的二叉树的所有形态。
9.
五、算法设计
1.设某头指针为head的单链表的结点结构说明如下：
typedefstructnode1
{
intdata;
structnode1*next
}node;
试设计一个算法voidchange（node*head）,将该单链表中的元素按原单链表相反的次序重新存放，即第一个结点变成最后一个结点，第二个结点变为倒数第二个结点，如此等等。
2.设某单链表中，存在多个结点其数据值均为D，试编写一算法统计该类结点的个数。
3.若二叉树存储结构采用二叉链表表示，试编写一算法，计算一棵二叉树的所有结点数。
4.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。
5.二叉树是由所有度数不大于2的结点构成的一种特定树，若某结点度为2，则该结点有左右两个孩子，请编写算法计算一二叉树所有度数为2的结点个数。
6.若循环单链表长度大于1，p为指向链表中某结点的指针，试编写一算法删除p结点的前驱结点。
7.若二叉树用二叉链表表示，试编写一算法计算一棵二叉树的叶子总数。
8.试编写一个函数，以读取单链表的第i个元素。
9.
升级会员 