11、设计算法实现从顺序表中删除所有值在x和y之间的所有元素，要求时间性能为O（n），空间性能为O（1）。
12、设计算法删除顺序表中重复的元素，要求算法移动元素的次数较少，并使剩余元素间的相对次序保持不变。
13、顺序表LA和LB中值非递减有序，设LA的空间足够大，试写一高效算法，将LB合并到LA中，使新生成LA依然有序。高效指的是最大限度的避免移动。
14、设A是线性表（a1，a2，?，an），采用顺序存储，则在等概率下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai和ai+1（1 ≤ i ≤ n）之间的概率为n-i/n(n-1)/2，则平均每插入一个元素要移动的元素个数是多少？
典型题目解析 链表
1、线性表的链式存储结构是一种（ ）的存储结构 A、随机存取B、顺序存取C、索引存取D、散列存取
2、将长度为n的单链表连在长度为m的单链表之后，时间复杂度是（ ） 3、在一个长度为n（n>1）的带头结点的单链表h上，另设有尾指针r指向尾结点，执行（ ）操作与链表的长度有关。
A删除单链表第一个元素 B删除单链表的最后一个元素 C在单链表第一个元素前插入一个新的元素 D在单链表的最后一个元素后插入一个新元素
4、设一个单链表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省时间 A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表 5、单链表中增加一个头结点的目的是（ ）
6
A、使表中至少有一个结点 B、标识表中首结点的位置
C、方便运算的实现 D、说明单链表是线性表的链式存储
6、对于一个线性表既要求能够快速的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）
A、顺序存储 B、链式存储 C、散列存储 D、以上均可
7、若要在O（1）的时间内实现2个循环单链表的首尾相连，则两个循环单链表应各设一个指针，分别指向（ ）
A、各自的头结点 B、各自的尾结点
C、各自的第一个元素节点 D、一个表的头结点，一个表的尾结点
8、在双链表中，指针pa所指结点后面插入pb结点，执行的语句序列是（ ） ①pb->next=pa->next; ②pb->prior=pa; ③pa->next=pb; ④pa->next->prior=pb; A、1234 B、4321 C、3412 D、1432
9、已知非空线性链表由list指示，结点结构为data，link。编写算法，将链表中数据域最小的结点移到链表最前面。要求：不得额外申请新结点。
10、给定一个带头结点的单链表，设head为头指针，设计算法按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。要求：不允许使用额外的存储空间。
11、单链表的就地逆置。
12、两个单链表的操作。 13、已知L为单链表的头结点地址，表中共有m（m>3）个结点，从表中第i（1 L a1 a2 a3 … an 14、设计算法，将双向链表中结点p与其后继结点交换位置。 7 15、单链表的头指针为head，设计算法将链表中记录按照数据域递增的次序进行就地排序。 16、设有两个单链表，一个升序，一个降序。设编写算法，将这两个链表合并为一个有序链表。 17、将下图中23和15的两个结点互换位置 p 23 15 18、两个整数序列a1,a2,?,am和b1,b2,?bn已经存入两个链表中，设计一个算法，判断序列B是否是A的子序列。 19、L1与L2分别为两单链表头结点指针。且两表中结点的数据域均为1个字母。设计把L1中与L2中数据相同的连续结点顺序完全倒置的算法。 20、用顺序表表示集合，设计算法实现集合的求差集运算，要求不另外开辟空间。 21、已知两个不带头结点的单链表A和B分别表示两个集合，并且其元素值递增有序。求两个集合的交集C，并以同样的递增形式存储，要求尽可能节省时间。 22、从键盘输入n个英文单词，输入格式为n,单词1，?，单词n，其中n表示 8 随后输入英语单词个数，试编写算法建立一个单链表，要求：如果单词重复出现，则只在链表上只保留一个；统计单词出现的次数，然后输出次数最多的前k(k 典型题目解析 静态链表 1、静态链表中的指针是（） A、下一元素的地址 B、内存储器的地址 C、下一元素在数组中的位置 D、左链或者右链指向的元素的地址 2、静态链表的相关说法错误的是 ①静态链表既有顺序表的优点又有动态链表的优点，所以，它存取表中第i个元素的时间与i无关。 ②静态链表中能容纳的元素个数在定义表时必须是确定的。 ③静态链表与动态链表在元素的插入、删除上类似，不需要做元素的移动。 A ① ② B ① C ① ② ③ D ② 第三章 栈和队列 考纲分析 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用 （五）特殊矩阵的压缩存储 典型题目解析 栈 1、若一个栈的输入序列是1，2，3，?，n，输出序列是p1，p2，p3?若p1=3，则p2的值是( ) A、一定是2 B、一定是1 C、不可能是1 D、都不对 2、若一个栈的输入序列是p1，p2，?pn，其输出序列是1，2，3?若p3=1，则p1的值是( ) A、可能是2 B、一定是2 C、不可能是2 D、不可能是3 3、表达式3*2^(4+2*2-6*3)-5求值过程中，当扫描到6时，对象栈和算符栈为（ ）。 4、利用栈计算表达式的值时，设置操作数栈OPND，设OPND只有两个存储单元，计算下列表达式时不发生上溢的是（ ） A、a-b*(c-d) B、(a-b)*c-d C、(a-b*c)-d D、(a-b)*(c-d) 5、在表达式求值的运算符栈中，从栈顶到栈底的运算符的优先级是（ ） A、从高到低 B、从低到高 C、无序 D、可能有序可能无序 6、与中缀表达式a*b+c/d-e等价的后缀表达式是（ ） 7、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，执行（ ） A、h->next=s; B、s->next=h; C、s->next=h;h->next=s D、s->next=h->next;h->next=s; 8、设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（ ） 9 A、S1的栈底位置为0，S2的占地位置为n-1 B、S1的栈底位置为0，S2的占地位置为n/2 C、S1的栈底位置为0，S2的占地位置为n D、S1的栈底位置为0，S2的占地位置为1 9、如上题，这样分配的好处是（ ） 10、下列最有效表示栈的链表结构是（ ） A、带头结点的单链表 B、单链表 C、带头结点的双向链表D、双向链表 11、消除递归不一定使用栈，此说法（ ） 12、任何一个递归过程都可以转换成非递归过程。（ ） 13、只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈（ ） 14、用单链表表示栈，栈顶设在链表的（ ） 15、有5个元素，其入栈次序为A、B、C、D、E，在各种可能的出栈序列中，第一个出栈元素为C且第二个出战元素为D的出栈序列有哪几个？ 16、元素abcdef依次进栈，允许进栈、出栈交替进行，但不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ） A、dcebfa B、cbdaef C、bcaefd D、afedcb 17、元素abcde依次进栈，允许进栈、出栈交替进行，则以d为首的出栈序列是（ ） 18、设计一个算法，判断一个算术表达式中的括号是否匹配。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。 典型题目解析 队列 1、若用一个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3，则队列中删除一个元素，再添加2个元素后，rear和front的值分别为（ ）。 2、循环队列的存储空间为数组A[21]，front指向队首元素的前一位置，rear指向队尾元素。假设当前front和rear的值分别是8和3，则队列的长度是（ ）。 3、最不适合用作链队列的链表是（ ） A 只带队首指针的非循环双链表 B 只带队首指针的循环双链表 C 只带队尾指针的循环双链表 D 只带队尾指针的循环单链表 4、下列更适合表示队列的链表结构是（ ） A、单链表B、单循环链表C、双链表D、双循环链表 5、执行（ ）操作时，需要队列作为辅助的存储结构 A、深度优先遍历图 B、广度优先遍历图 C、散列查找 D、遍历二叉树 10