本科随堂测验(带答案).docx

本科随堂测验(带答案).docx第1次测验算法的时间复杂度取决于( )()两大类。、静态结构B・顺序结构、、、构造型结构数据的逻辑结构::集合;线性结构;树形结构;图形结构.《数据结构》,线性结构是人个数据元素的有序(次序)集合•它有四个基本特征:"第一个元素〃;"最后的元素〃;3除最后元素之外丿其它数据元素均有唯一的”后继”;'其它数据元素均有唯一的"前驱数据结构屮线性结构指的是数据元素之间存在着"一对一''(曲仏2山勻“心为第一个元素山八为最后一个元素』:线性表丿栈,队列,双队列'数组':树(二叉树等)'图(网等).3・以下属于逻辑结构的是( )。 ?( ) :占用额外的空间以存储指针(浪费空间)存取某个元素速度慢插入元素和删除元素速度快没有空间限制,存储元素的个数无上限,:空间利用率高存取某个元素速度快插入元素和删除元素存在元素移动,速度慢,耗时⑷有空间限制,当需要存取的元素个数可能多于顺序表的元素个数时,会出现“溢出”,,,・若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( )存储方式最节省时间。,则采用( )存储方式最节省运算时间。单链表 ,所以时间时间复杂度为0(1),其他的都要0(n)若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用()存储方式最节省运算时间。A・・,能够迅速找到尾结点,然后进行插入和删除操作&链表不具有的特点是( )插入、 ,访问第i位置结点和增加、删除结点的时间复杂度为()。O(n)O(n) (n)0(1)(1)O(n) (1)0(1)线性表以链接方式存储时,访问第i位置元素的时间复杂性为()A・O(i)B・0(1)C・O(n) D・O(i・l)11・下面程序段的时间复杂度是O(n) 。4inti=l,k=100;while(i<n){k=k+l;i+=2;},指针p所指结点有后继结点的条件是:p->next!=NULL。13•长度为n的顺序表,在其第i个元素(l<i<n4-l)之前插入一个元素时,需向后移动n・i+l个元素,删除第i个元素(l<i<n)时,需向前移动n-i个元素。14•请写出顺序表的类型定义。。第2次测验、(---n,若输出序列的第一个元素是n,输出第i(l<=i<=n)个元素是( )。 -i+1 C・i -i因为栈的特点是“先进后出”,所以当第一个出栈的是n时,意味着l・・(n・l)这些数都在栈内,所以第二个出栈的肯定是ml,第n个出栈的一定是1•所以,第i个出栈的必定是(n+1-i)・若一个栈的输入序列为1,2,3,…,n,输出序列的第一^元素是i,则第j个输出元素是( )。-j-1 -j -i+1 ;因为他没说要小次性全进完,也没说要一次性全出完,只要进入的序列不变就行了。所以不确定的设1=2,J=3;进入怕方法有好多种,出来的方法也有好多种的,1进,1出,2进,2出,3进,4进,4出,3出;