第二章 顺序表

数据结构练习题线性表习题及答案精品文档第二章线性表一．名词解释1.线性结构2.数据结构的顺序实现3.顺序表4.链表5.数据结构的链接实现6. 建表7.字符串8.串9.顺序串 10.链串二、填空题1.为了便于讨论，有时将含n(n>=0)个结点的线性结构表示成(a，a,……a)，其中每n12个a代表一个______。

a称为______结点，a称为______结点，i称为a在线性表中的________ii1n或______。

对任意一对相邻结点a、a(1<=i<n),a称为a的直接______a称为a的直iii┼1i┼1┼i1i接______。

< bdsfid="75" p=""></n),a称为a的直接______a称为a的直iii┼1i┼1┼i1i接______。

<>2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。

不含任何结点的线性结构记为______或______。

3.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______.4.所有结点按1对1的邻接关系构成的整体就是______结构。

5.线性表的逻辑结构是______结构。

其所含结点的个数称为线性表的______，简称______.6.表长为O的线性表称为______7.线性表典型的基本运算包括:______、______、______、______、______、______等六种。

8.顺序表的特点是______。

9.顺序表的类型定义可经编译转换为机器级。

假定每个datatype 类型的变量占用k(k>=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点a的存储地址为______。

数据结构考研笔记整理（全）一、第二章线性表●考纲内容●一、线性表的基本概念●线性表是具有相同数据结构类型的n个数据元素的有限序列；线性表为逻辑结构，实现线性表的存储结构为顺序表或者链表●二、线性表的实现●1、顺序表●定义(静态分配)●#define MaxSize 50 \\ typedef struct{ \\ ElemType data[MaxSize];\\ intlength;\\ }SqList;●定义(动态分配)●#define MaxSize 50\\ typedef strcut{\\ EleType *data; //指示动态非配数组的指针\\ int MaxSize,length;\\ }SqList;●c的动态分配语句为L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);●c++动态分配语句为L.data=new ElemType[InitSize];●插入操作●删除操作●按值寻找●2、链表●单链表●单链表的定义●●头插法建立单链表●●尾插法建立单链表●●按序号查找getElem(LinkList L,int i)和按值查找locateElem(LinkListL,ElemType e)●插入结点（后插）●p=getElem(L,i-1); //查找插入位置的前驱结点\\ s.next=p.next;\\p.next=s;●将前插操作转化为后插操作,即先将s插入的p的后面然后调换s和p的数据域●s.next=p.next;\\ p.next=s.next;\\ temp=p.data;\\ p.data=s.data;\\s.data=temp;●删除结点●p.getElem(L,i-1);\\ q=p.next;\\ p.next=q.next;\\ free(q);●双链表（结点中有prior指针和next指针）●循环链表●静态链表●借助数组来描述线性表的链式存储结构，结点中的指针域next为下一个元素的数组下标●三、线性表的应用●使用的时候如何选择链表还是顺序表？●表长难以估计，经常需要增加、删除操作——链表;表长可以估计，查询比较多——顺序表●链表的头插法，尾插法，逆置法，归并法，双指针法；顺序表结合排序算法和查找算法的应用●小知识点（选择题）二、第三章栈，队列和数组●考纲内容●一、栈和队列的基本概念●栈：后进先出，LIFO，逻辑结构上是一种操作受限的线性表●队列：先进先出，FIFO，逻辑结构上也是一种操作受限的线性表●二、栈和队列的顺序存储结构●栈的顺序存储●●队列的顺序存储●进队：队不满时，送值到队尾元素，再将队尾指针加一●出队：队不空时，取队头元素值，再将队头指针加一●判断队空：Q.front==Q.rear==0;●循环队列（牺牲一个单元来区分队空和队满，尾指针指向队尾元素的后一个位置，也就是即将要插入的位置）●初始：Q.front==Q.rear●队满：(Q.rear+1)%MaxSize=Q.front●出队，队首指针进1:Q.front=(Q.front+1)%MaxSize●入队，队尾指针进1:Q.rear=(Q.rear+1)%MaxSize●队列长度：(Q.rear+MaxSize-Q.front)%MaxSize●三、栈和队列的链式存储结构●栈的链式存储●●队列的链式存储●实际是上一个同时带有头指针和尾指针的单链表，尾指针指向单链表的最后一个结点，与顺序存储不同,通常带有头结点●四、多维数组的存储●行优先：00，01，02，10，11，12●列优先：00，10，01，11，02，12●五、特殊矩阵的压缩存储●对称矩阵●三角矩阵●三对角矩阵（带状矩阵）●稀疏矩阵●将非零元素及其相应的行和列构成一个三元组存储●十字链表法●六、栈、队列、数组的应用●栈在括号匹配中的应用●栈在递归中的应用●函数在递归调用过程中的特点：最后被调用的函数最先执行结束●队列在层次遍历中的应用●二叉树的层次遍历●1跟结点入队●2若队空，则结束遍历，否则重复3操作●3队列中的第一个结点出队并访问，若有左孩子，则左孩子入队；若有右孩子，则右孩子入队●重点为栈的(出入栈过程、出栈序列的合法性)和队列的操作及其特征●小知识点(选择题)●n个不同元素进栈，出栈元素不同排列的个数为{2n\choose n }/(n+1)●共享栈是指让两个顺序栈共享一个存储空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，可以更有效的利用存储空间，同时对存储效率没有什么影响●双端队列是指允许两端都可以进行入队和出队操作的队列●输出受限的双端队列：允许两端插入，只允许一端删除●输入受限的双端队列：允许两端删除，只允许一端插入三、第四章串●考纲内容●字符串模式匹配●暴力算法●注意指针回退时的操作是i=i-j+2;j=j+1;●kmp算法●手工求next数组时，next[j]=s的最长相等前后缀长度+1，其中s为1到j-1个字符组成的串●在实际kmp算法中，为了使公式更简洁、计算简单，如果串的位序是从1开始的，则next数组需要整体加一；如果串的位序是从0开始的，则next数组不需要加一●根据next数组求解nextval数组：如果p[j]==p[next[j]]，则nextval[j]=nextval[next[j]]，否则nextval[j]=next[j];●小知识点●串和线性表的区别：1线性表的数据元素可以不同，但串的数据元素一般是字符；2串的操作对象通常是子串而不是某一个字符四、第五章树与二叉树●考纲内容●一、树的基本概念●定义●树是一种递归的数据结构，是一种逻辑结构●树的性质●结点数为n，则边的数量为n-1●树中的结点数等于所有结点的度数之和加1（一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度，每一条边表示一个结点，对应一个度，只有根结点上面无边，故结点树=度数之和+1）●度为m的树中第i层至多有m^{i-1}个结点（i\geq1）（m叉树的第i层最多有m^{i-1}个结点）●高度为h的m叉树至多有(m^h-1)/(m-1)个结点（假设每一个结点都有m个孩子，则由等比数列的求和公式可以推导出该式子）●具有n个结点的m叉树的最小高度是\lceil log_m(n(m-1)+1)\rceil（由高度为h的m叉树的最大结点树公式有，n满足式子(m^{h-1}-1)/(m-1) \leq n\leq (m^h-1)/(m-1)）●高度为h的m叉树至少有h个结点；高为h，度为m的树至少有h+m-1个结点（m叉树并不等于度为m的树，m叉树可以为空树，要求所有结点的度小于等于m，而度为m的树一定有一个结点的度数为m）●二、二叉树●二叉树的定义及其主要特征●定义●特点●每个结点至多只有两颗子树●二叉树是有序树，其子树有左右之分，次序不能颠倒，否则将成为另一颗二叉树，即使树中结点只有一颗子树，也要区分他是左子树还是右子树●特殊的二叉树●满二叉树：高度为h，结点数为2^h-1，所有叶子结点都集中在二叉树的最下面一层，除叶子结点外的所有结点度数都为2，从根结点为1开始编号，对于编号为i的结点，其父结点为\lfloor i/2 \rfloor，左孩子(若有)编号为2i，右孩子(若有)编号为2i+1，所以编号为偶数的结点只可能是左孩子，编号为奇数的结点只可能是右孩子●完全二叉树：删除了满二叉树中编号更大的结点，高为h，结点数为n的完全二叉树的每个结点的编号都与高度为h的满二叉树中编号为1到n的结点相同。

小数的计数单位和数位顺序表教学目标：1. 理解小数的计数单位，掌握数位顺序表。

2. 能够运用小数的计数单位和数位顺序表进行小数的读写和计算。

教学内容：第一章：小数的计数单位1.1 小数的产生和意义1.2 小数的计数单位：十分之一、百分之一、千分之一等1.3 练习运用小数的计数单位进行读写小数第二章：数位顺序表2.1 数位顺序表的定义和作用2.2 数位顺序表的构成：个位、十位、百位、千位等2.3 练习运用数位顺序表进行小数的读写和计算第三章：小数的读写3.1 小数的读法：整数部分和小数部分的读法3.2 小数的写法：整数部分和小数部分的写法3.3 练习运用小数的读写法进行小数的读写第四章：小数的计算4.1 小数的加法：同小数位加法和异小数位加法4.2 小数的减法：同小数位减法和异小数位减法4.3 小数的乘法和小数除法：乘法和除法的基本法则4.4 练习运用小数的计算法则进行计算第五章：综合练习5.1 运用小数的计数单位和数位顺序表进行小数的读写和计算5.2 解决实际问题，运用小数的知识进行计量和计算5.3 总结小数的计数单位和数位顺序表的应用教学方法：1. 采用讲解法，讲解小数的计数单位和数位顺序表的概念和运用。

2. 采用示范法，示范小数的读写和计算方法。

3. 采用练习法，让学生通过练习运用小数的计数单位和数位顺序表进行小数的读写和计算。

教学评价：1. 课堂练习：学生在课堂上进行小数的读写和计算练习，检验学生对小数的计数单位和数位顺序表的掌握程度。

2. 课后作业：布置相关的课后作业，让学生进一步巩固小数的计数单位和数位顺序表的知识。

3. 单元测试：进行单元测试，全面检验学生对小数的计数单位和数位顺序表的掌握程度。

第六章：小数的大小比较6.1 小数的大小比较方法：先比较整数部分，再比较小数部分6.2 练习运用小数的大小比较方法进行比较第七章：小数的应用7.1 小数在日常生活中的应用：如购物、烹饪等7.2 练习运用小数解决实际问题第八章：小数的换算8.1 小数与整数的换算：如将小数转换为整数，或将整数转换为小数8.2 小数与分数的换算：如将小数转换为分数，或将分数转换为小数8.3 练习运用小数的换算方法进行换算第九章：误差与近似值9.1 误差的定义和产生原因：如测量工具的精度、人的视觉误差等9.2 近似值的定义和求法：如四舍五入法、进一法、去尾法等9.3 练习运用误差和近似值的概念进行实际问题的解决第十章：总结与拓展10.1 总结小数的计数单位和数位顺序表的知识点，强化记忆10.2 拓展小数的知识：如小数的运算规则、小数在科学计算中的应用等10.3 布置课后作业，让学生进一步巩固小数的计数单位和数位顺序表的知识教学方法：1. 采用案例分析法，通过生活中的实例讲解小数的大小比较和应用。

小数的计数单位和数位顺序表第一章：小数的计数单位1.1 教学目标让学生理解小数的计数单位，包括十分之一、百分之一、千分之一等。

让学生能够用小数表示物品的单价、数量等。

培养学生运用小数进行计算和解决问题的能力。

1.2 教学内容小数的计数单位：十分之一、百分之一、千分之一等。

小数的表示方法：用小数表示物品的单价、数量等。

小数的计算方法：加法、减法、乘法、除法等。

1.3 教学步骤引入：通过实际例子，如购物场景，让学生接触到小数的计数单位。

讲解：详细讲解小数的计数单位，以及如何用小数表示物品的单价、数量等。

练习：让学生通过计算练习，运用小数的加法、减法、乘法、除法等计算方法。

1.4 作业布置让学生用小数表示一些日常生活中的物品价格和数量，如水果、零食等。

让学生完成一些小数计算的练习题，巩固所学知识。

第二章：数位顺序表2.1 教学目标让学生理解数位顺序表的概念，包括个位、十位、百位等。

让学生能够用数位顺序表表示整数和小数。

培养学生运用数位顺序表进行计算和解决问题的能力。

2.2 教学内容数位顺序表的概念：个位、十位、百位等。

小数的数位顺序表：整数部分和小数部分的数位顺序表。

小数的表示方法：用数位顺序表表示整数和小数。

2.3 教学步骤引入：通过实际例子，让学生接触到数位顺序表的概念。

讲解：详细讲解数位顺序表的概念，以及如何用数位顺序表表示整数和小数。

练习：让学生通过计算练习，运用数位顺序表表示整数和小数。

2.4 作业布置让学生用数位顺序表表示一些整数和小数，如身高、体重等。

让学生完成一些数位顺序表相关的练习题，巩固所学知识。

第三章：小数的比较3.1 教学目标让学生理解小数的大小比较方法，包括比较整数部分、比较小数部分等。

让学生能够用小数进行大小比较，并能够正确判断大小关系。

培养学生运用小数进行比较大小的能力和解决问题的能力。

3.2 教学内容小数的大小比较方法：比较整数部分、比较小数部分、比较十分位、比较百分位等。