数据结构考试复习题复习.docx

数据结构考试复习题复习.docx

《数据结构考试复习题复习.docx》由会员分享，可在线阅读，更多相关《数据结构考试复习题复习.docx（16页珍藏版）》请在冰点文库上搜索。

数据结构考试复习题复习

数据结构考试复习题复习

3.关于逻辑结构，以下说法错误的是　　　（）①逻辑结构与数据元素本身的形成、内容无关②逻辑结构与数据元素的相对位置有关③逻辑结构与所含结点个数无关

④一些表面上很不相同的数据可以有相同的逻辑结构⑤逻辑结构是数据组织的某种\本质性\的东西

7.通常从正确性、易读性、健壮性、高效性等四个方面评价算法（包括程序）的质量。

以下解释错误的是　　　　（）

①正确性算法应能正确地实现预定的功能（即处理要求）②易读性算法应易于阅读和理解以便于调试修改和扩充

③健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果

④高效性即达到所需要的时间性能

8.对于数据结构课程的主要内容，以下解释正确的是　　（）

①数据结构的定义，包括逻辑结构、存储结构和基本运算集②数据结构的实现，包括存储实现、运算实现和基本运算集

③数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储选择

12以下说法正确的是（）

①所谓数据的逻辑结构指的是数据元素之间的逻辑关系。

②逻辑结构与数据元素本身的内容和形式无关

③顺序文件只适合于存放在磁带上，索引文件只能存放在磁盘上④基于某种逻辑结构之上的运算，其实现是惟一的13以下说法正确的是　　（）①数据元素是数据的最小单位②数据项是数据的基本单位

③数据结构是带有结构的各数据项的集合④数据结构是带有结构的数据元素的集合14以下说法错误的是（）

①所谓数据的逻辑结构指的是数据元素之间的逻辑关系的整体

②数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的③数据结构、数据元素、数据项在计算机中的映象分别称为存储结构、结点、数据域

④数据项是数据的基本单位

15通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着　　（）

①数据元素具有同一特点

②不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致

③每个数据元素都一样

④数据元素所包含的数据项的个数要相等

3．顺序表的一个存储结点仅仅存储线性表的一个

①数据元素　　②数据项　　③数据　　④数据结构　　4．顺序表是线性表的

①链式存储结构　　②顺序存储结构　　③索引存储结构④散列存储结构

5.对于顺序表，以下说法错误的是　　①顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址　　②顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列③顺序表的特点是:

逻辑结构中相邻的结点在存储结构中仍相邻

④顺序表的特点是:

逻辑上相邻的元素，存储在物理位置也相邻的单元中

6.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以为标准操作

①条件判断　　②结点移动③算术表达式　　④赋值语句

7.对于顺序表的优缺点，以下说法错误的是　　①无需为表示结点间的逻辑关系而增加额外的存储空间②可以方便地随机存取表中的任一结点③插人和删除运算较方便

④于顺序表要求占用连续的空间，存储分配只能预先进行（静态分配）⑤容易造成一部分空间长期闲置而得不到充分利用

8.指针的全部作用就是　　　　①指向某常量　　②指向某变量　　③指向某结点　　④存储某数据

9.除了（　　），其它任何指针都不能在算法中作为常量出现，也无法显示。

①头指针　　②尾指针③指针型变量　　④空指针

10.单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法错误的是

①任何指针都不能用打印语句输出一个指针型变量的值

②如果要引用（如访问）p所指结点，只需写出p（以后跟域名）即可

③若想修改变量p的值（比如让P指向另一个结点），则应直接对p赋值　　④对于一个指针型变量P的值。

只需知道它指的是哪个结点

⑤结点*ｐ是两个域组成的记录，p->data是一个数据元素，p->next的值是一个指针

11.单链表的一个存储结点包含　　①数据域或指针域

②指针域或链域

③指针域和链域④数据域和链域

12.对于单链表表示法，以下说法错误的是　　①数据域用于存储线性表的一个数据元素

②指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针

③所有数据通过指针的链接而组织成单链表

④NULL称为空指针，它不指向任何结点，只起标志作用13.对于单链表表示法，以下说法错误的是　　①指向链表的第一个结点的指针，称为头指针

②单链表的每一个结点都被一个指针所指③任何结点只能通过指向它的指针才能引用④终端结点的指针域就为NULL

⑤尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表14．有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是　　①将“指针型变量”简称为“指针”②将“头指针变量”称为“头指针”

③将“修改某指针型变量的值”称为“修改某指针”④将“p中指针所指结点”称为“P值”15．设指针P指向双链表的某一结点，则双链表结构的对称性可用式来刻画

①p->prior->next->==p->next->next②p->prior->prior->==p->next->prior③p->prior->next->==p->next->prior④p->next->next==p->prior->prior

16.以下说法错误的是　　①对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表

②对单链表来说，只有从头结点开始才能扫描表中全部结点③双链表的特点是找结点的前趋和后继都很容易④对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。

17．在循环链表中，将头指针改设为尾指针后，其头结点和尾结点的存储位置分别是

①real和rear->next->next②rear->next和real

③rear->next->next和rear

④rear和rear->next

18.以下说错误的是（）

①对于线性表来说，定位运算在顺序表和单链表上的量级均为O

②读表元运算在顺序表上只需常数时间O便可实现，因此顺序表是一种随机存取结构

③在链表上实现读表元运算的平均时间复杂性为O④链入、摘除操作在链表上的实现可在O时间内完成

⑤链入、摘除操作在顺序表上的实现，平均时间复杂性为O19．在串的基本运算中，属于加工型运算的有

①EQAL（S,T）　　②LENGTH（S）

③CONCAT（S,T）④REPLACE（S,T,R）⑤INDEX（S,T）20.在串的基本运算中，属于引用型运算的有

①ASSIGN（S,T）　　②INSERT（S1,i,S2）

③DELETE（S,i,j）④SUBSTR（S,i,j）⑤REPLACE（S,T,R）21．循环链表主要优点是

①不再需要头指针了

②已知某个结点的位置后，能够容易找到它的直接前趋③在进行插入、删除运算时，能更好地保证链表不断开④从表中任一结点出发都能扫描到整个链表

22，每种数据结构都具备三个基本操作:

插入、删除和查找，这种说法①正确　　②错误23．以下说法错误的是

①数据的物理结构是指数据在计算机内实际的存储形式②算法和程序没有区别，所以在数据结构中二者是通用的③对链表进行插人和删除操作时，不必移动结点④双链表中至多只有一个结点的后继指针为空24．以下说法正确的是

①线性结构的基本特征是：

每个结点有且仅有一个直接前趋和一个直接后继②线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上

的实现效率要低③在线性表的顺序存储结构中，插人和删除元素时，移动元素的个数与该元素位置有关

④顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动

25．以下说法错误的是

①求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

②顺序存储的线性表可以随机存取

③于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

④线性表的链式存储结构优于顺序存储结构26．以下说法错误的是

①线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻

②在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻

③在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻④线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素

27．以下说法正确的是

①在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素

②在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构

③顺序存储结构属于静态结构，链式结构属于动态结构④顺序存储方式只能用于存储线性结构28.以下说法正确的是

①顺序存储方式的优点是存储密度大、且插入、删除运算效率高②链表的每个结点中都恰好包含一个指针③线性表的顺序存储结构优于链式存储结构

④顺序存储结构属于静态结构，链式结构属于动态结构29.下面关于线性表的叙述正确的是（　　）

①线性表采用顺序存储，必须占用一片连续的存储单元②线性表采用顺序存储，便于进行插人和删除操作

③线性表采用链接存储，不必占用一片连续的存储单元④线性表采用链接存储，不便于插人和删除操作

30.线性表L=（a1,a2,...,ai,...,an）,下列说法正确的是（）

①每个元素都有一个直接前驱和直接后继②线性表中至少要有一个元素

③表中诸元素的排列顺序必须是小到大或大到小的

④除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继

31.线性表的逻辑顺序与存储顺序总是一致的，这种说法（）

①正确　　②不正确

32.设p,q是指针,若p=q,则*p=*q,这种说法（　　）

①正确　　②不正确

33.线性表若采用链表存储结构时，要求内存中可用存储单元的地址（）

①必需是联系的　　②部分地址必须是连续的

③一定是不连续的　　④连续不连续都可以

34.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为（　　）

①p=rear;　　　②rear=rear->next;rear=rear->next;　　　free（rear）;free（p）

③rear=rear->next->next;　　④p=rear->next->next;

free（rear）;　　　rear->next->next=p->next;

free（p）;35.单链表中，增加头结点的目的是为了（）

①使单链表至少有一个结点　　②标示表结点中首结点的位置

③方便运算的实现　　④说明单链表是线性表的链式存储实现36线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着

①　　每个结点所代表的数据元素都一样。

②　　每个结点所代表的数据元素包含的数据项的个数要相等

③　　不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一

致

④　　结点所代表的数据元素有同一特点37．带头结点的单链表Head为空的判定条件是

①Head=Null　　②Head->next=NULL　　③Head->next=Head38.非空的单循环链表L的尾结点*P,满足

P->next=NULL　　P=NULL　　P->next=L　　P=L.39.双向链表结点结构如下：

LLinkdataRLink其中：

LLink是指向前驱结点的指针域：

data是存放数据元素的数据域；Rlink是指向后继结点的指针域。

下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到此双向链表中。

不能正确完成要求的算法段是①Q->LLink=P->LLink;　　②P->LLink=Q;Q->Rlink=P;　　　Q->Rlink=P;

P->LLink=Q;　　　P->LLink->Rlink=Q;P->LLink->Rlink=Q;　　Q->LLink=P->LLink;③Q->LLink=P->LLink;Q->Rlink=P;

P->LLink->Rlink=Q;

P->LLink=Q;

40.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用存储方式最节省时间。

①顺序表　　②单链表　　③双链表　　④单循环链表1．在以下栈的基本运算中，不是加工型运算的是

①lnitStack（S）②Push（S,X）③Pop（S）④empty（S）2.以下说法正确的是（）

①因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况②因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况

③对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”④对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。

3．在以下队列的基本运算中，不是加工型运算的是

①InitQueue（Q）②EnQueue（Q,X）③OutQueu（Q,X）④GetHead（Q,x）4.顺序队列的人队操作应为（）

①=+1　　　=x②=x　　　=+1③=（+1）%maxsize;　　=x④[sqrear]=x　　　=（+1）%maxsize

5.循环队列的人队操作应为（）

①=+1　　　=x②=x　　　=+1③=（+1）%maxsize　　=x④=x　　　=（+1）%maxsize

6.顺序队列的出队操作为（）

①=（+1）%maxsize②=+1③=（+1）%maxsize④=+1

7.循环队列的出队操作为（）

①=（+1）%maxsize②=+1

③=（+）%maxsize④=+1

8.循环队列的队满条件为（）

①（+1）%mazsize==（+1）%maxsize;

②（+1%maxsize==+1③sq.（rear+1）%maxsize==④==

9.循环队列的队空条件为（）

①（+1）%maxsize==（+1）%maxsize②（+）%maxsize==+1③（+1）%maxsize==④==

12．如果以链表作为栈的存储结构，则退栈操作是　　　（）

①必须判别栈是否满　　②必须判别栈是否空③判别栈元素的类型　　④对栈不做任何操作14．设C语言数组Data[m+1]作为循环队列SQ的存储空间，front为队头指针，

rear为队为指针，则执行出队操作的语句为　　

①front=front+1　　②front=%m③rear=（rear+1）%m　　④front=（front+1）%（m+1）

15.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是　　　

①2　　②3　　　③5　　④6

16．设有一顺序栈已含3个元素，如下图所示，元素a4正等待进栈。

那么下列4个序列中不可能出现的出栈序列是

a1a2a3

0　　1　　2　　3　　maxsize-1

sq↑top

①a3,a1,a4,a2　　②a3,a2,a4,a1　　③a3,a4,a2,a1　　④a4,a3,a2,a1

17.向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为①Top->next=s　　②s->next=Top->next;Top->next=s③s->next=Top;Top=s　　④s->next=Top;Top=Top->next

18.从栈顶指针为Top的链栈中删除一个结点，并将被删节点的值保存到x中，其操作步骤为

①x=Top->data;Top=Top->next　　②Top=Top->next;x=Top->data③x=Top;Top=Top->next　　　④x=Top->data

19.在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为

①f->next=c;f=s　　　②r->next=s;r=s③s->next=r;r=s　　　④s->next=f;f=s20．链栈与顺序栈相比，有一个比较明显的优点即

①插入操作更方便　　②通常不会出现栈满的情况③不会出现栈空的情况　　④删除操作更方便

22.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是

①edcba　　②decba　　③dceab　　④abcde

23.一个队列的人列序列是1，2，3，4，则队列的输出系列是

①4，3，2，1　　②1，2，3，4，　　③1，4，3，2　　④3，2，4，1

24．设计一个判别表达式中左、右括号是否配对出栈的算法，采用数据结构最佳。

①线性标的顺序存储结构　　②栈

③队列　　　④线性表的链式存储结构

25．若已知一个栈的输入序列为1，2，3，...,n,其输出序列为P1、P2、...Pn。

若

p1=n,则Pi为

①i　　②n=i　　③n-i+1　　④不确定

26．以下说法正确的是

①顺序队和循环队的队满和队空判断条件是一样的②栈可以作为实现过程调用的一种数据结构

③插人和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用

④在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件front=rear1．以下说法错误的是（　　）

①树形结构的特点是一个结点可以有多个直接前趋②线性结构中的一个结点至多只有一个直接后继③树形结构可以表达（组织）更复杂的数据

④树（及一切树形结构）是一种\分支层次\结构⑤任何只含一个结点的集合是一棵树2，以下说法错误的是（　　）①二叉树可以是空集

②二叉树的任一结点都有两棵子树③二叉树与树具有相同的树形结构

④二叉树中任一结点的两棵子树有次序之分

3、以下说法错误的是（　　）

①完全二叉树上结点之间的父子关系可它们编号之间的关系来表达②在三叉链表上，二叉树的求双亲运算很容易实现③在二叉链表上，求根，求左、右孩子等很容易实现④在二叉链表上，求双亲运算的时间性能很好5．深度为6的二叉树最多有（　　）个结点.①64　　②63　　③32　　④31

6．将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双结点编号为（　　）①42　　②40　　③21　　④20

7．任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置（）①肯定发生变化　　②有时发生变化③肯定不发生变化　　④无法确定

8．设二叉树有n个结点，则其深度为（　　）①n-1　　②n　　③5floor（log2n）　　④无法确定

9．设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少个

①k+1　　②2k　　③2k-1　　④2k+111．下列说法中正确的是（　　）

①任何一棵二叉树中至少有一个结点的度为2

②任何一棵二叉树中每个结点的度都为2③任何一棵二叉树中的度肯定等于2④任何一棵二叉树中的度可以小于213．设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有个结点。

①n1-1　　②n1　　③n1+n2+n3　　④n2+n3+n4

14．森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的左孩子上有个结点。

①n1-1　　②n1　　③n1+n2+n3④n2+n3+n4

16．讨论树、森林和二叉树的关系，目的是为了

①借助二叉树上的运算方法去实现对树的一些运算②将树、森林按二叉树的存储方式进行存储③将树、森林转换成二叉树

④体现一种技巧，没有什么实际意义

30、下列说法中正确的是　　　　（）①二叉树中任何一个结点的度都为2　　②二叉树的度为2

③任何一棵二叉树中至少有一个结点的度为2④一棵二叉树的度可以小于231、设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是

①2h　　②2h-1　　③2h-1　　④2h+1-1

二、判断题

三、填空题13、014、head->next==NULL15、上溢16、28　　17、每个数据元素是一个字符）

1、树是一种“________”结构。

在树上，________结点没有直接前趋。

对树上任一结点X来说，X是它的任一子树的根结点惟一的________。

2、一棵树上的任何结点称为根的________。

若B是A的子孙，则称A是B的________

3、一般的，二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______

的二叉树、同时有______的二叉树五种基本形态。

4、二叉树第i（i>=1）层上至多有______个结点。

5、深度为k（k>=1）的二叉树至多有______个结点。

6、对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。

7、满二叉树上各层的节点数已达到了二叉树可以容纳的______。

满二叉树也是______二叉树，但反之不然。

8、具有n个结点的完全二叉树的深度为______。

9.如果一棵树有6个度为1的结点，有5个度为2的结点，有2个度为3的结

点，其余结点均为叶子，则该树的结点总数为_______。

10.某完全二叉树有39个结点，计算其深度为_______。

11.深度为5的完全二叉树，结点个数最少为______。

3.线性结构的基本特征是:

若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______.

4.所有结点按1对1的邻接关系构成的整体就是______结构。

5.线性表的逻辑结构是______结构。

其所含结点的个数称为线性表的______，简称______.

6.表长为O的线性表称为______

12.下面语句段执行的时间复杂度是________。

inti,j,n,s=0;

cin>>n;　　//这里用n表示问题的规模fo