2、(n+1)/2二．填空题1．数据的逻辑结构被分为_____________、_____________、_____________和_____________四种。2．数据的存储结构被分为_____________、_____________、_____________和_____________四种。3．在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着_____________、_____________和_____________的联系。4．在C语言中，一个数组a所占有的存储空间的大小
3、即数组长度为_____________，下标为i的元素a[i]的存储地址为_____________。5．在下面程序段中，s=s+p语句的执行次数为_____________，p*=j语句的执行次数为_____________，该程序段的时间复杂度为_____________。inti=0,s=0;while(++i<=n){intj,p=1;for(j=1;j<=i;j++)p*=j;s=s+p;}6．某算法仅含2个语句，其执行次数分别为1000n2和0.01n3，则该算法的时间复杂度为_____
4、________。7．一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级表示为__________。三．应用题1有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。1．A=（K，R）其中K={a1,a2,a3,…,an}R={}2．B=（K，R）其中K={a,b,c,d,e,f,g,h}R={,,,,,,}3．C=（K，R）其中K={a,b,c,d,e,f,g,h
5、}R={,,,,,,}4．D=（K，R）其中K={1,2,3,4,5,6}R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}第二章线性表一．单选题1．下列有关线性表的叙述中，正确的是（）。A．线性表中的元素之间是线性关系B．线性表中至少有一个元素C．线性表中任何一个元素有且仅有一个直接前驱D．线性表中任何一个元素有且仅有一个直接后继2．在一个长度为n的顺序存储的线性表中，向第i个
6、元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次后移（）个元素。A．n-iB．n-i+1C．n-i-1D．i3．在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移（）个元素。A．n-iB．n-i+1C．n-i-1D．i4．在一个长度为n的顺序表中插入一个元素的时间复杂度为（）。A．O(n)B．O(n/2)C．O(1)D．O(n2)5．不带头结点的单链表的头指针为head，则该链表为空的判定条件是（）。A．head==NULLB．head->next=
7、=NULLC．head!=NULLD．head->next!=NULL6．带头结点的单链表的头指针为head，判定该链表为非空的条件是（）。A．head==NULLB．head->next==NULLC．head!=NULLD．head->next!=NULL7．在一个头指针为ph的单链表中，若要在结点*p之后插入一个结点*s，则应执行的语句是（）。A．s->next=p->next;p->next=s;B．p->next=s;s->next=p->next;C．p->next=s->next;s-
8、>next=p;D．s->next=p;p->next=s->next;8．在一个带头结点的循环双向链表中，若要在指针p所指向的结点之后插入一个q指针所指向的结点，则需要对q->right赋值为（）。1A．p->leftB．p->rightC．p->right->rightD．p->left->left9．在一个带头结点的循环双向链表中，若要在指针p所指向的结点之前插入一个q指针所指向的结点，则需要对p->left->right赋值为（）。A．qB．pC．p->rig
