数据结构习题库汇总

知识点：01．绪论02．顺序表03．链表04．栈05．链队列06．循环队列07．串08．数组的顺序表示09．稀疏矩阵10．广义表11．二叉树的基本概念12．二叉树遍历、二叉树性质13．树、树与二叉树的转换14．赫夫曼树15．图的定义、图的存储16．图的遍历17．图的生成树18．静态查找（顺序表的查找、有序表的查找）19．动态查找（二叉排序树、平衡树、B树）20．哈希查找21．插入排序（直接插入、折半插入、2路插入、希尔排序）22．选择排序（简单选择、树形选择、堆排序）23．快速排序、归并排序101A1（1）．数据的逻辑结构是（A）。A．数据的组织形式B．数据的存储形式C．数据的表示形式D．数据的实现形式101A1（2）．组成数据的基本单位是（C）。A．数据项B．数据类型C．数据元素D．数据变量101B1（3）．与顺序存储结构相比，链式存储结构的存储密度（B）。A．大B．小C．相同D．以上都不对101B2（4）．对于存储同样一组数据元素而言，（D）。A．顺序存储结构比链接结构多占空间B．在顺序结构中查找元素的速度比在链接结构中查找要快C．与链接结构相比，顺序结构便于安排数据元素D．顺序结构占用整块空间而链接结构不要求整块空间101B2（5）．下面程序的时间复杂度为（B）。x=0；for（i=1；in；i++）for（j=i+1；j=n；j++）x++；A．O（n）B．O（n2）C．O（1）D．O（n）101B2（6）．下面程序的时间复杂度为（C）。for（i=0；im；i++）for（j=0；jn；j++）A[i][j]=i*j；A．O（m2）B．O（n2）C．O（m×n）D．O（m+n）101C2（7）．下面程序段的执行次数为（B）。for（i=0；in-1；i++）for（j=0；ji；j++）state；A．n（n+1）/2B．（n-1）（n+2）/2C．n（n+1）/2D．（n-1）（n+2）101D3（8）．下面程序的时间复杂度为（A）。for（i=0；im；i++）for（j=0；jt；j++）c[i][j]=0；for（i=0；im；i++）for（j=0；jt；j++）for（k=0；kn；k++）c[i][j]=c[i][j]+a[i][k]*b[k][j]；A．O（m×n×t）B．O（m+n+t）C．O（m+n×t）D．O（m×t+n）102A1（9）．顺序表的特点是（B）。A．表中元素的个数为表长B．按顺序方式存储数据元素C．逻辑结构中相邻的结点在存储结构中仍相邻D．按表中元素的次序存储102C2（10）．设顺序表共有n个元素，用数组elem存储，实现在第i个元素之前插入一个元素e的操作，其主要语句为（D）。A．FORj=nDOWNTOiDOelem[j]=elem[j+1]；elem[i]=e；B．FORj=iTOnDOelem[j]=elem[j+1]；elem[i]=e；C．FORj=iTOnDOelem[j+1]=elem[j]；elem[i]=e；D．FORj=nDOWNTOiDOelem[j+1]=elem[j]；elem[i]=e；102D2（11）．顺序表有5个元素，设在任何位置上插入元素是等概率的，则在该表中插入一个元素时所需移动元素的平均次数为（C）。A．3B．2C．2．5D．5102D2（12）．设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为（C）。A．9B．4．5C．7D．6102D3（13）．设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为（B）。A．236B．239C．242D．245102D2（14）．设顺序表的第5个元素的存储地址为200，且每个元素占一个存储单元，则第14个元素的存储地址为（B）。A．208B．209C．210D．214103D3（15）．设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p-llink和p-rlink表示，则下列等式中（D）成立。A．p=p-llinkB．p=p-rlinkC．p=p-llink-llinkD．p=p-llink-rlink103A1（16）．线性表采用链式存储时，其地址（D）。A．必须是连续的B．一定是不连续的C．部分地址必须是连续的D．连续与否均可以103B1（17）．线性表是（A）。A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空103B1（18）．链式存储的线性表中的指针指向其（B）。A．前趋结点B．后继结点C．物理前趋D．物理后继103C2（19）．设在链式存储的线性表中，设结点结构为datalink，欲在p结点后插入一个结点q的关键步骤为（A）。A．q-link=p-link；p-link=q；B．p-link=q-link；p-link=q；C．q-link=p-link；q-link=p；D．p-link=q-link；q-link=p；103C3（20）．设有指针head指向的带表头结点的单链表，现将指针p指向的结点插入表中，使之成为第一个结点，其操作是（A）（其中，p-next、head-next分别表示p、head所指结点的链域）。A．p-next=head-next；head-next=p；B．p-next=head-next；head=p；C．p-next=head；head=p；D．p-next=head；p=head；104A1（21）．在栈中，下列说法正确的是（A）。A．每次插入总是在栈顶，每次删除也总是在栈顶。B．每次插入总是在栈顶，每次删除总是在栈底。C．每次插入总是在栈底，每次删除总是在栈顶。D．每次插入总是在栈底，每次删除也总是在栈底。104B2（22）．设有一个栈，按A、B、C的顺序进栈，则下列（C）为不可能的出栈序列。A．ABCB．CBAC．CABD．ACB104B2（23）．设有一个栈，按A、B、C、D的顺序进栈，则下列（D）为可能的出栈序列。A．DCABB．CDABC．DBACD．ACDB104A2（24）．顺序栈的上溢是指（B）。A．栈满时作退栈运算B．栈满时作进栈运算C．栈空时作退栈运算D．栈空时作进栈运算104D3（25）．顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（D）。A．s．elem[top]=e；s．top=s．top+1；B．s．elem[top+1]=e；s．top=s．top+1；C．s．top=s．top+1；s．elem[top+1]=e；D．s．top=s．top+1；s．elem[top]=e；104C2（26）．设有5个元素A，B，C，D，E顺序进栈（进栈过程中可以出栈），出栈后依出栈次序进入队列，已知其出队次序为D，C，E，B，A，则该栈容量必定不小于（C）。A．2B．3C．4D．5104B2（27）．设栈S的初始状态为空，现有五个元素组成的序列1，2，3，4，5，对该序列在栈S上依次进行PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH操作，出栈的元素序列是（C）。A．5，4，3，2，1B．2，1C．2，3D．3，4104B2（28）．在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为（C）。A．top不变B．top=0C．top--D．top++104D3（29）．向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行（B）。A．hs-next=s；B．s-next=hs；hs=s；C．s-next=hs-next；hs-next=s；D．s-next=hs；hs=hs-next；105A1（30）．在队列中，下列说法正确的是（A）。A．每次插入总是在队尾，每次删除总是在队头。B．每次插入总是在队尾，每次删除也总是在队尾。C．每次插入总是在队头，每次删除也总是在队头。D．每次插入总是在队头，每次删除总是在队尾。105D3（31）．在带头结点的链队列q中，用q．front表示队头指针，q．rear表示队尾指针，结点结构为datanext，删除链队列的队头结点的主要语句为（B）。A．s=q．front；q．front-next=s．next；B．s=q．front-next；q．front-next=s．next；C．s=q．front-next；q．front=s．next；D．s=q；q．front-next=s．next；106C3（32）．循环队列sq中，用数组elem存放数据元素，sq．front指示队头元素的前一个位置，sq．rear指示队尾元素的当前位置，队列的最大容量为MAXSIZE，则队列满的条件为（D）。A．sq．front=sq．rearB．sq．front=sq．rear+1C．（sq．front+1）modMAXSIZE=sq．rearD．（sq．rear+1）modMAXSIZE=sq．front106C2（33）．循环队列sq中，用数组elem存放数据元素，sq．front指示队头元素的前一个位置，sq．rear指示队尾元素的当前位置，队列的最大容量为MAXSIZE，则在队列未满时元素x入队列的主要操作为（A）。A．sq．rear=（sq．rear+1）modMAXSIZE；sq．elem[sq．rear]=x；B．sq．elem[sq．rear]=x；sq．rear=（sq．rear+1）modMAXSIZE；C．sq．front=（sq．front+1）modMAXSIZE；sq．elem[sq．front]=x；D．sq．elem[sq．front]=x；sq．front=sq．front+1；106B2（34）．循环队列sq中，用数组elem[0‥25]存放数据元素，sq．front指示队头元素的前一个位置，sq．rear指示队尾元素的当前位置，设当前sq．front为20，sq．rear为12，则当前队列中的元素个数为（D）。A．8B．16C．17D．18106B2（35）．设循环队列的元素存放在一维数组Q[0‥30]中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向（B）元素。A．Q[4]B．Q[5]C．Q[14]D．Q[15]105A1（36）．队列操作的原则是（A）。A．先进先出B．后进先出C．只能进行插入D．只能进行删除105B2（37）．一个队列的入列序列是1234，则队列的输出序列是（B）。A．4321B．1234C．1432D．3241108C2（38）．设6行8列的二维数组A6×8=（aij）按行优先顺序存储，若第一个元素的存储位置为200，且每个元素占3个存储单元，则元素a54的存储位置为（B）。A．308B．305C．266D．269109C2（39）．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（B）。A．13B．33C．18D．40108A1（40）．设二个数组为A[0‥7]、B[-5‥2，3‥8]，则这两个数组分别能存放的字符的最大个数是（C）。A．7和35B．1和5C．8和48D．1和6108C3（41）．二维数组M[i，j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下列j的范围从0到5。M按行存储时元素M[3，5]的起始地址与M按列存储时元素（B）的起始地址下同。A．M[2，4]B．M[3，4]C．M[3，5]D．M[4，4]108C2（42）．设二维数组为M[0‥8，0‥10]，每个元素占2L个存储单元，以行序为主序存储，第一个元素的存储位置为P。存储位置