1n    ,21)
n(n i n
1i ≥+=
∑=《数据结构》作业一
1-1什么是数据? 它与信息是什么关系?
1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面?
1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、 栈、队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ 1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求  (1) 在复数内部用浮点数定义它的实部和虚部。
(2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋
给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。  (3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。
(4) 定义重载的流函数来输出一个复数。
1-5 用归纳法证明：  (1)    (2)  1n    ,6
1)
1)(2n n(n i
n
1
i 2
≥++=
∑=
(3)
0n    1,  x ,1x 1x x 1n n
i i
≥≠--=+=∑ 1-6 什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。
1-7 设n 为正整数, 分析下列各程序段中加下划线的语句的程序步数。  (1)  for  (int  i = 1; i <= n ; i++)      (2)  x = 0;  y = 0;      for  (int  j = 1; j <= n ; j++) {
for  (int  i = 1; i <= n ; i++)
c[i][j] = 0.0;              for  (int  j = 1; j <= i ; j++)
for  (int  k = 1; k <= n ; k++)        for  (int  k = 1; k <= j ; k++)
c[i][j] = c[i][j] + a[i][k] * b[k][j];        x = x + y ;
}                                          (3)  int  i = 1,  j = 1;          (4)  int i =1;    while (i<=n && j<=n) {      do {
i = i + 1;  j = j + i ;            for  (int  j = 1; j <= n ; j++)
}
i = i + j ;
} while ( i < 100 + n );
1-8 试编写一个函数计算n!*2n 的值，结果存放于数组A[arraySize]的第n 个数组元素中，0 ≤ n ≤ arraySize 。若设计算机中允许的整数的最大值为maxInt ，则当n > arraySize 或者对于某一个k (0 ≤ k ≤ n)，使得k!*2k  > maxInt 时，应按出错处理。可有如下三种不同的出错处理方式：  (1) 用cerr<<；及exit (1)语句来终止执行并报告错误；
(2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回；
(3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。
试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。
1-9 (1) 在下面所给函数的适当地方插入计算count的语句：
void d (ArrayElement x[ ], int n ) {
int i = 1;
do {
x[i] += 2; i +=2;
} while (i <= n );
i = 1;
while ( i <= (n/2) ) {
x[i] += x[i+1];i++;
}
}
(2) 将由(1)所得到的程序化简。使得化简后的程序与化简前的程序具有相同的count值。
(3) 程序执行结束时的count值是多少？
(4) 使用执行频度的方法计算这个程序的程序步数，画出程序步数统计表。
1-10 设有3个值大小不同的整数a、b和c，试求
(1)其中值最大的整数；
(2)其中值最小的整数；
(3)其中位于中间值的整数。
2-1 设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n, s和m，求出这n个人的出局序列。请以n = 9, s = 1, m = 5为例，人工模拟Josephus的求解过程以求得问题的解。
2-2 试编写一个求解Josephus问题的函数。用整数序列1, 2, 3, ……, n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。
2-3 设有一个线性表(e0, e1, …, e n-2, e n-1) 存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为(e n-1, e n-2, …, e1, e0)。
2-4 假定数组A[arraySize]中有多个零元素, 试写出一个函数, 将A中所有的非零元素依次移到数组A的前端A[i]（0≤ i ≤ arraySize）。
2-5 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?
2-6 若矩阵A m⨯n中的某一元素A[i][j]是第i行中的最小值，同时又是第j列中的最大值，则
称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组中的位置（若鞍点存在时），并分析该函数的时间复杂度。
2-7 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
2-8 利用顺序表的操作，实现以下的函数。
(1) 从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。
(2) 从顺序表中删除第i个元素并由函数返回被删元素的值。如果i不合理或顺序表为空则显示出错信息并退出运行。
(3) 向顺序表中第i个位置插入一个新的元素x。如果i不合理则显示出错信息并退出运行。
while语句都可以用for改写(4) 从顺序表中删除具有给定值x的所有元素。
(5) 从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t 不合理或顺序表为空则显示出错信息并退出运行。
(6) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s 或t不合理或顺序表为空则显示出错信息并退出运行。
(7) 将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。
(8) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。
2-9 设有一个n⨯n的对称矩阵A，如图(a)所示。为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，如图(b)和图(c)所示。并称之为对称矩阵A的压缩存储方式。试问：
(1) 存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？
(2) 若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素
a ij在只存上三角部分的情形下(图(b))应存于一维数组的什么下标位置？给出计算公式。
(3) 若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素
a ij在只存下三角部分的情形下(图(c))应存于一维数组的什么下标位置？给出计算公式。
2-10 设A和B均为下三角矩阵，每一个都有n行。因此在下三角区域中各有n(n+1)/2个元素。另设有一个二维数组C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素a ij和B的矩阵元素b ij在C中的存放位置下标的公式。
2-11 在实际应用中经常遇到的稀疏矩阵是三对角
矩阵，如右图所示。在该矩阵中除主对角线及在主
对角线上下最临近的两条对角线上的元素外，所有
其它元素均为0。现在要将三对角矩阵A中三条对
角线上的元素按行存放在一维数组B中，且a11存
放于B[0]。试给出计算A在三条对角线上的元素a ij
（1≤ i ≤ n, i-1 ≤ j ≤ i+1）在一维数组B中的存放位
置的计算公式。
2-12 设带状矩阵是n⨯n阶的方阵，其中所有的非零元素都在由主对角线及主对角线上下各b条对角线构成的带状区域内，其它都为零元素。试问：
(1) 该带状矩阵中有多少个非零元素？
(2) 若用一个一维数组B按行顺序存放各行的非零元素，且设a11存放在B[0]中，请给出一个公式，计算任一非零元素a ij在一维数组B中的存放位置。
2-13 稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。稀疏矩阵有多少行，在行指针数组中就有多少个元素：第i个元素的数组下标i代表矩阵的第i行，元素的内容即为稀疏矩阵第i行的第一个非零元素在二元组表中的存放位置。二元组表中每个二元组只记录非零元素的列号和元素值，且各二元组按行号递增的顺序排列。试对右图所示的稀疏矩阵，分别建立它的三元组表和带行指针数组的二元组表。
2-14 字符串的替换操作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-15 编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。
2-16 设串s为“aaab”，串t为“abcabaa”，串r为“abc aabbabcabaacbacba”，试分别计算它们的失效函数f (j)的值。
3-1线性表可用顺序表或链表存储。试问：
(1) 两种存储表示各有哪些主要优缺点?
(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？
(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？
3-2 针对带表头结点的单链表，试编写下列函数。
(1) 定位函数Locate：在单链表中寻第i个结点。若到，则函数返回第i个结点的地址；若不到，则函数返回NULL。
(2) 求最大值函数max：通过一趟遍历在单链表中确定值最大的结点。
(3) 统计函数number：统计单链表中具有给定值x的所有元素。
(4) 建立函数create：根据一维数组a[n]建立一个单链表，使单链表中各元素的次序与a[n]中各元素的次序相同，要求该程序的时间复杂性为O(n)。
(5) 整理函数tidyup：在非递减有序的单链表中删除值相同的多余结点。
3-3 设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。
3-4 设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。
3-5 从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如右图所示。在图中的指针p指向当前正在访问的结点，指针pr指向指针p
所指结点的左侧的结点。此时，指针p 所指结点左侧的所有结点的链接方向都已逆转。  (1) 编写一个算法，从任一给定的位置(pr, p)开始，将指针p 右移k 个结点。如果p 移出链表，则将p 置为0，并让pr 停留在链表最右边的结点上。  (2) 编写一个算法，从任一给定的位置(pr, p)开始，将指针p 左移k 个结点。如果p 移出链表，则将p 置为0，并让pr 停留在链表最左边的结点上。
3-6 试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数、以
及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数。要求每个字符串结点中只存放一个字符。
3-7 如果用循环链表表示一元多项式，试编写一个函数Polynomial :: Calc(x)，计算多项式在x 处的值。
3-8 设a 和b 是两个用带有表头结点的循环链表表示的多项式。试编写一个算法，计算这两个多项式的乘积c = a*b ，要求计算后多项式a 与b 保持原状。如果这两个多项式的项数分别为n 与m, 试说明该算法的执行时间为O(nm 2
)或O(n 2
m)。但若a 和b 是稠密的, 即其很少有系数为零的项, 那么试说明该乘积算法的时间代价为O(nm)。
3-9 计算多项式 P n (x) = a 0 x n  + a 1 x n -1 + a 2 x n -2 + …… + a n -1 x + a n 的值，通常使用的方法是一种嵌套的方法。它可以描述为如下的迭代形式：b 0 = a 0 ,  b i+1 = x * b i  + a i+1,  i = 0, 1, …, n -1。
若设b n  = p n  （x ）. 则问题可以写为如下形式：P n  (x) = x * P n -1 (x) + a n  ，此处， P n -1 (x) = a 0 x n -1
+ a 1 x n -2
+ …… + a n -2 x + a n -1，这是问题的递归形式。试编写一个递归函数，计算这样的多项式的值。
3-10 试设计一个实现下述要求的Locate 运算的函数。设有一个带表头结点的双向链表L ，每个结点有4个数据成员：指向前驱结点的指针prior 、指向后继结点的指针next 、存放数据的成员data 和访问频度freq 。所有结点的freq 初始时都为0。每当在链表上进行一次Locate (L, x)操作时，令元素值为x 的结点的访问频度freq 加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。
3-11 利用双向循环链表的操作改写2-2题，解决约瑟夫(Josephus)问题。
3-12 试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的rLink 域中，并利用lLink 域把所有结点按照其值从小到大的顺序连接起来。
4-1 改写顺序栈的进栈成员函数Push (x )，要求当栈满时执行一个stackFull ( )操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新
数组的前MaxSize 位置。
4-2 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：  (1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?  (2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出"进栈"或"出栈"的序列)。
4-3 试证明：若借助栈可由输入序列1, 2, 3, …, n 得到一个输出序列p 1, p 2, p 3, …, p n (
它是

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