《数据结构》期中试卷-2015-2016学年第一学期.doc

《《数据结构》期中试卷-2015-2016学年第一学期.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京理工大学珠海学院2015～2016学年第一学期《数据结构》期中试卷诚信声明考场是严肃的，作弊是可耻的，对作弊人的处分是严厉的。我承诺遵守考场纪律，不存在抄袭及其它违纪行为。考生（承诺人）签字：专业：班级：学号：适用年级专业：14级计科，网工，数媒专业试卷说明：闭卷，考试时间90分钟题号一二三四总分得分一、单项选择题（每小题2分，共30分）【得分：】1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.1、设计一个判别表达式中左、右括号是否配对出现的算法，采用()数据结构最佳。A.线性表的顺序存储结构B.栈C.队列D.线性表的链

2、式存储结构2、以下算法的时间复杂度为()。voidfun(intn){inti=l;while(i<=n)i=i*2;}A.O(n)B.O(n2)C.O(nlog2n)D.O(log2n)3、带头结点的单链表为空的判定条件是（）。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL4.在一个具有n个单元的顺序栈中，假设栈底是存储地址的低端，现以top作为栈顶指针（指向栈顶元素的下一个位置），当进行出栈操作时，假定栈非空，top的变化是()。A.top=top+1B.top=top-

3、1C.top不变D.top不确定5.一个栈的入栈序列为a，b，c，d则出栈序列不可能的是()。A.a，b，c，dB、c，b，a，dC.d，c，b，aD、d，b，c，a6、二维数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，该数组按行优先存放时，元素A[6][8]的起始地址为（）。A.SA+210B.SA+171C.SA+204D.以上都不对7、以下关于单链表的叙述中，错误的是（）。A.在单链表中插入一个节点必须先找到其前趋节点B.在单链表中删除一个节点必须先找到其前趋节点^C.在单链表中

4、只能通过节点的next指针向后查找节点D.在单链表中查找第i个节点的时间复杂度为0(1)8.链表不具有的特点是（）。A.可随机访问任一元素　B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比9.在一个单链表中，已知q是p的前趋结点，若q和p之间插入结点s，则执行（）。Ａ.s->next=p->next;p->next=s;Ｂ.p->next=s->next;s->next=p;Ｃ.q->next=s;s->next=p;Ｄ.p->next=s;s->next=q;10.若某线性表中最常用的操作是取第i个元素和找第i个元

5、素的前趋元素，则采用（）存储方式最节省时间。A.顺序表B.单链表C.双向链表D.循环链表11、下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储12、循环链表主要优点是（）。A.不再需要头指针了B.已知某个结点的位置后，能够容易找到它的直接前趋C.在进行插入、删除运算时，能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表13、与单链表相比，双链表的优点之一是（）。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指

6、针或表尾指针D.前后访问相邻节点更灵活14.循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为空和为满的条件分别是（）A.Q.front!=Q.rear,Q.front==Q.rearB.Q.front==Q.rear,Q.front!=Q.rearC.Q.front==Q.rear,Q.front==(Q.rear+1)%nD.Q.front==Q.rear,Q.front!=(Q.rear+1)%n15.利用栈求表达式的值时，设立操作数栈OPND，假设OPND只有两个存

7、储单元，在下列表达式中，不发生溢出的是（）。A.A-B*(C-D)B.(A-B)*C-DC.(A-B*C)-DD.(A-B)*(C-D)二、填空题（每空2分，共10分）【得分：】1.若一个算法中的语句频度之和为T（n）=3n+n*log2n+4，则算法的时间复杂度为______。2.对于n阶对称矩阵，进行压缩存储，如果以行序或列序放入一维数组中，则需要个存储单元。3．在非空双向循环链表中，在结点q的前面插入结点p的过程如下：p->prior=q->prior;q->prior->next=p;p->next=q;;4.将一个下三角矩阵A[1..50

8、,1..50]按行优先存入一维数组B[1..n]中，A中元素A[30,20]在B数组中的位置为。5.设S=〃IamaStu