发布时间 : 星期三 文章练习题1-6章(含答案)更新完毕开始阅读
4. 将链表Ｌａ进行逆臵等操作。
5. 已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结
点移到链表的最前面。要求：不得额外申请新的链结点。
6. (6) 有一个单链表L（至少有1个结点），其头结点指针为head，编写一个过程将L逆臵，即最后一个结点变
成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。
7. 在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，
使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），分析算法的时间复杂度。
第三章
1. 对于栈操作数据的原则是（b ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
2. 在作进栈运算时,应先判别栈是否( ①b ),在作退栈运算时应先判别栈是否( ② a )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ b )。
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④d )分别设在这片内存空间的两端,这样,当( ⑤ c )时，才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点.
B. 其中一个栈的栈顶到达栈空间的中心点.
C. 两个栈的栈顶在栈空间的某一位臵相遇.
D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.
3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ b ）。
A. 不确定 B. n-i+1 C. i D. n-i
4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ d ）。i-j+1 A. i-j-1 B. i-j C. j-i+1 D. 不确定的
5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是( d )。 A. i B. n-i C. n-i+1 D. 不确定
6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ c ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6
8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ b ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2
13. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ b ）【中山大学 1999 一、8(1分)】
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
14. 若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( b )。
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
15. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ b ）。
A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 16. 栈在（ d ）中应用。【中山大学 1998 二、3（2分）】
A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ 17. 一个递归算法必须包括（ b ）。
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分 19. 表达式a*(b+c)-d的后缀表达式是( b )。
A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd
21. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ d ）数据结构最佳。
A．线性表的顺序存储结构 B. 队列C. 线性表的链式存储结构 D. 栈 22. 用链接方式存储的队列，在进行删除运算时（ d ）。【
A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 23. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( d )。
A．仅修改队头指针 B. 仅修改队尾指针
C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改
24. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ c ）的数据结构。
A．队列 B．多维数组 C．栈 D. 线性表
25. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ a ）。 A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m
26. 循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( a )。 A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front
27. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ）。
A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)
28. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( b )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
31. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ b ）。
A. (rear+1) MOD n=front B. rear=front
C．rear+1=front D. (rear-l) MOD n=front 32. 栈和队列的共同点是（ c ）。
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点 34. 栈和队都是（ c ）
A．顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构
35. 设栈S和队列Q的初始状态为空，元素a1，a2，a3，a4,a5和a6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是a2，a4，a3,a6,a5,a1则栈S的容量至少应该是( c )。
A． 6 B. 4 C. 3 D. 2 36. 用单链表表示的链式队列的队头在链表的（ a ）位臵。
A．链头 B．链尾 C．链中
第四章 串
1．下面关于串的的叙述中，哪一个是不正确的？（ b ）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 ．串的长度是指（ b ）
A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 3．空格串是指__(1)_由空格组成的串_，其长度等于___(2)空格的个数__。 4．组成串的数据元素只能是__字符______。
5．一个字符串中_．任意个连续的字符组成的子序列_______称为该串的子串 。
第 5 章 数组和广义表
1、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( b )。
A. BA+141 B. BA+180 C. BA+222 D. BA+225
2. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，