CHAPTER 11Data StructuresReview Questions1.We need data structures to hold a collection of related variables so that we cansolve complex problems more efficiently.3.An array is a fixed-size sequenced collection of elements of the same data type.5.Elements of an array are contiguous in memory and can be accessed by use of anindex. Elements of a linked list are stored in nodes that may be scattered through-out memory and can only be accessed via the access functions for the list (i.e., aspecific node is returned by a search function).7.A frequency array shows the number of elements with the same value found in aparticular collection of data.9.An array is stored contiguously in memory. A two-dimensional array uses row-major storage in which the array is essentially stored as an array of arrays.11.The fields of a node in a linked list are the data itself and a pointer (address) to thenext node in the list.13.The head pointer contains the address of the first node in the list.15.A singly linked list is a linked list in which each node contains only one pointerthat contains the address of the following node. There are multi-linked lists inwhich each node contains more than one pointer, allowing for much more complexdata structures.Multiple-Choice Questions17.d19.d21.b23.d25.c27.b29.d34CHAPTER 11DATA STRUCTURES31.a33.a35.bExercises37.CompareInput: Two arrays (A and B) of 10 integers1. Set Index equal to 02. While Index is less than 102.1 If A [Index] is not equal to B [Index]2.1.1 Return falseEnd if2.2 Increment IndexEnd loop3. Return trueEnd39.PrintInput: An array (A), the number of rows (I), and the number columns (J)1. Set RowIndex equal to 02. Set ColIndex equal to 03. While RowIndex is less than I3.1 While ColIndex is less than J3.1.1 Print A [RowIndex][ColIndex]3.1.2 Increment ColIndexEnd loop3.2 Move to next line in output3.3 Increment RowIndexEnd loopEnd41.AddFractionsInput: Two fractions (Fr1 and Fr2)1. Allocate new fraction object (Fr3)2. Set Fr3.denominator equal to Fr1.denominator * Fr2.denominator3. Set Fr3.numerator equal to (Fr1.numerator * Fr2.denominator) +(Fr2.numerator *Fr1.denominator)4. Return Fr3EndSECTION 543.MultiplyFractionsInput: Two fractions (Fr1 and Fr2)1. Allocate new fraction object (Fr3)2. Set Fr3.denominator equal to Fr1.denominator * Fr2.denominator3. Set Fr3.numerator equal to Fr1.numerator * Fr2.numerator4. Return Fr3End45.See Figure 11.1Figure 11.1Exercise 4547.When an element is to be added to the array, a new array must be allocated and allof the old elements and the new element must be moved to the new array.49.Adding an element to a linked list is easier because a linked list does not have to betotally reallocated.51.Accessing an element of an array is easier because an index can be used.53.Sorting an array is easier because the elements can just be swapped rather thanhaving to redirect up to four different pointers.6CHAPTER 11DATA STRUCTURESSECTION 78CHAPTER 11DATA STRUCTURES。
计算机科学导论原书第二版教学设计课程背景计算机科学导论是计算机专业的一门引导性课程，重点介绍计算机科学的基本概念、基本知识、基本工具和基本方法，以及计算机科学中的最新进展和最新应用。
本课程培养学生具有独立思考和探究的能力，为学生今后的专业学习打好基础。
教学目标1.理解计算机基本概念；2.学习计算机基本知识；3.掌握计算机基本工具；4.掌握计算机科学中的基本方法；5.了解计算机科学中的最新进展和应用。
教学内容第一章：计算机导论1.计算机的定义；2.计算机的发展历程；3.计算机硬件、软件、网络结构和操作系统。
第二章：数制与编码1.二进制、八进制、十进制和十六进制的相互转换；2.字符编码和数字编码；3.错误检测和纠正码。
第三章：计算机组成原理1.计算机的基本组成部分；2.中央处理器（CPU）和内存的组成和工作原理；3.输入输出设备的分类和作用。
第四章：操作系统1.操作系统的概念和分类；2.操作系统的功能和特点；3.操作系统的常用命令和操作。
第五章：计算机网络1.计算机网络的概念和分类；2.网络拓扑结构和传输介质；3.网络协议和通信方式。
第六章：数据库1.数据库的概念和分类；2.关系型数据库和非关系型数据库的特点和比较；3.SQL语言的基本操作和应用。
教学方法本课程采用多元化的教学方法，包括课堂讲解、案例演示、小组讨论、实验操作等。
在讲解理论知识的同时，注重教学与实践相结合，让学生在实践中巩固所学知识。
教材和参考书目1.计算机科学导论（第二版），Timothy Oesker & Linda Null 著，机械工业出版社，2015年；2.数据库系统原理，Silberschatz & Korth & Sudarshan 著，机械工业出版社，2011年；3.操作系统概念，Silberschatz & Galvin & Gagne 著，机械工业出版社，2010年。
评价方式本课程采用综合评价方式，包括课堂出勤、作业和实验成绩、期末考试成绩等。
计算机科学导论考试试题及答案一. 选择题1. 下列哪项不属于计算机科学的研究内容？A. 算法与数据结构B. 网络与通信技术C. 法律与伦理问题D. 人工智能与机器学习2. 下列哪项不是计算机硬件的组成部分？A. 主板B. 显卡C. 操作系统D. CPU3. 以下哪种存储介质具有最高的读写速度？A. 硬盘B. 固态硬盘C. 光盘D. U盘4. 在二进制数系统中，1111的十进制表示为：A. 15B. 14C. 13D. 125. 下列哪项不属于计算机网络的分类？A. 局域网B. 广域网C. 个人网D. 互联网二. 填空题1. 计算机中的最小存储单位为______。
2. HTML是用于______的标记语言。
3. 在计算机中，1KB等于______字节。
4. 执行一个计算机程序时，计算机首先从______读取指令。
5. OSI模型中，位于物理层之上的是______层。
三. 简答题1. 请简述计算机操作系统的作用。
计算机操作系统是控制和管理计算机硬件与软件资源的核心程序。
它的主要作用包括：- 硬件管理：操作系统能够管理计算机的硬件资源，如分配CPU时间片、处理IO请求、管理内存等。
- 软件管理：操作系统可以控制和管理各种软件程序的运行，如进程管理、文件管理、网络管理等。
- 用户接口：操作系统提供与用户交互的界面，使用户能够方便地操作计算机。
- 错误处理：操作系统可以监控和处理计算机系统中的错误和异常情况，保证系统的稳定性和安全性。
2. 解释什么是算法，并举例说明。
算法是解决问题的一系列有限步骤的描述，它可以作为计算机程序的基础。
算法包括输入、输出和执行步骤，用于描述问题的详细解决方法。
举个例子，比如我们要编写一个算法实现两个整数的相加。
算法的步骤如下：1. 输入两个整数a和b。
2. 将a和b相加，得到结果c。
3. 输出结果c。
这个算法通过输入两个整数，执行相加操作，最后输出结果，解决了整数相加的问题。
计算机科学导论以python为舟第三版答案计算机科学导论以python为舟第三版答案第一章：计算机概述- 计算机：是一种能够按照预设程序运行、能够自动、精确、高速处理信息的电子设备- 计算机的历史：从古代的算盘到现代的电子计算机- 计算机的分类：按照性能划分，分为超级计算机、大型计算机、小型计算机、微型计算机和嵌入式计算机- 计算机的发展趋势：集成度逐步提高，体积逐渐缩小，性能逐步强化，应用领域逐渐扩展第二章：Python语言概述- Python是一种高级编程语言，由Guido von Rossum在1989年开发而来- Python语言的特点：简单易学，可读性强，代码量少，模块化管理，流程控制灵活，面向对象编程等- Python语言的版本：Python 2和Python 3，其中以Python 3为主流第三章：Python语言基础- Python语言的标识符、注释、保留字、数据类型和计算表达式- Python语言的流程控制结构：顺序结构、选择结构和循环结构- Python语言的函数：函数定义、调用和参数传递第四章：Python语言高级特性- Python语言的递归算法：递归和非递归实现、递归的应用场景- Python语言的列表、元组、集合和字典：数据结构、操作方法和应用场景- Python语言的文件操作：文件打开、读写、关闭和异常处理第五章：面向对象编程- 面向对象编程的思想和方法：面向对象的三大特征、面向对象的五大原则- Python语言的面向对象编程：类的定义、继承、封装、多态和特殊方法- Python语言的异常处理：异常的类型、捕获和处理、自定义异常类第六章：函数式编程- 函数式编程的思想和方法：纯函数、不可变性、高阶函数、闭包、柯里化、递归和惰性计算- Python语言的函数式编程：匿名函数、高阶函数、map和reduce函数、filter函数、装饰器、生成器和协程总结：计算机科学导论以Python为舟第三版，全面介绍了计算机基础、Python语言概述、Python语言基础、Python语言高级特性、面向对象编程和函数式编程。
