数据结构-回文判断

第1章4．答案：（1）顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。

（2）链式存储结构顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。

但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。

所以链式存储结构通常借助于程序设计语言的指针类型来描述。

5. 选择题(1)~(6)：CCBDDA6．（1）O(1) （2）O(m*n) （3）O(n2)（4）O(log3n) （5）O(n2) （6）O(n)第2章1．选择题（1）~（5）：BABAD （6）~（10）：BCABD （11）~（15）：CDDAC 2．算法设计题（1）将两个递增的有序链表合并为一个递增的有序链表。

要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。

表中不允许有重复的数据。

[题目分析]合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。

如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。

当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后。

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){//合并链表La和Lb，合并后的新表使用头指针Lc指向pa=La->next; pb=Lb->next;//pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点Lc=pc=La; //用La的头结点作为Lc的头结点while(pa && pb){ if(pa->data<pb->data){pc->next=pa; pc=pa; pa=pa->next;}//取较小者La中的元素，将pa链接在pc的后面，pa指针后移else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;}//取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移else //相等时取La中的元素，删除Lb中的元素{pc->next=pa;pc=pa;pa=pa->next;q=pb->next; delete pb ; pb =q;}}pc->next=pa?pa:pb; //插入剩余段delete Lb; //释放Lb的头结点}（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。

数字的特殊性质回文数和素数数字的特殊性质：回文数和素数数字在数学中具有许多特殊性质，其中回文数和素数是两个常见且有趣的概念。

本文将介绍回文数和素数的定义、特点及其在数学和实际生活中的应用。

一、回文数回文数是指从左到右和从右到左读起来都相同的数。

例如，121、12321和1234321都是回文数。

回文数的特点是在十进制表示中，各个位数上的数字按对称排列。

回文数不仅局限于十进制表示，也存在于其他进制中，如二进制、八进制和十六进制等。

例如，十进制数121在二进制中表示为1111001，同样也是一个回文数。

回文数在数学中有广泛的研究和应用。

它们是对称性的具体体现，与对称几何和对称代数等领域有着紧密的联系。

此外，在计算机科学中，回文数被广泛应用于字符串处理和数据结构等领域。

二、素数素数是指除了1和自身以外没有其他因数的正整数。

素数的特点是只能被1和自身整除，不能被其他正整数整除。

例如，2、3、5、7和11等都是素数，而4、6和9等则不是素数。

素数在数学中一直以来都备受关注。

它们是数论中的重要研究对象，涉及到素数定理、费马大定理和哥德巴赫猜想等重要问题。

同时，在加密算法和密码学中，素数也起到了至关重要的作用。

三、回文数和素数的联系及应用回文数和素数虽然属于不同的数学概念，但它们之间存在一些有趣的联系和应用。

1. 回文素数回文素数是同时具备回文数和素数特性的数。

例如，131和313都是回文素数，因为它们既是回文数又是素数。

回文素数在数学研究中常常成为热门话题，因为它们具备两个特殊性质，被认为是十分珍稀的数字。

2. 素数回文对素数回文对是指两个素数互为回文数。

具体来说，两个素数分别从左到右和从右到左读起来都相同，且互为素数。

素数回文对在数论中也备受关注，被认为是一种特殊的数对组合。

4和回文素数13就是一个素数回文对的例子，它们既是素数，又是回文数。

3. 数字颠倒操作回文数和素数的性质还可以通过数字颠倒操作进一步发掘。

回文数c++语言程序编写回文数是指从左往右和从右往左读都相同的整数。

在C++语言中，我们可以编写一个程序来判断一个数是否为回文数。

首先，我们需要从用户那里获取一个整数作为输入。

可以使用`cin`来获取用户输入的整数。

接下来，我们需要编写一个函数来判断一个数是否为回文数。

我们可以将该函数命名为`isPalindrome`。

在这个函数中，我们可以使用以下步骤来判断一个数是否为回文数：1. 将输入的整数转化为字符串。

可以使用`to_string`函数来完成这一步骤。

2. 使用两个指针分别指向字符串的开头和结尾。

比较两个指针指向的字符是否相同。

3. 如果两个指针指向的字符相同，则将两个指针向中间移动，继续比较下一个字符。

4. 如果两个指针指向的字符不同，则返回`false`，说明该数不是回文数。

5. 当两个指针相遇时，说明已经比较完了所有的字符，返回`true`，说明该数是回文数。

下面是一个完整的示例代码：```cpp#include <iostream>using namespace std;bool isPalindrome(int num) {string str = to_string(num);int left = 0;int right = str.length() - 1;while (left < right) {if (str[left] != str[right]) { return false;}left++;right--;}return true;}int main() {int num;cout << '请输入一个整数: ';cin >> num;if (isPalindrome(num)) {cout << num << '是回文数' << endl;} else {cout << num << '不是回文数' << endl;}return 0;}```在上面的示例代码中，我们首先使用`cin`来获取用户输入的整数。

第二章习题与解答一判断题1．线性表的逻辑顺序与存储顺序总是一致的。

2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二单选题 (请从下列A，B，C，D选项中选择一项)1．线性表是( ) 。

(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。

4．用链表表示线性表的优点是（）。

(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

(A)单链表(B)双链表(C)单循环链表(D)带头结点的双循环链表6．循环链表的主要优点是( )。

(A)不在需要头指针了(B)已知某个结点的位置后，能够容易找到他的直接前趋(C)在进行插入、删除运算时，能更好的保证链表不断开(D)从表中的任意结点出发都能扫描到整个链表7．下面关于线性表的叙述错误的是( )。

《数据结构》课程上机实验指导书实验一【实验名称】顺序表的基本算法【实验目的】创建一个顺序表，掌握线性表顺序存储的特点。

设计和验证顺序表的查找、插入、删除算法。

【实验要求】（1）从键盘读入一组整数，按输入顺序形成顺序表。

并将创建好的顺序表元素依次打印在屏幕上。

（2）设计一个带选择菜单的主函数，菜单中具备任意选择删除、插入、查找数据元素的功能。

（3）当选择删除功能时，从键盘读入欲删除的元素位置或元素值，按指定方式删除；当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号。

（4）每种操作结束后，都能在屏幕上打印出此时顺序表元素的遍历结果。

【实验步骤】1、实验前先写好算法。

2、上机编写程序。

3、编译。

4、调试。

例程：书上参考算法2-1，2-4，2-5，2-6，2-8！带菜单的主函数参考书上综合实例！注意：顺序表的结构体！typedef struct{datatype items[listsize];int length;}SpList;实验二【实验名称】单链表的基本算法【实验目的】创建一个单链表，掌握线性表链式存储的特点。

设计和验证链表的查找、插入、删除、求表长的算法。

【实验要求】（1）从键盘读入一组整数，按输入顺序形成单链表。

并将创建好的单链表元素依次打印在屏幕上。

（注意：选择头插法或者尾插法！）（2）设计一个带选择功能菜单的主函数，菜单中至少具备任意选择删除、插入、查找数据元素，和求单链表表长等几项功能。

（3）当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。

（4）每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果。

【实验步骤】1、实验前先写好算法。

第1章绪论知识点归纳一、数据结构概述1.数据结构的定义（1）基本概念数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。

（2）相关术语① 数据元素数据元素又称元素、节点、顶点、记录等。

数据元素是数据的基本单位。

有时候，一个数据元素可以由若干个数据项组成。

② 数据项数据项又称字段或域，它是具有独立含义的最小数据单位。

③ 数据对象数据对象是性质相同的数据元素的集合，它是数据的子集。

（3）数据结构的内容① 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。

② 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。

③ 施加在数据上的操作，即数据的运算。

（4）逻辑结构数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

（5）存储结构数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。

一般只在高级语言（例如C／C++语言）的层次上讨论存储结构。

数据的运算最终需在对应的存储结构上用算法实现。

总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。

（6）数据结构的表示对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。

描述数据结构通常采用二元组表示：B=（D，R）其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R组成，即：D={d i | 1≤i≤n，n≥0}R={r j | 1≤j≤m，m≥0}其中d i表示集合D中的第i个数据元素（或节点），n为D中数据元素的个数，特别地，若n=0，则D 是一个空集。

《数据结构（C语言版第2版）》（严蔚敏著）第三章练习题答案第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答案：C解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。

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

A．i B．n-i C．n-i+1 D．不确定答案：C解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n答案：D解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（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；答案：A解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。

单元练习5一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（ㄨ）（1）串是n个字母的有限序列。

（√）（2）串的数据元素是一个字符。

（ㄨ）（3）串的长度是指串中不同字符的个数。

（ㄨ）（4）如果两个串含有相同的字符，则说明它们相等。

（ㄨ）（5）如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。

（√）（6）串的堆分配存储是一种动态存储结构。

（ㄨ）（7）“DT”是“DA TA”的子串。

（ㄨ）（8）串中任意个字符组成的子序列称为该串的子串。

（√）（9）子串的定位运算称为模式匹配。

（√）（10）在链串中为了提高存储密度，应该增大结点的大小。

二．填空题（1）由零个或多个字符组成的有限序列称为字符串（或串）。

（2）字符串按存储方式可以分为：顺序存储、链接存储和堆分配存储。

（3）串的顺序存储结构简称为顺序串。

（4）串顺序存储非紧凑格式的缺点是：空间利用率低。

（5）串顺序存储紧凑格式的缺点是对串的字符处理效率低。

（6）串链接存储的优点是插入、删除方便，缺点的空间利用率低。

（7）在C或C++语言中，以字符\0 表示串值的终结。

（8）空格串的长度等于空格的个数。

（9）在空串和空格串中，长度不为0的是空格串。

（10）两个串相等是指两个串相长度等，且对应位置的字符都相同。

（11）设S="My Music"，则LenStr(s)= _ 8 。

（12）两个字符串分别为：S1="Today is"，S2="30 July,2005",ConcatStr(S1,S2)的结果是： Today is 30 July,2005 。

（13）求子串函数SubStr("Today is 30 July,2005",13,4)的结果是：July 。

（14）在串的运算中，EqualStr(aaa,aab)的返回值为<0 。

（15）在串的运算中，EqualStr(aaa,aaa)的返回值为0 。

数据结构（C语⾔版）习题解答1.3设n是正整数。

试写出下列程序段中⽤记号“△”标注的语句的频度：(2) i=1; k=0;do {△k+=10*i;i++;}while(i<=n-1)当n=1时，执⾏1；当n>=2时，执⾏n-1次；(3)i=1; k=0;do {△k+ = 10*i; i++;}while(i==n);当n=2时，执⾏2次；当n!=2时，执⾏1次；(4) i=1; j=0;while(i+j≤n) {△if(i}执⾏n次；(5) x=n; y=0; //n是不⼩于1的常数while(x>=(y+1)*(y+1)){△y++;}执⾏向下取整)(6) x=91; y=100;while ( y>0 )△if(x>100) { x-=10; y--; }else x++ ;}If语句执⾏100次(7) for( i=0; ifor( j=i; jfor( k=j; k△x+=2;过程：n1n1i0j in(n1)(n2) (n j)6--==++ -=∑∑第⼆章2.3 已知顺序表La中数据元素按⾮递减有序排列。

试写⼀个算法，将元素x插到La的合适位置上，保持该表的有序性。

思路：先判断线性表的存储空间是否满，若满返回Error；否则从后向前先移动数据，找到合适的位置插⼊。

Status Insert_SqList(SqList &La,int x)//把x 插⼊递增有序表La 中{if(La.length==La.listsize) return ERROR;for(i=La.length-1;La.elem[i]>x&&i>=0;i--)La.elem[i+1]=La.elem[i];La.elem[i+1]=x;La.length++;return OK;}//Insert_SqList2.5 试写⼀个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表（a1,a2, ..., an-1,an）逆置为(an,an-1, ..., a2,a1//思路就是两个指⽰变量i，j同时分别从顺序表的开始和结尾处相向改变void reverse(SqList &A)//顺序表的就地逆置{ElemType p;for(i=1,j=A.length;i{//A.elem[i]<->A.elem[j];p=A.elem[i];A.elem[i[=A.elem[j];A.elem[j]=p;}}//reverse2.7 已知线性表L采⽤顺序存储结构存放，对两种不同情况分别写出算法，删除L中多余的元素，使得L中没有重复元素：（1）L中数据元素⽆序排列；(2)L中数据元素⾮递减有序排列。