第1 章 绪论 5.选择题:CCBDCA 6.试分析下面各程序段的时间复杂度。 (1)O(1) (2)O(m*n) (3)O(n2) (4)O(log3n) (5)因为x++共执行了n-1+n-2+……+1= n(n-1)/2,所以执行时间为O(n2) (6)O(n ) 第2 章 线性表 1.选择题 babadbcabdcddac 2.算法设计题 (6)设计一个算法,通过一趟遍历在单链表中确定值最大的结点。 ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; //假定第一个结点中数据具有最大值 p=L->next->next; while(p != NULL ){//如果下一个结点存在 if(p->data > pmax->data) pmax=p; p=p->next; } return pmax->data; (7)设计一个算法,通过遍历一趟,将链表中所有结点的链接方向逆转,仍利用原表的存储空间。 void inverse(LinkList &L) { // 逆置带头结点的单链表 L p=L->next; L->next=NULL; while ( p) { q=p->next; // q 指向*p 的后继 p->next=L->next; L->next=p; // *p 插入在头结点之后 p = q; } } ( 10) 已 知 长 度 为 n 的 线 性 表 A 采 用 顺 序 存 储 结 构 , 请 写 一 时 间 复 杂 度 为 O(n)、 空 间复 杂 度 为 O(1)的 算 法 , 该 算 法 删 除 线 性 表 中 所 有 值 为 item 的 数 据 元 素 。 [题 目 分 析 ] 在 顺 序 存 储 的 线 性 表 上 删 除 元 素 , 通 常 要 涉 及 到 一 系 列 元 素 的 移 动 ( 删 第i 个 元 素 , 第 i+1 至 第 n 个 元 素 要 依 次 前 移 )。 本 题 要 求 删 除 线 性 表 中 所 有 值 为 item 的 数 据元 素 , 并 未 要 求 元 素 间 的 相 对 位 置 不 变 。 因 此 可 以 考 虑 设 头 尾 两 个 指 针 ( i=1, j=n), 从 两端 向 中 间 移 动 , 凡 遇 到 值 item 的 数 据 元 素 时 , 直 接 将 右 端 元 素 左 移 至 值 为 item 的 数 据 元 素位 置 。 void Delete( ElemType A[ ], int n) ∥ A 是 有 n 个 元 素 的 一 维 数 组 , 本 算 法 删 除 A 中 所 有 值 为 item 的 元 素 。 {i=1; j=n; ∥ 设 置 数 组 低 、 高 端 指 针 ( 下 标 )。 while(...