《数据结构》作业习题
班级：学号：姓名：
《数据结构》习题
习题一 绪 论
1、数据结构主要研究的三个内容为 、 以及定义在该结构上的 。
2、数据结构从逻辑结构上可分为线性结构与非线性结构，其中树、图属于 。 3、数据结构被形式地定义为（D，R），其中D是 的有限集，R是D上的 有限集。
4、程序作用是利用swap函数，实现main函数中变量a与b的值的交换。填写空缺使代码完整。
void swap( ) { int temp;
; ; ; }
int main( ) { int a=7,b=11;
printf(\ swap( ); printf(\ }
5、函数triangleArea的作用是：根据三角形的三条边a、b、c，求三角形的面积。求三角形面积的公式为s(s?a)(s?b)(s?c)，其中s=(a+b+c)/2。要求函数返回值类型定义为状态类型（Status 类型），当给定的三条边不能构成三角形时，函数返回ERROR；否则函数返回OK，并利用引用类型参数返回三角形的面积。填写空缺使代码完整。
triangleArea( double a, double b, double c, area) { double s;
if(a+b<=c||a+c<=b||b+c<=a) return ; else
{ s=(a+b+c)/2;
=sqrt(s*(s-a)*(s-b)*(s-c)); return ; }
6、设有定义如下：
typedef struct stuInfo{ int num; char name[20]; char sex;
struct stuInfo *next; } stuType;
1
《数据结构》习题
（1）利用指针变量stus,实现一个能容纳40个stuType类型元素动态数组。实现该功能正确的代码为：
stuType *stus;
stus=( )malloc( ); （2）从内存中分配两个stuType类型的结点空间，其指针分别为p、q。按注释给出相应功能的正确代码：
stuType *p, *q;
p=( )malloc( );//分配p结点 q=( )malloc( );//分配q结点 ;//p结点的next指针指向q结点 ;//q结点的next指针指向空 ;//利用p给p结点的学号赋为1 ;//利用p给q结点的学号赋为2 ;//释放p结点空间
7、给出以下给定的两个程序段中划波浪线的语句的执行频度（次数）与时间复杂度。 （1） sum=0;
for(i=0;i for(j=0; j 8、分析以下各程序段的时间复杂度为（用大O记号表示） （1） i=s=0; while(s s+=i; } T(n)= （2）i=1; while(i<=n) i=i*3; T(n)= （2）sum=0; for(i=0;i 2 《数据结构》习题 习题二 线性表 1、n(n>=0)个元素的线性结构表示成(a1，a2,……an)，a1称为______元素，an称为______元素，i称为ai在线性表中的____________。对任意一对相邻结点ai、ai+1(1<=i 2、在表长为n的顺序表的第i个位置插入一元素（1<=i<=n+1，插入的新元素作为第i个元素），则涉及到的元素的移动次数为 ；若删除第i（1<=i<=n）个元素，则涉及到的元素的移动次数为 。 3、线性表的顺序存储结构（顺序表）其存储空间 。 A) 必须是连续的 B) 部分是连续的C) 一定是不连续的 D) 连续不连续都可以 4、一个顺序表的第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。 A）110 B）108 C）100 D）120 5、顺序表的存取特点为 ，单链表的存取特点为 。 6、对于顺序表的优缺点，以下说法错误的是（ ） A）无需为表示结点间的逻辑关系而增加额外的存储空间; B）可以方便地随机存取表中的任一结点; C）插人和删除运算较方便; D）容易造成一部分空间长期闲置而得不到充分利用; 7、以下说法正确的是（ ） A）线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继。 B）线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低。 C）在顺序表中，插入和删除元素时，移动元素的个数与插入或删除位置有关。 D）顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动。 8、以下说法正确的是（ ） A）顺序存储方式的优点是存储密度大、且插入、删除运算效率高 B）链表的每个结点中都恰好包含一个指针 C）线性表的顺序存储结构优于链式存储结构 D）顺序存储结构属于静态结构，链式结构属于动态结构 9、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ） 2