10．判断栈S满（元素个数最多n个）的条件是（C ）。 A．s->top==0 B．s->top!=0
C．s->top==n-1 D．s->top!=n-1
11．一个队列的入队顺序是a,b,c,d，则离队的顺序是（ B ）。 A．a,d,cb B．a,b,c,d C．d,c,b,a D．c,b,d,a
12．如果以链表作为栈的存储结构，则退栈操作时（ C ）。 A．必须判断栈是否满 B．判断栈元素类型
C．必须判断栈是否空 D．对栈不作任何判断
13．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（ B ）结构。
A．堆栈 B．队列 C．数组 D．先性表
14．一个递归算法必须包括（ B ）。
A．递归部分
15．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（ A ）。 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分别为队头和队尾指针，则删除一个结点的运算为（C ）。 A．r=f->next; B．r=r->next; C．f=f->next; D．f=r->next;
17．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（B ）。 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 ）。
A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串
19．设有两个串p和q，其中q是p的子串，q在p中首次出现的位置的算法称为（ C ）。 A．求子串 B．连接 C．匹配 D．求串长
20．串是（ D ）。
A．不少于一个字母的序列 B．任意个字母的序列 C．不少于一个字符的序列 D．有限个字符的序列
21．串的长度是指（ B ）。
A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数
22. 若串S==“English”，其子串的个数是（ D ）。 A．9 B．16 C． 36 D．28
B．终止条件和递归部分
C．迭代部分 D．终止条件和迭代部分
23．串与普通的线性表相比较，它的特殊性体现在（ C ）。 A．顺序的存储结构 B．链接的存储结构 C．数据元素是一个字符 D．数据元素可以任意
24．空串与空格串（ B ）。
A．相同 B．不相同 C．可能相同 D．无法确定
25．两个字符串相等的条件是（ D）。 A．两串的长度相等
B．两串包含的字符相同
C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同
26．在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（A ）存储比较合适（ ）。 A．链式 B． 顺序 C．堆结构 D．无法确定
27.一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（ C ）。 A．64 B．28 C．70 D．90
28．稀疏矩阵采用压缩存储的目的主要是（D ）。
A．表达变得简单 B．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素 D．减少不必要的存储空间的开销
29．一个非空广义表的表头（ C ）。
A．不可能是原子 B．只能是子表
C．只能是原子 D．可以是子表或原子
30．常对数组进行的两种基本操作是（ C ）。
A．建立与删除 B．索引与、和修改 C．查找和修改 D．查找与索引
31. 设二维数组A[5][6]按行优先顺序存储在内存中，已知A[0][0] 起始地址为1000，每个数组元素占用5个存储单元，则元素A[4][4]的地址为（ A ）。
A．1140 B．1145 C． 1120 D．1125
32．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（ D ）。
A．41 B．32 C．18 D．38
二、填空题
1．栈是限定在表的一端进行插入和删除操作的线性表，又称为 后进先出 。 2．循环队列队头指针在队尾指针 下一个 位置，队列是“满”状态
3．在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 增1 ，当删除一个元素队列时，头指针 增1 。
4．循环队列的引入，目的是为了克服 假上溢 。
5．向顺序栈插入新元素分为三步：第一步进行 栈是否满 判断，判断条件是 s->top=MAXSIZE-1 ；第二步是修改
栈顶指针 ；第三步是把新元素赋给 栈顶对应的数组元素 。同样从顺序栈删除元素分为三步：第一步进行 栈是否空 判断，判断条件是 s->top=-1 。第二步是把 栈顶元素 ；第三步 修改栈顶指针 。
6．假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e一系列栈操作SSXSXSSXXX之后，得到的输出序列为 bceda 。
7．一个递归算法必须包括 终止条件 和 递归部分 。
8．判断一个循环队列LU（最多元素为m0）为空的条件是 LU->front==LU->rear 。
9．在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的 运算符 ，而对于后者，进入栈的元素为 操作数
，中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是 ab+c/fde/-- 。
10．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行___ s->next=h _____和h=s;操作。(结点的指针域为next) 11．从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h->data;和__ h=h->next ______。(结点的指针域为next)
12．在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为___ r->next=s _____和r=s; (结点的指针域为next) 13．在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为__ f=f->next ______。 (结点的指针域为next) 14．串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是 字符 。
15．串的两种最基本的存储方式是 顺序存储方式 和 链式存储方式 。 16．空串的长度是 0 ；空格串的长度是 空格字符的个数 。 17．需要压缩存储的矩阵可分为 特殊 矩阵和 稀疏 矩阵两种。
18．设广义表L=（（），（）），则表头是 （） ，表尾是 （（）） ，L的长度是 2 。 19．广义表A（（a,b,c）,(d,e,f)）的表尾为 （（d,e,f）） 。
20．两个串相等的充分必要条件是_______串长度相等且对应位置的字符相等 ___。
21．设有n阶对称矩阵A，用数组s进行压缩存储，当i?j时，A的数组元素aij相应于数组s的数组元素的下标为__ i(i-1)/2+j _____。（数组元素的下标从1开始）
22．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的___行下标____、___列下标___和___非零元素值____三项信息。
三、问答题
1．简述栈和一般线性表的区别。
答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。
2．简述队列和一般线性表的区别。
队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。
3．链栈中为何不设头结点？
答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以一般不设置头结点。
4．利用一个栈，则：
（1）如果输入序列由A，B，C组成，试给出全部可能的输出序列和不可能的输出序列。 （2）如果输入序列由A，B，C，D组成，试给出全部可能的输出序列和不可能的输出序列。 答：
（1）栈的操作特点是后进先出，因此输出序列有： A入，A出，B入，B出，C入C出，输出序列为ABC。 A入，A出，B入，C入，C出，B出，输出序列为ACB。 A入，B入，B出，A出，C入，C出，输出序列为BAC。 A入，B入，B出，C入，C出，A出，输出序列为BCA。 A入，B入，C入，C出，B出，A出，输出序列为CBA。
由A，B，C组成的数据项，除上述五个不同的组合外，还有一个C，A，B组合。但不可能先把C出栈，再把A出栈，（A不在栈顶位置），最后把B出栈，所以序列CAB不可能由输入序列A，B，C 通过栈得到。
（2）按照上述方法，可能的输出序列有：
ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。 不可能的输出序列有：
DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD
5．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S和X操作串是什么？ 答：应是SXSSXSXX。各操作结果如下： S 1入栈
X 1出栈 输出序列：1 S 2入栈 S 3入栈
X 3出栈 输出序列：13 S 4入栈
X 4出栈 输出序列：134 X 2出栈 输出序列：1342
6．有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先的次序有哪几个？
答：从题中可知，要使C第一个且D第二个出栈，应是A入栈，B入栈，C入栈，C出栈，D入栈。之后可以有以下几种情况： （1）B出栈，A出栈，E入栈，E出栈，输出序列为：CDBAE。 （2）B出栈，E入栈，E出栈，A 出栈，输出序列为CDBEA。 （3）E入栈，E出栈，B出栈，A出栈，输出序列为CDEBA 所以可能的次序有：CDBAE，CDBEA，CDEBA
7．写出以下运算式的后缀算术运算式 ⑴ 3x2+x-1/x+5 ⑵ (A+B)*C-D/(E+F)+G
答；对应的后缀算术运算式 ⑴ 3x2^*x+1x/-5+ ⑵ AB+C*DEF+/-G+
8． 简述广义表和线性表的区别和联系。
答：广义表是线性表的的推广，它也是n(n>0)个元素a1 ,a2…ai… an的有限序列，其中ai或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai都是原子时，广义表退化成线性表。
四、程序填空题
1．在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整。 int write(LinkQueue *q) {QueueNode *p;
if (q->front==q->rear) /*队空*/ {printf(“underflow”); exit(0);}
while (q->front->next != NULL) {p=q->front->next;
(1) q->front->next=p->next;
printf(“M”,p->data);
(2) free(p); } （3） q->rear=q->front ; /*队空时，头尾指针指向头结点*/ } 五、综合题
1．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5和e6依次通过S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是多少？
答：出队序列是e2,e4,e3,e6,e5,e1的过程： ⑴ e1入栈（栈底到栈顶元素是e1） ⑵ e2入栈（栈底到栈顶元素是e1,e2） ⑶ e2出栈（栈底到栈顶元素是e1） ⑷ e3入栈（栈底到栈顶元素是e1,e3） ⑸ e4入栈（栈底到栈顶元素是e1,e3,e4） ⑹ e4出栈（栈底到栈顶元素是e1,e3） ⑺ e3出栈（栈底到栈顶元素是e1） ⑻ e5入栈（栈底到栈顶元素是e1,e5） ⑼ e6入栈（栈底到栈顶元素是e1,e5,e6） ⑽ e6出栈（栈底到栈顶元素是e1,e5） ⑾ e5出栈（栈底到栈顶元素是e1） ⑿ e1出栈（栈底到栈顶元素是空）
栈中最多时有3个元素，所以栈S的容量至少是3。
2．假设用循环单链表实现循环队列，该队列只使用一个尾指针rear，其相应的存储结构和基本算法如下；
（1）初始化队列initqueue(Q):建立一个新的空队列Q。 （2）入队列enqueue(Q,x):将元素x插入到队列Q中。 （3）出队列delqueue(Q):从队列Q中退出一个元素。 （4）取队首元素gethead(Q):返回当前队首元素。 （5）判断队列是否为空：emptyqueue(Q)。 （6）显示队列中元素：dispqueue(Q)。 算法设计如下：
/*只有一个指针rear的链式队的基本操作*/ #include
struct node /*定义链队列结点*/ {
elemtype data; struct node *next; };
typedef struct queue /*定义链队列数据类型*/ {
struct node *rear; } LinkQueue;
void initqueue(LinkQueue *Q)/*初始化队列*/ {
Q=(struct queue *)malloc(sizeof(struct queue)); Q->rear=NULL; }
void enqueue(LinkQueue *Q,elemtype x) /*入队算法*/ {
struct node *s,*p;
s=(struct node *)malloc(sizeof(struct node));
相关推荐：
loading