数据结构考试考试(带答案).doc

数据结构考试考试(带答案)————————————————————————————————作者:————————————————————————————————日期: ××科技大学成都学院二零零八至二零零九学年第一学期数据结构课堂测试(60分钟)闭卷考试时间:(每空2分,共40分);数据结构算法中,通常用时间复杂度和__空间复杂度___两种方法衡量其效率。下面程序段的时间复杂度为___O(n2)______。(n>1)for(i=1;i<=n;i++)for(j=1;j<=i;j++) x=x+1;静态链表中指针表示的是______下一结点的地址______。线型表、栈和队列都是____线型_______结构,可以在线型表的____任意___位置插入和删除元素;对于栈只能在____栈顶_____插入和删除元素;对于队列只能在____队尾___插入元素和_____队头_____删除元素。在具有n个单元的循环队列中,队满时共有_____n-1____个元素。在一个长度为n的顺序表中第i个元素(1<=i<=n)之前插入一个元素时,需向后移动__n-i+1__个元素。在n个结点的单链表中要删除已知结点*p,需找到它的_____前驱________。带有一个头结点的单链表head为空的条件是_________head->next==NULL__________。在栈顶指针为hs的链栈中,判断栈空的条件是_________hs==NULL__________。在hq的链队列中,->next==。非空的循环单链表head的尾结点(由p指向),满足条件____p->next==head。两个串相等的充分必要条件是______串长相等且对应字符相等_______。空串是_______长度为0的串______,其长度等于___0________。空格串是______由空格字符组成的串______,其长度等于_____空格的个数_________。(每题2分,共30分);(说明:请将答案填入下表中)题号**********答案AABBDBCBBC题号1112131415答案AACDD若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用(A)存储方式最节省时间。、a2、a3为3个结点,则如下的链式存储结构称为:,5,4,3,2,1的顺序进栈,问下列哪一个不是合法的出栈序列?(B),现两栈共享空间V[1..m],top[i]代表第i个栈(i=1,2)栈顶,栈1的底在v[1],栈2的底在V[m],则栈满的条件是(B)。[2]-top[1]|=[1]+1=top[2][1]+top[2]=[1]=top[2]数组Q[n]用来表示一个循环队列,front为当前队列头元素的前一位置,rear为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素的公式为(D)-frontB.(n+front-rear)%+rear-frontD.(n+rear-front)%n设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e6,e5,e3,e1则栈S的容量至少应该是(B)。,从逻辑上可以把数据结构分成(C)。(最多元素为N)为空的条件是(B)。!= == !=N ==N一个队列的入列序列是1,2,3,4,则队列的输出序列是B。 ,3,2,1 ,2,3,,4,3,2 ,2,4,1判定一个循环队列QU(最多元素为N)为空的条件是C。 ==(+1)%N !=(+1)%N == !=(最多元素为m0)为满队列的条件是A。 ==(+1)%N !=(QU