【模拟试题】数据结构与算法分析选编.docx

通信工程学院学生会学习实践部 PAGE  PAGE 22 数据结构与算法分析模拟试题 第1-3章习题 一、选择题 1.若进栈序列为a，b，c，d，进栈过程中可以出栈，则 不可能是一个出栈序列。 A) a,d,c,b B) b,c,d,a C) c,a,d,b D) c,d,b,a 6.设用一维数组A[1,…,n]来存储一个栈，令A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。当从栈中弹出一个元素时，变量T将变化为 。 A) T=T + 1 B) T=T – 1 C) T不变 D) T= n 7. 一个栈的入栈序列为a，b，c，d，e,则栈不可能的出栈序列是 。 A) e d c b a B) d e c b a C) d c e a b D) a b c d e 8.若语句S的执行时间为O(1),那么下列程序段的时间复杂度为 。 For(i = 0; i = n ; i++) For(j = 0; j =n ;j++) s A) O(n) B) O(n*n) C) O(n*log2n) D) O(n*i) 18.设计一个判断表达式中左右括号是否配对的算法，采用 数据结构最佳。 A) 队列 B) 堆栈 C) 二叉树 D) 链表 24.一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 A) 1，4，3，2 B) 4，3，2，1 C) 1，2，3，4 D) 3，2，4，1 29.在一个单链表中，若要删除P结点的后续结点，则应执行 。 A) P-next = P-next-next B) p = P-next; P-next = P-next-next C) delete(P-next) D) p = P-next-next 30.在计算递归函数时，如不使用递归过程，则一般情况下必须借助于 数据结构。 A) 栈 B) 树 C) 双向队列 D) 广义表 41.下列叙述中，正确的是 。 A) 用指针的方式存储一棵有n个结点的二叉树最少需要n+1个指针 B) 不使用递归，也可以实现二叉树的前序、中序和后序遍历 C) 已知树的前序遍历并不能唯一确定一棵树，因为不知道树的根结点是哪一个 D) 任一棵树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间 50.以下有关数据结构的叙述，正确的是 。 A) 线性表的线性存储结构优于链式存储结构 B) 二叉树的第i层上有2i-1个结点，深度为k的二叉树上有2k-1个结点 C) 二维数组是其数据元素为线性表的线性表 D) 栈的操作方式是先进先出 52.在一个单链表中，若要在指针P所指向的结点之后插入结点q，应执行的操作是 。 A) P-next=q B) P-next=q; q-next=P-next-next C) q-next = P-next; P-next:=q D)P-next=q; q-next=P-next 56.若进栈序列为3,5,7,9,进栈过程中可以出栈，则 不可能是一个出栈序列。 A) 7,5,3,9 B) 9,5,7,3 C) 9,7,5,3 D) 7,5,9,3 57.设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈，一个元素出栈后立即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是 。 A) 4 B) 6 C) 3 D) 2 59.有6个元素按6,5,4,3,2,1的顺序进栈，以下序列中，不合法的出栈序列是 。 A) 3,4,6,5,2,1 B) 5,4,3,6,1,2 C) 2,3,1,4,5,6 D) 4,5,3,1,2,6 61.下面关于线性表的叙述中，错误的是 。 A) 线性表采用顺序存储，必须占用一片连续的存储单元 B) 线性表采用顺序存储，便于进行插入和删除操作 C) 线性表采用链式存储，不必占用一片连续的存储单元 D