《数据结构与算法》复习题
一、选择题。
1．在数据结构中，从逻辑上可以把数据结构分为 C 。 B．紧凑结构和非紧凑结构A．动态结构和静态结构 D．内部结构和外部结构C．线性结构和非线性结构
．数据结构在计算机内存中的表示是指。A2
的关系 B．数据结构 CDA．数据的存储结构
．数据的逻辑结构．数据元素之间
数据结构在计算机
．在数据结构中，与所使用的计算机无关的是数据的结构。 A 3
。4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 5A 。 ．在决定选取何种存储结构时，一般不考虑
中的表示（映像）称为数．物理（．存储 C．逻辑和存储 DA．逻辑 B 据的物理（存储）结构） ．数据元素的类型．数据的处理方法 BA ．数据的存储方法C．数据元素之间的关系 D
A．各结点的值如何 ．结点个数
的多少B ．所用的编程语言实现这种结构是否方便。．对数据有哪些运算C D
D ．以下说法正确的是6。
逻辑结构D
A．数据项是数据的基本单位 ．数据元素是数据的
最小单位B ．数据结构是带结构的数据项的集合C ．一些表面上很不相同的数据可以有相同的
C，算法分析的两个主要方面是 A 。7．算法分析的目的是
析算法的效率以求改进
B．正确性和简明性 ．空间复杂度和时间复杂度（2）A D．数据复杂性和程序复杂性 C．可读性和文档性
B．研究算
法中的输入和输出的关系．找出数据结构的合理性 1（）AC．分析算法的易读性和文档性C．分
2。)O(n 8．下面程序段的时间复杂度是
for(j=0;j s=0; i++) for( I=0;i 9．下面程序段的时间复杂度是O(n*m)。 i++) i 0． ．下面程序段的时间复杂度是。 O(log10n)3 i<=n）while（ 3； i * i = 。 11．在以下的叙述中，正确的是 B方式是先进后出 0；i ＝ A．线性表的顺序存储结构优于链表存储结 构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作 B．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 。12 要一致B ．每个数据元素都一样C ．数据元素所包含的数据项的个数要相等D 。A13．链表不具备的特点是 ．数据 元素具有同一特点A ．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型 ．插入删除不需要移动元素BA．可随机访问任一结点 ------------学资学习网-------提供考研资料------- ．所需空间与其长度成正比．不必事先估计存储空间 DC 为空的判定条件是14．不带头结点的单链表 headA 。headA． == NULL head!=NULLD ==head head->nextC． 为空的判定条件是 15．带头结点的单链表 head B 。NULLhead->next ==head head!=NULLD C．head->next 16．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用 D 存储方式最节省运算时间。链表 C．双链表 A．单链表 17．需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是B 。 ==NULLB head->next ==NULLB A．head== D．带头结点的双循环链表B．给出表头指针的单循环 ．顺序存储结构B．静态链表 A．单链表C．线性链表 D headC 所指向）满足 的尾结点（由 p。 18．非空的循环单链表 A．p->next == NULL． == headD C．p->next==head ．p 。 19．在循环双链表的 p 所指的结点之前插入 s所指结点的操作是 D NULLp == B = p->prior ； ．Ap->prior =s；s->next= pp->prior->next =s；s->prior p->prior ； ；ss->next= ps->prior= ； ．Bp->prior=sp->prior->next= ； ．Cs->next=ps->prior=p->prior ；s p->prior；=p->prior->next =s 1． D．s->next = p；s->prior = p->prior；p->prior->next = s；p->prior = s 存储方式最节省时间。 D．如果最常用的操作是取第 i 个结点及其前驱，则采用20 顺序表． ．单链表 B．双链表 C．单循环链表 DA 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是n 。B21．在一个具 有 ）．O（nlog2nC1A．O（） ．O（n2） DB．O（n） ）的单链表上，设有头和尾两个指针，执行n（n>1B．在一个长度为操作与链表的长度有关。 22 A．删除单链表中的第一个元素 B．删除单链表中的最后一个元素 C．在单链表第一个元素前插入一个新元素 D．在单链表最后一个元素后插入一个新元素 D23．与单链表相比，双链表的优点之一是。 A．插入、删除操作更简单 B．可以 进行随机访问 ．可以省略表头指针或表尾指针C ．顺序访问相邻结点更灵活D ．如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使24 。用 B A．只有表头指针没有表尾指针的循环单链表 B．只有表尾指针没有表头指针的循环单链表 C．非循环双链表 D．循环双链表 。A ，元素的移动次数为：i 个位置上插入一个元素（1≤ i ≤n+1） 25．在长度为n 的顺序表的第 26 ．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为C 。 头指针表示的循环单链表B． A．顺序表 ．用尾指针表示的循环单链表D．单链表C 。C 27．下述哪一条是顺序存储结构的优点？ –1 ．．+ 1 Bn – i Ci D．iinA． – 用 B A 插入运算方便 可方便地用于各种逻辑结构的存储表示 删除运算方便DC 存储密度大 ------------学资学习网-------提供考研资料------- 的叙述中，错误的是哪一个？ 。28．下面关于线性表B A 线性表采用顺序存储，必须占用一片连续的存储单元 线性表采用顺序存储，便于进行插入和删除操作。B 线性表采用链式存储，不必占用一片连续的存储单元C D 线性表采用链式存储，便于进行插入和删除操作。 的有限序列。 B个n．线性表是具有29 ．表元素D．数据项 A．字符C ．数据元素B2． 30．在 n 个结点的线性表的数组实现中，算法的时间复杂度是 O（1）的操作是 A 。 个结点后插入一个新结点B i（1<=i<=n）个结点．删除第C D．以上都不对 ，在其第 i 个位置插入一个新元素的算法的时间复杂度为31．若长度为 n 的线性表采用顺序存储结构 ．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为32C 。 ．O(1) O(1)O(1) C．O(1) A．O(n) O(n) O(n) DB．O(n) i 个结点的直接前驱（1 C。 2 )．O(1) C．O(n) D．O(nBA．O(0) 位置元素的时间复杂度为i 33．线性表（a1,a2,… ,an）以链式方式存储，访问第 C 。 2 ) C．O(n) D．O(nB．A．O(0) O(1) C。 34．单链表中，增加一个头结点的目的是为了 A．使单链表至少有一个结点 ； B．标识表结点中首结点的位置 ．方面运算的实现 D．说明单链表是线性表的链式存储C 的结点，正确的操作是 s B 。 35．在单链表指针为 p 的结点之后插入指针为 p->next=s;B．；．p->next=ss->next=p->next s->next=p->next A ；p->next=s C．p->next=s；p->next=s->nextD．p->next=s->next 。36．线性表的顺序存储结构是一种A 存储结构 ．随机存取的存储结构A B．顺序存取的存储结构 C．索引存取的存储结构D．Hash 存取的 A B 37．栈的特点是，队列的特点是。 ．先进先出A ．先进后出B 38 ．栈和队列的共同点是C。 ．都是先进后出 B．都是先进先出A C．只允许在 端点处插入和删除元素 D．没有共同点 ，则栈的不可能的输出序列是，，bc，de 。C 39．一个栈的进栈序列是a，D A．edcba ．abcdedceabC． DB设有一个栈，元素依次进栈的顺序为C 40． A、、C、、E。下列 是不可能的出栈序列。． ．BB,C,D,E,AC A,B,C,D,EA． E,A,B,C,DD E,D,C,B,A． 不是队列的基本运算？B ．以下41 ．从队列中删除第B A个元素i ．从队尾插入一个新元素 DC ．读取队头元素的值．判断一个队列是否为空 3． decba B． 42．若已知一个栈的进栈序列是 1，2，3，，n，其输出序列为 p1，p2，p3，…，pn，若 p1＝n，则 pi 为 。C ．不确定＋1 D－i C．n－iA．i B．n == -1B!= MaxSize）为空的条件是B。 43．判定一个顺序栈 st（最多元素为 ------------学资学习网-------提供考研资料-------