严蔚敏数据结构课后习题及答案解析.pdf

第 一 章 绪 论一、选择题1.组 成 数 据 的 基 本 单 位 是（)（A）数 据 项（B）数据类型（C）数 据 元 素（D）数据变量2.数 据 结 构 是 研 究 数 据 的（）以及它们之间 的 相 互 关 系。（A）理 想 结 构，物理结构（B）理 想 结 构，抽象结构（C）物 理 结 构，逻辑结构（D）抽 象 结 构，逻辑结构3.在 数 据 结 构 中，从 逻 辑 上 可 以 把 数 据 结 构 分 成（）（A）动 态 结 构 和 静 态 结 构（B）紧凑结构和非紧凑结构（C）线 性 结 构 和 非 线 性 结 构（D）内部结构和外部结构4.数 据 结 构 是 一 门 研 究 非 数 值 计 算 的 程 序 设 计 问 题 中 计 算 机 的（）以 及 它 们 之 间 的（）和 运 算 等 的 学 科。（A）数 据 元 素（B）计 算 方 法（C）逻 辑 存 储（D）数据映像（A）结构（B）关系（C）运算（D）算法5.算 法 分 析 的 目 的 是（）。（A）找 出 数 据 结 构 的 合 理 性（B）研究算法中的输入和输出的关系（O分 析 算 法 的 效 率 以 求 改 进（D）分析算法的易懂性和文档性6.计 算 机 算 法 指 的 是（），它 必 须 具 备 输 入、输 出 和（）等5个特 性。（A）计算 方 法（B）排 序 方 法（C）解 决 问 题 的 有 限 运 算 序 列（D）调度方法（A）可 执 行 性、可 移 植 性 和 可 扩 充 性（B）可 行 性、确定性和有穷性（C）确 定 性、有 穷 性 和 稳 定 性（D）易 读 性、稳定性和安全性二、判断题1.数 据 的 机 内 表 示 称 为 数 据 的 存 储 结 构。（）2.算 法 就 是 程 序。（）3.数 据 元 素 是 数 据 的 最 小 单 位。（）4.算 法 的 五 个 特 性 为：有 穷 性、输 入、输 出、完 成 性 和 确 定 性。（）5.算 法 的 时 间 复 杂 度 取 决 于 问 题 的 规 模 和 待 处 理 数 据 的 初 态。（）三、填空题1.数据逻辑 结 构 包 括 _ _、_ _、.和 四种类型，其中树形结构和图形结构合称为_ _ _ _ _。2.在 线 性 结 构 中，第 一 个 结 点 前 驱 结 点，其 余每个结点有且只有_ _ _ _个 前 驱 结 点；最后一 个结点_ _ _ _ _ _ _ 后 续 结 点，其 余每个结点有且只有_ _ _ _ _ _ _ _ 个 后 续 结 点。3.在 树 形 结 构 中，树根结点没有_ _ _ _ _ _ 结点，其 余每个结点有且只有_ _ _ _ _ _ _ _ 个 前 驱 结 点；叶子结点没有_ _ _ _ _ _ _ _ _ 结点，其余每个结点的后续结点可以 _ _ _ _ _ _ _o4.在 图 形 结 构 中，每 个 结 点 的 前 驱 结 点 数 和 后 续 结 点 数 可 以 _ _ _ _ _ _ _ _。5.线性结构中元素之间存在_ _ _ _ _ _ _关系，树形结构中元素之间存在_ _ _ _ _ _ _ 关 系，图形结构中元素之间存在_ _ _ _ _ _ _ _ 关 系。6.算法的五个重要特性是_ _ _ _ _ _、_ _ _ _ _ _ _ _、_ _ _ _ _ _ _、_ _ _ _ _ _ _ _、_ _ _ _ _ _ _ _。7.数据结构的三要素是指_ _ _ _ _、_ _ _ _ _ _ _ _和_ _ _ _ _ _ _ _ _。8.链 式 存 储 结 构 与 顺 序 存 储 结 构 相 比 较，主要优点是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。9.设 有 一批数据 元 素，为 了 最 快 的 存 储 某 元 素，数据结构宜用_ _ _ _ _ _ _ _ 结 构，为了方便插入一个元素，数据结构宜用_ _ _ _ _ _ _ _ _ _ _ _ _ _ 结 构。四、算法分析题1.求下列算法段的语句频度及时间复杂度参 考 答 案：一、选择题1.C 2.C 3.C 4.A、B 5.C 6.C、B二、判 断 题：1、J 2、X 3、X 4、义 5、J三、填空题1、线 性、树 形、图 形、集 合？；非 线 性（网 状）2、没 有；1；没 有；1 3、前 驱；1;后继;任 意 多 个4、任 意 多 个5、一对 一；一对 多；多 对 多6、有 穷 性；确 定 性；可 行 性；输 入；输 出7、数 据 元 素；逻 辑 结 构；存 储 结 构8、插 入、删 除、合 并 等 操 作 较 方 便9、顺序存储;链式存者四、算法分析题f o r (i =l;i =n;i+)f o r(j=1;j=i;j+)x=x+1;分 析：该 算 法 为 一 个二重循 环，执 行 次 数 为 内、外 循 环 次 数 相 乘，但 内 循 环 次 数 不 固 定，与外 循 环 有 关，因 些，时 间 频 度T(n)=l+2+3+n=n*(n+l)/2有l/4W T(n)/n2W l,故 它 的 时 间 复 杂 度 为0 (n2),即T (n)与n 2数 量 级 相 同。2、分析下列算法段的时间频度及时间复杂度f o r (i=l;i=n;i+)f o r (j=l;j ne x t=p;p-ne x t=s;(B)s-ne x t=p-ne x t;p-ne x t=s;(C)s-ne x t=p-ne x t;p=s;(D)p-ne x t=s;s-ne x t=p;5.在 一 个 单 链 表 中，若 删 除p所 指 结 点 的 后 续 结 点，则 执 行()(A)p-ne x t=p-ne x t-ne x t;(B)p=p-ne x t;p-ne x t=p-ne x t-ne x t;(C)p-ne x t=p-ne x t;(D)p=p-ne x t-ne x t;6.下 列 有 关 线 性 表 的 叙 述 中，正 确 的 是()(A)线性表中的元素之间隔是线性关系(B)线性表中至少有一个元素(C)线 性 表 中 任 何 一 个 元 素 有 且 仅 有 个 直 接 前 趋（D）线性表中任何一个元素有且仅有一个直接后继7.线 性 表 是 具 有n个（）的 有 限 序 列（nW O）（A）表 元 素（B）字符（C）数据元素（D）数据项二、判断题1.线 性 表 的 链 接 存 储，表 中 元 素 的 逻 辑 顺 序 与 物 理 顺 序 一 定 相 同。（）2.如 果 没 有 提 供 指 针 类 型 的 语 言，就 无 法 构 造 链 式 结 构。（）3.线 性 结 构 的 特 点 是 只 有 一 个 结 点 没 有 前 驱，只 有 一 个 结 点 没 有 后 继，其余的结点只有一个前 驱 和 后 继。（）4.语 句p=p-ne x t完 成 了 指 针 赋 值 并 使p指针得到了 p指 针 所 指 后 继 结 点 的 数 据 域 值。（）5.要 想 删 除p指 针 的 后 继 结 点，我 们 应 该 执 行q=p-ne x t ；p-ne x t=q-ne x t；f r e e （q）（）三、填空题1 .已 知P为 单 链 表 中 的 非 首 尾 结 点，在P结 点 后 插 入S结 点 的 语 句 为：2.顺 序 表 中 逻 辑 上 相 邻 的 元 素 物 理 位 置（）相 邻，单链表中逻辑上相邻的元素物理位置_ _ _ _ _ _ _ _ _ _相 邻。3.线 性 表 匕=（a l,a 2,a n）采 用 顺 序 存 储，假 定 在 不 同 的n+1个位置上插入的概率相 同，则 插入一个新元素平均需要移动的元素个数是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _4.在 非 空 双 向 循 环 链 表 中，在 结 点q的 前 面 插 入 结 点p的 过 程 如 下：p-pr io r=q-pr io r;q-pr io r-ne x t=p;p-ne x t=q;5.已 知L是 无 表 头 结 点 的 单 链 表，是从 下 列 提 供 的 答 案 中 选 择 合 适 的 语 句 序 列，分别实现:（1）表 尾 插 入s结点的语句序列是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _（2）表 尾 插 入s结点的语句序列是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _1.p-nex t=s;2.p=L;3.L=s;4.p-nex t=s-nex t;5.s-nex t=p-nex t;6.s-nex t=L;7.s-nex t=nu l 1;8.w h i l e(p-nex t!=Q)?p=p-nex t;9.w h i l e(p-nex t!=nu l 1)p=p-nex t;四、算 法 设计题1.试 编 写 一 个 求 已 知 单 链 表 的 数 据 域 的 平 均 值 的 函 数(数 据 域 数 据 类 型 为 整 型)。2.已 知 带 有 头 结 点 的 循 环 链 表 中 头 指 针 为h ea d,试 写 出 删 除 并 释 放 数 据 域 值 为x的所有结点的c函 数。3.某 百 货 公 司 仓 库 中 有 一 批 电 视 机，按 其 价 格 从 低 到 高 的 次 序 构 成 一 个 循 环 链 表，每个结点有 价 格、数 量 和 链 指 针 三 个 域。现 出 库(销 售)m台 价 格 为h的 电 视 机，试编写算法修改原链 表。4.某 百 货 公 司 仓 库 中 有 一 批 电 视 机，按 其 价 格 从 低 到 高 的 次 序 构 成 一 个 循 环 链 表，每个结点有 价 格、数 量 和 链 指 针 三 个 域。现 新 到m台 价 格 为h的 电 视 机，试 编 写 算 法 修 改 原 链 表。5.线 性 表 中 的 元 素 值 按 递 增 有 序 排 列，针 对 顺 序 表 和 循 环 链 表 两 种 不 同 的 存 储 方 式，分别编写C函 数 删 除 线 性 表 中 值 介 于a与b (a W b)之 间 的 元 素。6.设A=(a O,a l,a 2,.,a n-1),B=(b O,b l,b 2.b m T)是两个给定的线性表,它们的结点个数分 别 是n和%且 结 点 值 均 是 整 数。若 n=m,且 a i=b i (O W i n),则 A=B；若 nm ,且 a i=b i (O W i n),则 A B；若存在一个 j,j m ,j n,且 a i=b i (O W ij ),若 a j b j,则 A B 7.试 编 写 算 法，删 除 双 向 循 环 链 表 中 第k个 结 点。8.线 性 表 由 前 后 两 部 分 性 质 不 同 的 元 素 组 成(a O,a l,a n-1,b O,b l,.,b m-1),m和n为两部 分 元素的个数，若 线 性 表 分 别 采 用 数 组 和 链 表 两 种 方 式 存 储，编写算法将两部分元素换位成(b O,b l,b m-1,a O,a l,.,a n-1),分 析 两 种 存 储 方 式 下 算 法 的 时 间 和 空 间 复 杂 度。9.用 循 环 链 表 作 线 性 表(a O,a l,.,a nT)和(b O,b l,.,b m-1)的存储结构，头指针分别为a h和b h,设 计C函 数，把 两 个 线 性 表 合 并 成 形 如(a O,b O,a l,b l,)的 线 性 表，要求不开辟新 的 动 态 空 间，利 用 原 来 循 环 链 表 的 结 点 完 成 合 并 操 作，结构仍为循环链表，头 指 针 为h ea d,并分 析 算 法 的 时 间 复 杂 度。10.试 写 出 将 一 个 线 性 表 分 解 为 两 个 带 有 头 结 点 的 循 环 链 表，并将两个循环链表的长度放在各自 的 头 结 点 的 数 据 域 中 的C函 数。其 中，线性表中序号为偶数的元素分解到第一个循环链表中,序 号 为 奇 数 的 元 素 分 解 到 第二个循 环 链 表 中。11.试 写 出 把 线 性 链 表 改 为 循 环 链 表 的C函 数。12.己 知 非 空 线 性 链 表 中x结 点 的 直 接 前 驱 结 点 为y,试 写 出 删 除x结 点 的C函 数。参 考 答 案：一、选择题1.B 2.C 3.D 4.B 5.A 6.A 7、C二、判 断 题：参 考 答 案：1、义2、J 3、X 4、X 5、V三、填空题1、s-n e x t=p-n e x t;p-n e x t=s;2、一 定；不 一(定 3、n/2 4、q-p r i o r=p;5、(1)6)3)(2)2)9)1)7)四、算 法 设计题1、#i n c l u d e s t d i o.h i n c l u d e /zm a l l o c.h t yp e d e f s t r u c t n o d e i n t d a t a;s t r u c t n o d e *1 i n k;N 0 DE;i n t a v e r(N O DE *h e a d)i n t i=0,s u m=0,a v e;N O DE *p;p二h e a d;w h i l e (p!=N U L L)p=p-l i n k;+i;s u m=s u m+p-d a t a;a v e=s u m/i;r e t u r n (a v e);2、t t i n c l u d e s t d i o.h t t i n c l u d e z，m a l l o c.h t yp e d e f s t r u c t n o d e(i n t d a t a;/*假 设 数 据 域 为 整 型*/s t r u c t n o d e *1 i n k;IN O DE；v o i d d e l _ l i n k (N O DE *h e a d,i n t x)/*删除数据域为 x 的结点*/(N O DE *p,*q,*s ;p二h e a d;q=h e a d-l i n k;w h i l e (q!=h e a d)i f (q-d a t a=x)p-l i n k=q-l i n k;s二q ；q=q-l i n k;f r e e (s);)e l s e(P=Q；q=q-l i n k;)3、v o i d d e l (N O DE *h e a d,f l o a t p r i c e,i n t n u m)N O DE *p,*q,*s ;p=h e a d;q二h e a d-n e x t;w h i l e (q-p r i c e n e x t;i f (q-p r i c e=p r i c e)q-n u m=q-n u m-n u m;e l s ep r i n t f (无此产品)；i f (q-n u m=0)(p-n e x t=q-n e x t;f r e e (q);)4、#i n c l u d e s t d i o.h i n c l u d e /zm a l l o c.h t yp e d e f s t r u c t n o d e(f l o a t p r i c e;i n t n u m;s t r u c t n o d e *n e x t;N O DE;v o i d i n s (N O DE *h e a d,f l o a t p r i c e,i n t n u m)N O DE *p,*q,*s ;p=h e a d;q=h e a d-n e x t;w h i l e (q-p r i c e n e x t;)i f (q-p r i c e=p r i c e)q-n u m=q-n u m+n u m;e l s e(s=(N O DE *)m a l l o c(s i z e o f(N O DE);s-p r i c e=p r i c e;s-n u m=n u m;s-n e x t=p-n e x t;p-n e x t=s;5、顺 序 表：算 法 思 想：从0开 始 扫 描 线 性 表，用k记 录 下 元 素 值 在a与b之 间 的 元 素 个 数，对于不满足该 条 件 的 元 素，前 移k个 位 置，最 后 修 改 线 性 表 的 长 度。v o i d d e l (e l e m t yp e 1i s t ,i n t *n,e l e m t yp e a,e l e m t yp e b)(i n t i=0,k=0；w h i l e (i=a&l i s t i l i n k;/*假 设 循 环 链 表 带 有 头 结 点*/w h i l e (q!=h e a d&q-d a t a l i n k;w h i l e (q!=h e a d&q-d a t a l i n k;f r e e (r);)i f (p!=q)p-l i n k=q;)6、#d e f i n e M AX SIZE 10 0i n t l i s t AM AX SIZE,1i s t BM AX SIZE;i n t n,m;i n t c o m p a r e (i n t a,i n t b)i n t i=0;w h i l e(a i=b i&i n&i m)i+；i f(n=m&i=n)r e t u r n (0);i f(n m&i=m)r e t u r n (1);i f (i n&i m)i f(a i b i)r e t u r n (1);7、v o i d d e l(DU N O DE *h e a d,i n t i)(DU N O DE *p;i f (i=0)(*h e a d=*h e a d-n e x t;*h e a d-p r i o r=N U L L;r e t u r n (0);)E l s e f o r(j=0;j n e x t;i f(p=N U L L|Ij i)r e t u r n(1);p-p r i o r-n e x t=p-n e x t;p-n e x t-p r i o r=p-p r o i r;f r e e (p);r e t u r n (0);8.顺序存储:v o i d c o n v e r t (e l e m t yp e l i s t,i n t l,i n t h)/*将数组中第 1 个到第 h 个元素逆置*/i n t i;e l e m t yp e t e m p;f o r(i=h;i=(l+h)/2;i+)(t e m p=l i s t i;l i s t i=l i s t 1+h-i;l i s t 1+h-i=t e m p;)v o i d e x c h a n g e(e l e m t yp e 1i s t ,i n t n,i n t m);(c o n v e r t(1i s t,0,n+m-1);c o n v e r t(1i s t,0,m-1);c o n v e r t(1i s t,m,n+m-1);)该 算 法 的 时 间 复 杂 度 为0(n+m),空 间 复 杂 度 为0(1)链 接 存 储：(不带头结点的单链表)t yp e d e f s t r u c t n o d e(e l e m t yp e d a t a;s t r u c t n o d e *1 i n k;N 0 DE;v o i d c o n v e r t (N O DE *h e a d,i n t n,i n t m)(N O DE *p,*q,*r;i n t i ;p=*h e a d;q=*h e a d;f o r (i=0;i l i n k;/*q 指向 a n T 结点*/r=q-l i n k;q-l i n k=N U L L;w h i l e(r-l i n k!=N U L L)r=r-l i n k;/*r指 向 最 后 一 个b m T结 点*/*h e a d=q;r-l i n k=p;)该 算 法 的 时 间 复 杂 度 为O(n+m),但 比 顺 序 存 储 节 省 时 间(不 需 要 移 动 元 素，只 需 改 变 指 针)，空间 复 杂 度 为0(1)9.t yp e d e f s t r u c t n o d e(e l e m t yp e d a t a;s t r u c t n o d e *1i n k;N 0 DE;N O DE *u n i o n (N O DE *a h,N O DE *b h)N O DE *a,*b,*h e a d,*r,*q;h e a d=a h;a=a h;b=b h;w h i l e(a-l i n k!=a h&b-l i n k!=b h)(r=a-l i n k;q=b-l i n k;a-l i n k=b;b-l i n k=r;a=r;b二 qi f (a-l i n k=a h)/*a 的 结 点 个 数 小 于 等 于 b的 结 点 个 数*/a-1i n k=b;w h i l e (b-l i n k!=b h)b=b-l i n k;b-l i n k=h e a d;)i f (b-l i n k=b h)/*b 的 结 点 个 数 小 于 a的 结 点 个 数*/(r=a-l i n k;a-l i n k=b;b-l i n k=r;)r e t u r n (h e a d);)该 算 法 的 时 间 复 杂 度 为 O(n+m),其 中 n和 m为两个循环链表的结点个数.10.t yp e d e f s t r u c t n o d e(e l e m t yp e d a t a;s t r u c t n o d e *1 i n k;N O DE;v o i d a n a l yz e (N O DE *a)(N O DE *r h,*q h,*r,*q,*p；i n t i=0,j=0；/*i 为 序 号 是 奇 数 的 结 点 个 数 j为 序 号 是 偶 数 的 结 点 个 数*/p=a；r h=(N O DE *)m a l l o c (s i z e o f (N O DE)；/*r h 为序号是奇数的链表头指针*/q h=(N O DE *)m a l l o c (s i z e o f (N O DE);/*q h 为序号是偶数的链表头指针*/r=r h;q=q h;w h i l e(p!=N U L L)r-l i n k=p;r=P；i+；p=p-l i n k;i f (p!=N U L L)(q-l i n k=p;q=P；j+；p=p-l i n k;)r h-d a t a=i;r-l i n k=r h;q h-d a t a=j;q-l i n k=q h;)11.t yp e d e f s t r u c t n o d e(e l e m t yp e d a t a;s t r u c t n o d e *1 i n k;)N 0 DE;v o i d c h a n g e(N O DE *h e a d)(N O DE *p;p二h e a d;i f (h e a d!=N U L L)w h i l e(p-l i n k!=N U L L)p=p-l i n k;p-l i n k=h e a d;)12.t yp e d e f s t r u c t n o d e(e l e m t yp e d a t a;s t r u c t n o d e *l i n k;N O DE;v o i d d e l (N O DE *x,N O DE *y)(N O DE *p,*q;e l e m t yp e d l;P=y；q=x;w h i l e (q-n e x t !=N U L L)/*把 后 一 个 结 点 数 据 域 前 移 到 前 个 结 点*/(p-d a t a=q-d a t a;q=q-l i n k;P二 q；p-l i n k=N U L L;/*删 除 最 后 一 个 结 点*/f r e e (q);第 三 章 栈 和 队 列一、选择题1.一 个 栈 的 入 栈 序 列 是a,b,c,d,e,则 栈 的 不 可 能 的 输 出 序 列 是（）。(A)e d c b a (B)d e c b a (C)d c e a b (D)a b o d e2.栈 结 构 通 常 采 用 的 两 种 存 储 结 构 是()。(A)线 性 存 储 结 构 和 链 表 存 储 结 构(B)散列方式和索引方式(C)链 表 存 储 结 构 和 数 组(D)线性存储结构和非线性存储结构3.判 定 个 栈 ST(最 多 元 素 为 mO)为 空 的 条 件 是()。(A)ST-top!=0(B)ST-top=0(C)ST-)top!=m0(D)ST-top=mO4.判 定 一 个 栈 ST(最 多 元 素 为 mO)为 栈 满 的 条 件 是()。(A)ST-top!=0(B)ST-top-=0(C)ST-top!=mO-l(D)ST-top=mO-l5.一个 队 列 的 入 列 序 列 是 1,2,3,4,则 队 列 的 输 出 序 列 是()。(A)4,3,2,1 (B)1,2,3,4(C)1,4,3,2(D)3,2,4,16.循 环 队 列 用 数 组 A0,m-l存 放 其 元 素 值，已 知 其 头 尾 指 针 分 别 是 front和 rear则当前队列中 的 元 素 个 数 是()(A)(rear-front+m)%m(B)rear-front+1(C)rear-front-1(D)rear-front7.栈 和 队 列 的 共 同 点 是()(A)都 是 先 进 后 出(B)都是先进先出(C)只 允 许 在 端 点 处 插 入 利 删 除 元 素(D)没有共同点8.表 达 式 a*(b+c)-d的 后 缀 表 达 式 是()。(A)abcd*+-(B)abc+*d-(C)abc*+d-(D)-+*abcd9.4 个 元 素 al,a2,a 3 和 a 4 依 次 通 过 一 个 栈，在 a 4 进 栈 前，栈 的 状 态，则不可能的出栈序是()(A)a4,a3,a2,al(B)a3.a2,a4,al(C)a3,al,a4,a2(D)a3,a4,a2,al10.以 数 组 Q0.m-l 存 放 循 环 队 列 中 的 元 素，变 量 rear和 qulen分别指示循环队列中队尾元 素 的 实 际 位 置 和 当 前 队 列 中 元 素 的 个 数，队 列 第 一 个 元 素 的 实 际 位 置 是()(A)rear qulen(B)rear qulen+m(C)m qulen(D)1 +(rear+m qulen)%m二、填空题1.栈的特点是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 队列的特点是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。2.线 性 表、栈 和队列都是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 结 构，可 以 在线性表的_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _位置插 入 和 删 除 元 素，对于栈只能在 插 入 和 删 除 元 素，对于队列只能在 插入元素和_ _ _ _ _ _ _ _ _ _ 删 除 元 素。3.一 个 栈 的 输 入 序 列 是1 23 4 5,则 栈 有 输 出 序 列1 23 4 5是_ _ _ _ _ _ _ _ _ _ _ _。（正确/错误）4.设 栈S和 队 列Q的 初 始 状 态 皆 为 空，元 素a l,a 2,a 3,a 4,a 5和a 6依 次 通 过 一 个 栈，一个 元 素 出 栈 后 即 进 入 队 列Q,若6个 元 素 出 队 列 的 顺 序 是a 3,a 5,a 4,a 6,a 2,a l则 栈S至少 应 该 容 纳 _ _ _ _ _ 个 元 素。三、算 法 设计题1.假 设 有 两 个 栈s i和s 2共 享 一 个 数 组s t a c k M,其 中 一 个 栈 底 设 在s t a c k 0 处，另一个栈底 设 在s t a c k M-l处。试 编 写 对 任 一 栈 作 进 栈 和 出 栈 运 算 的C函 数p us h（X,i）和p op（i）,i =l,2。其 中i =l表 示 左 边 的 栈，i=2表 示 右 边 的 栈。要求在整个数组元素都被占用时 才 产 生 溢 出。2.利 用 两 个 栈s i,s 2模 拟 一 个 队 列 时，如何用栈的 运 算 来 实 现 该 队 列 的 运 算？写出模拟队列的插 入 和 删 除 的C函 数。一 个 栈s i用 于 插 入 元 素，另 一 个 栈s 2用于删除元素.参 考 答 案：一、选择题1.C 2.A 3.B 4.B 5.B 6.B 7、C 8、C 9、C 1 0、D二、填空题1,先 进 先 出；先 进 后 出2、线 性；任 何；栈 顶：队 尾；对 头3、正 确 的4、3三、算 法 设计题1.t t d efi ne M 1 0 0elemt y p e s t a c k M;i nt t op l=0,t op 2=m-l;i nt p us h (elemt y p e x,i nt i)i f(t op l-t op 2=l)ret urn(1);/*上溢处理*/els ei f(i=l)s t a c k t op l+=x;i f(i=2)s t a c k t op 2-=x;ret urn(0);i nt p op (elemt y p e*p x,i nt i)(i f(i=l)i f(t op l=0)ret urn(1);els e(t op i-；*p x=s t a c k t op i ;ret urn(0);)els ei f(i=2)i f(t op 2=M-l)ret urn(1);els e(t op 2+;*p x=s t a c k t op 2;ret urn(0);2.elemt y p e s i MA X S I Z E,s 2 MA Z S I Z E;i nt t op i,t op 2;v oi d enq ueue(elemt y p e x)i f(t op l=MA X S I Z E)ret urn(1);els e(p us h (s i,x);ret urn(0);)v oi d d eq ueue(elemt y p e*p x)(elemt y p e x;t op 2=0;w h i le(!emp t y (s i)(p op(s i,&x);p us h (s 2,x);)p op(s 2,&x);w h i le(!emp t y (s 2)(p op(s 2,&x);p us h (s i,x);第 四 章 串一、选择题1.下 列 关 于 串 的 叙 述 中，正 确 的 是()(A)一 个 串 的 字 符 个 数 即 该 串 的 长 度(B)一 个 串 的 长 度 至 少 是1(C)空串是由一个 空 格 字 符 组 成 的 串(D)两 个 串S 1和S 2若 长 度 相 同，则这两个串相等2.字 符 串 a b a a a b a b”的 nex t v a l 值 为(？)(A)(0,1,0 1,1,0,4,1,0,1)(B)(0,1,0,0,0,0,2,1,0,1)(C)(0,1,0,1,0,0,0,1,1)(D)(0,1,0,1,0,1,0,1,1)3.字 符 串满足下式，其 中h ea d和t a i l的定义同广义表类似，如h ea d(x y z )=，x ,t a i l(x y z )=y z ，则 s=()。c onc a t (h ea d(t a i 1(s),h ea d(t a i l(t a i l(s)=，d c (A)a b ed (B)a eb d (C)a ed b (D)a d eb4.串 是一种特 殊 的 线 性 表，其 特 殊 性 表 现 在()(A)可 以 顺 序 存 储(B)数 据 元 素是一个字符(C)可 以 链 式 存 储(D)数据元素可以是多个字符5.设串 S l=A B C D EFG ,s 2=P Q R S T,函数 C ONC A T (X,Y)返回 X 和 Y 串 的 连 接 串，S U B S T R(S,I,J)返 回 串S从 序 号I开 始 的J个 字 符 组 成 的 字 串，L ENG T H (S)返 回 串S的 长 度，则 C ONC A T (S U B S T R (S I,2,L ENG T H (S 2),S U B S T R (S I,L ENG T H (S 2),2)的结果串是()(A)B C D EF(B)B C D EFG (C)B C P Q R S T (D)B C D EFEF二、算 法设计1.分 别 在顺序存储和 一 般 链 接 存 储 两种 方 式 下，用C语 言 写 出 实 现 把 串si复 制 到 串s2的串复制函数 strepy(si,s2)2.在 一 般 链 接 存 储(一个 结 点 存 放 个 字 符)方 式 下，写 出 采 用 简 单 算 法 实 现 串 的 模 式 匹 配 的C语言函数 in t L in dex(t,p)参 考 答 案：一、选择题1.A 2.B 3.D 4.D 5.D二、算法设计1.顺 序 存 储：ttin clude strin g,h”defin e MAXN 1 0 0char sMAXN;in t S str1 en (char s1)in t i;for(i=0;si!=0 ;i+);return (i);)void S strcpy(char si,char s2 )4.3 题(in t i;for(i=0;sii!=，0*;i+)s2 i=sl i;s2 i 0;一般链接存储：ttin clude stdio.htypedef struct n ode(char data;struct n ode*1 in k;NOD E;NOD E *L_strcpy(NOD E *sl)(NOD E *s2,*tl,*t2,*s;if(sl=NULL)return(NULL);else(tl=sl;t2=(NOD E *)malloc(sizeof(NOD E);s2=t2;while(tl!=NULL)(s=(NOD E *)malloc(sizeof(NOD E);s-data=tl-data;t2-lin k=s;1 2二s;tl=tl-lin k;)t2-lin k=NULL;s=s2;s2=s2-lin k;free(s);return (s2);)2.ttin clude stdio.htypedef struct n ode(char data;struct n ode*1 in k;NOD E;in t L_in dex(NOD E t,NOD E *p)(NO