1、程序员-数据结构与算法(四)及答案解析(总分：100.00，做题时间：90 分钟)一、试题一(总题数：1，分数：20.00)阅读以下说明和流程图，填补流程图中的空缺。说明已知数组 A1:n中各个元素的值都是非零整数，其中有些元素的值是相同的(重复)。为删除其中重复的值，可先通过以下流程图找出所有的重复值，并对所有重复值赋 0 标记之。该流程图采用了双重循环。处理思路：如果数组 A 某个元素的值在前面曾出现过，则该元素赋标记值 0。例如，假设数组 A 的各元素之值依次为 2，5，5，1，2，5，3，则经过该流程图处理后，各元素之值依次为 2，5，0，1，0，0，3。流程图（分数：20.00）填空
2、项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_二、试题二(总题数：1，分数：20.00)阅读以下说明和 C 函数，填补 C 函数中的空缺。说明函数 SetDiff(LA，LB)的功能是将 LA 与 LB 中的共有元素从 LA 中删除，使得 LA 中仅保留与 LB 不同的元素，而 LB 不变，LA 和 LB 为含头结点的单链表的头指针。例如，单链表 LA、LB 的示例如图中的(a)、(b)所示，删除与 LB 共有的元素后的 LA 如图中的(c)所示。（分数：20.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_三、试题三(总题数：1，分数：20.0
3、0)阅读以下说明和流程图，填补流程图中的空缺。说明本流程图用于计算菲波那契数列 a1=1,a2=1,an=an-1+an-2,n=3,4,.的前 n 项(n2)之和 S。例如，菲波那契数列前 6 项之和为 200 计算过程中，当前项之前的两项分别动态地保存在变量 A 和 B 中。流程图（分数：20.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_四、试题四(总题数：1，分数：20.00)阅读以下说明和 C 函数，填充函数中的空缺。说明函数 Insert _key(*root,key)的功能是将键值 key 插入到*root 指向根结点的二叉查找树中(二叉查找树为空时
4、*root 为空指针)。若给定的二叉查找树中已经包含键值为 key 的结点，则不进行插入操作并返回0；否则申请新结点、存入 key 的值并将新结点加入树中，返回 1。提示：二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；左、右子树本身就是二叉查找树。设二又查找树采用二叉链表存储结构，链表结点类型定义如下：typedef struct BiTrrodeint key _value; /*结点的键值，为非负整数*/struct BiTnode *
5、left,*right; /*结点的左、右子树指针*/BiTnode, *BSTree;C 函数int Insert _key(BsTree *root,int key)BiTnode *father=NULL,*p=*root,*s;while(_key!=p-key_value)(/*查找键值为Key 的结点*/father=p;if(keyp-key_value)p=_; /*进入左子树*/else p=_; /*进入右子树*/if (p) return 0; /*二叉查找树中已存在键值为 key 的结点，无须再插入*/s=(BiTraode*)malloc(_);/*根据结点类型生成新
6、结点*/if (!s) return-1;s-key_value=key; s-left=NULL; s-right=NULL;if(!father)_; /*新结点作为二叉查找树的根结点*/else /*新结点插入二叉查找树的适当位置*/if(keyfather-key_value)father-left=s;else father-right=s;return 1;（分数：20.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_五、试题五(总题数：1，分数：20.00)阅读以下说明和 C 函数，填充函数中的空缺。说明已知两个整数数组 A 和 B 中分别存放了长度为
7、 m 和 n 的两个非递减有序序列，函数Adiustment(A，B，m，n)的功能是合并两个非递减序列，并将序列的前 m 个整数存入 A 中，其余元素依序存入 B 中。例如：合并前 合并后数组 A 的内容 1,9,28 1,4,7数组 B 的内容 4,7,12,29,379,12,28,29,37合并过程如下：从数组 A 的第一个元素开始处理。用数组 B 的最小元素 B0与数组 A 的当前元素比较，若 A 的元素较小，则继续考查 A 的下一个元素；否则，先将 A 的最大元素暂存入 temp，然后移动 A 中的元素挪出空闲单元并将 B0插入数组 A，最后将暂存在 temp 中的数据插入数组 B
8、 的适当位置(保持 B 的有序性)。如此重复，直到 A 中所有元素都不大于 B 中所有元素为止。C 函数void Adjustment(int A,int B,int m,int n)/*数组 A 有 m 个元素，数组 B 有 n 个元素*/int k,temp;for(i=0;im;i+)if(Ai=B0) continue,temp=_;/*将 A 中的最大元素备份至 temp*/*从后往前依次考查 A 的元素，移动 A 的元素并将来自 B 的最小元素插入 A 中*/for(k=m-1;_;k-)Ak=Ak-i;Ai=_;/*将备份在 temp 的数据插入数组 B 的适当位置*/for(k
9、=1;_kn;k+)Bk-i=Bk;Bk-1=_;（分数：20.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_程序员-数据结构与算法(四)答案解析(总分：100.00，做题时间：90 分钟)一、试题一(总题数：1，分数：20.00)阅读以下说明和流程图，填补流程图中的空缺。说明已知数组 A1:n中各个元素的值都是非零整数，其中有些元素的值是相同的(重复)。为删除其中重复的值，可先通过以下流程图找出所有的重复值，并对所有重复值赋 0 标记之。该流程图采用了双重循环。处理思路：如果数组 A 某个元素的值在前面曾出现过，则该元素赋标记值 0。例如，假设数组 A 的各元素
10、之值依次为 2，5，5，1，2，5，3，则经过该流程图处理后，各元素之值依次为 2，5，0，1，0，0，3。流程图（分数：20.00）填空项 1:_ （正确答案：n-1）解析：填空项 1:_ （正确答案：Ai）解析：填空项 1:_ （正确答案：i+1）解析：填空项 1:_ （正确答案：Aj）解析：填空项 1:_ （正确答案：A(j)）解析：本题考查考生对程序流程的理解能力。根据题意，本题处理流程采用双重循环。其中，外层循环变量 i 用于标识未经处理前的原始数组的下标，内层循环变量 i 用于标识与原始数组中的元素进行比较的数组的下标。在比较时，由于最后一个元素是与前面的元素进行比较，因此，第一空
11、应填入 n-1。第二空处用于判断原始数组中是否有 0 元素，应填入：Ai。类似的思路，第三空处用于设置与原始数组中的元素进行比较的数组的下标。由于其初始元素为第二个元素，因此应填入：i+1。第四空处用于判断比较数组中是否有 0 元素，应填入：Aj。根据题目描述的处理思路，如果数组 A 某个元素的值在前面曾出现过，则该元素赋标记值 0。因此，若A(i)=A(j)，应将该元素赋标记值 0。这里需要注意数组下标的选择，显然第一个元素不会标记为 0，因此，第五空处应填入：A(j)。二、试题二(总题数：1，分数：20.00)阅读以下说明和 C 函数，填补 C 函数中的空缺。说明函数 SetDiff(LA
12、，LB)的功能是将 LA 与 LB 中的共有元素从 LA 中删除，使得 LA 中仅保留与 LB 不同的元素，而 LB 不变，LA 和 LB 为含头结点的单链表的头指针。例如，单链表 LA、LB 的示例如图中的(a)、(b)所示，删除与 LB 共有的元素后的 LA 如图中的(c)所示。（分数：20.00）填空项 1:_ （正确答案：pa=LA-next）解析：填空项 1:_ （正确答案：pb!=NULL 或 pb 或其等价形式）解析：填空项 1:_ （正确答案：pb=pb-next）解析：填空项 1:_ （正确答案：pa-next）解析：填空项 1:_ （正确答案：pre-next）解析：本题考
13、查考生对链表基本操作的掌握。第一空处用于实现将 pa 指向 LA 的第一个元素。由于单链表 LA 包含头结点，其第一个元素应为头结点的后继结点。因此，第一空处应填入 pa=LA-next。此时，pre 指向 LA 的头结点。根据题目描述的函数 SetDiff(LinkList LA，LinkList LB)的处理思路，在单链表 LB 中顺序查找与 LA 中当前元素相同的结点。第二空处需要填入一个循环条件，该循环条件应能实现对单链表 LB 的遍历。因此，第二空处应填入 pb!=NULL 或其等价形式。if(pa-data=pb-data) break 语句用于实现处理思路中描述的“相等，则结束在
14、 LB 中的查找过程”。而第三空处需要实现将选择 LB 中的下一个元素，因此应填入：pb=pb-next。第四空和第五空用于实现 LA 中元素的删除。要删除单链表 LA 的当前元素，应使其前驱结点的 next 指针指向当前结点的后继结点的 next 指针。因此，第四空处应填入：pa-next。当前指针 pa 应指向 pre 的后继结点，则第五空处应填入：pre-next。三、试题三(总题数：1，分数：20.00)阅读以下说明和流程图，填补流程图中的空缺。说明本流程图用于计算菲波那契数列 a1=1,a2=1,an=an-1+an-2,n=3,4,.的前 n 项(n2)之和 S。例如，菲波那契数列
15、前 6 项之和为 200 计算过程中，当前项之前的两项分别动态地保存在变量 A 和 B 中。流程图（分数：20.00）填空项 1:_ （正确答案：2 或 A+B 或其等价形式）解析：填空项 1:_ （正确答案：n）解析：填空项 1:_ （正确答案：A+B 或其等价形式）解析：填空项 1:_ （正确答案：B-A 或其等价形式）解析：填空项 1:_ （正确答案：S+B 或其等价形式）解析：本问题考查考生设计和阅读流程图的能力。从题日给出的流程图可以看出，第一空需要为 S 赋值。由于在初始时，S 为前两项之和，因此，第一空处应填入 A+B 或 2。第二空处需要设置一个循环条件。本流程图用于计算菲波那
16、契数列的前 n 项(n2)之和 S，显然，当循环变量值小于 n 时会一直循环进行求和，当循环变量值大于获等于 n 时循环结束，并输出和 S 的结果。因此，第二空处应填入 n。第三空至第五空处分别用于计算 B、A 和 S 的值。根据题目的描述，计算过程中，当前项之前的两项分别动态地保存在变量 A 和 B 中。因此，第三空处应填入 A+B。第四空处 A 为 B 的前一项，因此应填入 B-A。第五空处计算 S 的值，应在上次和的基础上再加上数列中下一项的值，因此应输入 S+B。四、试题四(总题数：1，分数：20.00)阅读以下说明和 C 函数，填充函数中的空缺。说明函数 Insert _key(*r
17、oot,key)的功能是将键值 key 插入到*root 指向根结点的二叉查找树中(二叉查找树为空时*root 为空指针)。若给定的二叉查找树中已经包含键值为 key 的结点，则不进行插入操作并返回0；否则申请新结点、存入 key 的值并将新结点加入树中，返回 1。提示：二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；左、右子树本身就是二叉查找树。设二又查找树采用二叉链表存储结构，链表结点类型定义如下：typedef struct BiTrr
18、odeint key _value; /*结点的键值，为非负整数*/struct BiTnode *left,*right; /*结点的左、右子树指针*/BiTnode, *BSTree;C 函数int Insert _key(BsTree *root,int key)BiTnode *father=NULL,*p=*root,*s;while(_key!=p-key_value)(/*查找键值为Key 的结点*/father=p;if(keyp-key_value)p=_; /*进入左子树*/else p=_; /*进入右子树*/if (p) return 0; /*二叉查找树中已存在键值为
19、 key 的结点，无须再插入*/s=(BiTraode*)malloc(_);/*根据结点类型生成新结点*/if (!s) return-1;s-key_value=key; s-left=NULL; s-right=NULL;if(!father)_; /*新结点作为二叉查找树的根结点*/else /*新结点插入二叉查找树的适当位置*/if(keyfather-key_value)father-left=s;else father-right=s;return 1;（分数：20.00）填空项 1:_ （正确答案：p）解析：填空项 1:_ （正确答案：p-left）解析：填空项 1:_ （正确
20、答案：p-right）解析：填空项 1:_ （正确答案：sizeof(BiTnode)）解析：填空项 1:_ （正确答案：*root=s）解析：本题考查数据结构中二叉查找树的实现，题目中涉及的考点主要有链表运算和程序逻辑。考生应理解二叉查找树的性质，分析程序时首先要明确各个变量所其的作用和代表的含义，并按照语句组分析各段代码的功能，从而完成空缺处的代码填写。根据程序段中的注释，while 循环所在的程序段用于查找键值为 key 的结点。此时的循环条件应满足二叉查找树非空。因此，第一空处应填入 p!=NULL 或其等价形式。根据二叉查找树的性质，若它的左子树非空，则其左子树上所有结点的键值均小于
21、根结点的键值。因此，若插入的键值 key 小于当前结点的键值，则应将其添加到其左子树中。因此，第二空处应填入 p-left。类似的思路，第三空处应填入 p-right 使其进入右子树。根据程序段中的注释，第四空处用于根据结点类型生成新结点。由于需申请的结点的类型为 BiTnode，因此，第四空处应填入 sizeof(BiTnode)，指定申请空间的大小。若该二叉查找树为空，新结点应作为二叉查找树的根结点进行插入，第五空处即实现该功能，应填入*root=s。五、试题五(总题数：1，分数：20.00)阅读以下说明和 C 函数，填充函数中的空缺。说明已知两个整数数组 A 和 B 中分别存放了长度为
22、m 和 n 的两个非递减有序序列，函数Adiustment(A，B，m，n)的功能是合并两个非递减序列，并将序列的前 m 个整数存入 A 中，其余元素依序存入 B 中。例如：合并前合并后数组A 的内容1,9,281,4,7数组B 的内容4,7,12,29,379,12,28,29,37合并过程如下：从数组 A 的第一个元素开始处理。用数组 B 的最小元素 B0与数组 A 的当前元素比较，若 A 的元素较小，则继续考查 A 的下一个元素；否则，先将 A 的最大元素暂存入 temp，然后移动 A 中的元素挪出空闲单元并将 B0插入数组 A，最后将暂存在 temp 中的数据插入数组 B 的适当位置(
23、保持 B 的有序性)。如此重复，直到 A 中所有元素都不大于 B 中所有元素为止。C 函数void Adjustment(int A,int B,int m,int n)/*数组 A 有 m 个元素，数组 B 有 n 个元素*/int k,temp;for(i=0;im;i+)if(Ai=B0) continue,temp=_;/*将 A 中的最大元素备份至 temp*/*从后往前依次考查 A 的元素，移动 A 的元素并将来自 B 的最小元素插入 A 中*/for(k=m-1;_;k-)Ak=Ak-i;Ai=_;/*将备份在 temp 的数据插入数组 B 的适当位置*/for(k=1;_kn;
24、k+)Bk-i=Bk;Bk-1=_;（分数：20.00）填空项 1:_ （正确答案：Am-1或*(A+m-1)或其等价表示）解析：填空项 1:_ （正确答案：ki）解析：填空项 1:_ （正确答案：B0或*B）解析：填空项 1:_ （正确答案：tempBk或其等价表示）解析：填空项 1:_ （正确答案：temp）解析：本题考查 C 语言中数组的基本概念和应用。根据程序段中的注释，第一空处将数组 A 中的最大元素备份至 temp。由于 A 中存放了长度为 m 的非递减有序序列，其最大元素为第 m 个元素，因此，第一空处应填入：Am-1或其等价表示。程序段接下来的 for 循环实现从后往前依次考查 A 的元素，移动 A 的元素并将来自 B 的最小元素插入 A 中。由于 B 的最小元素插入到 Ai和 Am-1之间，因此，第二空处的循环控制条件应填入：ki。第三空处将 B 的最小元素 b0插入到适当的位置，因此应填入 B0或其等价表示。程序段的最后一个 for 循环实现将备份在 temp 的数据插入数组 B 的适当位置。在将 temp 插入到 B 中时，须保持 B 的有序性，因此，第四空处应填入：tempBk。第五空处实现将 temp 插入到 B 中，因此应填入 temp。
