数据结构作业习题答案 修订

发布 2022-09-02 22:23:28 阅读 6557

第二章线性表。

a. (4 ) 1 )

b. (7 ) 11 ) 8 ) 4 ) 1 )

c. (5 ) 12 )

d. (11 ) 9 ) 1 ) 6 ) 或 ( 11 ) 9 ) 6 ) 1 )或( 11 ) 9 ) 6 ) 1 )

a. (11 ) 3 ) 4 )

b. (10 ) 12 ) 8 ) 11 ) 3 ) 14 )或( 10 ) 12 ) 8 ) 3 ) 14 )

c. (10 ) 12 ) 7) (3 ) 14 )

d. (10 ) 12 ) 13 ) 14 ) 或(12) (11) (3) (14)

e. (9 ) 11 ) 3 ) 14 )

1) 如果l的长度不小于2,则将首元结点删去并插入到表尾。

2) void bb():用*s所指结点的值替换*q所指结点的值。

void aa():将*pa与*pb所指结点的值交换。

或将单循环链表拆成两个单循环链表。

status insertorderlist(sqlist &va,elemtype x)

//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法。

int i;

if(for(i=>0,x<

return ok;

int length (linklist l)//求链表的长度。

for (k=0,p=l;p->next;p=p->next,k++)

return k;

//length

int listlength_l(linklist &l)

int i=0;

linklist p=l;

if(p) p=p-next;

while(p)

return i;

void reverse(sqlist &a)//顺序表的就地逆置。

for(i=1,j=

//reverse

status listoppose_sq(sqlist &l)

int i;

elemtype x;

for(i=0;i

return ok;

void linklist_reverse(linklist &l)//链表的就地逆置;为简化算法,假设表长大于2

p=l->next;q=p->next;s=q->next;p->next=null;

while(s->next)

q->next=p;s->next=q;l->next=s;

//linklist_reverse

status listoppose_l(linklist &l)

linklist p,q;

p=l;p=p->next;

l->next=null;

while(p)

return ok;

void reverse_merge(linklist &a,linklist &b,linklist &c)//把元素递增排列的链表a和b合并为c,且c中元素递减排列,使用原空间。

pa=a->next;pb=b->next;pre=null; /pa和pb分别指向a,b的当前元素。

while(pa||pb)

elsepre=pc;

c=a;a->next=pc; /构造新表头。

//reverse_merge

status listmergeoppose_l(linklist &a,linklist &b,linklist &c)

linklist pa,pb,qa,qb;

pa=a;pb=b;

qa=pa; /保存pa的前驱指针。

qb=pb; /保存pb的前驱指针。

pa=pa->next;

pb=pb->next;

a->next=null;

c=a;while(pa&&pb)else

while(pa)

while(pb)

pb=b;free(pb);

return ok;

第三章栈和队列。

2) 可以得到,不可能得到,因为 ’4356’ 出栈说明12已在栈中,则1不可能在2之前出栈。

输出结果:stack

1) 利用数组a 将栈s中的所有值实现逆置。

2) 利用栈t辅助将栈s中所有值为e的数据元素删除之。

void digui (int j)

if (j>1)

printf (j);

digui (j-1);

//digui

void test (int &sum)

stack s;

int x;

scanf (x);

initstack (s);

while (x)

push (s,x);

scanf (x);

sum=0;

printf (sum);

while (pop (s,x))

sum+=x;

printf (sum);

status g (int m,int n,int &s) /求递归函数g的值s

if (m==0&&n>=0) s=0;

else if(m>0&&n>=0) s=n+g(m-1,2*n);

else return error;

return ok;

//g int g(int m,int n);

int main()

int m,n;

cout<<"请输入m和n的值:";

cin>>m>>n;

if(n>=0) cout< else cout<<"no solution!";

return 0;

int g(int m,int n)

if(m>0)

return(g(m-1,2*n)+n);

else return 0;

假设主函数的返回地址为0,递归函数3条语句的地址分别为。第四章串。

s=’this sample is’

t=’a good’

v=’this sample is a good one’

strlength(s)=14

index(v,g)=3

index(u,g)=0

t=’these are books’

v=’yxy’

u=’xwxwxw’

typedef struct mytype;

void stranalyze (stringtype s) /统计串s中字符的种类和个数。

mytype t[maxsize]; 用结构数组t存储统计结果。

for (i=1;i<=s[0];i++)

}//for

for (j=0;t[j].ch;j++)

printf ("c:%d",t[j].ch,t[j].num);

//stranalyze

int substring_delete (stringtype &s,stringtype t) /从串s中删除所有与t相同的子串,并返回删除次数。

for (n=0,i=1;i<=s[0]-t[0]+1;i++)

//forreturn n;

//delete_substring

第五章数组与广义表。

6×8×6=288 byte

loc(5,7)=1000+(5×8+7)×6=1282

loc(1,4)=1000+(1×8+4)×6=1072

loc(4,7)=1000+(7×6+4)×6=1276

loc(0,0,0,0)=100

loc(1,1,1,1)=100+(1×3×5×8 + 1×5×8 + 1×8 + 1)×4=776

loc(3,1,2,5)=100+(3×3×5×8 + 1×5×8 + 2×8 + 5)×4=1784

loc(8,2,4,7)=100+(8×3×5×8 + 2×5×8 + 4×8 + 7)×4=4416

则得记a+b为add (a,b),一种写法为。

第六章树和二叉树。

a) 空二叉树。

只有一个结点的二叉树。

只有右子树的单支二叉树。

b) 空二叉树。

只有一个结点的二叉树。

数据结构课后作业答案

1.画出下图所示的无向图的邻接表。列出深度优先和广度优先搜索遍历该图所的顶点序列和边的序列。邻接表 深度优先搜索 顶点序列 1 2 3 4 5 6 边的序列 1,2 2,3 3,4 4,5 5,6 广度优先搜索 顶点序列 1 2 3 6 5 4 边的序列 1,2 1,3 1,6 1,5 5,4 2 ...

数据结构作业

数据结构作业 下周三交。题目描述 二叉排序树,也称为二叉查找树。可以是一颗空树,也可以是一颗具有如下特性的非空二叉树 1.若左子树非空,则左子树上所有节点关键字值均不大于根节点的关键字值 2.若右子树非空,则右子树上所有节点关键字值均不小于根节点的关键字值 3.左 右子树本身也是一颗二叉排序树。现在...

数据结构作业

数据结构 作业一。1 1什么是数据?它与信息是什么关系?1 2什么是数据结构?有关数据结构的讨论涉及哪三个方面?1 3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组 链表 栈 队列 优先级队列等 非线性结构包括树 图等 数据结构 作业一。1 1什么是数据?它与信息是什么关系?1 2什...