2019贵州大学831真题.docx

2019 贵州大学 831今年考的题目和大纲一致，并没有超纲！一、选择题（整体难度和往年真题最难那种选择题差不多，但还是有原题，大部分是改编过的）1. 有如下函数调用语句 func(rec1,rec2+rec3,(rec4,rec5),该函数调用语句中含有的实参个数是（ ）A. 2B. 3C. 4D. 52. 在一棵度为 3 的树中，有 2 个度为 3 的结点，1 个度为 2 的结点，3 个度为 1 的结点，问该树有多少叶子结点。3. 二维数组的引用（指针）。（2013 年第 12，14 题的改编）4. 单链表的删除。（将 2014 年选择题第 24 题插入改为删除）5. 循环队列入队的操作。6. 问下面选项中哪个算法的时间复杂度大于 O(log2n)。二、程序输出题1.2013 年阅读程序第一题2.2013 年阅读程序第二题（改编）3. 这题在网上找不到原题，所有我编了类似的题型（和原题是一个意思，只不过难度降了一个档次）如下：#include <stdio.h> int main () int x=0,i=0; for(i;x<=20;i+)x += 2;printf("x=%dni=%d",x,i); return 0;程序执行完后 x 和 i 的值为多少：x=22i=114. 这题在网上找不到原题，所有我编了类似的题型（和原题是一个意思，只不过难度降了一个档次）如下：#include <stdio.h> int main () int a20 = 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20;int *p = a;int *q = &a15; printf("%dn",*p);printf("%dn",*q); q = q+2; printf("%dn",*q); q = q-6; printf("%dn",*q);printf("%dn",*q+);return 0;程序运行的结果为：116181212三、简答题1. 写出操作线性结构的 5 种方法。2. 问实现树的深度优先和广度优先分别用什么数据结构作为辅助。3. 已知二叉树的先序遍历为 AB#CDE#F#,其中#表示 NULL，画出该二叉树。4. 已知待排序的一组数为 6,3,7,2,1,8,9.要求写出使用快速排序第一趟的结果， 选择排序第二趟的结果，简单插入排序第三趟的结果。5. 写出适用于二分查找的数据结构，并写出时间复杂度。四、算法编程题1. 猴子吃桃，猴子每天吃的桃是前一天的 2 倍加 1，猴子第一天吃了 1 个桃，问第五天吃了多少桃子。要求用递归的方式编程实现。2. 已知 abc+bca=1123，其中 a,b,c 是 0-9 的单个数字，编程打印输出 a,b,c 的值。3. 已知一个带权有向图，要求用 Prim 算法并以 A 顶点为起始点，画出加入第 4 条边后的图。（不要求编写代码，图不画了，和往年真题差不多）.4. 写出二叉搜索树的查找-递归算法（2015 年完善程序题的第三题）5. 已知 A 为一个二维数组，里面有 5 个字符串，要求使用合并排序算法对这 5 个字符串进行排序，其中有一个二维数组 B 作为辅助数组。题目提示可以使用 C 语言自带的两个函数：strcmp(),strcpy()；