第一章1．在数据结构中，从逻辑上可以把数据结构分为（C ）A．动态结构和静态结构 B. 紧凑结构和非紧凑结构C．线性结构和非线性结构 D. 内部结构和外部结构● 2.在数据结构中,与所使用的计算机无关的是( A )A. 逻辑结构B. 存储结构C. 逻辑和存储结构D. 物理结构3.下面程序的时间复杂度为____O（mn）_______。

for (int i=1; i<=m; i++)for (int j=1; j<=n; j++ )S+=i第二章线性表●链表不具备的特点是（A）A 可以随机访问任一结点（顺序）B 插入删除不需要移动元素C 不必事先估计空间D 所需空间与其长度成正比2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ）A head==nullB head->next==nullC head->next==headD head!=null●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D）A 单链表B 双链表C 循环链表D 顺序表● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C)A 顺序表B 用头指针表示的单循环链表C 用尾指针表示的单循环链表D 单链表● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序，则操作的时间复杂度为( D )A O(1)B O(log2n)C O(n2)D O(n)● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长度有关A 删除单链表中第一个元素B 删除单链表中最后一个元素C 在第一个元素之前插入一个新元素D 在最后一个元素之后插入一个新元素●7.与单链表相比，双向链表的优点之一是(D)A 插入删除操作更简单B 可以进行随机访问C 可以省略表头指针或表尾指针D 顺序访问相邻结点更容易●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域(头结点的地址)中存放的是( B )A list的地址B list的内容C list指的链结点的值D 链表第一个链结点的地址●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B )A list2比list1占用更多的存储单元B list1与list2占用相同的存储单元C list1和list2应该是相同类型的指针变量D 双向链表比单链表占用更多的存储单元10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确)11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。

V 100+4*12=14811.在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。

12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。

13、一个顺序表所占用存储空间的大小与（B）无关。

A．表的长度 B.元素的存放顺序 C. 元素的类型 D.元素中各的类型●14、设存储分配是从低地址到高地址进行的。

若每个元素占用4个存储单元，则某元素的地址是指它所占用的单元的（A）。

A. 第1个单元的地址B. 第2个单元的地址C. 第3个单元的地址D. 第4个单元的地址15、若线性表采用顺序存储结构，每个元素占用4个存储单元，第1个元素的存储地址为100，则第12个元素的存储地址是（ B）。

A. 112B. 144C.148D. 412●16、若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是( D )。

A. i>0B.i<=nC.1<=i<=nD. 1<=i<=n+117、若长度为n 的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应该是（ C ）。

A. i>0B.y<=nC.1<=i<=nD. d<=i<=i+1●18、若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表中（ B ）个数据元素。

A. n-iB.n+iC. n-i+1D. n-i-119、若长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，首先需要移动表中（ C ）个数据元素。

A. iB. n+iC.n-i+1D.n-i-120、若频繁地对线性表进行插入和删除操作，该线性表应该采用（ C ）存储结构。

A.散列B. 顺序C. 链式D. 索引●21、链表中的每一个链结点所占用的存储单元（ B ）。

A. 不必连续B.一定连续C.部分连续D. 连续与否无所谓●22、在一个具有n个链结点的线性链表中查找某一个链结点，若查找成功，需要平均比较（C）个链结点。

A. nB. n/2C.(n+1)/2D. (n-1)/2●23、给定具有n个元素的顺序表，建立一个有序线性链表的时间复杂度为（ C）。

A. O(1)B.O(n)C.O(n2)D. O(log2n)24、在非空线性链表中由p所指的链结点后面插入一个由q所指的链结点的过程是依次执行（ B ）。

A. q->next=p; p->next=q;B. q->next=p->next; p->next=q;C. q->next=p->next; p =q;D. p->next=q; q->next=p;25、若删除非空线性链表中由p所指的链结点的直接后继链结点的过程过程是依次执行（ B）。

A. r=p->next; p->next=r; free(r);B. r=p->next; p->next=r->next; free(r);C. r=p->next; p->next=r->next; free(p);D. p->next=p->next->next; free(p);26、在非空双向循环链表中由q所指的链结点后面插入一个由p所指的链结点的操作依次为p->prior=q; p->next=q->next;q->next=p;（ C ）。

A. q->prior=pB. q->next->prior=pC. p->next->prior=p;D. p->prior->next=p;27、在非空双向循环链表中由q所指的链结点前面插入一个由p所指的链结点的操作依次为p->next=q; p->prior=q->prior;q->prior=p;（ D ）。

A.q->next=p;B. q->prior->next=p;C. p->next->prior=p;D. p->prior->next=p;28、顺序存储的线性表(a1,a2,……,an),在任一结点前插入一个新结点时所需移动结点的平均次数为（ D ）。

A. nB. n/2C. n+1D. (n+1)/229、在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数是( A )。

A. n-i+1B. n-iC. iD. i-130、在线性表的下列存储结构中，读取元素花费时间最少的是（ D）。

A. 单链表B. 双链表C. 循环链表D. 顺序表31、在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ C ）。

A. 数据元素的相邻地址表示B. 数据元素在表中的序号表示C. 指向后继元素的指针表示D. 数据元素的值表示25、假设指针p指向单链表中的某一结点，若把p指针后面的结点删除，只需修改下列哪个指针值即可（）。

A．p=p->next; B．p->next=p->next->nextC．p=p->next->next; D．p->next=p;26、在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则执行( D )。

A．q->next＝p->next；p->next＝qB．p->next＝q->next；q＝p；C．q->next＝p->next；p->next＝q；D．p->next＝q->next；q->next＝p；27、构造一个空的线性表L用（ A ）A.InitList(&L)B.DestroyList (&L)C.ListEmpty(L)D.ClearList(&L)第三章1、栈和队列的共同点是（C ）A. 都是先进后出B. 都是先进先出在C. 只允许在端点处插入和删除元素D. 没有共同点2、一个栈的进栈顺序是a,b,c,d,e，则栈的出栈顺序不可能是（C ）A. edcbaB.decbaC. dceabD. adcbe3、设n个元素的进栈序列为1,2,3,……,n，出栈序列为p1,p2,p3,……,pn，若p1=n，则pi(1<=i<=n)的值为（ C ）。

A. iB. n-iC.n-i+1D. 有多种可能4、判断下面的说法是否正确（1）插入和删除操作比较简单，是链式栈和链式队列的优点之一。

X（2）堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。

X5、设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为多少？6、若数组s[0..n-1]为两个栈，s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为（C ）。

A. 1和n+1B. 1和n/2C. -1和nD. -1和n+17、判定一个顺序栈st（最多元素为Maxsize）为空的条件为（B ），判断栈满的条件为(D ).A. st.top!=-1B. st.top==0C.st.top!=MaxsizeD.st.top==Maxsize8、循环顺序队列中是否可以插入下一个元素，（A ）A. 与队头指针和队尾指针的值有关B. 只与队尾指针的值有关，与队头指针的值无关C. 只与数组的大小有关，与队首头指针和队尾指针的值无关D. 与曾经进行过多少次插入操作有关9、若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除1个元素，然后再插入2个新元素后，rear和front的值分别为（ B ）。