习题1一、选择题1．数据结构通常是研究数据的（）及它们之间的相互联系。

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．一对一B．一对多C．多对多D．无关系7．数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称为（）。

A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构8．非线性结构中的每个结点（）。

A．无直接前趋结点B．无直接后继结点C．只有一个直接前趋结点和一个直接后继结点D．可能有多个直接前趋结点和多个直接后继结点9．链式存储的存储结构所占存储空间（）。

A．分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点的值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点的值，另一部分存放结点所占单元素10．算法分析的两个主要方面是（）。

A．正确性和简单性B．可读性和文档性C．数据复杂性和程序复杂性D．时间复杂度和空间复杂度11．算法的计算量大小称为算法的（）。

A．现实性B．难度C．时间复杂性D．效率12．数据的基本单位是（）。

A．数据结构B．数据元素C．数据项D．文件13．每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种存储结构称为（）结构。

A．顺序存储B．链式存储C．索引存储D．散列存储14．每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（）存储方式。

A．顺序B．链式C．索引D．散列15．以下任何两个结点之间都没有逻辑关系的是（）。

A．图形结构B．线性结构C．树形结构D．集合16．在数据结构中，与所使用的计算机无关的是（）。

A．物理结构B．存储结构C．逻辑结构D．逻辑和存储结构17．下列四种基本逻辑结构中，数据元素之间关系最弱的是（）。

A．集合B．线性结构C．树形结构D．图形结构18．与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。

A．逻辑结构B．存储结构C．逻辑实现D．存储实现19．每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是（）存储方式。

A．顺序B．链式C．索引D．散列20．算法能正确的实现预定功能的特性称为算法的（）。

A．正确性B．易读性C．健壮性D．高效性21．算法在发生非法操作时可以做出处理的特性称为算法的（）。

A．正确性B．易读性C．健壮性D．高效性22．下列时间复杂度中最坏的是（）。

A．O(1) B．O(n) C．O(log2n) D．O(n2)23．在下面的程序段中，对x的赋值语句的频度为（）。

for( i=1;i<n;i++)for(j=1;j<n;j++)x++;A．O(2n) B．O(n) C．O(n2) D．O(log2n)二、填空题1．常见的数据结构有集合、线性结构、结构、结构。

2．算法的5个重要特性是有穷性、、可行性、输入、。

3．评价算法的优劣通常主要考虑算法的和这两方面。

4．线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。

5．数据的存储结构又叫。

6．数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的的有限集合。

7．算法的空间复杂度是指该算法所耗费的，它是该算法求解问题规模n的函数。

8．算法是一个的集合，算法效率的度量可以分为和。

9．若一个算法中的语句频度之和为T(n)=7n+4n2，则算法的时间复杂度为。

10．设有一组数据元素需存储，为了方便查找某元素，数据宜采用存储结构；为了方便插入与删除某元素，数据宜采用存储结构。

三、判断题1．数据的逻辑结构与数据元素本身的内容和形式无关。

（）2．一个数据结构是由一个逻辑结构和这个逻辑结构上一个基本运算集构成的整体。

（）3．数据元素是数据的最小单位。

（）4．数据的逻辑结构和数据的存储结构是相同的。

（）5．程序和算法原则上没有区别，所以在讨论数据结构时可以通用。

（）6．从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。

（）7．数据的存储结构是数据的逻辑结构的存储映像。

（）习题2一、选择题1．下面关于线性表的叙述中，错误的是（）。

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

2．在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（）。

A．O(1)B．O(n)C．O(n2)D．O(log2n)3．两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（）。

A．P->next == Q->next B．P->next == QC．Q->next == P D．P == Q4．在单链表中，增加头结点的目的是（）。

A．使单链表至少有一个结点B．标志表中首结点的位置C．方便运算的实现D．说明该单链表是线性表的链式存储结构5．在顺序表中，只要知道（），就可以求出任意一个结点的存储地址。

A．基地址B．结点大小C．向量大小D．基地址和结点大小6．链表不具备的特点是（）。

A．随机访问B．不必事先估计存储空间C．插入删除时不需移动元素D．所需空间与线性表成正比7．在（）的运算中，使用顺序表比链表好。

A．插入B．根据序号查找C．删除D．根据元素查找8．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（）。

A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;9．用链表表示线性表的优点是（）。

A．便于进行插入和删除操作B．便于随机存取C．占用的存储空间较顺序表少D．元素的物理顺序与与逻辑顺序一致10．在一个长度为n的顺序表中，若要删除第i（1≤i≤n）个元素，则需向前移动（）个元素。

A．n-i+1 B．n-i-1 C．n-i D．i11．在一个长度为n的顺序表中，若要在第i（1≤i≤n）个元素前插入一个元素时，则需向后移动（）个元素。

A．n-i+1 B．n-i-1 C．n-i D．i12．设p为指向单循环链表上某结点的指针，则*p的直接前驱（）。

A．找不到B．查找时间复杂度为O(1)C．查找时间复杂度为O(n)D．查找结点的次数约为n13．等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（）。

A．n B．(n-1)/2 C．n/2 D．(n+1)/214．以下链表结构中，从当前结点出发能够访问到任意结点的是（）。

A．单向链表和双向链表B．循环链表和单向链表C．循环链表和双向链表D．单向链表、双向链表和循环链表15．对具有n个结点的线性表进行插入或删除操作，所需的算法时间复杂度为（）。

A．O(n2) B．O(nlog2n)C．O(log2n) D．O(n)二、填空题1．线性表L=(a1,a2,…,a n)采用顺序存储，假定删除表中任意元素的概率相同，则删除一个元素平均需要移动元素的个数是。

2．顺序表相对于链表的优点是：和随机存取；链表相对于顺序表的优点是：方便。

3．在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为。

4．在长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移个元素。

5．链表相对于顺序表的优点是插入、删除方便；缺点是存储密度。

6．链式存储的特点是利用来表示数据元素之间的逻辑关系。

7．在双向链表中，每个结点有两个指针域，一个指向其结点，另一个指向其结点。

8．在一个双链表中，设指针p是指向该表中待删除的结点，则需要执行的操作为：。

9．若对一个线性表经常进行查找操作，而很少进行插入和删除操作时，则采用存储结构为宜，相反，若经常进行的是插入和删除操作时，则采用存储结构为宜。

三、判断题1．线性表的链式存储结构优于顺序存储结构。

（）2．链表的每个结点都恰好包含一个指针域。

（）3．在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

（）4．顺序存储方式的优点是存储密度大，插入、删除效率高。

（）5．线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

6．顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（）7．线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。

（）8．线性表采用顺序存储，必须占用一片连续的存储单元。

（）9．顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

（）10．插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。

（）习题3一、选择题1．对于栈操作数据的原则是（）。

A．先进先出B．后进先出C．后进后出D．不分顺序2．有6个元素按6,5,4,3,2,1 的顺序进栈，问下列（）不是合法的出栈序列？A．5 4 3 6 1 2B．4 5 3 1 2 6C．3 4 6 5 2 1D．2 3 4 1 5 63．插入和删除只能在一端进行的线性表，称为（）。

A．队列B．循环队列C．栈D．循环栈4．输入序列为ABC，可以变为CBA时，经过的栈操作为（）。

A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,popC．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop5．设有编号为1,2,3,4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为（）。

A．1234 B．1243C．1324 D．14236．如果以链表作为栈的存储结构，则出栈操作时（）。

A．必须判别栈是否满B．必须判别栈是否空C．必须判别栈元素类型D．队栈可不做任何判别7．顺序栈存储空间的实现使用（）存储栈元素。

A．链表B．数组C．循环链表D．变量8．在C语言中，一个顺序栈一旦被声明，其占用空间的大小（）。