华科2018年笔试题大概

着重学习知识点，写伪代码的基础规则

数据库：

1.画E-R图

3个重点：属性，实体、联系

2.判断一个函数依赖是否存在

如果x->y,则求x的闭包，看里面是否包含y

具体步骤:找出F中左部属于X的部分，将其右部加入X，如此循环直至X=U或者不发生改变即可。

3.SQL语句

多练习

4.关系代数表达式

如果是第二章内容，记住选择、投影、连接、笛卡尔积符号以及连接、除用基本运算表示。

如果是第九章内容，记下几个优化规则：先选择再投影，选择、投影与二目运算符的交换，以及等价表达式

算法设计：

1.动态规划

题目描述不清楚。

最优子结构证明：反证法

遗漏知识点：如何写伪代码

赋值：←

变量：不用声明，可在注释中说明

数组：A[1…n]

选择结构：if（条件）then（block1）else（block2）if-then-else

循环：

while c do 
s
end
或者
for 变量←初值 to 终值 步长 do
s
end

参数赋值：参数采用按值传递方式，即在被调用过程中的赋值x←y对主调过程来说是不可见的。但是，赋值f[x] = 3却是可见的。

指令：可以用文字表示某个操作

2.找出数组中出现次数大于数组一般大小的那个数

search（A,n）//A[1...n]是数组，n为大小
m←A[1]
num←1
p←0
for i←2 to n 1 do   
if num==0
then m←A[1]
else if m==A[i]
then num++
else num--
if num
then for i←1 to n 1 do
if A[i]==m
then p++
if p>n/2
return m
return -1

这个伪代码时间复杂度是n，空间复杂度1

如果用hash算法是n，n

一个一个找就是n²，1了