当前位置:文档之家› 数据结构课程__课后习题答案

数据结构课程__课后习题答案

《数据结构简明教程》练习题及参考答案练习题11. 单项选择题(1)线性结构中数据元素之间是()关系。

A.一对多B.多对多C.多对一D.一对一答:D(2)数据结构中与所使用的计算机无关的是数据的()结构。

A.存储B.物理C.逻辑D.物理和存储答:C(3)算法分析的目的是()。

A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性答:C(4)算法分析的两个主要方面是()。

A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性答:A(5)计算机算法指的是()。

A.计算方法B. 排序方法C.求解问题的有限运算序列D.调度方法答:C(6)计算机算法必须具备输入、输出和()等5个特性。

A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性答:B2. 填空题(1)数据结构包括数据的①、数据的②和数据的③这三个方面的内容。

答:①逻辑结构②存储结构③运算数据结构简明教程(2)数据结构按逻辑结构可分为两大类,它们分别是①和②。

答:①线性结构②非线性结构(3)数据结构被形式地定义为(D,R),其中D是①的有限集合,R是D上的②有限集合。

答:①数据元素②关系(4)在线性结构中,第一个结点①前驱结点,其余每个结点有且只有1个前驱结点;最后一个结点②后继结点,其余每个结点有且只有1个后继结点。

答:①没有②没有(5)在树形结构中,树根结点没有①结点,其余每个结点有且只有②个前驱结点;叶子结点没有③结点,其余每个结点的后继结点数可以是④。

答:①前驱②1 ③后继④任意多个(6)在图形结构中,每个结点的前驱结点数和后继结点数可以是()。

答:任意多个(7)数据的存储结构主要有四种,它们分别是①、②、③和④存储结构。

答:①顺序②链式③索引④哈希(8)一个算法的效率可分为①效率和②效率。

答:①时间②空间3. 简答题(1)数据结构和数据类型两个概念之间有区别吗?答:简单地说,数据结构定义了一组按某些关系结合在一起的数组元素的集合。

数据类型不仅定义了一组数据元素,而且还在其上定义了一组操作。

(2)简述线性结构、树形结构和图形结构的不同点。

答:线性结构反映结点间的逻辑关系是一对一的,树形线性结构反映结点间的逻辑关系是一对多的,图在结构反映结点间的逻辑关系是多对多的。

(3)设有采用二元组表示的数据逻辑结构S=(D,R),其中D={a,b,…,i},R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)},问相对于关系R,哪些结点是开始结点,哪些结点是终端结点?答:该逻辑结构为树形结构,其中a结点没有前驱结点,称为根结点,b、e、g、i结点没有后继结点,是终端结点,也称为叶子结点。

(4)以下各函数是算法中语句的执行频度,n为问题规模,给出对应的时间复杂度:T1(n)=n log2n-1000log2nT2(n)=3log2n-1000log2n.. . . . 学习参考 .322T 4(n )=2n log 2n -1000log 2n答:T 1(n )=O(n log 2n ),T 2(n )=O( ),T 3(n )=O(n 2),T 4(n )=O(n log 2n )。

(5)分析下面程序段中循环语句的执行次数。

int j=0,s=0,n=100;do{j=j+1; s=s+10*j;} while (j<n && s<n);答:j =0,第1次循环:j =1,s =10。

第2次循环:j =2,s =30。

第3次循环:j =3,s =60。

第4次循环:j =4,s =100。

while 条件不再满足。

所以,其中循环语句的执行次数为4。

(6)执行下面的语句时,语句s++的执行次数为多少?int s=0; for (i=1;i<n-1;i++)for (j=n;j>=i;j--) s++;答:语句s 的执行次数2)2)(3(3)1()1(12121-+=++-+=+-=∑∑∑-=-==n n n n i n n i n i i n j 。

(7)设n 为问题规模,求以下算法的时间复杂度。

void fun1(int n){int x=0,i;for (i=1;i<=n;i++)for (j=i+1;j<=n;j++)x++;} 答:其中x++语句属基本运算语句,∑∑∑=+==-=-==n i n i j n i n n i n n T 1112)1()(1)(=O(n 2)。

(8)设n 为问题规模,是一个正偶数,试计算以下算法结束时m 的值,并给出该算法的时间复杂度。

void fun2(int n){int m=0;for (i=1;i<=n;i++)for (j=2*i;j<=n;j++)m++;} 答:由于内循环j 的取值范围,所以i ≤n /2,则∑∑∑-===--==2/122/124/))12((n i n i j n i n i n m ,该3log 2n数据结构简明教程程序段的时间复杂度为O(n2)。

上机实验题1有一个整型数组a,其中含有n个元素,设计尽可能好的算法求其中的最大元素和次大元素,并采用相关数据测试。

解:maxs算法用于返回数组a[0..n-1]中的最大元素值max1和次大元素值max2,max1和max2设计为引用类型。

对应的程序如下:#include <stdio.h>void maxs(int a[],int n,int &max1,int &max2){ int i;max1=max2=a[0];for (i=1;i<n;i++)if (a[i]>max1){ max2=max1;max1=a[i];}else if (a[i]>max2)max2=a[i];}void main(){ int a[]={1,4,10,6,8,3,5,7,9,2};int n=10;int max1,max2;maxs(a,n,max1,max2);printf("最大元素值=%d,次大元素值=%d\n",max1,max2);}练习题21. 单项选择题(1)数据在计算机存储器内表示时,物理地址与逻辑地址相对顺序相同并且是连续的,称之为()。

A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构答:C(2)在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是()。

A.访问第i个结点(1≤i≤n)和求第i(2≤i≤n)个结点的前驱结点B.在第i(1≤i≤n)个结点后插入一个新结点.. . .D.将n个结点从小到大排序答:A(3)向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动()个元素。

A.8B.63.5C.63D.7答:B(4)链式存储结构所占存储空间()。

A.分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针B.只有一部分,存放结点值C.只有一部分,存储表示结点间关系的指针D.分两部分,一部分存放结点值,另一部分存放结点所占单元数答:A(5)线性表若采用链式存储结构时,要求内存中可用存储单元的地址()。

A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以答:D(6)一个线性表在()情况下适用于采用链式存储结构。

A.需经常修改其中的结点值B.需不断对其进行删除插入C.其中含有大量的结点D.其中结点结构复杂答:B(7)单链表的存储密度()A.大于1B.等于1C.小于1D.不能确定答:C2. 填空题(1)在顺序表中插入或删除一个元素时,需要平均移动(①)元素,具体移动的元素个数与(②)有关。

答:①表中一半②表长和该元素在表中的位置(2)向一个长度为n的顺序表的第i个元素(1≤i≤n+1)之前插入一个元素时,需向后移动()个元素。

答:n-i+1(3)向一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动()个. 学习参考.数据结构简明教程元素。

答:n-i(4)在顺序表中访问任意一个元素的时间复杂度均为(①),因此顺序表也称为(②)的数据结构。

答:①O(1) ②随机存取(5)顺序表中逻辑上相邻的元素的物理位置(①)相邻。

单链表中逻辑上相邻的元素的物理位置(②)相邻。

答:①一定②不一定(6)在带头结点的单链表中,除头结点外,任一结点的存储位置由()指示。

答:其前驱结点的链域的值(7)在含有n个数据结点的单链表中要删除已知结点*p,需找到它的(①),其时间复杂度为(②)。

答:①前驱结点的地址②O(n)(8)含有n(n>1)个结点的循环双向链表中,为空的指针域数为()。

答:03. 简答题(1)试比较顺序存储结构和链式存储结构的优缺点。

在什么情况下用顺序表比链表好?答:顺序存储结构中,相邻数据元素的存放地址也相邻,并要求内存中可用存储单元的地址必须是连续的。

其优点是存储密度大,存储空间利用率高;缺点是插入或删除元素时不方便。

链式存储结构中,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针。

其优点是插入或删除元素时很方便,使用灵活;缺点是存储密度小,存储空间利用率低。

顺序表适宜于做查找这样的静态操作;链表宜于做插入、删除这样的动态操作。

若线性表的长度变化不大,且其主要操作是查找,则采用顺序表;若线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表。

(2)对于表长为n的顺序表,在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需要移动的元素的平均个数为多少?删除一个元素所需要移动的平均个数为多少?答:插入一个元素所需要移动的元素的平均个数为(n-1)/2,删除一个元素所需要移动的平均个数为n/2。

(3)在链表中设置头结点的作用是什么?.. . .答:在链表中设置头结点后,不管链表是否为空表,头结点指针均不空,并使得对链表的操作(如插入和删除)在各种情况下统一,从而简化了算法的实现过程。

(4)对于双链表和单链表,在两个结点之间插入一个新结点时需修改的指针各为多少个?答:对于双链表,在两个结点之间插入一个新结点时,需修改前驱结点的next域、后继结点的prior域和新插入结点的next、prior域。

所以共修改4个指针。

对于单链表,在两个结点之间插入一个新结点时,需修改前一结点的next域,新插入结点的next域。

所以共修改两个指针。

(5)某含有n(n>1)结点的线性表中,最常用的操作是在尾结点之后插入一个结点和删除第一个结点,则采用以下哪种存储方式最节省运算时间。

相关主题