程序設(shè)計(jì)語言基礎(chǔ)和編譯原理適用班級：軟件設(shè)計(jì)師主講：鄧少勛QQ：957052659網(wǎng)址：.bitpxEMail:957052659@qq比特培訓(xùn)中心貴州·貴陽TOC\o"13"\h\z\u第1節(jié)主要程序設(shè)計(jì)語言 圖7.7所示。圖STYLEREF1\s7.SEQ圖\*ARABIC\s15執(zhí)行完第(5)行的結(jié)果圖STYLEREF1\s7.SEQ圖\*ARABIC\s16執(zhí)行完第(6)行的結(jié)果圖STYLEREF1\s7.SEQ圖\*ARABIC\s17執(zhí)行完第(7)行的結(jié)果請不要去糾結(jié)以上代碼的功能，只需要理解“=”兩端是指針的賦值表達(dá)式中指針變量的指向問題。指針變量作為函數(shù)參數(shù)對輸入的兩個(gè)整數(shù)按從大到小順序輸出#include<stdio.h>voidswap(int*p1,int*p2){//指針變量作形參，接收來自實(shí)參的地址值 inttemp; temp=*p1; *p1=*p2; *p2=temp;}voidmain(){ inta,b; int*ptr1,*ptr2; scanf("%d,%d",&a,&b); ptr1=&a; ptr2=&b; if(a<b)swap(&a,&b); printf("%d,%d\n",a,b); printf("%x,%d",ptr1,*ptr2);}輸出結(jié)果：1,2//輸入2,1//從大到小輸出51f934,1//輸出ptr1存儲的地址和ptr2指向的存儲單元值問題：程序中的“a<b”能不能改成“*ptr1<*ptr2”？函數(shù)調(diào)用swap(&a,&b)能否改成swap(ptr1,ptr2)？在程序運(yùn)行過程中，指針的指向改變了嗎？a、b兩個(gè)存儲單元的值變了嗎？指向數(shù)組元素的指針變量inta[5]={1,2,3,4,5};int*p;p=a;或p=&a[0];定義的時(shí)候：int*p=a；或int*p=&a[0]行不行？圖STYLEREF1\s7.SEQ圖\*ARABIC\s18指針指向數(shù)組如REF_Ref386703610\h圖7.8所示，如果p的初值是&a[0]，則：p+i和a+i就是a[i]的地址，或者說，他們都指向a數(shù)組中的第i個(gè)元素。printf("%x\n",p+3);//輸出3號單元地址printf("%x\n",a+3);//輸出3號單元地址輸出結(jié)果：91f90c//3號單元地址91f90c//3號單元地址*（p+i）或*（a+i）是p+i或a+i所指向的第i號數(shù)組元素的值。printf("%d\n",*(p+3));//輸出3號單元值printf("%d",*(a+3));//輸出3號單元值輸出結(jié)果：44指向數(shù)組的指針變量也可以帶下標(biāo)，如p[i]與a[i]、*(p+i)、*(a+i)等價(jià)。printf("%d\n",p[3]);//輸出3號單元值printf("%d",a[3]);//輸出3號單元值輸出結(jié)果：44當(dāng)指針指向地址連續(xù)的同一段內(nèi)存單元式，可對指針進(jìn)行++、及比較運(yùn)算通過指針輸入和輸出數(shù)組數(shù)據(jù)#include<stdio.h>voidmain(){ inta[5]; int*p=a,*r=&a[4]; for(;p<=r;p++) { scanf("%d",p); } p=&a[0];//也可寫p=a; for(;p<=a+4;p++) { printf("%d",*p); }}問題：程序中p=&a[0];作用是什么？刪除會出現(xiàn)什么后果？程序循環(huán)中的p能換成a嗎？如p++能換成a++嗎？指針數(shù)組和指向指針的指針指針數(shù)組的概念整型數(shù)組中每個(gè)存儲單元存儲的是一個(gè)整數(shù)，同理，指針數(shù)組的每個(gè)存儲單元存儲的是一個(gè)指針(地址)。定義如REF_Ref386721929\h圖7.9所示:圖STYLEREF1\s7.SEQ圖\*ARABIC\s19指針數(shù)組的定義#include<stdio.h>voidmain(){ inta=1,b=2,c=3,d=4; int*ints[4]={&a,&b,&c,&d}; for(inti=0;i<4;i++) { printf("%d",*ints[i]); }}輸出結(jié)果為：1234以上代碼中，p為一指針數(shù)組，其對應(yīng)的內(nèi)存圖如REF_Ref386722761\h圖7.10所示。圖STYLEREF1\s7.SEQ圖\*ARABIC\s110整型指針數(shù)組#include<stdio.h>voidmain(){ char*name[]={"HelloWorld","Bitpx"}; for(inti=0;i<2;i++) { printf("%s\n",name[i]); } //輸出"World"和"px"兩子串 puts(name[0]+6); puts(name[1]+3);}輸出結(jié)果：HelloWorldBitpxWorldpx以上代碼對應(yīng)的內(nèi)存圖如REF_Ref386724207\h圖7.11所示。圖STYLEREF1\s7.SEQ圖\*ARABIC\s111內(nèi)存圖指向指針的指針（二維指針）#include<stdio.h>voidmain(){ inta=8; int*p; int**r;//定義二維指針兩個(gè)*號 p=&a; r=&p; printf("%d\n",*p);//通過一維指針輸出 printf("%d",**r);//通過二維指針輸出}輸出結(jié)果為：88以上代碼對應(yīng)的內(nèi)存圖如REF_Ref386724723\h圖7.12所示。圖STYLEREF1\s7.SEQ圖\*ARABIC\s112二維指針#include<stdio.h>voidmain(){ char*name[]={"HelloWorld","Bitpx"}; char**r; r=name; for(inti=0;i<2;i++) { printf("%s\n",r[i]);//通過二維指針訪問 } //輸出"World"和"px"兩子串 puts(r[0]+6);//通過二維指針訪問 puts(r[1]+3);//通過二維指針訪問 inta=1,b=2,c=3,d=4; int*ints[4]={&a,&b,&c,&d}; int**p=ints; for(inti=0;i<4;i++) { printf("%d",*p[i]);//通過二維指針訪問 }}輸出結(jié)果：HelloWorldBitpxWorldpx1234注意：指針數(shù)組名就是二維指針(地址)常量，指針數(shù)組地址應(yīng)使用二維指針變量來存儲?！瘛?009年下】以下關(guān)于C/C++語言指針變量的敘述中，正確的是（21）。（21）A.指針變量可以是全局變量也可以是局部變量B.必須為指針變量與指針?biāo)赶虻淖兞糠峙湎嗤笮〉拇鎯臻gC.對指針變量進(jìn)行算術(shù)運(yùn)算是沒有意義的D.指針變量必須由動態(tài)產(chǎn)生的數(shù)據(jù)對象來賦值結(jié)構(gòu)體類型假設(shè)現(xiàn)在需要定義一種數(shù)據(jù)類型，如學(xué)生類型，其包含學(xué)生的屬性，如學(xué)號、姓名、性別、出生日期、成績、地址等信息，而C語言的預(yù)定類型中沒有這種數(shù)據(jù)類型，此時(shí)可定義用戶自定類型，即結(jié)構(gòu)體類型來滿足這一要求。在面向?qū)ο缶幊陶Z言中，可定義結(jié)構(gòu)體類型和類類型滿足此要求。聲明一個(gè)結(jié)構(gòu)體類型struct結(jié)構(gòu)體類型名{類型名成員名;………}；定義結(jié)構(gòu)體類型變量要先定義結(jié)構(gòu)體數(shù)據(jù)類型，才能定義屬于這種類型的變量。定義結(jié)構(gòu)體類型變量有三種形式：先聲明結(jié)構(gòu)體數(shù)據(jù)類型，在定義變量#include<stdio.h>#include<string.h>structstudent//聲明結(jié)構(gòu)體類型{ intno; charname[20]; chargender;};voidmain(){ structstudentstu;//定義結(jié)構(gòu)體變量 stu.no=100;//使用"結(jié)構(gòu)體變量.成員"形式訪問strcpy(,"dsx"); stu.gender='m'; printf("學(xué)號為:%d,姓名為:%s,性別為:%c",stu.no,,stu.gender);}輸出結(jié)果：學(xué)號為:100,姓名為:dsx,性別為:m假設(shè)int占2字節(jié)，char占一個(gè)字節(jié)，則結(jié)構(gòu)體變量stu的內(nèi)存圖如REF_Ref386727274\h圖8.1所示。圖STYLEREF1\s8.SEQ圖\*ARABIC\s11stu內(nèi)存圖在聲明類型的同時(shí)定義變量#include<stdio.h>#include<string.h>structstudent//聲明結(jié)構(gòu)體類型{ intno; charname[20]; chargender;}stu1,stu2;//聲明結(jié)構(gòu)體類型時(shí)定義結(jié)構(gòu)體變量voidmain(){ structstudentstu3;//定義結(jié)構(gòu)體變量 stu1.no=100;//使用"結(jié)構(gòu)體變量.成員"形式訪問 strcpy(,"dsx"); stu1.gender='m'; printf("stu1學(xué)號為:%d,姓名為:%s,性別為:%c",stu1.no,,stu1.gender);}輸出結(jié)果：stu1學(xué)號為:100,姓名為:dsx,性別為:m也可使用如下的定義方式：struct//只有struct關(guān)鍵字，無結(jié)構(gòu)體類型名{ intno; charname[20]; chargender;}stu;//只能在此定義結(jié)構(gòu)體變量常用的定義習(xí)慣（使用類型定義typedef）#include<stdio.h>#include<string.h>typedefstructstudent//聲明結(jié)構(gòu)體類型{ intno; charname[20]; chargender;}STU;//聲明STU為structstudent類型voidmain(){ STUstu;//定義結(jié)構(gòu)體變量//同樣也可使用structstudentstu；定義 stu.no=100;//使用"結(jié)構(gòu)體變量.成員"形式訪問 strcpy(,"dsx"); stu.gender='m'; printf("學(xué)號為:%d,姓名為:%s,性別為:%c",stu.no,,stu.gender);}類型定義typedef作用:聲明新的類型名來代替已有的類型名。注意：類型與變量是不同的概念，只能對變量賦值，不能對類型賦值。對結(jié)構(gòu)中的成員（即“域”），可以單獨(dú)任用，它的作用地位相當(dāng)于普通的變量。成員也可以是一個(gè)結(jié)構(gòu)體變量。#include<stdio.h>structdate{ inty; intm; intd;};typedefstructstudent{ intno; structdaterq;//rq為結(jié)構(gòu)體類型}STU;voidmain(){ STUstu; stu.no=100; stu.rq.y=1990; stu.rq.m=10; stu.rq.d=15; printf("學(xué)號為:%d,出生日期為:%d%d%d",stu.no,stu.rq.y,stu.rq.m,stu.rq.d);}輸出結(jié)果為：學(xué)號為:100,出生日期為:假設(shè)int占2字節(jié)，則以上代碼中stu結(jié)構(gòu)體變量的內(nèi)存如REF_Ref386732433\h圖8.2所示。圖STYLEREF1\s8.SEQ圖\*ARABIC\s12stu內(nèi)存圖結(jié)構(gòu)體變量的引用不能將一個(gè)結(jié)構(gòu)體變量作為一個(gè)整體進(jìn)行輸入和輸出，只能是“結(jié)構(gòu)體變量.成員”printf("no:%d,name:%s",stu.no,);如果成員是一個(gè)結(jié)構(gòu)體，一級一級的展開。printf(“%d”,stu.rq.y);對結(jié)構(gòu)體變量的成員可以像普通變量一樣運(yùn)算。stu1.no=stu2.no;stu.rq.d++;可以引用結(jié)構(gòu)體變量成員的地址，也可以引用結(jié)構(gòu)變量的地址。scanf(“%d”,&stu.no);//輸入學(xué)生學(xué)號printf(“%x”，&stu);//輸出結(jié)構(gòu)體變量的地址結(jié)構(gòu)體變量的初始化#include<stdio.h>structdate{ inty;· intm; intd;}rq={110,12,3};//定義變量時(shí)初始化typedefstructstudent//聲明結(jié)構(gòu)體類型{ intno; structdaterq;}STU;voidmain(){ STUstu={110,1990,12,4};//初始化 printf("年:%d,月:%d,日:%d\n",rq.y,rq.m,rq.d); printf("學(xué)號:%d,生日:%d%d%d",stu.no,stu.rq.y,stu.rq.m,stu.rq.d);}輸出結(jié)果為：年:110,月:12,日:3學(xué)號:110,生日:指向結(jié)構(gòu)體變量的指針可以設(shè)置一個(gè)指針變量，用來指向一個(gè)結(jié)構(gòu)體變量，此時(shí)該指針變量的值是結(jié)構(gòu)體變量的起始地址。STUstu;STU*p;p=&stu;//讓指針變量指向結(jié)構(gòu)體變量stu.no=100;strcpy(,"dsx");printf("no:%d,name:%s\n",stu.no,);printf("no:%d,name:%s\n",(*p).no,(*p).name);printf("no:%d,name:%s\n",p>no,p>name);在C語言中，通過指針訪問結(jié)構(gòu)體成員為“(*p).no”形式，但為了更方便和直觀，可把(*p).no改用p>no來代替，它表示*p所指向的結(jié)構(gòu)提變量中的no成員。同樣，(*p).name等價(jià)于p>name。結(jié)構(gòu)體和共用體的區(qū)別#include<stdio.h>unionMyUnion//定義共同體{ inta; floatb; doublec;};structMyStruct//定義結(jié)構(gòu)體{ inta; floatb; doublec;};voidmain(){ unionMyUnionmu; mu.a=1; mu.b=2; mu.c=4; printf("%d\n",sizeof(mu));//輸出共用體長度 structMyStructms; ms.a=1; ms.b=2; ms.c=4; printf("%d",sizeof(ms));//輸出結(jié)構(gòu)體長度}輸入結(jié)果：816注意：共用體變量是所有成員共享同一段內(nèi)存單元，這段共用的內(nèi)存單元大小按共用體中占內(nèi)存字節(jié)最長的成員所占用的內(nèi)存空間計(jì)算，如mu共用體變量，其中double類型成員c占8個(gè)字節(jié)，而且是占用內(nèi)存空間最長的成員(假設(shè)int和float都占4字節(jié)，double占8字節(jié))，故sizeof(mu)的值為8。結(jié)構(gòu)體變量占用的內(nèi)存單元式各個(gè)成員占用的內(nèi)存單元總和，故sizeof(ms)結(jié)果為16?！瘛?007年下】給定C語言的數(shù)據(jù)結(jié)構(gòu)structT{intw;unionT{charc;inti;doubled;}U;};假設(shè)char類型變量的存儲區(qū)大小是1字節(jié)，int類型變量的存儲區(qū)大小是4字節(jié)，double類型變量的存儲區(qū)大小是8字節(jié)，則在不考慮字對齊方式的情況下，為存儲一個(gè)structT類型變量所需要的存儲區(qū)域至少應(yīng)為（15）字節(jié)。（15）A.4 B.8 C.12 D.17鏈表知識鏈表概述鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，它是動態(tài)地進(jìn)行存儲分配的一種結(jié)構(gòu)。用數(shù)組存放數(shù)據(jù)時(shí)，必須事先定義固定的長度（即元素個(gè)數(shù)），這會造成內(nèi)存空間的浪費(fèi)，鏈表則沒有這種缺點(diǎn)，它根據(jù)需要開辟內(nèi)存單元。圖STYLEREF1\s9.SEQ圖\*ARABIC\s11帶頭指針及頭結(jié)點(diǎn)的鏈表鏈表有一個(gè)“頭指針”變量，REF_Ref386739421\h圖9.1中以head表示，它存放一個(gè)地址（在圖中是頭結(jié)點(diǎn)HeadN的地址1000）。而頭結(jié)點(diǎn)的指針域指向鏈表的首結(jié)點(diǎn)(指針域存儲的是首結(jié)點(diǎn)的地址1249)。在鏈表中，頭結(jié)點(diǎn)不是必須的，如果沒有頭結(jié)點(diǎn)，頭指針直接指向鏈表的首結(jié)點(diǎn)即可。鏈表中每一個(gè)結(jié)點(diǎn)的地址都是不連續(xù)的（連續(xù)是非常特殊的情況），每個(gè)結(jié)點(diǎn)都應(yīng)包括兩個(gè)部分：一為用戶需要用的實(shí)際數(shù)據(jù)，二為下一個(gè)結(jié)點(diǎn)的地址，在鏈表中，最后一個(gè)結(jié)點(diǎn)稱為尾結(jié)點(diǎn)，其不再指向其他元素，它的地址部分指向“NULL”（表示“空地址”），鏈表到此結(jié)束。處理動態(tài)鏈表所需的函數(shù)malloc函數(shù)void*malloc(unsignedintsize)在內(nèi)存的動態(tài)存儲區(qū)中分配一個(gè)長度為size的連續(xù)空間。申請成功返回空間的首地址，不成功則返回空（NULL）.calloc函數(shù)void*calloc(unsignedn,unsignedsize)在內(nèi)存的動態(tài)存儲區(qū)中分配n長度為size的連續(xù)空間。申請成功返回空間的首地址，不成功則返回空（NULL）.用calloc函數(shù)可以為一維數(shù)組開辟動態(tài)存儲空間，n為數(shù)組元素個(gè)數(shù)，每個(gè)元素長度為size。free函數(shù)voidfree(void*p);釋放由p指向的內(nèi)存區(qū)，使這部分內(nèi)存區(qū)能被其他變量使用。P是最近一次調(diào)用calloc或malloc函數(shù)時(shí)返回的值。注意，其無返回值。建立動態(tài)鏈表#include<stdlib.h>#include<stdio.h>#defineNULL0#defineLENsizeof(structSTU)typedefstructSTU{ intno; floatscore; structSTU*next;}STU;//補(bǔ)充:*STUtypedefstructHeadNode{ intn;//存儲鏈表中結(jié)點(diǎn)個(gè)數(shù) STU*next;}HN;//補(bǔ)充講解*HN情況//創(chuàng)建時(shí)有兩種情況://1.鏈表為空從創(chuàng)建第一個(gè)結(jié)點(diǎn)開始//2.鏈表不為空—把當(dāng)前結(jié)點(diǎn)加到已存在鏈表的尾部.HN*Creat(void){ HN*head;//定義頭指針和頭結(jié)點(diǎn) STU*p,*q; head=(HN*)malloc(sizeof(HN)*1); head>n=0; head>next=NULL; p=q=(STU*)malloc(LEN);//Why有*? if(!p)returnNULL;//p==NULL scanf("%d,%f",&p>no,&p>score); while(p>no!=0)//輸入0結(jié)束創(chuàng)建 { head>n++; if(head>n==1)head>next=p;//創(chuàng)建第一個(gè)結(jié)點(diǎn) else//創(chuàng)建其他結(jié)點(diǎn) { q>next=p;q=p; } p=(STU*)malloc(LEN); if(!p)returnNULL; scanf("%d,%f",&p>no,&p>score); } q>next=NULL; free(p);//不是必須的 return(head);}注意:head指向頭結(jié)點(diǎn),q指向鏈表的尾結(jié)點(diǎn),p指向當(dāng)前結(jié)點(diǎn)(即當(dāng)前創(chuàng)建的結(jié)點(diǎn))。加入一個(gè)結(jié)點(diǎn)后,鏈表中結(jié)點(diǎn)個(gè)數(shù)要加1，故要執(zhí)行head>n++。輸出鏈表打印時(shí)有兩種情況:1.鏈表為空—不打印2.鏈表不為空—從第一個(gè)結(jié)點(diǎn)開始往后打印。voidPrint(HN*head){ STU*p; p=head>next; if(head>next!=NULL) { do { printf("%1d,%5.1f\n",p>no,p>score); p=p>next; }while(p!=NULL); } else{printf("鏈表為空！");}}注意:head指向頭結(jié)點(diǎn),p指向當(dāng)前打印結(jié)點(diǎn)。對鏈表的刪除操作刪除鏈表有兩種情況:鏈表為空—不執(zhí)行刪除操作鏈表不為空(此種情況先進(jìn)行查找):沒有找到待刪除的結(jié)點(diǎn)找到:待刪除結(jié)點(diǎn)為首結(jié)點(diǎn)待刪除結(jié)點(diǎn)為非首結(jié)點(diǎn)HN*Del(HN*head,intno){ STU*p,*q; if(head>next==NULL)returnNULL;//鏈表為空 p=head>next; while(no!=p>no&&p>next!=NULL) {//往后找需要?jiǎng)h除的結(jié)點(diǎn) q=p;p=p>next; } if(no==p>no)//找到 { if(p==head>next){head>next=p>next;} //首結(jié)點(diǎn)為刪除結(jié)點(diǎn) else{q>next=p>next;} //待刪除結(jié)點(diǎn)非首結(jié)點(diǎn) head>n; free(p);//不是必須的 printf("刪除%d成功了！\n",no); } elseprintf("notbeenfound"); return(head);}注意:head指向頭結(jié)點(diǎn),p指向當(dāng)前結(jié)點(diǎn)(即待刪除結(jié)點(diǎn)),q指向當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn).刪除一個(gè)結(jié)點(diǎn)后,鏈表中結(jié)點(diǎn)個(gè)數(shù)要減1，故要執(zhí)行head>n操作。對鏈表的插入操作前提:假如已經(jīng)存在的鏈表元素為空表或數(shù)據(jù)從小到大排序的表。插入是有兩種情況:原鏈表為空—?jiǎng)?chuàng)建鏈表,把待插入的結(jié)點(diǎn)作為鏈表首結(jié)點(diǎn).原鏈表非空—進(jìn)行查找,查找結(jié)點(diǎn)的插入位置插入位置在首結(jié)點(diǎn)之前插入位置在鏈表中插入位置在鏈尾HN*Insert(HN*head,STU*stu){ STU*c,*p,*q; p=head>next; c=stu; if(head>next==NULL)//鏈表為空的情況 { head>next=c;c>next=NULL; } else { while((c>no>p>no)&&(p>next!=NULL)) {//查找插入位置 q=p; p=p>next; } } if(c>no<=p>no) {//插入到首結(jié)點(diǎn)前或者鏈表中 if(head>next==p)head>next=c;//插入位置在首結(jié)點(diǎn)之前 else{q>next=c;}//插入位置在鏈表中部 c>next=p; } else {//插入位置在鏈表的末尾 p>next=c;c>next=NULL; } head>n++; return(head);}注意:head指向頭結(jié)點(diǎn),c指向待插入的結(jié)點(diǎn),p指向鏈表中當(dāng)前結(jié)點(diǎn)(和c指向結(jié)點(diǎn)進(jìn)行比較的結(jié)點(diǎn)),q指向當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。插入一個(gè)結(jié)點(diǎn)后,鏈表中結(jié)點(diǎn)個(gè)數(shù)要加1，即執(zhí)行head>n++操作。main函數(shù)寫法示例voidmain(){ HN*head=Creat(); printf("刪除前鏈表內(nèi)容為：\n"); Print(head); head=Del(head,120); printf("刪除后鏈表內(nèi)容為：\n"); Print(head); STU*stu=(STU*)malloc(LEN); stu>no=120; stu>score=78; head=Insert(head,stu); printf("插入結(jié)點(diǎn)后鏈表內(nèi)容為：\n"); Print(head);}輸入數(shù)據(jù)：100,98回車120,67回車130,89回車140,100回車0,90回車輸出結(jié)果為：刪除前鏈表內(nèi)容為：100,98.0120,67.0130,89.0140,100.0刪除120成功了！刪除后鏈表內(nèi)容為：100,98.0130,89.0140,100.0插入結(jié)點(diǎn)后鏈表內(nèi)容為：100,98.0120,78.0130,89.0140,100.0請按任意鍵繼續(xù)...枚舉類型（會應(yīng)用）聲明枚舉類型用enum開頭。enumweekday{sun,mon,tue,wed,thu,fri,sat};enumweekdayworkday;//定義變量workday＝mon;//給變量賦值typedefenumWeekday{sun,mon,tue,wed,thu,fri,sat}WEEKDAY;WEEKDAYdate;//一種定義形式enumWeekdaydate1;//另一種定義形式注意一對枚舉元素按常量處理,故稱為枚舉常量.它們不是變量,不能對它們進(jìn)行賦值.sun=0;mon=1;//錯(cuò)誤注意二枚舉元素作為常量,它們是有值的,C語言編譯按定義時(shí)的順序使它們的值為0,1,….例子:voidmain(){ typedefenumWeekday { sun,mon,tue,wed,thu,fri,sat }WEEKDAY; inti; for(i=sun;i<=sat;i++) { printf("%d\n",i); }}程序的內(nèi)存分配一個(gè)由c/c++編譯的程序占用的內(nèi)存分為以下幾個(gè)部分：棧區(qū)（stack）：由編譯器自動分配釋放，存放函數(shù)的參數(shù)值，局部變量的值等。其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧。堆區(qū)（heap）：一般由程序員分配釋放，若程序員不釋放，程序結(jié)束時(shí)可能由OS回收。注意它與數(shù)據(jù)結(jié)構(gòu)中的堆是兩回事，鏈表的數(shù)據(jù)空間必須采用堆存儲分配策略。全局區(qū)（靜態(tài)區(qū)）（static）：全局變量和靜態(tài)變量的存儲是放在這一塊的。初始化的全局變量和靜態(tài)變量在一塊區(qū)域，未初始化的全局變量和未初始化的靜態(tài)變量在相鄰的另一塊區(qū)域，程序結(jié)束后由系統(tǒng)釋放。文字常量區(qū)：常量字符串就是放在這里的，程序結(jié)束后由系統(tǒng)釋放。程序代碼區(qū)：存放函數(shù)體的二進(jìn)制代碼?！瘛?009年下】若一個(gè)程序語言可以提供鏈表的定義和運(yùn)算，則其運(yùn)行時(shí)的（49）。（49）A.數(shù)據(jù)空間適合采用靜態(tài)存儲分配策略B.數(shù)據(jù)空間必須采用堆存儲分配策略C.指令空間需要采用棧結(jié)構(gòu)D.指令代碼必須放入堆區(qū)●【2015年上】C程序中全局變量的存儲空間在(22)分配。(22)A.代碼區(qū)B.靜態(tài)數(shù)據(jù)區(qū)C.棧區(qū)D.堆區(qū)形式化語言基礎(chǔ)知識字母表和符號串字母表是元素的非空有限集合，把字母表中的元素稱為符號，因此字母表也稱為符號集。如：∑＝{a,b,c}是由三個(gè)字母組成的字母表（或符號集）∑。符號串由字母表中的符號組成的任何有窮序列，例如00，11，10,0,1,000,是字母表∑={0，1}上的符號串，又如字母表A={a,b,c}上的一些符號串有：a,b,c,ab,aaca等。在符號串中，符號的順序是很重要的，例如符號串a(chǎn)b就不同于ba,abca和aabc也不同?？沾忙艁肀硎?。符號串的長度如果某符號串x中有m個(gè)符號，則稱其長度為|x|=m,如x＝001110，則m＝|001110|=6。符號串之間的運(yùn)算符號串的連接如：x=ab,(ab)0=ε，(ab)1=ab，(ab)2=abab,(ab)3=ababab，….(ab)n=(ab)+(n>=1)或者(ab)*(n>=0,其中包括ε）問題：假設(shè)x=a？符號串集合若集合A中的一切元素都是某字母表上的符號串，則稱A為該字母表上的符號串集合。兩個(gè)符號串集合A和B的乘積如下：AB={XY|X€A且Y€B}。例如：A={a,b},B={c,d},則集合AB={ac,ad,bc,bd}，因?yàn)閷θ我夥柎畑有εx=xε=x,所以有{ε}A=A{ε}=A。在指定字母表∑之后，可以用∑*表示∑上的所有有窮長的串的集合。例如：∑={0,1},則∑*={ε，0，1，00，01，10，11，000，001，010，……….},也可以表示為字母表的方冥形式：∑*=∑0∪∑1∪∑2∪∑3…∪∑n…∑*稱為集合∑的閉包。而∑+=∑1∪∑2∪∑3…∪∑n…稱為∑的正閉包.顯然有∑*=∑0∪∑+，∑*具有無窮數(shù)量的元素。使用一般的集合論的表示符號：如x是∑*中的元素，則表示x€∑*,否則x∑*，對于所有的∑*，都有ε€∑*。文法的形式定義文法G定義為一個(gè)四元組（vNvT,P,S）。其中：vN：一個(gè)非空有限的符號集合，它的每個(gè)元素稱為非終結(jié)符號（一般用大寫字母表示）。vT：是一個(gè)非空有限的符號集合，它的每個(gè)元素成為終結(jié)符（一般為小寫字母或數(shù)字表示），并且有vN∩vT=Ф。S：S€vN，稱為文法G的開始符號。P：是一個(gè)非空有限集合，它的元素稱為產(chǎn)生式，形如а→β，а稱為產(chǎn)生式的左部，β稱為產(chǎn)生式的右部，符號“→”表示為“定義為”，并且а、β€（vN∪vT）*，а≠ε，即а、β是由終結(jié)符和非終結(jié)符組成的符號串。開始符號S必須至少在某一產(chǎn)生式的左部出現(xiàn)一次。另外可以對形如а→β，а→γ的產(chǎn)生式縮寫為а→β|γ。文法的表示形式如下：例1：文法G=（vN，vT，p,S），其中vN={S},vT={0，1},P={S→0S1,S→01}例2：設(shè)G=（vN，vTp,S）,vN={S,B,E},vT={a,b,c},P由下列產(chǎn)生式組成：S→aSBE|aBEEB→BEaB→abbB→bbbE→beeE→ee文法的類型0型文法設(shè)G=（Vn,Vt,P,S），如果它的每個(gè)產(chǎn)生式а→β是這樣一種結(jié)構(gòu):а€（Vn∪Vt）*，|а|≠0,且至少包含一個(gè)非終結(jié)符，而β€（Vn∪Vt）*，則G是一個(gè)0型文法，也稱短語文法。如以下文法為0型文法：設(shè)G=（vN,vT，P,S）,vn={S,B,E},vT={a,b,e},P由下列產(chǎn)生式組成：(1)S→aSBE|aBE(2)EB→BE(3)aB→ab(4)bB→bb(5)bE→be(6)eE→ee對0型文法產(chǎn)生式的形式作某些限制，就得到1，2，3型文法的定義.1型文法設(shè)G=(vN,vT,p,s）為一個(gè)文法，若P中的每一個(gè)產(chǎn)生式а→β均滿足|β|≥|а|,僅僅s→ε除外，則文法G為1型或上下文有關(guān)文法。如以下文法為1型文法：設(shè)G=（vN，vT，p,s）,vN={S,B,E},vT={a,b,e},P由下列產(chǎn)生式組成：(1)S→aSBE|aBE(2)EB→BE(3)aB→ab(4)bB→bb(5)bE→be(6)eE→ee以上文法，每個(gè)|β|≥|а|，如|aSBE|=4>|S|=1，|ab|=2=|aB|所以其既是0型文法，同時(shí)也是1型文法。2型文法設(shè)G=（vN，vT，p,s）為一文法，若P中的每一個(gè)產(chǎn)生式а→β滿足：а屬于一個(gè)非終結(jié)符，β€（vN∪vT）*，則此文法稱為2型文法或上下文無關(guān)文法。上下文無關(guān)文法（2型文法）是形式語言理論中一種重要的變換文法，用來描述上下文無關(guān)語言。由于程序設(shè)計(jì)語言的語法基本上都是上下文無關(guān)文法，因此應(yīng)用十分廣泛。如以下文法為2型文法：G=({S,A,B},{a,b},P,S），其中P由下列產(chǎn)生式組成：S→aBA→BAAS→bAB→bA→aB→bSA→aSB→aBB可改寫為：S→aB|bA，A→BAA|a|aS,B→b|bS|aBB3型文法設(shè)G=（vN,vT,p,s）為一文法，若P中的每一個(gè)產(chǎn)生式а→β都為A→aB或A→a（右線性）,或A→Ba或A→a（左線性），其中A和B都是非終結(jié)符，a是終結(jié)符，則G是3型文法或正規(guī)文法。如以下文法為3型文法：文法G=（{S，A，B}，{0，1}，P，S），P由下列產(chǎn)生式組成：S→0AA→1BS→1BB→1BS→0B→1A→0AB→0A→顯然G是正規(guī)文法?！瘛?014年下】對于大多數(shù)通用程序設(shè)計(jì)語言，用(50)描述其語法即可。(50)A.正規(guī)文法B.上下文無關(guān)文法C.上下文有關(guān)文法D.短語結(jié)構(gòu)文法推導(dǎo)如а→β是文法G=（vN，vT，p,s）的規(guī)則（或說是P中的一個(gè)產(chǎn)生式），γ和δ是V*中的任意符號，如有符號串v,w滿足：v=γаδ，w=γβδ,由于а→β，代入v=γаδ中得γβδ，所以可以說V應(yīng)用規(guī)則а→β直接產(chǎn)生w,或說,w是v的直接推導(dǎo)，或說，w直接規(guī)約到v，記為：v＝＞w。例如：v=0S1,w=0011，應(yīng)用規(guī)則S→01，直接推導(dǎo)：0S1＝＞0011，則v應(yīng)用規(guī)則S→01直接產(chǎn)生w,或說,w是v的直接推導(dǎo)。這里γ為0，δ為1。v=S，w=0S1，直接推導(dǎo)：S＝＞0S1，應(yīng)用規(guī)則為：S→0S1，這里γ為ε，δ為ε。如果存在直接推導(dǎo)的序列：V=w0w1w2……wn=W,(n>0)則稱W規(guī)約到v，或者稱v推導(dǎo)出(產(chǎn)生)W（推導(dǎo)長度為n），記作。若有，或v=w，則記作，例如：文法G=(VN,VT,P,S）,其中Vn={S},Vt={0,1},P={S→0S1,S→01}，存在直接推導(dǎo)序列：V=0S1＝＞00S11＝＞000S111＝＞00001111=W,即。句型和句子設(shè)G[S]是一文法，如果符號串x是從識別符號推導(dǎo)出來的，即有，則稱x是文法G[S]的句型。如x僅由終結(jié)符號組成，即，則稱x為G[S]的句子。例如：文法G=(VN,VT,P,S）,其中Vn={S},Vt={0,1}，P={S→0S1,S→01}。其中S,0S1，00S11，000S111，00001111都是文法G的句型，其中00001111是G的句子。語言文法G所產(chǎn)生的語言定義為集合{x|,其中S為文法識別符號，且}，可以用L（G）表示該集合。換句話說：文法描述的語言是該文法一切句子的集合。上下文無關(guān)文法和語法樹上下文無關(guān)文法（2型文法）是形式語言理論中一種重要的變換文法，用來描述上下文無關(guān)語言。由于程序設(shè)計(jì)語言的語法基本上都是上下文無關(guān)文法，因此應(yīng)用十分廣泛。語法樹，也成為推導(dǎo)樹，是描述上下文無關(guān)文法的句型推導(dǎo)的直觀方法。因?yàn)榫湫筒晃ㄒ?，所以語法樹也不唯一。給定文法G=（VN，VT，P,S）,對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法書（推導(dǎo)樹）。這棵樹滿足下列條件：每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V（V=VN∪VT）的一個(gè)符號。根的標(biāo)記為S若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則A肯定在Vn中。如果結(jié)點(diǎn)n的直接子孫，從左到右的次序是節(jié)點(diǎn)n1,n2,n3,……，nk,其標(biāo)記分別為A1，A2，A3，……，Ak.那么A→A1A2A3……例如：G=（{S，A}，{a，b}，P，S}），其中P為：S→aASA→SbAA→SSS→aA→ba此文法的一個(gè)句型為aabbaa,其對應(yīng)的語法樹如REF_Ref386788258\h圖12.1所示。圖STYLEREF1\s12.SEQ圖\*ARABIC\s11aabbaa對應(yīng)的語法樹問題：構(gòu)建語法樹的時(shí)候，是不是每個(gè)產(chǎn)生式都要用到？如上例中的A→SS就沒有用到。正規(guī)式和正規(guī)集設(shè)Σ為有限字母表，在Σ上的正規(guī)式與正規(guī)集可遞歸定義如下：1.ε和Ф是Σ上的正規(guī)式，它們表示的正規(guī)集分別為{ε}和Ф；2.對任何a∈Σ,a是Σ上的正規(guī)式,它的正規(guī)集為{a}；3.若r,s都是正規(guī)式,它們的正規(guī)集分別為R和S,則(r|s)、(r·s)、(r)*也是正規(guī)式，它們分別表示的正規(guī)集是：R∪S，RS，R*。4.有限次使用上述三條規(guī)則構(gòu)成的表達(dá)式，稱為Σ上的正規(guī)式，僅由這些正規(guī)式表示的集合為正規(guī)集。更多正規(guī)式與正規(guī)集轉(zhuǎn)換關(guān)系如REF_Ref386831195\h表12.1所示：表STYLEREF1\s12.SEQ表\*ARABIC\s11正規(guī)式與正規(guī)集關(guān)系表正規(guī)式正規(guī)集a{a}a|b{a,b}ab{ab}(a|b)(a|b){aa,ab,ba,bb}a* {ε,a,aa,…..任意個(gè)a的串}(a|b)*{ε,a,b,aa,bb…..任意個(gè)所有a,b組成的串}注意：∑*=∑0∪∑1∪∑2∪∑3…∪∑n…設(shè)r，s，t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：r|s=s|r“或”滿足交換律r|(s|t)=(r|s)|t“或”滿足結(jié)合律(rs)t=r(st)“連接”的可結(jié)合律r(s|t)=rs|rt分配律(s|t)r=sr|trr=r，r=r，是“連接”的恒等元素正規(guī)式是描述程序語言單詞的表達(dá)式，正則文法到正規(guī)式的轉(zhuǎn)換規(guī)則如REF_Ref386831606\h表12.2所示。表STYLEREF1\s12.SEQ表\*ARABIC\s12正則文法到正規(guī)式的轉(zhuǎn)換規(guī)則文法產(chǎn)生式正規(guī)式規(guī)則1A→xB,B→yA→xy規(guī)則2A→xA|yA→x*y規(guī)則3A→x,A→yA→x|y●【2004年】文法G[S]：S→xSx|y所描述的語言是：A．(xyx)nB.xyxnC.xynD.xnyxn●【2002年】與正規(guī)式(a|b)*等價(jià)的正規(guī)式為：A．a(chǎn)*|b*B.a*b*C.(a*b*)*D.(ab)*●令∑={a,b},∑上的正規(guī)式和相應(yīng)的正規(guī)集有如下：一個(gè)文法G=(N，T，P，S)，其中N是非終結(jié)符號的集合，T是終結(jié)符號的集合，P是產(chǎn)生式集合，S是開始符號，令集合V=N∪T，那么G所描述的語言是(15)的集合。(15)A.由S推導(dǎo)出的所有符號串B.由S推導(dǎo)出的所有終結(jié)符號串 C.V中所有符號組成的符號串D.V的閉包中的所有符號串●【2003年上】以下關(guān)于語言L={anbn|n>1}的敘述中，正確的是(48)。(48)A.可用正規(guī)式“aa*bb*”描述，但不能通過有限自動機(jī)識別B.可用正規(guī)式“ambm”表示，也可用有限自動機(jī)識別C.不能用正規(guī)式表示，但可用有限自動機(jī)識別D.不能用正規(guī)式表示，也不能通過有限自動機(jī)識別問題:L={a*b*}與L={ambn|m≥0;n≥0}是正規(guī)集嗎?答案:只要m和n沒有任何關(guān)系便是正規(guī)集,否則不是。有窮自動機(jī)確定的有窮自動機(jī)（DFA）一個(gè)確定的有窮自動機(jī)M是一個(gè)五元組：M=（K,∑,f,S,Z）其中K是一個(gè)有窮集合，它的每一個(gè)元素稱為一個(gè)狀態(tài)；∑是也有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符，所以也稱∑為輸入符號字母表.f是轉(zhuǎn)換函數(shù)，是在Kx∑→K上的映像，即，如f(Ki,a)=Kj(Ki,Kj€K)就意味著，當(dāng)前狀態(tài)Ki，輸入字符為a時(shí)，將轉(zhuǎn)換到下一個(gè)狀態(tài)Kj，我們把Kj稱作Ki的一個(gè)后繼狀態(tài)；S€K是唯一的一個(gè)初態(tài)Z包含于K,是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。例：DFAM=({S，U，V，Q},{a,b},f,S,{Q})其中f定義為：f(S,a)=U，f(V,a)=U，f(S,b)=V，f(V,b)=Q，f(U,a)=Q，f(Q,a)=Q，f(U,b)=V，f(Q,b)=Q圖STYLEREF1\s12.SEQ圖\*ARABIC\s12狀態(tài)圖表示對于∑*中的任何字符串t,若存在一條從初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的道路,且這條路上所有弧的標(biāo)記符連接成的字符串等于t,則稱t可為DFAM所接受,若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn),則空字ε可為M所識別(接受)。如字符串baab可為REF_Ref386832464\h圖12.2狀態(tài)圖表示所示的DFA所接受，因?yàn)閒(S,baab)=f(f(S,b),aab)=f(V,aab)=f(f(V,a),ab)=f(U,ab)=f(f(U,a),b)=f(Q,b)=Q,Q屬于終態(tài)。不確定的有窮自動機(jī)（NFA）一個(gè)不確定的有窮自動機(jī)（NFA）M是一個(gè)五元組，M=（K，Σ，f,S,Z）其中K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；Σ是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符；f是一個(gè)從KΣ*到K的子集的映像。SK，一個(gè)非空初態(tài)集；ZK，是一個(gè)終態(tài)集。例：一個(gè)NFAM=（{0，1，2，3，4}，{a,b},f,{0},{2,4}）其中：f(0,a)={0,3}f(2,b)={2}f(0,b)={0,1}f(3,a)={4}f(1,b)={2}f(4,a)={4}f(2,a)={2}f(4,b)={4}它的狀態(tài)圖表示如REF_Ref386832724\h圖12.3所示：圖STYLEREF1\s12.SEQ圖\*ARABIC\s13（NFAM）對于∑*中的任何一個(gè)串t，若存在某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串（不理采那些標(biāo)記為ε的?。┑扔趖，則稱t可為NFAM所識別（讀出或接受）。NFA到DFA的轉(zhuǎn)換在有窮自動機(jī)的理論里,有這樣的定理:設(shè)L為一個(gè)由不確定的有窮自動機(jī)接受的集合,則存在一個(gè)接受L的確定的有窮自動機(jī)。使用子集法可將NFA轉(zhuǎn)換為DFA。為介紹算法首先定義對狀態(tài)集合I的幾個(gè)有關(guān)運(yùn)算：狀態(tài)集合I的ε—closure(I),定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條ε弧而能到達(dá)的狀態(tài)的集合。如輸入字符是空串，則自動機(jī)仍停留在原來的狀態(tài)上，顯然，狀態(tài)集合I的任何狀態(tài)S都屬于ε—closure(I)。狀態(tài)集合I的a弧轉(zhuǎn)換，表示為move(I,a)定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而達(dá)到的狀態(tài)的全體。我們使用下圖的NFAN的狀態(tài)集合來理解上述兩個(gè)運(yùn)算。圖STYLEREF1\s12.SEQ圖\*ARABIC\s14NFAN例：應(yīng)用上圖的算法對前述的NFAN構(gòu)造子集，步驟如下：首先計(jì)算，令T0=εclosure（0）={0，1，2，4}，T0未被標(biāo)記，它現(xiàn)在是子集族C的唯一成員。結(jié)果：T0標(biāo)記T0，令T1=εclosure（move(T0,a)）={1，2，3，4，6},將T1加入C中，T1未被標(biāo)記。結(jié)果：f(T0,a)=T1，令T2=εclosure(move(T0,b))={1,2,4,5,6},將T2加入C中，它未被標(biāo)記。結(jié)果：f(T0,b)=T2，目前得了三個(gè)狀態(tài)T0,T1,T2標(biāo)記T1，計(jì)算εclosure(move(T1,a)),結(jié)果為{1，2，3，4，6}，即T1，T1已在C中。結(jié)果：f(T1,a)=T1計(jì)算εclosure(move(T1,b))，結(jié)果為{1,2,4,5,6}，即T2，T2已在C中。結(jié)果：f(T1,b)=T2標(biāo)記T2，計(jì)算εclosure(move(T2,a))，結(jié)果為{1，2，3，4，6}，即T1，T1已在C中。結(jié)果：f(T2,a)=T1計(jì)算εclosure(move(T2,b))，結(jié)果為{1，2，4，5，6}，即T2，T2已在C中。結(jié)果：f(T2,b)=T2至此，算法終止共構(gòu)造了五個(gè)子集：T0={0，1，2，4}T1={1，2，3，4，6}T2={1，2，4，5，6}那么上圖的NFA構(gòu)造的DFA為:K={[T0]，[T1]，[T2]}Σ={a,b}F([T0],a)=[T1]F([T0],b)=[T2]F([T1],a)=[T1]F([T1],b)=[T2]F([T2],a)=[T1]F([T2],b)=[T2]S=[T0]Z=[T2]將[T0]，[T1]，[T2]重新命名A，B，C或0，1，2分別表示。若采用后者，該DFAM的狀態(tài)轉(zhuǎn)換圖如下：圖STYLEREF1\s12.SEQ圖\*ARABIC\s15（DFAM）正規(guī)式和有窮自動機(jī)的等價(jià)第一步：在M的狀態(tài)轉(zhuǎn)換圖上加兩個(gè)結(jié)，一個(gè)為x結(jié)點(diǎn)，一個(gè)為y結(jié)點(diǎn)。從x結(jié)點(diǎn)用ε弧連接到M的所有初態(tài)結(jié)點(diǎn)，從M的所有終態(tài)結(jié)點(diǎn)用ε弧連接到y(tǒng)結(jié)點(diǎn)。形成一個(gè)與M等價(jià)的M′，M′只有一個(gè)初態(tài)x和一個(gè)終態(tài)y。第二步：逐步消去M′中的所有結(jié)點(diǎn)，直至只剩下x和y結(jié)點(diǎn)。在消結(jié)過程中，逐步用正規(guī)式來標(biāo)記弧。其消結(jié)的規(guī)則如REF_Ref386833335\h圖12.6所示：圖STYLEREF1\s12.SEQ圖\*ARABIC\s16消結(jié)過程最后x和y結(jié)點(diǎn)間的弧上的標(biāo)記則為所求的正規(guī)式R。例：以REF_Ref386832724\h圖12.3所示的NFAM為例，M的狀態(tài)是（NFAM），求正規(guī)式R，使L（R）=L（M）。第一步：加x和y結(jié)點(diǎn)，形成REF_Ref386833568\h圖12.7（a）所示的M′第二步：逐步消去M′的結(jié)點(diǎn)，消去1和3之后如REF_Ref386833568\h圖12.7(b)所示；再消去點(diǎn)2和4后如圖12.7（c）所示，最后只剩下x和y結(jié)點(diǎn)如REF_Ref386833568\h圖12.7（d）所示。R=（a|b）*(aa|bb)(a|b)*即為所求。圖STYLEREF1\s12.SEQ圖\*ARABIC\s17構(gòu)造正規(guī)式R問題：以上解決了從有窮自動機(jī)到正則式的轉(zhuǎn)換過程，假設(shè)一個(gè)選擇題，給了正則式，求A,B,C,D四個(gè)選項(xiàng)中，哪一個(gè)是對應(yīng)的有窮自動機(jī)？這種題目怎么解答？（把四個(gè)選項(xiàng)中有窮自動機(jī)的等價(jià)正規(guī)式求出，等于題目所給正規(guī)式即為答案）軟件設(shè)計(jì)師歷年真題2010年上半年●邏輯表達(dá)式“a∧b∨c∧(b∨x＞0)”的后綴式為（21）。（其中∧、∨分別表示邏輯與、邏輯或，＞表示關(guān)系運(yùn)算大于，對邏輯表達(dá)式進(jìn)行短路求值）（21）A.abcdx0＞∨∧∧∨B.ab∧c∨b∧x0＞∨C.ab∧cb∧x＞0∨∨D.ab∧cbx0＞∨∧∨●編譯程序?qū)語言源程序進(jìn)行語法分析時(shí)，可以確定（22）。（22）A.變量是否定義（或聲明）B.變量的值是否正確C.循環(huán)語句的執(zhí)行次數(shù)D.循環(huán)條件是否正確●程序的三種基本控制結(jié)構(gòu)是（33）。（33）A.過程、子程序和分程序B.順序、選擇和重復(fù)C.遞歸、堆棧和隊(duì)列D.調(diào)用、返回和跳轉(zhuǎn)●以下關(guān)于高級語言程序的編譯和解釋的敘述中，正確的是（48）。（48）A.編譯方式下，可以省略對源程序的詞法分析、語法分析B.解釋方式下，可以省略對源程序的詞法分析、語法分析C.編譯方式下，在機(jī)器上運(yùn)行的目標(biāo)程序完全獨(dú)立于源程序D.解釋方式下，在機(jī)器上運(yùn)行的目標(biāo)程序完全獨(dú)立于源程序●對于正規(guī)式0*（10*1）*0*，其正規(guī)集中字符串的特點(diǎn)是（50）。（50）A.開頭和結(jié)尾必須是0B.1必須出現(xiàn)偶數(shù)次C.0不能連續(xù)出現(xiàn)D.1不能連續(xù)出現(xiàn)2010年下半年●以下關(guān)于變量和常量的途述中，錯(cuò)誤的是（20）。（20）A.變量的取值在程序運(yùn)行過程中可以改變，常量則不行B.變量具有類型屬性，常量則沒有C.變量具有對應(yīng)的存儲單元，常量則沒有D.可以對變量賦值，不能對常量賦值?！窬幾g程序分析源程序的階段依次是（21）。（21）A.詞法分析、語法分析、語義分析B.語法分析、詞法分析、語義分析C.語義分析、語法分析、詞法分析D、語義分析、詞法分析、語法分析●下圖所示的有限自動機(jī)中，0是初始狀態(tài)，3是終止?fàn)顟B(tài)，該自動機(jī)可以識別（22）。（22）A.ababB.aaaaC.bbbbD.abba●以下關(guān)于可視化程序設(shè)計(jì)的敘述中，錯(cuò)誤的是（49）。（49）A.可視化程序設(shè)計(jì)使開發(fā)應(yīng)用程序無需編寫的程序代碼B.可視化程序設(shè)計(jì)基于面向?qū)ο蟮乃枷耄肓丝刂坪褪录?qū)動C.在可視化程序設(shè)計(jì)中，構(gòu)造應(yīng)用程序界面就像搭積木D.在可視化程序設(shè)計(jì)中，采用解釋方式可隨時(shí)查看程序的運(yùn)行效果?！褚韵玛P(guān)于匯編語言的途述中，錯(cuò)誤的是（50）。（50）A.匯編語言源程序中的指令語鋸將被翻譯成機(jī)器代碼B.匯編程序先將源程序中的偽指令翻譯成機(jī)器代碼，然后再翻譯指令語句C.匯編程序以匯編語言源程序?yàn)檩斎?，以機(jī)器語言表示的目標(biāo)程序?yàn)檩敵鯠:匯編語言的指令語句必須具有操作碼字段，可以沒有操作數(shù)字段2011年上半年●算術(shù)表達(dá)式采用逆波蘭式表示時(shí)不用括號，可以利用（20）進(jìn)行求值，與逆波蘭式abcd+*對應(yīng)的中綴表達(dá)式是（21）。（20）A.數(shù)組 B.棧 C.隊(duì)列 D.散列表（21）A.ab+c*d B.(ab)*c+d C.(ab)*(c+d) D.ab*c+d●若一種程序設(shè)計(jì)語言規(guī)定其程序中的數(shù)據(jù)必須具有類型，則有利于（22）。①在翻譯程序的過程中為合理分配存儲單元②對參與表達(dá)式計(jì)算的數(shù)據(jù)對象進(jìn)行檢查③定義和應(yīng)用動態(tài)數(shù)據(jù)結(jié)構(gòu)④規(guī)定數(shù)據(jù)對象的取值范圍及能夠進(jìn)行的運(yùn)算⑤對數(shù)據(jù)進(jìn)行強(qiáng)制類型轉(zhuǎn)換（22）A.①②③ B.①②④ C.②④⑤ D.③④⑤●以下關(guān)于高級程序設(shè)計(jì)語言翻譯的敘述中，正確的是（48）。（48）A.可以先進(jìn)行語法分析，再進(jìn)行詞法分析B.在語法分析階段可以發(fā)現(xiàn)程序中的所有錯(cuò)誤C.語義分析階段的工作與目標(biāo)機(jī)器的體系結(jié)構(gòu)密切相關(guān)D.目標(biāo)代碼生成階段的工作與目標(biāo)機(jī)器的體系結(jié)構(gòu)密切相關(guān)●下圖所示為一個(gè)有限自動機(jī)（其中，A是初態(tài)、C是終態(tài)），該自動機(jī)可識別（49）。（49）A.0000 B.1111 C.0101 D.1010●傳值與傳地址是函數(shù)調(diào)用時(shí)常采用的信息傳遞方式，（50）。（50）A.在傳值方式下，是將形參的值傳給實(shí)參B.在傳值方式下，形參可以是任意形式的表達(dá)式C.在傳地址方式下，是將實(shí)參的地址傳給形參D.在傳地址方式下，實(shí)參可以是任意形式的表達(dá)式2011年下半年●若C程序的表達(dá)式中引用了未賦初值的變量，則（20）。（20）A.編譯時(shí)一定會報(bào)告錯(cuò)誤信息，該程序不能運(yùn)行B.可以通過編譯并運(yùn)行，但運(yùn)行時(shí)一定會報(bào)告異常C.可以通過編譯，但鏈接時(shí)一定會報(bào)告錯(cuò)誤信息而不能運(yùn)行D.可以通過編譯并運(yùn)行，但運(yùn)行結(jié)果不一定是期望的結(jié)果●某程序設(shè)計(jì)語言規(guī)定在源程序中的數(shù)據(jù)都必須具有類型，然而，（28）并不是做出此規(guī)定的理由。（28）A.為數(shù)據(jù)合理分配存儲單元B.可以定義和使用動態(tài)數(shù)據(jù)結(jié)構(gòu)C.可以規(guī)定數(shù)據(jù)對象的取值范圍及能夠進(jìn)行的運(yùn)算D.對參與表達(dá)式求值的數(shù)據(jù)對象可以進(jìn)行合法性檢查●下圖所示為一個(gè)有限自動機(jī)（其中，A是初態(tài)、C是終態(tài)），該自動機(jī)識別的語言可用正規(guī)式（48）表示。（48）A.(0|1)*01 B.1*0*10*1 C.1*(0)*01 D.1*(0|10)*1*●函數(shù)t、f的定義如下所示，其中，a是整型全局變量。設(shè)調(diào)用函數(shù)t前a的值為5，則在函數(shù)t中以傳值調(diào)用（callbyvalue）方式調(diào)用函數(shù)f時(shí)，輸出為（49）；在函數(shù)t中以引用調(diào)用（callbyreference）方式調(diào)用函數(shù)f時(shí)，輸出為（50）。（49）A.12 B.16 C.20 D.24（50）A.12 B.16 C.20 D.242012年上半年●對于邏輯表達(dá)式“xandyornotz”，and、or、not分別是邏輯與、或、非運(yùn)算，優(yōu)先級從高到低為not、and、or，and、or為左結(jié)合，not為右結(jié)合，若進(jìn)行短路計(jì)算，則（20）。(20)A．x為真時(shí)，整個(gè)表達(dá)式的值即為真，不需要計(jì)算y和z的值B．x為假時(shí)，整個(gè)表達(dá)式的值即為假，不需要計(jì)算y和z的值C．x為真時(shí)，根據(jù)y的值決定是否需要計(jì)算z的值D．x為假時(shí)，根據(jù)y的值決定是否需要計(jì)算z的值●算術(shù)表達(dá)式x(y+c)*8的后綴式是(22)（一、+、*表示算術(shù)的減、加、乘運(yùn)算，運(yùn)算符的優(yōu)先級和結(jié)合性遵循慣例）。(22)A.xyc8十*B.xyc+8*C.xyc8*+D.xyc+8*●下圖所示為一個(gè)有限自動機(jī)（其中，A是初態(tài)、C是終態(tài)），該自動機(jī)所識別的字符串的特點(diǎn)是(48)。(48)A．必須以11結(jié)尾的0、1串B．必須以00結(jié)尾的0、1串C．必須以01結(jié)尾的0、1串D．必須以10結(jié)尾的O、1串●函數(shù)（過程）調(diào)用時(shí)，常采用傳值與傳地址兩種方式在實(shí)參與形參間傳遞信息。以下敘述中，正確的是(50)。(50)A．在傳值方式下，將形參的值傳給實(shí)參，因此，形參必須是常量或變量B．在傳值方式下，將實(shí)參的值傳給形參，因此，實(shí)參必須是常量或變量C．在傳地址方式下，將形參的地址傳給實(shí)參，因此，形參必須有地址D．在傳地址方式下，將實(shí)參的地址傳給形參，因此，實(shí)參必須有地址●編譯和解釋是實(shí)現(xiàn)高級程序設(shè)計(jì)語言翻譯的兩種基本形式。以下關(guān)于編譯與解釋的敘述中，正確的是(51)。(51)A．在解釋方式下，對源程序不進(jìn)行詞法分析和語法分析，直接進(jìn)行語義分析B．在解釋方式下，無需進(jìn)行詞法、語法和語義分析，而是直接產(chǎn)生源程序的目標(biāo)代碼C．在編譯方式下，必須進(jìn)行詞法、語法和語義分析，然后再產(chǎn)生源程序的目標(biāo)代碼D．在編譯方式下，必須先形成源程序的中間代碼，然后再產(chǎn)生與機(jī)器對應(yīng)的目標(biāo)代碼2012年下半年●可用于編寫?yīng)毩⒊绦蚝涂焖倌_本的語言是(20)。(20)A．PythonB．PrologC．JavaD．C#●語言L={ambn|m≥0;n≥1}的正規(guī)表達(dá)式是(21)。(21)A.aa*bb*B.a*bb*C.aa*b*D．a(chǎn)*b*●算術(shù)表達(dá)式(ab)*c+d的后綴式是(22)（一、+、*表示算術(shù)的減、加、乘運(yùn)算，運(yùn)算符的優(yōu)先級和結(jié)合性遵循慣例）。(22)A.abcd*+B.abcd*+C.abc*d+D.abcd*+●將高級語言源程序翻譯成目標(biāo)程序的是(48)。(48)A．解釋程序B．編譯程序C．鏈接程序D．匯編程序●在對程序語言進(jìn)行翻譯的過程中，常采用一些與之等價(jià)的中間代碼表示形式。常用的中間代碼表示不包括(49)。(49)A．樹B．后綴式C．四元式D．正則式●以下關(guān)于程序錯(cuò)誤的敘述中，正確的是(50)。(50)A．編譯正確的程序必然不包含語法錯(cuò)誤B．編譯正確的程序必然不包含語義錯(cuò)誤C．除數(shù)為0的錯(cuò)誤可以在語義分析階段檢查出來D．除數(shù)為0的錯(cuò)誤可以在語法分析階段檢查出來2013年上半年●以下關(guān)于解釋程序和編譯程序的敘述中，正確的是（20)。(20)A.編譯程序和解釋程序都生成源程序的目標(biāo)程序B.編譯程序和解釋程序都不生成源程序的目標(biāo)程序C.編譯程序生成源程序的目標(biāo)程序，解釋程序則不然D.編譯程序不生成源程序的目標(biāo)程序，而解釋程序反之●以下關(guān)于傳值調(diào)用與引用調(diào)用的敘述中，正確的是（21)。①在傳值調(diào)用方式下，可以實(shí)現(xiàn)形參和實(shí)參間雙向傳遞數(shù)據(jù)的效果②在傳值調(diào)用方式下，實(shí)參可以是變量，也可以是常量和表達(dá)式③在引用調(diào)用方式下，可以實(shí)現(xiàn)形參和實(shí)參間雙向傳遞數(shù)據(jù)的效果④在引用調(diào)用方式下，實(shí)參可以是變量，也可以是常量和表達(dá)式(21)A.①③B.①④C.②③D.②④●在對高級語言源程序進(jìn)行編譯的過程中，為源程序中變量所分配的存儲單元的地址屬于（22)。(22)A.邏輯地址B.物理地址C.接口地址D.線性地址●以下關(guān)于語言L={anbn|n>1}的敘述中，正確的是（48)。(48)A.可用正規(guī)式“aa*bb*”描述，但不能通過有限自動機(jī)識別B.可用正規(guī)式“ambm”表示，也可用有限自動機(jī)識別C.不能用正規(guī)式表示，但可用有限自動機(jī)識別D.不能用正規(guī)式表示，也不能通過有限自動機(jī)識別●編譯過程中，對高級語言程序語句的翻譯主要考慮聲明語句和可執(zhí)行語句。對聲明語句，主要是將所需要的信息正確地填入合理組織的（49)中；對可執(zhí)行語句，則是(50)。(49)A.符號表B.棧C.隊(duì)列D.樹(50)A.翻譯成機(jī)器代碼并加以執(zhí)行B.轉(zhuǎn)換成語法樹C.翻譯成中間代碼或目標(biāo)代碼D.轉(zhuǎn)換成有限自動機(jī)2013年下半年●程序運(yùn)行過程中常使用參數(shù)在函數(shù)（過程）間傳遞信息，引用調(diào)用傳遞的是實(shí)參的（20）。（20）A.地址 B.類型 C.名稱 D.值●已知文法G:S>A0|B1,A>S1|1,B>S0|0，其中S是開始符號，從S出發(fā)可以推導(dǎo)出（21）。（21）A.所有由0構(gòu)成的字符串 B.所有由1構(gòu)成的字符串 C.某些0和1個(gè)數(shù)相等的字符串 D.所有0和1個(gè)數(shù)不同的字符串●將高級語言程序翻譯為機(jī)器語言的過程中，常引入中間代碼，其好處是（48）。（48）A.有利于反編譯處理B.有利于進(jìn)行與機(jī)器無關(guān)的優(yōu)化C.今早發(fā)現(xiàn)語法錯(cuò)誤D.可以簡化語法和語義分析●對高級語言程序進(jìn)行編譯的過程中，有窮自動機(jī)（NFA或DFA）是進(jìn)行（49）的適當(dāng)工具。（49）A.詞法分析 B.語法分析 C.語義分析 D.出錯(cuò)處理●弱類型語言（動態(tài)類型語言）是指不需要進(jìn)行變量/對象類型聲明的語言。（50）屬于弱類型語言。（50）A.Java B.C/C++ C.Python D.C#2014年上半年●以下程序設(shè)計(jì)語言中，(20)更適合用來進(jìn)行動態(tài)網(wǎng)頁處理。（20）A.HTMLB．LISPC.PHPD.JAVA/C++●在引用調(diào)用方式下進(jìn)行函數(shù)調(diào)用是將(21)。（21）A．實(shí)參的值傳遞給形參B．實(shí)參的地址傳遞給形參C．形參的值傳遞給實(shí)參D．形參的地址傳遞給實(shí)參●編譯程序?qū)Ω呒壵Z言源程序進(jìn)行編譯的過程中，要不斷收集、記錄和使用源程序中一些相關(guān)符號的類型和特征等信息，并將其存入(22)中。（22）A．符號表B．哈希表C．動態(tài)查找表D．棧和隊(duì)列●設(shè)計(jì)操作系統(tǒng)時(shí)不需要考慮的問題是(23)。（23）A．計(jì)算機(jī)系統(tǒng)中硬件資源的管理B．計(jì)算機(jī)系統(tǒng)中軟件資源的管理C．用戶與計(jì)算機(jī)之間的接口D．語言編譯器的設(shè)計(jì)實(shí)現(xiàn)●以下關(guān)于實(shí)現(xiàn)高級程序設(shè)計(jì)語言的編譯和解釋方式的敘述中，正確的是(48)。（48）A．在編譯方式下產(chǎn)生源程序的目標(biāo)程序，在解釋方式下不產(chǎn)生B．在解釋方式下產(chǎn)生源程序的目標(biāo)程序，在編譯方式下不產(chǎn)生C．編譯和解釋方式都產(chǎn)生源程序的目標(biāo)程序，差別是優(yōu)化效率不同D．編譯和解釋方式都不產(chǎn)生源程序的目標(biāo)程序，差別在是否優(yōu)化●大多數(shù)程序設(shè)計(jì)語言的語法規(guī)則用(49)描述即可。（49）A．正規(guī)文法B．上下文無關(guān)文法C．上下文有關(guān)文法D．短語結(jié)構(gòu)文法●在某C/C++程序中，整型變量a的值為0且應(yīng)用在表達(dá)式“c=b/a”中，則最可能發(fā)生的情形是(50)。（50）A．編譯時(shí)報(bào)告有語法錯(cuò)誤B．編譯時(shí)報(bào)告有邏輯錯(cuò)誤C．運(yùn)行時(shí)報(bào)告有語法錯(cuò)誤D．運(yùn)行時(shí)產(chǎn)生異常2014年下半年●屬于面向?qū)ο?、解釋型程序設(shè)計(jì)語言的是(18)。(18)A.XMLB.PythonC.PrologD.C++●算術(shù)表達(dá)式“(ab)*(c+d)”的后綴式是(21)。(21)A.abcd+*B.abcd*+C.ab*cd+D.abc+d*●將高級語言源程序翻譯成機(jī)器語言程序的過程中常引入中間代碼。以下關(guān)于中間代碼的敘述中不正確的是(22)。(22)A.中間代碼不依賴于具體的機(jī)器B.使用中間代碼可提高編譯程序的可移植性C.中間代碼可以用樹或圖表示D.中間代碼可以用棧和隊(duì)列表示●對高級語言源程序進(jìn)行編譯的過程可以分為多個(gè)階段，分配寄存器的工作在(48)階段進(jìn)行。(48)A.詞法分析B.語法分析C.語義分析D.目標(biāo)代碼生成●以下關(guān)于下圖所示有限自動機(jī)的敘述中，不正確的是(49)。(49)A.該自動機(jī)識別的字符串中a不能連續(xù)出現(xiàn)B.該自動機(jī)識別的字符串中b不能連續(xù)出現(xiàn)C.該自動機(jī)識別的非空字符串必須以a結(jié)尾D.該自動機(jī)識別的字符串可以為空串●對于大多數(shù)通用程序設(shè)計(jì)語言，用(50)描述其語法即可。(50)A.正規(guī)文法B.上下文無關(guān)文法C.上下文有關(guān)文法D.短語結(jié)構(gòu)文法2015年上半年●以下關(guān)于程序設(shè)計(jì)語言的敘述中，錯(cuò)誤的是(20)。(20)A.程序設(shè)計(jì)語言的基本成分包括數(shù)據(jù)、運(yùn)算、控制和傳輸?shù)菳.高級程序設(shè)計(jì)語言不依賴于具體的機(jī)器硬件C.程序中局部變量的值在運(yùn)行時(shí)不能改變D.程序中常量的值在運(yùn)行時(shí)不能改變●對高級語言源程序進(jìn)行編譯或解釋的過程可以分為多個(gè)階段，解釋方式不包含(48)階段。(48)A.詞法分析B.語法分析C.語義分析D.目標(biāo)代碼生成●C程序中全局變量的存儲空間在(22)分配。(22)A.代碼區(qū)B.靜態(tài)數(shù)據(jù)區(qū)C.棧區(qū)D.堆區(qū)●某非確定的有限自動機(jī)(NFA)的狀態(tài)轉(zhuǎn)換圖如下圖所示(q0既是初態(tài)也是終態(tài))，與該NFA等價(jià)的確定的有限自動機(jī)(DFA)是(49)?！襁f歸下降分析方法是一種(50)方法。(50)A.自底向上的語法分析B.自上而下的語法分析C.自底向上的詞法分析D.自上而下的詞法分析●試題答案：(50)B【解析】本題考查編譯原理知識點(diǎn)。遞歸下降法(RecursiveDescentMethod)，是指對文法的每一非終結(jié)符號，都根據(jù)相應(yīng)產(chǎn)生式各候選式的結(jié)構(gòu)，為其編寫一個(gè)子程序(或函數(shù))，用來識別該非終結(jié)符號所表示的語法范疇。遞歸下降法是一種語法分析方法，下降即自上而下之意。本題選擇B選項(xiàng)。2015年下半年●編譯器和解釋器是兩種基本的高級語言處理程序。編譯器對高級語言源程序的處理過程可以劃分為詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等階段，其中（20）并不是每個(gè)編譯器都必需的。與編譯器相比，解釋器（21）。（20）A.詞法分析和語法分析B.語義分析和中間代碼生成C.中間代碼生成和代碼優(yōu)化D.代碼優(yōu)化和目標(biāo)代碼生成（21）A.不參與運(yùn)行控制，程序執(zhí)行的速度慢B.參與運(yùn)行控制，程序執(zhí)行的速度慢C.參與運(yùn)行控制，程序執(zhí)行的速度快D.不參與運(yùn)行控制，程序執(zhí)行的速度快●某程序運(yùn)行時(shí)陷入死循環(huán)，則可能的原因是程序中存在（48）。（48）A.詞法錯(cuò)誤B.語法錯(cuò)誤C.動態(tài)的語義錯(cuò)誤D.靜態(tài)的語義錯(cuò)誤●某非確定的有限自動機(jī)（NFA）的狀態(tài)轉(zhuǎn)換圖如下圖所示（q0既是初態(tài)也是終態(tài)）。以下關(guān)于該NFA的敘述中，正確的是（49）。（49）A.其可識別的0、1序列的長度為偶數(shù)B.其可識別的0、1序列中0與1的個(gè)數(shù)相同C.其可識別的非空0、1序列中開頭和結(jié)尾字符都是0D.其可識別的非空0、1序列中結(jié)尾字符是1●函數(shù)t()、f(