当前位置：文档之家 › 数据结构答案1-5章

数据结构答案1-5章

  • 格式：doc
  • 大小：77.50 KB
  • 文档页数：7

习题练习第一章绪论1、void maxtrixmult (int n,int a[][100],int b[][100],intc[][100]){int j,k,r;int x;for(r=0;r<=n;r++) 1) n+2{for (j=0;j<=n;j++) 2) (n+1)*(n+2){x=0; 3) (n+1)2for(k=1；k<=n;k++) 4) (n+1)3x+=a[r][k]*[k][j]; 5) n* (n+1)2c[r][j]=x; 6) (n+1)2}}}计算时间每条语句的频度和该算法的时间复杂度2．一个算法应该是（ B ）。

【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.3. 下面说法错误的是（ C ）【南京理工大学 2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)4．从逻辑上可以把数据结构分为（ C ）两大类。

【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构5．以下与数据的存储结构无关的术语是（ D ）。

【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈6．连续存储设计时，存储单元的地址（ A ）。

【中山大学 1999 一、1（1分）】A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续7. 数据元素是数据的最小单位。

( F )【北京邮电大学 1998 一、1（2分）】【青岛大学 2000 一、1 （1分）】【上海交通大学 1998 一、1】【山东师范大学 2001 一、1 （2分）】8. 记录是数据处理的最小单位。

( F ) 【上海海运学院 1998 一、5（1分）】9. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。

( F )【华南理工大学 2002 一、2 （1分）】10. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

( F )【上海海运学院 1999 一、1（1分）】11. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( F )【上海海运学院 1998 一、1（1分）】12．一个数据结构在计算机中映像称为存储结构。

【华中理工大学 2000 一、1（1分）】13.下面程序段中带下划线的语句的执行次数的数量级是： log2n 【合肥工业大学1999三、1（2分）】i：=1； WHILE i<n DO i：=i*2;14. 下面程序段中带下划线的语句的执行次数的数量级是(.n )。

【合肥工业大学 2000 三、1（2分）】i:=1;WHILE i<n BEGIN FOR j:=1 TO n DO x:=x+1;i:=i*2 END；第二章线性表1．线性表是具有n个（ C ）的有限序列（n>0）。

【清华大学 1998 一、4（2分）】A．表元素 B．字符 C．数据元素 D．数据项 E．信息项2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

【哈尔滨工业大学 2001 二、1（2分）】A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表3．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

【南开大学 2000 一、3】A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表4．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表5. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。

【北京航空航天大学 1999 一、1（2分）】A. O(0)B. O(1)C. O(n)D. O(n2)6．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）A．O（i） B．O（1） C．O（n） D．O（i-1）【中山大学 1999 一、2】7．非空的循环单链表head的尾结点p↑满足（ A ）。

【武汉大学 2000 二、10】A．p->next=head B．p->next=NIL C．p=NIL D．p= head8．循环链表H的尾结点P的特点是（ A ）。

【中山大学 1998 二、2（2分）】A．P->NEXT=H B．P->NEXT= H->NEXT C．P=H D．P=H->NEXT9．在一个以h 为头的单循环链中，p 指针指向链尾的条件是（A）【南京理工大学1998 一、15（2分）】A. p->next=hB. p->next=NILC. p->next->next=hD. p->data=-110．完成在双循环链表结点p之后插入s的操作是（D ）；【北方交通大学 1999 一、4（3分）】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; s->next=p->next; p->next->priou=s ; p->next=s;11．在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( C )。

【北京邮电大学 1998 二、2（2分）】注:双向链表的结点结构为(llink,data,rlink)。

供选择的答案：A． p->llink=q； q->rlink=p；p->llink->rlink=q； q->llink=q；B． p->llink=q； p->llink->rlink=qq->rlink=p q->llink=p->llink；C． q->rlink=p； q->llink=p->llinkp->llink->rlink=q; p->llink=q;D． q->llink=p->llink； q->rlink=p；p->llink=q； p->llink=q；12. 线性表的特点是每个元素都有一个前驱和一个后继。

( F )【合肥工业大学2001 二、1（1分）】13．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是__（n-1）/2____。

插入是n/2【北方交通大学 2001 二、9】14．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动______N-I+1__个元素。

15、从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（N+1）/2 个结点【北京工商大学 2001 二、4（4分）】16. 带头结点的双循环链表L中只有一个元素结点的条件是：_L->next->next==L ___【合肥工业大学 1999 三、3 2000 三、2（2分）】17. 在单链表L中，指针p所指结点有后继结点的条件是：．p->next!=null__ 【合肥工业大学 2001 三、3 （2分）】18设有一带头结点的单链表,编程将链表颠倒过来.要求不用另外的数组或结点完成.【南京航空航天大学1999 八（10分）】（1）要求编程实现带头结点的单链表的逆置。

首先建立一单链表，然后逆置。

typedef struct node{int data；∥假定结点数据域为整型。

struct node *next；}node,*LinkedList；LinkedList creat（）{LinkedList head，pint x；head=（LinkedList）malloc（sizeof（node））；head->next=null； /*设置头结点*/scanf（“%d”，&x）；while（x!=9999） /*约定输入9999时退出本函数*/{p=（LinkedList）malloc（sizeof（node））；p->data=x；p->next=head->next；/* 将新结点链入链表*/head->next=p；scanf（“%d”，&x）；}return（head）；}∥结束creat函数。

LinkedList invert1（LinkedList head）/*逆置单链表*/{LinkedList p=head->next; /*p为工作指针*/head->next=null；while（p!=null）{r=p->next； /*暂存p的后继*/p->next=head->next；head->next=p；p=r；}return（head）；}/*结束invert1函数*/main（）{LinkedList la；la=creat( ）； /*生成单链表*/la=invert1（la）；/*逆置单链表*/}19、设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。

在链表被起用前，其值均初始化为零。

每当在链表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。

合集下载

数据结构第五章参考答案

数据结构第五章参考答案

习题51.填空题（1）已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为（___________）。

答案：129（2）3个结点可构成（___________）棵不同形态的二叉树。

答案：5（3）设树的度为5，其中度为1~5的结点数分别为6、5、4、3、2个，则该树共有（___________）个叶子。

答案：31（4）在结点个数为n（n>1）的各棵普通树中，高度最小的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。

高度最大的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。

答案：2 n-1 1 n 1 n-1（5）深度为k的二叉树，至多有（___________）个结点。

答案：2k-1（6）（7）有n个结点并且其高度为n的二叉树的数目是（___________）。

答案：2n-1（8）设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为（___________），最小结点数为（___________）。

答案：2k+1-1 k+1（9）将一棵有100个结点的完全二叉树按层编号，则编号为49的结点为X，其双亲PARENT （X）的编号为（）。

答案：24（10）已知一棵完全二叉树中共有768个结点，则该树中共有（___________）个叶子结点。

答案：384（11）（12）已知一棵完全二叉树的第8层有8个结点，则其叶子结点数是（___________）。

答案：68（13）深度为8（根的层次号为1）的满二叉树有（___________）个叶子结点。

答案：128（14）一棵二叉树的前序遍历是FCABED，中序遍历是ACBFED，则后序遍历是（___________）。

答案：ABCDEF（15）某二叉树结点的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则该二叉树结点的前序遍历序列为（___________），该二叉树对应的树林包括（___________）棵树。

数据结构-c语言描述(第二版)答案耿国华编著

数据结构-c语言描述(第二版)答案耿国华编著

第1章绪论2.(1)×(2)×(3)√3.（1）A（2）C（3）C5.计算下列程序中x=x+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;【解答】x=x+1的语句频度为：T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/66.编写算法，求一元多项式p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。

注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。

算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。

讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。

【解答】（1）通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。

缺点：形参须与实参对应，且返回值数量有限。

（2）通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue(){int i,n;float x,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<n;i++)scanf(“%f”,&a[i]);/*执行次数：n次*/p=a[0];for(i=1;i<=n;i++){p=p+a[i]*x;/*执行次数：n次*/x=x*x;}printf(“%f”,p);}算法的时间复杂度：T(n)=O(n)通过参数表中的参数显式传递float PolyValue(float a[],float x,int n){float p,s;int i;p=x;s=a[0];for(i=1;i<=n;i++){s=s+a[i]*p;/*执行次数:n次*/p=p*x;}return(p);}算法的时间复杂度：T(n)=O(n)第2章线性表习题1.填空：(1)在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。

数据结构答案第5章

数据结构答案第5章

第 5 章树和二叉树1970-01-01第 5 章树和二叉树课后习题讲解1. 填空题⑴树是n（n≥0）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成m（m＞0）个（）的集合，每个集合都是根结点的子树。

【解答】有且仅有一个，互不相交⑵树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）。

【解答】度，孩子，双亲⑶一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。

【解答】2i-1，(n+1)/2，(n-1)/2【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。

⑷设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。

【解答】2h -1，2h-1【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。

⑸深度为k的二叉树中，所含叶子的个数最多为（）。

【解答】2k-1【分析】在满二叉树中叶子结点的个数达到最多。

⑹具有100个结点的完全二叉树的叶子结点数为（）。

【解答】50【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。

⑺已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。

则该树中有（）个叶子结点。

【解答】12【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。

⑻某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。

【解答】CDBGFEA【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。

数据结构习题及答案

数据结构习题及答案

数据结构习题及答案第1章算法一、选择题1.算法的时间复杂度是指（）。

A）执行算法程序所需要的时间B）算法程序中的指令条数C）算法执行过程中所需要的基本运算次数D）算法程序的长度2.算法的空间复杂度是指（）。

A）算法程序的长度B）算法程序所占的存储空间C）算法执行过程中所需要的存储空间D）算法程序中的指令条数3.下面（）的时间复杂度最好（即执行时间最短）。

logn)O(）O(n ) B）A2logn2 ) D）O(n)C）O(n24.下面累加求和程序段的时间复杂度为（）。

int sum(int a[],int n){int i, s=0;for (i=0;i<n;i++)< p="">s+=a[i];return s;}logn ) ）O(A）O(1 ) B22)）O(nC）O(n ) D中的算法，c[][]相加的结果存放到b[][]n阶矩阵5.下面是将两个n阶矩阵a[][]与。

该算法的时间复杂度为（）void matrixadd(int a[][],intb[][],c[][],int n){int i,j;for (i=0;i<n;i++)< p="">for(j=0;j<n;j++)< p="">c[i][j]=a[i][j]+b[i][j];}nlog) ）O(1 ) B）O(A22) ）O(nO( n ) DC）。

6.下面程序段的时间复杂度为（） 1int i=0,s1=0,s2=0;while(i<n)< p="">{if(i%2)s1+=i;elses2+=i;i++;}nlog) O(A）O(1 ) B）22) ）O(nC）O(n ) D ）。

7.下面程序段的时间复杂度为（int prime(int n){int i=1;int x=(int)sqrt(n);while(i<=x){i++;if(n%i==0)break;}if(i>x)return 1;elsereturn 0;}nlog) O(O(1 ) BA））2n) O(）CO(n ) D））下面程序段的时间复杂度为（8.int fun(int n){int i=1,s=1;while(s<n)< p="">{i++;s+=i;}return i;}nlog)O(n/2) BA））O(2 2n) ）O(C）O(n ) D9.下面程序段的时间复杂度为（）int i,j,m,n,a[][];for(i=0;i<m;i++)< p="">for(j=0;j<n;j++)< p="">a[i][j]=i*j;22) ）O(nA）O(m) BO(m+n) ）C）O(m*n ) D ）10. 下面程序段的时间复杂度为（int sum1(int n){int i,p=1,s=0;for(i=1;i<=n;i++){p*=i;s=s+p;}return s;}nlog) ）O(A）O(1 ) B22)O(n ) D）O(nC）二、填空题复杂度。