数据结构2011年秋季期末复习提纲习题.doc

《数据结构2011年秋季期末复习提纲习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构2011年秋季期末复习提纲期末考试形式：闭卷试卷总评成绩：试卷70%+平时30%试卷题型：1.选择题（20分），2.应用题（30分）3.程序填空题（30分）4.算法设计题（20分）每章复习要点：第1章：概念理解：数据结构，时间复杂度程序段：i=1;while(i<=n)i=i*2;第2章：表的顺序存储结构，链式存储结构（单链表、循环链表、双向链表），表的基本操作与应用，本章所占分值在15分左右，会考表的算法。(1)顺序存储结构1、下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单

2、元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。2、对于顺序表的优缺点，以下说法错误的是：（）A、无需为表示节点间的逻辑关系而增加额外的存储空间；B、可以方便地随机存取表中的任一节点；C、插入和删除运算较方便；D、由于顺序表要求占用连续的空间，存储分配智能预先进行。(2)链式存储结构1、链表不具备的特点是？（）A．可随机访问任一节点。B．插入删除不需要移动元素。C．不必事先估计存储空间。D．所需空间与其长度成正比。2、（1)静态链

3、表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（）。A．（1）（2）     B．（1）      C．（1）（2）(3)     D．（2）3、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是A、head==NULL B、head→next==NULL   C、head→next==head  D、head!=NULL4

4、、如果对线性表的运算只有两种，即删除第一个元素，在最后一个元素后面插入新元素，最好使用（）A、只有表头指针而没有表尾指针的循环单链表B、只有表尾指针而没有表头指针的循环单链表C、非循环双链表D、循环双链表5、线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i）B．O（1）C．O（n）D．O（i-1）第3章：栈的实现，栈的应用（数制转换，括号匹配），Hanoi塔不考，队列的实现（其中循环队列重点）。本章所占分值在10分左右，可能会考算法。（1）栈1、一个栈的输入序列为12345，则下列序列

5、中不可能是栈的输出序列的是（）。A.23415B.54132C.23145D.154322、输入序列为ABC，输出为ABC时（假设元素出栈则输出），经过的栈操作为（）。A．push,pop,push,pop,push,popB．push,push,push,pop,pop,popC．push,push,pop,pop,push,popD．push,pop,push,push,pop,pop（2）队列1、循环队列用数组A【0…Maxsize】存放其元素值，头尾指针是front和rear，则队列中元素个数是（）A、（rear-fro

6、nt-1）%MaxsizeB、rear-frontC、（rear-front+1）%MaxsizeD、（rear-front+Maxsize）%Maxsize2、一个队列的入队序列是1，2，3，4，则队列的输出序列是（）。A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，1，43、用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()。A.1和5B.2和4C.4和2D.5和1第4章：只考计算模式串的NEXT

7、值,不考算法，本章所占分值在5分左右1、串"ababaaababaa"的next数组为（）。A．012345678999B．012121111212C．011234223456D．012301232234第5章：数组的存储位置计算，压缩矩阵的存储（不考算法）本章所占分值在5分左右1、n阶对称矩阵A,将其上三角的元按列优先顺序压缩存放在一维数组B[1…n(n+1)/2]中，第一个元素a1，1存于B[1]中，则应存放到B[k]中的元素ai,j(1<=i<=n,i<=j<=n)的下标i，j与k的对应关系是k=（）。A.i(i+1)/2

8、+jB.i(i-1)/2+jC.j(j+1)/2+iD.j(j-1)/2+i2、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储地址为()。A.BA+