【数据布局】数据布局试题集Ver2 第三章 栈和队列，第四章 串，第五章 数组 ...

---

关注作者了解更多
我的其他CSDN专栏
求职面试
大学英语
过程控制体系
工程测试技能
虚拟仪器技能
可编程控制器
工业现场总线
数字图像处置惩罚
智能控制
传感器技能
嵌入式体系
复变函数与积分变换
单片机原理
线性代数
大学物理
热工与工程流体力学
数字信号处置惩罚
光电融合集成电路技能
电路原理
模拟电子技能
高等数学
概率论与数理统计
数据布局
C语言
模式识别原理
自动控制原理
数字电子技能
关注作者了解更多
资料泉源于网络，如有侵权请联系编者
目次
第三章 栈和队列
第四章  串
第五章 数组和广义表

---

数据布局试题集Ver2





第三章 栈和队列


一、选择题

1、一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（   ）。
A. a,b,c,d,e              B. d,e,c,b,a    
C. d,c,e,a,b           D. e,d,c,b,a
2、判断一个循环队列Q（最多n个元素）为满的条件是（   ）。
A. Q->rear==Q->front   B. Q->rear==Q->front+1 
C. Q->front==(Q->rear+1)%n D. Q->front==(Q->rear-1)%n
3、计划一个鉴别表达式中括号是否配对的算法，采用（   ）数据布局最佳。
A. 次序表    B. 链表     C. 队列     D. 栈
4、带头结点的单链表head为空的判断条件是（   ）。
A. head==NULLB. head->next==NULL
C. head->next!=NULL  D. head!=NULL
5、一个栈的输入序列为：1,2,3,4，则栈的不可能输出的序列是（   ）。
A. 1243          B. 2134    C. 1432        D. 4312E. 3214
6、若用一个巨细为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再参加两个元素后，rear和front的值分别为（   ）。
A. 1和5   B. 2和4C. 4和2 D. 5和1
7、队列的插入操纵是在（   ）。
A. 队尾  B. 队头C. 队列任意位置D. 队头元素后
8、循环队列的队头和队尾指针分别为front和rear，则判断循环队列为空的条件是（   ）。
A. front==rear     B. front==0    
C. rear==0    D. front=rear+1
9、一个次序栈S，其栈顶指针为top，则将元素e入栈的操纵是（   ）。
A. *S->top=e;S->top++;     B. S->top++;*S->top=e; 
C. *S->top=e    D. S->top=e;
10、表达式a*(b+c)-d的后缀表达式是（   ）。
A. abcd+-B. abc+*d-C. abc*+d-  D. -+*abcd
11、将递归算法转换成对应的非递归算法时，通常需要使用（   ）来保存中间结果。
A. 队列    B. 栈C. 链表    D. 树
12、栈的插入和删除操纵在（   ）。
    A. 栈底       B. 栈顶   C.  任意位置      D. 指定位置
13、五节车厢以编号1，2，3，4，5次序进入铁路调度站（栈），可以得到（   ）的编组。
A. 3，4，5，1，2B. 2，4，1，3，5
C. 3，5，4，2，1D. 1，3，5，2，4
14、判断一个次序栈S（栈空间巨细为n）为空的条件是（   ）。
A. S->top==0   B. S->top!=0
C. S->top==nD. S->top!=n
15、在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操纵为（   ）。
A. front=front->next B. s->next=rear;rear=s
C. rear->next=s;rear=s;D. s->next=front;front=s;
16、一个队列的入队序列是1，2，3，4，则队列的出队序列是（   ）。
A. 1，2，3，4B. 4，3，2，1
C. 1，4，3，2D. 3，4，1，2
17、依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操纵，此时的队头元素是（   ）。
A. a    B. b     C. c     D. d
18、正常环境下，删除非空的次序存储布局的堆栈的栈顶元素，栈顶指针top的变革是（   ）。
A. top稳定    B. top=0   C. top=top+1   D. top=top-1
19、判断一个循环队列Q（空间巨细为M）为空的条件是（   ）。
A. Q->front==Q->rear       B. Q->rear-Q->front-1==M   
C. Q->front+1=Q->rear      D. Q->rear+1=Q->front

20、计划一个鉴别表达式中左右括号是否配对出现的算法，采用（   ）数据布局最佳。

A. 线性表的次序存储布局B. 队列C. 栈   D. 线性表的链式存储布局
21、当用巨细为N的数组存储次序循环队列时，该队列的最大长度为（   ）。
A. NB. N+1C. N-1D. N-2
22、队列的删除操纵是在（   ）。
A. 队首B. 队尾C. 队前D. 队后
23、若让元素1，2，3依次进栈，则出栈次序不可能是（   ）。
A. 3，2，1B. 2，1，3C. 3，1，2  D. 1，3，2
24、循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（   ）。
A. (rear-front+m)%mB. rear-front+1
C. rear-front-1D. rear-front
25、在办理计算机主机和打印机之间速度不匹配标题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（   ）布局。
A. 堆栈   B. 队列C. 数组 D. 线性表
26、栈和队列都是（   ）。
A. 链式存储的线性布局    B. 链式存储的非线性布局     
C. 限制存取点的线性布局   D. 限制存取点的非线性布局
27、在一个链队列中，假定front和rear分别为队头指针和队尾指针，删除一个结点的操纵是（   ）。
A. front=front->next   B. rear= rear->next
C. rear->next=frontD. front->next=rear
28、队和栈的主要区别是（   ）。
A. 逻辑布局不同       B. 存储布局不同
C. 所包罗的运算个数不同    D. 限定插入和删除的位置不同

二、填空题
1、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是            。
答案：3
2、一个循环队列Q的存储空间巨细为M,其队头和队尾指针分别为front和rear，则循环队列中元素的个数为：           。
答案：(rear-front+M)%M
3、在具有n个元素的循环队列中，队满时具有          个元素。
答案：n-1
4、设循环队列的容量为70，现经过一系列的入队和出队操纵后，front为20，rear为11，则队列中元素的个数为           。
答案：61
5、已知循环队列的存储空间巨细为20，且当前队列的头指针和尾指针的值分别为8和3，且该队列的当前的长度为_______。
三、判断题
1、栈和队列都是受限的线性布局。P
2、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机存取布局。O
3、以链表作为栈的存储布局，出栈操纵必须鉴别栈空的环境。P


四、程序分析填空题
1、已知栈的基本操纵函数：
int InitStack(SqStack *S); //构造空栈
int StackEmpty(SqStack *S);//判断栈空
int Push(SqStack *S,ElemType e);//入栈
int Pop(SqStack *S,ElemType *e);//出栈
函数conversion实现十进制数转换为八进制数，请将函数补充完备。
void conversion(){
InitStack(S);
scanf(“%d”,&N);
while(N){
      （1）           ;
N=N/8;
}
while(      （2）       ){
Pop(S,&e);
printf(“%d”,e);
}
}//conversion
答案：（1）Push(S,N%8)    （2）!StackEmpty(S)
2、写出算法的功能。
int  function(SqQueue *Q,ElemType *e){
if(Q->front==Q->rear)
return ERROR;
*e=Q->base[Q->front];
Q->front=(Q->front+1)%MAXSIZE;
return OK;
}
3、阅读算法f2,并答复下列标题：
（1）设队列Q=（1，3，5，2，4，6）。写出执行算法f2后的队列Q;
（2）简述算法f2的功能。
void  f2(Queue *Q){
   DataType   e;
   if (!QueueEmpty(Q)){
     e=DeQueue(Q);
     f2(Q);
     EnQueue(Q,e);
   }
}
答案：（1）6,4,2,5,3,1（2）将队列倒置


五、综合题
1、假设以带头结点的循环链表表现队列，而且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列算法（用函数实现）。

答案：void EnQueue(Lnode *rear, ElemType e)
  {  Lnode *new;
     New=(Lnode *)malloc(sizeof(Lnode));
If(!new) return ERROR;
new->data=e; new->next=rear->next;
rear->next=new; rear =new;
  }
2、已知Q是一个非空队列，S是一个空栈。编写算法，仅用队列和栈的ADT函数和少量工作变量，将队列Q的全部元素逆置。
栈的ADT函数有：
void makeEmpty(SqStack s);置空栈
void push(SqStack s,ElemType e);元素e入栈
ElemType pop(SqStack s);出栈，返回栈顶元素
int isEmpty(SqStack s);判断栈空
队列的ADT函数有：
void enQueue(Queue q,ElemType e);元素e入队
ElemType deQueue(Queue q);出队，返回队头元素
int isEmpty(Queue q);判断队空
答案：void QueueInvent(Queue q)
  {  ElemType x;
     makeEmpty(SqStack s);
while(!isEmpty(Queue q))
{x=deQueue(Queue q);
push(SqStack s, ElemTypex);}
while(!isEmpty(SqStack s))
{x=pop(SqStack s);
enQueue(Queue q, ElemType x);}
  }

3、对于一个栈，给出输入项A,B,C,D，如果输入项序列为A,B,C,D，试给出全部可能的输出序列。

答案：出栈的可能序列：
  ABCD  ABDC  ACDB  ACBD  ADCB  BACD  BADC  BCAD  BCDA
  CBDA  CBAD  CDBA  DCBA


第四章  串

一、选择题
1、设有两个串S1和S2，求串S2在S1中初次出现位置的运算称作（ C  ）。
A. 连接   B. 求子串C. 模式匹配D. 判断子串
2、已知串S=’aaab’，则next数组值为（  A ）。
A. 0123    B. 1123     C. 1231     D. 1211
3、串与平凡的线性表相比较，它的特别性体现在（  C ）。
A. 次序的存储布局B. 链式存储布局C. 数据元素是一个字符  D. 数据元素任意
4、设串长为n，模式串长为m，则KMP算法所需的附加空间为（ A  ）。
    A. O(m)              B. O(n)   C. O(m*n)           D. O(nlog2m)
5、空串和空格串（  B ）。
    A. 雷同              B. 不雷同   C. 可能雷同          D. 无法确定
6、与线性表相比，串的插入和删除操纵的特点是（   ）。
A. 通常以串团体作为操纵对象B. 需要更多的辅助空间
C. 算法的时间复杂度较高D. 涉及移动的元素更多
7、设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操纵，则对于S=’Beijing&Nanjing’，SUBSTR(S,4,5)=（ B  ）。
A. ‘ijing’  B. ‘jing&’C. ‘ingNa’   D. ‘ing&N’
二、判断题
（   ）1、造成简朴模式匹配算法BF算法执行服从低的原因是有回溯存在。
（√ ）2、KMP算法的最大特点是指示主串的指针不需要回溯。
（√ ）3、完全二叉树某结点有右子树，则肯定有左子树。
三、填空题
1、求子串在主串中初次出现的位置的运算称为      模式匹配      。
2、设s=’I︺AM︺A︺TEACHER’,其长度是____。
3、两个串相等的充分须要条件是两个串的长度相等且       对应位置字符雷同         。
四、程序填空题
1、函数kmp实现串的模式匹配，请在空格处将算法补充完备。
int kmp(sqstring *s,sqstring *t,int start,int next[]){
int i=start-1,j=0;
    while(i<s->len&&j<t->len)
        if(j==-1||s->data==t->data[j]){
            i++;j++;
        }
        else j=          ;
    if(j>=t->len)
        return(                 );
    else
        return(-1);
}
2、函数实现串的模式匹配算法，请在空格处将算法补充完备。
int index_bf(sqstring*s,sqstring *t,int start){
    int i=start-1,j=0;
    while(i<s->len&&j<t->len)
        if(s->data==t->data[j]){
            i++;j++;
        }else{
            i=     i-j+1     ;j=0;
        }
    if(j>=t->len)
        return     i-t->len+1      ;
    else
        return -1;
}}/*listDelete*/
3、写出下面算法的功能。
int function(SqString *s1,SqString *s2){
int i;
for(i=0;i<s1->length&&i<s1->length;i++)
if(s->data!=s2->data)
return s1->data-s2->data;
return s1->length-s2->length;
}

答案：.串比较算法

4、写出算法的功能。
int fun(sqstring *s,sqstring *t,int start){
    int i=start-1,j=0;
    while(i<s->len&&j<t->len)
        if(s->data==t->data[j]){
            i++;j++;
        }else{
            i=i-j+1;j=0;
        }
    if(j>=t->len)
        return i-t->len+1;
    else
        return -1;
}
答案：串的模式匹配算法


第五章 数组和广义表

一、选择题
1、设广义表L=((a，b，c))，则L的长度和深度分别为（ C  ）。
A. 1和1  B. 1和3C. 1和2D. 2和3
2、广义表((a),a)的表尾是（ B  ）。
A. a B. (a)C. ()D. ((a))
3、稀疏矩阵的常见压缩存储方法有（ C  ）两种。
A. 二维数组和三维数组   B. 三元组和散列表C. 三元组和十字链表D. 散列表和十字链表
4、一个非空广义表的表头（ D  ）。
A. 不可能是子表    B. 只能是子表C. 只能是原子    D. 可以是子表或原子
5、数组A[0..5,0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5][5]的地址是（   ）。
A. 1175   B. 1180C. 1205 D. 1210
6、广义表G=(a,b(c,d,(e,f)),g)的长度是（  A ）。
A. 3   B. 4C. 7D. 8
7、采用稀疏矩阵的三元组表情势进行压缩存储，若要完成对三元组表进行转置，只要将行和列对换，这种说法（  B ）。
A. 正确   B. 错误C. 无法确定 D. 以上均不对
8、广义表(a,b,c)的表尾是（ B  ）。
A. b,c    B. (b,c)     C. c     D. (c)
9、常对数组进行两种基本操纵是（   ）。
A. 建立和删除  B. 索引和修改C. 查找和修改   D. 查找与索引
10、对一些特别矩阵采用压缩存储的目的主要是为了（ D  ）。
A. 表达变得简朴        B. 对矩阵元素的存取变得简朴
C. 去掉矩阵中的多余元素    D. 减少不须要的存储空间的开销
11、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（   ）。
A. 13B. 33C. 18  D. 40
12、设矩阵A是一个对称矩阵，为了节流存储，将其下三角部门按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部门中任一元素ai,j(i>=j)，在一维数组B的下标位置k的值是（ B  ）。
A. i(i-1)/2+j-1    B. i(i-1)/2+j     C. i(i+1)/2+j-1    D. i(i+1)/2+j
13、广义表A=((a),a)的表头是（ B  ）。
A. a   B. (a)C. bD. ((a))
14、稀疏矩阵一般的压缩存储方法有两种，即（ C  ）。
A. 二维数组和三维数组B. 三元组和散列C. 三元组和十字链表D. 散列和十字链表
15、假设以三元组表表现稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（ B  ）。

16、以下有关广义表的表述中，正确的是（   ）。
A. 由0个或多个原子或子表构成的有限序列      B. 至少有一个元素是子表   
C. 不能递归定义      D. 不能为空表
17、对广义表L=((a,b),((c,d),(e,f)))执行head(tail(head(tail(L))))操纵的结果是（   ）。
A. 的     B. e   C. (e)D. （e,f）
二、判断题
（ ）1、广义表中原子个数即为广义表的长度。
（ ）2、一个稀疏矩阵采用三元组表现，若把三元组中有关行下标与列下标的值互换，并把mu和nu的值进行互换，则完成了矩阵转置。
（√ ）3、稀疏矩阵压缩存储后，必会失去随机存取功能。
（ ）4、广义表的长度是指广义表中括号嵌套的层数。
（√ ）5、广义表是一种多条理的数据布局，其元素可以是单原子也可以是子表。
三、填空题
1、已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，而且第一个元素的存储地址是LOC(A[0][0])，则A[j]的地址是___ Loc(A[0][0])+(i*N+j)*k ____。
2、广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是：     (x,y,z)       。
3、二维数组，可以按照                         两种不同的存储方式。
4、稀疏矩阵的压缩存储方式有：          和          。
四、综合题
1、现有一个稀疏矩阵，请给出它的三元组表。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。