C.分析算法的效率以求改进 答：CD.分析算法的易懂性和文档性（5）计算机算法指的是 （）。

答：C答：B 2. 填空题答：①逻辑结构 ②存储结构 ③运算数据结构简明教程》练习题及参考答案练习题11.单项选择题（1）线性结构中数据元素之间是 （）关系。

A. 一对多 B.多对多C.多对一答：DD.—对一（2）数据结构中与所使用的计算机无关的是数据的A.存储B.物理 答：CC •逻辑（）结构。

D.物理和存储（3）算法分析的目的是 （A.找出数据结构的合理性）。

B.研究算法中的输入和输出的关系 （4）算法分析的两个主要方面是）。

A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性答：AD.数据复杂性和程序复杂性A.计算方法B.排序方法C •求解问题的有限运算序列 D.调度方法（6）计算机算法必须具备输入 A. 可行性、可移植性和可扩充性、输出和（）等5个特性。

B. 可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性（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, •★},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为问题规模，给出对应的时间复杂度：「（n）=n log 2n-1000log 2nT2（n）= n log23-1000log 2n专业word可编辑数据结构简明教程T 3(n )=n 2-1000log 2n T 4(n )=2 n log 2n -lOOOIog 2n答：T i (n )=O( n log 2n ), T 2(n )=O(n Iog23 ), T 3(n )=0( n 2), T 4(n )=0( 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 的执行次数 fn i 1) -n (n 1)…• 3 -(n 3)(n- 2)。

i =1 j =Bi =12(7)设n 为问题规模 ,求以下算法的时间复杂度 。

void fun1(int n) { int x=0,i; for (i=1;i<=n;i++)for (j=i+1;j<=n;j++)x++;n n n，T(n)八 1 八(n_i )二且口 =o ( n 2)。

2i土 j ±1i士(8)设n 为问题规模，是一个正偶数，试计算以下算法结束时 法的时间复杂度void fun2(int n) { int m=0;for (i=1;i<=n;i++)for (j=2*i;j<=n;j++)m++;}n/ 2 n n/ 2 答：由于内循环j 的取值范围,所以i <n /2 ,则'二、(n -(2i T))二n 2/4 ,该\-4 j =2iil程序段的时间复杂度为 O(n 2)。

}答：其中x++语句属基本运算语句m 的值，并给出该算上机实验题1有一个整型数组a,其中含有n个元素，设计尽可能好的算法求其中的最大元素和次大元素，并采用相关数据测试。

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

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

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

A. 访问第i个结点(1 wiwn)和求第i (2<i<n)个结点的前驱结点B. 在第i (1 <i<n)个结点后插入一个新结点专业word可编辑数据结构简明教程C. 删除第i 个结点（1<i <n ）D. 将n 个结点从小到大排序 答：A（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变 ，平均要移动（）个元素。

（4）链式存储结构所占存储空间 （）。

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

A.必须是连续的B.部分地址必须是连续的C. 一定是不连续的D.连续或不连续都可以答：D（6） 一个线性表在（）情况下适用于采用链式存储结构 A.需经常修改其中的结点值 C.其中含有大量的结点 答：B（7）单链表的存储密度 （） A. 大于1 B 等于1 答：C 2. 填空题（1 ）在顺序表中插入或删除一个元素时 ，需要平均移动（①）元素，具体移动的元素个数与（②）有关。

答：①表中一半 ②表长和该元素在表中的位置（2）向一个长度为n 的顺序表的第i 个元素（1 £<n +1 ）之前插入一个元素时，需向 后移动（）个元素。

答：n -i +1兀素。

A.8 答：BB.63.5C.63D.7B.需不断对其进行删除插入 D.其中结点结构复杂C.小于1D.不能确定（3）向一个长度为 n 的顺序表中删除第 i 个元素（1 £ w n ）时，需向前移动（）个答：n-i（4）在顺序表中访问任意一个元素的时间复杂度均为（① ），因此顺序表也称为（② ）的数据结构。

答：①0（1）②随机存取（5）顺序表中逻辑上相邻的元素的物理位置（① ）相邻。

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

答：①一定②不一定（6）在带头结点的单链表中，除头结点外，任一结点的存储位置由（）指示。

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

答：①前驱结点的地址②0（n）（8）含有n（n>1 ）个结点的循环双向链表中，为空的指针域数为（）。

答：03. 简答题（1 ）试比较顺序存储结构和链式存储结构的优缺点。

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

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

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

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

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

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

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

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

(4)对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个？答：对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的next域、后专业word可编辑数据结构简明教程继结点的prior域和新插入结点的next、prior域。