【优质文档】严蔚敏数据结构课后习题与答案解析.pdf
《【优质文档】严蔚敏数据结构课后习题与答案解析.pdf》由会员分享,可在线阅读,更多相关《【优质文档】严蔚敏数据结构课后习题与答案解析.pdf(101页珍藏版)》请在三一文库上搜索。
1、98989 第一章绪论 一、选择题 1. 组成数据的基本单位是() (A)数据项( B)数据类型( C )数据元素( D)数据变量 2. 数据结构是研究数据的()以及它们之间的相互关系。 ( A)理想结构,物理结构(B )理想结构,抽象结构 ( C)物理结构,逻辑结构(D )抽象结构,逻辑结构 3. 在数据结构中,从逻辑上可以把数据结构分成() ( A)动态结构和静态结构(B )紧凑结构和非紧凑结构 ( C)线性结构和非线性结构(D)内部结构和外部结构 4. 数据结构是一门研究非数值计算的程序设计问题中计算机的()以及它们之间的()和运算等的学科。 (A)数据元素( B)计算方法( C)逻辑存
2、储( D)数据映像 (A)结构(B)关系(C)运算(D)算法 5. 算法分析的目的是()。 (A)找出数据结构的合理性(B)研究算法中的输入和输出的关系 (C)分析算法的效率以求改进( D )分析算法的易懂性和文档性 6. 计算机算法指的是(), 它必须具备输入、输出和()等 5 个特性。 (A)计算方法( B)排序方法( C)解决问题的有限运算序列(D)调度方法 (A)可执行性、可移植性和可扩充性(B)可行性、确定性和有穷性 ( C)确定性、有穷性和稳定性(D)易读性、稳定性和安全性 二、判断题 1. 数据的机内表示称为数据的存储结构。() 2. 算法就是程序。() 3. 数据元素是数据的最
3、小单位。() 4. 算法的五个特性为:有穷性、输入、输出、完成性和确定性。() 5. 算法的时间复杂度取决于问题的规模和待处理数据的初态。() 三、填空题 1. 数 据 逻 辑 结 构 包 括 _ 、 _ 、 _ 和 _ 四 种 类 型 , 其 中 树 形 结 构 和图形结构合称为_ 。 98989 2. 在线性结构中 ,第一个结点 _ 前驱结点 , 其余每个结点有且只有_ 个前驱结点;最后 一个结点 _ 后续结点 , 其余每个结点有且只有_ 个后续结点。 3. 在树形结构中 ,树根结点没有 _ 结点 ,其余每个结点有且只有_ 个前驱结点;叶子结点没有 _ 结点 , 其余每个结点的后续结点可以
4、_ 。 4. 在图形结构中 ,每个结点的前驱结点数和后续结点数可以_ 。 5. 线性结构中元素之间存在_ 关系 , 树形结构中元素之间存在_ 关系 , 图形结构中元素之间存在 _ 关系。 6. 算 法 的 五 个 重 要 特 性 是 _ 、 _ 、 _ 、 _ 、 _ 。 7. 数 据 结 构 的 三 要 素 是 指 _ 、 _ 和 _ 。 8. 链 式 存 储 结 构 与 顺 序 存 储 结 构 相 比 较 , 主 要 优 点 是 _ 。 9. 设有一批数据元素, 为了最快的存储某元素, 数据结构宜用 _ 结构, 为了方便插入一 个元素 ,数据结构宜用 _ 结构。 四、算法分析题 1. 求下
5、列算法段的语句频度及时间复杂度参考答 案: 一、选择题 1.C2.C3.C4.A 、B5.C6.C 、B 二、判断题 : 1、 2 、3、 4、 5、 三、填空题 1、线性、树形、图形、集合? ;非线性(网状) 2 、没有; 1;没有; 1 3 、前驱; 1;后继;任意多个 4 、任 意多个 5 、一对一;一对多;多对多 6 、有穷性;确定性;可行性;输入;输出 7 、数据元素;逻辑结构;存 储结构 8 、插入、删除、合并等操作较方便 9 、顺序存储;链式存储 四、算法分析题 98989 for(i=1; inext=p;p-next=s; (B )s-next=p-next;p-next=s
6、; ( C ) s-next=p-next;p=s; ( D ) p-next=s;s-next=p; 5. 在 一 个 单 链 表 中 , 若 删 除 p 所 指 结 点 的 后 续 结 点 , 则 执 行 () ( A ) p-next=p-next-next; ( B ) p=p-next; p-next=p-next-next; ( C ) p-next=p-next; ( D ) p =p-next-next; 6. 下列有关线性表的叙述中,正确的是() 98989 ( A)线性表中的元素之间隔是线性关系 ( B )线性表中至少有一个元素 ( C)线性表中任何一个元素有且仅有一个直接
7、前趋 98989 (D)线性表中任何一个元素有且仅有一个直接后继 7. 线 性 表 是 具 有 n 个 () 的 有 限 序 列 ( n 0) (A)表元素(B)字符(C)数据元素(D )数据项 二、判断题 1. 线性表的链接存储,表中元素的逻辑顺序与物理顺序一定相同。() 2. 如果没有提供指针类型的语言,就无法构造链式结构。() 3. 线性结构的特点是只有一个结点没有前驱,只有一个结点没有后继,其余的结点只有一个 前 驱和后继。() 4. 语 句 p=p- next 完 成 了 指 针 赋 值 并 使 p 指 针 得 到 了 p 指 针 所 指 后 继 结 点 的 数 据 域 值 。 ()
8、 5. 要 想 删 除 p 指 针 的 后 继 结 点 , 我 们 应 该 执 行 q=p-next ; p-next=q-next ; free(q) 。 () 三 、填空题 1. 已知 P 为单链表中的非首尾结点,在 P 结点后插入 S 结点的语句为: _ 。 2. 顺序表中逻辑上相邻的元素物理位置() 相邻, 单链表中逻辑上相邻的元素物理位置 _ 相 邻 。 3. 线 性 表 L ( a1 , a2 , . , an ) 采 用 顺 序 存 储 , 假 定 在 不 同 的 n 1 个 位 置 上 插 入 的 概 率相同,则插入一个新元素平均需要移动的元素个数是 _ 4. 在 非 空 双
9、向 循 环 链 表 中 , 在 结 点 q 的 前 面 插 入 结 点 p 的 过 程 如 下 : p-prior=q-prior; q-prior-next=p; p-next=q; _; 5. 已知 L 是无表头结点的单链表,是从下列提供的答案中选择合适的语句序列,分别实现: ( 1 ) 表 尾 插 入 s 结 点 的 语 句 序 列 是 _ (2)表 尾 插 入 s 结 点 的 语 句 序 列 是 _ 1.p-next=s; 2.p=L; 3.L=s; 98989 4.p-next=s-next; 98989 5.s-next=p-next; 6.s-next=L; 7.s-next=n
10、ull; 8.while(p-next!= Q)? p=p-next; 9.while(p-next!=null) p=p-next; 四、算法设计题 1. 试编写一个求已知单链表的数据域的平均值的函数(数据域数据类型为整型)。 2. 已 知 带 有 头 结 点 的 循 环 链 表 中 头 指 针 为 head, 试 写 出 删 除 并 释 放 数 据 域 值 为 x 的 所 有 结 点的 c 函 数 。 3. 某百货公司仓库中有一批电视机,按其价格从低到高的次序构成一个循环链表,每个结点有价 格 、 数 量 和 链 指 针 三 个 域 。 现 出 库 ( 销 售 ) m 台 价 格 为 h
11、的 电 视 机 , 试 编 写 算 法 修 改 原链 表 。 4. 某百货公司仓库中有一批电视机,按其价格从低到高的次序构成一个循环链表,每个结点有价 格 、 数 量 和 链 指 针 三 个 域 。 现 新 到 m 台 价 格 为 h 的 电 视 机 , 试 编 写 算 法 修 改 原 链 表 。 5. 线性表中的元素值按递增有序排列,针对顺序表和循环链表两种不同的存储方式,分别编写 C 函 数 删 除 线 性 表 中 值 介 于 a 与 b( a b ) 之 间 的 元 素 。 6. 设 A=(a0,a1,a2,.,an-1),B=(b0,b1,b2,.,bm-1) 是 两 个 给 定 的
12、线 性 表 , 它 们 的 结 点 个 数 分 别 是 n 和 m, 且 结 点 值 均 是 整 数 。 若 n=m , 且 ai= bi ( 0 iB 。 试编写一个比较 A 和 B 的 C 函数,该函数返回-1 或0 或1,分别表示AB 。 7. 试 编 写 算 法 , 删 除 双 向 循 环 链 表 中 第 k 个 结 点 。 8. 线 性 表 由 前 后 两 部 分 性 质 不 同 的 元 素 组 成 (a0,a1,.,an-1,b0,b1,.,bm-1),m 和 n 为 两 部分元素的个数 ,若线性表分别采用数组和链表两种方式存储, 编写算法将两部分元素换位成 (b0,b1,.,bm
13、-1,a0,a1,.,an-1), 分 析 两 种 存 储 方 式 下 算 法 的 时 间 和 空 间 复 杂 度 。 9. 用 循 环 链 表 作 线 性 表 (a0,a1,.,an-1) 和 ( b0,b1,.,bm-1 ) 的 存 储 结 构 , 头 指 针 分 别 为 ah 和 bh ,设 计 C 函 数 ,把 两 个 线 性 表 合 并 成 形 如( a0,b0,a1,b1, ?)的 线 性表 ,要 求 不 开 辟 98989 新 的 动 态 空 间 , 利 用 原 来 循 环 链 表 的 结 点 完 成 合 并 操 作 , 结 构 仍 为 循 环 链 表 , 头 指 针 为 hea
14、d, 并 分析算法的时间复杂度。 98989 10. 试写出将一个线性表分解为两个带有头结点的循环链表,并将两个循环链表的长度放在各自的头结点的数 据域中的 C 函数。其中 , 线性表中序号为偶数的元素分解到第一个循环链表中, 序号为奇数的元素分解到第二个循环链表中。 11. 试写出把线性链表改为循环链表的 C 函数。 12. 己 知 非 空 线 性 链 表 中 x 结 点 的 直 接 前 驱 结 点 为 y, 试 写 出 删 除 x 结 点 的 C 函 数 。参考答案: 一、选择题 1.B2.C3.D4.B5.A6.A7 、C 二、判断题 : 参考答案: 1、 2、 3、 4、 5、 三、填
15、空题 1、 s-next=p-next; p-next=s; 2 、一定;不一定 3、 n/2 4 、 q-prior=p; 5 、 (1)6) 3) (2)2)9 )1)7) 四、算法设计题 1、 #include “stdio.h“ #include “malloc.h“ typedef struct node int data; struct node *link; NODE; int aver(NODE *head) int i=0,sum=0,ave; NODE *p; p=head; 98989 while(p!=NULL) p=p-link;+i; 98989 sum=sum+p
16、-data; ave=sum/i; return (ave); 2、 #include “stdio.h“ #include “malloc.h“ typedef struct node int data; /* 假设数据域为整型 */ struct node *link; NODE; void del_link(NODE *head,int x) /* 删除数据域为 x 的 结 点 */ NODE *p,*q,*s; p=head; q=head-link; while(q!=head) if(q-data=x) p-link=q-link; s=q; q=q-link; free(s);
17、else p=q; q=q-link; 98989 98989 3、 void del(NODE *head,float price,int num) NODE *p,*q,*s; p=head;q=head-next; while(q-pricenext; if(q-price=price) q-num=q-num-num; else printf(“ 无此产品 “); if(q-num=0) p-next=q-next; free(q); 4、 #include “stdio.h“ #include “malloc.h“ typedef struct node float price; i
18、nt num; 98989 struct node *next; NODE; void ins(NODE *head,float price,int num) 98989 NODE *p,*q,*s; p=head;q=head-next; while(q-pricenext; if(q-price=price) q-num=q-num+num; else s=(NODE *)malloc(sizeof(NODE); s-price=price; s-num=num; s-next=p-next; p-next=s; 5、顺序表: 算 法 思 想 : 从 0 开 始 扫 描 线 性 表 , 用
19、 k 记 录 下 元 素 值 在 a 与 b 之 间 的 元 素 个 数 , 对 于 不 满 足 该 条 件 的 元 素 , 前 移 k 个 位 置 , 最 后 修 改 线 性 表 的 长 度 。 void del ( elemtype list , int *n , elemtype a , elemtype b ) int i=0 , k=0 ; while ( i=a /* 假设循环链表带有头结点 */ while(q!=head while(q!=head free(r); if(p!=q) p-link=q; 6、 #define MAXSIZE 100 int listAMAXSI
20、ZE,listBMAXSIZE; int n,m; 98989 int compare(int a,int b) int i=0; 98989 while(ai=bi if(ibi) return(1); 7、 void del(DUNODE *head,int i) DUNODE *p; if(i=0) *head=*head-next; *head-prior=NULL; return(0); Else for(j=0;jnext; if(p=NULL|ji) return(1); p-prior-next=p-next; p-next-prior=p-proir; free(p); 98
21、989 return(0); 8. 顺序存储 : 98989 void convert(elemtype list,int l,int h) /* 将数组中第 l 个 到 第 h 个 元 素 逆 置 */ int i; elemtype temp; for(i=h;ilink; /*q 指 向 an-1 结 点*/ r=q-link; q-link=NULL; while(r-link!=NULL) r=r-link; /*r 指 向 最 后 一 个 bm-1 结 点 */ *head=q; r-link=p; 该 算 法 的 时 间 复 杂 度 为 O(n+m), 但 比 顺 序 存 储 节
22、 省 时 间 ( 不 需 要 移 动 元 素 , 只 需 改 变 指 针 ), 空间复杂度为 O(1) 9. typedef struct node elemtype data; struct node *link; NODE; NODE *union(NO DE *ah,NODE *bh) NODE *a,*b,*head,*r,*q; head=ah; a=ah; b=bh; while(a-link!=ah q=b-link; 98989 a-link=b; b-link=r; a=r; b=q; 98989 if(a-link=ah) /*a 的 结 点 个 数 小 于 等 于 b 的
23、 结 点 个 数*/ a-link=b; while(b-link!=bh) b=b-link; b-link=head; if(b-link=bh) /*b 的 结 点 个 数 小 于 a 的 结 点 个 数*/ r=a-link; a-link=b; b-link=r; return(head); 该算法的时间复杂度为O(n+m ), 其 中 n 和 m 为 两 个 循 环 链 表 的 结 点 个 数 . 10. typedef struct node elemtype data; struct node *link; NODE; void analyze(NODE *a ) NODE i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优质文档 优质 文档 严蔚敏 数据结构 课后 习题 答案 解析
链接地址:https://www.31doc.com/p-5296062.html