1、数据结构习题包含全部答案解析数据结构习题集（自编）第一章 绪论一、选择题1数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（）和运算的学科。 A结构 B关系 C运算 D算法2在数据结构中，从逻辑上可以把数据结构分成（）。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D逻辑结构和存储结构3线性表的逻辑顺序和存储顺序总是一致的，这种说法（）。 A正确 B不正确 C无法确定 D以上答案都不对4算法分析的目的是（）。A找出算法的合理性 B研究算法的输人与输出关系C分析算法的有效性以求改进 D分析算法的易懂性5. 算法的时间复杂度取决于（ ）A问题的规模B待处理
2、数据的初态 C. A和B6一个算法应该是（ ）。A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C. 7. 下面关于算法说法错误的是（ ）A算法最终必须由计算机程序实现B.为解决某问题的算法与为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的8以下与数据的存储结构无关的术语是（ ）。A循环队列 B. 链表 C. 哈希表 D. 栈9在下面的程序段中，对x的赋值语句的频度为（ ）for（i=0;in;i+） for(j=0;jn;j+) x=x+1;A 2n Bn Cn2 Dlog2n 10以下数据结构中，（ ）是非线性数据结构A树 B字符串
3、C队列 D栈11. 下列数据中，（ ）是线性数据结构。A哈夫曼树 B.有向无环图 C. 二叉排序树 D. 栈12以下属于逻辑结构的是（ ）。A顺序表 B. 哈希表 C.有序表 D. 单链表二、填空题1、_是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，_是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。（数据、数据） 2、数据元素是数据的_，有些情况下也称为元素、结点、顶点、记录等。（基本单位）3、_是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为_。（数据项、数据项） 4、数据的逻辑结构是指数据之
4、间的_。逻辑结构是从_上描述数据，它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具体问题抽象出来的_。（逻辑关系、逻辑关系、数学模型） 5、数据的_指数据元素及其关系在计算机存储器的表示。_是逻辑结构在计算机里的实现，也称之为映像。（存储结构、存储结构） 6、数据逻辑结构可以分为四种基本的类型，_结构中的元素除了仅仅只是同属于一个_，不存在什么关系。（集合、集合） 7、数据逻辑结构的四种基本类型中，_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。（线性结构） 8、数据逻辑结构的
5、四种基本类型中，_中的元素是一种一对多的关系。（树形结构） 9、图型结构或图状结构是一种_的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。（多对多） 10、有时也可将树型结构、集合和图型结构称为_，这样数据的逻辑结构就可以分为_和_两大类。（非线性结构、线性结构、非线性机构） 11、_方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。（顺序存储） 12、_方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。（链式存储） 13、_
6、方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。（散列存储或哈希存储） 14、所谓算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的其中每个指令表示一个或多个操作。算法的五个重要特性是_、_、_、_和_。（有限序列、有穷性、确定性、可行性、输入、输出）15、算法的_性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间完成。（有穷性） 16、算法的_性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得
7、到_的输出结果。（确定性、相同） 17、算法的_性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行有限次来实现。（可行性） 18、判断一个算法的好坏主要以下几个标准：_、_、_、_。（正确性、可读性、健壮性、时间效率和空间效率） 19、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机_的长短和_的大小。（运行时间、所占据空间） 20、空间复杂度（SPace ComPlexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用_的大小。（存储空间）三、判断题 1顺序存储方式只能用于存储线性结构。（） 2数据元素是数据的最小单位。（） 3算法的优
8、劣与算法描述语言无关，但与所用计算机有关。() 4健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()5数据的逻辑结构是指各元素之间的逻辑关系，是根据用户需要而建立的。 6数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。（） 7数据的物理结构是指数据在计算机中实际的存储形式。（） 8具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。9算法实际上就是程序，程序也一定是算法。()10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。()11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()12. 数据结构的基本操作的设置的最重要的准则
9、是，实现应用程序与存储结构的独立。()13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。 () 14. 判断一个算法的好坏主要以下几个标准：正确性、有穷性、健壮性和可行性。() 15算法的时间复杂度T（n）=O(f(n)表示随问题规模n的增大，算法执行时间的增长率与函数f(n)的增长率相同。（）四、综合题 1用大O形式表示下面算法的时间复杂度： for（i=0；im；i十十） for（j=0；jn；j） Aij=i*j； 2写出下面算法的时间复杂度： i0； s=0； while(sn） i+; s+=i; 3写出以下算法的时间复杂度： for（i0; im; i）f
10、or（j0 ; jt; j） cij=0；for（i=0；im；i） for（j=o; jt; j+） for（k=0；kn；k） cijaik*bkj;4写出下面算法的时间复杂度：i=1;while（in） i=i*3;5求下面函数中各条语句的频度和算法的时间复杂度：prime（int n） int i2； while (ni）！=0isqrt(n) ) i+; if（isqrt(n) ) printf（”d is a prime number.n”，n）； else printf（”d is not a prime number.n”，n）；1. 该算法的时间复杂度为：O(mn)。2. 该
11、算法的时间复杂度为：O()3. 该算法的时间复杂度为：O(mnt)。4. 该算法的时间复杂度为：log3(n)。5. 该算法的时间复杂度为：O()。6将下列函数，按它们在n时的无穷大阶数，从小到大排序。 n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/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个元素（0inext=p-next-next Bp-n
12、ext=p-nextCp=p-next-next Dp=p-next; p-next=p-next-next 14在一个单链表中，已知q所指结点是p所指结点的前驱，若在q和p之间插入s所指的结点，则执行（ ）操作。 As-next=p-next; p-next=s; Bq-next=s; s-next=p;Cp-next=s-next; s-next=p; Dp-next=s; s-next=q; 15在单链表中附加头结点的目的是为了（ ）。 A保证单链表中至少有一个节点 B标识单链表中首结点的位置 C方便运算的实现 D说明单链表是线性表的链式存储 16循环单链表的主要优点是（ ）。 A不再需
13、要头指针了 B从表中任意一个结点出发都能扫描到整个链表 C已知某个结点的位置后，能够容易找到它的前驱 D在进行插入、删除操作时，能更好地保证链表不断开 17非空的循环单链表L的尾结点p满足（ ）。 Ap-next=NULL Bp=NULL Cp-next=L Dp=L 18在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( )。注:双向链表的结点结构为(prior,data,next)。 供选择的答案：Ap-prior=q； q-next=p； p-prior-next=q； q-prior=q；Bp-prior=q； p-prior-next=q; q
14、-next=p； q-prior=p-prior；Cq-next=p； q-prior=p-prior；p-prior-next=q; p-prior=q;Dq-prior=p-prior； q-next=p； p-prior=q； p-prior=q； 19在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。Ap-prior-next=p-next; p-next-prior=p-prior;Bp-prior=p-prior-prior; p-prior-next=p;(删p的前趋)Cp-next-prior=p; p-next=p-next-next;Dp-next= p-prior
15、-prior; p-prior= p-next-next;二、填空题1线性表（Linear List）是最简单、最常用的一种数据结构。线性表中的元素存在着_的相互关系。（一对一）2线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有且仅有一个_，除终端结点外，其他每个元素有且仅有一个_。3线性表是n（n=0）个数据元素的_。其中n为数据元素的个数，定义为线性表的_。当n为零时的表称为_。4所谓顺序表（Sequential LISt）是线性表的_，它是将线性表中的结点按其_依次存放在存中一组连续的存储单元中，使线性表中相邻的结点存放在_的存储单元中。5单链表不要求
16、逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些_的存储单元来存储线性表中的数据元素，这些存储单元可以分散在存中的_的位置上，它们在物理上可以是一片连续的存储单元，也可以是_的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的。6线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的_；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)，称为_或_。7线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种_存储结构，又称为_。8如果将单链表最后一个结
17、点的指针域改为存放链表中的头结点的地址值，这样就构成了_。9为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了_。10双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是p_。11在单链表中，删除指针P所指结点的后继结点的语句是_。12在双循环链表中，删除指针P所指结点的语句序列是P-prior-nextp-next及_。13单链表是_的存储表示。14可以使用_表示树形结构。15向一个长度为n的向量的第i个元素(lin+1）之前插人一个元素时，需向后移动_个元素。16删除一个长度为n的向量的第i个元素（lin）时，需向前移动_
18、个元素。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. 非顺序、非
19、顺序映像8. 循环链表9. 双向链表10. 所指向的结点本身11. P-next=p-next-next12. P-next-prior=P-prior13. 线性表14. 双链表15. n-i+116. n-i17. S-next=P-next; P-next=S18. 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线性表采用链表存储时，结点和结点部的存储空间可
20、以是不连续的。()2在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。()3顺序存储的线性表不可以随机存取。() 4单链表不是一种随机存取结构。（）5顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。() 6顺序存储结构是动态存储结构，链式存储结构是静态存储结构。()7线性表的长度是线性表所占用的存储空间的大小。()8双循环链表中，任意一结点的后继指针均指向其逻辑后继。()9线性表的惟一存储形式是链表。() 1. 错误：链表存储中，结点之间可以连续也可以不连续，但结点部是连续的。2. 错误：头指针指向头结点而不是数据结点。3. 错误：顺序存储的线性表可以随机存
21、取。4. 正确。5. 错误。6. 错误：顺序存储结构是静态存储结构，链式存储结构是动态存储结构。7. 错误：先行表的长度是线性表中结点的个数。8. 错误：注意最后一个结点。9. 错误：也可以有顺序存储的形式。第三章 栈和队列一、选择题 l一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是（）。Aa，b，c，d，e Bd，e，c，b，a Cd，c，e，a，b De，d，c，b，a 2若一个栈的输人序列是1，2，3，n，输出序列的第一个元素是n，则第k个输出元素是（ ）。 Ak Bn-k-1 Cn-k+1 D不确定3判定一个栈S（最多有n个元素）为空的条件是（ ）。 AS-top！0 B
22、S-top= =0 CS-top!=n DS-top= =n4判定一个栈S（最多有n个元素）为满的条件是（ ）。 AS-top!=0 BS-top= =0 CS-top!=n DS-top= =n5向一个栈顶指针为top的不带头结点的链栈中插人一个*S结点的时候，应当执行语句（ ）。 Atop-next=S； BS-next=top；top=S； CS-nexttop-next；top-nextS；DS-nexttop；topS-next；6向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（ ）。 Atop-next=S； BS-next=top；top=S； CS
23、-next=top-next；top-next=S； DS-next=top；top=S-next；7判定一个队列Q（最多有n个元素）为空的条件是（ ）。 AQ-rear-Q-front= =n BQ-rear-Q-front+1= =n CQ-rear = = Q-front DQ-rear +1= = Q-front8判定一个队列Q（最多有n个元素）为满的条件是（）。 AQ-rear-Q-front= =n BQ-rear-Q-front+1= =n CQ-rear = = Q-front DQ-rear +1= = Q-front9判定一个循环队列Q（最多有n个元素）为空的条件是（ ）。
24、 AQ-rear = = Q-front BQ-rear = = Q-frontl CQ-front= =(Q-rear +1)n DQ-front= =(Q-rear -1)n10判定一个循环队列Q（最多有n个元素）为满的条件是（ ）。 AQ-rear = = Q-front BQ-rear = = Q-frontl CQ-front= =(Q-rear +1)n DQ-front= =(Q-rear -1)n11在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（ ）。 Afrontfront-next BS-next=rear；rear=S Crear-next=S；rear=S DS-next=front；frontS12在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ ）。 Afront=front-next Brear=rear-next Crear-next=front Dfront-nextrear 13栈与队列都是（ ）。A链式存储的线性结构 B链式存储的非线性结构C限制存取点的线性结构 D限制存取点的非线性结构 14
