第三章 单链表 题目和答案

1、已知L是带表头的单链表，其P结点既不是首元结点，也不是尾元结点，a.删除p结点的直接后继的语句是11，3，14b.删除p结点的直接前驱的语句是10，12，8，11，3，14c.删除p结点的语句序列是10，7，3，14d.删除首元结点的语句序列是12，10，13，14e.删除尾元结点的语句序列是9，11，3，14（1）p=p->next;(2) p->next=p;(3)p->next=p->next->next;(4)p=p->next->next;(5)while(p)p=p->next;(6)whlie(Q->next){p=Q;Q=Q->next;}(7)while(p->next!=Q)p=p->next;(8)while(p->next->next!=Q)p=p->next;(9)while(p->next->next)p=p->next;(10)Q=p;(11)Q=p->next;(12)p=L;(13)L=L->next;(14)free(Q);2、已知L是带表头的单链表，其P结点既不是首元结点，也不是尾元结点，a.在p结点后插入s结点的语句序列是4，1b.在p结点前插入s结点的语句序列是7，11，8，4，1c.在表首插入s结点的语句序列是5，12d.在表尾插入s结点的语句序列是7，9，4，1或11，9，1，61.p-> next =s;2.p-> next=p-> next-> next;3.p->next=s->next;4.s->next=p-> next;5.s-> next=L;6.s->next=NULL;7.q=p ;8.while(p->next!=q) p=p->next;9.while(p->next!=NULL) p=p->next;10.p =q;11.p=L;12.L=s;13.L=P;3、已知P结点是某双向链表的中间结点，从下列提供的答案中选择合适的语句序列a.在P结点后插入S结点的语句序列是12，7，3，6b.在P结点前插入S结点的语句序列是13，8，5，4c.删除p结点的直接后继结点的语句序列是15，1，11，18d.删除p结点的直接前驱结点的语句序列是16，2，10，18e.删除p结点的语句序列是9，14，171.P->next=P->next->next;2.P->priou=P->priou->priou;3.P->next=S;4.P->priou=S;5.S->next=P;6.S->priou=P;7.S->next=P->next;8.S->priou=P->priou;9.P->priou->next=P->next;10.P->priou->next=P;11.P->next->priou=P;12.P->next->priou=S;13.P->priou->next=S;14.P->next->priou=P->priou;15.Q=p->next;16.Q=P->priou;17.free(P);18.free(Q);。

第3章栈和队列习题1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

A．i B．n-i C．n-i+1 D．不确定（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n （4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A．x=top->data;top=top->link； B．top=top->link;x=top->link；C．x=top;top=top->link； D．x=top->link；（5）设有一个递归算法如下int fact(int n) { //n大于等于0if(n<=0) return 1;else return n*fact(n-1); } 则计算fact(n)需要调用该函数的次数为（）。

A．n+1 B．n-1 C． nD． n+2（6）栈在（）中有所应用。

A．递归调用 B．函数调用 C．表达式求值 D．前三个选项都有（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。

主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是（）。

A．队列 B．栈 C．线性表 D．有序表（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。

关于单向链表的选择题：1.单向链表中，删除一个节点需要的时间复杂度是_______。

A. O(1)B. O(n)C. O(log n)D. O(n^2)2.在单向链表中，插入一个节点需要的时间复杂度是_______。

A. O(1)B. O(n)C. O(log n)D. O(n^2)3.单向链表相比于数组，其优点是_______。

A. 查找速度快B. 插入和删除操作方便C. 存储空间少D. 可以动态扩展4.在单向链表中，若要查找某个节点，则时间复杂度为_______。

A. O(1)B. O(n)C. O(log n)D. O(n^2)5.单向链表的一个缺点是_______。

A. 查找速度慢B. 插入和删除操作不方便C. 存储空间大D. 不能动态扩展6.在单向链表中，要插入一个新的节点，需要修改哪几个节点的指针？A. 新节点本身B. 新节点的父节点C. 新节点的子节点D. 新节点的兄弟节点7.在单向链表中，删除一个节点后，如何处理被删除节点的后继节点的指针？A. 置为空B. 指向被删除节点的父节点C. 指向被删除节点的下一个节点D. 保持不变8.单向链表与双向链表的主要区别是什么？A. 单向链表的节点只有一个指针，而双向链表的节点有两个指针B. 单向链表的节点只能沿一个方向遍历，而双向链表的节点可以沿两个方向遍历C. 单向链表的节点比双向链表的节点更小D. 单向链表的节点没有颜色，而双向链表的节点有颜色9.在单向链表中，如何找到中间的节点？A. 需要遍历整个链表B. 无法找到中间的节点，只能找到第n个节点C. 只能找到头节点和尾节点D. 需要知道头节点的地址和链表的长度10.在单向链表中，插入一个新节点时，需要注意哪些问题？A. 只需要考虑新节点的数据B. 需要考虑新节点的指针指向问题C. 需要考虑新节点的颜色问题D. 需要考虑新节点的年龄问题。

第1章习题选解一、选择题1-1 下列关于数据和逻辑结构的叙述中，哪一个是不正确的（）。

A ) 数据的逻辑结构是数据间关系的描述B) 数据的逻辑结构抽象反映数据元素间的逻辑关系C) 数据的逻辑结构具体反映数据在计算机中的存储方式D) 数据的逻辑结构分为线性结构和非线性结构【解析】本题考点是数据结构的组成。

数据结构包括 3 个方面的内容：数据的逻辑结构、数据的存储结构、数据的运算。

数据的逻辑结构是数据关系的描述，只抽象反映数据元素间的逻辑关系，而不管在计算机中的存储方式；数据结构包括线性结构和非线性结构。

数据的存储结构是逻辑结构在计算机中的存储实现。

数据的运算是逻辑结构相应的各种运算。

【答案】 C1-2 以下关于数据的存储结构的叙述中哪一条是正确的（）。

A) 数据的存储结构是数据间关系的抽象描述B) 数据的存储结构是逻辑结构在计算机存储器中的实现C) 数据的存储结构分为线性结构和非线性结构D) 数据的存储结构对数据运算的具体实现没有影响【解析】本题的考点是数据结构的组成。

数据结构包括 3 个方面的内容：数据的逻辑结构、数据的存储结构、数据的运算。

数据的逻辑结构是数据关系的描述，只抽象反映数据元素间的逻辑关系，而不管在计算机中的存储方式；数据的逻辑结构包括线性结构和非线性结构。

数据的存储结构是逻辑结构在计算机中的存储实现。

数据的运算是逻辑结构相应的各种运算，每一种逻辑结构都有一个运算的集合。

【答案】 B二、简答题1-1 数据结构的存储方式有哪几种？【解析】常用的存储表示方法有四种:1 、顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。

2 、链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。

由此得到的存储表示称为链式存储结构, 通常借助于程序语言的指针类型描述。

第三章栈、队列和数组一、名词解释：1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵二、填空题：1.栈修改的原则是_________或称________，因此，栈又称为________线性表。

在栈顶进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________或________。

2.栈的基本运算至少应包括________、________、________、________、________五种。

3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。

4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。

5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。

6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。

7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。

int InitStack(SqStackTp *sq){ ________;return(1);}8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。

Int Push(SqStackTp *sq,DataType x){ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);}else{________________:________________=x;return(1);}}9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。

单链表考研题库 1. 单链表的基本概念 - 什么是单链表？ - 单链表与数组有何不同？

2. 单链表的实现 - 如何使用类和对象实现单链表？ - 描述单链表节点的一般结构。

3. 单链表的遍历 - 如何遍历单链表？ - 遍历单链表的时间复杂度是多少？

4. 单链表的插入操作 - 如何在单链表的头部插入一个新节点？ - 如何在单链表的尾部插入一个新节点？ - 如何在单链表的中间插入一个新节点？

5. 单链表的删除操作 - 如何删除单链表的头部节点？ - 如何删除单链表的尾部节点？ - 如何删除单链表中的特定节点？

6. 单链表的反转 - 描述单链表反转的过程。 - 反转单链表的时间复杂度是多少？

7. 单链表的查找 - 如何在单链表中查找一个特定值的节点？ - 查找操作的时间复杂度是多少？

8. 单链表的排序 - 描述几种常见的单链表排序方法。 - 每种排序方法的时间复杂度是多少？

9. 单链表的合并 - 如何合并两个已排序的单链表？ - 合并操作的时间复杂度是多少？

10. 单链表的循环引用问题 - 什么是循环引用？ - 如何检测单链表中是否存在循环引用？

11. 单链表的空间复杂度分析 - 单链表的空间复杂度是多少？ - 与数组相比，单链表在空间使用上有何优势？

12. 单链表的动态内存管理 - 如何在单链表中管理动态分配的内存？ - 如何避免内存泄漏？

13. 单链表的应用场景 - 描述单链表在实际应用中的一些场景。 - 为什么在这些场景中选择使用单链表？

结束语 通过上述题目的练习，同学们可以更深入地理解单链表的工作原理和应用场景。单链表作为一种基础的数据结构，在计算机科学中有着广泛的应用。掌握单链表的实现和操作对于深入学习更高级的数据结构和算法非常重要。希望这些题目能够帮助同学们在考研复习中取得更好的成绩。

单链表、双链表、循环链表和静态链表的习题一、单项选择题1.关于线性表的顺序存储结构和链式存储结构的描述中，正确的是（）。

Ⅰ.线性表的顺序存储结构优于其链式存储结构Ⅱ.链式存储结构比顺序存储结构能更方便地表示各种逻辑结构Ⅲ.如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构Ⅳ.顺序存储结构和链式存储结构都可以进行顺序存取A. Ⅰ、Ⅱ、ⅢB. Ⅱ、ⅣC. Ⅱ、ⅢD. Ⅲ、Ⅳ2.对于一个线性表既要求能够进行较快速地插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（）。

A.顺序存储方式B.链式存储方式C.散列存储方式D.以上均可以3.对于顺序存储的线性表，其算法的时间复杂度为O(1)的运算应该是（）。

A.将n个元素从小到大排序B.删除第i个元素（1<i<n）C.改变第i个元素的值（1<=i<=n）D.在第i个元素后插入一个新元素（1<=i<=n）4.下列关于线性表说法正确的是（）。

Ⅰ.顺序存储方式只能用于存储线性结构Ⅱ.取线性表的第i个元素的时间同i的大小有关Ⅲ.静态链表需要分配较大的连续空间，插入和删除不需要移动元素Ⅳ.在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n) Ⅴ.若用单链表来表示队列，则应该选用带尾指针的循环链表A. Ⅰ、ⅡB.Ⅰ、Ⅲ、Ⅳ、ⅤC. Ⅳ、ⅤD. Ⅲ、Ⅳ、Ⅴ5.设线性表中有2n个元素，（）在单链表上实现要比在顺序表上实现效率更高。

A.删除所有值为x的元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素D.交换第i个元素和第2n-i-l个元素的值(i=0,…, n-1)6.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入结点s，则执行（）。

A .s->next=p->next;p->next=s; B.p->next=s->next; s->next=p;C. q->next=s;s->next=p;D. p->next=s;s->next=q;7.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是（）。

第3章栈和队列一、填空题（每空1分，共15分）1。

向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。

2。

栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。

不允许插入和删除运算的一端称为栈底。

3。

队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4。

在一个循环队列中，队首指针指向队首元素的前一个位置。

5。

在具有n个单元的循环队列中，队满时共有n-1 个元素.6. 向栈中压入元素的操作是先存入元素，后移动栈顶指针。

7.从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。

8。

〖00年统考题〗带表头结点的空循环双向链表的长度等于0。

解：二、判断正误(）（每小题1分，共10分）（×）1。

是一个复杂类型。

错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

（×）2。

在表结构中最常用的是线性表,栈和队列不太常用。

错，不一定吧？调用子程序或函数常用，CPU中也用队列。

（√）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（√）4. 对于不同的使用者，一个表结构既可以是栈,也可以是队列，也可以是线性表.正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

( ×）5. 栈和链表是两种不同的数据结构。

错,栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念,二者不是同类项。

（×)6. 栈和队列是一种非线性数据结构。

错,他们都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。

（√）7。

栈和队列的存储方式既可是顺序方式，也可是链接方式。

（√)8。

两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

（×）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

算法与数据结构C语⾔版课后习题答案（机械⼯业出版社）第3,4章习题参考答案第3章栈和队列⼀、基础知识题3.1有五个数依次进栈：1，2，3，4，5。

在各种出栈的序列中，以3，4先出的序列有哪⼏个。

（３在４之前出栈）。

【解答】34215 ，34251，345213.2铁路进⾏列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1，2，3，4，5，6，那么是否能够得到435612， 325641， 154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出"进栈"或"出栈"的序列)。

【解答】输⼊序列为123456，不能得出435612和154623。

不能得到435612的理由是，输出序列最后两元素是12，前⾯4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。

不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。

得到325641的过程如下：1 2 3顺序⼊栈，32出栈，得到部分输出序列32；然后45⼊栈，5出栈，部分输出序列变为325；接着6⼊栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。

得到135426的过程如下：1⼊栈并出栈，得到部分输出序列1；然后2和3⼊栈，3出栈，部分输出序列变为13；接着4和5⼊栈，5，4和2依次出栈，部分输出序列变为13542；最后6⼊栈并退栈，得最终结果135426。

3.3若⽤⼀个⼤⼩为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除⼀个元素，再加⼊两个元素后，rear和front的值分别为多少？【解答】2和43.4设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，⼀个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4，e6，e2，e1，则栈S的容量⾄少应该是多少？【解答】43.5循环队列的优点是什么，如何判断“空”和“满”。

单链表算法题以下是单链表算法题：1. 判断单链表是否有环题目描述：给定一个链表的头节点 head，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

示例：输入：head = [1,2,3,4], pos = -1输出：false解释：链表中没有环。

解题思路：使用快慢指针法，快指针每次移动两个节点，慢指针每次移动一个节点。

如果存在环，快指针最终会追上慢指针并相遇；如果不存在环，快指针会先到达链表尾部。

2. 单链表插入元素题目描述：给定一个链表的头节点 head 和要插入的位置 pos，以及要插入的元素 value。

在链表中插入新元素后，返回插入后的链表。

示例：输入：head = [1,2,3], pos = 2, value = 4输出：[1,2,4,3]解释：在位置 2 处插入元素 4，得到新的链表 [1,2,4,3]。

解题思路：在链表中插入元素需要先找到要插入的位置的前驱节点，然后将新节点插入到前驱节点和后继节点之间。

如果插入位置为链表第一个位置，则需要创建新节点并将其指向头节点；如果插入位置超过了链表的长度，则无法插入元素。

3. 单链表删除元素题目描述：给定一个链表的头节点 head 和要删除的位置 pos，删除链表中第 pos 个节点（从 1 开始计数），并返回删除后的链表。

示例：输入：head = [1,2,3,4], pos = 2输出：[1,3,4]解释：删除位置 2 上的节点 2，得到新的链表 [1,3,4]。

解题思路：在链表中删除元素需要先找到要删除位置的前驱节点，然后将前驱节点的 next 指针指向要删除节点的后继节点，最后释放要删除节点的内存空间。

如果删除位置为链表第一个位置，则需要修改头节点；如果删除位置超过了链表的长度，则无法删除元素。

第三章 栈和队列 一、判断题 1、链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULL。 （ × ） 2、递归定义的数据结构通常不需要用递归的算法来实现对它的操作。（ × ） 二、填空题 1、向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给___栈顶指针_____。 2、迷宫问题是一个回溯控制的问题，最好使用____栈______的方法来解决。 3、有如下递归过程： Void Print(int w) { int i; if (w!=0) { Print(w−1); for (i=1;i<=w;i++) printf(“%3d”,w); printf(“\n”); } } 调用语句print(4)的结果是__________。 1 2 2 3 3 3 4 4 4 4 4、假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时， 需执行下面语句：_ S->next=R->next _________；___ R->next=S _______；R=S； 三、选择题 1、设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A 2 ，第二次出栈得到的元素是 B 4 ；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C 1 ，第二次出队得到的元素是 D 2 。经操作后，最后在栈中或队中的元素还有 E 2 个。 供选择的答案： A～D：①a1 ②a2 ③ a3 ④a4 E：①1 ②2 ③ 3 ④ 0 2、 栈是一种线性表，它的特点是 A 2 。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B 2 ；从栈中弹出（POP）一个元素时，变量T的值 C 1 。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D 6 ，变量T的值是 E 4 。 供选择的答案： A：① 先进先出 ②后进先出 ③进优于出 ④出优于进 ⑤随机进出 B，C：① 加1 ②减1 ③不变 ④清 ⑤ 加2 ⑥减2 D： ① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥a,c E： ① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 3、在做进栈运算时，应先判别栈是否 A 2 ；在做退栈运算时，应先判别栈是否 B 1 。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 2 。 为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 D 4 分别设在这片内存空间的两端，这样，只有当 E 3 时，才产生上溢。 供选择的答案： A，B：①空 ② 满 ③ 上溢 ④ 下溢 C： ①n-1 ② n ③ n+1 ④ n/2 D： ① 长度 ②深度 ③ 栈顶 ④ 栈底 E： ①两个栈的栈顶同时到达栈空间的中心点 ②其中一个栈的栈顶到达栈空间的中心点 ③两个栈的栈顶在达栈空间的某一位置相遇 ④两个栈均不空，且一个栈的栈顶到达另一个栈的栈底 4、 以下哪一个不是队列的基本运算？ B A）在队尾插入一个新元素 B）从队列中删除第i个元素 C）判断一个队列是否为空 D）读取队头元素的值 四、综合题 1、写出下列程序段的输出结果（栈的元素类型SElem Type为char）。 void main( ){ Stack S; char x,y; InitStack(S); x=’c’;y=’k’; Push(S,x); Push(S,’a’); Push(S,y); } 2、写出下列程序段的输出结果：（队列中的元素类型QElem Type为char）。 void main( ){ Queue Q; Init Queue (Q); char x=’e’; y=’c’; EnQueue(Q,’h’); EnQueue (Q,’r’); EnQueue (Q,’y’); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,’a’); while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); }; printf(x); } 答：输出结果为:yhar 3、简述以下算法的功能（栈和队列的元素类型均为int）。 void algo3(Queue &Q) { Stack S; int d; InitStack(S); while(!QueueEmpty(Q)) { DeQueue (Q,d); Push(S,d); }; while(!StackEmpty(S)) { Pop(S,d); EnQueue (Q,d); } } 答：算法功能为：将队列Q中的整数逆置。

第一章数据结构概论1.1 判断下列叙述的对错。

如果正确，在题前打“√”，否则打“⨯”。

(1) 数据元素是数据的最小单位。

(2) 数据结构是数据对象与对象中数据元素之间关系的集合。

(3) 数据结构是具有结构的数据对象。

(4) 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。

(5) 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。

1.2 判断下列叙述的对错。

如果正确，在题前打“√”，否则打“⨯”。

(1) 所谓数据的逻辑结构是指数据元素之间的逻辑关系。

(2) 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。

(3) 数据的逻辑结构与数据元素本身的内容和形式无关。

(4) 数据结构是指相互之间存在一种或多种关系的数据元素的全体。

(5) 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。

1.3 填空题算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。

它应当具有输入、输出、( ① )、有穷性和可执行性等特性。

算法效率的度量分为( ② )和( ③ )。

( ② )主要通过在算法的某些部位插装时间函数来测定算法完成某一规定功能所需的时间。

而( ③)不实际运行算法，它是分析算法中语句的执行次数来度量算法的时间复杂性。

程序所需的存储空间包含两个部分( ④ )和( ⑤ )。

( ④ )空间的大小与输入输出数据的个数多少，数值大小无关；( ⑤)空间主要包括其大小与问题规模有关的成分变量所占空间，引用变量所占空间，以及递归栈所用的空间，还有在算法运行过程中动态分配和回收的空间。

1.4 设n为正整数, 分析下列各程序段中加下划线的语句的执行次数。

(1) for ( int i = 1; i <= n; i++ )for ( int j = 1; j <= n; j++ ) {c[i][j]=0.0;for ( int k = 1; k <= n; k++ )c[i][j] = c[i][j] + a[i][k] * b[k][j];}(2) x = 0; y = 0;for ( int i = 1; i <= n; i++ )for ( int j = 1; j <= i; j++ )for ( int k = 1; k <= j; k++ )x = x + y;1.5 试计算以下求和程序中所有语句的总执行次数。

第3章栈和队列习题1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

A．i B．n-i C．n-i+1 D．不确定（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n （4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；（5）设有一个递归算法如下int fact(int n) { //n大于等于0if(n<=0) return 1;else return n*fact(n-1); }则计算fact(n)需要调用该函数的次数为（）。

A． n+1 B． n-1 C．n D．n+2 （6）栈在（）中有所应用。

A．递归调用B．函数调用C．表达式求值D．前三个选项都有（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。

主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是（）。

A．队列 B．栈C．线性表D．有序表（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。

判断回文palindrome:#include <iostream>#include <string>using namespace std;bool huiwen(string s){int n=s.length();int i,j;i= 0;j=n-1;while(i<j && s[i]==s[j]){ i++;j--;}if(i>=j) return true;else return false;}int main(){string s1;cin>>s1;cout<<huiwen(s1);return 0;}=============（2）设从键盘输入一整数的序列：a1, a2, a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。

算法应对异常情况（入栈满等）给出相应的信息。

#include <iostream>using namespace std;#define OVERFLOW -2#define OK 1#define ERROR 0typedef int SElemType;typedef int Status;typedef struct {SElemType a[5];int top;} SqStack;Status InitStack(SqStack &S){S.top=0;return OK;}Status Push(SqStack &S,SElemType e){if (S.top>4){cout<<"overlow!"<<endl;return ERROR;}else S.a[S.top++]=e;return OK;}Status Pop(SqStack &S,SElemType &e){ if (S.top==0) {cout<<"underflow"<<endl; return ERROR;}e=S.a[--S.top];cout<<e<<endl;return OK;}int main(){ SqStack s;InitStack(s);int n,x,e1;cout<<"n=?"<<endl;cin>>n;for(int i=0;i<n;i++){ cin>>x;if(x!=-1 )Push(s,x);else Pop(s,e1); }return 0;}============（3）假设以I和O分别表示入栈和出栈操作。

链表结点插入删除选择题以下是一些链表结点插入删除的选择题：●题目1：在一个带头结点的单链表中，将结点x插入到结点p之后，则需要修改哪些指针？答案：需要修改p的next指针和x的next指针。

●题目2：在一个带头结点的单链表中，将结点x插入到表头，则需要修改哪些指针？答案：需要修改头结点的next指针和x的next指针。

●题目3：在一个带头结点的单链表中，删除结点x，则需要修改哪些指针？答案：需要修改x的前驱结点的next指针和x的next指针。

●题目4：在一个带头结点的单链表中，删除表头结点，则需要修改哪些指针？答案：需要修改头结点的next指针。

●题目5：在一个带头结点的单链表中，删除表尾结点，则需要修改哪些指针？答案：需要修改表尾结点的前驱结点的next指针。

以下是一些链表结点插入删除的简答题：简答题1：在一个带头结点的单链表中，将结点x插入到结点p之后，其具体操作步骤是什么？答案：●找到结点p。

●将结点x的next指针指向结点p的next。

●将结点p的next指针指向结点x。

简答题2：在一个带头结点的单链表中，将结点x插入到表头，其具体操作步骤是什么？答案：●将结点x的next指针指向头结点的next。

●将头结点的next指针指向结点x。

简答题3：在一个带头结点的单链表中，删除结点x，其具体操作步骤是什么？答案：●找到结点x。

●将结点x的前驱结点的next指针指向结点x的next。

●释放结点x的内存。

简答题4：在一个带头结点的单链表中，删除表头结点，其具体操作步骤是什么？答案：●将头结点的next指针指向头结点的next的next。

●释放头结点的内存。

简答题5：在一个带头结点的单链表中，删除表尾结点，其具体操作步骤是什么？答案：●找到表尾结点的前驱结点。

●将表尾结点的前驱结点的next指针指向NULL。

●释放表尾结点的内存。