usst大学生程序设计竞赛算法基础考试题2020年

题型包括
选择题 15*2=30
程序论述题 10+10
程序填空题 10
程序编程题3道 10+15+15=40

选择题

1.散列表查找的时间复杂度
散列表平均查找时间复杂度O(1)，因为散列表是基于数组的。
2 二叉树的度的概念
度为2 就是有2个孩子结点的结点
3 迪杰斯特拉算法用于求解什么问题
求最短路
4 for(int i=0,j=10;i=j=10;i++,j–)运行次数
无穷次
5 给出阶乘的递归函数，让求fact(4)
10
6 算法的时间复杂度由什么决定？
数据规模
7 下列运算符的运算数需要是整数的是 % ! 等等
%
8 动态规划问题，给出4个递推关系，说出哪个是无解的dp
其他题目遗忘，但是比较基础。

程序论述题
1 请谈一谈贪心算法和动态规划的联系和区别
2 二分法求方程的根，写出算法思路
这是上课例题。
这是上课例题

程序填空题
水仙花数 (位于100~999) 的立方和等于多少 ，使用三重循环，分别遍历百位、十位和个位，求出各个水仙花数，并且求各位的立方和。

程序编程题

1.与7无关的数
这是上课例题。

2 贪心
一辆车承重 w，最多承载2个人。给出n个学生和体重，问最少需要几辆车。如果有装不下的，输出-1.
我的解答:
如果有 大于w的体重，直接输出-1.
在不超重的情况下，从小到大排序。尽可能地让2个人一起上车，最小的体重和最大的体重(双指针).不能的话，让右指针左移。如果最小的体重都不能配对的话，说明只能每个人一辆车。

这个思路最终ac

3 bfs求最短路。 平地用空格表示，高山用x表示，起点是S，终点是E，求最短路，路径可以离开地图，也就是说地图外面一圈也可以走。
比如

3 3
xSx
Exx
x空格x

本题数据有点水。
问题出在：空格不会读入。