数据结构习题及标准答案

#/5第一章1.在数据结构中，从逻辑上可以把数据结构分为（C）A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构•2.在数据结构中，与所使用的计算机无关的是（A）A.逻辑结构B.存储结构C.逻辑和存储结构D.物理结构3.下面程序的时间复杂度为 O（mn） 。for（inti=1;i<=m;i++）for（intj=1;j<=n;j++）S+=i第二章线性表链表不具备的特点是（）可以随机访问任一结点（顺序） 插入删除不需要移动元素不必事先估计空间 所需空间与其长度成正比不带头结点的单链表 为空的判定条件为（），带头结点的单链表 为空的判定条件为（）Ahead==null Bhead->next==nullC在线性表的下列存储结构中，读取元素花费时间最少的是（）单链表 双链表 循环链表 顺序表对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为顺序表 用头指针表示的单循环链表 用尾指针表示的单循环链表 单链表在一个具有个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序，则操作的时间复杂度为（单）在一个长度为 的单链表上，设有头和尾两个指针，执行 操作与链表的长度有关删除单链表中第一个元素 删除单链表中最后一个元素在第一个元素之前插入一个新元素 在最后一个元素之后插入一个新元素7在与单链表相比，双向链表的优点之一是（单）插入删除操作更简单 可以进行随机访问可以省略表头指针或表尾指针 顺序访问相邻结点更容易若 是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域（头结点的地址）中存放的是（B）的地址 的内容 指的链结点的值 链表第一个链结点的地址•若和 分别为一个单链表与一个双向链表的第一个结点的指针，则比 占用更多的存储单元 与 占用相同的存储单元和 应该是相同类型的指针变量 双向链表比单链表占用更多的存储单元10链若表中的每个链结点占用的存储空间不必连续，这句话正确吗？ 不正（确）11.某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V100+4*12=14811在若顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。12若若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用（链）存储结构。、一个顺序表所占用存储空间的大小与（）无关。A表的长度 元素的存放顺序 元素的类型 元素中各的类型• 、设存储分配是从低地址到高地址进行的。若每个元素占用个存储单元，则某元素的地址是指它所占用的单元的（）。第个单元的地址第个单元的地址第个单元的地址第个单元的地址15、若线性表采用顺序存储结构，每个元素占用4个存储单元，第1个元素的存储地址为10，0则第12个元素的存储地址是（B）。^ 、若长度为的线性表采用顺序存储结构，在表的第个位置插入一个数据元素，的合法值应该是（素。）、若长度为的非空线性表采用顺序存储结构，删除表的第个数据元素，的合法值应该是（C）。^ 、若长度为的非空线性表采用顺序存储结构，删除表的第个数据元素，首先需要移动表中（）个数据元素。、若长度为的非空线性表采用顺序存储结构，在表的第个位置插入一个数据元素，首先需要移动表中（）个数据元素。0若频繁地对线性表进行插入和删除操作，该线性表应该采用（）存储结构。散列顺序链式索引21、链表中的每一个链结点所占用的存储单元（B）。不必连续 一定连续 部分连续 连续与否无所谓^ 、在一个具有个链结点的线性链表中查找某一个链结点，若查找成功，需要平均比较（分）个链结点。3给定具有个元素的顺序表，建立一个有序线性链表的时间复杂度为（C、在非空线性链表中由所指的链结点后面插入一个由所指的链结点的过程是依次执行（B）。5若删除非空线性链表中由所指的链结点的直接后继链结点的过程过程是依次执行（）B。、在非空双向循环链表中由所指的链结点后面插入一个由所指的链结点的操作依次为=）。、在非空双向循环链表中由所指的链结点前面插入一个由所指的链结点的操作依次为q)。A.q->next=p; B.q->prior->nexC.p->next->prior=p; D.p->prior->nex、顺序存储的线性表 …… 在任一结点前插入一个新结点时所需移动结点的平均次数为(D)。A.n B.n/2 C.n+1 D.(n+1)/、在长度为n的顺序表的第i(iwiwn+1)个位置上插入一个元素，元素的移动次数是(A)。A.n-i+1 B.n-i C.i D.i-130、在线性表的下列存储结构中，读取元素花费时间最少的是()D。单链表 双链表 循环链表 顺序表31、在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用(C)。数据元素的相邻地址表示 数据元素在表中的序号表示指向后继元素的指针表示 数据元素的值表示25、假设指针p指向单链表中的某一结点，若把p指针后面的结点删除，只需修改下列哪个指针值即可( )。A．p=p->next; B．p->next=p->next->nextC．p=p->next->next; D．p->next=p;6在一个单链表 中，若要在指针所指结点的后面插入一个由指针所指向的结点，则执行(D)。7构造一个空的线性表用( )第三章1、栈和队列的共同点是(C)A.都是先进后出B.都是先进先出在C.只允许在端点处插入和删除元素D.没有共同点2、一个栈的进栈顺序是a,b,c,d,e，则栈的出栈顺序不可能是(C)A.edcbaB.decbaC.dceabD.adcbe3设个元素的进栈序列为，…，出栈序列为 ……。若，则的值为()。有多种可能4、判断下面的说法是否正确(1)插入和删除操作比较简单，是链式栈和链式队列的优点之一。 X(2)堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。 X5、设有一个顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少应为多少？6、若数组s[0..n-1]为两个栈，si和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：si和s2的栈顶指针的初值分别为(C)。和 和 和 和7、判定一个顺序栈st(最多元素为Maxsize)为空的条件为(B)，判断栈满的条件为(D).A.st.top!=-1B.st.top==0C.st.8、循环顺序队列中是否可以插入下一个元素,(A)与队头指针和队尾指针的值有关只与队尾指针的值有关，与队头指针的值无关只与数组的大小有关，与队首头指针和队尾指针的值无关与曾经进行过多少次插入操作有关、若用一个大小为的一维数组来实现循环队列，且当前和 的值分别为和，当从队列中删除个元素，然后再插入个新元素后，和的值分别为()。和 和 和 和10、用单链表表示队列时，队头应该在单链表的(A)位置。链头链尾链中任意11、堆栈和队列的共同之处在于它们具有相同的(A)。逻辑特性物理特性 运算方法 元素类型12、堆栈和队列都是特殊的线性表,其特殊性在于(C)。它们具有一般线性表所没有的逻辑特性它们的存储结构特殊对它们的使用方法做了限制它们比一般线性表更简单13、若5个元素的出栈序列为1,2,3,4,5,则进栈序列可能是(D)。14、若堆栈采用顺序存储结构，正常情况下，向堆栈中插入一个元素，栈顶指针top的变化是(D)不变5若堆栈采用顺序存储结构，正常情况下，删除堆栈中一个元素，栈顶指针 的变化是(C)不变16、若队列采用顺序存储结构,元素的排列顺序(B)。与元素的值的大小有关 由元素进入队列的先后顺序决定与队头指针和队尾指针的取值有关 与作为顺序存储结构的数组的大小有关17、“链接队列”这一概念不涉及(B)。数据的存储结构 数据的逻辑结构 对数据进行的操作 链表的种类18、若堆栈采用链式存储结构，栈顶指针为top,向堆栈插入一个由p所指的新结点的过程是依次执行(C),top=p19、若非空堆栈采用链式存储结构，栈顶指针为top,删除堆栈一个元素的过程是依次执行p=top；(B);free(p)

20、若队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear,向队列中插入一个由p所指的新结点的过程是依次执行：（C）;rear=p;A.rear=pB.front=pC.rear->next=p21、若非空队列采用链式存储结构，，队头元素指针与队尾元素指针分别为front和rear，删除队列的一个元素的过程是依次执行：p=front;（D）;free（p）A.rear=pB.rear=p->nextC.p->next22、在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列队空的条件是（C）。A.front=rear+1B.rear=front+1C.f23、若描述某循环队列的数组为为Circle[M]，当循环队列满时，队列中有（B）个元素。A.MB.M-1C.M+1D.M+224、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印，该缓冲区应该是一个（D）结构。线性表 数组 C.堆栈 D.队列25、设计一个递归问题的非递