数据结构相关题库及答案.doc

第三章栈和队列一、判断题：1、栈和队列都是限制存取点的线性结构(易)2、栈和队列是两种重要的线性结构。(易)3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易)4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。(易)答案：1-4 二、选择题：1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C_。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为_C_。 A、 i B、 n=i C、 n-i+1 D、 不确定3、栈结构通常采用的两种存储结构是_A_。A、顺序存储结构和链式存储结构B、散列方式和索引方式C、链表存储结构和数组D、线性存储结构和非线性存储结构4、 判定一个顺序栈ST（最多元素为m0）为空的条件是_B_。A、top !=0 B、top= =0 C、top !=m0 D、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、HSnext=s;9B、snext= HSnext; HSnext=s;C、snext= HS; HS=s;D、snext= HS; HS= HSnext8、从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行_ _B_。(不带空的头结点) (中)A、x=HS; HS= HSnext; B、x=HSdata;C、HS= HSnext; x=HSdata; D、x=HSdata; HS= HSnext;9、 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是_C_ 。(易) A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，110、判定一个循环队列QU（最多元素为m）为空的条件是_C_。(中)A、rear - front= =m B、rear-front-1= =mC、front= = rear D、front= = rear+111、 判定一个循环队列QU（最多元素为m, m= =Maxsize-1）为满队列的条件是_A_。(易)A、(rear- front)+ Maxsize)% Maxsize = =mB、rear-front-1= =m C、front= =rear D、front= = rear+112、 循环队列用数组A0，m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_A。(中)A、 (rear-front+m)%m B、 rear-front+1C、 rear-front-1 D、 rear-front13、 栈和队列的共同点是_C_。A、 都是先进后出 B、 都是先进先出C、 只允许在端点处插入和删除元素 D、 没有共同点14、栈操作的原则是( B ) (易)A、 先进先出 B、 后进先出 C、 只能进行插入 D、 只能进行删除15、在顺序栈中，判断栈s为空的条件是( D) (中)A、t.base = NULL B、st.top = st.stacksizeC、st.top-st.base= st.stacksize D、st.top = st.base16、在顺序栈中，判断栈s满的条件是( C ) (易)A、 st.base = NULL B、 st.top = st.stacksizeC、 st.top-st.base= st.stacksize D、 st.top = st.base三、填空题：1、栈和队列都是_结构，对于栈只能在_插入和删除元素；对于队列只能在_插入元素和_删除元素。(易) 线性、栈顶、队尾、队首2、向一个长度为n的顺序表的第i个元素（1in+1）之前插入一个元素时，需向后移动_N-I+1_个元素。(易)3、向一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动_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、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF6、设串的长度为n，则它的子串个数为 C 。(易)A、nB、n(n+1)C、n(n+1)/2 D、n(n+1)/2+17、下列那些为空串（ B ）(易)A、S=“ ” B、S=“” C、S=“” D、S=“”8、S1=“ABCD”，S2=“CD”则S2在S3中的位置是（ C ）(易)A、1 B、2 C、3 D、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=IAMATEACHER,其长度是_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、设数组a76的基地址为1024,每个元素占2个存储单元,若以行序为主序顺序存储,则元素a24的存储地址是_B_。(中)A、1058 B、1056 C、1098 D、答案A,B,C都不对2、 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A47的起始地址为_B_。(中)A、 SA+141 B、 SA+180 C、 SA+222 D、 SA+2253、二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是_C_。(中)A、 80 B、 100 C、240 D、 2704、 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A74的起始地址为_C_。(中)A、 SA+141 B、 SA+144 C、 SA+222 D、 SA+225三、填空题：1、 已知二维数组Amn采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A00)，则Aij的地址是_ LOC (A00)+(n*i+j)*k _。(中)2、 二维数组A1020采用列序为主方式存储，每个元素占一个存储单元并且A00的存储地址是200，