《天津大学-901-2015-真题》由会员分享，可在线阅读，更多相关《天津大学-901-2015-真题（5页珍藏版）》请在金锄头文库上搜索。
1、考试科目名称：数据结构与程序设计考试科目编号：901共 5 页一、实作题(每题 10 分，共 50 分)1.如果一棵树用 n1 个度为 1 的节点，n2 个度为 2 的节点，.，nm 个度为 m 的节点，则该树共有多少个叶子节点?(给出计算公式和结果)2.已知关键字序列(55，31，11，35，46，73，63，02，07)，从空树开始构造一棵平衡二叉树，画出每加入一个新结点时二叉树的形态。3.采用折半查找方法在关键字序列(5,23,45,58,67,74,80,85,96)中查找关键字 45，给出查找过程，并计算等概率情况下查找成功的平均查找长度。4.已知一棵二叉树的中序遍历(或中根)结点序
2、列为 DGBAECHIF，后序遍历结点为 GDBEIHFCA。(1)试画出该二叉树。(2)试画出该二叉树的中序线索树；(3)试画出该二叉树对应的森林。5.已知一个有向图如图所示。(1)给出该图的邻接表表示；(2)给出拓扑排序有序序列的全排序；(3)以 V1 为源点，V8 为终点，给出关键路径。二、算法设计题(18 分)由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，用 C 语言或者 C+实现由已知某二叉树的前序遍历序列和中序遍历序列，生成一棵二叉链表表示的二叉树，并打印出后序遍历序列的算法。(算法要求有类型定义，且必须有主函数)各个学校计算机/软件专业考研真题 免费分享 h t t p
3、 s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研考试科目名称：数据结构与程序设计考试科目编号：901三、读程序，写结果。(每题 7 分，共 42 分)1.#include using namespace std;int main()int a =-1,b = 3, x, y;x = (a+)&(!(b-);y = (-a)&(!(+b);coutabxyendl;return 0;2.#include using namespace std;in
4、t main()int x = 1, y = 2, z = 3;if(x = y + z)x+;elsex-;coutxendl;return 0;各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研考试科目名称：数据结构与程序设计考试科目编号：9013.#include using namespace std;int main()int x = 0;for (int i = 0; i 2;
5、i+)if (j % 2)break;x+;x+;coutx = x endl;return 0;4.#include using namespace std;int funa(int x)if (x % 2)return 1;elsereturn 0;void funb(int x, int &y)for (int i = 1; i x; i+)if (funa(i)y += i;int main()int x = 10, y = 5;funb(x, y);cout x y endl;return 0;各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b
6、 .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研考试科目名称：数据结构与程序设计考试科目编号：9015.#include using namespace std;class ?int a, b;public:?(int i, int j):a(i),b(j)coutconstructorendl;?()coutdestructorendl;int main()? obj1(1, 2);? obj2 = obj1;return 0;6.#include using namespa
7、ce std;class ?friend class ?;private:int x;static int y;public:void set(int i)x = i;void print()cout x y endl;class ?:public ?public:?(int i, int j)a.x = i; ?:y = j;void print()cout a.x ?:y+ endl;private:? a;int ?:y = 5;各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获
8、取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研考试科目名称：数据结构与程序设计考试科目编号：901int main()? obj1;obj1.set(3);obj1.print();? obj2(1, 2);obj2.print();obj1.print();return 0;四、按照要求，使用 C+语言编写程序(每题 15 分，共 30 分)1.求正整数的根。题目描述：对于一个正整数，将它的每一位上的数字相加，得到的结果若只有一位数，那么该结果就是这个数的根，否则就再将该结果各位数相加，直至结果为一位数，这个一位数就是这个数的数根。输入：有多
9、组样例，每组样例输入一个正整数，输入以 0 结束。输出：每组样例输出一行，包含一个数，即输入数的根。输入样例：24390输出样例：632.单词反转题目描述：对于给定的单词集，将每个单词中的字母顺序反转后输出，且不改变原来单词集中的单词顺序。输入：输入样例中包含若干组测试，每组测试样例的第一行给出的是测试组数 T，接下来共 T 行数据，每行表示一组样例，包含多个单词，每个单词用空格隔开，且每个单词仅包含按大写字母和小写字母。输出：每组样例输出一行，即每个单词反转后的结果。输入样例：3I am happy todayTo be or not to beI want to win the practice constest输出样例：I ma yppah yadotoT eb ro ton ot ebI tnaw ot niw eht ecitacrp tsetnoc各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研
