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

《数据结构考试试题(带答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、××科技大学成都学院二零零八至二零零九学年第一学期数据结构课堂测试（60分钟）闭卷考试时间：题号一二三总分评卷教师分数一．填空题（每空2分，共40分）；1.数据结构算法中，通常用时间复杂度和__空间复杂度___两种方法衡量其效率。2.下面程序段的时间复杂度为___O(n2)______。(n>1)for(i=1;i<=n;i++)for(j=1;j<=i;j++)x=x+1;3.静态链表中指针表示的是______下一结点的地址______。4.线型表、栈和队列都是____线型_______结构，可以在线型表的____任意___位置插入和删除元

2、素；对于栈只能在____栈顶_____插入和删除元素；对于队列只能在____队尾___插入元素和_____队头_____删除元素。5.在具有n个单元的循环队列中，队满时共有_____n-1____个元素。6.在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动__n-i+1__个元素。7.在n个结点的单链表中要删除已知结点*p，需找到它的_____前驱________。8.带有一个头结点的单链表head为空的条件是_________head->next==NULL__________。9.在栈顶指针为hs的链栈中

3、，判断栈空的条件是_________hs==NULL__________。10.在hq的链队列中，判定只有一个结点的条件是__hq.front->next==hq.rear________。11.非空的循环单链表head的尾结点（由p指向），满足条件____p->next==head。12.两个串相等的充分必要条件是______串长相等且对应字符相等_______。13.空串是_______长度为0的串______，其长度等于___0________。14.空格串是______由空格字符组成的串______，其长度等于_____空格的个数__

4、_______。二．单项选择题（每题2分，共30分）；（说明：请将答案填入下表中）题号12345678910答案AABBDBCBBC题号1112131415答案AACDD1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表2.设a1、a2、a3为3个结点，则如下的链式存储结构称为：A表元编号结点表元间关系1a132a213a32A．循环链表B．单链表C．双向循环链表D．双向链表1.有六个元素6，5，4，3，2，1的顺序进栈，问下

5、列哪一个不是合法的出栈序列？（B）A.543612B.346521C.453126D.2341562.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（B）。A.top[2]-top[1]

6、=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]3.数组Ｑ［ｎ］用来表示一个循环队列，front为当前队列头元素的前一位置，rear为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式

7、为(D)A.rear－frontB.（n＋front－rear）%nC.n＋rear－frontD.（n＋rear－front）%n4.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4,e6,e5，e3,e1则栈S的容量至少应该是(B)。A．6B.4C.3D.25.在数据结构中，从逻辑上可以把数据结构分成（C）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构6.判定一个顺序栈ST（最多元素为N）为空的条

8、件是（B）。A．ST．top！=ST.baseB．ST．top==ST.baseC．ST．top！=ND．ST．top==N7.一个队列的入列序列是1，2，3，4，则队列的输出序列是B。A．4,3,2,1B．1,2,3,4C．1,4,3,2D．3,2,4,18.判定一个循环队列QU(最多元素为N)为空的条件是C。A．QU.front==（QU.rear+1）%NB．QU.front！=（QU.rear+1）%NC．QU.front==QU.rearD．QU.front！=QU.rear9.判定一个循环队列QU（最多元素为m0）为满队列的条件是

9、A。A．QU.front==（QU.rear+1）%NB．QU.front！=（QU.rear+1）%NC．QU.front==QU.rearD．QU.front！