1. 非空线性链表中，若要在由p所指的链结点后面插入新结点q，则应执行语句___q->link=p->link; __和___p->link=q; ___。
结点结构为
typedef struct Node{
int value;
node* link;
}node;
2. 线性表中的插入、删除操作，在顺序存储方式平均移动近一半的元素，时间复杂度为O（n） ；而在链式存储方式下，插入和删除时间复杂度都是 O(1)。
3. 设n为大于1的正整数， 计算机执行下面的语句时，带#语句的执行次数为n 。 i=1; j=0;
while(i+j<=n){ # if(i>j)
j++; else i++; }
4. 在具有n个链结点的链表中查找一个链结点的时间复杂度为O(n)。
5. 下面程序段的时间复杂度为O(mn) 。
for ( i = 0; i < n; i++ )
for ( j = 0; j < m; j++ )
a[i][j] = ( i > j ) ? ( i*i*i ) : ( j*j*j );
6. 假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示，计算机科学中，除非特别声明，对数都是以2为底，即log2X可表示为：log X或者log(X)）。
int time (int n) {
int count=0, x=2; while ( x < n/2 ) { x=2x; count++; }
return (count); }
时间复杂度：O(logn) count值：logn-2
7. 设n为大于1的正整数，计算机执行下面的语句时，带#语句的执行次数为n-1。 i=1; do{
# x++;
i++;
}while(i!=n);
8. 若某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第10个元素的存储地址为136。
9. 在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动 n-i+1 个元素。
10. 线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是(n-1)/2。
选择题
# 题目
1. 程序段 FOR i := n - 1 DOWNTO 1 DO
FOR j := 1 TO i DO
IF A [ j ] > A[ j + 1 ]
THEN A [j] 与 A[ j + 1] 对换;
其中n为正整数，则最后一行的语句频度在最坏的情况下是（D）
A. O(n)
B.O(nlogn)
C.O(n3)
D.O(n2) 2.
下面关于算法说法错误的是（D） A. 算法最终必须由计算机程序实现
B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的
3. 数据的存储结构通常有D 。
A．顺序存储结构和链式存储结构
B．顺序存储结构、链式存储结构和索引结构
C．顺序存储结构、链式存储结构和散列结构
D．顺序存储结构、链式存储结构、索引结构和散列结构
4. 在一个具有n个链结点的线性链表中查找某一个链结点，若查找成功，需要平均比较C.个链结点。
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
5. 在非空双向循环链表中由q所指的那个链结点前面插入一个由p所指的链结点的动作所对应的语句依次为：p一>rlink=q; p一>llink=q一>llink; q一>llink=p; D.。(空白处为一条赋值语句)
A. q一>rlink= p;
B. q一>llink一>rlink=p;
C. p一>rlink一>rlink= p;
D. p一>llink一>rlink=p;
6. 在包含1000个数据元素的线性表中，实现如下4个操作所需要的执行时间最长的是A 。
A. 线性表采用顺序存储结构，在第10个元素后面插入一个新的元素
B. 线性表采用链式存储结构，在第10个元素后面插入一个新的元素
C. 线性表采用顺序存储结构，删除第990个元素
D. 线性表采用链式存储结构，删除p所指的链结点
7. 数据采用链式存储结构，要求A。
A. 每个链结点占用一片地址连续的存储空间
B. 所有链结点占用一片地址连续的存储空间
C. 链结点的最后那个域一定为指针域
D. 每个链结点有多少个直接后继结点，它就应该设置多少个指针域
8. 将长度为m的线性链表链接在长度为n的线性链表之后的过程的时间复杂度若采用大O形式表示，则应该是B。
A．O(m) B．O(n) C．O(m+n) D．O(m-n)
9. 在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改__个指针域 A. 1 B. 2 C. 3 D. 4
10. 以下程序段的时间复杂度是C
int i=0; for (int j=1;j<=n;j*=2) {
for (int k=1;k<=n;k++) { i++; } }
A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2) 编程题
1. 合并链表 【问题描述】
两个数据以非降序排列的链表的并集的链表，例如将链表1->2->3 和 2->3->5 并为 1->2->3->5，只能输出结果，不能修改两个链表的数据。 【输入形式】
第一行为第一个链表的各结点值，以空格分隔。 第二行为第二个链表的各结点值，以空格分隔。 【输出形式】
合并好的链表，以非降序排列，值与值之间以空格分隔。
【样例输入】 4 7 10 34
1 4 6 29 34 34 52
【样例输出】
1 4 6 7 10 29 34 52
【评分标准】
要使用链表实现，否则不能得分。
2. 数字统计
【问题描述】对于1到n的所有自然数，计算0到n所有数字（0-9之间的数字）出现的次数分布。 【输入形式】一个整数n（n <= 100000）
【输出形式】10个数字，空格隔开，对应0-9数字在1..n这个序列中出现的次数总和。 【样例输入】 11
【样例输出】 1 4 1 1 1 1 1 1 1 1 【样例输入】 10000 【样例输出】
2893 4001 4000 4000 4000 4000 4000 4000 4000 4000 【评分标准】输出的10个数之间用空格区分。