线性表和栈和队列
线性表 栈 队列
一.选择题
1.下述哪一条是顺序存储结构的优点?( )【北方交通大学 2001 一、4(2分)】
A .存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示
2.下面关于线性表的叙述中,错误的是哪一个?( )【北方交通大学 2001 一、14(2分)】
A .线性表采用顺序存储,必须占用一片连续的存储单元。
B .线性表采用顺序存储,便于进行插入和删除操作。
C .线性表采用链接存储,不必占用一片连续的存储单元。
D .线性表采用链接存储,便于插入和删除操作。
3.线性表是具有n 个( )的有限序列(n>0)。 【清华大学 1998 一、4(2分)】
A .表元素 B.字符 C.数据元素 D.数据项 E.信息项
4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( )存储方式最节省时间。【哈尔滨工业大学 2001 二、1(2分)】
A .顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表
5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( )存储方式最节省运算时间。【南开大学 2000 一、3】
A .单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表
6. 链表不具有的特点是( ) 【福州大学 1998 一、8 (2分) 】
A .插入、删除不需要移动元素 B.可随机访问任一元素
C .不必事先估计存储空间 D.所需空间与线性长度成正比
7. 若长度为n 的线性表采用顺序存储结构,在其第i 个位置插入一个新元素的算法的时间复杂度为( )(1
A. O(0) B. O(1) C. O(n) D. O(n)
8. 对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为( )。
A .O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
9.在一个以 h 为头的单循环链中,p 指针指向链尾的条件是()【南京理工大学1998 一、15(2分)】
A. p->next=h B. p->next=NIL C. p->next->next=h D. p->data=-1
10.在双向链表中,在p 指针 所指的结点后插入一个指针q 所指向的新结点,其修改指针的操作是( )。
A .p->next=q; q->prior=p; p->next->prior=q; q->next=q
B.p->next=q; p->next-prior=q; q->prior=p; q->next=p-next
C.q->prior=p; q->next=p->next; p_next->prior=q; p->next=q
D .q->next=p->next;q->prior=p;p->next=q;p->prior=q
11.线性表中,哪些元素只有一个直接前驱和一个直接后继( )。
A. 首元素 B.尾元素 C.中间元素 D.所有元素
12.一个向量第一个元素的存储地址是100, 每个元素的长度为2, 则第5个元素的地址是( )
A.110 B.108 C. 100 D. 120
13. 对于栈操作数据的原则是( )。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
14. 一个栈的输入序列为123…n ,若输出序列的第一个元素是n ,输出第i (1
A. 不确定 B. n-i+1 C. i D. n-i
15. 一个栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的是( )。
A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2
16. 输入序列为ABC ,可以变为CBA 时,经过的栈操作为( )
A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop
C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop
17. 递归过程或函数调用时,处理参数及返回地址,要用一种称为( )的数据结构。
A .队列 B.多维数组 C.栈 D. 线性表 2
18. 栈和队列的共同点是( )。
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点
19. 若一个栈以向量V[1..n]存储,初始栈顶指针top 为-1,则下面x 进栈的正确操作是( )。
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
20. 若用一个大小为6的数组来实现循环队列,且当前rear 和front 的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,rear 和front 的值分别为多少?( )【浙江大学1999 四、1(4分) 】
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
一.填空题
1.当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用_______存储结构。
2.线性表L=(a1,a2, …,an )用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是________。
3.对于一个具有n 个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x 的结点后插入一个新结点的时间复杂度为________。
4. 已知指针p 指向单链表L 中的某结点,则删除其后继结点的语句是:________
5. 对于双向链表, 在两个结点之间插入一个新结点需修改的指针共 ______个,单链表为_______个。
6. 在单链表p 结点之后插入s 结点的操作是:_______。
7. 栈的特点是 ; 队列的特点是_______。
8. 循环队列的引入,目的是为了克服_______。【厦门大学 2001 一、1 (14/8分)】
9.设循环队列用数组A[1..M]表示,队首、队尾指针分别是FRONT 和TAIL ,判定队满的条件为_______。