内容发布更新时间 : 2024/5/18 9:22:25星期一 下面是文章的全部内容请认真阅读。

大理学院成人高等教育 《数据结构》课程作业

1．课程名称：数据结构 2．适用专业：计算机应用技术

3．选用教材：（数据结构），闫玉宝主编，清华大学出版社出版

第一章——第九章 请完成各章的课后习题。

第一章 绪 论 一、问答题

（1）试说明数据结构含义。

（2）叙述四类基本数据结构的名称与含义。 （3）叙述算法的时间复杂度。 （4）叙述数据类型的概念。

（5）叙述线性 结构与非线性结构的差别。

（6）简述结构化程序设计的含义、目的、构成、方法。 （7）叙述面向对象程序设计语言的特点。 （8）在面向对象程序设计中，类的作用是什么？ （9）叙述参数传递的主要方式及特点。 （10）叙述抽象数据类型的概念。

二、判断题（在各题和填写“√”“×”）

（1）线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（ ）

（2）算法就是程序。（ ）

（3）在高级语言（如C或Pascal）中，指针类型是原子类型。（ ）

三、填空题

（1）变量的作用域是指 。

（2）抽象数据类型具有 、 的特点。

（3）一种抽象类型包括 、 和 。

（4）当需要用一个形式参数直接改变对应实参的值时，该形式参数应说明为 。

（5）数据结构的逻辑结构分为 、 、 和 四种。

（6）据结构的存储结构分为 和 两种。

（7）在线性结构、树状结构和图结构中，数据元素之间分别存在着 、 和 联系。

（8）算法是规则的优先集合，是为解决特定问题而规定的 。

（9）算法具有 、确定性、 、 、

输出五大特性。

四、选择题

（1）若需要利用形式参数直接访问修改实参值，则应将形参说明为 参数。

A、指针 B、值参数

（2）执行下面的程序段的时间复杂度为 。 for( i=0;i

A、0（㎡） B、0（n2） C、0（mn） D、0（m+n）

（3）执行下面程序段时，语句S的执行次数为 。 for( i=0;i

A、n2 B、n2 /2 C、n(n+1) D、(n+1) (n+2)/2 5、计算下列程序段中X=X+1的语句频度。 for(i=1;i

6、编写算法，求一个元多项式Pn(x)=a?+a?x+a?x2+a?x3+…+anx?的值Pn（x?）,并确定算法中的每一条语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为ai (i=0,1, …,n) 、x和n,输出为pn(x?)。通常算法的输入和输出可采用下列两种方式之一。

（1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。

试讨论这两种方法的优缺点，并在本题得法中以你认为较好的一种方式实现输入和输出。

7、试总结参数设置规则。在算法的程序实现时，哪些量应设为传值方式？哪些量应作为传地址方式？

8、试总结函数结果带出方式各类。

第二章 线性表 一、填空题

（1）在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。 （2）线性表有顺序存储和链式存储两种存储结构。在顺序表中，线性表的长度在定义数组时就已确定，是 保存；在链式表中，整个链表由“头指针”来表示，单链表的长度是 保存。

（3）顺序表中，逻辑上相邻的元素，其物里位置 相邻。在单链表中，逻辑上相邻的元素，其物里位置 相邻。

（4）在带头结点的非空单链表中，头结点的存储位置由 指示，首元素结点的存储位置由 指示，除首元素结点外，其他任一元素结点的存储位置由 指示。 二、选择题

（1）在线性表中最常用的操作是存取第i元素及其前驱的值，采用 存储方式最省时间。

A、顺序表 B、带头结点的单向链表 C、带头指针的双向循环链表 D、带头指针的单向循环链表

E、带尾指针的单向循环链表

（2）已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。

①在P结点后插入S结点的语句序列是： 。 ②在P结点前插入S结点的语句序列是： 。 ③在表首插入S结点的语句序列是： 。 ④在表尾插入S结点的语句序列是： 。 供选择的语句如下：

A、P->next=S； B、P->next=P->next-next; C、P->next=S->next; D、S->next = P->next ;