数据结构课程--课后习题答案.doc

1、数据结构简明教程练习题及参考答案练习题 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.

2、 排序方法 C.求解问题的有限运算序列 D.调度方法答：C（6）计算机算法必须具备输入、输出和（ ）等 5 个特性。A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性答：B2. 填空题（1）数据结构包括数据的 、数据的 和数据的 这三个方面的内容。答：逻辑结构 存储结构 运算（2）数据结构按逻辑结构可分为两大类，它们分别是 和 。答：线性结构 非线性结构（3）数据结构被形式地定义为（D,R） ，其中 D 是 的有限集合，R 是 D 上的 有限集合。答：数据元素 关系数据结构简明教程（4）在线性结构中，第一个结点 前驱结点，其余每个结

3、点有且只有 1 个前驱结点；最后一个结点 后继结点，其余每个结点有且只有 1 个后继结点。答：没有 没有（5）在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余每个结点的后继结点数可以是 。答：前驱 1 后继 任意多个（6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（ ） 。答：任意多个（7）数据的存储结构主要有四种，它们分别是 、 、 和 存储结构。答：顺序 链式 索引 哈希（8）一个算法的效率可分为 效率和 效率。答：时间 空间3. 简答题（1）数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的

4、数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。（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 结点没有后继结点，是终端结点

5、，也称为叶子结点。（4）以下各函数是算法中语句的执行频度，n 为问题规模，给出对应的时间复杂度：T1(n)=nlog2n-1000log2nT2(n)= -1000log2n3logT3(n)=n2-1000log2nT4(n)=2nlog2n-1000log2n答：T 1(n)=O(nlog2n)，T 2(n)=O( )，T 3(n)=O(n2)，T 4(n)=O(nlog2n)。（5）分析下面程序段中循环语句的执行次数。int j=0,s=0,n=100;do j=j+1;s=s+10*j; while (j=i;j-)s+;答：语句s的执行次数 。2)(3)1()(122 nninini

6、ij （7）设 n 为问题规模，求以下算法的时间复杂度。void fun1(int n) int x=0,i;for (i=1;ivoid maxs(int a,int n,int max1=max2=a0;for (i=1;imax1) max2=max1;max1=ai;else 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);练习题 21. 单项选择题（1）数

7、据在计算机存储器内表示时，物理地址与逻辑地址相对顺序相同并且是连续的，称之为（ ） 。A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构答：C（2）在 n 个结点的顺序表中，算法的时间复杂度是 O（1）的操作是（ ） 。A.访问第 i 个结点（1in）和求第 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.

8、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B.只有一部分，存放结点值C.只有一部分，存储表示结点间关系的指针D.分两部分，一部分存放结点值，另一部分存放结点所占单元数答：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ） 。5练习题及参考答案A.必须是连续的 B.部分地址必须是连续的C.一定是不连续的 D.连续或不连续都可以答：D（6）一个线性表在（ ）情况下适用于采用链式存储结构。A.需经常修改其中的结点值 B.需不断对其进行删除插入C.其中含有大量的结点 D.其中结点结构复杂答：B（7）单链表的存储密度（ ）A.大于 1 B.等于 1 C.小于 1 D

9、.不能确定答：C2. 填空题（1）在顺序表中插入或删除一个元素时，需要平均移动（ ）元素，具体移动的元素个数与（ ）有关。答：表中一半 表长和该元素在表中的位置（2）向一个长度为 n 的顺序表的第 i 个元素（1i n+1）之前插入一个元素时，需向后移动（ ）个元素。答：n-i+1（3）向一个长度为 n 的顺序表中删除第 i 个元素（1i n）时，需向前移动（ ）个元素。答：n-i（4）在顺序表中访问任意一个元素的时间复杂度均为（ ） ，因此顺序表也称为（ ）的数据结构。答：O(1) 随机存取（5）顺序表中逻辑上相邻的元素的物理位置（ ）相邻。单链表中逻辑上相邻的元素的物理位置（ ）相邻。答：

10、一定 不一定（6）在带头结点的单链表中，除头结点外，任一结点的存储位置由（ ）指示。答：其前驱结点的链域的值（7）在含有 n 个数据结点的单链表中要删除已知结点*p，需找到它的（ ） ，其时间复杂度为（ ） 。答：前驱结点的地址 O(n)（8）含有 n（n1）个结点的循环双向链表中，为空的指针域数为（ ） 。答：03. 简答题（1）试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：顺序存储结构中，相邻数据元素的存放地址也相邻，并要求内存中可用存储单元数据结构简明教程的地址必须是连续的。其优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储结构中，

11、相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。其优点是插入或删除元素时很方便，使用灵活；缺点是存储密度小，存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。（2）对于表长为n的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为多少？删除一个元素所需要移动的平均个数为多少？答：插入一个元素所需要移动的元素的平均个数为(n-1)/2 ，删除一个

12、元素所需要移动的平均个数为n/2。（3）在链表中设置头结点的作用是什么？答：在链表中设置头结点后，不管链表是否为空表，头结点指针均不空，并使得对链表的操作（如插入和删除）在各种情况下统一，从而简化了算法的实现过程。（4）对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个？答：对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的next域、后继结点的prior域和新插入结点的next、prior 域。所以共修改 4个指针。对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的next域，新插入结点的next域。所以共修改两个指针。（5）某含有n（n1）结点的线

13、性表中，最常用的操作是在尾结点之后插入一个结点和删除第一个结点，则采用以下哪种存储方式最节省运算时间。单链表；仅有头指针不带头结点的循环单链表；双链表；仅有尾指针的循环单链表。答：在单链表中，删除第一个结点的时间复杂度为O(1)。插入结点需找到前驱结点，所以在尾结点之后插入一个结点，需找到尾结点，对应的时间复杂度为O(n) 。在仅有头指针不带头结点的循环单链表中，删除第一个结点的时间复杂度O(n) ，因为删除第一个结点后还要将其改为循环单链表；在尾结点之后插入一个结点的时间复杂度也为O(n)。在双链表中，删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点，也需找到尾结点，对应的时间

14、复杂度为O(n) 。在仅有尾指针的循环单链表中，通过该尾指针可以直接找到第一个结点，所以删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点也就是在尾指针所指结点之后插入一个结点，时间复杂度也为O(1)。因此最节省运算时间。7练习题及参考答案4. 算法设计题（1）设计一个高效算法，将顺序表的所有元素逆置，要求算法空间复杂度为 O(1)。解：遍历顺序表 L 的前半部分元素，对于元素 L.datai（0iL.length/2） ，将其与后半部分对应元素 L.dataL.length-i-1进行交换。对应的算法如下：void reverse(SqList ElemType x;for (i

15、=0;ij) /表示L.datai和L.data0.j 中所有元素都不相同 j+;L.dataj=L.datai;L.length=j+1; /顺序表长度置新值本算法的时间复杂度为 O(n2)，空间复杂度为 O(1)。（3）设计一个算法从有序顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。解：在有序顺序表 L 中，所有重复的元素应是相邻存放的，用 k 保存不重复出现的元素个数，先将不重复的有序区看成是 L.data0.0，置 e=L.data0，用 i 从 1 开始遍历 L 的所有元素：当 L.dataie 时，将它放在 L.datak中，k 增 1，置 e=L.datai，最后将

16、L 的length 置为 k。对应的算法如下：void delsame1(SqList /k保存不重复的元素个数数据结构简明教程ElemType e;e=L.data0;for (i=1;inext; /p指向*q的前驱结点while (q!=NULL q=q-next;if (q!=NULL) /找到值为x的结点 p-next=q-next;free(q);return 1;else return 0; /未找到值为x的结点（5）设计一个算法判定单链表 L 是否是递增的。解：判定链表 L 从第 2 个结点开始的每个结点的值是否比其前驱的值大。若有一个不成立，则整个链表便不是递增的；否则是递增

17、的。对应的算法如下：int increase(SLink *L) SLink *pre=L-next,*p; /pre指向第一个数据结点p=pre-next; /p指向*pre结点的后继结点while (p!=NULL) if (p-data=pre-data) /若正序则继续判断下一个结点 pre=p; /pre、p同步后移p=p-next;else return 0;9练习题及参考答案return 1;（6）有一个整数元素建立的单链表 A，设计一个算法，将其拆分成两个单链表 A 和B，使得 A 单链表中含有所有的偶数结点，B 单链表中所有的奇数结点，且保持原来的相对次序。解：采用重新单链表

18、的方法，由于要保持相对次序，所以采用尾插法建立新表A、B 。用 p 遍历原单链表 A 的所有数据结点，若为偶数结点，将其链到 A 中，若为奇数结点，将其链到 B 中。对应的算法如下：void Split(SLink *ra=A;B=(SLink *)malloc(sizeof(SLink); /建立头结点rb=B; /r总是指向B链表的尾结点while (p!=NULL) if (p-data%2=0) /偶数结点 ra-next=p; /将*p结点链到A中ra=p;p=p-next;else /奇数结点 rb-next=p; /将*p结点链到B中rb=p;p=p-next;ra-next=r

19、b-next=NULL;本算法的时间复杂度为 O(n)，空间复杂度为 O(1)。（7）有一个有序单链表（从小到大排列） ，表头指针为 L，设计一个算法向该单链表中插入一个元素为 x 的结点，使插入后该链表仍然有序。解：先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。对应的算法如下：void inorderList(SLink *s=(SLink *)malloc(sizeof(SLink); /建立一个待插入的结点s-data=x;s-next=NULL;if (L=NULL | xdata) /若单链表为空或x小于第1个结点date域

20、s-next=L; /把*s结点插入到头结点之后L=s;else q=L; /寻找插入位置,p指向待比较的结点,q指向p的前驱结点数据结构简明教程p=q-next;while (p!=NULL p=p-next;s-next=p; /将s结点插入到*q和*p之间q-next=s;（8）有一个单链表 L，其中可能出现值域重复的结点，设计一个算法删除值域重复的结点。并分析算法的时间复杂度。解：用 p 遍历单链表，用 r 遍历 *p 结点之后的结点，q 始终指向*r 结点的直接前驱结点，若 r-data=p-data，则删除*r 结点，否则 q、r 同步后移一个结点。对应的算法如下：void dels1(SLink *while (p!=NULL) q=p;r=q-next;while (r!=NULL) if (r-data=p-data) /r指向被删结点 t=r-next;q-next=t;free(r);r=t;else q=r;r=r-next;p=p-next;本算法的时间复杂度为 O(n2)。（9）有一个递增有序单链表（允许出现值域重复的结点） ，设计一个算法删除值域重复的结点。并分析算法的时间复杂度。解：由于是有序表，所以相同值域的结点都是相邻的。用 p 遍历递增单链表，若*p结点的值域等于其后结点的值域，则删除后者。对应的算法如下：void dels(SLink *