发布时间 : 星期一 文章数据结构复习更新完毕开始阅读bc2fb713be1e650e52ea9984
}
}
本算法的时间复杂度为O(1)。
（3）算法如下：
void maxmin(int a[], int n, int &max, int &min) { int k;
min=a[0]; max=a[0]; for(k=1;k if(a[k]>max) max=a[k]; else if(a[k] 本算法的时间复杂度为O(n)。 例题：设n是3的倍数，分析以下算法的时间复杂度（需给出推导过程）。 void fun(int n) { int i, j, x, y; for(i=0; i<=n;i++) if(3*i<=n) for(j=3*i; j<=n; j++) { x++; y=3*x+2; } } 第2章线性表 基本知识点：线性表的逻辑结构特征，线性表的基本运算，线性表的两种存储结构，以及在这两种存储结构下线性表的基本运算算法的实现，顺序表和链表的优缺点比较。 重点：掌握线性表的定义和特点，线性表的存储结构；顺序表和链表的组织方法和算法设计。 难点：单链表和双链表的各种算法设计。 选择题部分： 1、 线性表是_________。 (A) 一个有限序列，可以为空 (B) 一个有限序列，不可以为空 (C) 一个无限序列，可以为空 (D) 一个无限序列，不可以为空 2、链表不具有的特点是_________。 (A) 可以随机访问任一元素 (B) 插入删除不需要移动元素 (C) 不必事先估计存储空间 (D) 所需空间与线性表长度成正比 3、线性表采用链式存储结构时，其地址_________。 (A) 必须是连续的 (B) 一定是不连续的 (C) 部分地址必须是连续的 (D) 连续与否均可以 4、在线性表的的下列存储结构中，读取指定序号的元素花费时间最少的是_________。 (A) 单链表 (B) 双链表 (C) 循环链表 (D) 顺序表 5、若线性表最常用的运算是存取第i个元素及其前趋的值，则采用_________存储方式节省时间。 (A) 单链表 (B) 双链表 (C) 循环单链表 (D) 顺序表 6、在一个具有n个结点的有序单链表中插入一个新结点使得仍然有序，其算法的时间复杂度为_________. (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n) 7、在一个单链表中，删除*p结点之后的一个结点的操作是_________。 (A) p->next=p (B) p->next->next=p->next (C) p->next->next=p (D) p->next=p->next->next 8、在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度为_________。 (A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2 9、在一个长度为n的顺序表中，删除值为x的元素时需要比较元素和移动元素的总次数是_________。 (A) (n+1)/2 (B) n/2 (C) n (D) n+1 10、在一个顺序表的表尾插入一个元素的时间复杂度是_________。 (A) O(n) (B) O(1) (C) O(n2) (D) O(log2n) 11、在一个顺序表的任何位置插入一个元素的时间复杂度是_________。 (A) O(n) (B) O(1) (C) O(n2) (D) O(log2n) 12、在一个不带头结点（首结点为*head）的单循环链表中，至少有一个结点的条件是_________。 (A) head!=NULL (B) head->next!=NULL (C) head==NULL (D) head->next==NULL 13、在带头结点*head的循环单链表中，至少有一个结点的条件是_________。 (A) head->next!=NULL (B) head->next!=head (C) head==NULL (D) head- 14、带头结点的单链表head为空的判定条件是_________。 (A) head==NULL (B) head->next==NULL (C) head->next==head (D) head!=NULL 15、将两个长度为n的有序表归并为一有序表时，算法的时间复杂度是_________。 (A) O(1) (B) O(n) (C) O(n2) (D) O(log2n) 16、在长度为n的顺序表，当在任何位置上插入一个元素的概率相等时，插入一个元素需要移动的元素的平均个数为( ) (A) n/2 (B)（n-1）/ 2 (C) (n+1)/2 (D) (n+2)/2 17、在长度为n的顺序表中，删除第i个元素(1≤i≤n)需要向后移动（ ）个元素。 (A) n-i (B) n-i+1 (C) n-i-1 (D) i 18、一个栈的入栈顺序是1、2、3、4、5，则此栈不可能的输出顺序为（ ）。 (A) 5、4、3、2、1 (B) 4、5、3、2、1 (C) 4、3、5、1、2 (D)1、2、3、4、5 19、一个队列的入队序列是a，b，c，d，则队列的输出序列是（ ）。 （A）dcba （B）abcd （C）adcb （D）cbda 20、空串是指（ ）。 (A)空白串 (B)长度为零的串 (C)长度为1的串 (D)仅由空格组成的串 21、在链式存储结构中，一个存储结点存储一个_____。 (A) 数据项 (B) 数据元素 (C) 数据结构 (D) 数据类型 22、算法分析的目的是_______________。 (A) 找出数据结构的合理性 (B)研究算法中输入和输出的关系 (C)分析算法的效率以求改进 (D)分析算法的易读性和文档性 23、一个队列的入队序列是abcd，则队列的输出序列是_____。 （A）dcba （B）abcd （C）adcb （D）cbda 24、在表长为n的顺序表上做插入运算，平均要移动的结点数为（ ）。 （A）n (B) n/2 (C) n/3 (D) n/4 25、在双链表某结点（己知其地址）前，插入一新结点，其所需时间是（ ）。 （A）O（1） (B) O(lgn) (C) O(n) (D) O(n2) 26、设长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为（ ）。 （A） O(1) (B) O(lgn) (C) O(n) D O(n2) 27、在表长为n的顺序表上做删除运算，在等概率的情况下，平均要移动的结点数为（ ）。 （A）n/2 (B) （n-1）/2 (C) n/3 (D) n/4 28、线性表（ a1,a2,?,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ） （A）O（i） （B）O（1） （C）O（n） （D）O（n/2） 29、线性表的下列存储结构中，读取指定序号的元素花费的时间最少的是______。 （A）单链表 （B）顺序表 （C）双链表 (D)循环链表 30、线性表采用链式存储结构时，其地址_________。 (A) 必须是连续的 (B) 一定是不连续的 (C) 部分地址必须是连续的 (D) 连续与否均可 31、在线性表的下列存储结构中，读取指定序号的元素花费时间最少的是____。 (A) 单链表 (B) 双链表 (C)循环链表 (D)顺序表 32、 若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素，则采用（ ）存储方式最省时间。 (A)单链表 (B)双链表 (C)单向循环链表 (D)顺序表 33、在长度为n的顺序表中，向第i个元素(1≤i≤n+1)前插入一个元素需要向后移动（ ）个元素。 (A) n-i (B) n-i+1 (C) n-i-1 (D) i 34、在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（ ）。 (A) q->next=p->next; p->next=q; (B) p->next=q->next; q=p; (C) p->next=p->next; q->next=q; (D) p->next=q->next; q->nxet=p; 35、在表长为n的顺序表上做插入运算，平均要移动的结点数为（ ）。 （A）n (B) n/2 (C) n/3 (D) n/4 36、在双链表某结点（己知其地址）前，插入一新结点，其所需时间是（ ）。 （A）O（1） (B) O(lgn) (C) O(n) (D) O(n2) 37、在长度为n的顺序表中，当在任何位置插入一个元素的概率相等时，插入一个元素需要移动的元素的平均个数是________。 （A）n/2 (B) (n-1)/2 (C) (n+1)/2 (D)(n+2)/2 38、 若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素，则采用（ ）存储方式最省时间。 (A)单链表 (B)双链表 (C)单向循环链表 (D)顺序表 49、在长度为n的顺序表中，向第i个元素(1≤i≤n+1)前插入一个元素需要向后移动（ ） 个元素。 （A） n-i （B） n-i+1 （C） n-i-1 （D） i 40、在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（ ）。 (A) q->next=p->next; p->next=q; (B) p->next=q->next; q=p; (C) p->next=p->next; q->next=q; (D) p->next=q->next; q->nxet=p; 判断题： 1、顺序查找方法只能在顺序存储结构上进行。 2、线性表的顺序存储结构优于链式存储结构。 3、对于单链表来说，只有从头结点开始才能扫描表中全部结点。 4、对于单链表来说，只有从头结点开始才能扫描表中全部结点。 5、双向链表的特点是很容易找任何一个结点的前趋和后继。 6、线性表的顺序存储结构优于链式存储结构。 7、凡是为空的单链表都是不含任何结点的。 8、向顺序表中插入一个元素，平均要移动大约一半的元素。 9. 线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是O(n)，因而两种存储方式的插入、删除运算所花费的时间相同。 10、线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是O(n)，因而两种存储方式的插入、删除运算所花费的时间相同。 11、线性表采用链式存储时，结点和结点内部的存储空间可以是不连续的。 12、单链表中的头结点就是单链表的第一个结点。 13、在带头结点的单循环链表中，任何一个结点的后继结点的指针均非空。 14、线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都相同。 15、分配给单链表的内存单元地址必须是连续的。 16、双向链表的特点是很容易找任何一个结点的前趋和后继。 17、线性表的顺序存储结构优于链式存储结构。 18、对于单链表来说，只有从头结点开始才能扫描表中全部结点。 19、线性表就是顺序表。 20、线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是O(n)，因而两种存储方式的插入、删除运算所花费的时间相同。 21、在带头结点的单循环链表中，任一结点的后继指针均非空。 22、线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是O(n)，因而两种存储方式的插入、删除运算所花费的时间相同。 23、在带头结点的单循环链表中，任一结点的后继指针均非空。 24、线性表采用链式存储时，结点和结点内部的存储空间可以是不连续的。 填空题： 1、单链表是 的链接存储表示。 2、在有n个元素的顺序表中删除任意一个元素所需移动结点的平均次数是 。 3、在双链表中，每个结点有两个指针域，一个指向 另一个指向 。 4、在带有头结点的单链表L中，第一个元素结点的指针是