数据结构c语言课后习题

第一章

一.基础题
1.健壮的算法不会因为非法的输入数据而出现莫名其妙的状态
2.从逻辑结构上可以把数据结构分为线性结构和非线性结构
3.数据采用链式存储，存储单元的地址不一定连续
4.算法的时间复杂度取决于问题规模
5.下列程序段的时间复杂度

for (i=0;i<n;i++)             n
    for (j=0;j<n;j++)         n
        x=x+1;                n^2 -> O(n^2)

二.扩展题
1.简述下列概念:数据、数据元素、数据项。
数据是计算机加工处理的对象；数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理；数据项是组成数据元素的、不可分割的最小单位。

2.什么是数据结构?
数据结构是按某种逻辑关系组织起来的数据元素的集合，使用计算机语言描述并按一定的存储方式存储在计算机中，并在其上定义了一组运算。

3.简述逻辑结构的四种基本关系
集合结构、线性结构、树形结构和图形结构。在集合结构中，元素之间没有关系；线性结构中，元素之间存在一对一的关系；树形结构中，元素之间存在一对多的关系，其中最多只有一个元素没有前驱元素；图形结构，元素之间存在多对多的关系。
4.常见的存储结构有哪些?
顺序结构、链式结构、索引存储和散列存储

5.算法有哪些特征?
一个算法是对特定问题的求解步骤的一种描述，是指令的有限序列，其特征包括:
输入:算法有零个或多个输入
输出:算法至少产生一个输出
确定性:算法的每一条指令都有确切的定义，没有二义性。
可行性:可以通过已经实现的基本运算执行有限次来实现
有穷性:算法必须总能在执行有限步之后终止

6.算法和程序的区别和联系时什么?
联系：程序是计算机指令的有序集合；是算法用某种程序设计语言的表述，是算法在计算机上的具体实现
区别：在语言描述上不同，程序必须是用规定的程序设计语言来写，而算法的描述形式包括自然语言、伪代码、流程图和程序语言等;算法所描述的步骤一定是有限的，而程序可以无限地执行下去，比如一个死循环可以称为程序，但不能称为算法。

7.简述衡量算法优劣的基本标准
正确性:算法的执行结果应当满足功能需求，无语法错误，无逻辑错误
简明性:思路清晰、层次分明、易读易懂，有利于调试维护
健壮性:当输入不合法数据时，应能做适当处理，不至于引起严重后果
效率:有效使用存储空间和有高的时间效率
最优性:解决同一个问题可能有多种算法，应进行比较，选择最佳算法
可使用性:用户友好性

第二章

一.基础题
1.如果线性表最常用的操作是读取第i个元素的值,则采用顺序表存储方式最节省时间
2.对于线性表而言，除第一个元素和最后一个元素外，其余每一个元素都有且仅有一个直接前驱和直接后驱
3.已知顺序表中每个元素占2个存储单位,第一个元素a0在内存中的存储地址是100,则表中元素a5在内存中的存储地址为110
4.线性表采用链式存储结构所具有的特点为插入和删除操作不必移动元素
5.带表头结点的单链表中,first指向表头结点,当first->link == NULL 时，带表头结点的单链表为空。
6.设双向循环链表中结点包括数据域data、左指针域llink和右指针域rlink,若在指针p所指向的结点之后插入指针s所指向的结点,则执行如下操作
s->llink=p;s->rlink=p->rlink;p->rlink->link=s;p->rlink=s;
7.线性表若采用链式存储结构，要求内存中可用存储单元的地址连续或不连续都可以。
8.在单链表中增加表头结点的目的是方便插入和删除运算的实现
9.若某线性表中最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则采用顺序表存储方式最节省时间。
10.循环列表的主要优点是从表中的任意结点出发都能扫描到整个链表

第三章

一.基础题
1.栈和队列的主要区别是限定插入和删除的位置不同。

2.设A,B,C三个元素依次进栈(进栈后可立即出栈)，请写出所有可能的出栈序列。
五种:ABC,ACB,BAC,BCA,CBA

3.阐述栈和队列的特点，并说明他们的作用。
堆栈是先进后出，队列为先进先出。逻辑结构均为线性结构。存储结构既有顺序存储也有链式存储。

4.循环队列的元素存放在数组Q中,M是数组Q的最大长度,队尾指针rear指向队尾元素在Q中的下标值,队头指针front指向对头元素在Q中的下标值-1。写出队列为空和为满的条件。
队列为空:front = rear 队列为满：(rear+1)%M == front

5.利用栈计算下列表达式，指出栈中最多有几个元素，并给出对应的中缀表达式，
(1)5 3 2 * 3 + 3 / +
((3+(23))/3)+5=8
最多三个元素
(2)4 2 4 1 * 1 3 * - ^ 2 1 * / +
2^((41)-(13))/(21)+4=5
最多五个元素

6.写出下列表达式的后缀形式
(1) (a+b)/(c+d) a b + c d + /
(2) b^2-4ac b 2 ^ 4 a * c * -
(3) ac-b/c^2 a c * b c 2 ^ / -
(4) (a+b)c+d/(e+f) a b + c * d e f + / +
(5) (a+b)(cd+e)-a*c a b + c d * e + * a c * -

7.什么是递归，递归算法？比较递归和非递归算法的优缺点。
递归算法是算法过程中存在调用自身的结构，递归算法的优点是程序非常简洁和清晰，且易于分析。但它的缺点是费时间费空间。非递归算法则与之相反。

第四章不知道为什么字符串那部分我没印象，估计老师没讲，课后习题里也没有，跳了

第四章

1.二维数组A[4][3]中数组元素以行优先顺序存储,已知loc(A[0][0])=100,一个数组元素占四个单位存储空间，则数组元素A[3][2]的存储地址为:140 = 100 + (4*2+2)*4
2.三维数组A[5][4][3]中数组元素以行优先顺序存储,已知loc(A[0][0][0])=100,一个数组元素占4个单位存储空间,则数组元素A[2][2][2]的存储地址为:200
3.对10阶对称矩阵A中上三角元素以行优先顺序存储,已知loc(a00)=100,一个矩阵元素占2个单位存储空间，则矩阵元素a76的存储地址为:192
4.对稀疏矩阵进行压缩存储的目的是节省存储空间
5.数组不同于线性表,不便于像线性表一样进行数据元素的插入与删除运算