【1】i=i*2; 【1】x++;y--;
}While(x<y);
2
答:(1) n-1, O(n) (2)n,O(n) (3)(n+2)(n-1)/2, O(n )
(4) , O( ) (5)㏒(n-1)+1,O(n) (6)50,O(1)
n n
2 线性表
2.1 回答下列概念:线性结构,线性表,顺序表,单链表,静态链表
线性结构:设 Data_Structure =(D,S),r∈S,相对 r,D 中有且仅有一个开始结点和一个终
端结点,其余的内部结点都有且仅有一个前趋和一个后继,则称 Data_Structure 是相
对 r 的线性结构。
线性表:是具有相同属性的 n(n≥0)个数据元素的有限序列。
顺序表:顺序表(Sequential List)是采用顺序存储结构的线性表。
单链表:每个结点只附加一个指向后继的指针域,这样的链表称为单链表
(Single Linked List)
静态链表:用数组实现的链表,指针就变换为数组的下标,结点即为数组中的下标变量,由于
需要预先分配一个较大的数组空间,因此这种链表称之为静态链表。
2.2 比较顺序表和链表这两种线性表不同存储结构的特点。
1.逻辑关系的表示:顺序表隐含表示关系,链表显示表示关系。
2.存储密度:顺序表的存储密度大,而链表的存储密度小。
3.存储分配方式:顺序表的存储空间是预先静态分配的一块连续存储空间,在程序执行之前必
须明确规定它的存储规模。链表不用事先估计存储规模,动态分配和释放存
储空间,存储空间可连续也可不连续。
4.存取方法:顺序表可以随机存取,链表必须顺序存取。
5.插入、删除操作:在顺序表中做插入、删除时平均移动表中一半的元素;在链表中作插入、
删除时,只要修改指针域,而不需要移动元素。所以顺序表的插入、删除
效率低,链表的插入、删除效率高。
6.实现语言:顺序表容易实现,任何高级语言中都有数组类型。而链表的操作是基于指针的,
对于没有提供指针类型的高级语言,必须采用静态链表。
总之,两种存储结构各有长短,选择那一种由实际问题中的主要因素决定。通常“较稳定”的
线性表选择顺序存储,而频繁做插入、删除的线性表,即动态性较强的线性表宜选择链接存储。
2.3 已知长度为 n 的线性表 A 中的元素是整数,写算法求线性表中值大于 item 的元素个数。分两
种情况编写函数:(1)线性表采用顺序存储;(2)线性表采用单链表存储。
(1)线性表采用顺序存储
#define MAX 1024
typedef int DataType;
typedef struct
{ DataType data[MAX];
int last;
} SeqList;
int LocateElem (SeqList *L, DataType item)
{ int i,j=0;
for(i=0;i<=L->last ;i++)
if( L->data[i] >item ) j++;
return j;}
评论1
最新资源