第二章  线性表
2-1 设有一个线性表（e0, e1, …, en-2, en-1）存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为（en-1, en-2, …, e1, e0）。
2-2 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，问A[3][3]（10）存放在什么位置？脚注（10）表示用10进制表示。
2-3 设有一个nn的对称矩阵A，如图（a）所示。为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，如图（b）和图（c）所示。并称之为对称矩阵A的压缩存储方式。试问：
    (1) 存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？
    (2) 若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存上三角部分的情形下（图(b)）应存于一维数组的什么下标位置？给出计算公式。
    (3) 若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存下三角部分的情形下（图(c)）应存于一维数组的什么下标位置？给出计算公式。
2-4 编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。
2-5 利用顺序表的操作，实现以下的函数。
    (1) 从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。
    (3) 向顺序表中第i个位置插入一个新的元素x。如果i不合理则显示出错信息并退出运行。
    (8) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。
2-6 字符串的替换操作replace ( String& s, String& t, String& v) 是指：若t是s的子串，则用串v替换串t在串s中的所有出现；若t不是s的子串，则串s不变。例如，若串s为“aabbabcbaabaaacbab”，串t为“bab”，串v为“abdc”，则执行replace操作后，串s中的结果为“aababdccbaabaaacabdc”。试利用字符串的基本运算实现这个替换操作。
2-7 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?
2-8 设A和B均为下三角矩阵，每一个都有n行。因此在下三角区域中各有n（n+1）/2个元素。另设有一个二维数组C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。
2-9 稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。稀疏矩阵有多少行，在行指针数组中就有多少个元素：第i个元素的数组下标i代表矩阵的第i行，元素的内容即为稀疏矩
阵第i行的第一个非零元素在二元组表中的存放位置。二元组表中每个二元组只记录非零元素的列号和元素值，且各二元组按行号递增的顺序排列。试对右图所示的稀疏矩阵，分别建立它的三元组表和带行指针数组的二元组表。
2-10.  判断下列叙述的对错。如果正确，在题前打“”，否则打“”。
    (1) 线性表的逻辑顺序与物理顺序总是一致的。
    (2) 线性表的顺序存储表示优于链式存储表示。
    (3) 线性表若采用链式存储表示时所有存储单元的地址可连续可不连续。
    (4) 二维数组是其数组元素为线性表的线性表。
    (5) 每种数据结构都应具备三种基本运算：插入、删除和搜索。
2-11.  线性结构可用顺序表或链表存储。试问：
    (1) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？
    (2) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？   
2-12.  已知整数数组A[ ]中有n个元素，试设计一个算法，求数组中所有元素值的和。
2-13.  已知整数数组A[ ]中有n个元素，试设计一个算法，求数组中所有元素值的平均值。
2-14. 假定数组A[arraySize]中有多个零元素, 试写出一个函数, 将A 中所有的非零元素依次移到数组A的前端A[i] (0  i < arraySize)。
2-15.  已知A[n]为整数数组，试写出实现下列运算的递归算法：   
    (1) 求数组A中的最大整数。
    (2) 求n个整数的和。
2-16.  设有上三角矩阵A[n][n]，将其上三角元素逐行存储到一维数组B[m]中，使得B[k] = A[i][j]，且k = f1 (i) + f2 (j) + C。试推导出函数f1 (i)、f2 (j)和常数C，要求f1 (i)和f2 (j)中不包含常数项。
2-17.  设有三对角矩阵A[n][n]，将其三条对角线中的元素逐行存储到一维数组B[3n-2 ]中，使得B[k] = A[i][j]。试求：
    (1) 用i, j表示k的地址转换公式；
    (2) 用k表示i, j的地址转换公式；
2-18.  设有两个整数类型的顺序表A（有 m个元素）和B（有n个元素），其元素均以从小到大的升序排列。试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也以从小到大的升序排列。
2-19  设线性表存于a(1:arrsize)的前elenum 个分量中，且递增有序。试写一算法，将x插入到线性表的适当位置上，以保持线性表有序性。
字符串是什么数据结构
2-20  线性表有两种存储结构：一是顺序表，二是链表。试问：（1）两种存储表示各有哪些主要优缺点？（2）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动地变化。在此情况下，应选用哪种存储结？为什么？（3）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，
那么，应采用哪种存储结构？为什么？
2-21  描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
2-22  试写在带头结点的动态单链表结构上实现线性表操作 LOCATE(L,X)和 LENGTH（L).
2-23  试写在无头结点的动态单链表上实现线性表操作 INSERT（L，I，B）和 DELETE
      （L，I）的算法，并和在带头结点的动态单链表上实现相同操作的算法进行比较。
2-24  已知线性表中的元素以值递增有序排列，并以单链表作存储结构，试写一高效
      的算法，删除表中所有值大于 mink 且小于maxk 的元素（如果表中存在这样的
      元素），并分析你的算法的时间复杂度（注意：mink 和 maxk 是给定的两个参变
      量，它们的值为任意的整数）。
2-25  试分别以单链表作存储结构实现线性表的就地逆置算法，即在原表的存储空间内将线性表（a1,a2,···，an)逆置为（an,an-1,···，a1)。
2-26  假设有一个单向循环链表，其结点含三个区域：pre ,data 和 next,其中data为数据域，next为指针域，其值为后继结点的地址，pre也为指针域，它的值为空（NIL），      试编写算法将此链表改为双向循环链表。
2-27  假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。
2-28 设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n, s和m，求出这n个人的出局序列。请以n = 9, s = 1, m = 5为例，人工模拟Josephus的求解过程以求得问题的解。
2-29 **试编写一个求解Josephus问题的函数。用整数序列1, 2, 3, ......, n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。
2-30 假定数组A[arraySize]中有多个零元素, 试写出一个函数, 将A 中所有的非零元素依次移到数组A的前端A[i]（0￡ i ￡ arraySize）。
2-31 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?
2-32 若矩阵Am′n中的某一元素A[i][j]是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组中的位置（若鞍点存在时），并分析该函数的时间复杂度。
2-33 利用顺序表的操作，实现以下的函数。
        (1) 从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。
        (2) 从顺序表中删除第i个元素并由函数返回被删元素的值。如果i不合理或顺序表为空则显示出错信息并退出运行。
      (3) 向顺序表中第i个位置插入一个新的元素x。如果i不合理则显示出错信息并退出运行。
      (4) 从顺序表中删除具有给定值x的所有元素。
      (5) 从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。
      (6) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。