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=(a
1,a
2
,...,a
i
,...,a
n
),下列说法正确的是( )
①每个元素都有一个直接前驱和直接后继
②线性表中至少要有一个元素
③表中诸元素的排列顺序必须是由小到大或由大到小的
④除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继
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是指向后继结点的指针域。
下面给出的算法段是要把一个新结点*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，元素s
1,s
2
,s
3
,s
4
,s
5
,s
6
依次进栈，如果6个元素出栈的顺序
是s
2,s
3
,s
4
, s
6
, s
5
,s
1
,则栈的容量至少应该是
（）
①2 ② 3 ③ 5 ④6
16．设有一顺序栈已含3个元素，如下图所示，元素a4正等待进栈。那么下列4个序列中不可能出现的出栈序列是（）
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, 其输出序列为P
1、P
2
、...P
n
。
若p1=n,则P i为
①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(log
2
n) ④无法确定
9．设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（）个
①k+1 ②2k ③2k-1 ④2k+1
11．下列说法中正确的是 ( )
①任何一棵二叉树中至少有一个结点的度为2
②任何一棵二叉树中每个结点的度都为2
③任何一棵二叉树中的度肯定等于2
④任何一棵二叉树中的度可以小于2
13．设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有（）个结点。
①n
1-1 ②n
1
③n
1
+n
2
+n
3
④n
2
+n
3
+n
4
14．森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的左孩子上有（）个结点。
①n
1-1 ②n
1
③n
1
+n
2
+n
3
④n
2
+n
3
+n
4
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，则叶子数n
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.串是一种特殊的线性表，其特殊性在于---------。
一、填空。 1．顺序存储结构的特点是（静态存储的物理次序和逻辑次序一致），链式存储结构的特点式（动态存储的物理次序和逻辑次序不一定一致）。 2．算法在遇到非法操作时可以作出合理处理的特性为（健壮性）。 3．常见的算法时间复杂度用大O记号表示为：常数阶（ O(1) ），对数阶（ O(log2n ) ），线性阶（O(n) ），平方阶( O(n2) )和指数阶（ O(2n) ）。 4．在单链表中，除了头结点以外，任一结点的存储位置由（其直接前驱的指针域）指示。 5．当线性表采用顺序存储结构时，其主要特点是（静态存储物理次序和逻辑次序一致）。6．在双链表中，每个结点设置了两个指针域，其中一个指向（直接前驱）结点，另一个指向（直接后继）结点。 7．设有一个空栈，栈顶指针为1000H，现有输入序列为1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是（ 2,3 ），栈顶指针是（ 1003 H ）。8．栈S通常采用的两种存储结构是（顺序存储和链序存储）；其判定栈空的条件分别是（ s->top==-1 top->next==NULL ）, 判定栈满的条件分别是（ s->top==stack_size-1 ）。 9．（栈）可作为实现递归函数调用的一种数据结构。 10．栈和队列是两种特殊的线性表，栈的操作特性是（先进后出），队列的操作特性是（先进先出），栈和队列的主要区别是（栈是在表的一端进行操作，队列是在表的两端进行操作）。 11．循环队列的引入是为了克服（假溢出）。 12．数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为 ( (front-rear+n）mod n ）。 13．用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别为（ O(1) ）和（ O(n) ）。 14．串是一种特殊的线性表，其特殊性体现在（串的数据限定为字符集）。 15．两个串相等的充分必要条件是（两个串的长度相等并且每个对应位置的字符都相等）。 16．（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。17．从逻辑关系上讲，数据结构主要分为（集合结构）、（线性结构）、（树形结构）、（图状结构或网状结构）。 18．数据的存储结构主要有（顺序）和（非顺序）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（数据的表示）和（关系的表示）。 19．算法具有5个特性，分别是（可行性，有限性，确定性，输入和输出） 20．顺序表中第一个元素的地址是100，每个元素的长度为2，则第五个元素的存储地址是（ 108 ）。 21．单链表中设置头指针的作用是（标识链表在内存中的位置）。 22、设单链表中指针P指向结点A，若要删除A的后继结点（假设A存在后继结点），则修改指针的操作为（ p->next=p->next->next; ）。 23．设S=”I AM A TEACHER”,其长度为（ 14 ）。 24．对于栈和队列，无论它们采用顺序存储结构还是链式存储结构，进行插入和删除操作的时间复杂度都是（ O(1) ）。 25．数组通常有两种运算：（获得特定位置的元素值）和（修改特定元素的值），这决定了数组通常采用（顺序）结构来存储。
1. 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O (n) D. O (n2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 A. 2k-1 B. 2k C.2k-1 D. 2k-1 3．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。 A. 2i B. 2i C. 2i-1 D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p 5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。 A. 6 B. 4 C. 3 D. 2 6.设有以下四种排序方法，则（ B ）的空间复杂度最大。 A. 冒泡排序 B. 快速排 C. 堆排序 D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 A. 3 B. 4 C. 5 D. 1 8．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 A. 4 B. 5 C. 6 D. 7 9．对一个算法的评价，不包括如下（ A ）方面的内容。 A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在二叉排序树中插入一个结点的时间复杂度为（ C ）。 A．O(1) B．O(n) C．O(log 2 n) D．O(n2)
一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t)
1.什么是最小生成树？简述最小生成树的Prime算法的思想。 答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。 普里姆算法(Prim)的基本思想： 从连通网络N = { V, E }中的某一顶点u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2.简述AOV网络中为何不能出现回路，如何判断AOV网络是否有回路？ 答：在AOV网络中，如果活动vi必须在vj之前进行，则称为存在有向边；在AOV网络中不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环： 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。（1）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2）如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV 网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。
3.为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什 么？ 答：循环队列以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。 n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear，而队满的条件是(Q.rear+1)%N==Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。 4.简述堆的删除算法，其删除的是那个值？ 答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面，删除的值为根值。 5.线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？
0一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示（D，S，P）。其中：D是数据对象，S 是D上的关系，P是对 D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表（头指针为L）中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取?表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(顺序弄反了)(f) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。栈和队列是操作上受限制的线性表(f) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。对列不是(f) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的 特殊情形。(f) 15 二叉树是一棵结点的度最大为二的树二叉树和树相互独立。(f) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历后根遍历相当于中序遍历。(f) 19. 通常，二叉树的第i层上有2i-1个结点。应该为1~2i-1个(f) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。 (t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。只能表示无向图，有向图用十字链表(f) 24 可从任意有向图中得到关于所有顶点的拓扑次序带环图没有。(f) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 26 关键路径是AOE网中源点到汇点的最短路径。(f) 27 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。(f) 28 一个无向图的连通分量是其极大的连通子图。(t) 29 十字链表可以表示无向图，也可用以表示有向图。(f) 30 邻接表可以表示有向图，也可以表示无向图。（t ） 31. 二叉排序树的平均查找长度为O(logｎ)。(t) 32. 二叉排序树的最大查找长度与（LOG2N）同阶。(f) 33 选用好的HASH函数可避免冲突。哈希函数有几种处理冲突的方法(f) 34 折半查找不适用于有序链表的查找。(t) 35. 对于目前所知的排序方法，快速排序具有最好的平均性能。(t) 36 对于任何待排序序列来说，快速排序均快于冒泡排序。(f)
数据结构考试复习题集团档案编码：[YTTR-YTPT28-YTNTL98-UYTYNN08]
复习题集 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机内部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 （×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据]（×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的内存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表]
贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j
数据结构期中练习 学号姓名 一、选择题 1.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 参考答案：C 2.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 参考答案：A B 3.判定一个栈ST(最多元素为m0)为空的条件是（）。 （A） ST-〉top!=0 （B）ST-〉top==0 （C）ST-〉top!=m0 （D）ST-〉top=m0 参考答案：B 4.判定一个栈ST(最多元素为m0)为栈满的条件是（）。 （A）ST->top!=0 （B）ST->top==0 （C）ST->top!=m0-1（D）ST->top==m0 参考答案：D 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 参考答案：C 6.稀疏矩阵一般的压缩存储方法有两种,即（）。 （A）二维数组和三维数组（B）三元组和散列 （C）三元组和十字链表（D）散列和十字链表
参考答案：C 7. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。 （A）64（B）63 （C）63.5 （D）7 参考答案：C 8. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（） （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; 参考答案：B 9.在一个单链表中，若删除p所指结点的后续结点，则执行（） （A）p->next=p->next->next; （B）p=p->next; p->next=p->next->next; （C）p->next=p->next; （D）p =p->next->next; 参考答案：A 10.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为（）。 （A）SA+141（B）SA+180（C）SA+222（D）SA+225 参考答案：B 11. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。 （A） edcba（B）decba（C）dceab （D）abcde 参考答案：C 12.二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素( ) 的起始地址相同。 （A）M[2][4]（B）M[3][4]（C）M[3][5]（D）M[4][4] 参考答案：B 13.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（）。 （A）80（B）100（C）240（D）270 参考答案：C
数据结构习题集含答案 目录
选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性
7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0;
2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。
s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。
第1章绪论 1 自测习题 二、选择题 1．以下数据结构中，属于线性结构的是 ( B ) A）有向图B）串C）线索二叉树D）B树 2．下列与数据元素有关的叙述中错误的是 (A) A）数据元素是有独立含义的数据最小单位 B）数据元素是描述数据的基本单位 C）数据元素可以称做结点 D）数据元素可以称做记录 3．以下术语中与数据的存储结构无关的是 (A) A）栈B）散列表C）顺序表D）双链表 4．以下数据结构中，属于线性结构的是 (B) A）有向图B）串C）线索二叉树D）B树 三、填空题 1．数据结构包括的三方面内容分别是：数据的逻辑结构、数据的存储结构和数据的运算。 2．数据元素是数据的基本单位，在某些情况下也可以称为结点、记录和顶点。
3．数据逻辑结构的4种基本形态包括集合结构、线性结构、树型结构和图（网）结构。 4．一个正确的算法应该具有5个特性：输入、输出、确定性、可行性和有穷性。 5．数据的存储结构包括顺序、链式、索引和散列四种。6．一个数据结构在计算机中的映象称为存储结构。 7．一个算法的效率主要是指该算法的时间效率和空间效率。 8．以下程序段的时间复杂度T（n）=_) O_____。 (2n sum=0; for(i=0 ; i 环链表 2．线性表是具有n 个 (B) 的有限序列。 A ）数据项 B ）数据元素 C ）表元素 D ）字符 3．若长度为n 的线性表采用链式存储结构，访问其第i 个元素的算 法时间复杂度为 (B) A ）O(1) B ）O(n) C ） O(n 2) D ）O(log 2n) 4．在长度为n 的顺序表中，若要删除第i （1≤i ≤n ）个元素，则 需要向前移动的元素的次数为 (B) A ）i B ）n-i C ）n-i+1 D ）n-i-1 5．在长度为n 的顺序表中第i （1≤i ≤n ）个位置上插入一个元素时， 为留出插入位置所需移动元素的次数为 (C) A ）n-i B ）i C ）n-i+1 D ）n-i-1 三、填空题 1．有一单链表结构如下： 图2-1 填空题1附图 若要删除值为c 的结点，应做的操作是 p->link=p->link->link 。 2．线性表L=( a 1,a 2,…a n )用数组存储。假定删除表中任一元素的概 … … data link 2005年－2006学年第二学期“数据结构”考试试题（A）姓名学号(序号)_答案隐藏班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清晰姓名、班号和学号），需写清晰题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1．数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答：A。 2.链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答：参见本节要点3。本题答案为：A。 3.在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答：C。 4．以下线性表的存储结构中具有随机存取功能的是d 。 A.不带头结点的单链表 B.带头结点的单链表 C.循环双链表 D.顺序表 解D。 5.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。A.edcba B.decba C.dceab D.abcde 答：C。 6.循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答：D。 7.两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答：B。 8.用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是 c 。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90,80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94,40 答：C。 9.以下序列不是堆（大根或小根）的是 d 。 A.{100,85,98,77,80,60,82,40,20,10,66} B.{100,98,85,82,80,77,66,60,40,20,10} C.{10,20,40,60,66,77,80,82,85,98,100} D.{100,85,40,77,80,60,66,98,82,10,20} 第1章绪论 一、判断题 1.数据的逻辑结构与数据元素本身的容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（×） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√） 7.数据的存储结构是数据的逻辑结构的存储映象。（√） 8.数据的物理结构是指数据在计算机实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和步骤的描述。（√） 二、填空题 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算法和事后统计法。 16.一个算法的时间复杂度是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。 18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（nlog2n）。 19.若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O（n2）。 20.数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学 科。 三、选择题 1.数据结构通常是研究数据的（A）及它们之间的相互关系。 A．存储结构和逻辑结构B．存储和抽象C．联系和抽象D．联系与逻辑 2.在逻辑上可以把数据结构分成（C）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．部结构和外部结构。 3.数据在计算机存储表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。 A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构 4.非线性结构中的每个结点（D）。 A．无直接前驱结点．B．无直接后继结点． 数据结构复习题答案 一、选择题 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时 ( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、 尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？ ( ) A. 队列 B. 栈 C. 线 性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放 位置在644 ，A[2][2]存放位置在676(10)，每个 (10) 元素占一个空间，问A[3][3](10)存放在（）位 置，脚注 表示用10进制表示。 (10) A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B. 无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19] 中，第一个元素放A[1]中，现进行二分查找，则 查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2， 3 C. 9，5，3 D. 9，4，2， 3 8.对n个记录的文件进行快速排序，所需要的辅 助存储空间大致为( ) A. O（1） B. O（n） C. O n） D. O（n2） （1og 2 9.对于线性表（7，34，55，25，64，46，20，10） 进行散列存储时，若选用H（K）=K %9作为散列 函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列 3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 5、在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于（ A ） A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ） A、正确的 B、错误的 C、不一定，与具体的结构有关 4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ） A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是（ B ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（ A ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（ C ） A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ） A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ） 一、选择题 1、一个n个顶点的无向连通图，其边的个数至少为（）。 A．n-1 B．n C．n+1 D．nlogn 2、以下数据结构中，（）是非线性数据结构。 A．树B．字符串C．队列D．栈 3、在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为（）。 A．n –i+1 B．n –i C．i D．i-1 4、与线性表的链接存贮不相符合的特性是（）。 A．便于插、删运算B．需要连续的存贮空间 C．只能顺序查找D．存贮空间动态分配 5、顺序存放的循环队列的元素以数组A[m]存放,其头尾指针分别为front和rear，则当前队列中的元素个数 为（）。 A．(rear-front+m)%m B．rear-front+1 C．(front+rear+m)%m D．(rear-front)%m 6、一个有n个顶点的无向图最多有( )条边。 A．n(n-1)/2 B．n (n-1) C．n-1 D．n+1 7、设栈的入栈序列是1，2，3，4，则（）不可能是其出栈序列。 A．1，2，4，3 B．2，1，3，4 C．1，4，3，2 D．4，3，1，2， 8、从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．初等结构、构造型结构 C．线性结构、非线性结构D．树型结构、图型结构 9、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（） A．空或只有一个根结点B．高度等于其结点数 C．任一结点无左孩子D．任一结点无右孩子 10、已知一个有向图用邻接矩阵表示，要删除所有从第i个结点发出的边，应该（）。 A．将邻接矩阵的第i 行删除B．将邻接矩阵的第i 行元素全部置零 C．将邻接矩阵的第i 列删除D．将邻接矩阵的第i 列元素全部置零 11、算法分析的两个主要方面是（） A．空间复杂性和时间复杂性B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 12、线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以 13、具有6个顶点的无向连通图的生成树应有（）条边。 A．5 B．6 C．7 D．8 14、设栈的输入序列是A、B、C，则（）不可能是其出栈序列。 A．CBA B．CAB C．BCA D．ACB 15、有一个含头结点的单链表，头指针为head，则判断其是否为空的条件为（）。 A．head==NULL B．head->next==NULL C．head->next== head D．head ！=NULL 16、栈和队都是（） A．顺序存储的线性结构B．链式存储的非线性结构 C．限制存取点的线性结构D．限制存取点的非线性结构 17、在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。 A．①②③B．②③④C．②④D．①④ 18、以下数据结构中，（）是非线性数据结构。 《数据结构》课程复习资料 一、填空题: 1.设需要对5个不同的记录关键字进行排序，则至少需要比较________次，至多需要比较__________次。 2.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。 3.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查 找成功有结点数有_________个。 4.数据结构从逻辑上划分为三种基本类型：___________、__________和___________。 5.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中， 包含有________条边。 6.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。 7.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复 杂度为________。 8.在快速排序、堆排序、归并排序中，_________排序是稳定的。 9.在有n个叶子结点的哈夫曼树中，总结点数是_______。 10.一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定 _______。 11.3.已知数组A［10］［10］为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存 储在起始地址为1000的连续的内存单元中，则元素A［5，6］对应的地址是_______。 12.在有n个结点的无向图中，其边数最多为_______。 13.取出广义表A=(x,(a,b,c,d))中原子x的函数是_______。 14.对矩阵采用压缩存储是为了___ ____。 15.带头结点的双循环链表L为空表的条件是_______。 16.设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是。 17.对于顺序存储的栈，因为栈的空间是有限的，在进行运算时，可能发生栈的上溢，在进行运 算时，可能发生栈的下溢。 18.在双向链表中，每个结点有两个指针域，一个指向，另一个指向。 19.由一棵二叉树的前序序列和可唯一确定这棵二叉树。 20.折半查找的存储结构仅限于___ _，且是_ ___。 21.对于一个顺序存储的线性表，在表头插入元素的时间复杂度为____________,在表尾插入元素的时间复 杂度为________________。 22.在稀疏距阵所对应的三元组线形表中，每个三元组元素按____________为主序，__________为辅序的 次序排列。 23.中缀表达示3+X*（2.4/5-6）所对应的后缀表达示为______________。 24.在一棵高度为h的3叉树中，最多含有_______结点。 25.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i数据结构期末考试试题含复习资料
数据结构练习试题和答案解析
数据结构复习题答案
数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)
数据结构复习题及答案
数据结构复习题及参考答案
相关主题
文本预览