A、插入操作 B、结点移动 C、算术表达式 D、删除操作 20、对于顺序表的优缺点，以下说法错误的是（ ） A、无需为表示结点间的逻辑关系而增加额外的存储空间 B、可以方便地随机存取表中的任一结点 C、插入和删除运算较方便
D、由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
21、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
A、顺序表 B、单链表 C、双链表 D、单循环链表 22、循环链表主要优点是（ ） A、不再需要头指针了
B、已知某个结点的位置后，能够容易找到它的直接前趋 C、在进行插入、删除运算时，能更好地保证链表不断开 D、从表中任一结点出发都能扫描到整个链表
23、在线性表的下列存储结构中，读取元素花费时间最少的是（ ） A、单链表 B、双链表 C、循环链表 D、顺序表
二、填空题
１、在线性结构中，第一个结点（ ）前趋结点，其余每个结点有且只有（ ）个前趋结点。
２、在顺序表中插入或删除一个元素，需要平均移动（ ）元素，具体移动的元素个数与（ ）有关。 ３、已知Ｌ是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现： （１）表首插入Ｓ结点的语句序列是（ ）。 （２）表尾插入Ｓ结点的语句序列是（ ）。
Ａ、Ｐ->next=S; Ｂ、P=L; Ｃ、L=S; Ｄ、P->next=S->next; Ｅ、S->next=P->next; Ｆ、S->next=L; Ｇ、S->next=NULL; Ｈ、while(P->next!=Q)p=p->next; Ｉ、while(P->next!=NULL)P=P->next; 4、已知L是带表头结点的非空单链表，试从下列提供的答案中选择合适的语句序列。
（1）删除首元结点的语句序列是（ ） ,（2）删除尾元结点的语句序列是（ ） A、P=P->next; B、P->next=P->next->next; C、while(P!=NULL)p=p->next;
D、while(Q->next!=NULL){P=Q;Q=Q->next;} E、while(P->next!=Q)P=P->next;
F、Q=P; G、Q=P->next; H、P=L; I、L=L->next; J、free(Q);
5、已知L是带表头结点的非空链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 （1）删除P结点的直接后继结点的语句序列是（ ）, （2）删除P结点的直接前趋结点的语句序列是（ ）
A、P->next=P->next->next; B、P=P->Pnext->next; C、while(P->next!=Q)P=P->next;
D、while(P->next->next=Q)P=P->next; E、Q=P; F、Q=P->next; G、P=L; H、L=L->next; I、free(Q); 6、已知结点编号，在各结点查找概率相等的情况下，从n个结点的单链表中查找一个结点，平均要访问（ ）个结点，从n个结点的双链表中查找一个结点，平均要访问（ ）个结点。
7、对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是（ ）；在值域为给定值的结点后插入一个新结点的时间复杂度是（ ）。 8、单链表是（ ）的链接存储表示。
9、单链表中设置头结点的作用是（ ）。
10、在单链表中，除首元结点外，任一结点的存储位置由（ ）指示。 11、在非空双向循环链表中，在结点q的前面插入结点p的过程如下： p->prior=q->prior; q->prior->next=p;p->next=q;( ); 12、在双向链表中，每个结点有两个指针域，一个指向（ ），另一个指向（ ）。
13、顺序表中逻辑上相邻的元素的物理位置（ ）相邻。单链表中逻辑上相邻的元素的物理位置（ ）相邻。
14、为了便于讨论，有时将含n(n≥0)个结点的线性结构表示成(a1，a2,?,an)，其中每个ai代表一个______。a1称为______结点，an称为______结点，i称为ai在线性表中的________。对任意一对相邻结点ai、ai┼1(1≤i 15、线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______；除终端结点没有直接______外，其它结点有且仅有一个直接______. 16、所有结点按1对1的邻接关系构成的整体就是______结构。 17、线性表的逻辑结构是______结构。其所含结点的个数称为线性表的__________。 18、在单链表中，指针p所指结点为最后一个结点的条件是___________。 三、判断题 1. 顺序存储的线性表可以随机存取。 2. 顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要 移动。 3. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据 对象。 4. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。 5. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 6. 在单链表中，可以从头结点进行查找任何一个元素。 7. 线性表的链式存储结构优于顺序存储结构。 8. 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。 9. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 10. 顺序存储方式只能用于存储线性结构。 四、简答题 1、 若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？ 2、 描述概念：头指针、头结点、首元结点的区别？ 3、 设A是一个线性表（a1a2…an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需 要移动的元素个数为多少？若元素插在ai与ai+1之间（0<=I<=n-1）的概率为2(n-i)/(n(n+1))，则平均每插入一个元素所要移动的元素个数又是多少？ 4、为什么在单循环链表中设置尾指针比设置头指针更好？ 5、双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点*p从相应的链表中删除？若可以，其时间复杂度各为多少？ 6、下列算法的功能是什么？ LinkedList test1(LinkedList L) {//L是无头结点的单链表 ListNode *q,*p; if(L&&L->next) {q=L ; L=L->next; p=L; while(p->next) p=p->next; p->next=q; q->next=NULL; } return L; } 7、如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构。为什么？ 8、若线性表的总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构。为什么？ 9、设有多项式a(x)=9+8x+9x4+5x10 b(x)=-2x+22x7-5x10 （1） 用单链表给出a(x)、b(x)的存储表示； （2） 设c (x)=a(x)+b(x)，求得c(x)并用单链表给出其存储表示。 五、设计题 1、编写一个函数将一个顺序表A（有多个元素且任何元素不为0）分拆成两个顺序表，使A中大于0的元素存放在B中，小于0的元素存放在C中。 2、设顺序表L中的数据元素递增有序。试写一算法，将e插入到顺序表的适当位置，插入后保持该表的有序性。 3、A、B为元素递增有序排列的单链表（同一表中可能有相同元素），编写算法另建一单链表C，保存两个表的公共元素，要求C的元素值各不相同且递增有序。 4、设有一个由正整数组成的无序单链表，编写算法实现下列功能： （1） 找出最小值结点，且显示该数值。 （2） 若该数值为奇数，则将其与直接后继结点的数值交换。 （3） 若为偶数，则将其直接后继结点删除。 六、编程附加题 1. 试分别用顺序表和单链表作为存储结构，实现将线性表（a0,a1,a2,….an-1）就地逆置的操作，所谓“就地” 指辅助空间为O（1）。 2. 设顺序表L是一个递增（允许有相同的值）有序表，试写一算法将x 插入L中，并使L仍为一个有序 表。 3. 设单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有序性。 4. 试写出在无头结点的单链表的第i个元素之前插入一个元素的算法。 5. 设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式 存储将A和B归并成一个仍按元素值递增有序的线性表C，请分析算法的时间复杂度。 6. 设指针la和lb分别指向两个无头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素， 并将这些元素插入到lb中第j个结点之前的算法。 7. 单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点（若表中有这样 的结点），同时释放被删结点空间，这里min和max是两个给定的参数。请分析你的时间复杂度。 8. 编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和 pb，使得A链表中含有链表A中的序号为奇数的元素，而B链表中含有原链表A中的序号为偶数的元素，且保持原来的相对顺序。 9. 假设以两个元素依值递增有序排列的线性表A,B分别表示两个集合，先要求另辟空间构造一个线性表 C,其元素为两集合的交集，且表C中的元素也依值递增有序排列。是对顺序表编写求C的算法。 10. 设有线性表A=(a1,a2,.. .,am)和B=(b1,b2,.. .,bn)。试写合并A、B为线性表C的算法，使得： C=??(a1,b1,...,am,bm,bm?1,bn)当m?n; (a,b,...,a,b,a,...,a)当m?n;nnn?1m?11线性表A,B和C均以单链表作存储结构，且C表利用A表和B表的结点空间。 11. 假设在长度大于1的单循环链表中，既无头结点也无头指针。S为指向链表中某个结点的指针，试编写 算法删除结点*s 的直接前驱结点。 12. 计算带头结点的循环链表的结点个数。 13. 已知由单链表表示的线性表中，含有三类字符的数据元素（如：字母字符、数字字符和其他字符），试 编写算法构造三个以循环链表表示的线性表使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 14. 已知A,B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C 表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注：题中没特别指明同一表中的元素值各不相同）。 15. 双向循环链表中，设计满足下列条件的算法。 （1）在值为x的结点之前插入值为y的结点。 （2）删除值为x的结点。 16. 设有一个循环双链表，其中有一结点的指针为P，编写算法将P与其右边的一个结点进行交换。 17. 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个可访问频度域freq，在链表被 起用之前，其值均初始为0。每当链表进行一次LocateNode（L，x）运算时令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减次序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode的运算的算法。 18. 给出用单链表存储多项式的结构，并编写一个按指数值递增次序输入所产生的多项式链表的过程。 19. 根据上题的多项式链表结构，编写一个过程实现两个多项式相加的运算。 20. （Josephus环）任给正整数n、k，按下述方法可得排列1，2，?，n的一个置换:将数字1，2，?，n 环形排列，按顺时针方向从1开始 计数；计满K时输出该位置上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10，k=3时，输出的置换是3，6，9，2，7，1，8，5，10。分别以数组和以不带头结点的、已知尾指针的单循环链表为存储结构解决上述问题。 21 已知在一维数组A[1..m+n]中依次存放着两个向量（a1,a2,….am）和（b1,b2,….bn），编写算法将两个向量的位置互换，即把（b1,b2,….bn）放到（a1,a2,….am）之前。 22 给定一个不带头结点的单链表，编写计算此链表长度的算法。 23 设ha和hb分别是两个带头结点的非递减有序单链表的表头指针， 试设计一个算法， 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。 24 设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法： (1)找出最小值结点，且打印该数值； (2)若该数值是奇数，则将其与直接后继结点的数值交换； (3)若该数值是偶数，则将其直接后继结点删除； 25 利用顺序表的操作，实现以下的函数。 (1) 从顺序表中删除具有最小值的元素并由函数返回被删元素的值，空出的位置由最后一个元素填补。 (2) 从顺序表中删除具有给定值x的所有元素。 (3) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。 26 如果以单链表表示集合，设计算法建立先后输入的两个集合的差。 27 已知一个线性表中的元素按元素值非递减有序排列，分别以顺序存储和链式存储编写一个算法删除表中多余的值相同的元素。 28 设A=（a1,a2,a3,......an）和B=(b1,b2,.. .,bm)是两个顺序表（假定所含数据元素均为整数）。若n=m且 ai=bi(i=1,.. .,n),则称A=B;若ai=bi(i=1,...,j)且aj+1 29 已知一个循环单链表如图2.1所示，编写一个算法将所有箭头方向取反。 head a1 a2 an ? 图2.1 30 假设有一个单循环链表，其结点含有三个域：prior，data，和next。其中data为数据域，next指向后继结点，prior为指针域，它的值为空指针，试编写算法将此表改为双向循环链表。 31 设A是一个双向循环链表，其表中元素递增有序。试写一算法插入一个元素x，使表A中的元素依然递增有序。 32写出将双向循环链表倒置的算法。 33 设计一算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式各自仅有奇次幂或偶次幂项，并要求利用原链表中的结点空间来构造这两个链表。 34 设以带头结点的双向链表表示的线性表L=(a1,a2,…,an)，试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,…,an,a4,a2)。 35 设一单向链表的头指针为head，链表的记录中包含着整数类型的key域，试设计算法，将此链表的记录按照key 递增的顺序进行就地排序。 第三章栈与队列 练习题 一、 选择题 1、栈结构通常采用的两种存储结构是（ ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2、设栈ST用顺序存储结构表示，则栈ST为空的条件是（ ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3、向一个栈顶指针为HS的链栈中插入一个s结点时，则执行（ ） A、HS->next=s; B、s->next=HS->next;HS->next=s; C、s->next=HS;HS=s; D、s->next=HS;HS=HS->next; 4、从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删除结点的值，则执行（ ） A、x=HS;HS=HS->next; B、HS=HS->next;x=HS->data; C、x=HS->data;HS=HS->next; D、s->next=Hs;Hs=HS->next; 5、表达式a*(b+c)-d的后缀表达式为（ ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6、中缀表达式A-（B+C/D）*E的后缀形式是（ ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7、一个队列的入列序列是1，2，3，4， 则队列的输出序列是（ ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8、循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为空的条件是（ ） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9、循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为满的条件是（ ）