数据结构考试复习题复习

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．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是 （ ）

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

③rear->next->next和rear

④rear和rear->next

18.以下说错误的是 ( )

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

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

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

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

①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=Head 38.非空的单循环链表L的尾结点*P,满足

P->next=NULL P=NULL P->next=L P=L. 39.双向链表结点结构如下： LLink data RLink 其中：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.顺序队列的人队操作应为 ( )

①sq.rear=sq.rear+1 sq.data[sq.rear]=x ②sq.data[sq.rear]=x sq.rear=sq.rear+1 ③sq.rear=(sq.rear+1)% maxsize; sq.data[sq.rear]=x ④sq.data[sqrear]=x sq.rear=(sq.rear+1)% maxsize

5.循环队列的人队操作应为 ( )

①sq.rear=sq.rear+1 sq.data[sq.rear]=x ②sq.data[sq.rear]=x sq.rear=sq.rear+1 ③sq.rear=(sq.rear+1)% maxsize sq.data[sq.rear]=x ④sq.data[sq.rear]=x sq.rear=(sq.rear+1)% maxsize

6. 顺序队列的出队操作为 ( )

①sq.front=(sq.front+1)% maxsize ②sq.front=sq.front+1 ③sq.rear=(sq.rear+1)% maxsize ④sq.rear=sq.rear+1

7. 循环队列的出队操作为 ( )

①sq.front=(sq.ftont+1)% maxsize ②sq.front=sq.front+1

③sq.rear=(sq.rear+)% maxsize ④sq.rear=sq.rear+1

8.循环队列的队满条件为 ( )

①(sq.rear+1) % mazsize ==(sq.front+1) % maxsize;

②(sq.rear+1 % maxsize ==sq.front+1 ③sq.(rear+1) % maxsize ==sq.front ④sq.rear ==sq.front

9.循环队列的队空条件为 ( )

①(sq.rear+1) % maxsize ==(sq.front+1) % maxsize ②(sq.rear+) % maxsize ==sq.front+1 ③(sp.rear+1) % maxsize ==sq.front ④sq.rear == sq.front

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

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

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

①front=front+1 ② front=（front+1）%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个序列中不可能出现的出栈序列是 （ ）

a1 a2 a3

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=s 20．链栈与顺序栈相比，有一个比较明显的优点即 （ ）

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

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

① e d c b a ②d e c b a ③d c e a b ④a b c d e

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=rear 1． 以下说法错误的是 ( )

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

④树(及一切树形结构)是一种\分支层次\结构 ⑤任何只含一个结点的集合是一棵树 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+1 11．下列说法中正确的是 ( )

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

②任何一棵二叉树中每个结点的度都为2 ③任何一棵二叉树中的度肯定等于2 ④任何一棵二叉树中的度可以小于2 13．设森林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 ④一棵二叉树的度可以小于2 31、设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是（ ）

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

二、判断题

三、填空题 （附答：

1、 分支层次、根、直接前趋 2、 子孙、祖先

3、 空、只含根、非空左子树、非空右子树、非空左右子树 4、 2i-1 5、 2k-1 6、 n2+1

7、 最大值、完全 8、 floor(log2n)+1

9、23 10、6 11、16

3、前趋 前趋 后趋 后趋

4、线性 5、线性 长度 表长 6、空表

12、0（1） 13、0 14、head->next==NULL 15、上溢 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. 下面语句段执行的时间复杂度是________。

int i,j,n,s=0;

cin>>n; //这里用n表示问题的规模 for (i=1;i<=10;i++)

for (j=1;j<=10;j++)

s+=i+j;

13. 访问长度为n的顺序表第i个元素，需要移动的元素个数为_______。 14. 带头结点的单链表head为空的判断条件是 。 15. 当栈满时再执行进栈操作，会产生 。

16. 设某循环队列的排头front值为17，队尾rear值为15，保存队列元素的数组

下标定义为30，则该循环队列中有______个元素。 17. 串是一种特殊的线性表，其特殊性在于---------。

本文来源：https://www.bwwdw.com/article/et83.html