1、计算机学科专业基础综合数据结构-非统考补充内容：串、数组和稀疏矩阵、树与二叉树(二)及答案解析(总分：100.00，做题时间：90 分钟)一、B综合应用题/B(总题数：35，分数：100.00)1.采用顺序存储方式存储串，编写一个置换函数，将串 s1 中的第 i 个字符开始的 j 个字符(包括第 i 个字符)构成的子串用 s2 串进行替换，函数名为 replace(s1，i，j，s2)。例如：replace(“abcd“，1，3，“xyz“)返回“xyzd“。（分数：1.50）_2.采用顺序结构存储串，编写一个函数 index(s1，s2)，用于判定 s2 是否是 s1 的子串。若是子串，返回
2、其在主串中的位置；否则返回-1。（分数：1.50）_3.设计一个算法将串中的所有字符倒过来重新排列。（分数：1.00）_4.利用串的基本运算，编写一个算法，删除串 s1 中所有的 s2 子串。（分数：3.00）_5.编写一个算法，计算子串 s2 在主串 s1 中出现的次数。（分数：3.00）_6.采用顺序结构存储串，编写一个实现串通配符匹配的函数 pattern_index()，其中的通配符只有?，它可以和任一字符匹配成功，例如，pattern_index(“?re“，“there are“)返回的结果是 3。（分数：3.00）_7.设数组 R0n-1的 n 个元素中有多个 0 元素，设计一个
3、算法，将 R 中所有的非 0 元素依次移动到 R 数组的前端。（分数：3.00）_8.已知 R0n-1为整型数组，试设计实现下列运算的递归算法： (1)求数组 R 中的最大整数； (2)求 n个整数之和； (3)求 n 个整数的平均值。（分数：3.00）_9.一个 n 阶矩阵 A0n-1，0n-1采用一维数组 s0n*n-1按行序为主序，存放其上三角各元素，编写一个算法求出 Sk在 Aij中的位置和 Aij在 Sk中的位置。（分数：3.00）_10.试设计一个算法，将 A0n-1中所有奇数移到偶数之前。要求不另增加存储空间，且时间复杂度为O(n)。（分数：3.00）_11.要求设计一个算法，设
4、置 mn(m=2，n=3)阶矩阵的元素后，统计这个矩阵中具有下列特征的元素个数，并输出它们的坐标及数值：它们既是所在行中的最小值，又是所在列中的最小值：或者，它们既是所在行中的最大值，又是所在列中的最大值。（分数：3.00）_12.对于二维数组 Amn，其中 m80，n80，先读入 m 和 n，然后读该数组的全部元素，对如下三种情况分别编写相应函数： (1)求数组 A 靠边元素之和； (2)求从 A00开始的互不相邻的各元素之和； (3)当 m=n 时，分别求两条对角线上的元素之和，否则打印出 mn 的信息。（分数：3.00）_13.以下是一个 55 阶螺旋方阵。设计一个算法输出该形式的 nn
5、(n10)阶方阵(顺时针方向旋进)。 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9（分数：3.00）_14.已知 A 和 B 为两个 nn 阶的对称矩阵，输入时，对称矩阵只输入下三角形元素，存入一维数组，如图所示(对称矩阵 M 存储在一维数组 A 中)，设计一个算法求对称矩阵 A 和 B 的乘积。（分数：3.00）_15.说明稀疏矩阵的三元组存储结构并实现稀疏矩阵的基本操作。（分数：3.00）_16.在 nn(n3)阶的稀疏矩阵 A 中，只有下标满足 1in 和 n-ijn-i+2 的元素 Aij不等于0，若
6、这些非 0 元素按行优先的顺序存储在一维数组 B 中，编写一个算法通过 B 求 Aij之值。也就是说，在存在 B 的情况下已知 i、j，求 Aij。（分数：3.00）_17.假设稀疏矩阵只存放其非 0 元素的行号、列号和数值，以一维数组顺次存放，行号-1 作结束标志。例如，如下所示的稀疏矩阵 M，存放在一维数组 D 中，D 的元素如下：D0=0，D1=0，D2=1，D3=0，D4=4，D5=10，D6=2，D7=8，D8=5，D9=-1。 （分数：3.00）_18.如果一棵树有 n1个度为 1 的结点，有 n2个度为 2 的结点有 nm个度为 m 的结点，试问有多少个度为 0 的结点?试推导。
7、（分数：3.00）_19.如果一棵有 n 个结点的满二叉树的高度为 h(根结点所在的层次为 1)，则求解下列问题。 (1)用高度如何表示结点总数 n?用结点总数 n 如何表示高度 h? (2)若对该树的结点从 0 开始按中序遍历次序进行编号，则如何用高度 h 表示根结点的编号?如何用高度 h 表示根结点的左子女结点的编号和右子女结点的编号?（分数：3.00）_20.编写一个算法，将用二叉链表表示的完全二叉树转换为二叉树的顺序表示，假设数据类型为 int 型。（分数：3.00）_21.一棵完全二叉树以顺序方式存储在数组 A 的 n 个元素中。设计一个算法构造该二叉树的链接存储表示。（分数：3.0
8、0）_22.设计一个算法，将一棵以链接方式存储的二叉树按顺序方式存储到数组 A 中。（分数：3.00）_23.计算以 t 为根的二叉树中各结点中的最大元素的值，假设数据类型为 float 型。（分数：3.00）_24.设一棵二叉树 T 采用二叉链表表示，编写一个算法，判断 T 是否是完全二叉树。（分数：3.00）_25.设一棵二叉树以二叉链表作为它的存储表示，试编写一个算法，用括号形式 key(LT，RT)输出二叉树的各个结点。其中，key 是根结点的数据，LT 和 RT 是括号形式的左子树和右子树。要求空树不打印任何信息，一个结点的树的打印形式是 x，而不应是(x,)的形式。（分数：3.00
9、）_26.假设二叉树采用链接存储方式存储，编写一个后序遍历二叉树的非递归算法。（分数：3.00）_27.试设计判断两棵二叉树是否相似的算法。所谓二叉树 t1 和 t2 相似是指 t1 和 t2 都是空的二叉树；或者 t1 和 t2 的根结点是相似的，t1 的左子树和 t2 的左子树是相似的且 t1 的右子树与 t2 的右子树是相似的。（分数：3.00）_28.有一棵二叉排序树 r，设计一个非递归算法删除以 x 为根结点的子树，并释放这些被删结点的空间。（分数：3.00）_29.假设二叉树 T 中至多有一个结点的数据域值为 x，试设计一个算法拆开以该结点为根的子树，使原二叉树分成两棵二叉树。（分
10、数：3.00）_30.假设二叉树采用链接存储结构进行存储，t 指向根结点，s 所指结点为任意一个给定的结点，编写一个求出从根结点到 p 所指结点之间路径的函数。（分数：3.00）_31.编写一个算法判断一棵二叉树是否是对称的。所谓对称是指其左、右子树的结构是对称的。（分数：3.00）_32.设树 b 是一棵采用链接结构存储的二叉树，设计一个算法把树 b 的左子树和右子树进行交换的算法。（分数：3.00）_33.编写一个算法，在一棵中序线索二叉树中以非递归的方式中序正向和中序反向遍历该二叉树。（分数：3.00）_34.设一棵二叉树采用二叉链表作为它的存储表示，指针 t 指向根结点，试编写一个在二
11、叉树中查找值为x 的结点，并打印该结点所有祖先结点的算法。在此算法中，假设值为 x 的结点不多于一个且数据类型为int 型。（分数：3.00）_35.设一棵二叉树采用二叉链表表示，编写一个算法，利用二叉树的前序遍历求任意指定的两个结点 I 和J 间的路径和路径长度。（分数：3.00）_计算机学科专业基础综合数据结构-非统考补充内容：串、数组和稀疏矩阵、树与二叉树(二)答案解析(总分：100.00，做题时间：90 分钟)一、B综合应用题/B(总题数：35，分数：100.00)1.采用顺序存储方式存储串，编写一个置换函数，将串 s1 中的第 i 个字符开始的 j 个字符(包括第 i 个字符)构成的
12、子串用 s2 串进行替换，函数名为 replace(s1，i，j，s2)。例如：replace(“abcd“，1，3，“xyz“)返回“xyzd“。（分数：1.50）_正确答案：(本题比较简单，有多种处理方法： 思路 1：先给替换串腾出足够的位置，比如从 i 到 j 有 n个字符，s2 的长度为 m，如果 mn，则下标 j+1 往后的字串向前移动 n-m 个位置；如果 mn，则下标j+1 往后的字串向后移动 m-n 个位置；如果 m 等于 n，则无需移动。然后将 s2 串复制到腾出的位置上。 思路 2：先提取 s1 中位置 i 之前的所有字符构成的子串 str1，再提取位置 i+j-1 及之后
13、的所有字符构成的子串 str2，最后将 str1、s2、str2 连接起来便构成了结果串。 本题代码如下(仅提供“思路 2”的实现)： Str replace(Str *s1,int i,int j,Str *s2) Str s; int n,k; if(i+j-1=s1-length) for(n=0;ni-1;+n) /把 s1 的前 i-1 个字符赋给 s s.chn=s1-chn; for(n=0;ns2-length;+n) /连接 s2 串 s.chi+n-1=s2-chn; s.length=i+s2-length-1; for(n=s.length,k=i+j-1;ks1-le
14、ngth;+n,+k) /连接 s1 的位置 i 及之后的字符 s.chn=s1-chk; s.length=n; s.chs.length=/0; else s.ch0=/0; s.length=0; return s; )解析：2.采用顺序结构存储串，编写一个函数 index(s1，s2)，用于判定 s2 是否是 s1 的子串。若是子串，返回其在主串中的位置；否则返回-1。（分数：1.50）_正确答案：(本题的算法思想是，设s1=“a1a2am“s2=“b1b2bn“从 s1 中找与 b1 匹配的字符 ai，若 ai=b1，则判断是否 ai+1=b2，a i+1=bn，若都相等，则 s2
15、为 s1 子串；否则继续比较 ai之后的字符。本题代码如下：int index(Str *s1,Str *s2)int i=0,j,k;while(is1-length) j=0;if(s1-chi=s2-chj)k=i+1;+j;while(ks1-length+j;if(j=s2-length) /s2 终止时找到了子串break;else +i;else +i;if(i=s1-length)return -1;elsereturn i+1;)解析：3.设计一个算法将串中的所有字符倒过来重新排列。（分数：1.00）_正确答案：(Str reverse(Str *s) int i; Str
16、t; for(i=0;is-length;+i) t.chs-length-i-1=s-chi; t.length=s-length; t.cht.length=/0; return t; )解析：4.利用串的基本运算，编写一个算法，删除串 s1 中所有的 s2 子串。（分数：3.00）_正确答案：(本题利用 index()函数和删除子串的函数循环来实现。其程序如下： void delall(Str *s1,Str *s2) int n; n=index(s1,s2); while(n=0) del(s1,n,length(s2); n=index(s1,s2); disp(s1); 其中 d
17、el 函数实现如下： int del(Str *s,int pos,int n) /从串 s 中删除从位置 pos 开始的 n 个字符构成的子串 int i; if(pos+ns-length) return 0; for(i=pos+n-1;is-length;+i) s-chi-n=s-chi; s-length=s-length-n; s-chs-length=/0; return 1; )解析：5.编写一个算法，计算子串 s2 在主串 s1 中出现的次数。（分数：3.00）_正确答案：(对函数 index()稍加改进成为 preindex()，使其返回子串 s2 在主串 s1 中第 n
18、 个位置之后出现的位置，然后用循环判断即可。实现代码如下： int preindex(Str *s1,Str *s2,int n) int i=n,j,k; while(is1-length) j=0; if(s1-chi=s2-chj) k=i+1;+j; while(ks1-length +j; ) if(j=s2-length) /s2终止时找到了子串 break; else +i; else +i; if(i=s1-length) return -1; else return i+1; int count(Str *s1,Str *s2) /求出现次数 int n=0,i=0; do
19、i=preindex(s1,s2,i); if(i!=-1) i=i+length(s2); +n; while(i!=-1); return n; )解析：6.采用顺序结构存储串，编写一个实现串通配符匹配的函数 pattern_index()，其中的通配符只有?，它可以和任一字符匹配成功，例如，pattern_index(“?re“，“there are“)返回的结果是 3。（分数：3.00）_正确答案：(本题增加了?的处理功能。实现代码如下： int pattern_index(Str *subs,Str *s) int i,j,k; for(i=0;s-chi;+i) for(j=i,k
20、=0;(s-chj=subs-chk)|(subs-chk=?);+j,+k) if(subs-chk+1=/0) return i+1; return -1; )解析：7.设数组 R0n-1的 n 个元素中有多个 0 元素，设计一个算法，将 R 中所有的非 0 元素依次移动到 R 数组的前端。（分数：3.00）_正确答案：(用 i 指向不为 0 元素应放的下标，j 遍历 R，当 Rj不为 0 时，在 i 与 j 不相同时将 Ri与Rj交换。 void move(int R,int n) int i=-1,j,temp; for(j=0;jn;+j) if(Rj!=0) /Rj为第 i 个不为
21、 0 的元素 +i; if(i!=j) /Rj不在位置 i 上,则 Ri与 Rj交换 temp=Ri; Ri=Rj; Rj=temp; )解析：8.已知 R0n-1为整型数组，试设计实现下列运算的递归算法： (1)求数组 R 中的最大整数； (2)求 n个整数之和； (3)求 n 个整数的平均值。（分数：3.00）_正确答案：(本题属于简单的分治法的递归实现，关于递归和分治法相关问题请看数据结构高分笔记中的特别章讲解：考研中某些算法的分治法解释。 实现代码如下： int maxdata(int R,int n) /求R0到 Rn共 n+1 个元素中的最大值 int m; if(n=0) ret
22、urn R0; else m=maxdata(R,n-1); if(Rnm) return Rn; else return m; int sum(int R,int n) /求 R0到 Rn共 n+1 个元素之和 if(n=0) return R0; else return(Rn+sum(R,n-1); double avg(int R,int n) /求 R0到 Rn共 n+1 个元素的平均值 if(n=0) return R0; else return(Rn+n*avg(R,n-1)/(n+1); )解析：9.一个 n 阶矩阵 A0n-1，0n-1采用一维数组 s0n*n-1按行序为主序，
23、存放其上三角各元素，编写一个算法求出 Sk在 Aij中的位置和 Aij在 Sk中的位置。（分数：3.00）_正确答案：(这是一道简单题，只要注意区分行主序和列主序即可： 已知 Sk，求 Aij的算法如下： void findij(int k,int n,int j=k%n; 已知 Aij求 Sk的算法如下： void findk(int i,int j,int )解析：10.试设计一个算法，将 A0n-1中所有奇数移到偶数之前。要求不另增加存储空间，且时间复杂度为O(n)。（分数：3.00）_正确答案：(i 从左向右遍历，指向 A 左边的一个偶数，j 从右向左遍历，指向 A 右边的一个奇数，然
24、后将Ai与 Aj交换，如此循环直到 i 大于等于 j。代码如下： void move(int A,int n) int i=0,j=n-1,temp; while(ij) while(Ai*2=1 while(Aj%2=0 if(ij) /ii与 Aj交换 temp=Ai; Ai=Aj; Aj=temp; +i;-j; )解析：11.要求设计一个算法，设置 mn(m=2，n=3)阶矩阵的元素后，统计这个矩阵中具有下列特征的元素个数，并输出它们的坐标及数值：它们既是所在行中的最小值，又是所在列中的最小值：或者，它们既是所在行中的最大值，又是所在列中的最大值。（分数：3.00）_正确答案：(实现本
25、题的代码如下：void findmin(int R23,int m,int n)int i,j,k,min,minj,find;cout“最小值: “;for(i=0;im;+i) /处理第 i 列min=Ri0;minj=0;for(j=1;jn;+j) /找出第 i 行上的最小值，列号为 minjif(Rijmin)min=Rij;minj=j;find=1;for(k=0;km;+k) /判断 min 是否为 minj 列上的最小值if(minRkmini)find=0;break;if(find)cout“(“i“,“mini“): “min“ “;coutendl;void find
26、max(int R23,int m,int n)int i,j,k,max,maxj,find;cout“最大值: “;for(i=0;imax=Ri0;maxj=0;for(j=l;jn;+j) /找出第 i 行上的最大值，列号为 maxjif(Rijmax)max=Rij;maxj=j;find=1;for(k=0;km;+k) /判断 max 是否为 maxj 列上的最大值if(maxRkmaxj)find=0;break;if(find)cout“(“i“,“maxj“): “max“ “;coutendl;)解析：12.对于二维数组 Amn，其中 m80，n80，先读入 m 和 n，
27、然后读该数组的全部元素，对如下三种情况分别编写相应函数： (1)求数组 A 靠边元素之和； (2)求从 A00开始的互不相邻的各元素之和； (3)当 m=n 时，分别求两条对角线上的元素之和，否则打印出 mn 的信息。（分数：3.00）_正确答案：(1)本小题是计算数组 A 的最外围的 4 条边的所有元素之和，先分别求出各边的元素之和，累加后减去 4 个角的重复相加的元素即为所求。 (2)本小题的互不相邻是指上、下、左、右、对角线均不相邻，即求第 0，2，4，的各行中第 0，2，3，列的所有元素之和，函数中用 i 和 j 变量控制即可。 (3)本小题中一条对角线是 Aii(0im-1)，另一条
28、对角线是 Am-i-1i(0im-1)，采用循环实现。 实现代码如下： void proc1(int Amn) /实现(1)小题功能的函数 int s=0,i,j; for(i=0;im;+i) /第一列 s=s+Ai0; for(i=0;im;+i) /最后一列 s=s+Ain-1; for(j=0;jn;+j) /第一行 s=s+A0j; for(j=0;jm;+j+) /最后一行 s=s+Am-1j; s=s-A00-A0n-1-Am-10-Am-1n-1; /减去 4 个角的重复元素值 cout“结果 1: “sendl; void proc2(int Amn) /实现(2)小题功能的
29、函数 int s=0,i=0,j; do j=0; do s=s+Aij; j=j+2;/跳过一列 while(jn); i=i+2;/跳过一行 while(im); cout“结果 2: “sendl; void proc3(int Amn) /实现(3)小题功能的函数 int i,s; if(m!=n) cout“mn“endl; else s=0; for(i=0;im;+i) s=s+Aii; /求第一条对角线之和 for(i=0;in;+i) s=s+An-i-1i; /累加第二条对角线之和 cout“结果 3: “sendl; )解析：13.以下是一个 55 阶螺旋方阵。设计一个算
30、法输出该形式的 nn(n10)阶方阵(顺时针方向旋进)。 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9（分数：3.00）_正确答案：(本题代码实现如下： void fun(int aMaxLenMaxLen,int n)/MaxLen 是已经定义的常量 int i,j,k=0,m; if(n%2=0)/m=n/2 m=n/2; else m=n/2+1; for(i=0;im;+i) for(j=i;jn-i;+j) +k; aij=k; for(j=i+1;jn-i;+j) +k; ajn-i-1=k; f
31、or(j=n-i-2;j=i;-j) +k; an-i-1j=k; for(j=n-i-2;j=i+1;-j) +k; aji=k; )解析：14.已知 A 和 B 为两个 nn 阶的对称矩阵，输入时，对称矩阵只输入下三角形元素，存入一维数组，如图所示(对称矩阵 M 存储在一维数组 A 中)，设计一个算法求对称矩阵 A 和 B 的乘积。（分数：3.00）_正确答案：(对称矩阵第 i 行和第 j 列元素的数据在一维数组中的位置是： i(i-i)/2+j (当 ij 时) j(j-1)/2+i (当 ij 时) 本题实现代码如下： int value(int a,int i,int j) if (
32、i=j) return a(i*(i-1)/2+j; else return a(j*(j-1)/2+i; void mult(int a,int b,int cnn) int i,j,k,s; for(i=0;in;+i) for(j=0;jn;+j) s=0; for(k=0;kn;+k) s=s+value(a,i,k)*value(b,k,j)； cij=s; void disp(int a) int i,j; for(i=0;in;+i) for(j=0;jn;+j) coutsetw(3)value(a,i,j); coutendl; )解析：15.说明稀疏矩阵的三元组存储结构并实现稀疏矩阵的基本操作。（分数：3.00）_正确答案：(三元组存储结构是一种顺序结构，顺序表中的每个结点对应稀疏矩阵的一个非 0 元素
