数据结构习题正文
第一章数据结构概论
1-1 什么是数据? 它与信息是什么关系?
1-2 什么是数据、数据对象、数据元素、数据结构、存储结构和算法? 有关数据结构的讨论涉及哪三个方面?
1-3 数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？
1-4 什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。
1-5 (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-6 判断下列叙述的对错。如果正确，在题前打“√”，否则打“?”。
(1) 数据元素是数据的最小单位。
(2) 数据结构是数据对象与对象中数据元素之间关系的集合。
(3) 数据结构是具有结构的数据对象。
(4) 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。
(5) 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。
1-7 判断下列叙述的对错。如果正确，在题前打“√”，否则打“?”。
(1) 所谓数据的逻辑结构是指数据元素之间的逻辑关系。
(2) 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数
据项的个数都相等。
(3) 数据的逻辑结构与数据元素本身的内容和形式无关。
(4) 数据结构是指相互之间存在一种或多种关系的数据元素的全体。
(5) 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。
1-8 设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-9 填空题
算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应当具有输入、输出、( ① )、有穷性和可执行性等特性。
算法效率的度量分为( ② )和( ③ )。( ② )主要通过在算法的某些部位插装时间函数来测定算法完成某一规定功能所需的时间。而( ③ )不实际运行算法，它是分析算法中语句的执行次数来度量算法的时间复杂性。
程序所需的存储空间包含两个部分( ④ )和( ⑤ )。( ④ )空间的大小与输入输出数据的个数多少，数值大小无关；( ⑤ )空间主要包括其大小与问题规模有关的成分变量所占空间，引用变量所占空间，以及递归栈所用的空间，还有在算法运行过程中动态分配和回收的空间。
1-10. 试用大O表示法给出下面程序的时间复杂性。
void out ( float x[ ][ ], int m, int n ) {
float sum[ ];
for ( int i = 0; i < m; i++ ) {
sum[i] = 0.0;
for ( int j = 0; j < n; j++ )
sum[i] = x[i][j];
}
for ( int i = 0; i < m; i++ )
printf( "Line: %f :", sum[i]);
}
1-11 分析以下程序段的时间复杂度
(1). for (i=1;i { y=y+1; for(j=0;j<=(2*n);j++) x++; } (2). i=1; while(i<=n) i=i*2; (3). a=0;b=1; for(i=2;i<=n;i++) { s=a+b; b=a; a=s; } (4). Int a[]={2,5,1,7,9,3,6,8}; order(int j,int m) { int itemp; if(j { for(i=j;j<=m;i++) if(a[i] temp=a[i]; a[i]=a[j]; a[j]=temp; } j++; order(j,m); } } main() { int j; order(0,7); for(i=0;i<=7;i++) printf(“%d”,a[I]); } (5). i=1; while(i<=n) i=i*3; 1-12．试举例说明数据结构与算法的关系。 1-13．试编写一算法，自大到小依次输出顺序输入的三个数x,y,z,的值。 1-14．已知有实现同一功能的两种算法，其时间复杂度分别为O(2n)和O(n10), 假设现实计算机可连续运算的时间为107秒，又每秒可执行基本操作105次。试问在此条件，这两种算法可解决问题的规模各为多少？哪个算法更适宜？请说明理由。 1-15．求两个n阶矩阵的乘法C=AXB，其算法如下： # define MAX 100 void maxtrixmult(int n,float a[MAX][MAX],b[MAX][MAX], float c[MAX][MAX]) { int I,j,k; float x; for(I=1;I<=n;I++) { for(j=1;j<=n;j++) { x=0; for(k=1;k<=n;k++) x+=a[I][k]*b[k][j]; c[I][j]=x; } } } 分析该算法的时间复杂度。 1-16 数据结构在计算机中的表示称作数据的。 A 逻辑结构 B 存储结构 C 线性结构 D 顺序存储结构 1-17 算法是求解问题的一个运算序列.下列表述的各项中,______不属于一各算法应有的特性. A.有穷性 B.确定性 C.可行性 D.复杂性 1-18. 算法的主运算如下，其中i的初值为1，s的初值为0，“←”为赋值号。 while i { for j 1 to n do s s+a[i,j]; i i*2; } 则该算法的时间复杂度为＿＿＿。 A. O（2n） B.O（n+log2n ） 1-19 设三个函数f,g,h分别为 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^1.5+5000nlgn 请判断下列关系是否成立： (1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n^1.5)(4) h(n)=O(nlgn) 1-20 设有两个算法在同一机器上运行，其执行时间分别为100n^2和2^n,要使前者快于后者，n至少要多大? 1-21 设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。 (1) i=1; k=0 while(i { k=k+10*i;i++; } ◆ T(n)=n-1 ∴ T(n)=O(n) ◇这个函数是按线性阶递增的 (2) i=0; k=0; do{ k=k+10*i; i++; } while(i ∴ T(n)=O(n) ◇这也是线性阶递增的 (3) i=1; j=0; while(i+j<=n) { if (i else i++; } ◆ T(n)=n/2 ∴ T(n)=O(n) ◇虽然时间函数是n/2,但其数量级 仍是按线性阶递增的。 (4)x=n; // n>1 while (x>=(y+1)*(y+1)) y++; ◆ T(n)=n1/2 ∴ T(n)=O(n1/2) ◇最坏的情况是y=0，那么循环的 次数是n1/2次，这是一个按平方根 阶递增的函数。 (5) x=91; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++; ◆ T(n)=O(1) ◇这个程序看起来有点吓人，总共 循环运行了1000次，但是我们看 到n没有? 没。这段程序的运行是 和n无关的，就算它再循环一万 年，我们也不管他，只是一个常数 阶的函数。 1-22 算法的时间复杂度仅与问题的规模相关吗? 1-23 按增长率由小至大的顺序排列下列各函数： 2^100, (2/3)^n，(3/2)^n， n^n , , n! ，2^n ，lgn ,n^lgn, n^(3/2) ◇分析如下：2^100 是常数阶； (2/3)^n和 (3/2)^n是指数阶,其中前者是随n的增大而减小的； n^n是指数方阶；√n 是方根阶, n! 就是n(n-1)(n-2)... 就相当于n次方阶；2^n 是指数阶，lgn是对数阶 ,n^lgn是对数方阶, n^(3/2)是3/2次方阶。根据以上分析按增长率由小至大的顺序可排列如下： ◆ (2/3)^n < 2^100 < lgn < √n < n^(3/2) < n^lgn < (3/2)^n < 2^n < n! < n^n 1-24 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大"O"记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=2.0nlgn-2n=2.0lgn+O(n), 这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪 第二章线性表 2-1 设有一个线性表（e0, e1, …, e n-2, e n-1）存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为（e n-1, e n-2, …, e1, e0）。 2-2 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]（10）存放在什么位置？脚注（10）表示用10进（10） 制表示。 2-3 设有一个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-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的矩阵元素a ij和B的矩阵元素b ij在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不合理或顺序表为空则显示出错信息并退出运行。 (7) 将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。 (8) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。 2-34 设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。 2-35 计算多项式 P n (x) = a0 x n + a1 x n-1 + a2 x n-2 + …… + a n-1 x + a n的值，通常使用的方法是一种嵌套的方法。它可以描述为如下的迭代形式：b0 = a0 , 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) = a0 x n-1 + a1 x n-2 + …… + a n-2 x + a n-1，这是问题的递归形式。试编写一个递归函数，计算这样的多项式的值。 2-36 针对带表头结点的单链表，试编写下列函数。 (1) 求最大值函数max：通过一趟遍历在单链表中确定值最大的结点。 (2) 建立函数create：根据一维数组a[n]建立一个单链表，使单链表中各元素的次序与 a[n]中各元素的次序相同，要求该程序的时间复杂性为O(n)。 2-37 试设计一个实现下述要求的Locate运算的函数。设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Locate (x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。 2-38 线性表可用顺序表或链表存储。试问： (1) 两种存储表示各有哪些主要优缺点? (2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总 数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？ (3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的 元素，这时，应采用哪种存储表示？为什么？ 2-39 试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数、以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数。要求每个字符串结点中只存放一个字符。 2-40 设a和b是两个用带有表头结点的循环链表表示的多项式。试编写一个算法，计算这两个多项式的乘积c = a*b，要求计算后多项式a与b保持原状。如果这两个多项式的项数分别为n与m, 试说明该算法的执行时间为O(nm2)或O(n2m)。但若a和b是稠密的, 即其很少有系数为零的项, 那么试说明该乘积算法的时间代价为O(nm)。 2-41. 设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？ (1) s->link = p->link; p->link = s; (2) q->link = s; s->link = p; (3) p->link = s->link; s->link = p; (4) p->link = s; s->link = q; 2-42. 设单链表中结点的结构为（data, link）。已知指针p所指结点不是尾结点，若在*p 之后插入结点*s，则应执行下列哪一个操作？ (1) s->link = p; p->link = s; (2) s->link = p->link; p->link = s; (3) s->link = p->link; p = s; (4) p->link = s; s->link = p; 2-43. 设单链表中结点的结构为（data, link）。若想摘除结点*p的直接后继，则应执行下列哪一个操作？ (1) p->link = p->link->link; (2) p = p->link; p->link = p->link->link; (3) p->link = p->link; (4) p = p->link->link; 2-44. 已知head为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法： (1) 求链表中的最大整数。 (2) 求链表的结点个数。 2-45. 定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。 2-46. 统计函数number：统计单链表中具有给定值x的所有元素。 2-47. 整理函数cleardupnode：在非递减有序的单链表中删除值相同的多余结点。 2-48. 设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作？ (1)s = rear; rear = rear->link; free(s); (2)rear = rear->link; free(rear); (3)rear = rear->link->link; free(rear); (4) s = rear->link->link; rear->link->link = s->link; free(s); 2-49. 有一个循环链表，它既没有头指针又没有头结点。只有一个指针p指向表中的某一结点。试编写一个函数，删除指针p所指结点的直接前驱结点。 2-50. 判断一个带表头结点的双向循环链表L是否对称相等的算法如下所示，请在算法中的处填入正确的语句。 int symmetry ( DlinkList L ) { int sym = 1; DlistNode * p = L->next, q = L->prior; while ( ( p != q || p->prior == q ) &&① ) if ( p->data == q->data ) { ②; ③; } else sym = 0; return sym; } 2-51. 设双向循环链表中结点的结构为（data, prior, next），且不带表头结点。若想在指针p所指结点之后插入指针s所指结点，则应执行下列哪一个操作？ (1)p->next = s; s->prior = p; p->next->prior = s; s->next = p->next; (2)p->next = s; p->next->prior = s; s->prior = p; s->next = p->next; (3)s->prior = p; s->next = p->next; p->next = s; p->next->prior = s; (4)s->prior = p; s->next = p->next; p->next->prior = s; p->next = s; 2-52. 设有一个栈，元素进栈的次序为：A，B，C，D，E。试问能否得到出栈序列： (1) C,E,A,B,D (2) C,B,A,D,E (3) D,C,A,B,E (4) A,C,B,E,D (5) A,B,C,D,E (6) E,A,B,C,D 若能，请写出操作序列。 2-53** 假设在算法描述语言中引入指针的二元运算“异或”（用“⊙”表示），若a和b 为指针，则a⊙b的运算结果仍为原指针类型，且：a⊙(a⊙b)=(a⊙a) ⊙b, (a⊙b) ⊙b=a ⊙(b⊙b),则可利用一个指针来实现双向链表。每个结点有两个域：data和link 域，link域存放该结点前驱与后续结点指针（不存在时为NULL）的异货。若设指针h 指向链表中第一个结点，e指向链表中最后一个结点，则可实现从前向后或从后向前遍历次双向链表（这种链表称为对称表）。（1）编写一个函数从前向后输出该链表中个元素的值。（2）编写一个函数在第I个结点之前插入一个其data域为 x 的结点的函数。（3）编写一个函数删除第I个结点的函数。 2-54 线性表可用顺序表或链表存储。试问： (1) 两种存储表示各有哪些主要优缺点? (2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总 数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？ (3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中 的元素，这时，应采用哪种存储表示？为什么？ 第三章栈和队列 3-1 试写一个判别表达式中开，闭括号是否配对出现的算法。 3-2 按照四则运算加，减，乘，除和幂运算优先关系，仿照教科书，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A+B C*E-D/F*G 3-3 假设有2个栈共享向量空间v（1：m)，它们的栈底分别设在向量的两端，且进栈的每个元素只占一个分量。试写出这两个栈共用的栈操作方法pushi（I,X)，popi(I)和 topi(I)，其中I为1或0，用以指示出栈号。并讨论过程或函数设计这些操作算法各有什么优缺点。 3-4 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（注意不设头指针），试编写相应的置空队列，如队列和出队列的算法。 3-5 假设以数组sequ(0:m-1)存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。试给出循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。 3-6 给定元素的向量，建立一个有序单链表表示的链栈的时间复杂度是多少？ 3-7 有一个单链表表示的链式队列（不同结点的数据域值可能相同），其队首指针为head，编写一个函数计算数据域为x 的结点个数。 3-8 已知有两个栈A和B，其栈顶指针分别为topa和topb，编写一个函数从栈A中删除自I个元素起的共 len个元素，然后将它们插入到栈B的第j个元素之前。 3-9 输入一个名单，有n个名字，每个名字不超过10个字符，按字典顺序将名单的序列号排出单链表表示的队列序列（即每个名字对应的链表值是其后继名字的序号，最后一个链表值为0）。 3-10 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问： (1) 设有编号为1, 2, 3, 4, 5, 6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序 列有多少种? (2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和 135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出"进栈" 或"出栈"的序列)。 3-11 假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(EnQueue)和删除(DlQueue)算法。 3-12 试建立一个继承结构，以栈、队列和优先级队列为基本函数结构类，建立它们的抽象基类——Bag结构。写出各个结构类型的声明。统一命名各种类型的插入操作为Add，删除操作为Remove，存取操作为Get和Put，初始化操作为MakeEmpty，判空操作为Empty，判满操作为Full，计数操作为Length。 3-13 若将一个双端队列顺序表示在一维数组V[m]中，两个端点设为end1和end2，并组织成一个循环队列。试写出双端队列所用 指针end1和end2的初始化条件及队空与 队满条件，并编写基于此结构的相应的插 入(EnQueue)新元素和删除(DlQueue)算 法。 3-14 将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。 当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。当向第0号栈插入一个新元素时，使top[0]增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top[1]减1得到 新的栈顶位置。当top[0]+1 == top[1]时或top[0] = top[1]-1时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈结构的类定义，并实现判栈空、判栈满、插入、删除算法。 3-15 假设以数组Q[m]存放循环队列中的元素, 同时以rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(EnQueue)和删除(DlQueue)元素的操作。 3-16 若使用循环链表来表示队列，p是链表中的一个指针(视为队尾指针)。试基于此结构给出队列的插入(EnQueue)和删除(DlQueue)算法，并给出p为何值时队列空。 3-17. 设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？ 3-18. 设顺序栈S的元素个数最大为MaxSize。试改写顺序栈的进栈函数Push (S, x)，要求当栈满时执行一个stackFull(S) 操作进行栈满处理。其功能是：动态创建一个比原来的栈元素存放数组大二倍的新数组，代替原来的栈元素存放数组，原来栈元素存放数组中的元素占据新数组的前MaxSize位置。 3-19. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行下列哪一个操作？ (1) top->link = s; (2) s->link = top->link; top->link = s; (3) s->link = top; top = s; (4) s->link = top; top = top->link; 3-20. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列哪一个操作？ (1)x = top->data; top = top->link; (2) top = top->link; x = top->data; (3) x = top; top = top->link; (4) x = top->data; 3-21. 若使用循环链表来表示队列，p是链表中的一个指针(视为队尾指针)。试基于此结构给出队列的插入(EnQueue)和删除(DlQueue)的函数，并给出p为何值时队列空。 3-22. 写出下列中缀表达式的后缀形式： (1) A * B * C (2) - A + b - C + D (3) A* - B + C (4) (A + B) * D + E / (F + A * D) + C (5) A && B|| ! (E > F) {注：按C++的优先级) (6) !(A && !( (B < C)||(C > D) ) )||(C < E) 3-23 根据课文中给出的优先级，回答以下问题： (1) 在函数postfix中，如果表达式e含有n个运算符和分界符，问栈中最多可存入多 少个元素？ (2) 如果表达式e含有n个运算符，且括号嵌套的最大深度为6层，问栈中最多可存 入多少个元素？ 3-24 设表达式的中缀表示为a * x - b / x↑2，试利用栈将它改为后缀表示ax * bx2↑/ -。 写出转换过程中栈的变化。 3-25. 试利用运算符优先数法，画出对如下中缀算术表达式求值时运算符栈和运算对象栈的变化。 A + b * (c – d) – e↑f / g 3-26 若已知一个栈的的入栈序列是1，2，3，。。。，n，其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为？ 3-27 如果用一个循环数组qu[0,m0-1]表示队列时，该队列只有一个头指针front,不设队尾指针rear，而改置计数器count用以记录队列中结点的个数。编写实现队列的5个基本运算；队列中能容纳的最多元素个数还是m0-1吗？ 3-28 编写一个程序求解迷宫问题。迷宫是一个如图所示的m行n列的0-1矩阵，其中0表示无障碍，1表示有障碍。设入口为(1,1)，出口为（m,n），每次移动只能从一个无障碍的单元移动到其他周围8个方向上任一个无障碍的单元，编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。 3-29 改写顺序栈的进栈成员函数Push (x)，要求当栈满时执行一个stackFull( )操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize位置。 3-40 试证明：若借助栈可由输入序列1, 2, 3, ..., n得到一个输出序列p1, p2, p3, ..., pn (它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在i < j < k，使得pj < pk < pi。(提示：用反证法) 3-41 若将一个双端队列顺序表示在一维数组V[m]中，两个端点设为end1和end2，并组织成一个循环队列。试写出双端队列所用指针end1和end2的初始化条件及队空与队满条件，并编写基于此结构的相应的插入(EnQueue)新元素和删除(DlQueue)算法。 3-42 设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结构的队列的插入(EnQueue)和删除(DlQueue)算法，并给出队列空和队列满的条件。 第四章串 4-1 简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 4-2 假设有如下的串说明： char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p; (1)在执行如下的每个语句后p的值是什么? p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6'); (2)在执行下列语句后，s3的值是什么? strcpy(s3,s1); strcat(s3,","); strcat(s3,s2); (3)调用函数strcmp(s1,s2)的返回值是什么? (4)调用函数strcmp(&s1[5],"ton")的返回值是什么? (5)调用函数stlen(strcat(s1,s2))的返回值是什么? 4-3 设T[0..n-1]="adaabaabcaabaa",P[0..m-1]="aab".当用模式串匹配目标串T时，请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。 4-4 利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。 4-5 利用C的库函数strlen 和strcpy(或strncpy)写一算法void StrDelete(char *S,int i, int m)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若 i+m≥strlen(S),则将S中从位置i开始直至末尾的字符均删去。 4-6 以HString为存储表示，写一个求子串的算法。 4-7 一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为： a b c d e f g h i j k l m n o p q r s t u v w x y z n g z q t c o b m u h e l k p d a w x f y i v r s j 则字符串"encrypt"被加密为"tkzwsdf".试写一算法将输入的文本串进行加密后输出；另写一算法，将输入的已加密的文本串进行解密后输出。 4-8 写一算法void StrReplace(char *T, char *P, char *S),将T中首次出现的子串P替换为串S。注意：S和P的长度不一定相等。可以使用已有的串操作。 4-9 将NaveStrMatch改写为输出目标串中所有也模式串匹配的有效位移。 *4-10 利用4.9的结果写一算法void StrReplaceAll(char *T, char *P, char *S),将T中出现的所有与P相等的不重叠子串替换为S，这里S和P的长度不一定相等。 4-11 若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。 4-12 试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数、以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数。要求每个字符串结点中只存放一个字符。 第五章 数组与广仪表 5-1 【背包问题】设有一个背包可以放入的物品的重量为s ，现有n 件物品，重量分别为 w[1], w[2], …, w[n]。问能否从这n 件物品中选择若干件放入此背包中，使得放入的重量之和正好为s 。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)；否则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。（提示：此背包问题的递归定义如下：） ?????????--≥>-<><== ] w[n ) 1n w[n],KNAP(s w[n]1n 0s 1)n KNAP(s, 1n 0s False 0s False 0s T rue n)KNAP(s,时所选物品中包括时所选物品中不包括且或物品件数不能为负数且总重量不能为负数此时背包问题一定有解 5-2 画出下列广义表的图形表示和它们的存储表示： (1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1)) 5-3 已知A[n]为整数数组，试写出实现下列运算的递归算法： (1) 求数组A 中的最大整数。 (2) 求n 个整数的平均值。 (3) 求所有整数的平均值。 5-4 已知f 为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归 算法： (1) 求数组A 中的最大整数。 (2) 求n 个整数的平均值。 (3) 求所有整数的平均值。 5-5 【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在 第1行，第2行，…。第8行上布放棋子。在每一行中有8个可选择位置，但在任一时刻，棋盘的合法布局都必须满足3个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局。(提示：用回溯法。在第n 行第j 列安放一个棋子时，需要记录在行方向、列方向、正斜线方向、反斜线方向的安放状态，若当前布局合法，可向下一行递归求解，否则可移走这个棋子，恢复安放该棋子前的状态，试探本行的第j +1列。) 5-6 利用广义表的head 和tail 操作写出函数表达式，把以下各题中的单元素banana 从广 义表中分离出来： (1) L1(apple, pear, banana, orange) (2) L2((apple, pear), (banana, orange)) (3) L3(((apple), (pear), (banana), (orange))) (4) L4((((apple))), ((pear)), (banana), orange) (5) L5((((apple), pear), banana), orange) (6) L6(apple, (pear, (banana), orange)) 5-7 广义表具有可共享性，因此在遍历一个广义表时必需为每一个结点增加一个标志域 mark ，以记录该结点是否访问过。一旦某一个共享的子表结点被作了访问标志，以后就不再访问它。 (1) 试定义该广义表的类结构； (2) 采用递归的算法对一个非递归的广义表进行遍历。 (3) 试使用一个栈，实现一个非递归算法，对一个非递归广义表进行遍历。 5-8. 已知Ackerman 函数定义如下： ?? ???≠≠--=≠-=+=时当时 当时当0n 0,m ))1n akm(m, 1,akm(m 0n 0,m )1 ,1akm(m 0m 1n n)akm(m, (1) 根据定义，写出它的递归求解算法； (2) 利用栈，写出它的非递归求解算法。 5-9. 已知A[n]为整数数组，试写一个递归算法，求数组A 中所有整数的和。 5-10 已知A[n]为整数数组，试写出实现下列运算的递归算法： (1) 求数组A 中的最大整数。 (2) 求n 个整数的和。 (3) 求n 个整数的平均值。 5-11 已知Ackerman 函数定义如下： (1) 根据定义，写出它的递归求解算法； (2) 利用栈，写出它的非递归求解算法。 5-12 画出下列广义表的图形表示和它们的存储表示： (1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1)) 5-13 广义表具有可共享性，因此在遍历一个广义表时必需为每一个结点增加一个标志域 mark ，以记录该结点是否访问过。一旦某一个共享的子表结点被作了访问标志，以后就不再访问它。 (1) 试定义该广义表的类结构； (2) 采用递归的算法对一个非递归的广义表进行遍历。 (4) 试使用一个栈，实现一个非递归算法，对一个非递归广义表进行遍历。 5-14 设带状矩阵是n ′n 阶的方阵，其中所有的非零元素都在由主对角线及主对角线上下 各b 条对角线构成的带状区域内，其它都为零元素。试问： (1) 该带状矩阵中有多少个非零元素？ (2) 若用一个一维数组B 按行顺序存放各行的非零元素，且设a11存放在B[0]中，请 给出一个公式，计算任一非零元素aij 在一维数组B 中的存放位置。 5-15 稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。稀疏矩阵有多少行，在 行指针数组中就有多少个元素：第i 个元素的数组下标i 代表矩阵的第i 行，元素的内容即为稀疏矩阵第i 行的第一个非零元素在二元组表中的存放位置。二元组表中每个二元组只记录非零元素的列号和元素值，且各二元组按行号递增的顺序排列。试对右图所示的稀疏矩阵，分别建立它的三元组表和带行指针数组的二元组表。 第六章 树与二叉树 6-1 在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？ 多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 6-2 一棵高度为h 的满k 叉树有如下性质: 第h 层上的结点都是叶结点, 其余各层上每个结 点都有k 棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问: (1) 各层的结点个数是多少? (2) 编号为i 的结点的父结点(若存在)的编号是多少? (3) 编号为i 的结点的第m 个孩子结点(若存在)的编号是多少? (4) 编号为i 的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为 n, 则高度h 是n 的什么函数关系? 6-3 试用判定树的方法给出在中序线索化二叉树上： (1) 如何搜索指定结点的在中序下的后继。 (2) 如何搜索指定结点的在前序下的后继。 (3) 如何搜索指定结点的在后序下的后继。 6-4 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法： (1) 统计二叉树中叶结点的个数。 (2) 统计二叉树中的层数 6-5 如果一棵树有n 1个度为1的结点, 有n 2个度为2的结点, … , n m 个度为m 的结点, 试问 有多少个度为0的结点? 试推导之。 6-6 试分别找出满足以下条件的所有二叉树： (1) 二叉树的前序序列与中序序列相同； (2) 二叉树的中序序列与后序序列相同； (3) 二叉树的前序序列与后序序列相同。 6-7 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法： (1) 以二叉树为参数，复制该二叉树. (2) 以二叉树为参数，交换每个结点的左子树和右子 树。 6-8 试用判定树的方法给出在中序线索化二叉树上： (1) 如何搜索指定结点的在前序下的后继。 (2) 如何搜索指定结点的在后序下的后继。 6-9. 列出右图所示二叉树的叶结点、分支结点和每个结点的层次。 6-10. 使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出右图所示二叉树的存储表示。 6-11. 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 6-9,6-10题图 6-12. 一棵具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度如何用n来表示（注意n可能为0）？ 6-13. 假定在一棵二叉树中，度为2 的结点有15个，度为1的结点有20个，试问度为0的结点有多少个？ 6-14. 判断下列叙述的对错。如果正确，在题前打“√”，否则打“?”。 (1) 二叉树是树的特殊情形。 (2) 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一 定是该子树的前序遍历结果序列的最后一个结点。 (3) 若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一 定是该子树的中序遍历结果序列的最后一个结点。 (4) 若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则 它一定是该子树的前序遍历结果序列的最后一个结点。 (5) 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则 它一定是该子树的中序遍历结果序列的最后一个结点。 6-15 判断以下序列是否是最小堆? 如果不是, 将它调整为最小堆。 (1) { 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 } (2) { 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } (3) { 103, 97, 56, 38, 66, 23, 42, 12, 30, 52, 06, 20 } (4) { 05, 56, 20, 23, 40, 38, 29, 61, 35, 76, 28, 100 } 6-16 在森林的二叉树表示中，用llink存储指向结点第一个孩子的指针，用rlink存储指向结点下一个兄弟的指针，用data存储结点的值。如果我们采用静态二叉链表作为森林的存储表示，同时按森林的先根次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志ltag代替llink，用rtag代替rlink。并设定若ltag = 0，则该结点没有孩子，若ltag ≠0，则该结点有孩子；若rtag = 0，则该结点没有下一个兄弟，若rtag ≠0，则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法，将用这种表示存储的森林转换成用llink - rlink表示的森林。 6-17 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。 6-18 已知一棵树的先根次序遍历的结果与其对应二叉树表示(长子-兄弟表示)的前序遍历结果相同, 树的后根次序遍历结果与其对应二叉树表示的中序遍历结果相同。试问利用树的先根次序遍历结果和后根次序遍历结果能否唯一确定一棵树? 举例说明。 6-19 假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设计不等长Huffman编码, 并给出该电文的总码数。 6-20 已知一棵完全二叉树存放于一个一维数组T[n]中，T[n]中存放的是各结点的值。试设计一个算法，从T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。 6-21 试编写一个算法，把一个新结点l作为结点s的左子树插入到一棵线索化二叉树中，s原来的左子树变成l的左子树。 6-22 二叉树的双序遍历(Double-order traversal)是指：对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树。试写出执行这种双序遍历的算法。 6-23 给定权值集合{ 15, 03, 14, 02, 06, 09, 16, 17 }, 构造相应的霍夫曼树, 并计算它的带权外部路径长度。 6-24 给定一组权值: 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 试构造一棵具有最小带权外部路径长度的扩充4叉树, 要求该4叉树中所有内部结点的度都是4, 所有外部结点的度都是0。这棵扩充4叉树的带权外部路径长度是多少? (提示：如果权值个数不足以构造扩充4叉树，可补充若干值为零的权值，再仿照霍夫曼树的思路构造扩充4叉树) 6-25. 若用二叉链表作为二叉树的存储表示，试编写一个递归算法求二叉树中指定结点所在层次。(设二叉树的高度为h，空树时h = -1，只有一个结点的二叉树的高度为h = 0) 6-26. 若用二叉链表作为二叉树的存储表示，试编写一个递归算法，将它按完全二叉树的顺序存储方式存于一个一维数组T[n]中，T[n]中存放各结点的值。 6-27. 下面是一个二叉树的前序遍历的递归算法。 void PreOrder ( BinTreeNode *t ) { if ( t != NULL ) {//递归结束条件 cout << t->data;//访问(输出)根结点 PreOrder ( t->leftChild );//前序遍历左子树 PreOrder ( t->rightChild );//前序遍历右子树 } } (1) 改写PreOrder算法，消去第二个递归调用PreOrder (t->rightChild ); (2) 利用栈改写PreOrder算法，消去两个递归调用。 6-28. 设二叉树采用二叉链表表示，指针root指向根结点，指针p指向二叉树中某一指定结点。试编写一个算法，找出从根结点到结点*p之间的路径。 6-29. 写出向堆中加入数据4, 2, 5, 8, 3, 6, 10, 14时，每加入一个数据后堆的变化。 6-30. 从供选择的答案中选择与下面有关二叉树和森林的叙述中各括号相匹配的词句，将其编号填入相应的括号内。 (1) 设二叉树有n个结点且根结点处于第0层，则其高度为（ A ）。 (2) 设高度为h（空二叉树的高度为-1，只有一个结点的二叉树的高度为0）的二叉树 只有度为2和度为0的结点，则该二叉树中所含结点至少有（ B ）个。 (3) 设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4，当 把森林F转换成一棵二叉树后，其根结点的右子树中有（ C ）个结点。 数据结构例题（及答案） 项目一习题(答案) 一选择题 1. 算法的计算量的大小称为计算的(B )。 A( 效率 B. 复杂性 C. 现实性 D. 难度 2.算法的时间复杂度取决于(C ) A(问题的规模 B. 待处理数据的初态 C. A和B 3(从逻辑上可以把数据结构分为(C )两大类。 A(动态结构、静态结构 B(顺序结构、链式结构 C(线性结构、非线性结构 D(初等结构、构造型结构 4(连续存储设计时，存储单元的地址(A )。 A(一定连续 B(一定不连续 C(不一定连续 D(部分连续，部分不连续 5. 以下属于逻辑结构的是(C )。 A(顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题 1. 数据元素是数据的最小单位。(×) 2. 记录是数据处理的最小单位。(×) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(×) 4(程序一定是算法。(×) 5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×) 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×) 7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(?) 8. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×) 三、填空 1(数据的物理结构包括数据元素的表示和数据元素间关系的表示。 2. 对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形 结构，图状结构或网状结构四种。 3(数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而 逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 4(一个数据结构在计算机中表示(又称映像) 称为存储结构。 5(抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表 示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响 其外部使用。 6(数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。 7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互 关系，并对与这种结构定义相应的操作(运算)，设计出相应的算法。 ( 一个算法具有5个特性: 有穷性、确定性、可行性，有零个或多个输入、 有一个或多个输8 出。 四、应用题 1. 1. 数据结构是一门研究什么内容的学科, 答:数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象 及对象间的关系和施加于对象的操作等的学科 2. 2. 数据元素之间的关系在计算机中有几种表示方法,各有什么特点, 答:四 种表示方法 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据 类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 单元练习1 一．判断题（下列各题，正确的请在前面的括号打√；错误的打╳） （√）（1）数据的逻辑结构与数据元素本身的容和形式无关。 （√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。 （ㄨ）（3）数据元素是数据的最小单位。 （ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。 （ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。 （√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（7）数据的存储结构是数据的逻辑结构的存储映像。 （√）（8）数据的物理结构是指数据在计算机实际的存储形式。 （ㄨ）（9）数据的逻辑结构是依赖于计算机的。 （√）（10）算法是对解题方法和步骤的描述。 二．填空题 （1）数据有逻辑结构和存储结构两种结构。 （2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。（4）树形结构和图形结构合称为非线性结构。 （5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。（6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。（7）数据的存储结构又叫物理结构。 （8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。（9）线性结构中的元素之间存在一对一的关系。 （10）树形结构结构中的元素之间存在一对多的关系， （11）图形结构的元素之间存在多对多的关系。 （12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的容。 （13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。 （14）算法是一个有穷指令的集合。 （15）算法效率的度量可以分为事先估算法和事后统计法。 （16）一个算法的时间复杂性是算法输入规模的函数。 （17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n 的函数。 （18）若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O （nlog2n）。 .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 一、选择题(20分) 1．下面关于线性表的叙述错误的是（D ）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 3．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C ）。 (A) 9 (B) 10 (C) 11 (D) 12 4．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（B ）。 (A) O(1) (B) O(log2n) (C) (D) O(n2) 5．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（B ）方法可以达到此目的。 (A) 快速排序(B) 堆排序(C) 归并排序(D) 插入排序 第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。 6.下列四种排序中（D ）的空间复杂度最大。 (A) 插入排序(B) 冒泡排序(C) 堆排序(D) 归并排序 7．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2) 8．设一棵二叉树的深度为k，则该二叉树中最多有（D ）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1 9．在二叉排序树中插入一个结点的时间复杂度为（B ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2) 10．设用链表作为栈的存储结构则退栈操作（B ）。 (A) 必须判别栈是否为满(B) 必须判别栈是否为空 (C) 判别栈元素的类型(D) 对栈不作任何判别 11．下列四种排序中（A ）的空间复杂度最大。 (A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆 12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（C ）。 (A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1 (D) N0=2N1+l 13.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不 超过（A ）。 (A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1) 14．数据的最小单位是（A ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 15．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（D ）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n) 第一章 1．在数据结构中，从逻辑上可以把数据结构分为（C ） A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C．线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O（mn）_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是（A） A 可以随机访问任一结点（顺序） B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ） A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D） A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序， 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比，双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确) 11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V 100+4*12=148 11.在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。 2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷) 一、应用题(3小题，共24分) 1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3 次、4次和9次，对该字符串用［0,1］进行前缀编码，问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路 径长度=2X 5+1X 5+3X 4+5X 3+9X 2+4X 3+4X 3+7X 2=98，所以，该字符串的编码长度至少为98位。 2.已知关键码序列为(Ja n, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec), 散列表的地址空间为0~16,设散列函数为H(x)= ［i/2」(取下整数)，其中i为关键码 中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。 【解答】H(Ja n)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Ju n)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1 X 7+2X 4+3X 1)/12=18/12 3.分析下面各程序段的时间复杂度 (1)s1(int n) { int p=1,s=0; for (i=1;iv=n;i++) { p*=i;s+=p; } return(s); } ——0(n) (2)s2(int n) x=0;y=0; For (k=1;kv=n;k++) x++; For (i=1;iv=n;i++) For (j=1;jv=n;j++) y++; ——0(n) 1?下述算法的功能是什么？ ListNode *Demo l(LinkList L P ListNode *p) ("L是有头结蛊的单链表 ListNodc *q=L->rLCxt P (1) V ‘V … 」(1 )返回结点*p的直接前趋结点地址。 q=q->nest; if (q) return q, else ?ro< #*p not in L"); I ⑵ i/oid Demo2(LisINode *p ,ListNode +q) 〔//p t*q*8S 表中的 两个结点 (2)交换结点*p和结点*q (p和q的值不变)。 DataTypetemp; temp=p->data, p->data=q->data; q-x^ata^emp, 1.对给定的一组权值W=( 5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 第三章栈和队列 一、判断题： 1、栈和队列都是限制存取点的线性结构(易) 2、栈和队列是两种重要的线性结构。(易) 3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易) 4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。(易) 答案：1-4 √√×× 二、选择题： 1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C____。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为_C___。 A、 i B、 n=i C、 n-i+1 D、不确定 3、栈结构通常采用的两种存储结构是_A___。 A、顺序存储结构和链式存储结构 B、散列方式和索引方式 C、链表存储结构和数组 D、线性存储结构和非线性存储结构 4、判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。A、top !=0 B、top= =0 C、top !=m0 D、top= =m0-1 5、判定一个顺序栈ST（最多元素为m0）为栈满的条件是D。A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-1 6、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删 除 7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ _C_。(不带空的头结点) (易) A、HS—＞next=s;9 B、s—＞next= HS—＞next; HS—＞next=s; C、s—＞next= HS; HS=s; D、s—＞next= HS; HS= HS—＞next 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 《数据结构与算法》复习题 选择题 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑 B．存储 C．逻辑和存储 D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何 B．结点个数的多少 C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是 O(n2) 。 s =0; for( I =0; i 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data 习题1 一、单项选择题 1. 数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5. 算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1）A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2）A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1）A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2）A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8. 数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 10. 计算机内部数据处理的基本单位是（）。 A.数据 B.数据元素 C.数据项 D.数据库数据结构经典例题
严蔚敏版数据结构课后习题答案-完整版
数据结构试题库答案
经典数据结构面试题(含答案)
数据结构课后参考答案
经典数据结构面试题(含答案)
大数据结构经典复习题(仅供参考)
数据结构习题及答案精编版
数据结构题库教材
数据结构经典例题
数据结构课后习题及答案
数据结构模拟卷(含答案)经典习题培训讲学
数据结构相关题库及答案
数据结构典型例题
数据结构习题与答案
数据结构(C语言)【经典题库】含标准答案
数据结构经典算法试题
数据结构习题及参考答案