数据结构自测题

本文格式为Word版，下载可任意编辑——数据结构自测题一．绪论1.1单项选择题

1.数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。

①A．操作对象Ｂ．计算方法Ｃ．规律结构Ｄ．数据映象②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2.数据结构DS(DataStruct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②的有限集合。

①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象②A．操作Ｂ．映象Ｃ．存储Ｄ．关系3.在数据结构中，从规律上可以把数据结构分成。

A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4.算法分析的目的是①，算法分析的两个主要方面是②。

①A.找出数据结构的合理性B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进D.分析算法的易懂性和文档性②A.空间繁杂性和时间繁杂性B.正确性和简明性

C.可读性和文档性D.数据繁杂性和程序繁杂性

5.计算机算法指的是①，它必具备输入、输出和②等五个特性。①A.计算方法B.排序方法

C.解决问题的有限运算序列D.调度方法

②A.可行性、可移植性和可扩展性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性

1.2填空题（将正确的答案填在相应的空中）

1.数据规律结构包括、和三种类型，树形结构和图形结构合称为。

2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最终一个结点后续结点，其余每个结点有且只有个后续结点。

3.在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。

4.在图形结构中，每个结点的前驱结点数和后续结点数可以。

5.线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。

6.算法的五个重要特性是____,____,____,____,____。7.分析下面算法（程序段），该算法的时间繁杂度是____。

for(i=0;inext=p->next->next;B.p=p->next;C.p=p->next->next;D.next=p;

6、设单链表中指针p指向结点ai，指针f指向将要插入的新结点x，问：（1）当x插在链表中两个数据元素ai和ai+1之间时，只要先修改______后修改______即可。

A.p->next=fB.p->next=p->next->nextC.p->next=f->nextD.f->next=p->nextE.f->next=NULLF.f->next=p

（2）在链表中最终一个结点an之后插入时，只要先修改______后修改______即可。

A.f->next=pB.f->next=p->nextC.p->next=fD.p->next=f->nextE.f=NULL

7、在一个单链表中，若要在p所指向的结点之前插入一个新结点，则此算法的时间繁杂度为________。

A.O(n)B.O(n/2)C.O(1)D.O(n)8、不带头结点的单链表L为空的判定条件为_________。A.L==NULLB.L->next==NULLC.L->next==LD.L!=NULL9、带头结点的单链表L为空的判定条件为_________。A.L==NULLB.L->next==NULLC.L->next==LD.L!=NULL

10、指针p指向双向链表中的结点ai，ai-1为ai的前驱结点，指针f指向将要插入的新结点x。x插在ai-1和ai之间，此时需要修改指针的操作依次为_________________。

A.p->prior->next=fB.p->prior=f

C.f->next=pD.f->prior=p->prior

11、在一个带头结点的双向循环链表中，若要在指针p所指的结点之后插入一个q指针所指向的结点，则需要对q->next赋值为______。A.p->priorB.p->next

C.p->next->nextC.p->prior->prior

二、填空题：

1、线性表的两种存储结构分别为__________和_______________。

2、若经常需要对线性表进行插入和删除运算，则最好采用_______存储结构，若经常需要对线性表进行查找运算，则最好采用________存储结构。3、访问一个线性表中具有给定值元素的时间繁杂度为__________。

3

4、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间繁杂度为______，在表尾插入元素的时间繁杂度为___________。5、单链表是____________的链接存储表示。6、在一个单链表中指针p所指向的结点的后面插入一个指针q所指向的结点时，首先把_______的值赋给q->next，然后把__________的值赋给p->next。

7、在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作：（1）s->next=?______________;（2）p->next=s;（3）t=p->data;

（4）p->data=?______________;（5）s->data=?______________;

8、假定指向单链表中第一个结点的表头指针为head，则向该单链表的表头插入指针p所指向的新结点时，首先执行____________赋值操作，然后执行________________赋值操作。9、在一个单链表中删除指针p所指向结点的后继结点时，需要把_____________的值赋给p->next指针域。

10、在一个单链表中删除指针p所指结点时，应执行以下操作：

q=p->next;

p->data=p->next->data;p->next=___________;free(q);

11、在________链表中，既可以通过设定一个头指针也可以通过设定一个尾指针来确定它，即通过头指针或尾指针可以访问到该链表中的每个结点。12、在一个双向循环链表中指针p所指向的结点之前插入一个新结点时，其时间繁杂性的量级为___________________。

三、简答题

1、对于线性表的两种存储结构，假使线性表的总数基本稳定，并且很少进行插入和删除操作，但是要求以最快的速度存取线性表中的元素，则应选中用哪种存储结构？试说明理由。

2、有哪些链表可仅由一个尾指针来唯一确定，即从尾指针出发能访问到链表上任何一个结点？

3、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删除？若可以，其时间繁杂度各为多少？

4

四、算法阅读题

读下面的程序段，画出执行过程的示意图及所完成的功能。1.

#defineN6voidmain(){

SqListL;intA[N];

inti,j,m,elem;

InitList_Sq(L);//初始化顺序表for(j=0;jnext;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}