2018年浙江理工大学938数据结构与数据库技术考研专业课真题分享.pdf
第 1 页 , 共 7 页浙 江 理 工 大 学2018 年 硕 士 研 究 生 招 生 考 试 初 试 试 题考 试 科 目 : 数 据 结 构 与 数 据 库 技 术 代 码 : 938( 请 考 生 在 答 题 纸 上 答 题 , 在 此 试 题 纸 上 答 题 无 效 )第 一 部 分 : 数 据 结 构 ( 本 部 分 共 90 分 )一 、 单 项 选 择 题 ( 每 小 题 3 分 , 本 题 共 36 分 )1. 下 列 程 序 段 所 代 表 的 算 法 的 时 间 复 杂 度 为 。i=1;while(irear-next=HQ-front (B)HQ-front-next=HQ-rear(C)HQ-front=HQ-rear (D)HQ-front-next=HQ-rear-next5. 在 一 个 栈 顶 指 针 为 HS的 链 栈 中 插 入 一 个 *s结 点 时 , 应 执 行 的 操 作 为 。(A)HS-next=s;s-next=HS-next; (B)s-next=HS-next; HS-next=s;(C)s-next=HS; HS=s; (D)s-next=HS; HS=HSnext;6. 有 一 组 数 值 13, 21, 32, 17, 26, 用 以 构 造 哈 夫 曼 树 , 则 其 带 权 路 径 长 度 WPL值 为 。(A)241 (B)248 (C)252 (D)2707. 假 设 结 点 序 列 为 50,30,90,60,95,70,48,18, 以 此 构 成 一 棵 二 叉 排 序 树 , 则 在该 二 叉 排 序 树 上 查 找 一 个 结 点 的 平 均 查 找 长 度 为 。(A)11/4 (B)21/4 (C)19/8 (D)5/28. 假 定 对 共 有 144个 元 素 的 线 性 表 进 行 分 块 查 找 , 若 将 表 均 匀 地 分 为 x块 ( 每 块 元素 个 数 相 同 ) 。 假 设 块 查 找 和 块 内 查 找 均 采 用 顺 序 查 找 法 , 则 在 等 概 率 情 况 下 ,若 要 使 分 块 查 找 的 平 均 查 找 长 度 ASL最 小 , 则 分 块 数 x的 值 应 为 。(A)11 (B)12 (C)13 (D)149. 已 知 一 个 带 权 图 的 顶 点 集 V 和 边 集 G 分 别 如 下 , 则 该 图 的 最 小 生 成 树 的 权 值为 。第 2 页 , 共 7 页V=1, 2, 3, 4, 5, 6, 7, 8;E=(3,1)6, (3,4)7, (3,7)5, (1,2)3, (1,4)4, (4,7)8, (4,5)4, (7,8)5, (2,6)3,(2,5)5, (5,8)8, (5,6)5, (8,6)6,(A)24 (B)29 (C)30 (D)3110.当 待 排 序 的 关 键 字 个 数 n 很 小 , 且 初 始 排 列 为 逆 序 时 , 采 用 下 列 排 序 方 法 中的 , 算 法 的 时 间 复 杂 度 最 小 。(A)直 接 插 入 排 序 (B)简 单 选 择 排 序 (C)冒 泡 排 序 (D)快 速 排 序11.已 知 一 个 待 散 列 存 储 的 线 性 表 17,80,56,34,26,75,67,51,93, 散 列 函 数 为h(k)=k%11, 散 列 地 址 空 间 为 010。 若 采 用 线 性 探 查 法 解 决 冲 突 , 则 平 均 查 找 长度 为 。(A)4/3 (B)13/9 (C)17/9 (D)19/912.已 知 一 组 记 录 的 关 键 字 值 为 46,74,18,53,14,20,40,38,86, 按 快 速 排 序 方 法 对该 序 列 进 行 一 趟 排 序 后 的 结 果 是 。(A)38,14,18,20,40,46,53,74,86 (B)38,40,18,20,14,46,53,74,86(C)14,20,40,38,18,46,74,53,86 (D)18,14,20,40,38,46,74,53,86二 、 程 序 填 空 题 ( 每 个 空 格 2 分 , 本 题 共 24 分 )1. 下 列 程 序 是 将 两 个 有 序 的 单 链 表 lnode1和 lnode2合 并 成 一 个 依 然 有 序 的 单 链 表 ,试 在 下 列 空 白 处 填 入 正 确 语 句 。typedefstructnodeintdata; /数 据 域structnode*next; /指 针 域linklist;voidsort(linklist*lnode1,linklist*lnode2)linklist*p1,*p2,*tmp;p1=lnode1;p2= (1) ;while(p1-next!=nullp2-next=p1-next;(3) =p2;p2=tmp;elsep1=p1-next;if(p2!=null) (4) ;第 3 页 , 共 7 页2. 下 列 程 序 在 单 链 表 head上 实 现 简 单 选 择 排 序 算 法 , 其 中 调 用 函 数 GetMinKey, 试在 下 列 空 白 处 填 入 正 确 语 句 。typedefstructnodeintdata; /数 据 域structnode*next; /指 针 域linklist;linklistGetMinKey(linklistr)linklistminp; /minp是 较 小 值 的 指 针minp=r;while(r-next!=null)if(minp-datar-next-data) minp=r-next;r=r-next;returnminp;/返 回 较 小 值 的 指 针voidSelectSort(linklisthead)linklistq,p=head-next;inttemp;for(;p-next!=NULL;p=p-next)(5) =GetMinKey( (6) );if(p-data!=q-data)temp=p-data;( 7) ;( 8) ;3. 已 知 二 叉 排 序 树 的 根 节 点 为 t, 左 孩 子 和 右 孩 子 分 别 为 lch 和 rch。 下 列 程 序 将 一个 结 点 x插 入 到 二 叉 排 序 树 中 , 试 在 下 列 空 白 处 填 入 正 确 语 句 。typedefstructnodeintdata;structnode*lch,*rch;snode;snode*insert(snode*t,intx)snode*p,*q,*s;s=(snode*)malloc(sizeof(snode);第 4 页 , 共 7 页s-data=x;if(t=null) (9) ;elsep= (10) ;while(p!=null)q=p;if( (11) ) p=p-lch;elsep=p-rch;if( (12) ) q-lch=x;else q-rch=x;return(t);三 、 程 序 设 计 题 ( 本 题 30 分 , 任 选 2 小 题 解 答 , 每 小 题 15 分 , 按 得 分最 高 的 2 小 题 计 分 )1. 已 知 一 颗 二 叉 树 的 根 节 点 为 t, 其 二 叉 链 表 存 储 结 构 定 义 如 下 。 试 编 写 程 序 , 按 照中 序 遍 历 非 递 归 算 法 , 计 算 x这 个 结 点 ( 数 值 域 为 x) 之 后 输 出 的 其 它 结 点 的 个 数 。typedefstructnodeintdata; /数 值 域structnode*lch,*rch;tnode;这 里 , data为 结 点 数 值 域 , lch为 结 点 的 左 孩 子 , rch为 结 点 的 右 孩 子 。2. 已 知 一 个 线 性 表 以 单 链 表 结 构 存 储 , 单 链 表 的 头 指 针 为 head, 结 点 结 构 定 义 如 下 :typedefstructnode intdata; /数 值 域structnode*next;lnode;试 将 该 单 链 表 中 所 有 的 奇 数 排 在 所 有 偶 数 之 前 。 要 求 时 间 复 杂 度 尽 可 能 地 少 , 结 果仍 放 在 原 来 的 单 链 表 中 。3. 设 哈 希 函 数 为 HT, 解 决 冲 突 的 方 法 为 外 链 地 址 法 , 哈 希 函 数 采 用 除 留 余 数 法 (k%p,k为 待 删 除 的 关 键 字 , p为 小 于 基 本 哈 希 表 容 量 m的 质 数 )。 若 哈 希 表 中 某 个 位 置 上的 key域 值 为 零 , 则 表 示 该 位 置 未 被 占 用 。 试 编 写 程 序 , 实 现 从 用 哈 希 表 中 删 除 关键 字 k的 算 法 。第 5 页 , 共 7 页第 二 部 分 : 数 据 库 技 术 ( 本 部 分 共 60 分 , 每 小 题 10 分 。 任 选 6 小题 解 答 , 按 得 分 最 高 的 6 小 题 计 分 , 本 部 分 合 计 得 分 不 超 过 60 分 )数 据 库 Sales用 来 存 放 某 企 业 销 售 数 据 , 它 有 4张 表 , Products表 用 来 存 储 商 品信 息 , Customers表 用 来 存 储 客 户 信 息 , Orders表 用 来 存 储 订 单 信 息 , OrderItems表用 来 存 储 订 单 明 细 信 息 , 各 表 结 构 如 下 :1 Products表 结 构 :列 名 类 型 长 度 规 则 中 文 说 明ProductID 数 值 型 8 主 键 商 品 编 码ProductName 字 符 型 30 非 空 商 品 名 称Category 字 符 型 20 非 空 商 品 类 别QuantityPerUnit 字 符 型 20 非 空 规 格 型 号UnitPrice 数 值 型 8,2 成 本 单 价Products表 记 录 举 例 :ProductID ProductName Category QuantityPerUnit UnitPrice1 Chai Beverages 10boxesx20bags 18.202 Chang Condiments 2412ozbottles 19.503 AniseedSyrup Condiments 12550mlbottles 10.254 ChefAntonsGumboMix Beverages 36boxes 21.35 14 Tofu Produce 40-100gpkgs 23.25 77 EscargotsdeBourgogne Seafood 24pieces 13.252 Customers表 结 构 :列 名 类 型 长 度 规 则 中 文 说 明CustomerID 字 符 型 5 主 键 客 户 编 码CustomerName 字 符 型 50 非 空 客 户 名 称Country 字 符 型 20 客 户 所 在 国 家City 字 符 型 20 客 户 所 在 城 市Address 字 符 型 80 客 户 地 址Customers表 记 录 举 例 :CustomerID CustomerName Country City AddressALFKI AlfredsFutterkiste Germany Berlin ObereStr.57ANATR AnaTrujilloEmparedadosyhelados Mexico MexicoD.F. Avda.delaConstitucion2222ANTON AntonioMorenoTaqueria Mexico MexicoD.F. Mataderos 2312AROUT AroundtheHorn UK London 120HanoverSq.第 6 页 , 共 7 页BERGS Berglundssnabbkop Sweden Luleo Berguvsvogen8BLAUS BlauerSeeDelikatessen Germany Mannheim Forsterstr.57BLONP Blondesddslpreetfils France Strasbourg 24,placeKleberBOLID BolidoComidaspreparadas Spain Madrid C/Araquil,67BONAP Bonapp France Marseille 12,ruedesBouchersBOTTM Bottom-DollarMarkets Canada Tsawassen 23TsawassenBlvd. 3 Orders表 结 构 :列 名 类 型 长 度 规 则 中 文 说 明OrderID 数 值 型 8 主 键 订 单 编 号CustomerID 字 符 型 5 非 空 , 外 键 客 户 编 码OrderDate 日 期 型 8 非 空 订 单 日 期RequiredDate 日 期 型 8 要 货 日 期ShippedDate 日 期 型 8 发 货 日 期Orders表 记 录 举 例 :OrderID CustomerID OrderDate RequiredDate ShippedDate10248 VINET 2009-07-04 2009-08-01 2009-08-1610249 TOMSP 2009-07-05 2009-08-16 2009-08-1610250 HANAR 2009-08-08 2009-09-05 2009-09-0710251 VINET 2009-08-11 2009-09-15 2009-09-12 4 OrderItems表 结 构 :列 名 类 型 长 度 规 则 中 文 说 明OrderID 数 值 型 8 外 键 订 单 编 号ProductID 数 值 型 8 外 键 商 品 编 码UnitPrice 数 值 型 8,2 两 位 小 数 , 单 价 大 于 0 销 售 单 价Quantity 数 值 型 8 非 空 , 默 认 为 0 销 售 数 量Amount 数 值 型 12,2 计 算 列 ( =unitprice*quantity) 销 售 额OrderItems表 记 录 举 例 :OrderID ProductID UnitPrice Quantity Amount10248 11 14 12.5 175.0010248 42 9 10.4 93.6010248 72 34 5.6 190.4010249 14 18 9.5 171.0010249 51 42 40.45 1698.9010250 41 7 10.25 71.7510250 51 42 35.25 1480.50 第 7 页 , 共 7 页试 编 写 SQL语 句 , 完 成 以 下 各 项 功 能 ( 注 : 必 要 时 一 个 小 题 可 以 用 多 条 语 句 去实 现 )1) 根 据 订 单 明 细 表 ( OrderItems) 结 构 , 在 该 表 中 插 入 一 条 记 录 , 各 列 数 值 如 下 。注 意 : 这 里 有 些 列 是 不 能 赋 值 的 。2) 将 商 品 表 中 价 格 最 低 的 前 20%个 商 品 涨 价 25%。3) 检 索 哪 些 商 品 的 名 称 中 包 含 “ to” 这 个 字 符 串 而 且 其 单 价 超 过 所 有 商 品 单 价 的平 均 值 。4) 从 Condiments 类 商 品 中 随 机 提 取 一 个 商 品 , 计 算 2008年 这 个 商 品 的 销 售 额 在 同类 商 品 中 的 排 名 名 次 。5) 统 计 检 索 2008 年 度 哪 些 客 户 的 销 售 额 超 过 Around the Horn 这 个 客 户 销 售 额 的1.5倍 。6) 统 计 检 索 哪 些 客 户 购 买 tofu 这 个 商 品 的 金 额 最 多 , 要 求 查 询 结 果 中 包 含 客 户 名称 。7) 统 计 2008 年 哪 些 客 户 购 买 了 tofu 这 个 商 品 但 没 有 购 买 longlife tofu 这 个 商品 。8) 创 建 一 个 存 储 过 程 , 从 订 单 表 中 提 取 检 索 其 中 的 一 部 分 记 录 , 例 如 从 订 单 表 的 第51行 开 始 提 取 后 面 的 10行 记 录 。 要 求 输 入 两 个 整 数 start和 limit, 检 索 订 单表 中 从 start 行 开 始 的 后 limit 行 记 录 ( 提 示 : 可 以 使 用 not in 或 排 名 函 数rownumber())