数据结构算法设计题库及答案_数据结构的算法设计题资源-CSDN文库

需积分: 50 200 浏览量 2013-06-25 15:59:56 上传评论 3 收藏 1.66MB DOC 举报

资源推荐

资源详情

资源评论

第一章绪论

一填空题

数据结构包括数据的逻辑结构、数据的存储结构和 数据的运算  。

数据的逻辑结构可以分为 线性和非线性两大类型。

在算法正确的前提下，评价一个算法好坏的两个主要标准是时间复杂度和空间复杂度。

对于给定的  个元素可以构造出的逻辑结构有线性、树形、图形和集合四种。

数据的存储结构不仅有顺序存储结构、链式存储结构，还有 索引存储结构和 散列存储

结构。

组成数据的基本单位是数据元素。

数据结构的两个要素是 数据元素和 数据元素之间的关系 。

语句频度是语句重复执行的次数。

算法是 对特定问题求解步骤的一种描述，是指令的有限序列。

数值计算问题是 操作对象之间的关系可以用数学方程加以描述的问题；非数值计算问

题是 操作对象之间的关系不能用数学方程加以描述的问题  。

程序是 算法在计算机上的特定的实现。

抽象数据类型是 指一个数学模型以及定义在该模型上的一组操作。

学习数据结构课程的目的是 非数值计算问题的程序设计。

算法可用 自然语言、流程图、 N-S

图、计算机语言、伪码语言等描述。

存储密度是 一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。

二简答题

试说明算法与程序有哪些区别？

答：至少有四点区别：

（1）程序不一定满足有穷性(如操作系统)；

（2）程序中的指令必须是机器可执行的，算法中的指令则无此限制；

（3）算法代表了对问题的解，程序则是算法在计算机上的特定的实现(一个算法若用程

序设计语言来描述，它才是一个程序);

（4）数据结构+算法=程序。

举一个数据结构的例子，叙述其逻辑结构、存储结构和运算（操作）三方面的内容。

答：例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记

成的表，这个表就是一个数据结构。每个记录（有姓名、学号、成绩等项）就是一个结点

对于整个表来说，只有一个开始结点（它的前面无记录）和一个终端结点（它的后面无记

录），其它的结点则各有一个也只有一个直接前趋和直接后继（它的前面和后面均有且只有

一个记录）。这几个关系就确定了这个表的逻辑结构——线性结构。

那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间

的关系呢? 是用一片连续的内存单元来存放这些记录（如用数组存储，亦即顺序存储）还

是随机存放各结点数据再用指针进行链接（链式存储）呢? 这就是存储结构的问题，我们

都是从高级语言的层次来讨论这个问题的。

最后，我们有了这个表（数据结构），肯定要用它，那么就是要对这张表中的记录进行

查询、修改、删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的

运算（操作）问题了。

什么叫算法效率？如何度量算法效率？

答：算法效率包括时间效率和空间效率。时间效率指算法运行得有多快；空间效率关心算

法需要的额外空间。算法效率通常用时间复杂度和空间复杂度来度量。

数据的逻辑结构与存储结构的区别和联系是什么？

答：区别：数据的逻辑结构是一个

数学模型；

数据的存储结构是数据的逻辑结构在计算机

内部的

存储方式。

联系：一种逻辑结构可以用多种存储结构来存储；一种存储结构可以用来存多种逻辑

结构。

算法有什么特性？评价一个算法有几个标准？

答：一个算法应该具有以下五个特性：

(1)有穷性。一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成

(有限步完成）。

(2)确定性。算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入

口和一个出口（无二义性）。

(3)可行性。一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算

执行有限次来实现的（每一步都可通过执行有限次基本操作实现）。

(4)输入性。一个算法有零个或多个输入,这些输入取自于某个特定的对象集合(有零个

或多个输入）。

(5)输出性。一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量

（有一个或多个输出）。

评价一个算法有以下几个标准:

(1) 正确性。算法应满足具体问题的需求。

(2) 可读性。算法应该好读。以有利于阅读者对程序的理解。

(3) 健壮性。算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是

产生莫名其妙的输出结果。

(4) 高效性。指算法执行的时间和执行过程中所需要的最大存储空间要少。一般，这两

者与问题的规模有关。

第二章顺序表

一填空题

当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取

线性表中的元素时，应采用顺序存储结构。

线性表 （…）用数组表示，假定删除表中任一元素的概率相同，则删除一个

元素平均需要移动元素的个数是（ n-1 ） /2 。

顺序表中查找某个元素时，从前到后查找与从后到前查找的时间复杂度相同。

在具有  个元素的顺序表中插入一个元素，合法的插入位置有 n+1 个。

在一个长度为 的顺序表中第 个元素（）之前插入一个元素时，需向后移动 n-

i+1 个元素。

顺序存储结构的线性表中所有元素的地址一定连续。

顺序存储结构的线性表其物理结构与逻辑结构是一致的。

在具有  个元素的顺序存储结构的线性表任意一个位置中插入一个元素，在等概率条件

下，平均需要移动 n/2 个元素。

在具有  个元素的顺序存储结构的线性表任意一个位置中删除一个元素，在等概率条件

下，平均需要移动（ n-1 ） /2 个元素。

在具有  个元素的顺序存储结构的线性表中查找某个元素平均需要比较（ n + 1 ） /2

次。

顺序存储结构的线性表中，插入或删除某个元素时，元素移动的次数与其位置有关

（填有或无）。

顺序存储结构的线性表中，访问第  个元素与其位置 无关。（填有或无）。

在具有  个元素的顺序存储结构的线性表中要访问第  个元素的时间复杂度是 。

在顺序表  中的  个位置插入某个元素 ，正常插入时， 位置以及  位置以后的元素需

要后移，首先后移的是最后一个元素。

要删除顺序表  中的  位置的元素 ，正常删除时， 位置以后的元素需要前移，首先前

移的是第

i+1

个元素或

i+1

位置上的元素 。

在具有  个元素的顺序存储结构的线性表中插入某个元素的时间复杂度是 。

若顺序表中的元素是从  位置开始存放的，要删除具有  个元素的顺序表中某个元素，

合法的删除位置是 1

到

n 。

在具有  个元素的顺序存储结构的线性表中删除某个元素的时间复杂度是 。

二简答题

下列算法完成在顺序表  的第  个位置插入元素 ，正常插入返回 ，否则返回  或

，请在空的下划线上填写合适的内容完成该算法。

 !"#

$%&

'()*+,表满,

$#-./0)'1))2/&

-1-&3

)'44(()5,位置不对,

$#-./0#6768)92/&

-1-&3

),正常插入,

$'6-%()&%(&%

( 9:%5; ( 9:%;& ,元素后移,

( 9:;& ,插入元素,

()55&,表长加 ,

-1-&

3

下列算法完成删除顺序表  的第  个元素，元素类型为 !"#，其值通过参数 # 返

回，请在空的下划线上填写合适的内容完成该算法。

9)， !"# # 

$%&

'（(),表空,

$#-./0)*#"2/&-1-&3

)'44(() ,位置不对,

$#-./20#6768)9/&-1-&3

),正常删除,

$#(9:;&,删除元素通过参数 #返回,

'6-%5&%()&%55

( 9:%; ( 9:%; &,元素前移,

()()&,表长减 ,

-1-&3

什么是线性表？线性表有什么特点？

答：线性表是具有相同数据类型的 n（ ³ 0）个数据元素的有限序列。线性表除第一个元素

外，其它每一个元素有一个且仅有一个直接前驱；除最后一个元素外，其它每一个元素有

一个且仅有一个直接后继。

设有一整型顺序表 ，元素从位置  开始存放，下列算法实现将以第一个元素为基准，将

其放置在表中合适的位置，使得其前面的元素都比它小，后面的元素均大于等于该元素。

请在空的下划线上填写合适的内容完成该算法。

869#-

$ %&,循环变量声明,

&

 (9: ;& ,将第一个元素置入  中,

'6-&()&55

'(9: ; ,当前元素小于基准元素,

$(9:;(9:;&,当前元素暂存在  位置,

'6-%&%(&%,当前元素前面所有元素后移,

(9:%5;(9:%;&

(9: ;(9: ;&,当前元素从  位置移到最前面,

3

3

什么是顺序存储结构？顺序存储结构的优点和缺点各是什么？

答：顺序存储结构是把逻辑上相邻的元素存储在物理位置相邻的存储单元中。通常用数组

实现。

顺序存储有三个优点:

（1）方法简单，用数组，容易实现。

（2）不用为表示结点的逻辑关系而增加额外开销。

（3）具有按元素序号随机访问的特点。

顺序存储有两个缺点：

（1）进行插入、删除时，平均移动表中一半的元素，效率较低。

（2）需预先分配足够大的存储空间。空间估计过大，会导致空间闲置（造成浪费）；预

先分配过小，又会造成溢出。

三程序设计题

  在顺序存储结构的职工工资表中，职工工资信息包括：职工号（ 6 ）、姓名

（*）、

职称（#-6）、工资（ )）等四项信息，请编写一完整的程序，实现以下功能：

（）创建信息表：从键盘读入所有职工的信息。（ 分）

（）删除：给定职工号，删除该职工的信息。（ 分）

（）修改：对职称为“教授”的职工工资加 。（  分）

（）在显示器（屏幕）上显示所有职工的各项信息。（ 分）

（）主程序以菜单的方式调用以上功能。（ 分）

元素类型及顺序表类型定义如下：

"#9'-1<

$<0-6:;*:;#-6:;&

=6)；

3 !"#&

"#9'-1<

$ !"#9:>?@AB5;；

)&

3&

图书管每本图书包含：书号（6）、书名（ *）、现存量（ C1*）、总库存量

（1*

1*）四项信息，编写完整程序通过顺序表实现：

（）初始化：录入现有的所有图书的四项信息。（ 分）

（）借书：每本书每次只能借一本，如果库中有该书，则允许借阅并使该书的现存

量

减 ，否则给出相应提示信息。（ 分）

（）价值估算：统计库中所有书的价钱。价钱为所有书的单价乘以库存量的累加和。

（ 分）

（）显示：显示图书管所有藏书信息。（ 分）

（）主程序以菜单的方式调用以上功能。（ 分）

元素类型及顺序表类型定义  分。

设有两个整型顺序表 ，，其元素值递增有序存放，请定义该顺序表的元素类型及表

类型（ 分）；设计以下自定义函数：

（）录入顺序表中所有元素的值。（ 分）

（）将顺序表 ， 合并为到另外一个顺序表  中， 中的元素非递减有序排列。

（ 分）

（）输出顺序表中元素的值。（ 分）

主函数通过调用以上函数实现两个表的合并并显示合并结果。（ 分）

有一个职工基本信息管理，职工信息包含：职工号、姓名、性别；编写完整程序，实现

如下功能：

录入函数 #1D从键盘读入职工信息。 分）

删除函数 9)D给定职工号删除该职工的信息。 分

插入函数 -：假定表中职工信息按职工号升序排列，任意给定一职工信息，

使得插入后依然有序。 分

主函数以菜单形式调用以上功能，类型定义  分，主函数  分。

有一个学生信息包含：学号 6〈主关键字〉；姓名 *；英语成绩 <6-。定义学生信

息类型 !"# 及顺序表类型 &

录入函数 #1D从键盘读入学生信息。（ 分）

查找函数 -<0：任意给定一个学号，查找其英语成绩，将其成绩通过函数返回，

若找不到，返回。（  分）

插入函数 -：假定表中学生信息按学号升序排列，任意给定一学生信息，使得

插

剩余63页未读，继续阅读

评论收藏

内容反馈

gabralia007

粉丝: 0
资源: 4

数据结构算法设计题库及答案

数据结构试题及答案

数据结构算法设计题集

数据结构与算法设计习题与答案

数据结构与算法 题库答案

数据结构习题及答案

数据结构算法设计笔试面试题

非常经典的数据结构和算法习题和答案

数据结构与算法考试复习试题和答案

算法设计和分析题目和源代码.doc

百度，微软等数据结构+算法经典面试100题（集锦版，含答案）

数据结构与算法设计试卷及答案

数据结构试题库集及答案

算法与数据结构考试题库

数据结构与算法试题及答案

C语言期末考试题库+十套数据结构与算法试题及答案+实验报告.zip

《数据结构(c语言版)习题集》算法设计题答案

数据结构习题库及答案word版

数据结构题库与答案 （C语言版）

数据结构与算法经典习题

数据结构与算法视频课程（59集）

数据结构教程（第5版）课后题参考答案，第四章串

目前最完整的数据结构1800题包括完整答案.rar

常见算法题库

面试算法题库

《数据结构与算法》期末考试试题及答案.docx

算法与数据结构考研试题精析

数据结构试题库及答案.docx

数据结构\数据结构考研试题精选及答案

数据结构与算法试题及答案.docx

最新资源

数据结构与算法题库答案

数据结构题库与答案（C语言版）