|
一、填空：（每空1分，共44分）
1.简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的_________以及它们之间的_______和_______等等的学科。
2.数据(Data)是指能够输入到计算机中，并能被计算机程序识别和处理的______的总称。它是计算机程序加工的“原料”。
3.数据元素是组成数据的_____单位，在计算机程序中通常作为一个整体进行考虑和处理。有时，一个数据元素还可以分割成若干个具有不同属性的_______（Data Item/字段），数据项是数据的不可分割的_____单位。
4.具体来说，数据结构包含三个方面的内容，即数据的_________，数据的_________和对数据所施加的______。
5.数据从逻辑结构划分为：_______结构和________结构,数据从存贮结构划分为：______存贮、________存贮_________存贮和________存贮。
6.算法的五大特性：________、________、________、________、________。
7.
线性结构特点：
在数据元素的非空有限集中
存在_______的一个被称作_______的数据元素。
存在_______的一个被称作_______的数据元素。
除第一个外，集合中的每个数据元素均只有一个________。
除最后一个外，集合中的每个数据元素均只有一个________。
8.线性表（linear list）是n（n≥0）个数据元素a1,a2,……,an组成的有限序列。其中n 称为数据元素的个数或线性表的________。
9.在稍复杂的线性表中，一个数据元素可以由若干个________组成，在这种情况下，常把数据元素称为________,含有大量记录的线性表又称________。
10.线性表的特征：
（1）有且仅有一个开始结点(表头结点)a1，它没有_________，只有一个_________；
（2）有且仅有一个终端结点(表尾结点)an，它没有_________，只有一个_________；
（3）其它结点都有一个_________和_________；
（4）元素之间为一对一的______关系。
11.线性表的顺序存储结构的特点：实现了_______相邻，________也相邻；实现了______存取。
12.线性表的链式存储结构中,利用_______实现了用不相邻的存储单元存放逻辑上相邻的元素；一个结点包括两个域，________域和________域。
二、单项选择题（每题4分，共36分）
1.在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针P所指向的结
点，则执行( )。
A．q->next＝p->next；p->next＝q
B．p->next＝q->next；q＝p；
C．q->next＝p->next；p->next＝q；
D．p->next＝q->next；q->next＝p；
2.下面程序段的执行次数为： （ ）
for(i=0；i<n-1；i++)
语句；
A． n
B． n-1
C． n-2
D． n+1
3.设P是指向变量I的指针变量，I的值是3，如下图，*P的值是（ ）
P I
2000 3
2000
A．2000
B．3
C．2002
D．2003
4.构造一个空的线性表L用（ ）
A.InitList(&L)
B.DestroyList (&L)
C.ListEmpty(L)
D.ClearList(&L)
5.假设线性表L=(23,56,89,76,18),i=3,x=56,y=88,则对L执行GetElem(L,i,&e)
的操作结果为（ ）
A．23
B．56
C．89
D．76
6.在长度为n的线性表中，在第i个元素之前插入一个新的元素x，需要移动（ ）个元素。
A． n
B． n-i+1
C． n-i
D． i+1
7.在长度为n的线性表中，删除第i个元素，需要移动（ ）个元素
A． n
B． n-i+1
C． n-i
D． i+1
8.假设p是指向线性表中第i个数据元素结点的指针，则p->next 是指向第i+1个数据元素结点的指针，若p->data=ai, 则p->next->data=ai+1，那么p->next->next指向的是第（ ）个结点
A. i
B. i+1
C. i+2
D. i+3
9.在双向链表中，一个结点包含（ ）个指针
A．1
B．2
C．3
D．4
三、应用题：（每题5分，共10分）
1.在单链表中删除结点b，画出相应的指针变化：
2.在双向链表中插入一个结点x,画出相应的指针变化：
四、算法设计题：（10 分）
在单链表L的两个数据元素a和b间插入x，已知p指向a，写出插入x的算法实现 |
