数据结构复习题总结.docx
《数据结构复习题总结.docx》由会员分享，可在线阅读，更多相关《数据结构复习题总结.docx（26页珍藏版）》请在冰点文库上搜索。
数据结构复习题总结
填空题
1.文件可按其记录的类型不同而分成两类，操作系统文件和数据库文件。
2.数据库文件按记录中关键字的多少可分成（单关键字文件）和（多关键字文件）两种文件。
3.文件由（记录）组成，记录由（数据项）组成。
4.从用户观点看，文件的逻辑结构通常可以区分为两类：
一类是如DBASE中数据库文件那样的文件组织结构，称为（数据库）文件；另一种是诸如用各种文字处理软件编辑成的文本文件，称为（文本）文件。
从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即（顺序组织）、（随机组织）、（链组织）。
B+树适用于组织（随机组织）的索引结构，
m阶B+树每个结点至多有（m）
除根结点外每个结点至少有（（m/2）向上取整）个儿子，根结点至少有
（2）个儿子，有k个儿子的结点必有（k）个关键码。
5.物理记录之间的次序由指针相链表示的顺序文件称为（串联文件）
6.顺序文件中，要存取第I个记录，必须先存取（第I-1）个记录。
7.索引顺序文件既可以顺序存取，也可以（随机）存取。
8.建立索引文件的目的的（提高查找速度）。
9.索引顺序文件是最常用的文件组织之一，通常用（树）结构来组织索引。
10.倒排文件的主在优点在于（检索记录块）。
11.检索是为了在文件中满足一定条件的记录而设置的操作。
检索可以按（关键字）检索，也可以按（记录号）检索；
按（记录号）检索又可以有（顺序）检索和（直接）检索。
12.哈希检索的技术的关键是（构造哈希函数）和（解决冲突的方法）。
结构来组织索引。
13.VSAM系统是由（索引集）、（顺序集）、（数据集）构成的。
14.VSAM（虚拟存储存取方法）文件的优点是：
动态地（分配和释放存储空间），不需要文件进行（重组），并能较快地（对插入的记录）进行查找。
一～五章选择题
一
1.学习数据结构的主要目的是（C）。
A．处理数据计算问题B．研究程序设计技巧
C．选取合适数据结构，写出更有效的算法D．是计算机硬件课程的基础
2.数据结构是一门研究非数值计算的程序设计问题中计算机的逻辑存储以及它们之间的（B）和运算的科学。
A．结构B．关系C．运算D．算法
3.在计算机中存储一个数据元素的位串称为（A）。
A.结点B.数据项C.数据字段D.字符串
4.算法指的是（C）
A.计算机程序B.排序算法
C.解决问题的有限运算序列D.解决问题的计算方法
5.（D）是数据不可分割的最小单位。
A．数据结构B．数据对象C．数据元素D．数据项
6.数据结构有（D）种基本逻辑结构。
A.1B.2C.3D.4
7.在数据结构中，从逻辑上可以把数据结构分成（C）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构
C．线性结构和非线性结构D．内部结构和外部结构
8.通常所说的时间复杂度是指（B）。
A．语句的频度和B．算法的时间消耗C．渐近时间复杂度D．最坏时间复杂度
9.（C）是数据的基本单位。
A．数据结构B．数据项C．数据元素D．数据类型
10.数据元素是数据的基本单位，其内（C）数据项。
A.只能包括一个B.不包含C.可以包含多个D.必须包含多个
11.计算机算法必须具有输入、输出和（A）等五个特性。
A．可执行性、确定性、有穷性B可执行性、可移植性、可扩充性
C．确定性、有穷性和稳定性D．易读性、稳定性和安全性
12.下列时间复杂度中最好的是（A）。
A.O
（1）B.O（n）C.O（log2n）D.O（n^2）
13.对于反复多次使用的程序，应尽是选用（B）算法。
A．节约空间B．节约时间C．简明易懂D．容易调试
14.对于反复多次使用的程序，应尽是选用（B）算法。
A．节约空间B．节约时间C．简明易懂D．容易调试
15.下列说法不正确的是（D）。
A．数据元素是数据的基本单位
B．数据项是数据中不可分割的最小可标识单位
C．数据可由若干个数据元素构成
D．数据项可由若干个数据元素构成
16.计算机算法指的是（C）。
A．计算方法和运算结果B．排序方法C．解决某一问题的有限序列D．调度方法
17.下列时间复杂度中最坏的是（D）。
A.O
（1）B.O（n）C.O（log2n）D.O（n^2）
18.根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式，其中解释错误的是（A）。
A．集合中任何两个结点之间都有逻辑关系但组织形式松散
B．线性结构中结点按逻辑关系依次排列形成一条“锁链”
C．树形结构具有分支、层次特性，其形态有点像自然界中的树
D．图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接
19.下列四种基本的逻辑结构中，数据元素之间关系最弱的是（A）。
A.集合B.线性结构C.树形结构D.图状结构
20.某算法的时间耗费为T（n）=100n+10log2n+n2+10，该算法的时间复杂度为（A）：
A．O（n2）B．O（n3）C．O（n）D．O
（1）
21.一般而言，最适合描述算法的语言是（C）。
A．自然语言B．计算机程序语言C．介于自然语言和程序设计语言之间的语言D．数学公式
22.研究数据结构就是研究（D）。
A．数据的存储结构
B．数据的存储结构
C．数据的逻辑结构及其数据在运算上的实现
D．数据的逻辑和存储结构及其数据在运算上的实现
23.下列四种基本的逻辑结构中，数据元素之间关系最弱的是（A）。
A.集合B.线性结构C.树形结构D.图状结构
24.评价一个算法时间性能的主要标准是（D）。
25.D．算法的时间复杂度
26.一个算法必须保证执行有限步之后结束，这是算法的（A）特性。
A．有穷性B．确定性C．可行性D．输出
27.逻辑关系是指数据元素间的（C）。
A.类型B.存储方式C.结构D.数据项
28.研究数据结构就是研究（D）。
A．数据的逻辑结构及其数据在运算上的实现
B．数据的存储结构
C．数据的逻辑和存储结构
D．数据的逻辑和存储结构及其数据在运算上的实现
29.算法分析的两个主要方面是（A）。
A．空间复杂性和时间复杂性B．正确性和简明性
C．可读性和文档性D．数据复杂性和程序复杂性
30.用类C语言描写的算法（B）。
A.可以直接在计算机上运行B.可以描述解题思想和基本框架
C.不能改写成C语言程序D.与C语言无关
31.逻辑结构是（A）关系的整体。
A.数据元素之间逻辑B.数据项之间逻辑C.数据类型之间D.存储结构之间
32.要求同一逻辑结构的所有数据元素具有相同特性，这意味着（B）。
A.数据元素具有同一的特点
B.不仅数据元素包含的数据项的个数要相同,而且对应数据项的类型要一致
C.每个数据元素都一样式
D.数据元素所包含的数据项的个数要相等
33.算法分析的目的是（C）。
A.找出数据结构的合理性B.研究算法中的输入与输出的关系
C.分析算法的效率以求改进D.分析算法的易懂性和文档性
34.数据结构被形式化地定义为（K，R），其中，R是K上（D）的有限集合。
A．操作B．映象C．存储D．关系
35.数据结构被形式化地定义为（K，R），其中，R是K上（D）的有限集合。
A．操作B．映象C．存储D．关系
36.一个存储结点存放一个（B）。
A.数据项B.数据元素C.数据结构D.数据类型
37.算法能正确地实现预定功能的特性称为（A）。
A.正确性B.易读性C.健壮D.高效率
38.数据结构被形式化地定义为（K，R），其中K是（B）的有限集合。
A．算法B．数据元素C．数据操作D．逻辑结构
39.数据结构被形式化地定义为（K，R），其中，R是K上（D）的有限集合。
A．操作B．映象C．存储D．关系
40.数据结构被形式化地定义为（K，R），其中K是（B）的有限集合。
A．算法B．数据元素C．数据操作D．逻辑结构
41.以下说法不正确的是（A）。
A．数据结构就是数据之间的逻辑结构
B．数据类型可看成是程序设计语言中已实现的数据结构
C．数据项是组成数据元素的最小标识单位
D．数据的抽象运算不依赖具体的存储结构
42.算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成，这是算法的（C）。
A．有穷性B．确定性C．可行性D．输出
二
1.线性表L=（a1,a2,…ai,…,an）,下列说法正确的是（D）。
A.每个元素都有一个直接前驱和直接后继
B.线性表中至少要有一个元素
C.表中诸元素的排列顺序必须是由小到大或由大到小的
D.除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继
2.对线性表进行二分法查找，其前提条件是（A）。
A．线性表以顺序方式存储，并且按关键码值排好序
B．线性表以顺序方式存储，并且按关键码值的检索频率排好序
C．线性表以链接方式存储，并且按关键码值排好序
D．线性表以链接方式存储，并且按关键码值的检索频率排好序
3.对于只在表的首尾两端进行插入操作的线性表，宜采用的存储结构为（ C）。
A.顺序表B.用头指针表示的单循环链表
C.用尾指针表示的单循环链表D.单链表
4.线性表的顺序存储结构是一种（A）的存储结构。
A．随机存取B．顺序存取C．索引存取D．散列存取
5.用数组表示线性表的优点是（B）。
A.便于插入和删除操作B.便于随机存取
C.可以动态地分配存储空间D.不需要占用一片相邻的存储空间
6.在线性表的下列存储结构中,读取元素花费时间最少的是（D）。
A.单链表B.双链表C.循环链表D.顺序表
7.线性结构中的一个结点代表一个（A）。
A.数据元素B.数据项C.数据D.数据结构
8.对于顺序表,以下说法错误的是（A）。
A.顺序表是用一维数组实现的线性表,数组的下标可以看成是元素的绝对地址
B.顺序表的所有存储结点按相应数据元素元素间的逻辑关系决定的次序依次排列
C.顺序表的特点是:
逻辑结构中相邻的结点在存储结构中仍相邻
D.顺序表的特点是:
逻辑上相邻的元素,存储在物理位置也相邻的单元中
9.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（A）存储方式最节省时间。
A．单链表B．双链表C．单向循环D．顺序表
10.线性表是（A）。
A.一个有限序列，可以为空B.一个有限序列，不可以为空
C.一个无限序列，可以为空D.一个无限序列，不可以为空
11.在（C）运算中，使用顺序表比链表好。
A．插入B．删除C．根据序号查找D．根据元素值查找
12.在循环双向链表的p所指的结点之后插入s所指结点的操作是（D）。
A．p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;
B．p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;
C．s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;
D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;
13.（D）适合作为经常在首尾两端操作线性表的存储结构。
A.顺序表B.单链表C.循环链表D.双向链表
14.对于顺序表的优缺点,以下说法错误的是（ C ）。
A.无需为表示结点间的逻辑关系而增加额外的存储空间
B.可以方便地随机存取表中的任何一结点
C.插入和删除操作较方便
D.由于顺序表要求占用连续的空间,存储分配只能预先进行（静态分配）
15.设非空单链表的数据字段为data，指针字段为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i+1个结点，下列算法段能正确完成上述要求的是（C）。
A.s->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
16.线性表中各元素之间的关系是（C ）关系。
A.层次B.网状C.有序D.集合
17.在长度为n的顺序表的第i（1≤i≤n+1）各位置上插入一个元素，元素的移动次数为（D）。
A.n-（i-1）B.n-iC.iD.i-1
18.在一个单链表HL中,若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（D）。
A．q->next=p->next;p->next=q;
B．p->next=q->next;q=p;
C．q->next=p->next;p->next=p;
D．p->next=q->next;q->next=p;
19.不带头结点的单链表head为空的判定条件是（A）
A．head==NULLB．head->next==NULLC．head->next==headD．head!
=NULL
20.非空的循环单链表head的尾结点（由p所指向）满足（C）。
A．p->next=NULLB．p=NULLC．p->next=headD．p=head
21.顺序表是线性表的（B）。
A.链式存储结构B.顺序存储结构C.索引存储结构D.散列存储结构
22.线性表中哪些元素只有一个直接前驱和一个直接后继（ C）。
A.首元素B.尾元素C.中间元素D.所有的元素
23.在长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移（A）个元素。
A．n-IB．n-i+1C．n-i-1D．i
24.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（D）。
A．s->next=p;p->next=s;B．s->next=p->next;p->next=s;
C．s->next=p->next;p=s;D．p->next=s;s->next=p;
25.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（B）个结点。
A．nB．n/2C．（n-1）/2D．（n+1）/2
26.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针字段，现要把一个指针s所指的新结点作为非空双链表中q所指结点（中间结点）的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是（C）。
A.q->right=s；s->left=q；q->right->left=s；s->right=q->right；
B.s->left=q；q->right=s；q->right->left=s；s->right=q->right；
C.s->left=q;s-right=q->right;q->right-left=s;q->right=s;
D.以上都不对
27.下面给出的算法段是把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双链表中，能正确完成要求的算法段是（A）。
A．q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q;
B．p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink;
C．q->llink=p->llink;q->rlink=p;p->llink->rlink=q;p->llink=q;
D．以上都不对
28.循环链表的主要优点是（D）。
A.不再需要头指针了
B.已知某个结点的位置后,容易找到它的直接前驱
C.在进行插入、删除操作时,能更好地保证链表不断开
D.从表中任一结点出发都能扫描到整个链表
29.在单链表的一个结点中有（A）个指针。
A.1B.2C.0D.3
30.在一个单链表中，删除p所指的直接后继的操作是（A）。
A．p->next=p->next->next;B．p=p->next->next;
C．p=p->next;D．p->next->next=p->next;
31.带有头结点的单链表head为空的判定条件是（B）。
A．head==NULLB．head->next==NULL
C．head->next==head D．head!
=NULL
32.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C）。
A．O
（1）B．O（n）C．O（m）D．O（m+n）
33.下面关于线性表的叙述中，错误的是（B）。
A.线性表采用顺序存储，必须占用一片连续的存储单元
B.线性表采用顺序存储，便于进行插入和删除操作
C.线性表采用链接存储，不必占用一片连续的存储单元
D.线性表采用链接存储，便于插入和删除操作
34.一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B ）。
A.O
（1）B.O（n）C.O（n^2）D.O（log2n）
35.在单循环链表中，用尾指针取代头指针的作用是（D）。
A．方便查找中间结点B．方便查找终端结点
C．方便查找开始结点D．查找开始结点和终端结点同样方便
36.在一个单链表中，已知q所指结点是p所指结点的前趋结点，若在p和q之间插入s结点，则执行的操作序列是。
（C）。
A.s->next=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;
37.带有头结点的单循环链表head为空的判定条件是（C）。
A．head==NULLB．head->next==NULLC．head->next==head D．head!
=NULL
38.链式存储的存储结构所占存储空间（A）。
A.分两部分，一部分存放结点值，另一部分存放表示结点关系的指针
B.只有一部分，存放结点值
C.只有一部分，存放表示结点关系的指针
D.分两部分，一部分存放结点值，另一部分存放结点所占单元数
39.线性表（L）经运算InitList（L）后，函数IEmpty（L）的值是（C）。
A.0B.falseC.1D.Null
40.以下关于链式存储结构的叙述中，（C）是不正确的。
A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B.逻辑上相邻的结点物理上不必邻接
C.可以通过计算直接确定第i个结点的存储地址
D.插入、删除运算操作方便，不必移动结点
41.在等概率情况下，顺序表的插入操作要移动（B）结点。
A．全部B．一半C．三分之一D．四分之一
42.在一个具有n个结点的有序单链表中插入一个新的结点并仍然有序的时间复杂度是（B）。
A．O
（1）B．O（n）C．O（n^2）D．O（log2n）
43.单链表中，增加头结点的作用是（A）。
A.方便运算的实现B.用于标志单链表
C.使单链表中至少有一个结点D.用于标志起始结点
44.两指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱的条件是（A）。
A.p->next==qB.q->next==pC.p==qD.p->next==null
45.线性表采用链式存储时，其地址（D）。
A.必须是连续的B.一定是不连续的
C.部分地址必须是连续的D.连续与否均可以
46.以下关于线性表的说法不正确的是（C）。
A.线性表中的数据元素可以是数字、字符、记录等不同类型
B.线性表中包含的数据元素个数不是任意的
C.线性表中的每个结点都有且只有一个直接前驱和直接后继
D.存在这样的线性表：
表中各结点都没有直接前驱和直接后继
47.在具有n个结点的单链表中，实现（A）的操作，其算法的时间复杂度都是O（n）。
A．遍历链表和求链表的第I个结点B．在地址为p的结点之后插入一个结点C．删除开始结点D．删除地址为p的结点的后继结点
48.指针P所指的元素是双向循环链表L的尾元素的条件是（D）。
A.P==LB.p==nullC.p->prior==LD.p->next==L
49.对顺序表上的插入、删除算法的时间复杂度分析来说，通常以（B）为标准操作。
A．条件判断B.结点移动C.算术表达式D.赋值语句
50.两个指针p和q分别指向双向循环链表L两个元素，p所指元素是q所指元素的后继的条件是（B）。
A.p==qB.q->next==pC.p->next==qD.q->next==p->next
51.线性表的链接实现有利于（A）运算。
A.插入B.读表元C.查找D.定位
52.用单链表的方式存储的线性表，存储每一个结点需要两个域，一个是数据域，另一个是（B ）。
A.当前结点所在地址域B.指针域C.空指针域D.空闲域
53.在双向链表的一个结点中有（B）个指针。
A.1B.2C.0D.3
54.指针p指向线性链表L首元素的条件是（A）。
A.p=LB.L->next=pC.p->next=LD.p->next=null
55.对线性表，在（B）情况下应当采用链表表示。
A．经常需要随机在存取元素B．经常需要进行插入和删除
C．表中元素需要占据一片连续的存储空间D．表中元素的个数不变
56.若某线性表中，最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（C）存储方式最省时。
A.单链表B.仅有头指针的单循环链表
C.双链表D.仅有尾指针的单循环链表
57.线性表的链式存储结构是一种（B）的存储结构。
A．随机存取B．顺序存取C．索引存取D．散列存取
58.用链接方式存储的队列，在进行删除运算时（D）。
A．仅修改头指针B．仅修改尾指针
C．头、尾指针都要修改D．头、尾指针可能都要修改
59.在顺序表中，只要知道（D），就可在相同时间内求出任一结点的存储地址。
A．基地址B．结点大小C．向量大小D．基地址和结点大小
三
1.4个元素进S栈的顺
升级会员 