当前位置:首页 > 开发 > 编程语言 > 数据结构 > 正文

数据结构随记_2

发表于: 2015-07-05   作者:lx.asymmetric   来源:转载   浏览:
摘要: 第三章 栈与队列 一.简答题 1. 在一个循环队列中,队首指针指向队首元素的  前一个    位置。  2.在具有n个单元的循环队列中,队满时共有  n-1  个元素。  3. 向栈中压入元素的操作是先  移动栈顶指针&n

第三章 栈与队列

一.简答题

1. 在一个循环队列中,队首指针指向队首元素的  前一个    位置。 

2.在具有n个单元的循环队列中,队满时共有  n-1  个元素。 

3. 向栈中压入元素的操作是先  移动栈顶指针  ,后  存入元素     

4.从循环队列中删除一个元素时,其操作是   移动队首指针  ,后   取出元素  

 

二、判断正误(判断下列概念的正确性,并作出简要的说明。) 

   ×  1. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。   

错,线性表是逻辑结构概念,可以顺序存储或链式存储,与元素数据类型无关。 

 

 ×  2.栈和链表是两种不同的数据结构。   

错,栈是逻辑结构的概念,是特殊殊线性表,而链表是存储结构概念,二者不是同类项。 

 

     3.栈和队列的存储方式既可是顺序方式,也可是链接方式。   

 

     4. 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端

 

三、单项选择题  

   B   1. 判定一个栈ST(最多元素为m0)为空的条件是 

   A.ST->top !=0    B.ST->top=0       C.ST->top !=m0       D.ST->top=m0 

 

   A   2.判定一个队列QU(最多元素为m0)为满队列的条件是 

   A.QU->rear  QU->front = = m0    

B.QU->rear  QU->front 1= = m0      

C.QU->front = = QU->rear           

D.QU->front = = QU->rear+1 

解:队满条件是元素个数为m0。由于约定满队时队首指针与队尾指针相差1,所以不必再减1了,应当选A。当然,更正确的答案应该取模,即:QU->front = = (QU->rear+1)% m0   

 

   D   3.数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素的公式为 

(A)rf;     (B)(nfr% n;  (C)nrf;         (D)(nrf% n

 

4.  从供选择的答案中,选出应填入下面叙述      内的最确切的解答,把相应编号写在答卷的对应栏内。 

栈是一种线性表,它的特点是  A   。设用一维数组A[1,,n]来表示一个栈,A[n]为栈底,用整型变量T指示当前栈顶位置,A[T]为栈顶元素。往栈中推入(PUSH)一个新元素时,变量T的值  B   ;从栈中弹出(POP)一个元素时,变量T的值  C   。设栈空时,有输入序列abc,经过PUSHPOPPUSHPUSHPOP操作后,从栈中弹出的元素的序列是  D   ,变量T的值是  E    供选择的答案: 

A  先进先出    ②后进先出  ③进优于出       ④出优于进  随机进出 

BC  1    ②减1       ③不变            ④清0   2      ⑥减

D:① a,b    b,c  c,a  b,a      c,b      a,c

 E:① n+1     n+2    n   n-1     n-2

 答案:ABCDE=2,  2,  1,  6,  4 

注意,向地址的高端生长,称为向上生成堆栈;向地址低端生长叫向下生成堆栈,本题中底部为n,向地址的低端递减生成,称为向下生成堆栈。

 

四、简答题

1.说明线性表、栈与队的异同点。 

答:

相同点:都是线性结构,都是逻辑结构的概念;

都可以用顺序存储或链表存储;

栈和队列是两种特殊的线性表,即受限的线性表,只是对插入、删除运算加以限制。 

不同点:①运算规则不同,线性表为随机存取,而栈是只允许在一端进行插入、删除运算,因而是后进先出表LIFO;队列是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表FIFO 

 用途不同,堆栈用于子程调用和保护现场,队列用于多道作业处理、指令寄存及其他运算等等。 

 

2.设有编号为1234的四辆列车,顺序进入一个栈式结构的车站,具体写出这四辆列车开出车站的所有可能的顺序。 

答:至少有14种。 

 全进之后再出情况,只有1种:4321 

 3个之后再出的情况,有3种:3,4,2,1  3,2,4,1  3,2,1,4 

 2个之后再出的情况,有5种:2,4,3,1   2,3,4,1   2,1, 3,4  2,1,4,3  2,1,3,4

 1个之后再出的情况,有5种:1,4,3,2  1,3,2,4  1,3,4,2  1,2,3,4  1,2,4,3 

 

3.假设正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘abcde 和‘ababab’则不是回文。假设一字符序列已存入计算机,请分析用线性表、堆栈和队列等方式正确输出其回文的可能性? 

答:

线性表是随机存储,可以实现,靠循环变量(j--)从表尾开始打印输出; 

堆栈是后进先出,也可以实现,靠正序入栈、逆序出栈即可; 

队列是先进先出,不易实现。 

哪种方式最好,要具体情况具体分析。若正文在机内已是顺序存储,则直接用线性表从后往前读取即可,或将堆栈栈顶开到数组末尾,然后直接用POP动作实现。(但堆栈是先减后压还是„„) 

若正文是单链表形式存储,则等同于队列,需开辅助空间,可以从链首开始入栈,全部压入后再依次输出。 

  

4.顺序队的“假溢出”是怎样产生的?如何知道循环队列是空还是满? 

答:一般的一维数组队列的尾指针已经到了数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫“假溢出”。 采用循环队列是解决假溢出的途径。 

另外,解决队满队空的办法有三: 

 设置一个布尔变量以区别队满还是队空。

 浪费一个元素的空间,用于区别队满还是队空。

 使用一个计数器记录队列中元素个数(即队列长度)。 

我们常采用法②即队头指针、队尾指针中有一个指向实元素,而另一个指向空闲元素。 

判断循环队列队空标志是: f=rear      队满标志是:f=(r+1)%N 

 

5.设循环队列的容量为40(序号从039),现经过一系列的入队和出队运算后,有 

 front=11rear=19;     front=19rear=11;问在这两种情况下,循环队列中各有元素多少个?

 答:用队列长度计算公式:  (Nrf)% N 

 L=401911% 40=8                L=401119% 40=32

 

五、阅读理解

1.写出下列程序段的输出结果(栈的元素类型SElem Typechar)。

 void main( ){ 

Stack S; 

Char x,y; 

InitStack(S); 

x=c;y=k

Push(S,x); Push(S,a);  Push(S,y); 

Pop(S,x); Push(S,t); 

Push(S,x); Pop(S,x); Push(S,s);

while(!StackEmpty(S)){

 Pop(S,y);

printf(y); 

}; 

Printf(x); 

答:输出为stack  

 

2.写出下列程序段的输出结果(队列中的元素类型QElem Typechar)。 

void main( ){ 

Queue Q;  Init Queue (Q); 

Char x=e; y=c

EnQueue (Q,h); EnQueue (Q,r);  EnQueue (Q, y); 

DeQueue (Q,x); EnQueue (Q,x);  

DeQueue (Q,x); EnQueue (Q,a);  

while(!QueueEmpty(Q)){

 DeQueue (Q,y);printf(y); 

}; 

Printf(x); 

答:输出为“char”。  

 

3.简述以下算法的功能(栈和队列的元素类型均为int)。 

void algo3(Queue &Q){

Stack S; int d; 

InitStack(S); 

while(!QueueEmpty(Q)){  

DeQueue (Q,d);  Push(S,d); 

}; 

while(!StackEmpty(S)){  

Pop(S,d); EnQueue (Q,d);  

答:该算法的功能是:利用堆栈做辅助,将队列中的数据元素进行逆置。    

 

六、算法设计

1.假设一个数组squ[m]存放循环队列的元素。若要使这m个分量都得到利用,则需另一个标志tag,以tag01来区分尾指针和头指针值相同时队列的状态是“空”还是“满”。试编写相应的入队和出队的算法。 

解:这就是解决队满队空的三种办法之① 设置一个布尔变量以区别队满还是队空(其他两种见简答题); 思路:一开始队空,设tag=0,若从rear一端加到与front指针相同时,表示入队已满,则令tag=1;若从front一端加到与rear指针相同时,则令tag=0,表示出队已空。   

 

2.试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。

 答:编程如下: 

int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0 { 

Stack S;Queue Q;

InitStack(S);InitQueue(Q);   

while((c=getchar())!='@')   { 

      Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构   

     while(!StackEmpty(S))   { 

    Pop(S,a);DeQueue(Q,b));     

if(a!=b) return ERROR;  

     return OK; 

}//Palindrome_Test

 

 

 

第四章 串与数组

 

一、填空题

1.子串的定位运算称为串的模式匹配 被匹配的主串称为 目标串   子串称为 模式   

 

2.设目标T=abccdcdccbaa”,模式P=cdcc”,则第  6    次匹配成功。  

 

3..n为主串长,m为子串长,则串的古典(朴素)匹配算法最坏的情况下需要比较字符的总次数为  (n-m+1)*m    

 

4.假设有二维数组A6×8,每个元素用相邻的6个字节存储,存储器按字节编址。已知A的起始存储位置(基地址)为1000,则数组A的体积(存储量)为    288    ;末尾元素A57的第一个字节地址为   1282     ;若按行存储时,元素A14的第一个字节地址为  (8+4)×6+1000=1072    ;若按列存储时,元素A47的第一个字节地址为  (6×74)×61000)=1276      

(注:数组是从00列还是从11列计算起呢?由末单元为A57可知,是从00列开始!)  

 

5.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素    行下标      列下标        元素值        

 

6.求下列广义表操作的结果: 

1 GetHead((a,b),(c,d))===   (a, b)      ;      //头元素不必加括号 

2 GetHeadGetTail((a,b),(c,d))】】===  (c,d)     ; 

3 GetHeadGetTailGetHead((a,b),(c,d))】】】===   b   ; 

4 GetTailGetHeadGetTail((a,b),(c,d))】】】===   d      ;

 

 

二、单选题

 B  1. 串是一种特殊的线性表,其特殊性体现在: 

  A.可以顺序存储       B.数据元素是一个字符       C.可以链式存储       D.数据元素可以是多个字符 

 

 B  2.设有两个串pq,求qp中首次出现的位置的运算称作: 

   A.连接      B.模式匹配    C.求子串       D.求串长 

 

 D  3. 设串s1=ABCDEFG’,s2=PQRST’,函数con(x,y)返回xy串的连接串,subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串,len(s)返回串s的长度,则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是: 

   A.BCDEF       B.BCDEFG     C.BCPQRST        D.BCDEFEF 

解:con(x,y)返回xy串的连接串,即 con(x,y)=‘ABCDEFGPQRST’; subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串,则 

subs(s1, 2, len(s2))subs(s1, 2, 5)= BCDEF;  subs(s1, len(s2), 2)subs(s1, 5, 2)= EF

所以con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))con( BCDEF EF)之连接,即BCDEFEF  

 

 A  4. 假设有6070列的二维数组a[160, 170]以列序为主序顺序存储,其基地址为10000,每个元素占2个存储单元,那么第32行第58列的元素a[32,58]的存储地址为      。(无第0行第0列元素) 

   A.16902    B.16904      C.14454       D.答案A, B, C均不对 

答:(57列×60行+31行)×2字节+10000=16902  

 

三、简答题

1. 已知二维数组Am,m采用按行优先顺序存放,每个元素占K个存储单元,并且第一个元素的存储地址为Loc(a11),请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢? 

解:公式教材已给出,此处虽是方阵,但行列公式仍不相同; 

按行存储的元素地址公式是: Loc(aij)= Loc(a11) +[ (i-1)*m+(j-1) ] * K 

按列存储的元素地址公式是: Loc(aij)= Loc(a11) +[ (j-1)*m+(i-1) ] * K  

 

2.递归算法比非递归算法花费更多的时间,对吗?为什么? 

答:不一定。时间复杂度与样本个数n有关,是指最深层的执行语句耗费时间,而递归算法与非递归算法在最深层的语句执行上是没有区别的,循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同,递归用栈隐含循环次数,非递归用循环变量来显示循环次数而已。  

 

四、计算题

1. s=I AM A STUDENT, t=GOOD, q=WORKERReplace(s,STUDENT,q)  Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))

 解:① Replace(s,STUDENT,q)=’I AM A WORKER 

 因为  SubString(s,6,2)=‘’;SubString(s,7,8)=‘ STUDENT

 Concat(t,SubString(s,7,8))=’GOOD STUDENT 

所以Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))=‘A GOOD STUDENT   

 

五、算法设计题

1.  编写一个实现串的置换操作Replace(&S, T, V)的算法。 

解:C程序参考,请转换为C++ 

//将串S中所有子串T替换为  V,并返回置换次数

int Replace(Stringtype &S,Stringtype T,Stringtype V) {  

   for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围  

     if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串      

       { //分别把T的前面和后面部分保存为headtail        

       StrAssign(head,SubString(S,1,i-1));  

       StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));        

       StrAssign(S,Concat(head,V));  

          StrAssign(S,Concat(S,tail)); //head,V,tail连接为新串        

       i+=Strlen(V); //当前指针跳到插入串以后       

       n++;        

       n++;      

    }//if    

    return n;  

}//Replace 

分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下会引起不希望的后果,虽然在大多数情况下没有影响.请思考:S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?     

 

2. 试设计一个算法,将数组An 中的元素A[0]A[n-1]循环右移k位,并要求只用一

个元素大小的附加存储,元素移动或交换次数为O(n) 

解: 

分析:要把A的元素循环右移k,A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[ 0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,nk的最大公约数为p,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p"循环链"上面.举例如下:  n=15,k=6,p=3.  

第一条链:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0].  /已“顺便”移动了A[6]A[12] 第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].  第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].  恰好使所有元素都右移一次.  

 程序如下(C程序参考,请转换为C++): 

void RSh(int A[n],int k)//把数组A的元素循环右移k,只用一个辅助存储空间  {  

  for(i=1;i<=k;i++)  

if(n%i==0&&k%i==0) p=i;//nk的最大公约数p    

for(i=0;i<p;i++)    {  

     j=i;l=(i+k)%n;

temp=A[i];      

while(l!=i)      {  

       A[j]=temp;        

temp=A[l];        

A[l]=A[j];        

j=l;l=(j+k)%n;      

}// 循环右移一步      

A[i]=temp;    

}//for 

}//RSh

数据结构随记_2

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

推荐文章
编辑推荐
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号