数据结构习题第一章绪论1.1数据结构是一门研究非数值计算的程序设计问题中计算机的___①__以及它们之间的__②_ 和运算等的学科。

①A.数据元素B.计算方法C.逻辑存储D.数据映像②A.结构 B.关系 C.运算 D.算法1.2 算法分析的目的是___①__ ，算法分析的两个主要方面是__②___ 。

① A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求该进D.分析算法的易懂性和文档性② A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性1.3 计算机算法指的是__①__ ，它必须具备输入、输出和__②_ 等5个重要特性。

① A.计算方法 B.排序方法C.解决问题的有限运算序列D.调度方法② A.可读性、可移植性和可扩展性 B. 可读性、可移植性和有穷性C.确定性、有穷性和可行性D.易读性、稳定性和安全性1.4数据元素是数据处理的基本单位；数据项是数据处理的_最小单位。

1.5数据结构是研究数据的逻辑结构___和__物理结构__，并对这种结构定义相适应的运算，设计出相应的算法，分析算法的效率。

算法的效率包括时间和空间两个方面，分别称为_空间复杂度和时间复杂度。

数据的逻辑结构是指_数据元素之间的关系__；包括线性结构、树形结构和图形结构三种类型,其中树形结构和图状结构合称为__非线性结构__。

1.6 线性结构中元素之间存在_一对一___ 关系，树形结构中元素之间存在_一对多___ 关系，图状结构中元素之间存在__多对多__ 关系。

1.7 数据结构在计算机中的表示称为数据的物理（或存储）结构，数据的物理结构可以采用_顺序存储和_链式存储__两种存储方法。

1.8顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的内存单元中；链式存储方法中元素间的关系是由__指针来表示_的。

第二章线性表2.1 链表不具备的特点是____ 。

A.可随机访问任一结点B.插入删除不需移动元素C.不必事先估计存储空间D.所需空间与其长度成正比2.2 不带头结点的单链表head 为空的判定条件是____。

A. head==nullB. head->next==nullC. head->next==headD. head !=null2.3带头结点的单链表head 为空的判定条件是____。

A. head==nullB. head->next==nullC. head->next==headD. head!=null2.4 非空的循环单链表head 的尾结点（由p所指向）满足____。

A. p->next==nullB. p==nullC. p->next==headD. p==head2.5 在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是____。

A. O(1)B. O(n)C. O(n2)D. O(nlog2n)2.6线性链表中各个结点之间的地址不一定连续。

2.7线性表中数据元素之间具有__一对一__，除第一个和最后一个元素外，其他数据元素有且只有_一个后继和前趋。

2.8若频繁地对线性表进行插入和删除操作，该线性表采用链式存储结构比较合适。

2.9 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_p->next_和p->next=_s_的操作。

2.10 已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)=__ LOC(a1)+（i-1）*k_。

2.12 若线性表采用顺序存储结构，每个数据元素占用3个存储单元，第11个数据元素的存储地址为130，则第1个数据元素的存储地址是100 。

2.12 若线性表采用顺序存储结构，线性表的最大长度为1000，每个数据元素占3个存储单元，则要分配给该线性表_3000__存储单元，若第一个数据元素的存储地址是2000，则第11个元素的存储地址是__2030__。

2.13 以head为头结点循环双链表为空时，应满足head->llink= head，head->rlink= head。

2.14 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是。

A.p=p->next;B.p->next=p->next->next;C.p->next=p;D.p=p->next->next;2.15 在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行________。

A. s->next=p->next;p->next=sB. q->next=s;s->next=pC. p->next=s->next;s->next=pD.p->next=s;s->next=q2.16 用链表表示线性表的优点是（）A．便于随机存储 B.便于进行插入和删除操作C. 占用的存储空间较顺序表少D.元素的物理顺序与逻辑顺序相同2.17 下面关于线性表的叙述中，错误的是（）A. 线性表采用顺序存储必须占用一片连续的存储单元B. 线性表采用顺序存储便于进行插入和删除操作C. 线性表采用链式存储不必占用一片连续的存储单元D. 线性表采用链式存储便于进行插入和删除操作2.18 线性表是具有n个（）的有限序列A. 数据项B. 数据元素C. 表元素D. 字符2.19长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间复杂度为（）A. O（1）B.O（n）C. O（n2）D.O（log2n）2.20 在长度为n的顺序表删除第i（1≤i≤n）个元素，则需要向前移动元素的次数为（）A. iB. n-iC. n-i+1D.n-i-12.21 在长度为n的顺序表中第i（1≤i≤n）个位置上插入一个元素时，为留出插入位置所需要移动元素的次数为（）A. n-iB. iC. n-i-1D. n-i+12.22 以下对单链表的叙述错误的是（）A. 单链表中的每一个结点都由存放结点值的数据域和存放直接后继结点地址信息的指针域两部分组成B.从单链表的第i 个结点出发，可以访问到链表中的任何一个结点C.在单链表结构中加入头结点可以简化结点的插入和删除操作D.单链表尾结点的指针域应置为空指针2.23 以下记叙中正确的是（）A. 线性表的链式存储结构优先于顺序存储结构B. 线性表的存储结构不影响其各种运算的实现C. 选择线性表的存储结构就是要保证存储其各个元素的值D.顺序存储属于静态结构，链式存储属于动态结构第三章栈与队列一、选择题3.1 栈的特点是___B_ ，队列的特点是___A_ 。

A.先进先出B.先进后出3.2 栈和队列的共同点时____。

A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点3.3 一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是____ 。

A. edcbaB. decbaC. dceabD. abcde3.4 判定一个栈ST（最多元素MaxSize）为空的条件是____ 。

A.ST->top!=-1B. ST->top==-1C.ST->top!= MaxSizeD. ST->top==MaxSize-13.5 判定一个栈ST（最多元素MaxSize）为栈满的条件是____ 。

A.ST->top!=-1B. ST->top==-1C.ST->top!= MaxSizeD. ST->top==MaxSize-13.6 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是____。

A.（rear-front+m）%mB. rear-front+1C. rear-front-1D. rear-front3.7 在一个链队中，假设f和r 分别是队头和队尾指针，则插入一个s结点的运算时____。

A. f->next=s; f=s;B. r->next=s; r=s;C. s->next=r; r=s;D. s->next=f; f=s;3.8在一个链队中，假设f和r 分别是队头和队尾指针，则删除一个结点的运算时____。

A. r=f->next;B. r=r->next;C. f=f->next;D. f=r->next;3.9若进栈序列为a，b，c，进栈过程中允许出栈，则以下_____是不可能得到的出栈序列。

A. a,b,cB. b,a,cC. c,a,bD. c,b,a3.10一个最多能容纳m个元素的顺序存储的循环队列Q，其头尾指针分别为front和rear，则判定该队列为满的条件是__________A. (Q.rear+1)%m= =Q.frontB. Q.front= =Q.rearC. Q.rear+1= =Q.frontD. (Q.front+1)%m= =Q.rear3.11一个最多能容纳m个元素的顺序存储的循环队列Q，其头尾指针分别为front和rear，则判定该队列为空的条件是__________A. (Q.rear+1)%m= =Q.frontB. Q.front = = Q.rearC. Q.rear+1= =Q.frontD. (Q.front+1)%m= =Q.rear3.12若进栈序列为1，2，3，4，，进栈过程中可以出栈，则以下不可能的出栈序列是（）A. 1，4，3，2B.2，3，4，1C. 3，1，4，2D.3，4，2，13.13一个队列的入队序列是1，2，3，4，则队列的输出序列是_____。

A. 4,3,2,1B. 1,2,3,4C. 1,4,3,2D. 3,2,4,13.14 若用一个可容纳6个元素的数组来实现循环队列，且当前rear和front的值分别是0和4，当执行2次出队和1次入队操作后，rear和front 的值分别为（）A.1和0B.0和2C.2和5D.1和5第四章串和数组4.1串是一种特殊的线形表，其特殊性体现在____A. 可以顺序存储B. 数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符4.2 串的两种最基本的存储方式是_顺序和链式___。

4.3两个串相等的充分必要条件是: 长度相等_且_对应位置上的字符相等__。

4.4 如下陈述中正确的是______。

A．串是一种特殊的线性表B．串的长度必须大于零C．串中元素只能是字母D．空串就是空白串4.5 不含任何字符的串称为__空串_,其长度为_长度等于零__。