山东科技大学算法复习题

//////////Problem D: 货币兑换Description给出人民币对美元、欧元、日元的当日汇率，求给定金额的人民币能兑换成外币的金额，求给定金额的外币能兑换成人民币的金额。

要计算的外币有三种：美元、欧元、日元。

Input输入有三行。

第一行依次为美元、欧元、日元外币汇率，用空格分开。

汇率用100外币为单位，精确到小数点后4位，如668.5200表示“100美元=668.5200人民币”。

汇率浮动范围为(0,10000)。

第二行为外币金额x，第三行为人民币金额y。

x,y均为整数，且0<x,y<10000。

Output输出为两行。

第一行为金额为x的美元、欧元、日元兑换成人民币的金额，用空格分开。

第二行为金额为y的人民币兑换成美元、欧元、日元的金额，用空格分开。

所有金额精确到小数点后两位。

Sample Input668.5200 908.0685 7.985215001500Sample Output10027.80 13621.03 119.78#include <stdio.h>int main(){double i,j,k,a,b,c,d,e,f;double x,y;scanf ("%lf %lf %lf",&i,&j,&k);scanf ("%lf%lf",&x,&y);a=x/100*i;b=y/100*j;c=x/100*k;d=y*100/i;e=y*100/j;f=y*100/k;printf ("%.2lf %.2lf %.2lf\n",a,b,c);printf ("%.2lf %.2lf %.2lf\n",d,e,f);}////Problem E: 求字符的值////Description从键盘输入3个字符（不含双字节字符），分别输出每个字符的十进制值（ASCII码）、八进制值和十六进制值。

2021年山东科技大学数据结构与操作系统--真题及参考答案数据结构与操作系统Z试卷《数据结构》部分（90分）一、简答题（20分，每题5分）1、请给出四种数据结构基本类型。

答：根据数据元素之间关系的不同特征，通常有下列4类的基本结构：（1）集合。

（2）线性结构。

（3）树形结构。

（4）图状结构或网状结构。

2、简述栈和队列的区别。

（P44;P58）区别和联系：从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。

栈只允许在表的一端进行插入或删除操作，队列只允许在表的一端进行插入操作、而在另一端进行删除操作。

因而，栈和队列也可以被称作为操作受限的线性表。

3、什么是关键路径？(P183)在AOE网中，有些活动可以并行地运行，最短完成时间应是从源点到汇点的最长路径长度（指路径上所有权值之和），称这样的路径为关键路径。

4、插入类排序有哪几种？其中，哪些是不稳定的排序算法？(P265)二、应用题（40分）1、如果进栈的序列是12345，请给出所有3、4先出栈的序列（3在4之前出栈）。

（5分）(P)【解答】34215 ，34251， 34521 (可以参考下面这个题：【￥】铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1，2，3，4，5，6，那么是否能够得到435612， 325641， 154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出\进栈\或\出栈\的序列)。

【解答】输入序列为123456，不能得出435612和154623。

不能得到435612的理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。

不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。

得到325641的过程如下：1 2 3顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。

Problem A: Hello world! DescriptionXiao_ming有两个哥哥，大哥叫Da_min，二哥叫Er_min。

三兄弟放学回家，父母分别跟他们打招呼。

Input无Output请输出：Hello Da_min,Hello Er_min,Hello Xiao_ming!Sample InputSample OutputHello Da_min,Hello Er_min,Hello Xiao_ming!HINT请注意换行符#include <stdio.h>int main(){printf("Hello Da_min,\nHello Er_min,\nHello Xiao_ming!");}Problem A: 算术基本运算Description计算两整数x和y（0<x,y<1000）的和、差、积、商、余数、x的平方和y的三次方。

Input输入只有一行，格式见sample。

Output输出为多行，按顺序每行输出x,y的和、差、积、商、余数、x的平方和y的三次方，格式见sampleSample Inputx = 11, y = 3Sample Outputx + y : 14x - y : 8x * y : 33x / y quotient: 3, remainder: 2x ^ 2 : 121y ^ 3 : 27HINT注意输入输出格式。

了解C语言整数除法运算符的特点，并且没有求幂的运算符。

#include <stdio.h>int main(){int x,y;scanf ("x = %d, y = %d",&x,&y);printf ("x + y : %d\n",x+y);printf ("x - y : %d\n",x-y);printf ("x * y : %d\n",x*y);printf ("x / y quotient: %d, remainder: %d\n",x/y,x%y);printf("x ^ 2 : %d\n",x*x);printf ("y ^ 3 : %d\n",y*y*y);}Problem B: 求圆的面积和周长Description从键盘输入圆的半径，求圆的面积和周长，圆周率取3.14。

山东科技大学第二届ACM程序设计大赛试题册试题共14页，题目共计12道山东科技大学第二届ACM 程序设计大赛试题册Problem A 简单计算Description给出n 个十进制的数，找出这n 个数的二进制表示中1的个数最少的数。

Input输入的第一行为一个正整数T （1≤T ≤20）,代表测试数据组数。

对于每组测试数据，输入的第一行为一个正整数n （1≤n ≤10000），第二行为n个正整数A 1、A 2、…、A n （1≤A i ≤109），每个数之间以空格分隔。

Output每组数据输出一行，先输出数据组数，再输出二进制中含1最少的数，如果存在多个数符合条件，输出最小的那个。

具体输出格式见样例输出。

Sample Input Sample Output山东科技大学第二届ACM 程序设计大赛试题册Problem B 关键字搜索Description我们的新网站具有了全新的搜索功能，使用了2个通配符“*”和“？”，其中“*”表示0或者多个小写字母，“？”代表1个字母。

当我们输入一个关键字的时候，我们在不确定的地方就使用通配符。

我们在数据库里面有多条记录，每条记录都是由小写字母组成，现在给出一个关键字，你能告诉我数据库里面有多少条与关键字相匹配的记录吗？例如： 如果关键字是j*y*m*y?，那么jiyanmoyu ，jyanmoyu ，jymyu 都是相匹配的记录。

Input第一行输入一个T （T ≤20），表示有T 组测试数据。

对于每组测试数据，第一行是输入的关键字，接下是数据库里面的所有记录的条数n ，1≤n ≤10000,每条记录的长度不超过50个小写字母。

Output对于每组测试数据，输出与关键字相匹配的总记录条数，占一行。

Sample Input Sample Output山东科技大学第二届ACM 程序设计大赛试题册Problem C 正方形Description在二维坐标轴内给出四个点，这四个点能否构成一个正方形。

2022年山东科技大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-13、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、已知串S='aaab'，其next数组值为（）。

A.0123B.1123C.1231D.12116、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定8、一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11至1025之间D.10至1024之间9、有n（n>0）个分支结点的满二叉树的深度是（）。

A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。

A.(n-1)/2B.n/2C.(n+1)/2D.n二、填空题11、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。

c语言考试题及答案山东科技大学一、选择题（每题2分，共20分）1. 下列哪个选项是C语言中的关键字？A. voidB. intC. floatD. All of the above答案：D2. C语言中，用于定义一个字符常量的是什么？A. "A"B. 'A'C. AD. a答案：B3. 在C语言中，以下哪个函数用于计算并返回字符串的长度？A. strlen()B. strcat()C. strcpy()D. strcmp()答案：A4. 下列哪个选项不是C语言中的控制语句？A. ifB. whileC. switchD. continue答案：D5. C语言中，以下哪个选项是正确的二维数组定义？A. int array[3][4];B. int array[][];C. int array[3][];D. int array[3][4] = {{1,2},{3,4},{5,6}};答案：A6. 在C语言中，哪个运算符用于将一个值赋给变量？A. +B. -C. =D. %答案：C7. 下列哪个选项是C语言中的正确注释？A. // This is a single line commentB. /* This is a single line comment */C. // This is a multi-line commentD. /* This is a multi-line comment */答案：A8. 在C语言中，以下哪个选项是正确的函数定义？A. int function(int a) { return a; }B. int function(int a) { return a; }C. int function(int a) { return a; }D. int function(int a) { return a; }答案：A9. C语言中，以下哪个选项是正确的文件包含指令？A. #include <stdio.h>B. #include "stdio.h"C. #include <stdio.h>D. #include "stdio.h"答案：A10. 在C语言中，以下哪个选项是正确的宏定义？A. #define PI 3.14159B. #define PI "3.14159"C. #define PI 3.14159D. #define PI 3.14159答案：A二、填空题（每题2分，共20分）1. C语言中，用于声明一个整型变量的关键字是________。

《数据结构》部分一、简答题（10分，每题5分）1、数据元素之间的关系在计算机中的存储有几种表示方法？各有什么特点？（P6）解：数据元素之间的关系在计算机中有四种不同的表示方法：(1)顺序存储方法。

数据元素顺序存放，每个结点只含有一个元素。

存储位置反映数据元素间的逻辑关系。

存储密度大，但有些操作(如插入、删除)效率较差。

(2)链式存储方法。

每个结点除包含数据元素信息外还包含一组指针。

指针反映数据元素间的逻辑关系。

这种操作不要求存储空间连续，便于进行插入和删除等操作，但存储空间利用率较低。

另外，由于逻辑上相邻的数据元素在存储空间上不一定相邻，所以不能对其进行随机存取。

(3)索引存储方法。

除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表。

索引表中的索引指示结点的存储位置，兼有动态和静态特性。

(4)哈希(或散列)存储方法。

通过哈希函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将哈希函数的值作为该数据元素的存储地址。

其特点是存取速度快，只能按关键字随机存取，不能顺序存储，也不能折半存取。

2、对于堆排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其中哪种方法？其次选取哪种方法？若仅考虑排序结果的稳定性，则应该选取其中哪种方法？若仅从平均情况下排序最快这一点考虑，则应该选取其中哪些方法？（P289）答：若只从存储空间考虑，则应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；若只从排序结果的稳定性考虑，则应选取归并排序方法；若只从平均情况下最快考虑，则应选取快速排序方法；若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。

二、应用题（55分）1、证明：同一棵二叉树的所有叶子结点，在前序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同）。

（8分）（例如先序abc，后序bca，中序bac。

）(P128) 答：【答案】先序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。

数学11-1 C语言平时训练题1、算术基本运算Description计算两整数x和y（0<x,y<1000）的和、差、积、商、余数、x的平方和y的三次方。

Input输入只有一行。

Output输出为多行，按顺序每行输出x,y的和、差、积、商、余数、x的平方和y的三次方。

Sample Inputx = 11, y = 3Sample Outputx + y : 14x - y : 8x * y : 33x / y quotient: 3, remainder: 2x ^ 2 : 121y ^ 3 : 27Answer#include <stdio.h>int main(){int x,y,a,b,c,d,e,f,g;0<x<1000,0<y<1000;scanf("x = %d, y = %d",&x,&y);a=x+y;b=x-y;c=x*y;d=x/y;e=x%y;f=x*x;g=y*y*y;printf("x + y : %d\n",a);printf("x - y : %d\n",b);printf("x * y : %d\n",c);printf("x / y quotient: %d, remainder: %d\n",d,e);printf("x ^ 2 : %d\n",f);printf("y ^ 3 : %d\n",g);return 0;}2、求圆的面积和周长Description从键盘输入圆的半径，求圆的面积和周长，圆周率取3.14。

Input输入一个浮点型数据，有效数字不会超过十进制的6位。

Output输出为两行。

第一行为圆的面积，第二行为圆的周长，格式见sample。

Sample Input3Sample OutputArea: 28.260000Perimeter: 18.840000Answer#include<stdio.h>#define PI 3.14int main(){float r,s,c;scanf("%f",&r);s=PI*r*r;c=2*PI*r;printf("Area: %f\n",s);printf("Perimeter: %f\n",c);return 0;}3、平均值Description求3个数的平均值。

Problem A: Hello world! DescriptionXiao_ming有两个哥哥，大哥叫Da_min，二哥叫Er_min。

三兄弟放学回家，父母分别跟他们打招呼。

Input无Output请输出：Hello Da_min,Hello Er_min,Hello Xiao_ming!Sample InputSample OutputHello Da_min,Hello Er_min,Hello Xiao_ming!HINT请注意换行符#include <stdio.h>int main(){printf("Hello Da_min,\nHello Er_min,\nHello Xiao_ming!");}Problem A: 算术基本运算Description计算两整数x和y（0<x,y<1000）的和、差、积、商、余数、x的平方和y的三次方。

Input输入只有一行，格式见sample。

Output输出为多行，按顺序每行输出x,y的和、差、积、商、余数、x的平方和y的三次方，格式见sampleSample Inputx = 11, y = 3Sample Outputx + y : 14x - y : 8x * y : 33x / y quotient: 3, remainder: 2x ^ 2 : 121y ^ 3 : 27HINT注意输入输出格式。

了解C语言整数除法运算符的特点，并且没有求幂的运算符。

#include <stdio.h>int main(){int x,y;scanf ("x = %d, y = %d",&x,&y);printf ("x + y : %d\n",x+y);printf ("x - y : %d\n",x-y);printf ("x * y : %d\n",x*y);printf ("x / y quotient: %d, remainder: %d\n",x/y,x%y);printf("x ^ 2 : %d\n",x*x);printf ("y ^ 3 : %d\n",y*y*y);}Problem B: 求圆的面积和周长Description从键盘输入圆的半径，求圆的面积和周长，圆周率取3.14。