第1章 绪论
1、填空题
1.常见的数据结构有_线性__结构，__树形___结构，__图形__结构等三种。 2.常见的存储结构有__顺序存储___结构，__链式存储____结构等两种。 3.数据的基本单位是_数据元素__，它在计算机中是作为一个整体来处理的。
4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，__线性结构____和__非线性结构___。
2、应用题
1、给出以下算法的时间复杂度. void fun(int n) {
int i=1,k=100; while(i 时间复杂度为____O（n）_____。 2、给出以下算法的时间复杂度. void fun2(int n) { int i=1,k=100; k=k+1; i=i+2; 1 while(i 时间复杂度为____O（log n）___________。 i=i*10; k=k+1; 第2章 线性表 1、填空题 1. 线性表按照存储结构不同主要有两种实现方式，一种是__顺序_表，另一种是___链___表。 2.顺序表采用__随机___访问机制对数据元素进行访问。 3.若在单链表结点p的后面插入一个新的结点s，则其操作序列为: ①____s->next=p->next_____________； ②____p->next=s___________________； 4.在单向链表中，若要删除某个结点p，一般要找到__p的前趋__结点，才能实现该操作。 2、选择题 1. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数 是 A 。 (A)n (B)2n－1 (C)2n (D)n-1 2. 在单链表中，如果在结点p之后插入一个新结点s，其操作为 A 。 （A）s->next=p->next; p->next=s; （B）p->next=s; s->next=p->next; 2 （C）s->next=p; p->next=s->next; （D）p->next=s; s->next=p; 3.若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复杂度为( C )。(1≤i≤n) A．O(0) B．O(1) C.O(n) D．O(n2) 4. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素需要移动的元素个数为( B )。(1≤i≤n+1) A．n-i B．n-i+1 C. i D．n-i-1 3、判断题 1.线性表中每一个元素都有一个前驱和一个后继。（ × ） 4、程序设计题 1、单链表的结点结构定义如下： struct LinkNode { LinkNode *next; int data; }; 请根据述函数的功能写程序。 void Insert(LinkNode *h,LinkNode *s) {//h指向链表的头结点（即使链表中没有元素，头结点也存在。） //链表中元素已经递增有序 //函数功能为将结点s插入到链表h中。插入后链表仍然保持递增的顺序 LinkNode *p,*q;//q指向p的前驱 q=h; p=h->next; while(p) { if(p->data>s->data) 3