【综合文库】
《数据结构简明教程》练习题及参考答案
练习题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.数据复杂性和程序复杂性 答:A
(5)计算机算法指的是( )。 A.计算方法 B. 排序方法C.求解问题的有限运算序列 D.调度方法 答:C
(6)计算机算法必须具备输入、输出和( )等5个特性。 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性D.易读性、稳定性和安全性 答:B 2. 填空题
(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)=nlog2n-1000log2n T2(n)=nlog23-1000log2n T3(n)=n2-1000log2n
T4(n)=2nlog2n-1000log2n
3答:T1(n)=O(nlog2n),T2(n)=O( n log2 ),T3(n)=O(n2),T4(n)=O(nlog2n)。 (5)分析下面程序段中循环语句的执行次数。
int j=0,s=0,n=100; do {
j=j+1; s=s+10*j;
} while (j 答: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 for (j=n;j>=i;j--) s++; n?2in?2i?1答:语句s的执行次数??1??(n?i?1)?n?(n?1)???3?i?1j?n(n?3)(n?2)。 2(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++语句属基本运算语句,T(n)???1??(n?i)?i?1j?i?1i?1nnnn(n?1)=O(n2)。 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++; n/2nn/2i?1答:由于内循环j的取值范围,所以i≤n/2,则m?????(n?(2i?1))?n2/4,该程 i?1j?2i序段的时间复杂度为O(n2)。 上机实验题1 有一个整型数组a,其中含有n个元素,设计尽可能好的算法求其中的最大元素和次大元素,并采用相关数据测试。 解:maxs算法用于返回数组a[0..n-1]中的最大元素值max1和次大元素值max2,max1和max2设计为引用类型。对应的程序如下: #include void maxs(int a[],int n,int &max1,int &max2) { int i; max1=max2=a[0]; for (i=1;i 3 数据结构简明教程 } 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\ if (a[i]>max1) {} else if (a[i]>max2) max2=a[i]; max2=max1; max1=a[i]; 练习题2 1. 单项选择题 (1)数据在计算机存储器内表示时,物理地址与逻辑地址相对顺序相同并且是连续的,称之为( )。 A.存储结构 B.逻辑结构 C.顺序存储结构D.链式存储结构 答:C (2)在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是( )。 A.访问第i个结点(1≤i≤n)和求第i(2≤i≤n)个结点的前驱结点 B.在第i(1≤i≤n)个结点后插入一个新结点 C.删除第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.等于1 C.小于1D.不能确定 答:C 2. 填空题 (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)个结点的循环双向链表中,为空的指针域数为( )。 答:0 3. 简答题 (1)试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好? 答:顺序存储结构中,相邻数据元素的存放地址也相邻,并要求内存中可用存储单元 5 查看全文