《数据结构(本)形成性考核作业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串是