数据结构练习题1 指导老师：***
姓名：***
学校：滨州学院
院系：信息工程学院软件技术
填空题
1.对于一个n个结点的单链表，在表头插入元素的时间复杂度为_____O(1)_____，在表尾插入元素的时间复杂度为_____O(n)_____。

2.删除非空线性链表中由q所指的链结点（其直接前驱结点由r指出）的动作时执行语句___r->link=q->link_______和______free(q)____。

结点结构为
typedef struct Node{
int value;
node * link;
}node;
3.非空线性链表中，若要在由p所指的链结点后面插入新结点q，则应执行语句____ q->link=p->link;______和_____ p->link=q;_____。

结点结构为
typedef struct Node{
int value;
node* link;
}node;
4.线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____(n-1)/2_____。

5.在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动_____ n-i+1_____ 个元素。

6.在具有n个链结点的链表中查找一个链结点的时间复杂度为O(_______n___)。

7.线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为_____O（n）_____；而在链式存储方式下，插入和删除操作的时间复杂度都是____O(1)______ 。

8.若某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第10个元素的存储地址为____136______。

选择题
1.对于一个带头结点的单链表，头指针为head，判定该表为空的条件是________B__。

A. head==NULL
B. head->next==NULL
C. head->next==head
D. head!=NULL
2.将长度为m的线性链表链接在长度为n的线性链表之后的过程的时间复杂度若采用大O形式表示，则应该是______B____。

A．O(m) B．O(n) C．O(m+n) D．O(m-n)
3.在包含1000个数据元素的线性表中，实现如下4个操作所需要的执行时间最长的是______A____ 。

A. 线性表采用顺序存储结构，在第10个元素后面插入一个新的元素
B. 线性表采用链式存储结构，在第10个元素后面插入一个新的元素
C. 线性表采用顺序存储结构，删除第990个元素
D. 线性表采用链式存储结构，删除p所指的链结点
4.在非空双向循环链表中由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;
5.在一个单向循环链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改____B______个指针域的值
A. 1
B. 2
C. 3
D. 4
6.在一个具有n个链结点的线性链表中查找某一个链结点，若查找成功，需要平均比较_____C_____个链结点。

A. n
B. n/2
C. (n+1)/2
D. (n-1)/2
7.给定一个具有n个元素的顺序表，建立一个有序线性链表的时间复杂度为______C____ 。

A. O(1)
B.O(n)
C. O(n2)
D. O(log2n)
8.链表不具有的特点是（_____B_____）
A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比
9.下面关于线性表的叙述中，错误的是哪一个？_B_________
A.线性表采用顺序存储，必须占用一片连续的存储单元。

B.线性表采用顺序存储，便于进行插入和删除操作。

C.线性表采用链接存储，不必占用一片连续的存储单元。

D.线性表采用链接存储，便于插入和删除操作。

10.下列哪一个术语与数据的存储结构无关？____D______
A. 顺序表
B. 链表
C. 散列表
D. 队列
11.设指针q指向单链表中结点A，指针p指向单链表中结点A 的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为______B____。

A．s->next=p->next；p->next=-s；
B．q->next=s；s->next=p；
C．p->next=s->next；s->next=p；
D．p->next=s；s->next=q；
12.在一个单链表中，若p所指节点不是最后节点，在p之后插入s所指节点，则执行_____B_____
A. s->link=p; p->link=s;
B. s->link=p->link; p->link=s;
C. s->link=p->link; p=s;
D. p->link=s; s->link=p;
13.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用__D________存储方式最节省运算时间。

A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表
14.对N 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为__B________
A．N/2 B. （N+1）/2 C. N D. [（1+N）*N ]/2
15.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（_____C_____）(1<=i<=n+1)。

A. O(0)
B. O(1)
C. O(n)
D. O(n2)
16.在一个以h 为头的单循环链表中，p 指针指向链尾的条件是______A____ 。

A. p->next = h
B. p->next = NULL
C. p->next->next = h
D. p->data = -1
算法填空题：
设lista，listb分别为两个有序链表（升序）的第1个链结点的指针，将这两个有序链表合并为一个有序链表，并设合并后的链表的第一个链结点的指针为listc.
LinkList MERGELIST(LinkList lista,LinkList listb)
{
LinkList listc,p=lista,q=listb,r;
if(lista->data<=listb->data){
listc=lista;
r=lista;
p=lista->link;
}
else{
listc=listb;
r=listb;
q=listb->link;
}
while(p!=NULL&&q!=NULL){
if(p->data<=q->data){
____r->next=p______
r=p;
______p=p->next____ }
else{
__r->next=q________
r=q;
_____q=q->next_____ }
}
r->link=_______p___?p:q;
return listc;
}。