《数据结构课程 课后习题答案（2020年7月整理）.pdf》由会员分享，可在线阅读，更多相关《数据结构课程 课后习题答案（2020年7月整理）.pdf（68页珍藏版）》请在金锄头文库上搜索。
1、 1 1 练习题及参考答案 数据结构简明教程练习题及参考答案 练习题 1 1. 单项选择题 （1）线性结构中数据元素之间是（ ）关系。 A.一对多 B.多对多 C.多对一 D.一对一 答：D （2）数据结构中与所使用的计算机无关的是数据的（ ）结构。 A.存储 B.物理 C.逻辑 D.物理和存储 答：C （3）算法分析的目的是（ ） 。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 答：C （4）算法分析的两个主要方面是（ ） 。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂
2、性 答：A （5）计算机算法指的是（ ） 。 A.计算方法 B. 排序方法 C.求解问题的有限运算序列 D.调度方法 答：C （6）计算机算法必须具备输入、输出和（ ）等 5 个特性。 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 答：B 2. 填空题 （1）数据结构包括数据的 、数据的 和数据的 这三个方面的内容。 答：逻辑结构 存储结构 运算 （2）数据结构按逻辑结构可分为两大类，它们分别是 和 。 答：线性结构 非线性结构 （3）数据结构被形式地定义为（D,R） ，其中 D 是 的有限集合，R 是 D 上的 有 限集合
3、。 数据结构简明教程 2 答：数据元素 关系 （4） 在线性结构中， 第一个结点 前驱结点， 其余每个结点有且只有 1 个前驱结点； 最后一个结点 后继结点，其余每个结点有且只有 1 个后继结点。 答：没有 没有 （5） 在树形结构中， 树根结点没有 结点， 其余每个结点有且只有 个前驱结点； 叶子结点没有 结点，其余每个结点的后继结点数可以是 。 答：前驱 1 后继 任意多个 （6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（ ） 。 答：任意多个 （7）数据的存储结构主要有四种，它们分别是 、 、 和 存储结构。 答：顺序 链式 索引 哈希 （8）一个算法的效率可分为 效率和 效
4、率。 答：时间 空间 3. 简答题 （1）数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据 类型不仅定义了一组数据元素，而且还在其上定义了一组操作。 （2）简述线性结构、树形结构和图形结构的不同点。 答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关 系是一对多的，图在结构反映结点间的逻辑关系是多对多的。 （ 3 ） 设 有 采 用 二 元 组 表 示 的 数 据 逻 辑 结 构 S=(D,R) ， 其 中 D=a,b,i ， R=(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),
5、(f,g),(h,i)，问相对于关系 R，哪些结点是开始结点，哪些结 点是终端结点？ 答：该逻辑结构为树形结构，其中a结点没有前驱结点，称为根结点，b、e、g、i结 点没有后继结点，是终端结点，也称为叶子结点。 （4）以下各函数是算法中语句的执行频度，n为问题规模，给出对应的时间复杂度： T1(n)=nlog2n-1000log2n T2(n)= 3log2 n-1000log2n T3(n)=n 2-1000log 2n T4(n)=2nlog2n-1000log2n 答：T1(n)=O(nlog2n)，T2(n)=O( )，T3(n)=O(n 2)，T 4(n)=O(nlog2n)。 （5
6、）分析下面程序段中循环语句的执行次数。 int j=0,s=0,n=100; do j=j+1; s=s+10*j; while (jn 答：j=0，第1次循环：j=1，s=10。第2次循环：j=2，s=30。第3次循环：j=3，s=60。第4 3log2 n 3 3 练习题及参考答案 次循环：j=4，s=100。while条件不再满足。所以，其中循环语句的执行次数为4。 （6）执行下面的语句时，语句 s+的执行次数为多少？ int s=0; for (i=1;i=i;j-) s+; 答：语句s的执行次数 2 )2)(3( 3) 1() 1(1 2 1 2 1 + =+=+= = = nn n
7、nin n i n i i nj 。 （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 ij n i nn innT 111 2 ) 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+; 答：由于内循环
8、j的取值范围，所以in/2，则 = = 2/ 12 2/ 1 2 4/)12( n i n ij n i ninm，该程序段 的时间复杂度为O(n 2)。 上机实验题 1 有一个整型数组a， 其中含有n个元素， 设计尽可能好的算法求其中的最大元素和次大元素， 并采用相关数据测试。 解： maxs算法用于返回数组a0.n-1中的最大元素值max1和次大元素值max2， max1和max2 设计为引用类型。对应的程序如下： #include void maxs(int a,int n,int max1=max2=a0; for (i=1;imax1) max2=max1; max1=ai; els
9、e if (aimax2) max2=ai; 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,次大元素值=%dn,max1,max2); 练习题 2 1. 单项选择题 （1） 数据在计算机存储器内表示时， 物理地址与逻辑地址相对顺序相同并且是连续的， 称之为（ ） 。 A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构 答：C （2）在n个结点的顺序表中，算法的时间复杂度是 O（1）的操作是（ ） 。 A.访问第i个结点（1in
10、）和求第i（2in）个结点的前驱结点 B.在第i（1in）个结点后插入一个新结点 C.删除第i个结点（1in） D.将n个结点从小到大排序 答：A （3） 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要 移动（ ）个元素。 A.8 B.63.5 C.63 D.7 答：B （4）链式存储结构所占存储空间（ ） 。 A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B.只有一部分，存放结点值 C.只有一部分，存储表示结点间关系的指针 D.分两部分，一部分存放结点值，另一部分存放结点所占单元数 答：A （5）线性表若采用链式存储结构时，要求内存中可用存储单
11、元的地址（ ） 。 5 5 练习题及参考答案 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续或不连续都可以 答：D （6）一个线性表在（ ）情况下适用于采用链式存储结构。 A.需经常修改其中的结点值 B.需不断对其进行删除插入 C.其中含有大量的结点 D.其中结点结构复杂 答：B （7）单链表的存储密度（ ） A.大于 1 B.等于 1 C.小于 1 D.不能确定 答：C 2. 填空题 （1）在顺序表中插入或删除一个元素时，需要平均移动（ ）元素，具体移动的元 素个数与（ ）有关。 答：表中一半 表长和该元素在表中的位置 （2）向一个长度为n的顺序表的第i个元素（1i
12、n+1）之前插入一个元素时，需 向后移动（ ）个元素。 答：n-i+1 （3）向一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动（ ）个 元素。 答：n-i （4）在顺序表中访问任意一个元素的时间复杂度均为（ ） ，因此顺序表也称为 （ ）的数据结构。 答：O(1) 随机存取 （5）顺序表中逻辑上相邻的元素的物理位置（ ）相邻。单链表中逻辑上相邻的元 素的物理位置（ ）相邻。 答：一定 不一定 （6）在带头结点的单链表中，除头结点外，任一结点的存储位置由（ ）指示。 答：其前驱结点的链域的值 （7）在含有n个数据结点的单链表中要删除已知结点*p，需找到它的（ ） ，其时 间复杂度为
13、（ ） 。 答：前驱结点的地址 O(n) （8）含有 n（n1）个结点的循环双向链表中，为空的指针域数为（ ） 。 答：0 3. 简答题 （1）试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表 好？ 答：顺序存储结构中，相邻数据元素的存放地址也相邻，并要求内存中可用存储单元 数据结构简明教程 6 的地址必须是连续的。其优点是存储密度大，存储空间利用率高；缺点是插入或删除元素 时不方便。 链式存储结构中，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放 结点值，另一部分存放表示结点间关系的指针。其优点是插入或删除元素时很方便，使用 灵活；缺点是存储密度小，存储空间利
14、用率低。 顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线 性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大， 且其主要操作是插入、删除操作，则采用链表。 （2）对于表长为n的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个 元素所需要移动的元素的平均个数为多少？删除一个元素所需要移动的平均个数为多少？ 答：插入一个元素所需要移动的元素的平均个数为(n-1)/2，删除一个元素所需要移动的平 均个数为n/2。 （3）在链表中设置头结点的作用是什么？ 答：在链表中设置头结点后，不管链表是否为空表，头结点指针均不空，并使得对链表的 操
15、作（如插入和删除）在各种情况下统一，从而简化了算法的实现过程。 （4）对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个？ 答：对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的next域、后继结 点的prior域和新插入结点的next、prior域。所以共修改4个指针。 对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的next域，新插入结点 的next域。所以共修改两个指针。 （5）某含有n（n1）结点的线性表中，最常用的操作是在尾结点之后插入一个结点和删 除第一个结点，则采用以下哪种存储方式最节省运算时间。 单链表； 仅有头指针不带头结点的循环单
16、链表； 双链表； 仅有尾指针的循环单链表。 答：在单链表中，删除第一个结点的时间复杂度为O(1)。插入结点需找到前驱结点，所以 在尾结点之后插入一个结点，需找到尾结点，对应的时间复杂度为O(n)。 在仅有头指针不带头结点的循环单链表中，删除第一个结点的时间复杂度O(n)，因为删除 第一个结点后还要将其改为循环单链表；在尾结点之后插入一个结点的时间复杂度也为 O(n)。 在双链表中，删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点，也需找 到尾结点，对应的时间复杂度为O(n)。 在仅有尾指针的循环单链表中，通过该尾指针可以直接找到第一个结点，所以删除第一个 结点的时间复杂度为O(1)；在尾结点之
