《数据结构章习题课答案》由会员分享，可在线阅读，更多相关《数据结构章习题课答案（25页珍藏版）》请在金锄头文库上搜索。
1、习 题 课 （12章）曾 永 懂 络 蜂 腊 扰 勒 穗 萤 三 吨 簧 刃 挥 环 正 杖 改 券 资 脚 亭 棱 凶 至 强 御 慰 插 批 萝 数 据 结 构 1 - 2 章 习 题 课 答 案 数 据 结 构 1 - 2 章 习 题 课 答 案1一、填空题1. 数据的逻辑结构被分为 、 、 和 4种. 2. 数据的存储结构被分为 、 2种.3. 在线性结构、树形结构和图形结构中，直接前驱和 4. 直接后继结点之间分别存在着 、 和 5. 的联系。 6. 4. 一个算法应具有 、 、 输 7. 入和输出特性. 5. 一个算法的效率主要由 和 来度量。 6. 抽象数据类型包括_和_。 道
2、朱 变 声 忌 岗 熊 巡 睹 氮 莫 圭 势 潜 蓬 幕 涛 骡 糖 啡 肆 民 将 剃 皇 敢 疮 筏 车 递 邓 老 数 据 结 构 1 - 2 章 习 题 课 答 案 数 据 结 构 1 - 2 章 习 题 课 答 案27. 在顺序表中插入一个元素，需要平均移动 8. 元素，具体移动的元素个数与 有关。8. 在顺序表中逻辑上相邻的元素的物理位置 紧邻。 单链表中逻辑上相邻的元素的物理位置 紧邻。9. 在单链表中，除了首元结点外，任一结点的存储位置由 指示。10. 在单链表中设置头结点的作用是 。 涟 馆 漫 郊 峰 喘 申 迅 蚌 题 区 寿 楚 术 紧 散 奏 罩 祥 鬼 惯 娥 哥
3、 键 秒 疼 洪 残 能 扑 缴 旨 数 据 结 构 1 - 2 章 习 题 课 答 案 数 据 结 构 1 - 2 章 习 题 课 答 案314. 从一维数组An中顺序找出一个最大值元素的时间复杂度15. 为 ,输出一个二维数组Bmn中所有元素值的 时16. 间复杂度为 . 15. 在下面的程序中，s=s+p语句的执行次数为 ,p*=j语句的执行次数为 ,该程序段的时间复杂度为 .int i=0; s=0;while(+inext=S; (2) p-next=p-next-next; P-next= S-next; (4) S-next =P-next; S-next=L; (6) S-ne
4、xt=NULL; Q=P; while(P-next!=Q) P= P-next; while(P-next!=NULL) P= P-next; P=Q; (11) P=L; (12) L=S; (13) L=P;妻 滋 屯 裴 盲 液 俘 跳 骋 绣 洽 跪 颐 腔 岭 佑 寂 政 集 概 狞 焚 贬 付 悼 混 辉 淘 拉 饶 痈 恒 数 据 结 构 1 - 2 章 习 题 课 答 案 数 据 结 构 1 - 2 章 习 题 课 答 案8四、设有一个10*10的对称矩阵A1010，采取按行压缩存 储的方式存放于一个一维数组B 中，则数组B 的容量应有 多大？若设A00为第一个元素，存放于B
5、0，且数组A 的每一个数组元素在数组B 中占一个数组元素位置，则 A85在数组B 中地址是多少？答案： 数组B应有55个元素，对于下三角矩阵， LOC(A85)=1+8+5=41对于上三角矩阵，LOC(A85)= LOC(A58)=10+9+8+7+6+(8-5)=43柿 霓 履 憾 付 京 彭 盲 骋 否 查 客 景 儒 没 扔 呵 送 皑 瘦 疾 棘 姚 鼎 丘 缄 写 恤 芝 患 斡 网 数 据 结 构 1 - 2 章 习 题 课 答 案 数 据 结 构 1 - 2 章 习 题 课 答 案9五、（1）画出执行下列各行语句后各指针及链表的示意图。 Node *L=new Node( );
6、P=L;for(i=1; inext=Q; P=P-next; P-data=2*i-1;P-next=NULL;for(i=4; i=1; i-) Insert(2*i, i+1);for(i=1; inext) Q=L; L=L-next; P=L;while(P-next) P=P-next; P-next=Q; Q-next=NULL; 怒 且 沂 耽 羞 娱 蹿 超 蘸 壁 世 颠 棕 鞘 獭 坊 姓 含 探 宵 网 吁 呸 彦 紫 迸 若 酱 昨 欧 雁 豁 数 据 结 构 1 - 2 章 习 题 课 答 案 数 据 结 构 1 - 2 章 习 题 课 答 案11(2) void
7、BB(ListNode *s; ListNode *q) p=s;while(p-next!=q) p-p-next;p-next=s;void AA (ListNode *pa; ListNode *pb) BB(pa,pb); /pa和pb分别指向单循环链表中的两个结点。BB(pb,pa);泌 种 钧 枯 氓 渝 粮 悼 向 鲁 阻 树 弗 奠 卧 担 扫 厉 嘶 劲 蹬 栽 摆 五 系 慢 憨 燕 栅 浇 胸 御 数 据 结 构 1 - 2 章 习 题 课 答 案 数 据 结 构 1 - 2 章 习 题 课 答 案12数据结构: 所研究内容的着重点主要体现在三个方面： 第一是数据间的逻辑
8、关系，即数据元素之间的关系。 第二是数据的存储关系，即数据在计算机中的存储结构。 第三是算法，即定义在逻辑关系上的一组操作。 因此，简单说来，数据结构所研究的问题是如何将现实世界中的事 物合理描述为计算机世界中所研究的对象，并根据研究对象的特点 ，分析对象之间的关系、存储结构和操作的学科。1.试说明基本数据类型、数据结构和抽象数据类型的联系与差异。基本数据类型（Data Type）：在程序设计高级语言中，数据类型用来说明一个数据在数据 分类中的归属。它是数据的一种属性。这个属性限定了该数据的 变化范围。高级语言中都有基本数据类型。例如在C、C+和 Java语言中，有基本类型int（整型）、fl
9、oat（浮点型）和char（ 字符型），有构造类型数组、结构、联合、指针、枚举型和自定 义等。数据类型仅局限于计算机中定义并实现了的数据类型;绰 酥 卡 熏 询 霹 宇 厦 跳 艾 使 郸 太 臃 斑 酥 掳 保 仓 熙 饥 菇 猩 畦 堤 昼 惨 柴 杠 夜 纷 幢 数 据 结 构 1 - 2 章 习 题 课 答 案 数 据 结 构 1 - 2 章 习 题 课 答 案13抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于抽象数据类型的逻辑特性，与它在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要数学特性不变，都不影响抽象数据类型外部的使用。抽
10、象数据类型除了计算机中定义并实现了的数据类型；还包括用户在设计软件系统时自己定义的数据类型。曼 洛 乡 辑 东 修 梆 够 骗 痴 跳 铭 幢 讶 绦 体 鸳 佯 诛 制 殿 躯 唐 崖 控 苔 迷 掠 醚 熔 怎 类 数 据 结 构 1 - 2 章 习 题 课 答 案 数 据 结 构 1 - 2 章 习 题 课 答 案141-5 试说明数据的逻辑结构、存储结构和算法三者之间的关系。1个数据逻辑结构可有多种不同的存储结构；存储结构是对逻辑结构实现；算法是基于逻辑结构对操作的实现；函数是 基于存储结构对算法的实现，是程序；答：数据的逻辑结构、存储结构和算法是数据结构所讨论的三个方面。赴 檬 肿
11、菜 搐 秧 鲜 弗 辞 犊 堡 开 憋 泄 妻 制 盲 驱 茬 走 叙 斤 娄 张 坊 芹 瘫 媳 掀 垃 雾 油 数 据 结 构 1 - 2 章 习 题 课 答 案 数 据 结 构 1 - 2 章 习 题 课 答 案151-6 请给出下列函数的大O和表示：O(n1/2logn)O(n)O(n1.5)O(n1/2)咖 往 捌 间 封 吏 揭 逛 酵 爆 线 孤 冉 臼 咐 酶 丽 戚 婶 峻 糊 屿 抵 氟 霍 凰 医 义 雅 解 彬 酿 数 据 结 构 1 - 2 章 习 题 课 答 案 数 据 结 构 1 - 2 章 习 题 课 答 案162-1描述以下三个概念的区别：头指针、头结点、首
12、结点（第一个元素结点）。在单链表中设置头结点的 作用是什么？答：首结点就是存放数据元素的第一个元素结点，头 结点是为了插入和删除的方便说增设的一个结点，头 指针是指向链表中第一个结点的存储位置，在没有头 结点的链表中，头指针指向链表中的首结点，在有头 结点的链表中，头指针指向链表中的头结点。习 题 2（p55）彩 界 叶 茁 浪 拇 逃 牲 由 埠 擦 思 谷 粪 襟 铡 烛 巍 统 批 即 腹 素 路 稳 估 挖 夸 韦 氖 奔 坝 数 据 结 构 1 - 2 章 习 题 课 答 案 数 据 结 构 1 - 2 章 习 题 课 答 案172-4 已知二维数组Am,m采用按行优先顺序存放 ，每
13、个元素占K个存储单元，并且第一个元素的存储地 址为Loc(a00)，请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？答：行优先顺序存放时:Loc(aij)= Loc(a00) +(i*m+j)*K列优先顺序存放时:Loc(aij)= Loc(a00) +(j*m+i)*K南 吼 诬 横 蝇 竹 瞪 容 怔 憎 寿 豪 楼 横 霜 寓 愤 筒 杰 铆 队 鳞 捎 强 莉 莽 惊 遇 滚 夸 空 半 数 据 结 构 1 - 2 章 习 题 课 答 案 数 据 结 构 1 - 2 章 习 题 课 答 案182-5 在链表类的实现中增加一个成员函数实现对表中元素置逆 的操作（设原链表为
14、a0, a1, , an-2, an-1；则置逆后的序列为 an-1, an-2, ,a1, a0）。对于有n个元素的线性表，你的算法的运行 时间应为O(n)。 void LinkList: Inverse( ) if (head-next=NULL) return;p=head-next; head-next=NULL;while(p!=NULL) q=p-next; p-next=head-next;head-next=p; p=q;氟 宋 耸 痪 秒 瞳 遁 索 瞒 侯 瑞 扫 物 稚 硅 乌 泡 玲 药 牲 票 亲 鹃 拓 杆 顾 徊 妨 钾 恬 抿 蹭 数 据 结 构 1 - 2 章 习 题 课 答 案 数 据 结 构 1 - 2 章 习 题 课 答 案192-10 设计一个算法，将数组A(0n-1)中的元素循环右 移k位，假设原数组序列为a0, a1, , an-2, an-1；移动后 的序列为 an-k, an-k+1, , a0, a1, , an-k-1。要求只用一个
