[单项选择]给定有n个元素，建立一个有序单链表的时间复杂度为( )
A. O(1)
B. O(n)
C. O(n²)
D. O(nlog₂n)

[单项选择]设有n个元素的向量，逐个输入其中的元素值，建立一个有序单链表的时间复杂度是（）
A. O(1)
B. O(n)
C. O(n²)
D. O(nlog₂n)

[单项选择]在具有n个结点的有序单链表中插入一个新结点并保持有序的运算的时间复杂度为（）。
A. O(1)
B. O(logn)
C. O(N)
D. O(n²)

[单项选择]对于一个具有n个元素的线性表，建立其单链表的最小时间复杂度为( )
A. O(log₂n)
B. O(1)
C. O(n²)
D. O(n)

[单项选择]给定一个有n个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动（）个元素。
A. (n+1)/2
B. n/2
C. (n-1)/2
D. 1

[填空题]给定程序中已建立一个带有头结点的单向链表，在main函数中将多次调用fun函数，每调用一次fun函数，输出链表尾部结点中的数据，并释放该结点，使链表缩短。
[注意] 部分源程序给出如下。
请勿改动主函数main和其他函数中的任何内容，仅在函数fun的横线上填入所编写的若干表达式或语句。
[试题源程序]
#include＜stdio.h＞
#include＜stdlib.h＞
#define N 8
typedef struct list

int data;
struct list *next;
SLIST;
void fun(SLIST *p)

SLIST *t, *s;
t=P-＞next;
s=p;
while(t-＞next!=NULL)

s=t;
/*********found**********/
t=t-＞ (1) ;

/**********found**********/
printf(”%d”, (2) );
s-＞next=NULL:
/**********found**********/
free( (3) );

SLIST *creatlist(int *a)

SLIST *h, *p, *q;
int i;
h=p=(SLIST *)malloc(sizeof(SLIST));
for(i=0; i＜N; i++)

q=(SLIST *)malloc(sizeof(SLIST));
q-＞data=a[i];
p-＞next=q;
p=q;

P-＞next=0;
return h;

void outlist(SLIST *h)

SLIST *p;
p=h-＞next;
if(

[简答题]

下列给定程序是建立一个带头结点的单向链表，并用随机函数为各结点赋值。函数fun（　）的功能是：将单向链表结点(不包括头结点)数据域为偶数的值累加起来，并作为函数值返回。
其累加和通过函数值返回main（　）函数。例如，若n=5，则应输出8.391667。
请改正程序中的错误，使它能得到正确结果。
[注意] 不要改动main函数，不得增行或删行，也不得更改程序的结构。
[试题源程序]
#include＜stdio.h＞
#include＜stdiib.h＞
typedef struct aa

int data;
struct aa *next;
NODE;
int fun(NODE *h)

int sum=0;
NODE *P;
/**********found**********/
p=h;
while(P-＞next)

if(p-＞data%2==0)
sum+=p-＞data;
/**********found**********/
p=h-＞next;

return sum;

NODE *creatlink(int n)

NODE *h, *p, *s, *q；
int i, x;
h=p=(NODE *)malloc(si zeof(NODE));
for(i=1; i＜=n; i++)

s=(NODE *)malloc(sizeof(NODE));
s-＞data=rand（　）%16;
s-＞next=p-＞next;
p-＞next=s;
p=p->next;

p-＞next=NULL;
return h;

outlink(NODE *h, FILE *Pf)

[简答题]下列给定程序中，是建立一个带头结点的单向链表，并用随机函数为各结点数据域赋值。函数fun的作用是求出单向链表结点(不包括头结点)数据域中的最大值，并且作为函数值返回。
请改正程序指定部位的错误，使它能得到正确结果。
[注意] 不要改动main函数，不得增行或删行，也不得更改程序的结构。
[试题源程序]
#include＜stdio.h＞
#include＜stdlib.h＞
typedef struct aa

int data;
struct aa *next;
NODE;
fun(NODE *h)

int max=-1;
NODE *p;
/***********found************/
p=h;
while(p)

if(p-＞data＞max)
max=p-＞data;
/************found************/
p=h-＞next;

return max;

outresult(int s, FILE *Pf)

fprintf(pf, "/nThe max in link: %d/n", s);

NODE *creatlink(int n, int m)

NODE *h, *p, *s, *q;
int i, x;
h=p=(NODE *)malloc(sizeof(NODE));
h-＞data=9999;
for(i=1; i＜=n; i++)

s=(NODE *)malloc(sizeof(NODE));
s-＞data=rand（　）%m; s-＞next=p-＞next;
p-＞next=s; p=p-＞next;

p-＞next=NULL;
return h;

outlink(NODE *h, FILE *pf)

[填空题]在一个有n个元素的顺序表的第i个元素(1≤i≤n)之前插入一个新元素时，需要向后移动 【1】 个元素。

[单项选择]对于n个结点的单向链表(无表头结点)需要指针单元的个数至少为
A. n-1
B. n
C. n+1
D. 2n

[单项选择]设线性表有n个元素，以下操作中，( )在顺序表上实现比在链表上实现效率更高。
A. 输出第i(1≤i≤n)个元素值
B. 交换第1个元素与第2个元素的值
C. 在第i个元素前插入一个元素
D. 删除第i个元素

[单项选择]顺序查找一个具有n个元素的线性表，二分查找一个具有n个元素的有序表，其时间复杂性为______。
A. O(n)
B. O(log₂n)
C. O(n²)
D. O(nlog₂n)

[单项选择]设线性表中有2n个元素，算法( )，在单链表上实现要比在顺序表上实现效率更高。
A. 删除所有值为x的元素
B. 在最后一个匀速的后面插入一个新元素
C. 顺序输出前k个元素
D. 交换第i个元素和第2n-i-1个元素的值(i=0，1，…，n-1)

[单项选择]设线性表中有2n个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高的是( )。
A. 删除指定元素
B. 在最后一个元素的后面插入一个新元素
C. 顺序输出前k个元素
D. 交换第i个元素和2n—i—1个元素的值(i=0，1，…，n-1)

[单项选择]从含有N个元素的总体中，抽取n个元素作为样本，为了使得总体中的每一个元素都有相同的机会(概率)被抽中，应采取的抽样方式是( )。
A. 简单随机抽样
B. 分层抽样
C. 系统抽样
D. 整群抽样

[填空题]在一个有n个元素的顺序表的第i个元素(1≤i≤n)；之前插入一个新元素时，需要向后移动 【2】 个元素。