数据结构相关题库及答案第三章栈和队列一、判断题：1、栈和队列都是限制存取点的线性结构(易)2、栈和队列是两种重要的线性结构。

(易)3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易)4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。

(易)答案：1-4 √√××二、选择题：1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C____。

A、 edcba B、 decbaC、 dceabD、 abcde2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为_C___。

A、 iB、 n=iC、 n-i+1D、不确定3、栈结构通常采用的两种存储结构是_A___。

A、顺序存储结构和链式存储结构B、散列方式和索引方式C、链表存储结构和数组D、线性存储结构和非线性存储结构4、判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。

A、top !=0B、top= =0C、top !=m0D、top= =m0-15、判定一个顺序栈ST（最多元素为m0）为栈满的条件是D。

A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-16、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ _C_。

(不带空的头结点) (易)A、HS—＞next=s;9B、s—＞next= HS—＞next; HS—＞next=s;C、s—＞next= HS; HS=s;D、s—＞next= HS; HS= HS—＞next8、从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行__ _B_。

(不带空的头结点) (中)A、x=HS; HS= HS—＞next;B、x=HS—＞data;C、HS= HS—＞next; x=HS—＞data;D、x=HS—＞data; HS= HS—＞next;9、一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是___C_ 。

(易)A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，110、判定一个循环队列QU（最多元素为m）为空的条件是__C__。

(中)A、rear - front= =mB、rear-front-1= =mC、front= = rearD、front= = rear+111、判定一个循环队列QU（最多元素为m, m= =Maxsize-1）为满队列的条件是___A_。

(易)A、((rear- front)+ Maxsize)% Maxsize = =mB、rear-front-1= =mC、front= =rearD、front= = rear+112、循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front 和rear，则当前队列中的元素个数是_A。

(中)A、 (rear-front+m)%mB、 rear-front+1C、 rear-front-1D、 rear-front13、栈和队列的共同点是__C__。

A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素 D、没有共同点14、栈操作的原则是( B ) (易)A、先进先出B、后进先出C、只能进行插入D、只能进行删除15、在顺序栈中，判断栈s为空的条件是( D) (中)A、t.base == NULLB、st.top == st.stacksizeC、st.top-st.base>=st.stacksizeD、st.top == st.base16、在顺序栈中，判断栈s满的条件是( C ) (易)A、 st.base == NULLB、 st.top == st.stacksizeC、 st.top-st.base>=st.stacksizeD、 st.top == st.base三、填空题：1、栈和队列都是____结构，对于栈只能在____插入和删除元素；对于队列只能在____插入元素和____删除元素。

(易) 线性、栈顶、队尾、队首2、向一个长度为n的顺序表的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动__N-I+1__个元素。

(易)3、向一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动__N-1__个元素。

(易)4、向栈中压入元素的操作是先移动栈顶指针，后存入元素5、对栈进行退栈时的操作是____。

(易) 先取出元素，后移动栈顶指针6、在一个循环队列中，队首指针指向队首元素的__前一个位置__。

(易)7、从循环队列中删除一个元素时，其操作是__先移动队首元素，后取出元素__。

(易)8、在具有n个单元的循环队列中，队满时共有__N-1__个元素。

(易)9、一个栈的输入序列是12345，则栈的输出序列43512是__不可能__。

(易)10、一个栈的输入序列是12345，则栈的输出序列12345是_可能___。

(易)11、队列的基本性质是FIFO_______；栈的基本性质是_________。

(易)12、在一个链栈中，若栈顶指针等于NULL则为_______________，在一个链队中，若队首指针与队尾指针的值相同，则表示该队列为____________或该队列______________。

(易) 栈空空队只有一个元素13、向一个栈顶指针为top的链栈中插入一个新结点*P，应执行和p->next=top top=p 操作。

(易)14、栈的顺序存储结构即顺序栈，是利用来依次存放自栈底至栈顶的数据元素；当栈为非空时，栈顶指针top始终指向栈顶元素的下一位置。

15、从数据结构的角度看，栈和队列是受限的线性表两类线性表。

(易)1、空串是由空白字符组成的串(易)2、串的定长顺序结构是用一组地址连续的存储单元存储串值的字符序列，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。

(易)3、串的堆分配存储表示是用一组地址连续的存储单元存储串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。

(易)4、如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。

(易)5、串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。

(易)6、广义表的表头一定是列表。

(易)7、广义表的表尾一定是列表。

(易)8、空串的长度为零。

(易)9、广义表的元素即可以是原子，也可以是子表。

(易)10、广义表中的子表与串中的子串的含义一样。

(易)11、广义表A=()，为空表，其长度为0。

(易)12、由于广义表的元素可以是列表，所以可以将广义表转化为一个树型结构答案：1-5 ×√√×× 6-10 ×√√√× 11-12 √√二、选择题：1、以下叙述中正确的是 A 。

(易)A、串是一种特殊的线性表B、串的长度必须大于零C、串中无素只能是字母D、空串就是空白串2、空串与空格串是相同的，这种说法_B___。

(易)A、正确B、不正确3、串是一中特殊的线性表，其特殊性体现在_B___。

(易)A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符4、设有两个串p和q，求q在p中首次出现的位置的运算称作__B__。

(易)A、连接B、模式匹配C、求子串D、求串长5、设串s1=’ABCDEFG’，s2=’PQRST’，函数con (x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con (subs (s1,2,len (s2)), subs (s1,len (s2),2))的结果串是___D_。

(中)A、BCDEFB、BCDEFGC、BCPQRSTD、BCDEFEF6、设串的长度为n，则它的子串个数为 C 。

(易)A、nB、n(n+1)C、n(n+1)/2D、n(n+1)/2+17、下列那些为空串（ B ）(易)A、S=“”B、S=“”C、S=“φ”D、S=“θ”8、S1=“ABCD”，S2=“CD”则S2在S3中的位置是（C ）(易)A、1B、2C、3D、49、串是一种特殊的线性表，其特殊性体现在( B )。

(易)A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符10、串是( D )。

(易)A、少于一个字母的序列B、任意个字母的序列C、不少于一个字符的序列D、有限个字符的序列11、串的长度是(C )。

(易)A、串中不同字母的个数B、串中不同字符的个数C、串中所含的字符的个数D、串中所含字符的个数，且大于012、若某串的长度小于一个常数，则采用( C )存储方式最为节省空间。

(易)A、链式B、堆结构C、顺序表三、填空题：1、串的两种最基本的存储方式是_顺序存储方式和链接存储方式___。

(易)2、两个串相等的充分必要条件是_两个串的长度相等且对应位置的字符相同___。

(易)3、空串是____，其长度等于____。

(易)零个字符的串、零4、空格串是____，其长度等于____。

(易)由一个或多个空格字符组成的串、其包含的空格个数5、设s=’I︺AM︺A︺TEACHE R’,其长度是_14___。

(易)6、串s=’abcdef’,s1=’cde’，s1在s中的位置为__3___。

(易)7、广义表A=(a,(b,c d))；其表头为___a___，表尾为_ ((b,c,d)) _____。

(中)8、广义表A=(a,A)；其表头为__a____，表尾为_(A)_____。

(易)9、串是每个结点仅由一个字符组成的（线性表）。

(易)1、设数组a[7][6]的基地址为1024,每个元素占2个存储单元,若以行序为主序顺序存储,则元素a[2][4]的存储地址是_B_。

(中)A、1058B、1056C、1098D、答案A,B,C都不对2、二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为__B__。

(中)A、 SA+141B、 SA+180C、 SA+222D、 SA+2253、二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是__C__。

(中)A、 80B、 100C、240D、 2704、二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为___C_。