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

《数据结构相关题库及答案-.pdf》由会员分享，可在线阅读，更多相关《数据结构相关题库及答案-.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章栈和队列一、判断题：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、不确定

2、3、栈结构通常采用的两种存储结构是_A_。A、顺序存储结构和链式存储结构B、散列方式和索引方式C、链表存储结构和数组D、线性存储结构和非线性存储结构4、判定一个顺序栈ST（最多元素为 m0）为空的条件是 _B_。A、top!=0 B、top=0 C、top!=m0 D、top=m0-1 5、判定一个顺序栈ST（最多元素为 m0）为栈满的条件是 D。A、top！=0 B、top=0 C、top！=m0 D、top=m0-1 6、队列操作的原则是(A)A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除7、向一个栈顶指针为 HS的链栈中插入一个s 所指结点时，则执行 _ _C_。(不带空

3、的头结点)(易)A、HS next=s;9 B、snext=HSnext;HS next=s;C、snext=HS;HS=s;D、snext=HS;HS=HS next 8、从一个栈顶指针为HS的链栈中删除一个结点时，用 x 保存被删结点的值，则执行_ _B_。(不带空的头结点)(中)A、x=HS;HS=HSnext;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，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 1

4、0、判定一个循环队列QU（最多元素为 m）为空的条件是 _C_。(中)A、rear-front=m B、rear-front-1=m C、front=rear D、front=rear+1 11、判定一个循环队列QU（最多元素为 m,m=Maxsize-1）为满队列的条件是_A_。(易)A、(rear-front)+Maxsize)%Maxsize=m B、rear-front-1=m C、front=rear D、front=rear+1 12、循环队列用数组 A0，m-1存放其元素值，已知其头尾指针分别是front和 rear，则当前队列中的元素个数是_A。(中)A、(rear-front

5、+m)%m B、rear-front+1 C、rear-front-1 D、rear-front 13、栈和队列的共同点是 _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.stacksizeD、st.top=st.base 16、在顺序栈中，判断栈s 满的条件是(C)(易)A、st.base=NUL

6、L B、st.top=st.stacksizeC、st.top-st.base=st.stacksizeD、st.top=st.base 三、填空题：1、栈和队列都是 _结构，对于栈只能在 _插入和删除元素；对于队列只能在 _插入元素和 _删除元素。(易)线性、栈顶、队尾、队首2、向一个长度为 n 的顺序表的第 i 个元素（1i n+1）之前插入一个元素时，需向后移动 _N-I+1_个元素。(易)3、向一个长度为 n 的顺序表中删除第i 个元素（1i n）时，需向前移动_N-1_个元素。(易)4、向栈中压入元素的操作是先移动栈顶指针，后存入元素5、对栈进行退栈时的操作是_。(易)先取出元素，后

7、移动栈顶指针6、在一个循环队列中，队首指针指向队首元素的_前一个位置 _。(易)7、从循环队列中删除一个元素时，其操作是_先移动队首元素，后取出元素_。(易)8、在具有 n 个单元的循环队列中，队满时共有_N-1_个元素。(易)9、一个栈的输入序列是12345，则栈的输出序列 43512是_不可能 _。(易)10、一个栈的输入序列是12345，则栈的输出序列12345是_可能_。(易)11、队列的基本性质是FIFO_；栈的基本性质是 _。(易)12、在一个链栈中，若栈顶指针等于NULL则为_，在一个链队中，若队首指针与队尾指针的值相同，则表示该队列为 _或该队列_。(易)栈空空队只有一个元素1

8、3、向一个栈顶指针为top 的链栈中插入一个新结点*P，应执行和p-next=top top=p 操作。(易)14、栈的顺序存储结构即顺序栈，是利用来依次存放自栈底至栈顶的数据元素；当栈为非空时，栈顶指针 top 始终指向栈顶元素的下一位置。15、从数据结构的角度看，栈和队列是受限的线性表两类线性表。(易)1、空串是由空白字符组成的串(易)2、串的定长顺序结构是用一组地址连续的存储单元存储串值的字符序列，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。(易)3、串的堆分配存储表示是用一组地址连续的存储单元存储串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。(易)

9、4、如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。(易)5、串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。(易)6、广义表的表头一定是列表。(易)7、广义表的表尾一定是列表。(易)8、空串的长度为零。(易)9、广义表的元素即可以是原子，也可以是子表。(易)10、广义表中的子表与串中的子串的含义一样。(易)11、广义表 A=()，为空表，其长度为0。(易)12、由于广义表的元素可以是列表，所以可以将广义表转化为一个树型结构答案：1-5 6-10 11-12 二、选择题：1、以下叙述中正确的是 A 。(易)A、串是一种特殊的线性表B、

10、串的长度必须大于零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

11、的长度，则 con(subs(s1,2,len(s2),subs(s1,len(s2),2)的结果串是 _D_。(中)A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 6、设串的长度为 n，则它的子串个数为 C 。(易)A、n B、n(n+1)C、n(n+1)/2 D、n(n+1)/2+1 7、下列那些为空串（B ）(易)A、S=“”B、S=“”C、S=“”D、S=“”8、S1=“ABCD”，S2=“CD”则 S2在 S3中的位置是（C）(易)A、1 B、2 C、3 D、4 9、串是一种特殊的线性表，其特殊性体现在(B )。(易)A、可以顺序存储 B、数据元素是一个字符

12、C、可以链接存储 D、数据元素可以是多个字符10、串是(D )。(易)A、少于一个字母的序列 B、任意个字母的序列C、不少于一个字符的序列 D、有限个字符的序列11、串的长度是(C )。(易)A、串中不同字母的个数 B、串中不同字符的个数C、串中所含的字符的个数 D、串中所含字符的个数，且大于0 12、若某串的长度小于一个常数，则采用(C)存储方式最为节省空间。(易)A、链式 B、堆结构 C、顺序表三、填空题：1、串的两种最基本的存储方式是_顺序存储方式和链接存储方式_。(易)2、两个串相等的充分必要条件是_两个串的长度相等且对应位置的字符相同_。(易)3、空串是 _，其长度等于 _。(易)零

13、个字符的串、零4、空格串是 _，其长度等于 _。(易)由一个或多个空格字符组成的串、其包含的空格个数5、设 s=I AM ATEACHER,其长度是 _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、1

14、058 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+225 3、二维数组 A 中，每个元素的长度为3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9，从首地址 SA开始连续存放在存储器内，存放该数组至少需要的字节数是 _C_。(中)A、80 B、100 C、240 D、270 4、二维数组 A中，每个

15、元素 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，则 A612的地址是 _326_。(中)3、二维数组 A10,205,10 采用行序为主方式存储，每个元素占4 个存储单元，并且 A105的存储地址是 1000，则 A189的地址是 1208_。(中)4、现有一个 n 阶的对称矩阵 ann，现将其压缩存储在一个一维数组sm中，则 m=_，若以行序为主序进行存储，则元素aij(i=j)在 s 中的下标 k=_。(中)n(n+1)/2 i(i-1)/2+j-15、在一个 m*n的矩阵中，若 a00是第一个元素，则 aij是第_ i*n+j_个元素。(中)