数据结构()测试.doc

《数据结构()测试.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一题、单项选择题（每题1分，5道题共5分）1、在线性结构中，除最后一个以外的其余结点有＿＿＿＿＿＿＿＿个后继结点。A、0B、1C、任意多D、2、下列函数中，时间复杂度最小的是＿＿＿＿＿＿＿＿。A、nlogn+1000lognB、n[logn]-1000logn***C、n*n-1000lognD、2nlogn-1000logn3、栈和队列属于＿＿＿＿＿＿＿＿逻辑结构。A、线性B、非线性C、动态D、静态4、一个算法所需时间由下述递归方程表示，该算法的时间复杂度是＿＿＿＿＿＿＿＿。T(1)＝1,T(n)＝2T(n/2)+n(n>1)其中n为问题的规模，设n为2的整数幂。A、O(n)B、O

2、(logn)C、O(nlogn)D、O(n*n)5、n为正整数，下列程序段的时间复杂度是＿＿＿＿＿＿＿＿。x＝n;y＝0;while(x>＝(y+1)*(y+1))y++;A、O(n)B、O(n*n)C、O(n[1/2])***D、O(1)第二题、多项选择题（每题2分，5道题共10分）1、数据结构的三要素是指＿＿＿＿＿＿＿＿。A、数据元素B、逻辑结构C、物理结构D、顺序结构E、链式结构2、下列说法中，正确的是＿＿＿＿＿＿＿＿。A、数据元素是数据的基本单位B、数据项是数据中不可分割的最小标识单位C、数据可由若干个数据元素组成D、数据项可由若干个数据元素组成3、算法分析的主要方面是＿＿＿＿

3、＿＿＿＿。A、时间复杂度B、空间复杂度C、数据复杂性D、程序复杂性4、一个"好"的算法应达到的目标有＿＿＿＿＿＿＿＿。A、正确性B、可行性C、可读性D、健壮性E、高效与低存储量F、确定性5、研究数据结构就是研究＿＿＿＿＿＿＿＿。A、数据的逻辑结构B、数据的物理结构C、数据在运算上的实现D、数据的复杂度第三题、判断题（每题1分，5道题共5分）1、任何数据结构都具备三个基本运算：插入、删除和查找。（）正确错误2、数据元素可以由很多数据项组成。（）正确错误3、数据元素是数据的基本单位。（）正确错误4、算法分析的目的是研究算法中输入和输出的关系。（）正确错误5、在计算机科学中，数据的含义可以很

4、广泛，图像、声音等都可以通过编码的形式而归之于数据的范畴。（）正确错误第二章1、顺序表是线性表的一种＿＿＿＿＿＿＿的存储结构。A、顺序存取B、随机存取C、索引存取D、2、在一个单链表中，在p所指结点之后插入s所指结点应执行＿＿＿＿＿＿＿＿。A、s->next＝p;p->next＝s;B、s->next＝p->next;p->next＝s;C、s->next＝p->next;p＝s;D、p->next＝s;s->next＝p;3、在n个元素的单链表中插入或删除一个元素的算法的时间复杂度为＿＿＿＿＿＿＿＿。A、O(1)B、O(n)C、O(n*n)D、4、建立n个元素的单链表，其算法的时间复

5、杂度为＿＿＿＿＿＿＿＿。A、O(1)B、O(n)C、O(n*n)D、5、建立n个元素的有序单链表，其算法的时间复杂度为＿＿＿＿＿＿＿＿。A、O(1)B、O(n)C、O(n*n)D、O(n*n*n)第二题、多项选择题（每题2分，5道题共10分）1、顺序表的特点是＿＿＿＿＿＿＿＿。A、随机存取B、顺序存取C、逻辑相邻的元素物理位置也相邻D、元素的物理位置可以相邻也可以不相邻2、单链表的特点是＿＿＿＿＿＿＿＿。A、随机存取B、顺序存取C、逻辑相邻的元素物理位置也相邻D、元素的物理位置可以相邻也可以不相邻3、在双向循环链表（L为头指针）中，指针p所指结点为尾结点的条件是＿＿＿＿＿＿＿＿。A、p

6、＝＝LB、p->next＝＝LC、L->prior＝＝pD、L->next＝＝p4、一元多项式中非零项的系数指数对所成的线性表可用＿＿＿＿＿＿＿＿来表示。A、顺序结构B、链式结构C、逻辑结构D、索引结构5、在双向循环链表中，若要在指针q所指结点的后面插入一个s所指结点，则须执行下列语句：s->prior＝q;s->next＝q->next;＿＿＿＿＿＿＿;q->next＝s;A、q->next->prior＝sB、s＝qC、s->next->prior＝sD、s->prior->next＝q第三题、判断题（每题1分，5道题共5分）1、在单链表中插入或删除元素时是以结点的指针变化来反映逻

7、辑关系的变化，因此不需要移动元素。正确错误2、整个单链表的存取必须从头指针开始沿链表进行，因此单链表中的元素是可以进行随机存取的。正确错误3、一元多项式的链式存储结构优于顺序存储结构。（）正确错误4、在双向循环链表中插入或删除元素时仅需要修改结点的指针，不需要移动元素，因此算法的时间复杂度为O(1)。（）正确错误5、用线性链表表示一元多项式时，其有序性是指链表中的结点按此项的系数由小到大有序排列。正确错误第一题、单项选择题（每题1分，5道题共5