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

数据结构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．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2、对于顺序表的优缺点，以下说法错误的是：（） A、无需为表示节点间的逻辑关系而增加额外的存储空间； B、可以方便地随机存取表中的任一节点； C、插入和删除运算较方便； D、由于顺序表要求占用连续的空间，存储分配智能预先进行。 (2) 链式存储结构 1、链表不具备的特点是？（ ） A．可随机访问任一节点。 B．插入删除不需要移动元素。 C．不必事先估计存储空间。 D．所需空间与其长度成正比。 2、（1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第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!=NULL 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、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 2、输入序列为ABC，输出为ABC时（假设元素出栈则输出），经过的栈操作为（ ）。 A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop （2）队列 1、循环队列用数组A【0…Maxsize】存放其元素值，头尾指针是front和rear，则队列中元素个数是（） A、（rear-front-1）%Maxsize B、rear-front C、（rear-front+1）%Maxsize D、（rear-front+Maxsize）%Maxsize 2、一个队列的入队序列是1，2，3，4，则队列的输出序列是（ ）。 A. 4，3，2，1 B. 1，2，3，4 C.1，4，3，2 D. 3，2，1，4 3、用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为多少？( )。 A. 1 和 5 B. 2 和 4 C. 4 和2 D. 5 和1 第4章：只考计算模式串的NEXT值,不考算法，本章所占分值在5分左右 1、串ababaaababaa的next数组为（ ）。 A．012345678999 B．012121111212 C．011234223456 D．012301232234 第5章：数组的存储位置计算，压缩矩阵的存储（不考算法）本章所占分值在5分左右 1、n阶对称矩阵A,将其上三角的元按列优先顺序压缩存放在一维数组B[1…