洛阳理工数据结构期末复习题

《洛阳理工数据结构期末复习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构一适用班级：B110501-07班考试时间：120分钟一、选择题（每小题1分，共15分）1．算法分析的目的是（　　）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性2．把长度为m的单链表LB接在长度为n的单链表LA之后的算法的时间复杂度为()A．O(m)B．O(n)C．O(m+n)D．O(1)3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（　　）A．插入B．删除C．定位D．排序4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出

2、栈序列为（　　）A．3，2，6，1，4，5B．5，6，4，2，3，1C．1，2，5，3，4，6D．3，4，2，1，6，55．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2,1)的值为（　　）A．15B．16C．17D．186．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是（　　）A.108　　　B.112　　　C.116　　D.1207．有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是()A.访问第

3、i个节点（1≤i≤n）B.在第i个节点后插入一个新节点（1≤i≤n）C.删除第i个节点（1≤i≤n）D.将n个节点从小到大排序8.将递归过程转化为非递归过程需用到()A．栈B．队C．线性表D．链表9.设有一广义表E=（a,b,(c,d)），其长度为()A．2B．3C．4D．510．在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指结点，则执行（　　）　　A.s->next=p;p->next=sB.p-next=s;s->next=pC.p=s;s->next=p->nextD.s->next=p->ne

4、xt;p->next=s11.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。A.

5、top[2]-top[1]

6、=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]12.有一个100×90的稀疏矩阵，非0元素有10，设每个整型数占2个字节，则用三元组表示该矩阵时，所需的字节数是（）。A．20B．66C．18000D．3313.为解决计算机主机与打印机之间速度不匹

7、配的问题通常设置一个打印数据缓冲区。打印机将要打印输出的数据一次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）A．栈B.队列C.树D.图14.某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。设入队顺序是abcde,则不可能得到的出队顺序是（）。A.bacdeB.dbaceC.dbcaeD.ecbad15.在链表中最常用的操作是删除表中最后一个结点和在最后一个结点之后插入元素，则采用()最节省时间。第3页共3页A．头指针的单向循环链表B．双向链表C．带尾指针的单向循环链表D．带头

8、指针双向循环链表二、填空题（每空2分，共30分）1.数据结构所研究的内容包括数据的逻辑结构、数据的物理结构、数据的运算集合。存储结构（又称物理结构）是逻辑结构在_____，它包括_____和_____的表示。2.在顺序栈中，当栈顶指针top＝-1时，表示_____；当top=MaxSize-l时，表示_____。3.假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为___。4.在数据结构中，数据的逻辑结构分线性结构和。5.称算法的时间复杂度为O(f(n))，其含义是指算

9、法的执行时间和_______的数量级相同。6.在一个长度为n的单链表L中，删除链表中p所指结点的前驱结点的时间复杂度为__。7.在具有n个单元的循环队列中，队满时共有　　　个元素。8.对于栈只能在_______插入和删除元素。9.通常以正确性、健壮性、可读性和等四个方面作为设计一个“好”算法的目标。10.广义表A=((a，b，c)，(d，e，f))的表尾为。11.设有一个顺序栈S，元素sl，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，sl，则顺序栈的容量至少应为。12.数组

10、A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放的存储器内，该数组按行存放，元素A[5][8]的起始地址为。三、判断题（每题1分，共10分）1.算法的时间复杂度是算法执行时间的绝对度量。2.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。3.栈和队列都