《算法与数据结构》习题 第一到三章 习题 选择题 1.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 2.非空的循环单链表head 的尾结点p 满足（A ）。 A．P->next=head B．P->next=NIL C．p=NIL D．p= head 3.在单链表指针为p 的结点之后插入指针为s 的结点，正确的操作是：（ B）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next; p->next=s; 4.在双向链表指针p 的结点前插入一个指针q 的结点操作是（ C）注:双向链表的结点结构为(pre,data,next)。 A. p->pre=q;q->next=p;p->pre->next=q;q->pre=q； B. p->pre=q;p->pre->next=q;q->next=p;q->pre=p->pre; C. q->next=p;q->pre=p->pre;p->pre->next=q;p->pre=q; D. q->pre=p->pre;q->next=q;p->pre=q;p->pre=q; 5.栈的特点是（ ①B ）,队列的特点是（ ② A）,栈和队列都是（ A ③ A ）。若进栈序列为1,2,3,4 则（ ④C ）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（ ⑤ E）是一个出队列序列。 ①, ②: A. 先进先出 B. 后进先出 C. 进优于出 D. 出优于进 ③: A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构 ④, ⑤: A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 E. 1,2,3,4 F. 1,3,2,4 6.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。 A. 不确定 B. n-i+1 C. i D. n-i 7.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j 个输出元素是（ D ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 8.若一个栈以向量 V[1..n]存储，初始栈顶指针top 为n+1，则下面 x 进栈的正确操作是( C )。 A．top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1 C. top:=top-1; V [top]:=x D. V [top]:=x; top:=top-1 9.表达式a*(b+c)-d 的后缀表达式是( B )。 A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 10. 表达式3* 2^(4+2*2-6*3)-5 求值过程中当扫描到6 时，对象栈和算符栈为（ D ），其中^为乘幂 。 A. 3,2,4,1,1；*^(+*- B. 3,2,8；*^- B. ...
