計算機二級棧的計算(計算機二級的)

1.計算機二級的基礎(chǔ)知識

二級公共基礎(chǔ)知識（填空題40道）（1） 算法的復雜度主要包括______復雜度和空間復雜度。

時間（2） 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的______。（3） 若按功能劃分，軟件測試的方法通常分為白盒測試方法和______測試方法。

答：黑盒（4） 如果一個工人可管理多個設(shè)施，而一個設(shè)施只被一個工人管理，則實體"工人"與實體"設(shè)備"之間存在______聯(lián)系。答：一對多#1:n#1:n(5) 關(guān)系數(shù)據(jù)庫管理系統(tǒng)能實現(xiàn)的專門關(guān)系運算包括選擇、連接和______。

答：投影（6） 在先左后右的原則下，根據(jù)訪問根結(jié)點的次序，二叉樹的遍歷可以分為三種：前序遍歷、______遍歷和后序遍歷。答：中序（7） 結(jié)構(gòu)化程序設(shè)計方法的主要原則可以概括為自頂向下、逐步求精、______和限制使用goto語句。

答：模塊化（8） 軟件的調(diào)試方法主要有：強行排錯法、______和原因排除法。答：回溯法（9） 數(shù)據(jù)庫系統(tǒng)的三級模式分別為______模式、內(nèi)部級模式與外部級模式。

答：概念#概念級（10） 數(shù)據(jù)字典是各類數(shù)據(jù)描述的集合，它通常包括5個部分，即數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流、______和處理過程。答：數(shù)據(jù)存儲（11） 設(shè)一棵完全二叉樹共有500個結(jié)點，則在該二叉樹中有______個葉子結(jié)點。

答：250(12) 在最壞情況下，冒泡排序的時間復雜度為______。答：n(n-1)/2#n*(n-1)/2#o(n(n-1)/2)#o(n*(n-1)/2)(13) 面向?qū)ο蟮某绦蛟O(shè)計方法中涉及的對象是系統(tǒng)中用來描述客觀事物的一個______。

答：實體（14） 軟件的需求分析階段的工作，可以概括為四個方面：______、需求分析、編寫需求規(guī)格說明書和需求評審。答：需求獲?。?5） ______是數(shù)據(jù)庫應用的核心。

答：數(shù)據(jù)庫設(shè)計（16） 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的______結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)。答：邏輯（17） 軟件工程研究的內(nèi)容主要包括：______技術(shù)和軟件工程管理。

答：軟件開發(fā)（18） 與結(jié)構(gòu)化需求分析方法相對應的是______方法。答：結(jié)構(gòu)化設(shè)計（19） 關(guān)系模型的完整性規(guī)則是對關(guān)系的某種約束條件，包括實體完整性、______和自定義完整性。

答：參照完整性（20） 數(shù)據(jù)模型按不同的應用層次分為三種類型，它們是______數(shù)據(jù)模型、邏輯數(shù)據(jù)模型和物理數(shù)據(jù)模型。答：概念（21） 棧的基本運算有三種：入棧、退棧和______。

答：讀棧頂元素#讀棧頂?shù)脑?讀出棧頂元素（22） 在面向?qū)ο蠓椒ㄖ?，信息隱蔽是通過對象的______性來實現(xiàn)的。答：封裝（23） 數(shù)據(jù)流的類型有______和事務型。

答：變換型（24） 數(shù)據(jù)庫系統(tǒng)中實現(xiàn)各種數(shù)據(jù)管理功能的核心軟件稱為______。答：數(shù)據(jù)庫管理系統(tǒng)#dbms(25) 關(guān)系模型的數(shù)據(jù)cao縱即是建立在關(guān)系上的數(shù)據(jù)cao縱，一般有______、增加、刪除和修改四種cao作。

答：查詢（26） 實現(xiàn)算法所需的存儲單元多少和算法的工作量大小分別稱為算法的 ______。答：空間復雜度和時間復雜度（27） 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 ______以及對數(shù)據(jù)的cao作運算。

答：存儲結(jié)構(gòu)（28） 一個類可以從直接或間接的祖先中繼承所有屬性和方法。采用這個方法提高了軟件的______。

答可重用性（29） 面向?qū)ο蟮哪Ｐ椭?，最基本的概念是對象?______。答：類（30） 軟件維護活動包括以下幾類：改正性維護、適應性維護、______維護和預防性維護。

答：完善性（31） 算法的基本特征是可行性、確定性、______和擁有足夠的情報。答：有窮性（32） 順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置______的存儲單元中。

答：相鄰（33） jackson結(jié)構(gòu)化程序設(shè)計方法是英國的m.jackson提出的，它是一種面向______的設(shè)計方法。答：數(shù)據(jù)結(jié)構(gòu)（34） 數(shù)據(jù)庫設(shè)計分為以下6個設(shè)計階段：需求分析階段、______、邏輯設(shè)計階段、物理設(shè)計階段、實施階段、運行和維護階段。

答：概念設(shè)計階段#數(shù)據(jù)庫概念設(shè)計階段（35） 數(shù)據(jù)庫保護分為：安全性控制 、______、并發(fā)性控制和數(shù)據(jù)的恢復。答：完整性控制（36） 測試的目的是暴露錯誤，評價程序的可靠性；而______的目的是發(fā)現(xiàn)錯誤的位置并改正錯誤。

答：調(diào)試（37） 在最壞情況下，堆排序需要比較的次數(shù)為______。答：o(nlog2n)(38) 若串s="program"，則其子串的數(shù)目是______。

答：29(39) 一個項目具有一個項目主管，一個項目主管可管理多個項目，則實體"項目主管"與實體"項目"的聯(lián)系屬于______的聯(lián)系。答：1對多#1:n(40) 數(shù)據(jù)庫管理系統(tǒng)常見的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和______三種。

答：關(guān)系模型。

2.二級公共基礎(chǔ)里面棧的定義和特點是什么

1.棧的基本概念 棧是限定只在一端進行插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。

當表中沒有元素時稱為空棧。棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。

棧是按照"先進后出"或"后進先出"的原則組織數(shù)據(jù)的。 2.棧的順序存儲及其運算 用一維數(shù)組S(1∶m)作為棧的順序存儲空間，其中m為最大容量。

在棧的順序存儲空間S(1∶m)中，S(bottom)為棧底元素，S(top)為棧頂元素。top=0表示?？?；top=m表示棧滿。

棧的基本運算有三種：入棧、退棧與讀棧頂元素。 （1）入棧運算：入棧運算是指在棧頂位置插入一個新元素。

首先將棧頂指針加一（即top加1），然后將新元素插入到棧頂指針指向的位置。當棧頂指針已經(jīng)指向存儲空間的最后一個位置時，說明棧空間已滿，不可能再進行入棧操作。

這種情況稱為棧"上溢"錯誤。 （2）退棧運算：退棧是指取出棧頂元素并賦給一個指定的變量。

首先將棧頂元素（棧頂指針指向的元素）賦給一個指定的變量，然后將棧頂指針減一（即top減1）。當棧頂指針為0時，說明?？?，不可進行退棧操作。

這種情況稱為棧的"下溢"錯誤。 （3）讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個指定的變量。

這個運算不刪除棧頂元素，只是將它賦給一個變量，因此棧頂指針不會改變。當棧頂指針為0時，說明?？?，讀不到棧頂元素。

麻煩采納，謝謝。

3.求計算機C語言中“?！钡幕靖拍?希望各個方面都有,全一點

棧，是硬件。

主要作用表現(xiàn)為一種數(shù)據(jù)結(jié)構(gòu)，是只能在某一端插入和刪除的特殊線性表。它按照后進先出的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）。

棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂（top），另一端為棧底（bottom）；棧底固定，而棧頂浮動；棧中元素個數(shù)為零時稱為空棧。

插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。 棧也稱為先進后出表。

?？梢杂脕碓诤瘮?shù)調(diào)用的時候存儲斷點，做遞歸時要用到棧！ 以上定義是在經(jīng)典計算機科學中的解釋。 在計算機系統(tǒng)中，棧則是一個具有以上屬性的動態(tài)內(nèi)存區(qū)域。

程序可以將數(shù)據(jù)壓入棧中，也可以將數(shù)據(jù)從棧頂彈出。在i386機器中，棧頂由稱為esp的寄存器進行定位。

壓棧的操作使得棧頂?shù)牡刂窚p小，彈出的操作使得棧頂?shù)牡刂吩龃蟆?棧在程序的運行中有著舉足輕重的作用。

最重要的是棧保存了一個函數(shù)調(diào)用時所需要的維護信息，這常常稱之為堆棧幀或者活動記錄。堆棧幀一般包含如下幾方面的信息： 1. 函數(shù)的返回地址和參數(shù) 2. 臨時變量：包括函數(shù)的非靜態(tài)局部變量以及編譯器自動生成的其他臨時變量。

二、基本算法 1、進棧（PUSH）算法 ①若TOP≥n時，則給出溢出信息，作出錯處理（進棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）； ②置TOP=TOP+1（棧指針加1，指向進棧地址）； ③S(TOP)=X，結(jié)束（X為新進棧的元素）； 2、退棧（POP）算法 ①若TOP≤0，則給出下溢信息，作出錯處理（退棧前先檢查是否已為空棧， 空則下溢；不空則作②）； ②X=S(TOP)，（退棧后的元素賦給X）： ③TOP=TOP-1，結(jié)束（棧指針減1，指向棧頂）。三、棧的實現(xiàn) 棧分順序棧和鏈式棧，下面程序介紹了順序棧的實現(xiàn)。

#include #include #define DataType int #define MAXSIZE 1024 typedef struct { DataType data[MAXSIZE]; int top; }SeqStack; SeqStack *Init_SeqStack（)//棧初始化 { SeqStack *s; s=(SeqStack *)malloc(sizeof(SeqStack)); if(!s) { printf（"空間不足\n"）; return NULL; } else { s->top=-1; return s; } } int Empty_SeqStack(SeqStack *s)//判?？?{ if(s->top==-1) return 1; else return 0; } int Push_SeqStack(SeqStack *s,DataType x)//入棧 { if(s->top==MAXSIZE-1) return 0；//棧滿不能入棧 else { s->top++; s->data[s->top]=x; return 1; } } int Pop_SeqStack(SeqStack *s,DataType *x)//出棧 { if(Empty_SeqStack(s)) return 0；//?？詹荒艹鰲?else { *x=s->data[s->top]; s->top--; return 1； }//棧頂元素存入*x，返回 } DataType Top_SeqStack(SeqStack *s)//取棧頂元素 { if(Empty_SeqStack(s)) return 0；//?？?else return s->data[s->top]; } int Print_SeqStack(SeqStack *s) { int i; printf（"當前棧中的元素：\n"）; for(i=s->top;i>=0;i--) printf("%3d",s->data[i]); printf("\n"); return 0; } int main() { SeqStack *L; int n,num,m; int i; L=Init_SeqStack(); printf（"初始化完成\n"）; printf（"棧空：%d\n",Empty_SeqStack(L)); printf（"請輸入入棧元素個數(shù)：\n"）; scanf("%d",&n); printf（"請輸入要入棧的%d個元素：\n",n）; for(i=0;i<n;i++) { scanf("%d",&num); Push_SeqStack(L,num); } Print_SeqStack(L); printf（"棧頂元素：%d\n",Top_SeqStack(L)); printf（"請輸入要出棧的元素個數(shù)（不能超過%d個）：\n",n); scanf("%d",&n); printf（"依次出棧的%d個元素：\n",n）; for(i=0;i<n;i++) { Pop_SeqStack(L,&m); printf("%3d",m); } printf("\n"); Print_SeqStack(L); printf（"棧頂元素：%d\n",Top_SeqStack(L)); return 0; }。