搜索
第1页共7页……………………………………………装………………………………订…………………………线………………………………………………………此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写北京理工大学珠海学院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、以下算法的时间复杂度为()。voidfun(intn){inti=l;while(i=n)i=i*2;}A.O(n)B.O(n2)C.O(nlog2n)D.O(log2n)第2页共7页3、带头结点的单链表为空的判定条件是（）。A.head==NULLB.head-next==NULLC.head-next==headD.head!=NULL4.在一个具有n个单元的顺序栈中，假设栈底是存储地址的低端，现以top作为栈顶指针（指向栈顶元素的下一个位置），当进行出栈操作时，假定栈非空，top的变化是()。A.top=top+1B.top=top-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.在单链表中只能通过节点的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个元素的前趋元素，则采用（）存储方式最节省时间。A.顺序表B.单链表C.双向链表D.循环链表11、下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储12、循环链表主要优点是（）。第3页共7页……………………………………………装………………………………订…………………………线………………………………………………………此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写A.不再需要头指针了B.已知某个结点的位置后，能够容易找到它的直接前趋C.在进行插入、删除运算时，能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表13、与单链表相比，双链表的优点之一是（）。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针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只有两个存储单元，在下列表达式中，不发生溢出的是（）。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,1..50]按行优先存入一维数组B[1..n]中，A中元素A[30,20]在B数组中的位置为。5.设S=〃IamaStudent〃，T=〃good〃,则ConCat(T,SubStr(S,7,8)))=。三、简答题（每题6分，共30分）【得分：】1.假设Q[0，9]是一个非循环线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，如果不能入队，请指出其元素，第4页共7页并说明理由。d,e,b,g,h入队d,e出队I,j,k,l,m入队b出队n,o,p,q,r入队。2.已知稀疏矩阵如下所以，请写出该稀疏矩阵对应的三元组表示和该矩阵转制矩阵的三元组表示。3．设有多项式a(x)=9+8x+9x4+5x10，b(x)=-2x+22x7-5x10，c(x)=a(x)+b(x)。用单链表给出a(x)、b(x)和c(x)的存储表示。第5页共7页……………………………………………装………………………………订…………………………线………………………………………………………此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写4.若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？5．对于堆栈，给出三个输入项A，B，C，如果输入项序列为ABC，试给出全部可能的输出序列，并写出每种序列对应的操作。例如：A进B进C进C出B出A出，产生的序列为CBA。四、算法阅读题（每空2分，共16分）1．以下为头插法建立单链表的算法，请在下划线处填上适当的语句。voidCreateList_L(LinkList&L,intn){//输入n个元素的值，建立带头结点的单链表L//每次都将新结点(由p指向)插入到头结点的后面。L=(LinkList)malloc(sizeof(LNode));;//先建立一个带头结点的单链表for(i=n;i0;--i){p=(LinkList)malloc(sizeof(LNode));scanf(&p→data);;L→next=p;}}//CreateList_L2．已知循环队列存储结构的定义，以下运算实现在循环队列上的入队列和出队列，请在下划线处用适当的语句予以填充。#defineMAXQSIZE100//最大队列长度第6页共7页typedefstruct{QElemType*base;//初始化的动态分配存储空间intfront;//头指针,若队列不空,指向队列头元素.intrear;//尾指针,若队列不空,指向队列尾元素的下一个位置.}SqQueue;StatusEnQueue(SqQueue&Q,QElemTypee){//入队if(________________________)returnERROR;//队列满Q.base[Q.rear]=e;________________________returnOK;}//EnQueueStatusDeQueue(LinkQueue&Q,QElemType&e){//出队if(________________________)returnERROR;//队列空e=Q.base[Q.front];________________________;returnOK;}//DeQueue3．以下为带头结点的单链表的定位运算，分析算法，请在下划线处填上适当的语句。intLocateElem(LinkListhead,DataTypex){/*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/p=head-next;j=1;while(p!=NULL&&_______________){______________;j++;}if(p&&p-data==x)return(j);else{return(0);}第7页共7页……………………………………………装………………………………订…………………………线………………………………………………………此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写}五、算法设计题（1小题，共14分）【得分：】1．已知栈的基本操作函数：intInitStack(SqStack*S);//构造空栈intStackEmpty(SqStack*S);//判断栈空intPush(SqStack*S,ElemTypee);//入栈intPop(SqStack*S,ElemType*e);//出栈试写一算法conversion实现十进制数转换为十六进制数，利用上面的基本操作来实现。