数据结构自测题

1、一绪论1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的 、数据信息在计算机中的 以及一组相关的运算等的课程。 A操作对象计算方法逻辑结构数据映象 A存储结构 关系 运算 算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是 的有限集合，R是D上的 的有限集合。 A算法 数据元素 数据操作 数据对象 A操作 映象 存储 关系3. 在数据结构中，从逻辑上可以把数据结构分成 。A动态结构和静态结构 紧凑结构和非紧凑结构 线性结构和非线性结构 内部结构和外部结构4. 算法分析的目的是 ，算法分析的两个主要方面是 。 A. 找出数据

2、结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性 D. 数据复杂性和程序复杂性5. 计算机算法指的是 ，它必具备输入、输出和 等五个特性。 A. 计算方法 B. 排序方法C. 解决问题的有限运算序列 D. 调度方法 A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性1.2 填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括 、 和 三种类型，树形结构和图形结构合称为 。2. 在线性结构

3、中，第一个结点 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。3. 在树形结构中，树根结点没有 结点，其余每个结点有且只有 个直接前驱结点，叶子结点没有 结点，其余每个结点的直接后续结点可以 。4. 在图形结构中，每个结点的前驱结点数和后续结点数可以 。5. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。6. 算法的五个重要特性是_ _ , _ _ , _ _ , _ _ , _ _。7. 分析下面算法（程序段），该算法的时间复杂度是_ _。for (i=0;i<n;i+) for (j=

4、0;j<n; j+) Aij=0;8. 分析下面算法（程序段），该算法的时间复杂度是_ _。for (i=0;i<n;i+) for (j=0; j<i; j+)Aij=0;9. 分析下面算法（程序段），该算法的时间复杂度是_ _。s=0;for (i=0;i<n;i+) for (j=0;j<n;j+) for (k=0;k<n;k+) s=s+Bijk;sum=s;10. 分析下面算法（程序段），该算法的时间复杂度是_ _。i=s=0;while (s<n) i+; s+=i; /s=s+i 11. 分析下面算法（程序段），该算法的时间复杂度是_

5、_。i=1;while (i<=n) i=i*2;第二章基础知识一、选择题1、线性表是_。A.一个有限序列，可以为空 B.一个有限序列，不能为空C.一个无限序列，可以为空 D.一个无限序列，不能为空2、在一个长度为n的顺序存储的线性表中，向第i 个元素（1£ i £ n+1）位置插入一个新元素时，需要从后向前依次后移_个元素。A. n-i B. n-i+1 C. n-i-1 D. i3、在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为_。A. (n+1)/2 B. n/2 C. n D. n+14、在一个顺序表的表尾插入一个元素的时间复杂性

6、的量级为_。A. O(n) B. O(1) C. O(n2) D. O(log2n)5、设单链表中指针p指向结点，若要删除之后的结点（若存在），则需修改指针的操作为_。A. p->next=p->next->next; B. p=p->next;C. p=p->next->next; D. next=p;6、设单链表中指针p指向结点，指针f指向将要插入的新结点x，问：（1）当x插在链表中两个数据元素和之间时，只要先修改_后修改_即可。A. p->next=f B. p->next=p->next->nextC. p->next=

7、f->next D. f->next=p->nextE. f->next=NULL F. f->next=p（2）在链表中最后一个结点之后插入时，只要先修改_后修改_即可。A. f->next=p B. f->next=p->nextC. p->next=f D. p->next=f->nextE. f=NULL7、在一个单链表中，若要在p所指向的结点之前插入一个新结点，则此算法的时间复杂度为_。A. O(n) B. O(n/2) C. O(1) D. O()8、不带头结点的单链表L为空的判定条件为_。A. L=NULL B.

8、L->next=NULLC. L->next=L D. L!=NULL9、带头结点的单链表L为空的判定条件为_。A. L=NULL B. L->next=NULLC. L->next=L D. L!=NULL10、指针p指向双向链表中的结点，为的前驱结点，指针f指向将要插入的新结点x。x插在和之间，此时需要修改指针的操作依次为_。A. p->prior->next=f B. p->prior=fC. f->next=p D. f->prior=p->prior11、在一个带头结点的双向循环链表中，若要在指针p所指的结点之后插入一个q指

9、针所指向的结点，则需要对q->next赋值为_。A. p->prior B. p->nextC. p->next->next C. p->prior->prior二、填空题：1、线性表的两种存储结构分别为_和_。2、若经常需要对线性表进行插入和删除运算，则最好采用_存储结构，若经常需要对线性表进行查找运算，则最好采用_存储结构。3、访问一个线性表中具有给定值元素的时间复杂度为_。4、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。5、单链表是_的链接存储表示。6、在一个单链表中指针p所指向的结点的后面

10、插入一个指针q所指向的结点时，首先把_的值赋给q->next，然后把_的值赋给p->next。7、在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作：（1）s->next=j_;（2）p->next=s;（3）t=p->data;（4）p->data=k_;（5）s->data=l_;8、假定指向单链表中第一个结点的表头指针为head，则向该单链表的表头插入指针p所指向的新结点时，首先执行_赋值操作，然后执行_赋值操作。9、在一个单链表中删除指针p所指向结点的后继结点时，需要把_的值赋给p->next指针域。10、在一个单链表中删

11、除指针p所指结点时，应执行以下操作：q=p->next;p->data=p->next->data;p->next=_;free(q);11、在_链表中，既可以通过设定一个头指针也可以通过设定一个尾指针来确定它，即通过头指针或尾指针可以访问到该链表中的每个结点。12、在一个双向循环链表中指针p所指向的结点之前插入一个新结点时，其时间复杂性的量级为_。三、简答题1、对于线性表的两种存储结构，如果线性表的总数基本稳定，并且很少进行插入和删除操作，但是要求以最快的速度存取线性表中的元素，则应该选用哪种存储结构？试说明理由。2、有哪些链表可仅由一个尾指针来唯一确定，即从尾

12、指针出发能访问到链表上任何一个结点？3、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删除？若可以，其时间复杂度各为多少？四、算法阅读题读下面的程序段，画出执行过程的示意图及所完成的功能。1.# define N 6void main ( ) SqList L ; int A N ;int i ,j,m, elem ;InitList_Sq(L); /初始化顺序表 for (j=0; j<N; j+) scanf("%d",&A j ) ; for ( m=0; m<N; m+) ListInsert

13、_Sq( L , m+1 ,Am) ; PrintList( L ) ; / 输出函数，顺序输出表中元素2.int A(LinkList L) /*L是无表头结点的单链表*/ if ( L&&L->next) Q=L; L=L->next; P=L; while (P->next) P=P->next; P->next=Q; Q->next=NULL; return 1; 3. void BB(LNode *s, LNode *q) p=s; while (p->next !=q ) p=p->next; p->next=s

14、;void AA(LNode *pa, LNode *pb) /*pa 和 pb 分别指向单循环链表中两个节点*/ BB(pa,pb); BB(pb,pa);五、算法设计题1、分别编写在顺序表和带头结点的单链表上统计出值为x的元素个数的算法，统计结果由函数值返回。2、设线性表存放于顺序表A中，其中有n个元素，且递减有序，请设计一算法，将x插入到线性表的适当位置，以保持线性表的有序性。3、已知两个单链表A和B，指向头结点的指针分别为La和Lb，试编写一个算法从单链表A中删除自第i个元素起的共length个元素，然后将它们插入到单链表B的第j个元素之前。4、已知A，B和C为三个元素值递增有序的单链

15、表，现要求对表A作如下运算：删去那些既在表B中出现又在表C中出现的元素。试分别以两种存储结构（一种顺序的，一种链式的）编写实现上述运算的算法。5、已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。试编写一个删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）的算法。6、有两个循环不带头结点的单链表如图所示，编写一个算法将链表1连接到链表2之后，并仍然保持循环链表形式。7、假设有一个单向循环链表，其结点含有三个域：pre，data和next，其中data为数据域；next为指针域，它指向后继结点；pre为指针域，它的值为空指针（NULL）。试编写算法将此表改为双向循环

16、链表。8、编写算法实现顺序表的就地逆置，即利用原顺序表的存储单元把数据元素序列 如（），逆置为（ ） 。9、假设在长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某个结点的指针，编写一个算法删除该结点的前趋结点。10、设头指针为head，编写算法实现带头结点单链表head的就地逆置，即利用原带头结点单链表head的结点空间把数据元素序列（）逆置为（）。11、设头指针为head，并设带头结点单链表中的数据元素递增有序，编写算法将数据元素x插入到带头结点单链表的适当位置上，要求插入后保持单链表数据元素的递增有序。12、设head为单链表的头指针，并设单链表带有头结点，编写算法将单链

17、表中的数据元素按照元素值递增有序的顺序就地排序。13、编写不带头结点单链表的初始化操作、插入操作和删除操作。第三章基础知识一、 选择题1、栈的插入和删除操作在（ ）进行。A、栈顶 B、栈底 C、任意位置 D、指定位置2、若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn, 那么p1=n；pi为（ ）。、i 、n-i 、ni1 、不确定3、假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列。下列序列（ ）是合法的。、IOIIOIOO 、IOOIOIIO C、IIIOIOIO D、OIIOIOIO4、递归函数可以调用自

18、身（ ）次。、至多1次 、任意次数 、0 次 、至多2次二、 填空题1、线性表、栈和队列都是（ ）结构，可以在线性表的（ ）位置插入和删除元素；对于栈只能在（ ）插入和删除元素；对于队列只能在（ ）插入元素和在（ ）删除元素。2、对于一个顺序栈作进栈运算时，应先判别栈是否为（ ），作退栈运算时，应先判别栈是否为（ ），当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为（ ）。3、设有一个空栈，现有输入序列1，2，3，4，5，经过push，push，pop，push，pop，push，push后，输出序列是（ ）。4、无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除操作的

19、时间复杂度均相同为（ ）。5、有一个循环队列，分配到的存储空间大小为n，则其队满条件是（ ），队列为空的条件是（ ）。三、 应用题、若依次读入数据元素序列a,b,c,d进栈，进栈过程中允许出栈，试写出各种可能的出栈元素序列。 2、以下代码段执行什么操作？Stack S1 ，tmp；Elemtype X ； While(！StackEmpty(S1)Pop(S1,X)；Push(tmp ，X)；While(!StackEmpty(tmp)Pop(tmp,X)；Push(S1，X)；四、算法设计题1、有两个栈s1和s2共享存储空间cm（下标为0,.,m-1），其中一个栈底设在c0处，另一个栈底设在cm-1处，分别编写s1和s2的进栈Push(i,x)、出栈Pop(i,x)和设置栈空Setnull(i)的函数，其中i=1,2。注意：仅当整个空间c占满时才产生上溢。2、假设一个算术表达式中包含圆括弧、方括弧和花括弧3种类型的括弧，编写一个判别表达式中括弧是否正确配对的函数。以字符“#”作为算术表达式的结束符。3、回文是指正读和反读均相同的字符序列，如“abba”和“abdba”均是回