形考作业二
（本部分作业覆盖教材第3-5章的内容）
一、单项选择题
1．若让元素1，2，3依次进栈，则出栈顺序不可能为（ ）。
A．3，2，1 B．2，1，3
C．3，1，2 D．1，3，2
2．一个队列的入队序列是1，2，3，4。则队列的输出序列是（ ）。
A．4，3，2，1 B．1，2，3，4
C．1，4，3，2 D．3，2，4，1
3．向顺序栈中压入新元素时，应当（ ）。
A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针
C．先后次序无关紧要 D．同时进行
4．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（ ）。
A．top->next=p;
B．p->next=top->next; top->next=p;
C．p->next=top; top=p;
D．p->next=top->next; top=top->next;
5．在一个栈顶指针为top的链栈中删除一个结点时，用 x保存被删结点的值，则执行（ ）。
A．x=top;top=top->next;
B．x=top->data;
C．top=top->next; x=top->data;
D．x=top->data; top=top->next;
6．一般情况下，将递归算法转换成等价的非递归算法应该设置（ ）。
A．栈 B．队列
C．堆栈或队列 D．数组
7．表达式a*(b+c)-d的后缀表达式是（ ）。
A．abcd*+- B．abc+*d- C．abc*++d- D．-+*abcd
8．判断一个顺序队列sq（最多元素为m）为空的条件是（ ）。
A．sq->rear-sq->front== m B．sq->rear-sq->front-1= = m
C．sq->front==sq->rear D．sq->front==sq->rear+1
9．判断一个循环队列Q（最多元素为m）为满的条件是（ ）。
A．Q->front==Q->rear B．Q->front!=Q->rear
C．Q->front==(Q->rear+1)% m D．Q->front!= (Q->rear+1)%m
10．判断栈S满（元素个数最多n个）的条件是（ ）。
A．s->top==0 B．s->top!=0
C．s->top==n-1 D．s->top!=n-1
11．一个队列的入队顺序是a,b,c,dprintf怎么加两个条件，则离队的顺序是（ ）。
A．a,d,cb B．a,b,c,d C．d,c,b,a D．c,b,d,a
12．如果以链表作为栈的存储结构，则退栈操作时（ ）。
A．必须判断栈是否满 B．判断栈元素类型
C．必须判断栈是否空 D．对栈不作任何判断
13．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（ ）结构。
A．堆栈 B．队列 C．数组 D．线性表
14．一个递归算法必须包括（ ）。
A．递归部分 B．终止条件和递归部分
C．迭代部分 D．终止条件和迭代部分
15．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（ ）。
A．x=top->data; top=top->next; B．x=top->data;
C．top=top->next; x=top->data; D．top=top->next; x=data;
16．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（ ）。
A．r=f->next; B．r=r->next; C．f=f->next; D．f=r->next;
17．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（ ）。
A．f->next=s; f=s; B．r->next=s;r=s;
C．s->next=r;r=s; D．s->next=f;f=s;
18.以下陈述中正确的是（ ）。
A．串是一种特殊的线性表 B．串的长度必须大于零
C．串中元素只能是字母 D．空串就是空白串
19．设有两个串p和q，其中q是p的子串，q在p中首次出现的位置的算法称为（ ）。
A．求子串 B．连接
C．匹配 D．求串长
20．串是（ ）。
A．不少于一个字母的序列 B．任意个字母的序列
C．不少于一个字符的序列 D．有限个字符的序列
21．串的长度是指（ ）。
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
22. 若串S==“English”，其子串的个数是（ ）。
A．9 B．16 C． 36 D．28
23．串与普通的线性表相比较，它的特殊性体现在（ ）。
A．顺序的存储结构 B．链接的存储结构
C．数据元素是一个字符 D．数据元素可以任意
24．空串与空格串（ ）。
A．相同 B．不相同 C．可能相同 D．无法确定
25．两个字符串相等的条件是（ ）。
A．两串的长度相等
B．两串包含的字符相同
C．两串的长度相等，并且两串包含的字符相同
D．两串的长度相等，并且对应位置上的字符相同
26．在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（ ）存储比较合适（ ）。
A．链式 B． 顺序 C．堆结构 D．无法确定
27.一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（ ）。
A．64 B．28
C．70 D．90
28．稀疏矩阵采用压缩存储的目的主要是（ ）。
A．表达变得简单 B．对矩阵元素的存取变得简单
C．去掉矩阵中的多余元素 D．减少不必要的存储空间的开销
29．一个非空广义表的表头（ ）。
A．不可能是原子 B．只能是子表
C．只能是原子 D．可以是子表或原子
30．常对数组进行的两种基本操作是（ ）。
A．建立与删除 B．索引与、和修改
C．查和修改 D．查与索引
31. 设二维数组A[5][6]按行优先顺序存储在内存中，已知A[0][0] 起始地址为1000，每个数组元素占用5个存储单元，则元素A[4][4]的地址为（ ）。
A．1140 B．1145 C． 1120 D．1125
32．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（ ）。
A．41 B．32 C．18 D．38
二、填空题
1．栈是限定在表的一端进行插入和删除操作的线性表，又称为 。
2．循环队列队头指针在队尾指针 位置，队列是“满”状态
3．在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 ，当删除一个元素队列时，头指针 。
4．循环队列的引入，目的是为了克服 。
5．向顺序栈插入新元素分为三步：第一步进行 判断，判断条件是 ；第二步
是修改 ；第三步是把新元素赋给 。同样从顺序栈删除元素分为三步：第一步进行 判断，判断条件是 。第二步是把 ；第三步 。
6．假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e一系列栈操作SSXSXSSXXX之后，得到的输出序列为 。
7．一个递归算法必须包括 和 。
8．判断一个循环队列LU（最多元素为m）为空的条件是 。
9．在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的 ，而对于后者，进入栈的元素为 ，中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是 。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论