首页写一个C语言程序实现给定标识符集(a 1 , a 2 , …a n )，这些字符的下标从1开始按自然序编号，p i 是对a i 成功检索的概率, q i 是不成功检索的概率, 且∑ (1<=i<=n) p i +∑ (0<=i<=n) q i =1，问:它的最优二分检索树是怎样的？输入格式: 第1行是n，表示字符个数；第2行是这n个字符的成功检索概率p i , 0<p i <1; 第3行是失败检索概率q i ，0<q i <1，且∑ (1<=i<=n) p i +∑ (0<=i<=n) q i =1。输出格式: 最优二分检索树先根遍历时得到的字符编号序列。输入样例1: 4 0.1875 0.1875 0.0625 0.0625 0.125 0.1875 0.0625 0.0625 0.0625 输出样例1: 2 1 3 4

写一个C语言程序实现给定标识符集(a 1 , a 2 , …a n )，这些字符的下标从1开始按自然序编号，p i 是对a i 成功检索的概率, q i 是不成功检索的概率, 且∑ (1<=i<=n) p i +∑ (0<=i<=n) q i =1，问:它的最优二分检索树是怎样的？输入格式: 第1行是n，表示字符个数；第2行是这n个字符的成功检索概率p i , 0<p i <1; 第3行是失败检索概率q i ，0<q i <1，且∑ (1<=i<=n) p i +∑ (0<=i<=n) q i =1。输出格式: 最优二分检索树先根遍历时得到的字符编号序列。输入样例1: 4 0.1875 0.1875 0.0625 0.0625 0.125 0.1875 0.0625 0.0625 0.0625 输出样例1: 2 1 3 4

时间: 2024-04-22 20:23:05 浏览: 151

C语言程序设计试卷A （3学分）.doc

【C语言程序设计试卷概述】 C语言是一种强大的编程语言，被广泛用于系统开发、软件工程、嵌入式系统以及各种应用程序的编写。本试卷“C语言程序设计试卷A （3学分）.doc”旨在测试学生对C语言基础知识的掌握程度，包括语法、逻辑和编程实践能力。 1. C语言的标识符规则： C语言中的标识符是用来命名变量、函数等的符号，必须以字母或下划线开头，后续可以是字母、数字或下划线。选项A) _1a 符合此规则，而B) 2a_ 以数字开头，C) do 是保留字，D) a.12 包含非法字符点号，所以A)是正确的自定义标识符。 2. 温氏转换表达式：根据题意，温度华氏转摄氏的公式为 C = (F - 32) * 5 / 9。正确表达式是C)，即C=5/9*(F-32)，因为C++中的除法运算符(/)对于整数操作数会进行整数除法，但在这里需要浮点数结果，因此需要使用括号确保先执行减法。 3. 浮点数输入：在C语言中，使用`scanf`函数读取浮点数时，应使用`%f`格式说明符。正确选项是C)，即`scanf("%f",&x)`，这会将输入的浮点数存储在变量x的内存地址中。 4. 程序执行起点： C程序的执行始终从`main()`函数开始，直到`main()`函数执行完毕。所以正确答案是A)。 5. 判断字符是否为数字：在C语言中，字符型变量可以用字符常量进行比较。正确表达式是D)，即`c1>='0'&&c1<='9'`，这样可以判断字符变量c1是否在'0'到'9'的范围内。 6. `switch`语句的表达式类型： `switch`语句的表达式可以是整型或字符型。所以正确答案是C)，即`int, char`。 7. 循环计算：题目中的嵌套循环在结束时，外层循环会执行5次，内层循环在每次外层循环中执行4次，因此x的最终值是20。答案是B)。 8. 条件循环与分支：这个循环结构涉及`break`和`continue`，当x达到10时跳出循环，所以y的最终值是5，选项A)正确。 9. 数组赋值：数组元素的赋值可以是整数、字符等。错误的赋值是B)，`scanf("%c",a[3]);`，因为`%c`格式说明符用于读取字符，不能用于读取整数，且数组名加下标后是一个地址，不能直接接收`%c`的输入。 10. 数组作为函数参数：传数组给函数时，实际上是传递了数组的首地址，所以A)正确。 11. 多维数组初始化：对于`int a[2][3]={{1},{2,3}};`，a[1][1]的值是2，因此C)正确。 12. 数组初始化：当初始化数组时，如果只给出了部分元素的值，剩余元素会被自动设置为0。所以A)是正确的，b[8]的值为0。 13. 函数调用：函数调用可以在不同的语境中使用，如作为独立语句、表达式的一部分、函数参数等。D)是错误的，因为函数调用可以被替换为非递归算法。 14. 全局变量的作用域：全局变量在整个源文件内有效，从定义位置开始到文件结束。所以A)是正确答案。 15. 全局变量作用域的范围：全局变量的作用域限于定义它的源文件，不包含其他源文件，因此A)正确。 16. 输出数组：给定程序将输出数组的倒序，从第三行的第三个元素开始，逆时针打印，结果是B) 357。 17. 指针赋值：指针变量p指向浮点数m的正确赋值语句是B)，即`p=&m;`，这将使p指向m的内存地址。以上是对试卷中部分选择题知识点的详细解析，涵盖了C语言的基本概念，如变量、运算符、控制结构、数组、函数、指针以及输入输出等。通过这些题目，可以看出C语言学习的重点在于理解和应用其核心语法以及逻辑思维能力。

这是一道经典的动态规划问题，可以使用动态规划算法求解。具体思路如下：定义 $w(i,j)$ 表示从$i$到$j$的权值和，$e(i,j)$ 表示最优的二叉树的期望搜索代价，$root(i,j)$ 表示从$i$到$j$的最优根结点。对于一个区间 $[i,j]$ 中的每一个$k$，都可以将其作为根结点，然后计算期望搜索代价。显然，$e(i,j)$ 的计算需要依赖 $w(i,j)$ 和 $e(i,k-1)$，$e(k+1,j)$ 以及 $p_k$ 和 $q_k$。因此，可以使用动态规划算法计算 $w$ 和 $e$。具体实现时，可以先预处理出 $w$ 数组，然后根据 $w$ 数组求解 $e$ 和 $root$ 数组，最后根据 $root$ 数组输出序列。 C++代码如下：

阅读全文