【优质文档】严蔚敏数据结构课后习题与答案解析.pdf

98989 第一章绪论 一、选择题 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）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（ D ）分析算法的易懂性和文档性 6. 计算机算法指的是（）, 它必须具备输入、输出和（）等 5 个特性。 （A）计算方法（ B）排序方法（ C）解决问题的有限运算序列（D）调度方法 （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （ C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1. 数据的机内表示称为数据的存储结构。（） 2. 算法就是程序。（） 3. 数据元素是数据的最小单位。（） 4. 算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5. 算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1. 数 据 逻 辑 结 构 包 括 _ 、 _ 、 _ 和 _ 四 种 类 型 , 其 中 树 形 结 构 和图形结构合称为_ 。 98989 2. 在线性结构中 ,第一个结点 _ 前驱结点 , 其余每个结点有且只有_ 个前驱结点；最后 一个结点 _ 后续结点 , 其余每个结点有且只有_ 个后续结点。 3. 在树形结构中 ,树根结点没有 _ 结点 ,其余每个结点有且只有_ 个前驱结点；叶子结点没有 _ 结点 , 其余每个结点的后续结点可以_ 。 4. 在图形结构中 ,每个结点的前驱结点数和后续结点数可以_ 。 5. 线性结构中元素之间存在_ 关系 , 树形结构中元素之间存在_ 关系 , 图形结构中元素之间存在 _ 关系。 6. 算 法 的 五 个 重 要 特 性 是 _ 、 _ 、 _ 、 _ 、 _ 。 7. 数 据 结 构 的 三 要 素 是 指 _ 、 _ 和 _ 。 8. 链 式 存 储 结 构 与 顺 序 存 储 结 构 相 比 较 , 主 要 优 点 是 _ 。 9. 设有一批数据元素, 为了最快的存储某元素, 数据结构宜用 _ 结构, 为了方便插入一 个元素 ,数据结构宜用 _ 结构。 四、算法分析题 1. 求下列算法段的语句频度及时间复杂度参考答 案： 一、选择题 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; （ 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）线性表中任何一个元素有且仅有一个直接前趋 98989 （D）线性表中任何一个元素有且仅有一个直接后继 7. 线 性 表 是 具 有 n 个 （） 的 有 限 序 列 （ n 0) （A）表元素（B）字符（C）数据元素（D ）数据项 二、判断题 1. 线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（） 2. 如果没有提供指针类型的语言，就无法构造链式结构。（） 3. 线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个 前 驱和后继。（） 4. 语 句 p=p- next 完 成 了 指 针 赋 值 并 使 p 指 针 得 到 了 p 指 针 所 指 后 继 结 点 的 数 据 域 值 。 （） 5. 要 想 删 除 p 指 针 的 后 继 结 点 ， 我 们 应 该 执 行 q=p-next ； p-next=q-next ； free(q) 。 （） 三 、填空题 1. 已知 P 为单链表中的非首尾结点，在 P 结点后插入 S 结点的语句为： _ 。 2. 顺序表中逻辑上相邻的元素物理位置() 相邻， 单链表中逻辑上相邻的元素物理位置 _ 相 邻 。 3. 线 性 表 L （ a1 ， a2 ， . ， an ） 采 用 顺 序 存 储 ， 假 定 在 不 同 的 n 1 个 位 置 上 插 入 的 概 率相同，则插入一个新元素平均需要移动的元素个数是 _ 4. 在 非 空 双 向 循 环 链 表 中 ， 在 结 点 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=null; 8.while(p-next!= Q)? p=p-next; 9.while(p-next!=null) p=p-next; 四、算法设计题 1. 试编写一个求已知单链表的数据域的平均值的函数（数据域数据类型为整型）。 2. 已 知 带 有 头 结 点 的 循 环 链 表 中 头 指 针 为 head, 试 写 出 删 除 并 释 放 数 据 域 值 为 x 的 所 有 结 点的 c 函 数 。 3. 某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价 格 、 数 量 和 链 指 针 三 个 域 。 现 出 库 （ 销 售 ） m 台 价 格 为 h 的 电 视 机 ， 试 编 写 算 法 修 改 原链 表 。 4. 某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价 格 、 数 量 和 链 指 针 三 个 域 。 现 新 到 m 台 价 格 为 h 的 电 视 机 ， 试 编 写 算 法 修 改 原 链 表 。 5. 线性表中的元素值按递增有序排列，针对顺序表和循环链表两种不同的存储方式，分别编写 C 函 数 删 除 线 性 表 中 值 介 于 a 与 b（ a b ） 之 间 的 元 素 。 6. 设 A=(a0,a1,a2,.,an-1),B=(b0,b1,b2,.,bm-1) 是 两 个 给 定 的 线 性 表 , 它 们 的 结 点 个 数 分 别 是 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-1,a0,a1,.,an-1), 分 析 两 种 存 储 方 式 下 算 法 的 时 间 和 空 间 复 杂 度 。 9. 用 循 环 链 表 作 线 性 表 (a0,a1,.,an-1) 和 （ b0,b1,.,bm-1 ） 的 存 储 结 构 , 头 指 针 分 别 为 ah 和 bh ，设 计 C 函 数 ，把 两 个 线 性 表 合 并 成 形 如（ a0,b0,a1,b1, ?）的 线 性表 ，要 求 不 开 辟 98989 新 的 动 态 空 间 , 利 用 原 来 循 环 链 表 的 结 点 完 成 合 并 操 作 , 结 构 仍 为 循 环 链 表 , 头 指 针 为 head, 并 分析算法的时间复杂度。 98989 10. 试写出将一个线性表分解为两个带有头结点的循环链表，并将两个循环链表的长度放在各自的头结点的数 据域中的 C 函数。其中 , 线性表中序号为偶数的元素分解到第一个循环链表中, 序号为奇数的元素分解到第二个循环链表中。 11. 试写出把线性链表改为循环链表的 C 函数。 12. 己 知 非 空 线 性 链 表 中 x 结 点 的 直 接 前 驱 结 点 为 y, 试 写 出 删 除 x 结 点 的 C 函 数 。参考答案： 一、选择题 1.B2.C3.D4.B5.A6.A7 、C 二、判断题 : 参考答案： 1、× 2、 3、 ×4、 ×5、 三、填空题 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-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); 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; int 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 开 始 扫 描 线 性 表 ， 用 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 listAMAXSIZE,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); 98989 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), 但 比 顺 序 存 储 节 省 时 间 ( 不 需 要 移 动 元 素 , 只 需 改 变 指 针 ), 空间复杂度为 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 的 结 点 个 数*/ 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 int i=0 * r h ， *qh ， *r,*q,*p ； ， j=0 ； /*i 为 序 号 是 奇 数 的 结 点 个 数 j 98989 为序号 是偶数 的结点 个数 */ p=a ； rh= （ NODE * ） malloc （ sizeof （ NODE ） ） ； /*rh 为 序 号 是 奇 数 的 链 表 头 指 针 qh=(NODE *)malloc(sizeof(NODE); /*qh 为 序 号 是 偶 数 的 链 表 头 指 针*/ */ r=rh; q=qh; 98989 while(p!=NULL) r-link=p; r=p; i+; p=p-link; if(p!=NULL) q-link=p; q=p; j+; p=p-link; rh-data=i; r-link=rh; qh-data=j; q-link=qh; 11. typedef struct node elemtype data; struct node *link; NODE; void change(NODE *head) 98989 NODE *p; p=head; if(head!=NULL) 98989 while(p-link!=NULL) p=p-link; p-link=head; 12. typedef struct node elemtype data; struct node *link; NODE; void del(NODE *x,NODE *y) NODE *p,*q; elemtype d1; p=y; q=x; while(q-next!=NULL) /* 把 后 一 个 结 点 数 据 域 前 移 到 前 一 个 结 点 */ p-data=q-data; q=q-link; p=q; p-link=NULL; /* 删 除 最 后 一 个 结 点 */ free(q); 第三章栈和队列 一、选择 题 1. 一个栈的入栈序列是 （ A）edcba （ B ） decba 98989 a,b,c,d,e, （ C ） dceab 则栈的不可 能的输出序 列是（）。 （ D ） abcde 98989 2. 栈结构通常采用的两种存储结构是（）。 （ A） 线性存储结构和链表存储结构（B ）散列方式和索引方式 （ C）链表存储结构和数组（D ）线性存储结构和非线性存储结构 3. 判 定 一 个 栈 ST( 最 多 元 素 为 m0) 为 空 的 条 件 是 （） 。 （ A）ST- top!=0 （ B ） ST- top=0 （ C ） ST- top!=m0 （ D ） ST- top=m0 4. 判 定 一 个 栈 ST( 最 多 元 素 为 m0) 为 栈 满 的 条 件 是 （） 。 （ A） ST-top!=0 （ B ） ST-top=0 （ C ） ST-top!=m0-1 （ D ） ST-top=m0-1 5. 一个队列的入列序列是 1,2,3,4, 则队列的输出序列是（）。 （ A） 4,3,2,1 （ B ） 1,2,3,4 （ C） 1,4,3,2 （ D ） 3,2,4,1 6. 循 环 队 列 用 数 组 A0,m-1 存 放 其 元 素 值 , 已 知 其 头 尾 指 针 分 别 是 front 和 rear 则 当 前 队 列 中的元素个数是（） （ A） (rear-front+m)%m （ B ）rear-front+1 （ C） rear-front-1 （ D ） rear-front 7. 栈和队列的共同点是（） （ A） 都是先进后出（B）都是先进先出 （ C）只允许在端点处插入和删除元素（ D ）没有共同点 8. 表 达 式 a*(b+c)-d 的 后 缀 表 达 式 是 （ ） 。 （ A） abcd*+- （ B ） abc+*d- （ C） abc*+d- （ D ） -+*abcd 9.4 个 元 素 a1 ， a2 ， a3 和 a4 依 次 通 过 一 个 栈 ，在a4 进 栈 前 ，栈 的 状态 ，则 不 可 能 的 出 栈 序 是 （） (A)a4 ， a3 ， a2 ， a1 (B)a 3 ， a2 ， a4 ， a1 (C)a3 ， a1 ， a4 ， a2 (D)a 3 ， a4 ， a2 ， a1 10. 以 数 组 Q0m 1 存 放 循 环 队 列 中 的 元 素 ，变 量 rear 和 qulen 分 别 指 示 循 环 队 列 中 队 尾 元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（） (A)rea r qulen (B)rear qulen m (C)m qulen (D)1 （ rear m qulen ） % m 二、填空题 1. 栈 的 特 点 是 _, 队 列 的 特 点 是 _。 98989 2. 线 性 表 、 栈 和 队 列 都 是 _结 构 , 可 以 在 线 性 表 的 _ 位 置 插入和删除元素，对于栈只能在_ 插入和删除元素，对于队列只能在_ 插入元素 98989 和 _ 删 除 元 素 。 3. 一个栈的输入序列是 12345, 则栈有输出序列 12345 是_ 。(正确 / 错误 ) 4. 设 栈 S 和 队 列 Q 的 初 始 状 态 皆 为 空 ， 元 素 a1 ， a2 ， a3 ， a4 ， a5 和 a6 依 次 通 过 一 个 栈 ， 一个 元 素 出 栈 后 即 进 入 队 列 Q ，若 6 个 元 素 出 队 列 的 顺 序 是 a3 ， a5 ， a4 ， a6 ， a2 ， a1 则 栈 S 至 少应该容纳 _ 个元素。 三、算法设计题 1. 假 设 有 两 个 栈 s1 和 s2 共 享 一 个 数 组 stackM, 其 中 一 个 栈 底 设 在 stack0 处 ， 另 一 个 栈 底 设 在 stackM-1 处 。 试 编 写 对 任 一 栈 作 进 栈 和 出 栈 运 算 的 C 函 数 push （ x,i) 和 pop(i),i=l,2 。其 中 i=1 表 示 左 边 的 栈 ， ,i=2 表 示 右 边 的 栈 。要 求 在 整 个 数 组 元 素 都 被 占 用 时才产生溢出。 2. 利 用 两 个 栈 s1,s2 模 拟 一 个 队 列 时 , 如 何 用 栈 的 运 算 来 实 现 该 队 列 的 运 算 ? 写 出 模 拟 队 列 的插入和删除的 C 函数。 一 个 栈 s1 用 于 插 入 元 素 , 另 一 个 栈 s2 用 于 删 除 元 素 . 参考答案： 一、选择题 1.C2.A3.B4.B5.B6.B7 、C8 、C9 、C10 、D 二、填空题 1、先进先出；先进后出 2 、线性；任何；栈顶；队尾；对头 3 、正确的4、3 三、算法设计题 1. #define M 100 elemtype stackM; int top1=0,top2=m-1; int push(elemtype x,int i) 98989 98989 if(top1-top2=1) return(1); /* else if(i=1) stacktop1+=x; if(i=2)stacktop2-=x; return(0); int pop(elemtype *px,int i) if(i=1) if(top1=0) return(1); else top1-; *px=stacktop1; return(0); else if(i=2) if(top2=M-1) return(1); else top2+; *px=stacktop2; return(0); 2. elemtype s1MAXSIZE,s2MAZSIZE; int top1,top2; void enqueue(elemtype x) 98989 上溢处理 */ 98989 if(top1=MAXSIZE) return(1); else push(s1,x); return(0); void dequeue(elemtype *px) elemtype x; top2=0; while(!empty(s1) pop(s1, push(s2,x); pop(s2, while(!empty(s2) pop(s2, push(s1,x); 第四章串 一、选择题 1. 下列关于串的叙述中，正确的是（ (A) 一个串的字符个数即该串的长度 ） (B) 一个串的长度至少是 1 (C) 空串是由一个空格字符组成的串 (D) 两个串 S1 和 S2 若长度相同，则这两个串相等 98989 2. 字 符 串 “abaaabab“ 的 nextval 值 为 (? ) (A)(0,1,01,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) 98989 3. 字 符 串 满 足 下 式 , 其 中 head 和 tail 的 定 义 同 广 义 表 类 似 , 如 head( xyz )= x ,tail( xyz )= yz , 则s=( ) 。concat(head(tail(s),head(tail(tail(s)= dc 。 (A)abcd (B)acbd (C)acdb (D)adcb 4. 串是一种特殊的线性表, 其特殊性表现在（） (A) 可以顺序存储 (B) 数据元素是一个字符 (C) 可以链式存储 (D) 数据元素可以是多个字符 5设 串 S1= ABCDEFG,s2= PQRST , 函 数 CONCAT （ X ，Y）返 回 X 和 Y 串 的 连 接 串 ，SUBSTR （ S，I ， J ）返回串S 从序号I 开始的J 个字符组成的字串，LENGTH（ S）返回串S 的长度，则 CONCAT （ SUBSTR （ S1 ， 2 ， LENGTH（ S2 ） ， SUBSTR （ S1 ， LENGTH（ S2 ） ， 2 ） ） 的 结 果 串是 （ ） （ A） BCDEF (B) BCDEFG (C)BCPQRST (D)BCDEFEF 二、算法设计 1. 分 别 在 顺 序 存 储 和 一 般 链 接 存 储 两 种 方 式 下 , 用 C 语 言 写 出 实 现 把 串 s1 复 制 到 串 s2 的 串 复 制 函 数 strcpy(s1,s2) 。 2. 在一般链接存储(一个结点存放一个字符)方式下 ,写出采用简单算法实现串的模式匹配的 C 语 言 函 数 int L_index(t,p) 。 参考答案： 一、选择题 1.A2.B3.D4.D5.D 二、算法设计 1. 顺序存储： #include “string.h“ #define MAXN 100 98989 char sMAXN; int S_strlen(char s) 98989 int i; for(i=0;si!='0'i+); return(i); void S_strcpy(char s1,char s2) /4.3 题 int i; for(i=0;s1i!='0'i+) s2i=s1i; s2i='0' 一般链接存储： #include “stdio.h“ typedef struct node char data; struct node *link; NODE; NODE *L_strcpy(NODE *s1) NODE *s2,*t1,*t2,*s; if(s1=NULL) return(NULL); else t1=s1; t2=(NODE *)malloc(sizeof(NODE); s2=t2; 98989 while(t1!=NULL) s=(NODE *)malloc(sizeof(NODE); s-data=t1-data; 98989 t2-link=s; t2=s; t1=t1-link; t2-link=NULL; s=s2; s2=s2-link; free(s); return(s2); 2. #include “stdio.h“ typedef struct node char data; struct node *link; NODE; int L_index(NODE *t,NODE *p) NODE *t1,*p1,*t2; ?int i; t1=t;i=1; while(t1!=NULL) p1=p; t2=t1-link; 98989 while(p1-data=t1-data t1=t1-link; 98989 if(p1=NULL) return(i); i+; t1=t2; return(0); 第五章数组和广义表 一、选择题 1.常对数组进行的两种基本操作是（） （A）建立与删除（B ）索引和修改（C）查找和修改（D）查找与索引 2. 二 维 数 组 M 的 元 素 是 4 个 字 符 ( 每 个 字 符 占 一 个 存 储 单 元 ) 组 成 的 串 , 行 下 标 i 的 范 围 从 0 到 4, 列 下 标 j 的 范 围 从 0 到 5,M 按 行 存 储 时 元 素 M35 的 起 始 地 址 与 M 按 列 存 储 时 元 素 ( ) 的 起始地址相同。 （ A） M24 （ B ） M34 （ C） M35 （ D ） M44 3. 数组 A810 中, 每个元素 A 的长度为 3 个字节 , 从首地址 SA 开始连续存放在存储器内, 存 放该数组至少需要的单元数是（）。 （ A） 80 （ B ） 100 （ C） 240 （ D ） 270 4. 数组 A810 中, 每个元素 A 的长度为 3 个字节 , 从首地址 SA 开始连续存放在存储器内, 该 数组按行存放时 ,元素 A74 的起始地址为（）。 （ A） SA+141 （ B ） SA+144 （ C） SA+222 （ D ） SA+225 5. 数组 A810 中, 每个元素 A 的长度为 3 个字节 , 从首地址 SA 开始连续存放在存储器内, 该 数组按列存放时 ,元素 A47 的起始地址为（）。 （ A） SA+141 （ B ） SA+180 （ C） SA+222 （ D ） SA+225 6. 稀疏矩阵一般的压缩存储方法有两种, 即（ ）。（ A） 二 维数组和三维数组（B）三元组和散列 （C）三元组和十字链表（D）散列和十字链表 7. 若采用三元组压缩技术存储稀疏矩阵, 只要把每个元素的行下标和列下标互换, 就完成了对 该矩阵的转置运算, 这种观点（）。 98989 （A）正确（ B）错误 98989 8. 设矩阵 A 是一个对称矩阵, 为了节省存储 , 将其下三角部分按行序存放在一维数组 B1,n(n-1)/2 中 , 对 下 三 角 部 分 中 任 一 元 素 ai,j(i #define m 3 #define n 4 void minmax(int amn) int i1,j,have=0; int minm,maxn; for(i1=0;i1max j) maxj=ai1j; 98989 for(i1=0;i1=m*/ for(j=0;jtag=1; h-dd.sublist=creat_GL(s); 98989 Else h-tag=0; h-dd.data=ch; else h=NULL; ch=*(*s); (*s)+; if(h!=NULL) if(ch=',') h-link =creat_GL(s); else h-link=NULL; return(h); void prn_GL(NODE *p) if(p!=NULL) if(p-tag=1) printf(“(“); if(p-dd.sublist =NULL) printf(“ “); else 98989 prn_GL(p-dd.sublist ); else printf(“%c“,p-dd.data); 98989 if(p-tag=1) printf(“)“); if(p-link!=NULL) printf(“,“); prn_GL(p-link); NODE *copy_GL(NODE *p) NODE *q; if(p=NULL) return(NULL); q=(NODE *)malloc(sizeof(NODE); q-tag=p-tag; if(p-tag) q-dd.sublist =copy_GL(p-dd.sublist ); else q-dd.data =p-dd.data; q-link=copy_GL(p-link); return(q); NODE *head(NODE *p) /* 求表头函数 */ return(p-dd.sublist); NODE *tail(NODE *p) /* 98989 求表尾函数*/ return(p-link); int sum(NODE *p) /*