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

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

① A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求该进D.分析算法的易懂性和文档性。

② A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性计算机算法指的是__①__ ，它必须具备输入、输出和__②_ 等5个重要特性。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A.（rear-front+m）%mB. rear-front+1;C. rear-front-1D. rear-front在一个链队中，假设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;在一个链队中，假设f和r 分别是队头和队尾指针，则删除一个结点的运算时____。

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

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

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

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

如下陈述中正确的是______。

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

￥设有字符串S=“ABC123XYZ”，问该串的长度为（）.10 C已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC（A[0][0]），则A[i][j]的地址是__loc(a[0][0])+(n*i+j)*k。

二维数组有两种存储方式，第一种是以_行为主序的存储方式，第二种是以_列_为主序的存储方式。

设有二维数组A[10][20]，其中每个元素占2个字节，数组按行优先顺序存储，第一个元素的存储地址为100，那么元素A[8][12]的存储地址为__100+（20*8+12）*2对于稀疏矩阵的压缩存储，通常用一个三元组表示非零元素的信息，其中包括非零元素的值、行、列。