数据结构第1、2章练习题讲解

1、练习题1.数据结构是研究数据的( )以及它们之间的相互关系。A. 物理结构，逻辑结构 B. 理想结构，抽象结构C. 理想结构，物理结构 D. 抽象结构，逻辑结构2.从逻辑上可以把数据结构分为（ ）两大类。A.动态结构、静态结构 B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构3.以下不属于算法要素的是（ ）。A. 有穷性 B. 可行性 C. 可读性D. 输入4. 算法的时间复杂度与（ ）有关。A.问题规模 B.计算机硬件性能 C.编译程序质量 D.程序设计语言ACCA5.某算法的时间复杂度为O（n2），表明该算法的（ ）A.问题规模是n2 B.执行时间等于n2 C.执行

2、时间与n2成正比 D.问题规模与n2成正比1输入非法数据时，也要能作出相应的处理，这种算法要求称为 （ ） A正确性 B可行性C健壮性 D输入性6.假设某算法语句总的执行次数为T(n)=2n+n,那么该算法的时间复杂性量级为（ ）。 A. O(2) B. O(n) C. O(n) D. O(1)7.设n为正整数，下面程序段中标号为的语句频度为 （ n-1 ）。 i = 1;k = 0;while ( i = n-1 )k += 10*i; i+;CCB8. 数据结构是指 （ ）。A. 一种数据类型B. 数据的存储结构C. 一组性质相同的数据元素的集合D. 相互之间存在一种或多种特定关系的数据元

3、素的集合9. 以下算法的时间复杂度为 ( ) 。void func(int n)int i=0,s=0;while (s=n)i+;s=s+i;A. O(n)B. O( )C. O(nlog2n)D. O(log2n)DB10. 以下算法的时间复杂度为 ( ) 。void fun(int n)int i=1;while (i=n)i=i*3;A. O(n)B. O(n2)C. O(log2n)D. O(log3n)11. 某算法的空间复杂度为O(1)，则 ( ) 。A.该算法执行不需要任何辅助空间B.该算法执行所需辅助空间大小与问题规模n无关C.该算法执行不需要任何空间D.该算法执行所需全部空

4、间大小与问题规模n无关12. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储( )。A. 数据的处理方法 B. 数据元素的类型C. 数据元素之间的关系 D. 数据的存储方法DBC10. 以下算法的时间复杂度为 ( ) 。void fun(int n)int i=1;while (i=n)i=i*3;A. O(n)B. O(n2)C. O(log2n)D. O(log3n)11. 某算法的空间复杂度为O(1)，则 ( ) 。A.该算法执行不需要任何辅助空间B.该算法执行所需辅助空间大小与问题规模n无关C.该算法执行不需要任何空间D.该算法执行所需全部空间大小与问题规模n无关12. 在存

5、储数据时，通常不仅要存储各数据元素的值，而且还要存储( )。A. 数据的处理方法 B. 数据元素的类型C. 数据元素之间的关系 D. 数据的存储方法DBC13.数据结构中，与所使用的计算机无关的是数据的哪种结构 （ ）A.存储 B.物理 C. 逻辑 D. 物理和存储14.数据逻辑结构包括线性结构 、 和 三种类型。（树形结构 图状结构）15.评估一个算法的优劣，通常从 和空间复杂度两个方面考察。 （时间复杂度） C16. 程序段for( i=0; in; i+ ) for( j=0; ji; j+ ) k+;中，语句k+的执行次数为_n*(n-1)/2_。17.在下面的程序段中，对x的赋值语句

6、的渐进时间复杂度为O(n2) 。for(k=1;k=n;k+) for(j=1;j=n;j+) x=x+1;18.下面程序段的时间复杂度为 O(log2n) 。void fun(int n) int y=1;while (y next=h C. h-next=NULL D.h!=NULL第2章练习题DADC5.在表头指针为head且表长大于1的单向循环链表中，指针p指向表中的某个结点，若p-next-next= =head,则( ) A. p指向头结点 B. *p的直接后继是尾结点 C. p指向尾结点 D. *p的直接后继是头结点6.如果线性表长度变化较大，且经常进行插入删除操作，则采用（ ）

7、更合适。A. 单链表 B. 有序表 C. 无序表 D.顺序表7.在顺序线性表（a1,a2,a29,a30）中，在a20之前插入一个新的结点，需要将( )个结点后移。A. 11 B. 20 C. 19 D. 10BAA8.在不带头结点的单链表L中的第一个结点前插入结点S，以下正确的是( )。A. S-next=L;L =S; B. L-next=S;S-next=L-next; C. S-next=L-next;L-next=S; D. S-next=L-next;9.在一个单链表中，若结点不是最后结点，在p之后插入结点s。则执行( )。A.s-next=p;p-next=s; B.s-next

8、=p-next;p-next=s;C.s-next=p-next;p=s; D.p-next=s;s-next=p;10.在单链表中，删除*p结点的后一个结点的操作是( ) A.p-next=p B.p-next-next=p-next C.p-next-next=p D.p-next=p-next-nextABD11顺序存储结构的优势是 （ ）A利于插入操作 B利于删除操作C利于顺序访问 D利于随机访问12 在带有头结点的单链表L中，要向表头插入一个由指针p指向的结点，则执行操作（ ）Ap-next=L-next; L-next=p; Bp-next=L; L=p；Cp-next=L; p=

9、L DL=p; p-next=L；13对线性表，应当采用链表表示的是 （ ）A经常需要随机地存取元素B经常需要进行插入和删除操作C表中元素需要占据一片连续的存储空间D表中元素的个数不变DAB14. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 （ ）A. 必须是连续的 B. 部分地址必须是连续的C. 一定是不连续的 D. 连续或不连续都可以15. 不带头结点的单链表head为空的判定条件是 （ ）A. head=nullB. head-next=null C. head-next=headD. head!=null16. 在一个单链表中，若p结点不是最后结点，在p之后插入s结点，则

10、执行（ ）A. s-next=p；p-next=sB. s-next=p-next；p-next=s C. s-next=p-next；p=sD. p-next=s；s-next=pDAB17.链表不具备的特点是（ ）A可随机访问任一结点 B插入删除不需要移动元素C不必事先估计存储空间 D所需空间与其长度成正比18.在一个单链表中，若p结点不是最后结点，在p之后插入s结点，则执行（ ）A. s-next=p；p-next=sB. s-next=p-next；p-next=s C. s-next=p-next；p=sD. p-next=s；s-next=p19. 在一个带头结点的循环单链表L中，

11、删除元素值为x的结点，算法的时间复杂度为 ( ) 。A. O(n)B. O( ) C. O(nlog2n)D. O(n2)AAB20. 在长度为n的顺序表中插入一个元素，对应算法的时间复杂度为 ( )。A.O(1)B.O(log2n) C.O(n) D.O(n2)21. 设线性表中有n个元素，以下运算中,在单链表上实现要比在顺序表上实现效率更高的是( )。A.删除指定位置元素的后一个元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素D.交换第i个元素和第n-i+1个元素的值（i=1，2，n）22、顺序表和链表相比存储密度较大，这是因为（ ）。A.顺序表的存储空间是预先分配的B.顺

12、序表不需要增加指针来表示元素之间的逻辑关系C.链表中所有节点的地址是连续的D.顺序表中所有元素的存储地址是不连续的CAB1评估一个算法的优劣，通常从 和空间复杂度两个方面考察。2在单链表中（假设结点指针域名称为next），删除指针P所指结点的后继结点的语句是 。3.设单链表的结点结构为(data,next)，next为指针域，已知指针p指向单链表中data为x的结点，指针q指向data为y的新结点，若将结点y插入结点x之后，则需要执行以下语句： q-next=p-next ； p-next=q ；4.p是指向单链表L的中间结点的指针，补充下列删除p的后继结点的程序段。s = p-next;_p

13、-next=s-next;_free( s );5.在一个长度为n的顺序表的最后插入一个数据元素，其时间复杂度为（O（1），在第i个元素（1in+1）之前插入一个元素时，需向后移动( ni+1 )个元素。6.循环单链表LA中，指针P所指结点为表尾结点的条件是 P-next=LA 7.以下是双向链表中结点s（data，prior，next）插入到结点p之前的插入过程，请补充完整。s-next =（ p ）; （ p-prior-next ） = s;（ s-proir ）= p-proir; ( p-proir ) = s;8. 在双链表中，每个结点有两个指针域，一个指向 ，另一个指向 。（前驱结点 后继结点）（ ）1线性表的链式存储结构优于顺序存储结构。（ ）2在单链表P指针所指结点之后插入S结点的操作是：P-next= S ; S- next = P-next。（ ）3. 线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。 1. 什么是算法? 它具有哪些特性?算法概念：通俗地讲，一个算法就是一种解