数据结构作业解答

1、C. 解决问题的步骤序列 D. 调度方B. 可执行性、确定性、有穷性D. 易读性、稳定性、平安性C .要满足五个根本特性D . A和C.C. 算法的可行性是指指令不能有二义性D.以上几个都是错误的第一章作业 一、选择题1. 算法的计算量的大小称为计算的( B )。A. 效率 B.复杂性 C. 现实性D.难度2. 算法的时间复杂度取决于(A)A. 问题的规模 B.待处理数据的初态C. A 和B3. 计算机算法指的是(C),它必须具备(B)这三个特性。(1) A .计算方法 B. 排序方法 法(2) A .可执行性、可移植性、可扩充性C. 确定性、有穷性、稳定性4. 一个算法应该是(B )。A .

2、程序 B .问题求解步骤的描述5. 下面关于算法说法错误的选项是( D )A算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的6. 下面说法错误的选项是( C )(1 )算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下，复杂度0(n)的算法在时间上总是优于复杂度0(2)的算法( 3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界( 4)同一个算法，实现语言的级别越高，执行效率就越低A(1)B.(1),(2) C.(1),(4)D.(3)7从逻辑上可以把数据结构分为(C )两大类。A. 动态结构、静态结构B.顺序结构、链式结构C.

3、线性结构、非线性结构D.初等结构、构造型结构&在下面的程序段中，对x的赋值语句的频度为(D )F0R i:=1 T0 n D0F0R j:=1 T0 n D0x:=x+1;A 0(2n)B 0(n) C0(n2)D 0(log 2n)9程序段 F0R i:=n-1 D0WNT0 1 D0F0R j:=1 T0 i D0IF Aj>Aj+1THEN Aj与 Aj+1 对换；其中 n 为正整数，那么最后一行的语句频度在最坏情况下是( D )32A. 0 ( n) B. 0(nlogn) C. 0(n3) D. 0(n2)二、判断题1. 数据元素是数据的最小单位。 ( X )2. 记录

4、是数据处理的最小单位。 (X )3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系； (X )4算法的优劣与算法描述语言无关，但与所用计算机有关。(V )5健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( X )6. 算法可以用不同的语言描述，如果用 C语言或PASCAL语言等高级语言来描述，那么算法 实际上就是程序了。 ( X )7. 程序一定是算法。( X )8. 数据的物理结构是指数据在计算机内的实际存储形式。(V )9. 数据结构的抽象操作的定义与具体实现有关。 (X )10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。( X )11. 顺序存储方式的优点是存储密度

5、大，且插入、删除运算效率高。( X )三、用C语言程序完成三元组的初始化、取i号位上的值及修改i号位上的值。#include<stdio.h>#include<stdlib.h>#define ok 1#define error -1 typedef int *triplet; typedef int status;status init(triplet *t,int v1,int v2,int v3) *t=(int *)malloc(3*sizeof(int);if (!(*t) return error;(*t)0=v1;(*t)1=v2;(*t)2=v3;ret

6、urn ok;status get(triplet t,int i,int *e) if(i<1|i>3) return error;*e=ti-1 ;return ok;void main() triplet a; int i,e,e1,e2,e3;int b; printf(" 输入三元组的三个值 :"); scanf("%d%d%d",&e1,&e2,&e3); b=init(&a,e1,e2,e3);if(b=1)printf("%5d,%5d,%5dn",a0,a1,a2);els

7、e printf(" 创立三元组失败 n"); printf(" 输入取得三元组元素的位置 :"); scanf("%d",&i);b=get(a,i,&e);if(b=1) printf("%5dn" ,e); else printf(" 位置错误 n");第二章作业一 选择题1下述哪一条是顺序存储结构的优点？A A.存储密度大 B 插入运算方便 C 删除运算方便 D 可方便地用于各种逻辑结构 的存储表示2下面关于线性表的表达中，错误的选项是哪一个？B A. 线性表采用顺序存储

8、，必须占用一片连续的存储单元。B. 线性表采用顺序存储，便于进行插入和删除操作。C. 线性表采用链接存储，不必占用一片连续的存储单元。D. 线性表采用链接存储，便于插入和删除操作。3.线性表是具有 门个C 的有限序列n >0。A.表元素B .字符 C .数据元素 D .数据项 E.信息项4假设某线性表最常用的操作是存取任 一指定序号的元素和在最后进行插入和删除运算， 那么利用 A 存储方式最节省时间。A.顺序表B .双链表C .带头结点的双循环链表D .单循环链表5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素， 那么采用 D 存储方式最节省运算时间。A.单链表

9、B 仅有头指针的单循环链表C 双链表D 仅有尾指针的单循环链表6设一个链表最常用的操作是在末尾插入结点和删除尾结点，那么选用 D 最节省时间。A. 单链表 B. 单循环链表 C. 带尾指针的单循环链表 D. 带头结点的双循环链表 7假设某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。那么采用D 存储方式最节省运算时间。A单链表B 双链表C 单循环链表D 带头结点的双循环链表8.静态链表中指针表示的是 C).A内存地址B 数组下标C 下一元素地址D 左 、右孩子地址9.链表不具有的特点是B A插入、删除不需要移动元素B 可随机访问任一元素C不必事先估计存储空间D 所需空间与线

10、性长度成正比10. 下面的表达不正确的选项是 B,C)A线性表在链式存储时，查找第i个元素的时间同i 的值成正比B.线性表在链式存储时，查找第 i个元素的时间同i 的值无关C.线性表在顺序存储时，查找第 i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关12. (1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以 ， 它存取表中第 i 个元 素的时间与 i 无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的选项是( B )A (

11、 1)，(2) B ( 1) C ( 1)，(2) ,(3) D.(2)13. 假设长度为 n 的线性表采用顺序存储结构， 在其第 i 个位置插入一个新元素的算法的时间 复杂度为( C ) (1<=i<=n+1) 。2A. O(0) B. O(1)C. O(n)D. O(n2)14. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( C )。AO(n) O(n)B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)15. 线性表(a1,a2,an )以链接方式存储时，访问第i位置元素的时间复杂性为(C )A O( i )B16.非空的循环单链表.

12、 O( 1 ) C . O( n ) head 的尾结点 p 满足( AO( i-1 )。A. p->link=head Bp->link=NILL Cp=NILL D . p= head17循环链表H的尾结点P的特点是(A )。A . P»NEXT:=HBP»NEXT:= HA.NEXTP:=H D . P:=HA.NEXT18. 在一个以 h 为头的单循环链中， p 指针指向链尾的条件是(A)A. p->next=h B. p->next=NULLL C. p->next->next=h D. p->data=-119. 完成在

13、双循环链表结点p 之后插入 s 的操作是( D )；A. p->next:=s ; s->priou:=p; p->next->priou:=s ; s->next:=p->next;B. p ->next ->priou:=s; p ->next:=s; s ->priou:=p; s ->next:= p->next;C. s ->priou:=p; s ->next:=p->next; p->next:=s; p->next->priou:=s ;D. s->priou:=p

14、; s->next:=p->next; p->next->priou:=s ; p->next:=s; 二、判断I. 链表中的头结点仅起到标识的作用。(X )2顺序存储结构的主要缺点是不利于插入或删除操作。(V )3 .线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(V )4. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( X )5. 对任何数据结构链式存储结构一定优于顺序存储结构。(X )6 .顺序存储方式只能用于存储线性结构。 ( X )7. 集合与线性表的区别在于是否按关键字排序。(X )8. 所谓静态链表就是一直不发生变化

15、的链表。(X )9. 线性表的特点是每个元素都有一个前驱和一个后继。 (X )10. 取线性表的第 i 个元素的时间同 i 的大小有关 . ( X )II. 循环链表不是线性表 . ( X )12. 线性表只能用顺序存储结构实现。 (X )13. 线性表就是顺序存储的表。 ( X )14. 为了很方便的插入和删除数据，可以使用双向链表存放数据。( V )15. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( X )16. 链表是采用链式存储结构的线性表 , 进行插入、删除操作时，在链表中比在顺序存储结 构中效率高。 ( V )三、编写以下算法：1、将两个单链表合并成一个单链表。vo

16、id merge(ListLink &La,ListLink &Lb)p=La->next;while(p->next) p=p->next;p->next=Lb->next;free(Lb);2、 有一个有序单链表(从小到大)，表头指针为head,编写一个算法向该单链表中插入一个元素值为 x 的结点，使插入后该链表依然有序。void insert(LinkList &head, ElemType x)p=head;while(p->next &&p->next<x) p=p->next;s= ( L

17、inkList ) malloc( sizeof ( LNode ) ;s->data=x;s->next= p->next ;p->next =s ;3、用算法是实现带头结点的单链表数据结点逆置。(原链表为a1, a2,an)(逆置后为：an,an-1,a2,a1)void server(LinkList &L)p=L->next; L->next=NULL;while(p) r=p->next;/ 将 p 的后继结点的地址保存在 r 中p->next=L->next;/ 将 p 卸下来，每次插在 L 之和，第一个结点之前L-&g

18、t;next=p;p=r;/ 复原 pA。如果对这个队列重复执第三章作业1、 设队列中有 A、B、C、D、E 这五个元素，其中队首元素为行以下4 步操作：(1)输出队首元素；( 2)把队首元素值插入到队尾；( 3)删除队首元素；( 4)再次删除队首元素。直到队列为空为止，求得到的输出序列。 ACECC(1)输出A ,队列为ABCDEA(3)队列为 BCDEA ( 4)队列为 CDEA 重复：( 1)输出 C， (2)队列为 CDEAC(3)队列为 DEAC ( 4)队列为 EAC 重复：( 1)输出 E， (2)队列为 EACE(3)队列为ACE (4)队列为CE重复：( 1)输出 C， (2

19、)队列为 CC(3)队列为 C( 4)队列为空得到的输出序列： ACECC2、假设以带头结点的循环链表表示队列，并且只设一个尾指针rear 指向队尾元素结点(注意不设头指针) ，试编写相应的队列初始化、入队列和出队列的算法。void initqueue ( LinkList &rear )/ 初始化队列为空队列rear= ( LinkList ) malloc( sizeof ( LNode ) ;rear->next=rear;void inqueue ( LinkList &rear ,ElemTypee)/ 入队列s= ( LinkList ) malloc( si

20、zeof ( LNode ) ;s->data=e;p->next=rear->next;rear->next=p;rear=p;void Delqueue ( LinkList &rear ,ElemType &e )/出队列if(rear->next=rear) printf( “队列为空 )；elsep=rear- >n ext- >n ext;rearr- >n ext-> next=p-> next; free(p);第六章作业1二叉树的前序序列为 ABDGCEFI和中序序列 GDHBECIF，求后序序列。Q

21、A/ OB OC/ / OD OEOF/ /OG 0H 012、对二叉树中的结点进行按层次顺序 每一层自左至右的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。现一棵二叉树的层次序列为 ABCDEFGHIJ,中序序列为DBGEHJACIF请画出此二叉树。OA/ OB OC/ OD OE OF/ /GO H0 01OJ3、对以下图所示的森林：(1)求森林的前序序列和后序序列; 将此森林转换为相应的二叉树;(1)此森林的前序序列:此森林的后序序列：ABCDEFGHIJKLMPQRNOBDEFCAIJKHGQRPMNOLA Qa,b,c,d,e,f,g,h中的字母构成,4、假设

22、用于通信的电文由字符集现的概率分别为 0.07,0.19 , 0.02 , 0.06 ,0.32, 0.03 , 0.21 ,0 .10这8个字母在电文中出(1)试构造哈夫曼树。(2)写出这8个字母的哈夫曼编码。哈夫曼编码图见题图 根据上图可得编码表:注意r每冼含并后要重新撐序取最小的两令值再合并.根据上图可得编码表：a:0010b:10c:00000d:0001e:01f:00001g:11h:00115、算法设计：用先序遍历和中根序遍历的思想统计叶子结点的个数。解法一：先序遍历int Leaf ( Bitree t )int static n=0;if(t) if(t->lchild=NULL&&t->rchild=NULL) n+;Leaf(t->lchild);Leaf(t->lchild);return n;解法一：中序遍历int n=0 ；void Leaf ( Bitree t )if(t) Leaf(t->lchild); if(t->lchild=NULL