第 1 章绪论送母亲什么花
1.1什么是数据结构？
【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。
1.2 数据结构涉及哪几个方面？
【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集合。
1.3 两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？
口舌之争【答】：不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是不一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样，所以它们是两种不同的数据结构。
1.4 线性结构的特点是什么？非线性结构的特点是什么？
【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点，元素之间的关系可以是一对多的或多对多的。
1.5 数据结构的存储方式有哪几种？
【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。
1.6 算法有哪些特点？它和程序的主要区别是什么？
【答】：算法具有（1）有穷性（2）确定性（3）0个或多个输入（4）1个或多个输出（5）可行性等特征。程序是算法的一种描述方式，通过程序可以在计算机上实现算法。
1.7 抽象数据类型的是什么？它有什么特点？
【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用
者依据这些描述使用抽象数据类型。
1.8 算法的时间复杂度指的是什么？如何表示？
【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n的数据处理问题，用T(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写 O符号表示算法的时间复杂度，大写 O符号给出了函数 f的一个上限。其它义如下：
定义：f (n)=O (g (n)) 当且仅当存在正的常数 c和 n0，使得对于所有的n≥n0，有f (n) ≤c g(n)。
2
上述定义表明，函数 f顶多是函数g的 c倍，除非 n 小于 n0。因此对于足够大的 n (如n≥n0)，g是f 的一个上限（不考虑常数因子c）。在为函数f 提供一个上限函数g 时，通常使用比较简单的函数形式。比较典型的形式是含有n的单个项（带一个常数系数）。表1-1列出了一些常用的g函数及其名称。对于
表1-1中的对数函数logn，没有给出对数基，原因是对于任何大于1的常数a和b都有log a n =log b n/log b a，所以log a n和log b n都有一个相对的乘法系数1/log b a，其中 a是一个常量。
表 1-1常用的渐进函数
函数名称
1 常数
海蛎包logn 对数
n 线性
nlogn n个 logn
n2 平方
n3 立方
2n 指数
n! 阶乘
1.9 算法的空间复杂度指的是什么？如何表示？
【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表示为问题规模的函数，并通过大写O符号表示空间复杂度。
1.10 对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度T(n)。
（1） i++;
（2） for(i=0;i<n;i++)
if (a[i]<x) x=a[i];
（3）for(i=0;i<n;i++)
for(j=0;j<n;j++)
printf(“%d”,i+j);
（4）for (i=1;i<=n-1;i++)
{ k=i;
for(j=i+1;j<=n;j++)
if(a[j]>a[j+1]) k=j;
t=a[k]; a[k]=a[i]; a[i]=t;
}
（5）for(i=0;i<n;i++)
for(j=0;j<n;j++)
{++x;s=s+x;}
【答】：（1）O（1）；（2）O（n）；（3）O（n2）；（4）O（n2）；（5）O（n2）
夜半歌声歌词
3
第 2 章线性表及其顺序存储
2.2什么是顺序表？什么是栈？什么是队列？
【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具有先进先出，后进后出的特点。
2.3设计一个算法，求顺序表中值为 x的结点的个数。
【答】：顺序表的存储结构定义如下（文件名qlist.h）：
#include <stdio.h>
#define N 100 /*预定义最大的数据域空间*/
typedef int datatype; /*假设数据类型为整型*/
typedef struct {
datatype data[N]; /*此处假设数据元素只包含一个整型的关键字域*/
int length; /*线性表长度*/
} qlist; /*预定义的顺序表类型*/
算法 countx（L,x）用于求顺序表 L中值为 x的结点的个数。int
countx(qlist *L,datatype x)
{ int c=0;
int i;
for (i=0;i<L->length;i++)
if (L->data[i]==x) c++;
return c;
}
2.4 设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组a中，倒置
的结果是使得数组 a中的 a[0]等于原来的最后一个元素，a[1] 等于原来的倒数第 2个元素，…，
a的最后一个元素等于原来的第一个元素。
【答】：顺序表的存储结构定义同题 2.3，实现顺序表倒置的算法程序如下：void
verge(qlist *L)
{int t,i,j;
i=0;
j=L->length-1;
while (i<j)
{ t=L->data[i];
L->data[i++]=L->data[j];
L->data[j--]=t;
}
}
2.5已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为 x的结点，使
顺序表中的结点仍然是从小到大有序。
【答】：顺序表的定义同题 2.3，实现本题要求的算法程序如下：
void inrtx(qlist *L,datatype x)
{int j;
if (L->length<N)
{ j=L->length-1;
while (j>=0 && L->data[j]>x)
{ L->data[j+1]=L->data[j];
j--;
}
L->data[j+1]=x;
L->length++;
}
}
2.6 将下列中缀表达式转换为等价的后缀表达式。
(1) 5+6*7
(2) (5-6)/7
(3) 5-6*7*8
(4) 5*7-8
(5) 5*(7-6)+8/9
(6) 7*(5-6*8)-9
【答】：韦庄简介
(7) 5+6*7 后缀表达式：5 6 7*+
屈原的作品有哪些(8) (5-6)/7 后缀表达式：5 6-7/
(9) 5-6*7*8 后缀表达式：5 6 7*8*-
(10)5*7-8 后缀表达式：5 7* 8-
(11)5*(7-6)+8/9 后缀表达式：5 7 6-*8 9/+
(12)7*(5-6*8)-9 后缀表达式：7 5 6 8*-*9-
2.7 循环队列存储在一个数组中，数组大小为 n，队首指针和队尾指针分别为 front和 rear，请写出求循环队列中当前结点个数的表达式。
【答】：循环队列中当前结点个数的计算公式是：(n+rear-front)%n
2.8编号为1,2,3,4的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果有n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。【答】：
方法一：
算法思想：逐次输出所有可能，用回溯法。即：
总体：对原始序列中的每一个元素，总是先入栈，后出栈
1．入栈后的操作：a.该元素出栈；b.下一个元素入栈；
2．出栈后的操作：a.（栈中其他元素）继续出栈；b. （原始序列中）下一个数入栈；
注意：回溯法，关键在于回溯，即在某分支结点X：处理X的一个子分支，再退回分支X，接着处理 X的下一个子分支，若所有 X的子分支处理完，再退回上一层分支节点。所谓“退回”，
6
实际上就是恢复。
程序代码：(2_8_1.c)
#include <stdio.h>
#define MAX 26
typedef struct s{
char a[MAX];
int top;
}Stack;
/*定义一些全局变量*/
Stack S; /*定义全局性的栈*/
char d[MAX],q[MAX]; /*d[MAX]用于存储原始入栈序列，q[MAX]用于存储输出序列*/
int len; /*定义将通过栈的元素个数*/
int count=0; /* 用于统计输出序列的个数 */
void initStack(Stack *S) /*初始化空栈*/
{ S->top=-1; }
void push(Stack *S, char x) /*进栈*/
{ if (S->top>=MAX) return;
S->top++;
持之以恒作文S->a[S->top]=x;
}
char pop(Stack *S)/*出栈*/
{ if (S->top==-1)
{ printf("ERROR, POP Empty Stack");
return -1;
}
S->top--;
return S->a[S->top+1];
}
跟陌生人说话int isEmpty(Stack *S)/*判断栈是否为空*/
{ if (S->top==-1) return 1;
return 0;
}
void outSeq(char *q, int len)/*输出顶点序列*/
{ int i;
for(i=0; i<len; i++)
printf("%2c",q[i]);
printf("\n");
}
void scheduler(int pos, int q_pos)
7
