《数据结构(本)形成性考核作业2》由会员分享，可在线阅读，更多相关《数据结构(本)形成性考核作业2（9页珍藏版）》请在金锄头文库上搜索。
1、1数据结构（本）课程作业 2（本部分作业覆盖教材第 3-5 章的内容）一、单项选择题1若让元素 1，2，3 依次进栈，则出栈顺序不可能为（ ） 。A3，2，1 B2，1，3 C3，1，2 D1，3，22一个队列的入队序列是 1，2，3，4。则队列的输出序列是（ ） 。A4，3，2，1 B1，2，3，4 C1，4，3，2 D3，2，4，13向顺序栈中压入新元素时，应当（ ） 。A先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针 C先后次序无关紧要 D同时进行4在一个栈顶指针为 top 的链栈中，将一个 p 指针所指的结点入栈，应执行（ ） 。Atop-next=p; Bp-next=to
2、p-next; top-next=p;Cp-next=top; top=p; Dp-next=top-next; top=top-next;5在一个栈顶指针为 top 的链栈中删除一个结点时，用 x 保存被删结点的值，则执行（ ） 。Ax=top;top=top-next; Bx=top-data;Ctop=top-next; x=top-data; Dx=top-data; top=top-next;6一般情况下，将递归算法转换成等价的非递归算法应该设置（ ） 。A栈 B队列C堆栈或队列 D数组7表达式 a*(b+c)-d 的后缀表达式是（ ） 。Aabcd*+- Babc+*d- Cabc
3、*+d- D-+*abcd8判断一个顺序队列 sq（最多元素为 m0）为空的条件是（ ） 。Asq-rear-sq-front= m 0 Bsq-rear-sq-front-1= = m 0 Csq-front=sq-rear Dsq-front=sq-rear+19判断一个循环队列 Q（最多元素为 m0）为空的条件是（ ） 。AQ-front=Q-rear BQ-front!=Q-rear 2CQ-front=(Q-rear+1)% m0 DQ-front!= (Q-rear+1)%m 0 10判断一个循环队列 Q（最多元素为 m0）为空的条件是（ ） 。AQ-front=Q-rear BQ
4、-front!=Q-rear CQ-front=(Q-rear+1)% m0 DQ-front!= (Q-rear+1)% m 0 11判断栈 S 满（元素个数最多 n 个）的条件是（ ） 。As-top=0 Bs-top!=0 Cs-top=n-1 Ds-top!=n-1 12一个队列的入队顺序是 a,b,c,d，则离队的顺序是（ ） 。Aa,d,cb Ba,b,c,d Cd,c,b,a Dc,b,d,a13如果以链表作为栈的存储结构，则退栈操作时（ ） 。A必须判断栈是否满 B判断栈元素类型 C必须判断栈是否空 D对栈不作任何判断14在解决计算机主机与打印机之间速度不匹配问题时通常设置一个
5、打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（ ）结构。A堆栈 B队列 C数组 D先性表15一个递归算法必须包括（ ） 。A递归部分 B终止条件和递归部分 C迭代部分 D终止条件和迭代部分16从一个栈顶指针为 top 的链栈中删除一个结点时，用变量 x 保存被删结点的值，则执行（ ） 。Ax=top-data; top=top-next; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;17在一个链队中，假设 f 和 r 分别为队头和队尾指针，则删除一个结点的
6、运算为（ ） 。Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;18在一个链队中，假设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的运算为（ ） 。Af-next=s; f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-next=f;f=s;19.以下陈述中正确的是（ ）。A串是一种特殊的线性表 B串的长度必须大于零C串中元素只能是字母 D空串就是空白串320设有两个串 p 和 q，其中 q 是 p 的子串，q 在 p 中首次出现的位置的算法称为（ ） 。A求子串 B连接 C匹配 D求串长 21串是（ ）。A不少于一个
7、字母的序列 B任意个字母的序列C不少于一个字符的序列 D有限个字符的序列 22串的长度是指（ ） 。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数23. 若串 S=“English”，其子串的个数是（ ） 。A9 B16 C 36 D2824下面关于串的叙述中，不正确的是（ ） 。A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D串即可以采用顺序存储，也可以采用链式存储 25串与普通的线性表相比较，它的特殊性体现在（ ） 。A顺序的存储结构 B链接的存储结构 C数据元素是一个字符 D数据元素可以任意26空串与空格串
8、（ ） 。A相同 B不相同 C可能相同 D无法确定27两个字符串相等的条件是（ ） 。A两串的长度相等 B两串包含的字符相同C两串的长度相等，并且两串包含的字符相同D两串的长度相等，并且对应位置上的字符相同28在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（ ）存储比较合适（ ） 。A链式 B 顺序 C堆结构 D无法确定 29.一维数组 A 采用顺序存储结构，每个元素占用 6 个字节，第 6 个元素的存储地址为100，则该数组的首地址是（ ）。A64 B28C70 D90430稀疏矩阵采用压缩存储的目的主要是（ ） 。A表达变得简单 B对矩阵元素的存取变得简单 C去掉矩阵中的多余元
9、素 D减少不必要的存储空间的开销31一个非空广义表的表头（ ）。A不可能是原子 B只能是子表C只能是原子 D可以是子表或原子 32常对数组进行的两种基本操作是（ ） 。A建立与删除 B索引与、和修改C查找和修改 D查找与索引33. 设二维数组 A56按行优先顺序存储在内存中，已知 A00 起始地址为 1000，每个数组元素占用 5 个存储单元，则元素 A44的地址为（ ） 。A1140 B1145 C 1120 D112534设有一个 20 阶的对称矩阵 A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组 B 中（数组下标从 1 开始） ，则矩阵中元素 a9,2在一维数组 B 中
10、的下标是（ ） 。A41 B32 C18 D3835一个非空广义表的表头（ ） 。A不可能是子表 B只能是子表 C只能是原子 D可以是子表或原子二、填空题1栈是限定在表的一端进行插入和删除操作的线性表，又称为 。2队列的特性是 。3往栈中插入元素的操作方式是：先 ，后 。4删除栈中元素的操作方式是：先 ，后 。5循环队列队头指针在队尾指针 位置，队列是“满”状态6在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 ，当删除一个元素队列时，头指针 。7循环队列的引入，目的是为了克服 。8向顺序栈插入新元素分为三步：第一步进行 判断，判断条件是 ；第二步是修改 ；第三步是把新元素赋给 。同样
11、从顺序栈删除元素分为三步：第一步进行 判断，判断条件是 。第二步是把 ；第三步 。9假设以 S 和 X 分别表示入栈和出栈操作，则对输入序列 a,b,c,d,e 一系列栈操作SSXSXSSXXX 之后，得到的输出序列为 。10一个递归算法必须包括 和 。511判断一个循环队列 LU（最多元素为 m0）为空的条件是 。12在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的 ，而对于后者，进入栈的元素为 ，中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是 。 16向一个栈顶指针为 h 的链栈中插入一个 s 所指结点时，可执行_和 h=s;操作。( 结点的指针域为 next)17从一个栈顶指针为 h 的链栈中删除一个结点时，用 x 保存被删结点的值，可执行x=h-data;和_ 。( 结点的指针域为 next)18在一个链队中，设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的操作为_和 r=s; (结点的指针域为 next)19在一个链队中，设 f 和 r 分别为队头和队尾指针，则删除一个结点的操作为_。 (结点的指针域为 next)20串是
