50、在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点时，需要进行的操作为____________和____________语句。 数据结构复习题：线性表 问答题
1、线性表有两种存储结构：一是顺序表，二是链表。试问： (1)两种存储表示各有哪些主要优缺点?
(2)如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?
(3)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构?为什么?
解答：(1)顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。 (2)应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。
(3)应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。 2、用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么?
不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、 扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。 3、在单链表和双向表中，能否从当前结点出发访问到任一结点?
在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。 4、编写下列算法
(1)向类型有list的线性表L的第i个元素（0≤i≤L.len）之后插入一个新元素x。 (2)从类型为list的线性表L中删除其值等于x的所有元素。
(3)将两个有序表A和B合并成一个有序表C，其中A，B，C均为list类型的变参。 (1) 解答: status insert(SqList L,int i,ElemType x){
// 向线性表L中第i个元素之后插入值为x的新元素 (1) if (L.len = =m0) error('overflow');
(2) if (i<0) || (i>L.len) error ('out of range'); (3) for (j=L.len ;j>= i＋1;--j ) L.vec[j＋1]＝L.vec[j]; }
(4) L.vec[i＋1]＝x; (5) L.len＝len＋1; }
(2) 解答: status delete(L,x) {
// 从线性表L中删除其值等于x的所有元素 i＝1;
while (i<＝L.len ) if (L.vec[i]= =x ){
- 16 -
(Ⅰ) for( j＝i＋1 ;j<= L.len ;++j) L.vec[
5、编写下列算法，假定单链表的表头指针用HL表示，类型为linklist。 (1)将一个单链表中的所有结点按相反次序链接。 (2)删除单链表中第i个（i≥1）结点。 (3)删除单链表中由指针p所指向的结点。
(4)从带有附加表头结点的循环单链表中删除其值等于x的第一个结点。 (5)在单链表中指针p所指结点之前插入一个值为x的新结点。 (6)从循环单链表中查找出最小值。
(7)根据一维数组A(1:n)中顺序存储的具有n个元素的线性表建立一个带有附加表头结 点的单链表。 解答：(1)将一个单链表中的所有结点按相反次序链接。 (1) 解答: status contrary(HL){
// 使HL单链表中的所有结点按相反次序链接
p＝HL ; //p指向未被逆序的第一个结点，初始指向原表头结点 HL＝nil; //HL指向逆序后的表头结点，初始值为空 while (p!=nil ){
(1) q＝p; //q指向将被逆序链接的结点 (2) p＝p＾.next; (3) q＾.next＝HL; (4) HL＝q; } }
(2)删除单链表中第i个（i≥1）结点。 (2) 解答:status delete(HL,i){
(1) if (i<＝0) or (HL＝nil) error('not h&&le'); (2) if (i＝1 )
{ HL＝HL->next; return ; }
(3) j＝1; p＝HL; //p指针所指向的结点，是单链表中第j 6、对链表设置头结点的作用是什么?(至少说出两条好处)
解答：(1) 对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。
(2) 对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。
7、在单链表、双链表和单循环表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？若可以，其时间复杂度各为多少？
解答：1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。
2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，
- 17 -
所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。 8、简述顺序表和链表存储方式的特点。
答：顺序表可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率；而链表内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序表方便，但结点的插入、删除操作较简单。
9、有两个递增有序表，设计一个算法将它们归并成一个有序表(假设每个表中没有重复关键字的元素，归并时重复关键字的元素只归并一次)。 答：void Merge (LinkList &La, LinkList Lb) { pa=La->next; pb=Lb->next; p=La; while(pa && pb)
{ if (pa->data<=pb->data)
{p->next=pa; p=pa; pa=pa->next;} else
{p->next=pb; p=pb; pb=pb->next;} }
if(pa) p->next=pa; else p->next=pb; free(Lb); }
3 栈和队列
沈阳理工大学应用技术学院
信息与控制学院 计算机科学与技术教研室
2011-5-8
数据结构复习题：栈和队列
- 18 -
单选题
1、在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针， 则当做退栈处理时，top变化为_____。
2、向顺序栈中压入元素时，是__先移动栈顶指针，后存入元素___。
3、在一个顺序存储的循环队列中，队首指针指向队首元素的__前一个位置___。 4、若进栈序列为1,2,3,4,进栈过程中可以出栈，则_____不可能是一个出栈序列。
5、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是_____。
6、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是_____。
7、向一个栈项指针为hs的链栈中插入一个*s结点时，则执行_____。
8、在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行_____。
9、栈的特点是_______队的特点是______ 10、栈和队列的共同点是_______。
11、一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是________。
12、若己知一个栈的进栈序列是1,2,3,?,n,其输出序列为p1,p2,p3,?,pn,若p1=n,则pi(1 16、若己知一个栈的进栈序列p1,p2,p3,?,pn，输出序列是1,2,3,?,n。若pn=1,则pi(1<=i 19、最不适合用作链栈的链表是___只有表头指针没有表尾指针的循环单链表_____。 20、向一个栈项指针为hs的链栈中插入一个s所指结点时，则执行_______。 21、从一个栈项指针为hs的链栈中删除一个结点时，用x保存被删结点的值，则执行__x=hs->data;hs=hs->next____。 22、一个队列的入队序列是1,2,3,4,则队列的输出序列是_______。 23、判定一个环形队列qu(最多元素为MaxSize)为空的条件是________。 24、判定一个环形队列qi(最多元素为MaxSize)为满队列的条件是________。 25、环形顺序队列中是否可以插入下一个元素,________。 26、环形队列用数组A[0...MaxSize-1]存放其元素值,己知其头尾指针分别是front和rear,则当前队列的元素个数是_______。 27、若用一个大小为6的一维数组来实现环形队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是______。 28、最不适合用作链队的链表是__只带队头指针的非循环双链表____。 29、在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是_______。 30、在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算是_______。 31、用单链表表示的链队的队头在链用不着的____链头____位置。 32、中缀表达式A*(B+C)/(D-E+F)的后缀表达式是________。 33、己知一个栈的进栈序列是ABC,出栈序列为CBA,经过的栈操作是________。 34、判定一个顺序栈st为(元素个数最多为MaxSize)空的条件为______。 35、判定一个顺序栈st(元素个数最多为MaxSize)为栈满的条件是______。 36、表达式a*(b+c)-d的后缀表达式是______。 - 19 - 37、表达式(2+2*3)*2+6*3/2的后缀表达式是______。 38、链栈与顺序栈相比有一个明显的优点,即___通常不会出现栈满的情况___。 39、最不适合用作链栈的链表是__只有表头指针没有表尾指针的循环单链表____。 40、如果以链表作为栈的存储结构,则退链栈操作时___必须差别链栈是否空___。 41、向一个不带头结点的栈指针为1st的链栈中插入一个s所指结点时,则执行______。 42、从一个不带头结点的栈顶指针为1st的链栈中删除一个结点时,用x保存被删结点的值,则执行______。 43、一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是______. 44、在一个长度为n的顺序存储的集合中查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度为_________。 45、在一个长度为n的链接存储的集合中查找值为x的元素时，算法的时间复杂度为___O(n)______。 46、已知一个元素x不属于一个长度为n的顺序或链接存储的集合Ｓ中的元素，把它插入集合Ｓ时不进行比较过程，则插入过程的时间复杂度为_________。 47、设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为____O(n*t)_____。 数据结构复习题：栈和队列 判断题 1、栈底元素是不能删除的元素。 2、顺序栈中元素值的大小是有序的。 3、在n个元素进栈后,它们的出栈顺序和进栈顺序一定正好相反。 4、栈顶元素和栈底元素有可能是同一个元素。 5、若用S[1]-S[m]表示顺序栈的存储空间,则对栈的进栈、出栈操作最多只能进行m次。F 6、空栈没有栈顶指针。 数据结构复习题答案：栈和队列 判断题 1、False 2、False 3、True 4、True 5、False 6、False 数据结构复习题：栈和队列 算法分析题 1、设计一个算法,利用栈的基本运算将指定栈中的内容进行逆转。 status Nizhuan(sqstacks, int a, int b, int t) { If(s.top==s.base) error(‘no data’); for(i=0;i a=*--top; b=*s.base; - 20 -
