2024年1月4日发(作者：)

数据结构实用教程答案

【篇一：数据结构实用教程课后习题答案万健c++】

1. b

2. a，d

3. 1，n/2，(n-1)/2，n，0，0

4.

templete class elemtype

void sqlist elemtype :: reverse()

{

elemtype e;

for (int i = 0; i len / 2; i++)

{

e = elem[i];

elem[i] = elem[len – i -1];

elem[len – i – 1] = e;

}

}

templete class elemtype

void linklist elemtype :: reverse()

{

if (!head-next) return;

linknode elemtype *q = head - next, *p = q - next;

q - next = null;

tail = q;

while (p)

{

q = p;

p = p – next;

q – next = head - next;

head - next = q;

}

}

8.

void add(linklist monomial pa, linklist monomial pb)

{

int pa_len, pb_len, i, j;

pa_len = ();

pb_len = ();

i = j = 1;

monomial pa_e, pb_e;

m(pa_e, 1);

m(pb_e, 1);

while (i = pa_len j = pb_len)

{

if (pa_ pb_)

{

i++;

if (i = pa_len) m(pa_e, i);

}

else if (pa_ pb_)

{

(pb_e, i);

i++;

pa_len++;

j++;

if (j = pb_len) m(pb_e, j);

}

else

{

if (pa_ += pb_)

{

m(pa_e, i);

i++;

}

else

{

(pa_e, i);

pa_len--;

}

j++;

if (i = pa_len) m(pa_e, i);

if (j = pb_len) m(pb_e, j);

}

}

while (j = pb_len)

{

m(pb_e, j++);

(pb_e);

}

}

第3章作业参考答案

1.

1,4,3,5,2)能，ioiiiooioo；

(1,4,2,3,5)不能，因为4先于3和2出栈，4出栈时，2和3都在栈中，且2压在3之下，故只能3先出栈才能2出栈。

*若借助栈由输入序列1,2, … , n得到输出序列为p1, p2, …, pn，则在输出序列中不可能出现这样的情形：存在着ijk使pjpkpi。

2. 借助栈t，删除栈s中元素值为k的元素。

4.

//定义双向栈类

template class elemtype//声明一个类模板

class dsqstack

{

public://双向栈类的各成员函数

dsqstack(int m = 100);

~dsqstack();

bool empty(int i) const;

elemtype top(int i) const;

void push(const elemtype e,int i);

void pop(int i);

private: //双向栈类的数据成员

elemtype *base; //基地址指针

int top[2];//栈顶指针

int size; //向量空间大小

};

//构造函数，分配m个结点的顺序空间，构造一个空的双向栈。

template class elemtype

dsqstack elemtype::dsqstack(int m)

{

top[0] = -1; top[1] = m; base = new elemtype[m]; size = m;

}//dsqstack

//析构函数，将栈结构销毁。

template class elemtype

dsqstack elemtype::~dsqstack()

{

if (base != null) delete[] base;

}//~sqstack

//判栈是否为空，若为空，则返回true，否则返回false。

template class elemtype

bool dsqstack elemtype::empty(int i) const

{//i的取值为0或1

if (i == 0)

//取栈顶元素的值。先决条件是栈不空。

template class elemtype

elemtype dsqstack elemtype::top(int i) const

{//i的取值为0或1

return base[top[i]];

}//top

//入栈，若栈满，则先扩展空间。插入e到栈顶。

template class elemtype

void dsqstack elemtype::push(const elemtype e, int i)

{//i的取值为0或1

if (top[0] == top[1] - 1)

{//若栈满，则扩展空间。

elemtype *newbase;

newbase = new elemtype[size + 10];

for(int j = 0; j = top[0]; j++)

newbase[j] = base[j];

for(int k = size - 1; k = top[1]; k--)

newbase[k + 10] = base[k];

delete[] base;

base = newbase;

size += 10;

top[1] += 10;

}

if (i == 0) base[++top[0]] = e; else return top[0] == -1; else

return top[1] == size; }//empty

base[--top[1]] = e;

}//push

//出栈，弹出栈顶元素。先决条件是栈非空。

template class elemtype

void dsqstack elemtype::pop(int i)

{//i的取值为0或1

if (i == 0)

top[0]--;

else

}//pop

5.

(1). a, c, d

(2). 从左到右读序列，任何时候累计i的个数都应大于等于o的个数。

(3).

bool islegal(char *a)

{

int s = 0, n = strlen(s);

for (int i = 0; i n; i++)

{

if (a[i] == “i”)

s++;

else

s--;

if (s 0) return false;

}

return true;

}

7. 借助队列q0和q1，将队列q中的元素重新排列：奇数值元素在前，偶数值元素在后。

8.

类型定义：

typedef struct qnode {

qelemtype data;

struct qnode *next;

} qnode, * qlink;

template class elemtype//声明一个类模板

class cyclinkqueue

{

public://循环链表队列的各成员函数

cyclinkqueue ();//~cyclinkqueue (); top[1]++;

//void clear();

//bool empty() const;

//int length() const;

【篇二：数据结构教程,含习题和答案】

ass=txt>本章的重点是了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。

需要达到识记层次的基本概念和术语有：数据、数据元素、数据项、数据结构。特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。

需要达到领会层次的内容有算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。

--------------------------------------------------------------------------------对于基本概念，仔细看书就能够理解，这里简单提一下：

数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。

数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。

比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。

而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。)

第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。

弄清了以上三个问题，就可以弄清数据结构这个概念。

--------------------------------------------------------------------------------通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构 (这两个很容易理解)

数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。

--------------------------------------------------------------------------------下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。 首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。

当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度t(n)=o(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。

此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。

常见的时间复杂度，按数量级递增排列依次为：常数阶o(1)、对数阶o(log2n)、线性阶o(n)、线性对数阶o(nlog2n)、平方阶o(n^2)、立方阶o(n^3)、k次方阶o(n^k)、指数阶o(2^n)。时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。

数据结构习题一

--------------------------------------------------------------------------------

1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

◆ 数据：指能够被计算机识别、存储和加工处理的信息载体。

◆ 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。

◆ 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

◆ 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

◆ 逻辑结构：指各数据元素之间的逻辑关系。

◆ 存储结构：就是数据的逻辑结构用计算机语言的实现。

◆ 线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。

◆ 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。

--------------------------------------------------------------------------------

1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

◆ 例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。

那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。(所以各位赶快学c语言吧)。

最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。

--------------------------------------------------------------------------------

1.3 常用的存储表示方法有哪几种?

常用的存储表示方法有四种:

◆ 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。

◆ 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。

◆ 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。 ◆ 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。

--------------------------------------------------------------------------------

1.4 设三个函数f,g,h分别为 f(n)=100n^3+n^2+1000 ,

g(n)=25n^3+5000n^2 ,

h(n)=n^1.5+5000nlgn 请判断下列关系是否成立：

(1) f(n)=o(g(n))

(2) g(n)=o(f(n))

(3) h(n)=o(n^1.5)

(4) h(n)=o(nlgn)

◆ (1)成立。

(1)题中两个函数的最高次项都是n^3,因此当n→∞时，两个函数的比值是一个常数，所以这个关系式是成立的。

◆ （2）成立。

◆ （3）成立。

◆ （4）不成立。

--------------------------------------------------------------------------------

1.5 设有两个算法在同一机器上运行，其执行时间分别为100n^2和2^n,要使前者快于后者，n至少要多大?

◆ 15

◇ 最简单最笨的办法就是拿自然数去代呗。假定n取为10，则前者的值是10000，后者的值是1024,小于前者，那我们就加个5，用15代入得前者为22500，后者为32768，已经比前者大但相差不多，那我们再减个1，用14代入得，前者为19600,后者为16384，又比前者小了，所以结果得出来就是n至少要是15.

--------------------------------------------------------------------------------

1.6 设n为正整数，利用大o记号，将下列程序段的执行时间表示为n的函数。

1.6 设n为正整数，利用大o记号，将下列程序段的执行时间表示为n的函数。 (1) i=1; k=0

while(in)

{ k=k+10*i;i++;

} ◆ t(n)=n-1 ∴ t(n)=o(n) ◇ 这个函数是按线性阶递增的

(2) i=0; k=0;

do{

k=k+10*i; i++;

}

while(in);

(3) i=1; j=0;

while(i+j=n)

{

if (ij)j++;

else i++;

} ◆ t(n)=n ∴ t(n)=o(n) ◇ 这也是线性阶递增的 ◆ t(n)=n/2 ∴

t(n)=o(n) ◇ 虽然时间函数是n/2,但其数量级仍是按线性阶递增的。

◆ t(n)=n1/2

(4)x=n; // n1

while (x=(y+1)*(y+1))

y++; ∴ t(n)=o(n1/2) ◇ 最坏的情况是y=0，那么循环的次数是n1/2次，这是一个按平方根阶递增的

函数。

◆ t(n)=o(1)

◇ 这个程序看起来有点吓人，总共循环

运行了1000次，但是我们看到n没有?

没。这段程序的运行是和n无关的，就

算它再循环一万年，我们也不管他，只

是一个常数阶的函数。 (5) x=91; y=100; while(y0) if(x100) {x=x-10;y--;} else x++;

--------------------------------------------------------------------------------

1.7 算法的时间复杂度仅与问题的规模相关吗?

◆ no,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。

--------------------------------------------------------------------------------

1.8 按增长率由小至大的顺序排列下列各函数： 2^100, (2/3)^n，(3/2)^n， n^n , , n! ，2^n ，lgn ,n^lgn, n^(3/2)

◇ 分析如下：2^100 是常数阶； (2/3)^n和 (3/2)^n是指数阶,其中前者是随n的增大而减小的； n^n是指数方阶； √n 是方根阶, n! 就是n(n-1)(n-2)... 就相当于n次方阶；2^n 是指数阶，lgn是对数阶 ,n^lgn是对数方阶, n^(3/2)是3/2次方阶。根据以上分析按增长率由小至大的顺序可排列如下：

【篇三：数据结构教程(第二版)课后答案】

链表的各种基本运算，并在此基础上设计一个主程序完成如下功能。

（1） 初始化单链表h；

（2） 依次采用尾插法插入a,b,c,d,e元素；

（3） 输出单链表h；

（4） 输出单链表h长度；

（5） 判断单链表h是否为空；

（6） 输出单链表h的第3个元素；

（7） 输出元素a的位置；

（8） 在第4个元素位置上插入‘f’元素；

（9） 输出单链表h；

（10） 删除h的第3个元素；

（11） 输出单链表h；

（12） 释放单链表h；

程序：

#includestdio.h

#includemalloc.h

#define true 1

#define false 0

#define ok 1

#define error 0

#define null 0

typedef int status;

typedef int elemtype;

typedef struct lnode {

elemtype data;

struct lnode *next;

}lnode,*linklist;

status initlist_h(linklist h) { //初始化线性表

h=(linklist )malloc(sizeof(lnode)); //h指向头节点，头节点数据域为空

h-next=null;

return ok;

}// initlist_h

status displist_h(linklist h) { //输出线性表

linklist p=h-next;

while(p!=null)

{

printf(%c,p-data);

p=p-next;

}

return ok;

} // displist_h

status createlist_h(linklist h,elemtype a[],int n) { //尾插法建表

linklist s,r;int i;

h=(linklist )malloc(sizeof(lnode));

r=h;

for(i=0;in;i++)

{

s=(linklist )malloc(sizeof(lnode));

s-data=a[i];

r-next=s;

r=s;

}

r-next=null;

return ok;

}// createlist_h

status listlength_h(linklist h) { //求线性表的长度

linklist p=h;int n=0;

while(p-next!=null)

{

n++;

p=p-next;

}

return(n);

}// listlength_h

status listempty_h(linklist h) {//判断单链表是否为空

return(h-next==null);

}// listempty_h

status destroylist_h(linklist h) {//销毁线性表

linklist p=h,q=p-next;

while(q!=null)

{

free(p);

p=q;

q=p-next;

}

free(p);

return ok;

}// destroylist_h

status getelem_h(linklist h, int i, elemtype e) {

// h为带头节点的单链表的头指针。

// 当第i个元素存在时，其值赋给e并返回ok，否则返回error

int j=0;

linklist p=h;

while(jip!=null)

{

j++;p=p-next;

}

if(p==null)

{

return error;

}

else

{

e=p-data;

return ok;

}

}// getelem_h

status listinsert_h(linklist h, int i, elemtype e) { //插入数据元素

int j=0;

linklist p=h,s;

/*

找到插入节点的上一个元素，如果是头节点则退出，当i=1时表示头节点，i=2时，表示第一个元素

*/

while(ji-1p!=null)

{

j++;

p=p-next;

}

if(p==null)

{

return error;

}

else

{

s=(linklist )malloc(sizeof(lnode));

s-data=e;

s-next=p-next;

p-next=s;

return ok;

}

}// listiet_h

status listdelete_h(linklist h, int i, elemtype e) { //删除数据元素

int j=0;

linklist p=h,q;

while(ji-1p!=null) //查找删除元素的前一个节点

{

j++;

p=p-next;

}

if(p==null)

{

return error;

}

else

{

q=p-next;//q为要删除的元素节点

if(q==null)

{

return error;

}

e=q-data;//e为删除节点的数据区域

p-next=q-next;

free(q);

return ok;

}

}// listdelete_h

int locateelem_h(linklist h, elemtype e) {//按元素值查找元素

linklist p=h-next;

int i=1;

while(p!=nullp-data!=e)

{

p=p-next;i++;

}

//如果要插入的节点为头节点，则退出

if(p==null)

{

return error;

}

else

{

return(i);

}

}// locateelem_h

int main() {

elemtype e,a[5]={a,b,c,d,e};

linklist h;

printf((1)初始化单链表hn);

initlist_h(h);//初始化单链表h printf((2)依次采用尾插法插入a,b,c,d,e元素n);

createlist_h(h,a[0],5); //依次采用尾插入法插入a，b，c，d，e元素 printf((3)输出单链表h：);

displist_h(h); //输出单链表h

printf(n);

printf((4)单链表h的长度为：);

if(listempty_h(h))

{

printf((5)该单链表为空n);

}

else

{

printf((5)该单链表不为空n); //判断单链表h是否为空 }

getelem_h(h,3,e);

printf((6)单链表h的第三个元素为：);

printf(%c,e); printf(n); //输出单链表h的第3个元素 printf((7)单链表h中a的位置为：);

printf(%d,locateelem_h(h,a)); //输出元素a的位置

printf(n);

listinsert_h(h,4,f); //在第4个元素位置插入f元素 printf((8)在第4个元素位置上插入 f 元素n);

printf((9)输出单链表h：);

displist_h(h);//输出单链表h

printf(n);

listdelete_h(h,3,e); //删除h的第3个元素 printf((10)删除h的第3个元素n);

printf((11)输出单链表h:); //输出单链表h

displist_h(h);

printf(n);

printf((12)释放单链表hn);

destroylist_h(h);//释放单链表h

return 0;

}