数据结构考研分类复习真题 第一章 答案[7]

struct node

{int yearmonthday; };

typedef struct

{int num;//帐号

char name[];//姓名

struct node date;//开户年月日

int tag;//储蓄类型如 零存 一年定期……

float put;//存入累加数

float interest;//利息

float total;//帐面总数

}count

．()n ()n+ ()n ()(n+)(n)/ ()(n+)(n)/ ()n

这是一个递归调用因k的初值为由语句（）知每次调用k增故第()语句执行n次（）是FOR循环语句在满足()的条件下执行该语句进入循环体()n次加上最后一次判断出界故执行了n+次()也是循环语句当k=时判断n+次（进入循环体()n次）k=时判断n次最后一次k=n时判断次故执行次数是（n+）+n+…+=(n+)(n)/次语句()是()的循环体每次比()少一次判断故执行次数是n+(n)+…+=(n+)(n)/次注意分析时不要把()分析成n次更不是次

． （这时i= s=） REPEAT语句先执行循环体后判断条件直到条件为真时退出循环

．算法在最好情况下即二进制数的最后一位为零时只作一次判断未执行循环体赋值语句A[i]执行了一次最坏情况出现在二进制数各位均为（最高位为零因题目假设无溢出）这时循环体执行了n次时间复杂度是O(n)循环体平均执行n/次时间复杂度仍是O(n)

．该算法功能是将原单循环链表分解成两个单循环链表其一包括结点h到结点g的前驱结点另一个包括结点g到结点h的前驱结点时间复杂度是O(n)

[] [] [] [] [] [] [] [] []