本科随堂测验(带答案)

《本科随堂测验(带答案)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第1次测验1.算法的时间复杂度取决于（）A.问题的规模B.待处理数据的初态C.A和B2.从逻辑上可以把数据结构分为（）两大类。A.动态结构、静态结构B・顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构数据的逻辑结构：指反映数据元素之间的逻辑关系的数据结构丿其屮的逻辑关系是指数据元素之间的前后件关系丿而与他们在计算机屮的存储位置无关.逻辑结构包括:集合;2.线性结构;3.树形结构;4.图形结构.《数据结构》数据结构课程屮数据的逻辑结构分为线性结构和非线性结构.対于数据结构课程而言丿简单地说,线性结构是人个数据元素的有序（次序）集合•它有四个基本

2、特征:2.集合中必存在唯一的一个"第一个元素〃；2.集合中必存在唯一的一个"最后的元素〃；3除最后元素之外丿其它数据元素均有唯一的”后继”；4.除第一元索之外'其它数据元素均有唯一的"前驱数据结构屮线性结构指的是数据元素之间存在着"一对一''的线性关系的数据结构.如（曲仏2山勻“心为第一个元素山八为最后一个元素』匕集合即为一个线性结构的集合.相对应于线性结构丿非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后驱.常用的线性结构有：线性表丿栈,队列,双队列'数组'串.常见的非线性结构有：树(二叉树等)'图(网等).3・以下属于逻辑结构的是()。A.丿

3、帧序表B.哈希表C.有序表有序表是排好序的线性表D.单链表4.下述哪一条是顺序存储结构的优点？()A.存储密度大B.插入运算方便C.带头结点的双循环链表D.单循环链表C.删除运算方便D.可方便地用于各种逻辑结构的存储表示链式存储结构：(1)占用额外的空间以存储指针(浪费空间)(2)存取某个元素速度慢(3)插入元素和删除元素速度快(4)没有空间限制，存储元素的个数无上限，基本只与内存空间大小有关.顺序存储结构：(1)空间利用率高(2)存取某个元素速度快(3)插入元素和删除元素存在元素移动，速度慢，耗时⑷有空间限制，当需要存取的元素个数可能多于顺序表的元素个数时，

4、会出现“溢出”问题.当元素个数远少于预先分配的空间时，空间浪费巨大.在存取元素频繁，但删除或插入操作较少的情况宜用顺序表.堆排序，二分査找适宜用顺序表.5・若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用()存储方式最节省时间。B.双链表A.顺序表6.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用()存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表因为有尾指针，所以时间时间复杂度为0(1),其他的都要0(n)7.若某表最常用的操作是在最后一个结点之后

5、插入一个结点或删除最后一个结点。则采用()存储方式最节省运算时间。A・单链表B.双链表c・单循环链表D.带头结点的双循环链表双循坏链表能够通过头结点的前驱就是尾结点，能够迅速找到尾结点，然后进行插入和删除操作&链表不具有的特点是()A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比9.对于顺序表,访问第i位置结点和增加、删除结点的时间复杂度为()。A.O(n)O(n)B.O(n)0(1)C.0(1)O(n)D.0(1)0(1)10.线性表以链接方式存储时，访问第i位置元素的时间复杂性为()A・O(i)B・0(

6、1)C・O(n)D・O(i・l)11・下面程序段的时间复杂度是O(n)。4inti=l,k=100;while(inext!=NULL。13•长度为n的顺序表，在其第i个元素(l

7、123---n,若输出序列的第一个元素是n,输出第i（l<=i<=n）个元素是（）。A.不确定B.n-i+1C・iD.n-i因为栈的特点是“先进后出”，所以当第一个出栈的是n时,意味着l・・（n・l）这些数都在栈内，所以第二个出栈的肯定是ml,第n个出栈的一定是1•所以，第i个出栈的必定是（n+1-i）・3.若一个栈的输入序列为1,2,3,…,n,输出序列的第一^元素是i，则第j个输出元素是（）。A.i-j-1B.i-jC.j-i+1D.不确定的B.应该是不确定的；因为他没说要小次性全进完，也没说要一次性全出完，只要进入的序列不变就行了。所以不确定的设1=2,

8、J=3；进入怕方法有好多种，出来的方法