习题31．填空题（部分答案）（1）栈的进出原则是（___________），队列的进出原则是（___________）。答案：后进先出（LIFO）先进先出（FIFO）（2）设32位计算机系统中，空栈S存储int型数据，栈顶指针为1024H。经过操作序列push(1)，push(2)，pop，push(5)，push(7)，pop，push(6)之后，栈顶元素为（___________），栈底元素为（___________），栈的高度为（___________），输出序列是（___________），栈顶指针为（___________）H。答案：6132,71030（3）两栈共享存储空间，其数组大小为100，数组下标从0开始。top1和top2分别为栈1和栈2的栈顶元素下标，则栈1为空的条件为（___________），栈2为空的条件为（___________），栈1或栈2满的条件为（___________）。答案：top1==-1top2==100top1+1==top2（4）一个队列的入队顺序是1234，则队列的输出顺序是（___________）。答案：1234（5）设循环队列数组大小为100，队头指针为front，队尾指针为rear；约定front指向队头元素的前一个位置，该位置永远不存放数据。则入队操作时，修改rear=（___________），出队操作修改front=（___________），队空的判别条件为（___________），队满的判别条件为（___________）。若front=20，rear=60，则队列长度为（___________），若front=60,rear=20，则队列长度为（___________）。答案：(rear+1)%100(front+1)%100rear==front(rear+1)%100=front4060（6）朴素模式匹配算法中，每个串的起始下标均为1，变量i=100，j=10，分别表示主串和模式串当前比较的字符元素下标，若本次比较两字符不同，则i回溯为（___________），j回溯为（___________）。答案：921（7）用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别为（___________）和（___________）。答案：O(1)O(n)（8）一般来说，数组不执行（___________）和（___________）操作，所以通常采用（___________）方法来存储数组。通常有两种存储方式：（___________）和（___________）。答案：删除插入顺序存储行优先存储列优先存储（9）设8行8列的二维数组起始元素为A[0][0]，按行优先存储到起始元素下标为0的一维数组B中，则元素B[23]在原二维数组中为（___________）。若该二维数组为上三角矩阵，按行优先压缩存储上三角元素到起始元素下标为0的一维数组C中，则元素C[23]即为原矩阵中的（___________）元素。答案：A[2][7]A[3][5]（10）设二维数组A为6行8列，按行优先存储，每个元素占6字节，存储器按字节编址。已知A的起始存储地址为1000H，数组A占用的存储空间大小为（___________）字节，数组A的最后一个元素的下标为（___________），该元素的第一个字节地址为（___________）H，元素A[1][4]的第一个字节的地址为（___________）H。（提示：下标从0开始计）答案：288A[5][7]111AH1048H（11）10行100列的二维数组A按行优先存储，其元素分别为A[1][1]~A[10][100]，每个元素占4字节，已知Loc(A[6][7])=10000H，则Loc(A[4][19])=（）。答案：FD10H（12）设C++中存储三维数组Amnp，则第一个元素为a000，若按行优先存储，则aijk前面共有（___________）个元素；若按列优先存储，则aijk前面共有（___________）个元素。答案：inp+jp+ki+mj+mnk（13）常见的稀疏矩阵压缩方法有：（___________）和（___________）。答案：三元组表十字链表2．选择题（1）将一个递归算法改为对应的非递归算法时，通常需要使用（）。A.数组B.栈C.队列D.二叉树（2）四个元素1、2、3、4依次进栈，出栈次序不可能出现（）情况。A.1234B.4132C.1432D.4321（3）设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（）。A.r-fB.r-f+1C.(r-f)modn+1D.(r-f+n)modn说明：这里的数组不是指C++数组，也就说假定数组长度依然为n，而不是n+1。（4）设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为（）。A.连接B.模式匹配C.求子串D.求串长（5）为了解决计算机主机和键盘输入之间速度不匹配问题，通常设置一个键盘缓冲区，该缓冲区应该是一个（）结构。A.栈B.队列C.数组D.线性表（6）STL中的双端队列为（）。A.顺序容器B.容...
