数据结构复习题23601

1、一、选择题1、在数据结构中，从逻辑上可以把数据结构分成（）A、动态结构和静态结构 B、紧凑结构和非紧凑结C、线性结构和非线性结构 D、内部结构和外部结构1、 若进栈序列为1、2、3、4，进栈过程中可以出栈，则下列不可能的一个出栈序是（）A、1，4，3，2 B、2，3，4，1 C、3，1，4，2 D、3，4，2，12、 栈和队列的共同点是（）A、 都是先进先出 B、都是先进后出 C、只允许在端点处插入和删除元素 D、没有共同点4、一个队列的入队列序列是1，2，3，4，则队列的输出序列是（）A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，15、设栈S的初始状态为空，6个

2、元素入栈的顺序为e1，e2，e3，e4，e5和e6。若出栈的顺序是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（）A、6 B、4 C、3 D、26、算法的时间复杂度是指（）A、执行算法程序所需要的时间 B、算法程序的长度 C、算法执行过程中所需要的基本运算次数 D、算法程序中的指令条数7、链表不具有的特点是（）A、可随机访问任一元素 B、插入和删除不需要移动元素 C、不必事先估计存储空间 D、所需空间与线性表长度成正8、数据的存储结构是指（）A、数据所占的存储空间量 B、数据的逻辑结构在计算机中的表示C、数据在计算机中的顺序存储方式 D、存储在外存中的数据9、线性表是( ) 。A

3、、一个有限序列，可以为空； B、一个有限序列，不能为空； C、 一个无限序列，可以为空； D、一个无序序列，不能为空。 10、对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ ）个元素。A、 n/2 B、 n+1/2 C、 n -1/2 D、 n 11、线性表采用链式存储时，其地址( ) 。A、必须是连续的； B、部分地址必须是连续的； C、一定是不连续的； D、连续与否均可以。 12、用链表表示线性表的优点是 （ ）。A、便于随机存取 B、花费的存储空间较顺序存储少 C、便于插入和删除 D、数据元素的物理顺序与逻辑顺序相同13、循环链

4、表的主要优点是( ) 。A、不在需要头指针了 B、已知某个结点的位置后，能够容易找到他的直接前趋C、在进行插入、删除运算时，能更好的保证链表不断开D、从表中的任意结点出发都能扫描到整个链表14、下面关于线性表的叙述错误的是( )。A、线性表采用顺序存储，必须占用一片地址连续的单元； B、线性表采用顺序存储，便于进行插入和删除操作；C、线性表采用链式存储，不必占用一片地址连续的单元； D、线性表采用链式存储，不便于进行插入和删除操作；15.在长度为n的顺序表中，向第i个元素(1in+1)之前插入一个新元素时，需向后移动 个元素。A、 n-1 B、 n-i+1 C、n-i-1 D、i16、若某线性

5、表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。A、单链表 B、仅有头指针的单循环链表 C、 双链表 D、仅有尾指针的单循环链表17、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省运算时间（ ）。A、 单链表 B、 顺序表 C、 双链表 D、 单循环链表18.以下不是栈的基本运算的是（ ）A、删除栈顶元素 B、删除栈底元素 C、判断栈是否为空 D、将栈置为空栈19在一个链式队列中，f 和 r分别为队头和队尾指针，则删除结点的运算是（ ）A、r=f->next; B、r=r->next

6、C、f=f->next D、f=r->next20在表达式求值算法中，需要用几个栈？（ ）A、0 B、1 C、2 D、3二、判断题1线性表的逻辑顺序与存储顺序总是一致的。 （ ）2顺序存储的线性表可以按序号随机存取。 （ ）3顺序表插入和删除操作不需要付出很大时间代价，因为每次操作平均有近一半元素需要移动。（ ）4线性表中元素可以是各种各样，但同一线性表中数据元素具有相同特性，因此属于同一数据对象。（ ）5在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（ ）6在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（ ）7线性表的链式存储结构优于

7、顺序存储结构。（ ） 8在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（ ）9线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（ ）10单链表中要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（ ）11基于某种逻辑结构之上的运算，其实现是唯一的。（ ）12数据元素是最小的单位。（ ）三、填空题1线性结构的顺序存储结构是一种_的存储结构，线性结构的链式存储是一种_的存储结构。2线性结构中元素的关系是_，树形结构中元素的关系是_，图形结构中元素的关系是_。3算法的5个重要特性是_、_、_、_、_。4.已知具有n个元素的一维

8、数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，第i个元素LOC(ai)=_。 5在顺序表中做插入操作时首先检查_。6线性表、栈和队列都是_结构，可以在线性表的_位置插入和删除元素，对于栈只能在_位置插入和删除元素，对于队只能在_位置插入和_位置删除元素。7非空单循环链表L中*p是尾结点的条件是_。8在一个单链表中已知q所指结点是p所指结点的前驱结点，若在q和p之间插入一个由指针s所指结点，应执行q=L; while(_) q=_; s->next=_; q->next=_。9带头结点的单链表H为空的条件是_。10不带头结点的单链表H为空的条件是_。四、算法设计题1 编写一个函数，从一给定的顺序表A中删除值在xy(x<=y)之间的所有元素，要求以较高的效率来实现。提示：可以先将顺序表中所有值在xy之间的元素置成一个特殊的值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值的元素后，移动其后面的元素将其删