一、填空:(每空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的算法实现 |