《本科随堂测验(带答案)》由会员分享，可在线阅读，更多相关《本科随堂测验(带答案)（17页珍藏版）》请在金锄头文库上搜索。
1、第1次测验1. 算法的时间复杂度取决于（）A.问题的规模B.待处理数据的初态C.A和B从逻辑上可以把数据结构分为（）两大类。A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构数据的逻辑结构：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关?逻辑结构包括：乙集合；线性结构；2. 树形结构；4.图形结构.数据结构数据结构课程中数据的逻辑结构分为线性结构和非线性结构.对于数据结构课程而言，简单地说线性结构是1. 集合中必存在唯一的一个第一个元素2. 集合中必存在唯一的一个最后的元素3. 除最
2、后元素之外，其它数据元素均有唯一的4. 除第一元素之外其它数据元素均有唯一的数据结构中线性结构指的是数据元素之间存在着n个数据元素的有序（次序）集合.它有四个基本特征后继；前驱一对一”的线性关系的数据结构.如山工为第一个元素丿an为最后一个元素丿此集合即为一个线性结构的集合.相对应于线性结构,非线丿队列，双队列擞组，串常见的非线性结构有：树(二叉树等)，图(网等).2. 以下属于逻辑结构的是()。A.丿顺序表B.哈希表C.有序表有序表是排好序的线性表D.单链表3. 下述哪一条是顺序存储结构的优点？()A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示链式存储结
3、构：占用额外的空间以存储指针(浪费空间)存取某个元素速度慢(2) 插入元素和删除元素速度快没有空间限制，存储元素的个数无上限，基本只与内存空间大小有关.顺序存储结构：(1) 空间利用率高存取某个元素速度快(2) 插入元素和删除元素存在元素移动，速度慢，耗时有空间限制，当需要存取的元素个数可能多于顺序表的元素个数时，会岀现“溢岀问题.当元素个数远少于预先分配的空间时，空间浪费巨大.在存取元素频繁,但删除或插入操作较少的情况宜用顺序表?堆排序，二分查找适宜用顺序表.4. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用()存储方式最节省时间。A.顺序表B.双链表C.
4、带头结点的双循环链表D.单循环链表某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用()存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表因为有尾指针，所以时间时间复杂度为0(1)，其他的都要0(n)5. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则釆用()存储方式最节省运算时间。A. 单链表B.双链表C.单循环链表D.带头结点的双循环链表双循环链表能够通过头结点的前驱就是尾结点，能够迅速找到尾结点，然后进行插入和删除操作&链表不具有的特点是()A.插入、删除不需要移动兀素B.可随机访问任兀素
5、C.不必事先估计存储空间D.所需空间与线性长度成正比9.对于顺序表，访问第i位置结点和增加、删除结点的时间复杂度为()0A.O(n)O(n)B.O(n)0(1)C.0(1)O(n)D.0(1)0(1)10. 线性表以链接方式存储时，访问第i位置元素的时间复杂性为()A. 0(i)B.0(1)C.0(n)D.O(i-I)下面程序段的时间复杂度是O(n)。4inti=l,k=100;while(inext!二NULL。11. 长度为n的顺序表，在其第i个元素(lin+l)之前插入一个元素时，需向后移动n-i+1个元素,删除第i个元素(lin)时，需向前移动n-i个元素。14请写出顺序表的类型定义。
6、15请写出单链表的类型定义。第2次测验C.后进后出D.不分顺序n,若输出序列的第一个元素是n,）。C.iD.n-i因为栈的特点是“先进（n-l）这些数都在栈内，所以第二个岀栈的肯定是n-I,第（n+l?i）?n；输出序列的第一个元素是）。C.j-i+1D.不确定的、选择题对于栈操作数据的原则是（）A. 先进先出B.后进先出一个栈的输入序列为123?输出第i（lUiUn）个元素是（A. 不确定B.n-i+1后出”，所以当第一个出栈的是n时,意味着l.n个出栈的一定是1?所以，第i个出栈的必定是若一个栈的输入序列为1,2,3,i,则第j个输出元素是（i-j-1B.i-jB.应该是不确定的；因为他没
7、说要小次性全进完，也没说要一次性全出完，只要进入的序列不变就行了。所以不确定的设1=2,J=3；进入怕方法有好多种，出来的方法也有好多种的，1进，1出，2进，2出，3进，4进，4出，3出；1. 有六个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 543612B.453126C.346521D.234156栈在（）中应用。A.递归调用B.子程序调用C.表达式求值DAB,C一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分2. 表达式a*(b+c)-d的后缀表达式是()oA.abcd*+-B.abc+*d-设计一个判别表
8、达式中左,()数据结构最佳。Ct修改头指针存储结构C.线性表的链式存储结构A.abcd*+-B.abc+*d-设计一个判别表达式中左,()数据结构最佳。Ct修改头指针存储结构C.线性表的链式存储结构C.abc*+d-D.-+*abcd右括号是否配对出现的算法，采用仅修改尾指针可能都要修改D.栈9用链接方式存储的队列,在进行删除运算时(1.0.假设以数组Am存放循环队列的元素，其头尾指针分别为front和rear,则当前队列中的元素个数为(A.(rear-front+m)%mC.(front-rear+m)%m11.循环队列存储在数组A.rear=rear+lC.rear=(rear+l)mod
9、mA.(rear-front+m)%mC.(front-rear+m)%m11.循环队列存储在数组A.rear=rear+lC.rear=(rear+l)modmB. rear-front+1D.(rear-front)%m)oA0.m中，则入队时的操作为(rear=(rear+l)mod(m-1)D.rear=(rear+l)mod(m+l)12.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3,当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()A.1和5B.2和4当出队列中删除一个元素，也就是出队，即front搜索+1:=4再
10、插入两个元素，即rear+2=28C.4和2D.5和113.最大容量为n的循环队列，队尾指针是rear,队头是front,A（rear+1）MODn=frontCrear+l二front栈和队列都是（A顺序存储的线性结构C. 限制存取点的线性结构B. rear二frontD. (rear-1)MODn=frontB.链式存储的非线性结构D.限制存取点的非线性结设栈S和队列Q的初始状态为空，元素el,e2,e3,e4,e5和e6依次通过栈S,个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,el则栈S的容量至少应该是（）oA. 6B.4C.3D.2下面关于串的的叙述中，
11、哪一个是不正确的？（）A.串是字符的有限序列B.空串是由空格构成的串含0个字符的串为空串A. 模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储设有两个串p和q,其中q是P的子串，求q在p中首次出现的位置的算法称为（A.求子串A.求子串B.联接C.匹配D.求串长15. 串的长度是指（A.串中所含不同字母的个数A.串中所含不同字母的个数B.串中所含字符的个数C. 串中所含不同字符的个数CI. 串中所含不同字符的个数D. 串中所含非空格字符的个数16. 设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储,如为第一元素，其存储地址为1,每个元素占一个地址空间，则a*5的
12、A.B.C.D.13331840设有数组Ai,j,数组的每个元素长度为3字节，i的值为1到8,j的值为1到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时，元素A5,8的存储首地址为()oA.BA+141B.BA+180这个问题只要找出元素A5,8在以列为主存放时，到第一元素之间总共有多少个元素，所谓列存储是一列存完了，再存下面一列。A5,8前面有完整的7列，每死8个元素，共有56个元素，第8列，A5,8前共4个元素，总共有60个元素，数组的每个元素长度为3字节共180个字节元素A5,8的存储首地址为：BA+(j-1)*8+i-1)*3=BA+180C.BA+222D.BA+225有
13、一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是()0A.60B.66每个元素要用行号，列号，元素值来表示，由于二维稀疏矩阵的大小都是在256之内，所以行号和列号只需要char来存储。在用三元组表示稀疏矩阵，还要三个成员来记住，矩阵的行数列数，总的元素数，所以所需的字节数是10*(1+1+1)*2+3*2=66C.18000D.33已知广义表L二(x,y,z),a,(u,t,w),从L表中取出原子项t的运算是()。A.head(tail(tail(L)B.tail(head(head(tail(L)C. head(tail(head(t
14、ail(L)D. head(tail(head(tail(tail(L)getTaii(L)得到的是(a,(u,t,w)getTail(getTail(L)t得到的就是(u,t,w)getHead(getTail(getTail(L)得到的就是(u,t,w)getTail(getHead(getTail(getTail(L)得到的就是(t,w)getHead(getTail(getHead(getTail(getTail(L)得到的就是(t,w)getHead(getHead(getTail(getHead(getTail(getTail(L)得到的就是t.这里要注意的是,getHead得到的是一个原子，而getTail得到的却是原子外组成的新的广义表，不管是只有一个元素，但也是一个广义表，而不是直接的元素.17. 广义表运算式Ta订(a,b),(c,d)的操作结果是()。A.B.D.d(c,d)c,d18. 设广义表L二(a,b,c),则L的长度和深度分别为(A.1和1B.1和325. 下面说法不正确的是(A.广义表的表头总是一个广义表C.广义表难以用顺序存储结构A.1和1B.1和326. 下面说法不正确的是(A.广义表的表头总是一个广义表C.广义表难以用顺序存储结构C.1和2D.2和3)oB. 广义表的表尾总是一个广义表D.广义表可以是一个多层次的结构第
