数据结构习题集（自编）
第一章绪论
一、选择题
1．数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之
间的（）和运算的学科。
A．结构B．关系C．运算D．算法
2．在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构 B ．紧凑结构和非紧凑结构C．线性结
构和非线性结构 D ．逻辑结构和存储结构
3．线性表的逻辑顺序和存储顺序总是一致的，这种说法（）。
A．正确B．不正确C．无法确定D．以上答案都不对4．算法分析的目的是（）。
A．找出算法的合理性B．研究算法的输人与输出关系
C．分析算法的有效性以求改进D．分析算法的易懂性
5.算法的时间复杂度取决于（）
A．问题的规模 B 待处理数据的初态 C. A 和 B
6．一个算法应该是（）。
A．程序B．问题求解步骤的描述
C ．要满足五个基本特性D．A和C.
7.下面关于算法说法错误的是（）
A．算法最终必须由计算机程序实现
B.为解决某问题的算法与为该问题编写的程序含义是相同的
C.算法的可行性是指指令不能有二义性
D.以上几个都是错误的
8．以下与数据的存储结构无关的术语是（）。
A．循环队列 B.链表 C.哈希表 D.栈
9．在下面的程序段中，对 x 的赋值语句的频度为（）
for （ i=0;i for(j=0;j x=x+1; 2n A． 2n B．n D．log C．n2 10．以下数据结构中，（）是非线性数据结构 A．树B．字符串 C ．队列D．栈 11. 下列数据中，（）是线性数据结构。 A．哈夫曼树 B.有向无环图 C.二叉排序树 D. 栈12．以下属于逻辑结构的是（）。 A．顺序表 B.哈希表 C.有序表 D.单链表 二、填空题 1、_______是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理， ________是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。（数据、数据） 2、数据元素是数据的 ______，有些情况下也称为元素、结点、顶点、记录等。（基本单位） 3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。 例如构成一个数据元素的字段、域、属性等都可称之为________。（数据项、数据项） 4、数据的逻辑结构是指数据之间的 ________。逻辑结构是从 ________上描 述数据，它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具 体问题抽象出来的 ______________。（逻辑关系、逻辑关系、数学模型） 5、数据的 ________指数据元素及其关系在计算机存储器内的表示。 _________是逻辑结构在计算机里的实现，也称之为映像。（存储结构、存储结构） 6、数据逻辑结构可以分为四种基本的类型， _______结构中的元素除了仅仅 只是同属于一个 _________________，不存在什么关系。（集合、集合） 7、数据逻辑结构的四种基本类型中，________中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端 结点，并且所有结点最多只能有一个直接前驱和一个直接后继。（线性结构） 8、数据逻辑结构的四种基本类型中， ____________中的元素是一种一对多 的关系。（树形结构） 9、图型结构或图状结构是一种 ________的关系。在这种逻辑结构中，所有 结点均可以有多个前驱和多个后继。（多对多） 10、有时也可将树型结构、集合和图型结构称为 __________，这样数据的逻辑结构就可以分为 __________和 ________两大类。（非线性结构、线性结构、非线性机构） 11、____________方式是指逻辑上相邻的结点被存储到物理上也相邻的存储 单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的 关系是通过存储单元的相邻关系隐含的表示出来的。（顺序存储） 12、_______方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。（链式存储） 13、_________方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。（散列存储或哈希存储） 14、所谓算法（ Algorithm ）是对特定问题求解步骤的一种描述，它是指令 的其中每个指令表示一个或多个操作。算法的五个重要特性是__________、 __________、__________、__________和__________。（有限序列、有穷性、 确定性、可行性、输入、输出） 15、算法的 _______性是指算法必须能够在执行有限个步骤之后结束，并 且每个步骤都必须在有穷的时间内完成。（有穷性） 16、算法的 ________性是指算法中的每一个步骤必须是有明确定义的，不允 许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟 一的一条执行路径，即只要输人是相同的就只能得到 ____________的输出结果。（确定性、相同） 17、算法的 ____________性又称为算法的能行性，是指算法中描述的操作 是可以通过已经实现的基本运算执行有限次来实现。（可行性） 18、判断一个算法的好坏主要以下几个标准： ________、________、________、_________。（正确性、可读性、健壮性、时间效率和空间效率） 19、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机 _________的长短和 ___________________的大小。（运行时间、所占据空间） 20、空间复杂度（ SPace ComPlexity ）也是度量一个算法好坏的标准，它 所描述的是算法在运行过程中所占用 _____________的大小。（存储空间） 三、判断题 1．顺序存储方式只能用于存储线性结构。（×） 2．数据元素是数据的最小单位。（×） 3．算法的优劣与算法描述语言无关，但与所用计算机有关。( × ) 4．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。() 5．数据的逻辑结构是指各元素之间的逻辑关系，是根据用户需要而建立的。 6．数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、 结点、数据域。（） 7．数据的物理结构是指数据在计算机中实际的存储形式。（） 8．具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。 9．算法实际上就是程序，程序也一定是算法。 ( × ) 10.在顺序存储结构中，有时也存储数据结构中元素之间的关系。( × ) 11.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ×) 12.数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。() 13.数据的逻辑结构说明数据元素之间的顺序关系 , 它依赖于计算机的储存结构。 ( × ) 14.判断一个算法的好坏主要以下几个标准：正确性、有穷性、健壮性和可 行性。 ( ×) 15．算法的时间复杂度 T（ n）=O(f(n)) 表示随问题规模 n 的增大，算法执行 时间的增长率与函数 f(n) 的增长率相同。（） 四、综合题 1．用大 O形式表示下面算法的时间复杂度： for（i=0；i＜m；i十十） for（j=0；j＜n；j＋＋） A[i][j]=i*j； 2．写出下面算法的时间复杂度： i＝ 0； s=0； while(s＜n） ｛i++; s+=i; ｝ 3．写出以下算法的时间复杂度： for（i ＝0; i＜m; i＋＋） for （j ＝ 0 ; j＜t; j＋＋） c[i][j]=0； for （i=0 ；i ＜m；i ＋＋） for（j=o; j for（ k=0；k＜n；k＋＋） c［i ］［ j ］＋＝ a［i ］［k］*b[k][j]; 4．写出下面算法的时间复杂度： i=1; while （i ＜＝ n） i=i*3; 5．求下面函数中各条语句的频度和算法的时间复杂度： prime （int n） ｛ int i＝2； while ((n％i）！=0＆＆i＜sqrt(n) ) i++; if（i ＞sqrt(n) ) printf（?％ d is a prime number.＼n?，n）； else printf（?％ d is not a prime number.＼n?，n）；｝ 1.该算法的时间复杂度为： O(m×n) 。 2.该算法的时间复杂度为： O( n ) 3.该算法的时间复杂度为： O(m×n×t) 。 4.该算法的时间复杂度为： log 3(n) 。 5.该算法的时间复杂度为： O( n ) 。 6．将下列函数，按它们在n→∝时的无穷大阶数，从小到大排序。 n, n-n3+7n5 , nlogn, 2 n/2 , n 3, logn, n 1/2 +logn, (3/2) n, ,n!, n2+logn 从小到大排列为： logn, n1/2 +logn, n, nlogn, n2+logn ， n3, n-n3+7n5, 2n/2 , (3/2) n, n!, 第二章线性表 一、选择题 1 ．在一个长度为 n 的顺序表中删除第 i 个元素（ 0 动( ) 个元素。 A．n-i B． n-i+1C．n-i-1D．i+1 2．从一个具有 n 个元素的线性表中查找其值等于x 的结点时，在查找成功的情况下，需平均比较 ( )个元素结点。 A．n/2B． n C．(n-1)/2D．(n +1)/2 3．对一个具有 n 个元素的线性表，建立其单链表的时间复杂度为 ( ) 。 A．O(n)B． O(1)C．O(n2）D．O（long 2n）4．线性表采用链式存储时，其地址 ( ) 。 A．必须是连续的B．一定是不连续的 C．部分地址必须连续D．连续与否均可以 5．在一个具有 n 个结点的有序单链表中插人一个新的结点，使得链表仍然 有序，该算法的时间复杂度是 ( ) 。 A ．O（long 2n） B ．O（l ） C D． O（ n） ．O（ n2） 6．线性表是 ( ) 。 A．一个有限序列，可以为空B．一个有限序列，不可以为空 C ．一个无限序列，可以为空D．一个无限序列，不可以为空 7．在一个长度为 n 的顺序表中，向第 i个位置（ 0 一 1＜n＋1）插入一个新元素时，需要向后移动 ( )个元素。 A ． n-i B． n-i ＋1C． n－ i －1 D ． i ＋ 1 8．如果某链表中最常用的操作是取第i个结点及其前驱，则采用 ( )存储方式最节省时间。 A ．单链表B．双向链表C．单循环链表D．顺序表 9．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第 6 个元素的存储地址是（）。 A ．98B．100C．102D．106 10．在顺序存储的线性表（ a1⋯⋯ a n）中，删除任意一个结点所需移动结点 的平均移动次数为 ( ) A．n B．n／2C．(n-1)/2D．（n＋l）/2 11．在线性表的下列存储结构中，读取第i 个元素花费的时间最少的是（）。 A．单链表B．双链表C．循环链表D．顺序表12．若某链表中最常用的操作为在最后一个结点之后插入一个结点和删除 最后一个结点，则采用（）存储方式最节省时间。 A ．双链表 B ．单链表 C ．单循环链表 D．带头结点的双循环链表 13．在单链表中删除指针p 所指结点的后继结点，则执行（）操作。 A．p->next=p->next->next B．p->next=p->next C．p=p->next->next D．p=p->next; p->next=p->next->next 14．在一个单链表中，已知q 所指结点是 p 所指结点的前驱，若在q 和 p 之间插入 s 所指的结点，则执行（）操作。 A．s->next=p->next;p->next=s; B．q->next=s; s->next=p; C．p->next=s->next;s->next=p; D．p->next=s; s->next=q; 15．在单链表中附加头结点的目的是为了（）。 A．保证单链表中至少有一个节点 B．标识单链表中首结点的位置 C．方便运算的实现 D．说明单链表是线性表的链式存储 16．循环单链表的主要优点是（）。 A．不再需要头指针了 B．从表中任意一个结点出发都能扫描到整个链表 C．已知某个结点的位置后，能够容易找到它的前驱 D．在进行插入、删除操作时，能更好地保证链表不断开 17．非空的循环单链表L 的尾结点 p 满足（）。 A．p->next=NULL B．p=NULL C．p->next=L D．p=L 18．在双向循环链表中 , 在 p 指针所指向的结点前插入一个指针 q 所指向的新 结点 , 其修改指针的操作是 ( ) 。 注 : 双向链表的结点结构为 (prior,data,next)。供选择的答案： A．p->prior=q；q->next=p；p->prior->next=q；q->prior=q； B．p->prior=q；p->prior->next=q; q->next=p；q->prior=p->prior； C． q->next=p ； q->prior=p->prior；p->prior->next=q; p->prior=q; D． q->prior=p->prior；q->next=p；p->prior=q；p->prior=q； 19．在双向链表存储结构中，删除p 所指的结点时须修改指针（）。 A． p->prior->next=p->next;p->next->prior=p->prior; B． p->prior=p->prior->prior; p->prior->next=p;(删p的前趋) C． p->next->prior=p;p->next=p->next->next; D． p->next= p->prior->prior; p->prior= p->next->next; 二、填空题 1．线性表（ Linear List ）是最简单、最常用的一种数据结构。线性表中的元素存在着 __________的相互关系。（一对一） 2．线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有且仅有一个__________，除终端结点外，其他每个元素有且仅有一个 ______。 3．线性表是 n（n>=0）个数据元素的 ________。其中 n 为数据元素的个数，定义为线性表的 __________。当 n 为零时的表称为 _________。 4．所谓顺序表（ Sequential LISt ）是线性表的 __________，它是将线性表中的结点按其 ____________依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在 ____________的存储单元中。 5．单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些_______的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的 _________的位置上，它们在物理上可以是一片连续的存储单元，也可以是 __________的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的。 6．线性表的链式存储结构的每一个结点（ Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的 _________；另一部分用来存放元素的指向直接后继元素的指针( 即直接后继元素的地址信息) ，称为 ________或____________。 7．线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种 _________存储结构，又称为 __________。8．如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了 ______________。 9．为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了___________。 10．双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是p_______。 11．在单链表中，删除指针P 所指结点的后继结点的语句是____________。12．在双循环链表中，删除指针P 所指结点的语句序列是P->prior->next＝p->next 及__________。 13．单链表是 ___________的链接存储表示。 14．可以使用 ___________表示树形结构。 15．向一个长度为 n 的向量的第 i 个元素 (l ≤i ≤n+1）之前插人一个元素时，需向后移动 __________个元素。 16．删除一个长度为 n 的向量的第 i 个元素（ l ≤i ≤n）时，需向前移动 _______个元素。 17．在单链表中，在指针P 所指结点的后面插人一个结点S 的语句序列是__________。 18．在双循环链表中，在指针 P 所指结点前插人指针S 所指的结点，需执行语句_______。 19．取出广义表 A＝（（ x，（a，b，c，d））中原子 c 的函数是 _________。20．在一个具有 n 个结点的有序单链表中插人一个新结点并使之仍然有序的时间复杂度为 _______________。 21．写出带头结点的双向循环链表L 为空表的条件 ________________。 22．线性表、栈和队列都是_________________结构。 23．向栈中插人元素的操作是先移动栈_____________针，再存人元素。 1.一对一 2.直接前驱、直接后继 3.有限序列、长度、空表 4.顺序存储结构、逻辑顺序、地址相邻 5.任意、任意、不连续、逻辑关系 6.数据域、指针域、链域 7.非顺序、非顺序映像 8.循环链表 9.双向链表 10.所指向的结点本身 11.P->next=p->next->next 12.P->next->prior=P->prior 13.线性表 14.双链表 15.n-i+1 16.n-i 17.S->next=P->next; P->next=S 18.p->prior->next=S; s->prior=p->prior; s->next=p; p->prior=s; 19.head(tail(tail((head(tail(head(A)))))) 20.O(n) 21.(L==L->Next) && (L==L->Prior) 22.线性 23.顶 三、判断题 1．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ×) 2．在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。( ×) 3．顺序存储的线性表不可以随机存取。( ×) 4．单链表不是一种随机存取结构。（） 5．顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置 无关。(×) 6．顺序存储结构是动态存储结构，链式存储结构是静态存储结构。( ×) 7．线性表的长度是线性表所占用的存储空间的大小。( ×) 8．双循环链表中，任意一结点的后继指针均指向其逻辑后继。( ×) 9．线性表的惟一存储形式是链表。( × ) 1.错误：链表存储中，结点之间可以连续也可以不连续，但结点内部是连 续的。 2.错误：头指针指向头结点而不是数据结点。 3.错误：顺序存储的线性表可以随机存取。 4.正确。 5.错误。 6.错误：顺序存储结构是静态存储结构，链式存储结构是动态存储结构。 7.错误：先行表的长度是线性表中结点的个数。 8.错误：注意最后一个结点。 9.错误：也可以有顺序存储的形式。 第三章栈和队列 一、选择题 l．一个栈的序列是： a，b，c，d，e，则栈的不可能输出的序列是（）。A．a，b，c，d，e B ．d，e，c，b，a C．d，c，e，a，b D ．e，d，c，b， a 2 ．若一个栈的输人序列是 1，2，3，⋯， n，输出序列的第一个元素是 n，则第 k 个输出元素是（）。 A ． k B．n-k-1 C ．n-k+1 D ．不确定 3．判定一个栈 S（最多有 n 个元素）为空的条件是（）。 A ．S->top ！＝ 0B．S->top= =0 C．S->top!=n D．S->top= =n 4．判定一个栈 S（最多有 n 个元素）为满的条件是（）。 A ．S->top!=0 B．S->top= =0C．S->top!=n D．S->top= =n 5．向一个栈顶指针为top 的不带头结点的链栈中插人一个*S 结点的时候，应当执行语句（）。 A ．top->next=S ； B ．S->next=top ； top=S； C ．S->next ＝top->next ；top->next ＝S；D．S->next ＝top ；top ＝S->next ；6．向一个带头结点、栈顶指针为top 的链栈中插人一个 *S 结点的时候，应当执行语句（）。 A ．top->next=S ；B．S->next=top；top=S； C． S->next=top->next；top->next=S；D．S->next=top；top=S->next；7．判定一个队列 Q（最多有 n 个元素）为空的条件是（）。 A ．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n C．Q->rear = = Q->front D．Q->rear +1= = Q->front 8．判定一个队列 Q（最多有 n 个元素）为满的条件是（）。 A．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n C ．Q->rear = = Q->front D．Q->rear +1= = Q->front 9．判定一个循环队列Q（最多有 n 个元素）为空的条件是（）。 A．Q->rear = = Q->front B．Q->rear = = Q->front＋l C ．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n 10．判定一个循环队列Q（最多有 n 个元素）为满的条件是（）。 A．Q->rear = = Q->front B．Q->rear = = Q->front＋l C．Q->front= =(Q->rear +1) ％n D ． Q->front= =(Q->rear -1) ％n 11．在一个链队列中，假定 front 和 rear 分别为头指针和尾指针，则插入一个 结点 *S 的操作是（）。 A．front＝front->next B．S->next=rear；rear=S C．rear->next=S ；rear=S D．S->next=front；front＝S 12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结 点的操作是（）。 A． front=front->next B．rear=rear->next C ． rear->next=front D．front->next＝rear 13 ．栈与队列都是（）。A．链式存储的线性结构B．链式存储的非线性结构C．限制存取点的线性结构D．限制存取点的非线性结构 14 ．若进栈序列为l ， 2， 3， 4，则（）不可能是一个出栈序列。 A ．3，2，4，1 B ．l ， 2， 3，4C．4，2， 3，1D．4，3，2，l 15．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据 缓冲区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走 数据打印。该缓冲区应该是一个（）结构。 A ．堆栈B．队列C．数组D．线性表 1.C 2. C 3. B 4.D 5.B 6.C 7. C 8. A 9.A10.C 11.C12. A13. C14. C15. B 二、填空回 1．栈（ stack ）是限定在 ________一端进行插人或删除操作的线性表。在栈中， 允许插人和删除操作的一端称为 __________，而另一端称为 _________。不含元 素的栈称为 _______。 2．在栈的运算中，栈的插人操作称为 ________或 ________，栈的删除操作称为_________或 __________。 3．根据栈的定义，每一次进栈的元素都在原___________之上，并成为新的 __________；每一次出栈的元素总是当前的_____________，因此最后进栈的元 素总是 __________，所以栈也称为 ___________线性表，简称为 ____________表。4．栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有 __________和_________________两种存储结构，分别称为 ______________和 ___ 5．当栈满的时候，再进行人栈操作就会产生____________，这种情况的溢出称 为___________；当栈空的时候，如果再进行出栈操作，也会 _____________，这种情况下的溢出称为 __________________。 6．栈的链式存储结构简称为 ____________，是一种 __________________。7．人们日常计算用到的表达式都被称为 ____________，这是由于这种算术表达 式的运算符被置于两个操作数中间。 8．计算机中通常使用 ___________，这是一种将运算符置于两个操作数后面的算 术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为 _____________ 9．队列（ Queue）也是一种 ___________，但它与栈不同，队列中所有的插人均 限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端 称为 _________，允许删除的一端称为 _______________。 10．队列的特点是 _________，因此队列又被称为 _______________．的线性表，或称为 _________________表。 11．队列的 _________又称为 __________，是用一组地址连续的存储单元依次 存放队列中的元素。 12．由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行， 因此需要设置两个指针分别指向 __________和 __________，这两个指针又称为 __________和_____________。 13．循环顺序队列（ Circular Sequence Queue）经常简称为 ___________，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接 起来形成一个环形表。首尾相连的状态是通过数学上的 _________________ 来实现的。 14．在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己 的时候，则称这个函数为，也称为 ____________。函数直接调用自己，则称为 __________；当一个函数通过另一个函数来调用自己则称为_________________。15．在循环队列中规定：当 Q->rear= =Q->front 的时候循环队列为 ___________， 当（ Q->rear+1 ）％ MAXSIZE＝front的时候循环队列为____________________。16．用链表方式表示的队列称为____________________。 17．已知栈的输人序列为1，2，3，⋯， n，输出序列为 a1，a2，⋯， an，符合 a2= =n 的输出序列共有 __________________。 18．一个栈的输人序列是 12345，则栈的输出序列为43512 是________（填是否可能）。 19．一个栈的输人序列是 12345，则栈的输出序列为12345 是_________（填是 否可能）。 20．设 sq[1 ．．maxsize] 为一个顺序存储的栈，变量top 指示栈顶元素的位置， 则作入栈操作的条件是 ______________。 21．设 sq[1 ．．maxsize] 为一个顺序存储的栈，变量top 指示栈顶元素的位置， 如果把栈顶元素弹出并送到X 中，则需执行语句 ______________。 22．栈的特性是 __________________。 23．对栈进行退栈时的操作是先取出元素，后移动_________。 24．设 s[1 ．．max]为一个顺序存储的栈，变量 top 指示栈顶位置，栈为满的条 件是 ____。 25．设链栈的栈顶指针为top ，则栈非空的条件是 ___________。 26．已知循环队列用数组 data[1...n] 存储元素值，用 f ，r 分别作为头尾指针，则当 前元素个数为 ____________。 27．在一个循环队列中，队首指针指向队首元素的________位置。（前一个或后 一个） 28．队列中允许进行删除的一端称为_______________。 29．链队列实际上是一个同时带有头指针和尾指针的单链表（ 1．．n），尾指针指 向该单链表的第 ___________个元素。 30．设双向链表链列为 lq ，lq 的头指针为 lq.Front ，尾指针为 lq.Rear ，则队列为 空的条件是 ____________。 31．从循环队列中删除一个元素，其操作是先取出一个元素，后移动 ____________ 32．队列中允许进行插入的一端称为_________。 1.表尾、栈顶、栈底、空栈 2.进栈、入栈、退栈、出栈 3.栈顶元素、栈顶元素、栈顶元素、最先出栈、后进先出、LIFO 4.顺序、链式、顺序栈、链栈 5.溢出、上溢、溢出、下溢 6.链栈、特殊的单链表 7.中缀表达式 8.后缀表达式、波兰式 9.特殊的线性表、队尾、队头 10.先进先出、先进先出、 FIFO 11.顺序存储结构、顺序队列 12.队头元素、队尾元素、队头指针、队尾指针 13.循环队列、取模运算 14.递归函数、自调用函数、直接递归调用、间接递归调用 15.空、满 16.链队列 18.不可能的 19.可能的 20.top!=maxsize 21.x=sq[top]; top=top-1 22.先进后出 23.栈顶指针 24.top==max 25.top!=nil 26.(n+r-f)mod n 27.前一个 28.队首 29.n 30.lq->front==lq->rear 31.栈顶指针 32.队尾 三、判断题 1．栈和队列都是限制存取点的线性结构。（） 2．不同的入栈和出栈组合可能得到相同输出序列。（） 3．消除递归一定要用栈。（） 4．循环队列是顺序存储结构。（） 5．循环队列不会产生溢出。（） 6．循环队列满的时候rear= =front。（） 7．在对链队列（带头结点）做出队操作时不会改变front指针的值。（） 1.正确。 2.错误：不同的入栈和出栈组合得到不同输出序列。 3.错误：某些情况如尾递归可以转换为递推的形式。 4.正确。 5.错误：循环队列不会产生假溢出。 6.错误。 7.正确。 四、综合题 1．设有 4 个元素 A、B、C 和 D 进栈，给出它们所有可能的出栈秩序。 可能的出栈序列：（共 14 个） ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCA CBAD CBDA CDBA DCBA 不可能的出栈序列：（共 10 个） ADBC BDAC CABD CADB CDAB DABC DACB DBAC DBCA DCAB 一、选择项 l ．空串与空格串（）。 A．相同B．不相同C．可能相同D．无法确定 2．设有两个申 S1与 S2，求串 S2在 S1中首次出现位置的运算称作（）。 A．连接B．求子串C．模式匹配D．判子串3．串与普通的线性表相比较，它的特殊性体现在（）。 A．顺序的存储结构B．链接的存储结构 C ．数据元素是一个字符D．数据元素可以任意 4．设有串 S=‘ Computer’，则其子串的数目是（）。 A．36B．37C．8D．9 1.B 2.C 3.C 4.B 二、境空题 1．串是由零个或多个字符组成的____________。通常记作：s＝? c1，c2，⋯，cn? (n=>0) ，其中， S 称为 ________；串中的 Ci （1<=i<=n ）可以是字母、数字字格或其他字符。用双引号括起来的部分是_________．即串 S 的内容。 2．串中字符的个数称为串的________。 3．不含有任何字符的串称为_________，它的长度为 ___________。 4．由一个或多个空格构成的串称为____________，它的长度为 ___________。 5．串中任意多个连续字符组成的子序列称为该串的____________；包含___________的串称为主串。 6．字符在序列中的序号称为该字符在串中的________________。 7．两个字符串相等是指两个字符串的，也就是说这两个字符串不仅 __________，而且对应位置上的字符也。 8．两个串的比较实际上是_________的比较。两个串从第一个位置上的 字符开始进行比较，当第一次出现_____________大的串为大，若比较过程中出 现一个字符串结束的情况，则另一个串为 _________________。 9．串的 _______________就是把串所包含的字符序列，依次存人连续的存储单元中去。 10．有些计算机系统中为了充分利用存储空间，允许一个存储单元可以 存放多个字 符，串的这种存储方式是一种 __________________。 11．串的 ______________是以存储单元为存储单位，一个存储单元中只存放 __________。在这种情况下，即使一个存储单元能存放多个字符，这时候 也只存放 ________________。 12．串在非紧缩方式下，串长度的存储是隐式的，__________即串的长度。 13．一些计算机是以字节为存取单位，恰好一个字符占用一个字节，自 然形成了每个存储单元存放__________的分配方式，这种方式就是一种 __________。这种方式一般不需要存放 ____________的存储单元，而需要以程 序中各变量值所、的字符为结束符。 14 ．串的链式存储结构是将存储区域分成一系列大小相同的结点，每个结点有两个城： ____________域和 ________域。其中 ___________域用于存放数据， ___________域用于存放下一个结点的指针。 15．子串定位StrIndex (s，t)，也称为_______，是返回串t 在 s 主串中的位置。 1.有限序列、串名、串值 2.长度 3.空串、零 4.空格串、空格的个数 5.子串、子串 6.位置 7.值相等、长度相等、相等 8.ASCII 码、 ASCII 码、较大者 9.顺序存储结构 10.紧缩式存储方式 11.非紧缩存储方式、一个字符、一个字符 12.串所占用的存储单元的个数 13.一个字符、单字节存储方式、串长、不包含 14.数据、指针、数据、指针 15.模式匹配 三、判断回 1．子串是主串中字符构成的有限序列。（×） 2．KMP算法的最大特点是指示主串的指针不需要回溯。（） 3．串中的元素只能是字符。（） 4．串中的元素只可能是字母。（×） 5．串是一种特殊的线性表。（） 6．串中可以包含有空白字符。（） 7．串的长度不能为零。（×） 8．两个串相等必有串长度相同。（） 9．两个串相等则各位置上字符必须对应相等。（） 习题五 一、选择题 l．数组常用的两种基本操作是（）。 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))的表头是（）。 A．（）B．a C．（ a）D．（（a））7．广义表（（ a））的表尾是（）。 A．（）B．a C．（a）D ．（（a））8．广义表（（ a），a）的表头是（）。 A．（）B．a C．（ a）D．（（a））9．广义表（（ a），a）的表尾是（）。 A．( )B．a C．（a）D．（（a））10．广义表（ a， b， c）的表头是（）。 A．a B．（a）C．a，b D．（b，c）11．广义表（ a， b， c）的表尾是（）。 A ．b，c B ．（b，c）C．a．b，c D．（a，b，c） 12．广义表 A 满足 Head（） = Tail （），则 A 为（）。 A．（）B．（（））C（（），（））D．（（），（），（）） 1.D 2.B 3.B 4.B 5.A 6.C 7.A 8.C 9.C10.A 11. B 12. B 二、填空题 1．数组（ array ）是 n（ n＞ 1）个 __________的有序组合，数组中的数据是按顺序存储在一块 ______________的存储单元中。 2．数组中的每一个数据通常称为_____，________用下标区分，其中下标的个数由数组的 ________________决定。 3．由于计算机内存中的存储单元是一个一维的存储结构，因此对于多维数组要想按顺 序存储到计算机存储单元中就必须有一个排列顺序问题。对于二维数组，有两种排列形式：一种是 ___________；另一种是 _____________。 15/ 51 相同值元素或零元素在矩阵中分布具有一定规律的矩阵，我们称之为 ___________；而对于那些零元素数目远远多于非零元素数目，并且非零元素 的分布没有规律的矩阵称为 _____________。 5．在一个 n 阶方阵 a 中，若元素满足性质： a ij＝ a ji（0<=i ，j<=n-l ），则称A 为 n 阶_______。 6．采用顺序存储结构表示三元组表 (Trope Table) ，以实现对稀疏矩阵的一种压缩存储形式，称为 ______________，简称 ________________表。 7． ________________运算是矩阵运算中最基本的一项，它是将一个 m*n 的矩阵变成另外一个 n*m 的矩阵，同时使原来矩阵中元素的行和列的位置互换而值保持不变。 8．广义表是 n（ n>=0）个元素的序列。记作： A＝（ a1， a2，⋯， an），其中， A 是广义表的 _________， n 是它的 _________，当 n=0 的时候称为 ____________。 9．在一个非空的广义表中，其元素a i可以是某一确定类型的单个元素，称 为__________，也可以又是一个广义表，称为 _____________________。 10．广义表的定义是一种递归的定义，广义表是一种递归的数据结构。当广 义表非空的时候，称第一个元素a1为广义表 A 的 __________，称其余元素组成的表（ a2，a3，⋯， an）是 A 的 ______________。 11．广义表的深度一般定义为广义表元素_________，或者说是广义表 ___________。利用递归的定义，广义表的深度就是所有子表中 _________________________。 1.相同类型数据、地址连续 2.数组元素、数组元素、维数 3.以行序为主、以列序为主 4.特殊矩阵、稀疏矩阵、特殊矩阵、稀疏矩阵 5.对称矩阵 6.三元组顺序表、三元组 7.矩阵转置 8.名称、长度、空表 9.原子、子表 10.表头、表尾 11.最大的层数、括号的重数、最大深度加 1 三、判断题 1．十字链表不是顺序存储结构。（） 2．三元组表不是一个随机存取结构。（） 3．稀疏矩阵压缩存储后，必然会失去随机存取功能。（） 4．若一个广义表的表头为空表，则此广义表也为空表。（） 5．广义表是线性表的推广，是一类线性数据结构。（） 6．任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广 义表。（） 7．一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和 n 的值互换，则就完成了Am*n的转置运算。（） 8．数组中每个元素必定具有相同的数据类型。（） 9．线性表是广义表的特例。（） 10．如果广义表中的每个元素都是原子，则广义表便成为线性表。（）11．广义表中原子个数即为广义表的长度。（） 12．广义表最大子表的深度为广义表的深度。（） 13．广义表中元素最大的层数称为广义表的深度。（） 14．广义表是一种多层次结构。（） 15．广义表是一种线性结构。（） 16．广义表是一种共享结构。（） 17．广义表是一种递归结构。（） 18．广义表是一种单链表结构。（） 1.正确：十字链表是链接存储结构。 2.正确：具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构，三元组表存储矩阵的时候，要访问第 i 行 j 列元素必须扫描三元组表，显然查找三元组表前面的元素与后面元素所耗费的时间不同，因此三元组表不是一个随机存取结构。 3.正确：随机存取结构是指存取任一元素的时间相等这一特点的存储结构，对稀疏矩阵压缩存储所用的存储结构是十字链表和三元组，而这两种存储 结构都不是随机存取结构。 4. 错误：如广义表L=((),(A, B))为非空，而表头为空表。 5.错误：广义表是线性表的推广，是一类非线性数据结构。 6.正确：表尾的定义是除表头元素以外其余元素（可以为空）构成的表，所以必定是广义表。 7.错误：应该在互换行列后再按照行优先重新存储。 8.正确。 9.正确。 10.正确。 11.错误：广义表中元素个数为广义表的长度。 12.错误：广义表最大子表的深度加 1 为广义表的深度。 13.正确。 14.正确。 15.错误：广义表是一种非线性结构。 16.正确。 17.正确。 18.正确：注意单链表结构不一定是线性的。 第六章树和二叉树 一、选择题 l ．在二叉树后序遍历中，任一个结点均在其子女结点后面，这种说法（）。 A．正确B．不正确C．无法判断D．以上均不对2．在二叉树先序遍历中，任一个结点均在其子女结点前面，这种说法（）。 A．正确B．不正确C．无法判断D．以上均不对3．设深度为 h 的二叉树上只有叶子结点和同时具有左右子树的结点，则此 类二叉树中所包含的结点数目至少为（）。 A ．2h B．2h C．2h＋1D．2h-l 4．二叉村第 k 层上最多有（）个结点。 A．2k B．2k-1C．2k-1D．2k+1 5．二叉树的深度为 k，则二叉树最多有（）个结点。 A ． 2k B．2k-1C．2k-1D．2k -1 6．设某一二叉树先序遍历为abdec，中序遍历为 dbeac，则该二叉树后序遍 历的顺序是（）。 A．abdec B．debac C．debca D．abedc 7．设某一二叉树中序遍历为badce，后序遍历为 bdeca，则该二叉树先序遍 历的顺序是（）。 A．adbec B．decab C．debac D．abode 8．将一棵树 T 转换为一棵二叉树T2，则 T 的先序遍历是T2 的（）。 A．先序B．中序C．后序D．无法确定 9．将一棵树 T 转换为一棵二叉树T2，则 T 的后序遍历是T2 的（）。 A．先序B．中序C．后序D．无法碉定 l0 ．树最适合于用来表示（）。 A．线性结构的数据B．顺序结构的数据 C．元素之间无前驱和后继关系的数据 D．元素之间有包含和层次关系的数据 11．二叉树的叶子结点在先序、中序和后序遍历过程中的相对秩序（）。 A．发生改变B．不发生改变 C．无法确定D．以上均不正确 12．设一棵二叉树度为 2 的结点数是 7，度为 1 的结点数是6，则叶子结点数是（）。 A． 6B． 7C．8D． 9 13．用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序 存放在一维数组 R[1．． n] 中，若结点 R[i] 有左孩子，则其左孩子是（）。 A． R[2i-1]B．R[2i+1]C．R[2i]D． R[2/i] 144．用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺 序存放在一维数组 R[1．．n] 中，若结点 R[i]有右孩子，则其右孩子是（）。 A．R[2i-1]B．R[2i ＋ l]C．R[2i]D．R[2/i] 15．一棵非空的二叉树，先序遍历与后序遍历正好相反，则该二叉树满足（）。 A．无左孩子B．无右孩子 C．只有一个叶子结点D．任意二叉树 16．设 a、b 为一棵二叉树的两个结点，在后序遍历中， a 在 b 前的条件是（）。 A． a 在 b 上方B．a 在 b 下方 C． a 在 b 左方D．a 在 b 右方 17．线索二叉树是一种（）。 A．逻辑结构B．线性结构 C．逻辑和线性结构D．物理结构 18．N 个结点的线索二叉树中，线索的数目是（）。 A． N-1B．N＋1C．2ND．2N－1 19．权值为｛l ，2，6，8｝的四个结点构成的哈夫曼树的带权路径长度是（）。 A．18B． 28C．19D．29 20．实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是 二叉村采用（）存储结构。 A．二叉链表B．广义表存储结构 C．三叉链表D．顺序存储结构 21．对一个满二叉树， m个树叶， k 个分枝结点， n 个结点，则（）。 A． n＝ m＋ 1 B ． m+1=2n C ．m＝k-1D．n=2k+1 23．具有五层结点的二叉平衡树至少有（）个结点。 A． 10B． 12C．15D． 17 24．设 n，m为一棵二叉树上的二个结点，在中序遍历时，n 在 m前的条件是（）。 A． n 在 m右方B． n 是 m祖先 C． n 在 m左方D． n 是 m子孙 25．线索二又树是一种（）结构。 A．逻辑B．逻辑和物理C．物理D．线性 26．将一棵有 100 个结点的完全二又树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49 的结点的左孩子编号为（）。 A．98B．99C．50D．48 二、填空题 1．树 (Tree) 是 n(n ≥ 0) 个结点的 _____________集。 2．任何一个非空树中：有且仅有一个特定的结点，称为该树的 ______________的结点， ___________结点之外的其余结点可分为 m(m≥ 0) 个互不相交的有限集合 T1， T2，⋯， Tm，且其中每一个集合又是一棵树，称之为 __________的______________。 3 ．树的 __________是指一个数据元素及指向其子树的分支。通常通 过一个 __________来描述，在树型表示中，用一个圆圈及短线表示。 4．结点的度是指结点所拥有的 ________________。 5．树内各结点度的 ___________________为树的度。 6．度大于 0 的结点称为 ________________或______________________。 7．____________称为叶子结点，简称为叶子，又称作终端结点。 8．一个结点的 ____________，或者说一个结点的 ____________称为该结点的孩子结点，简称为孩子。 9．一个结点称为其后继结点（即孩子结点）的 ______________。 10．一个结点的子树中的任一结点都称为该结点的 _______________。 11．从根到该结点所经分支上的所有结点称为该结点的 _____________。 习题课 填空 1、对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为，双亲结点的编号为。 2、向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。 3、在一棵二叉树中，若双分支结点数为5个，单分支结点数为6个，则叶子结点数 为个。 4、为了实现折半查找，线性表必须采用方法存储。顺序 5、一种抽象数据类型包括数据对象和。 6、在以L为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为__________和_______。 7、数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。 8、队列的插入操作在进行，删除操作在进行。 9、二叉搜索树的中序遍历得到的结点序列为____ ____。 10、在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 11、栈的特点是。 12、在单链表中，除了首元结点外，任一结点的存储位置由。 13、在一个具有n个顶点的无向图中，要连通所有顶点则至少需要条边。 14、深度为k（设根的层数为1）的完全二叉树至少有个结点，至多 有个结点。 15、一棵深度为6的满二叉树有个分支结点和个叶子结点。 16、一个算法的效率可分为效率和效率。 17、队列的特点是。 18、一棵深度为5的满二叉树中的结点数为个。 19、在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。 简答题 1、已知一组元素为（38，26，62，94，35，50，28，55），画出按元素排列顺序输入生成的一棵二叉搜索树。 答: 2、假设有二维数组A[0..5,0..7]，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，计算： （1）末尾元素A57的第一个字节地址为； （2）若按列存储时，元素A47的第一个字节地址为。 (3) 数组A的体积（存储量）； (4) 若按行存储时，元素A14的第一个字节地址为。 第1章绪论 1、填空题 1.常见的数据结构有集合，_线性__结构，__树形___结构，__图形__结构等四种。 2.常见的存储结构有__顺序存储_______结构，__链式存储____结构等两种。 3.数据的基本单位是_数据元素___，它在计算机中是作为一个整体来处理的。 4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，__线性结构____和__非线性结构___。 2、选择题 1. 算法的计算量的大小称为计算的（B）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（C） A．问题的规模 B. 待处理数据的初态 C. A和B D. 以上都不对 3.计算机算法指的是（1）（c），它必须具备（2）（B）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4. 下面关于算法说法错误的是（D） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 3、应用题 1、给出以下算法的时间复杂度. void fun(int n) { int i=1,k=100; while(i 数据结构练习题（一） 一、单选题 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( )。 A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中( )是非线性结构。 A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(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 +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.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个。 A．1 B．2 C．3 D．4 9.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 二、填空题 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为 __________个，树的深度为___________，树的度为_________。 4.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 5.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 6.AOV网是一种___________________的图。 7.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 8.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数 的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 9.在快速排序、堆排序、归并排序中，_________排序是稳定的。 三、计算题 1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data next 2. 线性表 1.下列有关线性表的叙述中，正确的是（A）。 A）线性表中元素之间的关系是线性关系 B）线性表中至少有一个元素 C）线性表中的任一元素有且仅有一个直接前趋 D）线性表中的任一元素有且仅有一个直接后继 2.下述哪一条是顺序存储结构的优点？（A） A）存储密度大B）插入方便 C）删除方便D）可方便地用于各种逻辑结构的存储表示 3.在一个长度为n的顺序表中，在第i个元素（1<=i<=n）之前插入一个新元素时需向后移动（D）个元素。 A）1 B）n-i C）n-i-1 D）n-i+1 4.如果某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，那么采用（A）存储方式最节省时间。 A）顺序表B）单链表 C）双链表D）循环链表 5.对顺序存储的线性表，设其长度为n，且在任何位置上插入或删除操作都是等概率的。则插入一个元素时平均要移动表中的（A）个元素。 A）n/2 B）(n+1)/2 C）(n-1)/2 D）n 6.下述哪一条是顺序存储结构的缺点？（C） A）存储密度太大 B）随机存取 C）一般要估计最大的需要空间 D）只能应用于少数几种逻辑结构的存储表示 7.在单链表中，增加头结点的目的是（C）。 A）使单链表至少有一个结点 B）标志表中首结点的位置 C）方便运算的实现 D）说明单链表是线性表的链式存储表示 8.单链表不具有的特点是（A）。 A)可随机访问任一元素B)插入和删除不需要移动元素 C)不必事先估计存储空间D)所需空间和线性表长度成正比 9.循环链表的主要优点是（D）。 A）不再需要头指针了 B）已知某个结点的位置后，能够容易找到他的直接前趋 C）在进行插入、删除运算时，能更好的保证链表不断开 D）从表中的任意结点出发都能扫描到整个链表 10.链表对于数据元素的插入与删除是（B）。 A）不需移动结点，不需改变结点指针 B）不需移动结点，只需改变结点指针 C）只需移动结点，不需改变结点指针 D）既需移动结点，又需改变结点指针 数据结构习题集（自编） 第一章绪论 一、选择题 1．数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之 间的（）和运算的学科。 A．结构B．关系C．运算D．算法 2．在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B ．紧凑结构和非紧凑结构C．线性结 构和非线性结构 D ．逻辑结构和存储结构 3．线性表的逻辑顺序和存储顺序总是一致的，这种说法（）。 A．正确B．不正确C．无法确定D．以上答案都不对4．算法分析的目的是（）。 A．找出算法的合理性B．研究算法的输人与输出关系 C．分析算法的有效性以求改进D．分析算法的易懂性 5.算法的时间复杂度取决于（） A．问题的规模 B 待处理数据的初态 C. A 和 B 6．一个算法应该是（）。 A．程序B．问题求解步骤的描述 C ．要满足五个基本特性D．A和C. 7.下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法与为该问题编写的程序含义是相同的 C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B.链表 C.哈希表 D.栈 9．在下面的程序段中，对 x 的赋值语句的频度为（） for （ i=0;i 数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i 第一章概论 一、选择题 1、研究数据结构就是研究（ D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i O(m+n) 6、算法是（ D ）。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（A ）。 i=s=0; while(s 第一章 一、填空题 1 数据元素是数据的基本单位，..数据项.......是具有独立含义的最小标识单位。 3 数据之间的关系（逻辑结构）有四种集合、线性结构、树形结构、网状结构或图状结构,可分为....................... ....、...................两大类。 4 数据的存储结构包括..顺序存储结构.....................、..链式存储结构.......................... 二、问答题 1.什么是数据结构?什么是数据类型? 答：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 2.叙述算法的定义与特性。 答：算法是对待定问题求解步骤的一种描述，他是指令的有限序列，其中每一条指令表示一个或多个操作。 一个算法具有以下5个重要特性： 1）、有穷性 2）、确定性3）、可行性 4）、输入 5)、输出 3. 叙述算法的时间复杂度。 答：算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时量度，记作T（n）=O(f(n)) 他表示随着问题规模n的增大，算法执行时间增长率和f（n）的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。 三、判断题（在各题后填写“√”或“×”） 1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（×） 2．下列几种数量级从小到大的排列顺序为： O(1) 、O(logn)、O(n) 、O(nlogn) 、O(n2) 、O(n3 ) 、O(2n)。（√） 四、1．计算机执行下面的语句时，语句s的执行频度（重复执行的次数）为 _______ 。 FOR(i=l；i 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 数据结构试题及答案(十套)数据结构试题及答案(十套) 一、选择题 1. 数据结构是指（）。 A. 存储数据的方式 B. 数据的逻辑结构和物理结构 C. 数据的存储结构和存储方式 D. 数据的逻辑结构、存储结构和存储方式 答案：D 2. 在数据结构中，线性表的存储方式包括（）。 A. 顺序存储和链式存储 B. 数组存储和链表存储 C. 顺序存储、链表存储和索引存储 D. 顺序存储、链表存储和树形存储 答案：A 3. 栈是一种（）的数据结构。 A. 先进先出 B. 先进后出 C. 后进先出 D. 后进后出 答案：C 4. 队列是一种（）的数据结构。 A. 先进先出 B. 先进后出 C. 后进先出 D. 后进后出 答案：A 5. 二叉树中，度为0的节点称为（）。 A. 叶子节点 B. 根节点 C. 中间节点 D. 子节点 答案：A 6. 以下哪个排序算法是稳定的？ A. 快速排序 B. 选择排序 C. 插入排序 D. 希尔排序 答案：C 7. 图中表示顶点之间关系的边的数量称为（）。 A. 顶点度数 B. 边数 C. 路径数 D. 网络 答案：B 8. 哈希表通过（）来实现高效的查找操作。 A. 散列函数 B. 排序算法 C. 遍历操作 D. 顺序存储 答案：A 9. 平衡二叉树是一种具有左右子树高度差不超过（）的二叉树。 A. 0 B. 1 C. 2 D. 3 答案：B 10. 在链表中，删除节点的操作时间复杂度是（）。 A. O(1) B. O(logn) C. O(n) D. O(nlogn) 答案：A 二、填空题 1. 在顺序存储结构中，元素之间的逻辑关系由（）表示。 答案：下标 2. 二叉查找树的中序遍历结果是一个（）序列。 答案：递增 3. 哈希表通过散列函数将关键字映射到（）上。 数据结构练习题 第一部分绪论 一、单选题 1. 一个数组元素a[i]与________的表示等价。 A、 *(a+i) B、 a+i C、 *a+i D、 &a+i 2. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。 A、参数类型 B、参数个数 C、函数类型 3. 若需要利用形参直接访问实参，则应把形参变量说明为________参数 A、指针 B、引用 C、值 4. 下面程序段的时间复杂度为____________。 for(int i=0; i 数据结构_习题集（含答案） 《数据结构》课程习题集 一、单选题 1.头结点为L的单循环链表为空的条件是（） A、L==NULL B、L->next==NULL C、L->next==L D、L!==NULL 2.与线性表的链式存储结构特点不符的是：（） A、便于插入、删除运算 B、查找操作费时 C、需要连续的地址空间 D、空间动态分配 3.采用邻接表存储的图，其深度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 4.对序列{1,5,7,10,12,15,19}，采用折半查找1，需比较（）次。 A、1 B、2 C、3 D、4 5.直接选择排序算法的时间复杂度为（） A、O（n） B、O（n2） C、 O（n*log（n）） D、 O（1） 6.一个栈的入栈序列为1、2、3、4，则栈的不可能的输出序列是 （） A、1 2 3 4 B、4 3 2 1 C、4 1 2 3 D、3 4 2 1 7.判定一个顺序栈S为空的条件为（）。 A、S.top=0 B、S.base=0 C、S.top=S.base D、S.top>S.stacksize 8.设有两个串r和t，求r在t中首次出现位置的运算称作（） A、求串长 B、连接 C、模式匹配 D、求子串 9.按二叉树的定义，具有3个结点的二叉树共有（）种形态。 A、3 B、4 C、5 D、6 10.一个有n个顶点的完全无向图共有（）条边。 A、n B、2n C、n*(n-1) D、n*(n-1)/2 11.对序列{5，7，12，19，20，30}，采用折半查找19，需比较（）次。 A、1 B、2 C、3 数据结构习题集含答案 目录 目录 (1) 选择题 (2) 第一章绪论 (2) 第二章线性表 (4) 第三章栈和队列 (6) 第四章串 (9) 第五章数组和广义表 (9) 第六章树和二叉树 (10) 第七章图 (13) 第八章查找 (15) 第九章排序 (17) 简答题 (21) 第一章绪论 (21) 第二章线性表 (22) 第三章栈和队列 (23) 第四章串 (25) 第六章树和二叉树 (25) 第七章图 (29) 第八章查找 (32) 第九章排序 (33) 编程题 (35) 第一章绪论 (35) 第二章线性表 (35) 第三章栈和队列 (37) 第四章串 (37) 第五章数组和广义表 (37) 第六章树和二叉树 (37) 第七章图 (37) 第八章查找 (37) 第九章排序 (39) 选择题 第一章绪论 1. 数据结构这门学科是针对什么问题而产生的？（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2. 数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3. 某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90 分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 5. 算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 6. 算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 7. 计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 精心整理 程序复杂性 3、具有线性结构的数据结构是（D）。 A.图 B.树 C.广义表 D.栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B）等5个特性。 A.可执行性、可移植性和可扩充性 B.可执行性、有穷性和确定性 C.确定性、有穷性和稳定性 D.易读性、稳定性和确定性 5、下面程序段的时间复杂度是（C）。 for(i=0;i A.O(n) B.) O C. O(1) D.O(n2) (n 二、填空题 1、程序段“i=1;while(i<=n)i=i*2;”的时间复杂度为O(log2n)。 2、数据结构的四种基本类型中,树形结构的元素是一对多关系。 1 1、（C）。 2A）存储 A. 3 4 5 6 A. C.不必事先估计存储空间 D.所需空间与线性表长度成正比 7、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（C）。 A.p->next=q;q->prior=p;p->next->prior=q;q->next=q; B.p->next=q;p->next->prior=q;q->prior=p;q->next=p->next; C.q->prior=p;q->next=p->next;p->next->prior=q;p->next=q; D.q->next=p->next;q->prior=p;p->next=q;p->next=q; 8、线性表采用链式存储时，结点的存储地址（C）。 A.必须是连续的 B.必须是不连续的 C.连续与否均可 D.和头结点的存储地址相连续 数据结构练习题（含答案） ①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2.数据结构DS(DataStruct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象②A．操作Ｂ．映象Ｃ．存储Ｄ．关系3.在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4.算法分析的目的是①，算法分析的两个主要方面是②。 ①A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性②A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性5.计算机算法指的是①，它必具备输入、输出和②等五个特性。 ①A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法②A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性1.2填空题（将正确的答案填在相应的空中） 1.数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点； 最后一个结点后续结点，其余每个结点有且只有个后续结点。 3.在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4.在图形结构中，每个结点的前驱结点数和后续结点数可以。 5.线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6.算法的五个重要特性是____,____,____,____,____。 第一章绪论 一、填空题 1．数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。_________是数 据的基本单位；___________是数据的最小单位。通常被计 算机加工处理的数据不是孤立无关的，而是彼此之间存在 着某种联系，将这种数据间的联系称为________。 2．数据结构进行形式化定义时，可以从逻辑上认为数据结构DS是_________的集合D和D上_________的集合R所构成 的二元组：DS=（D，R）。 3．已知某数据结构的二元组形式表示为：A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>， <01，03>，<01，04>，<02，05>，<02，06>，<03，07>， <03，08>，<03，09>}。则此数据结构属于_____________ 结构。 4．一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时， 则表示为__________；成正比关系时，则表示为 ___________；成对数关系时，则表示为___________；成 平方关系时，则表示为__________。 5．数据结构的逻辑结构包括_____________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为 _____________；数据结构的存储结构主要包括 ____________和____________两种类型。 6．线性结构的特点是：第一个结点_______前驱结点，其余结点有且仅有_______个前驱结点；最后一个结点_______后 继结点，其余每个结点有且仅有_______个后继结点。 7．树型结构的特点是：根结点没有________结点，其余每个结点有且仅有________个前驱结点；叶子结点_________后 继结点，其余结点可以有_________个后继结点。 8．图型结构的特点是：每个结点可以有_________个前驱结点和后继结点。 9．程序段for（i=1，s=0；s 第一章绪论 一、选择题 1.组成数据的基本单位是（） A．数据项B．数据类型C．数据元素D．数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 A．理想结构，物理结构B．理想结构，抽象结构 C．物理结构，逻辑结构D．抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ①A．数据元素B．计算方法C．逻辑存储D．数据映像 ②A．结构B．关系C．运算D．算法 5.算法分析的两个主要方面是（）。 A．数据复杂性和程序复杂性B．正确性和简明性 C．可读性和简明性D．空间复杂性和时间复杂性 6.算法分析的目的是（）。 A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进D．分析算法的易懂性和文档性 7.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。 ①A．计算方法B．排序方法 C．解决问题的有限运算序列D．调度方法 ②A．可执行性，可移植性和可扩充性B．可行性，确定性和有穷性 C．确定性、有穷性和稳定性D．易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、________和________四种类型,其中树形结构和图形结构合称为________。 2.在线性结构中,第一个结点________前驱结点,其余每个结点有且只有________个前驱结点；最后一个结点________后续结点,其余每个结点有且只有________个后续结点。 3.在树形结构中,树根结点没有________结点,其余每个结点有且只有________个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存在________关系,图形结构中元素之间存在________关系。 6.算法的五个重要特性是________、________、________、________、________。 7.数据结构的三要素是指________、________和________。 8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。 9.设有一批数据元素,为了最快的存储某元素,数据结构宜用________结构,为了方便插入一个元素,数据结构宜用________结构。 四、算法分析题 1.求下列算法段的语句频度及时间复杂度数据结构习题和答案
数据结构习题集和答案
数据结构练习题及答案
经典数据结构习题集含答案
数据结构习题集(包含全部答案)
数据结构练习题(含答案)
数据结构试题集(包含答案完整版)
数据结构习题集及答案
数据结构习题和答案及解析
数据结构试题及答案(十套)
(完整版)数据结构练习题及参考答案
数据结构_习题集（含答案）
数据结构习题集含参考答案
数据结构试习题集(含答案
数据结构练习题（含答案）
数据结构习题(含答案)
数据结构习题集附答案
相关主题
文本预览