数据结构考试试题(带答案)

系别班次学号姓名第1页共14页××科技大学成都学院二零零八至二零零九学年第一学期数据结构课堂测试（60分钟）闭卷考试时间：题号一二三总分评卷教师分数一．填空题（每空2分，共40分）；1.数据结构算法中，通常用时间复杂度和__空间复杂度___两种方法衡量其效率。2.下面程序段的时间复杂度为___O(n2)______。(n1)for(i=1;i=n;i++)for(j=1;j=i;j++)x=x+1;3.静态链表中指针表示的是______下一结点的地址______。4.线型表、栈和队列都是____线型_______结构，可以在线型表的____任意___位置插入和删除元素；对于栈只能在____栈顶_____插入和删除元素；对于队列只能在____队尾___插入元素和_____队头_____删除元素。5.在具有n个单元的循环队列中，队满时共有_____n-1____个元素。6.在一个长度为n的顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动__n-i+1__个元素。7.在n个结点的单链表中要删除已知结点*p，需找到它的_____前驱________。8.带有一个头结点的单链表head为空的条件是_________head-next==NULL__________。9.在栈顶指针为hs的链栈中，判断栈空的条件是_________hs==NULL__________。10.在hq的链队列中，判定只有一个结点的条件是__hq.front-next==hq.rear________。11.非空的循环单链表head的尾结点（由p指向），满足条件____p-next==head。12.两个串相等的充分必要条件是______串长相等且对应字符相等_______。13.空串是_______长度为0的串______，其长度等于___0________。14.空格串是______由空格字符组成的串______，其长度等于_____空格的个数_________。二．单项选择题（每题2分，共30分）；（说明：请将答案填入下表中）题号12345678910答案AABBDBCBBC题号1112131415答案AACDD1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表2.设a1、a2、a3为3个结点，则如下的链式存储结构称为：A系别班次学号姓名第2页共14页表元编号结点表元间关系1a132a213a32A．循环链表B．单链表C．双向循环链表D．双向链表3.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（B）A.543612B.346521C.453126D.2341564.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（B）。A.top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]5.数组Ｑ［ｎ］用来表示一个循环队列，front为当前队列头元素的前一位置，rear为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为(D)A.rear－frontB.（n＋front－rear）%nC.n＋rear－frontD.（n＋rear－front）%n6.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4,e6,e5，e3,e1则栈S的容量至少应该是(B)。A．6B.4C.3D.27.在数据结构中，从逻辑上可以把数据结构分成（C）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构8.判定一个顺序栈ST（最多元素为N）为空的条件是（B）。A．ST．top！=ST.baseB．ST．top==ST.baseC．ST．top！=ND．ST．top==N9.一个队列的入列序列是1，2，3，4，则队列的输出序列是B。A．4,3,2,1B．1,2,3,4C．1,4,3,2D．3,2,4,110.判定一个循环队列QU(最多元素为N)为空的条件是C。A．QU.front==（QU.rear+1）%NB．QU.front！=（QU.rear+1）%NC．QU.front==QU.rearD．QU.front！=QU.rear11.判定一个循环队列QU（最多元素为m0）为满队列的条件是A。A．QU.front==（QU.rear+1）%NB．QU.front！=（QU.rear+1）%NC．QU.front==QU.rearD．QU.front！=QU.rear+112.不带头结点的单链表head为空的判定条件是AA．head=NULLB．head-next=NULLC．head-next=headD．head!=NULL13.15.在双向链表指针p的结点前插入一个指针q的结点操作是（C）。系别班次学号姓名第3页共14页A.p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B.p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C.q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D.q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;14.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较___D___个结点。A．nB．n/2C．(n—1)/2D．(n+1)/215.设串s1=‘ABCDEFG’,s2='PQRST',函数con(x,y)返回x和y串的连接串，subs（s,i,j）返回串s的从序号i的字符开始的j个字符组成的字串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是DA）BCDEFB）BCDEFGC）BCPQRSTD）BCDEFEF三．综合题（每题6分，共30分）1.线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以单链表方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节,由大写字母表示）组成，如下所示：p47q23r05s31t17100120其中指针p，q，r，s，t的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？(共6分)2.答：p=108q=116r=112s=0或NULLt=100首址=104末址=112。3.如果想将输入的一个字符序列逆序输出，如输入“abcdef”，输出“fedcba”，请分析用线性表、堆栈和队列等方式正确输出的可能性？(共6分)线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现。4.写出删除顺序表中第i个元素的算法：(共6分)系别班次学号姓名第4页共14页StatusListDelete_sq(SqList&L,inti,ElemType&e)Statusdel_sqllist(SqList&L,inti,ElemType&e){if(i1‖iL.length)returnERROR;e=L.elem[i];for(j=i+1;j=L.length;j++)L.elem[j-1]=L.elem[j];--L.length;returnOK;}5.写出顺序栈的入栈算法(共6分)StatusPush(SqStack&S,SelemTypee)voidPush(Stack&S,ElemTypee){//在栈顶之上插入元素e为新的栈顶元素p=newLNode;//建新的结点if(!p)exit(1);//存储分配失败p-data=e;p-next=S.top;//链接到原来的栈顶S.top=p;//移动栈顶指针++S.length;//栈的长度增1}//Push6.写出链队列的出队列算法(共6分)StatusDeQueue(LinkQueue&Q,QelemType&e)StatusDeQueue(LinkQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，//用e返回其值，并返回OK；否则返回ERROR系别班次学号姓名第5页共14页if(Q.front==Q.rear)returnERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}系别班次学号姓名第6页共14页××科技大学成都学院2008~2009学年第一学期中期试题——数据结构答案一．填空题（每题2分，共40分）；题号参考答案1空间复杂度2O(n2)3下一结点的地址4线型，任意，栈顶，队尾，队头5n-16n-i+17前驱8head-next==NULL9hs==NULL10hq.front-next==hq.rear11p-next==head12串长相等且对应字符相等13长度为0的串，014由空格字符组成的串，空格的个数二．单项选择题（每题2分，共30分）；题号12345678910答案AABBDBCBBC题号1112131415答案AACDD三．综合题（共30分）7.p=108q=116r=112s=0或NULLt=100首址=104末址=112。8.线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现。3．Statusdel_sqllist(SqList&L,inti,ElemType&e)系别班次学号姓名第7页共14页{if(i1‖iL.length)returnERROR;e=L.elem[i];for(j=i+1;j=L.length;j++)L.elem[j-1]=L.elem[j];--L.length;returnOK;}4.voidPush(Stack&S,ElemTypee){//在栈顶之上插入元素e为新的栈顶元素p=newLNode;//建新的结点if(!p)exit(1);//存储分配失败p-data=e;p-next=S.top;//链接到原来的栈顶S.top=p;//移动栈顶指针++S.length;//栈的长度增1}//Push5．StatusDeQueue(LinkQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，//用e返回其值，并返回OK；否则返回ERRORif(Q.front==Q.rear)returnERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}系别班次学号姓名第8页共14页全真模拟试题（一）一、单项选择题（在每小题的4个备选答案中，选出正确的答案，并将其号码填在题干的括号内。每小题2分，共24分）1．若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（4）存储方式最节省时间。①单链表②双链表③单向循环④顺序表2．串是任意有限个（1）①符号构成的序列②符号构成的集合③字符构成的序列④字符构成的集合3．设矩阵A（aij，l≤i,j≤10）的元素满足：aij≠0(i≥j,l≤i,j≤10)aij