軟件技術(shù)基礎(chǔ)試題及答案

1、.軟件技術(shù)基礎(chǔ)系班級姓名成績得分評卷人一、填空題（每空1 分，共 25 分）1.數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科，主要研究數(shù)據(jù)的、存儲(chǔ)結(jié)構(gòu)以及三方面內(nèi)容。2.當(dāng)對一個(gè)線性表經(jīng)常進(jìn)行插入或刪除操作時(shí)，則宜采用存儲(chǔ)結(jié)構(gòu)；而經(jīng)常進(jìn)行的是訪問操作，而很少進(jìn)行插入或刪除操作時(shí)，則宜采用存儲(chǔ)結(jié)構(gòu)。3.在線性結(jié)構(gòu)中，首結(jié)點(diǎn)有個(gè)前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有個(gè)前驅(qū)結(jié)點(diǎn)。4.限定在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表稱為；限定在表的一端進(jìn)行插入和刪除運(yùn)算的線性表稱為。5. 一個(gè) 8 階的下三角矩陣B 按行優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組中，則數(shù)組的大小應(yīng)設(shè)為。6.按照二叉樹的定義，具有3 個(gè)結(jié)點(diǎn)的二叉樹形態(tài)有種；具有6

2、5 個(gè)結(jié)點(diǎn)的完全二叉樹其深度為; 深度為 10 的完全二叉樹最多有個(gè)結(jié)點(diǎn)7.在長度為 n 的順序表的第i 個(gè)位置上插入一個(gè)元素，元素的移動(dòng)次數(shù)為；刪除第 i 個(gè)元素時(shí)，需要從前向后依次前移個(gè)元素。 (1 i n+1)8. 順序存儲(chǔ)結(jié)構(gòu)的循環(huán)隊(duì)列中，設(shè)front 和 rear 分別為隊(duì)頭和隊(duì)尾指示器，該隊(duì)列中能存放的最大元素的個(gè)數(shù)為MAX-1 ，則判斷隊(duì)列為滿的條件為，而判斷隊(duì)列為空的條件是。9. 設(shè) D=A ，B ，C ，D， E ，R=<A ，B> ，<C ，D> ，<D ，B> ，<C ，E> ，結(jié)構(gòu)（ D，R ）描述的數(shù)據(jù)結(jié)構(gòu)是。10.系統(tǒng)

3、出現(xiàn)死鎖一定是同時(shí)保持了，和環(huán)路條件這四個(gè)必要條件。11.操作系統(tǒng)通過記載、跟蹤、控制進(jìn)程的執(zhí)行，它是進(jìn)程存在的唯一標(biāo)志。作業(yè)調(diào)度程序是從處于狀態(tài)的作業(yè)中選取一個(gè)作業(yè)并把它裝入主存。.12A. 軟件生命周期瀑布模型一般可分為問題分析、和軟件維護(hù)五個(gè)階段。,得分評卷人二、選擇題（每小題1 分，共 10 分）1.已知： int x;下列語句正確的是（）。A. int *p=&x;B. int *p=x;C. int p=&x;D. int *p=*x;2.int a =1,2,3,4,5,b5,*p;則下列語句中不正確的語句是（）。A. p=b+1;B.p=&a3;C. p

4、=a;D.b=a;3. 設(shè)有以下說明語句structnodeinta ； floatb； ；structnodenode1,node2,*pnode;則下列語句中正確是（）。A. node1=node2 ；B. pnode.a=10；C. return (node1+node2)；D. scanf( “%d %f ”,node1);4.線性鏈表不具有的特點(diǎn)是（）。A. 可隨機(jī)訪問任一個(gè)結(jié)點(diǎn)B 不必事先估計(jì)所需存儲(chǔ)空間大小C. 插入與刪除時(shí)不必移動(dòng)元素D 所需空間與線性表長度成正比5.若讓元素 1 ， 2， 3 依次進(jìn)棧，則出棧次序不可能出現(xiàn)（）種情況。A3，2，1B2，1，3C 3，1，2D1

5、，3，26.有向圖的鄰接表中，頂點(diǎn)Vi的出度是（）。A. 依附于 Vi 的弧數(shù)B.Vi 鏈表中的鄰接結(jié)點(diǎn)個(gè)數(shù)C. Vi 在表結(jié)點(diǎn)中出現(xiàn)的次數(shù)D. Vi度的一半7.某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A空或只有一個(gè)結(jié)點(diǎn)B 深度等于其結(jié)點(diǎn)數(shù).C任一分支結(jié)點(diǎn)均無左子樹D 任一分支結(jié)點(diǎn)均無右子樹8.在一個(gè)單鏈表中 ,若指針 p 指向某一結(jié)點(diǎn)，指針q 指向 p 的前驅(qū)結(jié)點(diǎn)，要在q 與 p 之間插入一個(gè)由 s 所指的結(jié)點(diǎn)，則執(zhí)行（）。As next=p next ； p next=s ；B p next =s ；s next =q ；C p next =s next ； s

6、 next =p ；D q next =s ； s next =p ；9.如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則出棧操作時(shí)（）。A必須判別棧是否滿B 對棧不作任何判別C必須判別棧是否空D 判別棧元素的類型10. 設(shè)單鏈表中指針 p 指著結(jié)點(diǎn) A，若要?jiǎng)h除 A 之后的結(jié)點(diǎn)（若存在） ，則需要修改指針操作為（）。A. p->next=p->next->nextB p=p->nextC p=p->next->nextD p->next=p11.具有 6個(gè)頂點(diǎn)的無向圖至少需要（）條邊才能確保是一個(gè)連通圖。A. 6B 7C 4D 512.對線性表進(jìn)行二分查找時(shí)，要求線性

7、表必須滿足（）。A、以順序方式存儲(chǔ)B 、以鏈接方式存儲(chǔ)C、以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列D 、以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列13.對于進(jìn)程的描述，下列說法錯(cuò)誤的是（）。A一個(gè)進(jìn)程可以包含若干個(gè)程序B. 一個(gè)程序可能被多個(gè)進(jìn)程執(zhí)行C一個(gè)程序僅對應(yīng)一個(gè)進(jìn)程D. 進(jìn)程是程序的一次執(zhí)行過程14.臨界區(qū)是指并發(fā)進(jìn)程中訪問共享變量的（）段。A.管理信息B. 信息存儲(chǔ)C. 數(shù)據(jù)D. 程序15.若當(dāng)前進(jìn)程因時(shí)間片用完而讓出處理機(jī)時(shí)，該進(jìn)程應(yīng)轉(zhuǎn)變?yōu)椋ǎ顟B(tài)。A、執(zhí)行B 、就緒C、阻塞D、喚醒.得分評卷人二、簡答題（每題 5 分，共 20 分）1 . 軟件設(shè)計(jì)的任務(wù)是什么？分為哪幾個(gè)步驟？每個(gè)步驟

8、的任務(wù)是什么？2. 用簡單插入排序法，對關(guān)鍵字值序列為： 12，3，24，45，1， 18 按從小到大的順序進(jìn)行排列，試寫出每趟排序的結(jié)果。 （ 5 分）3.已知一棵二叉樹的中序遍歷結(jié)果為 DBHEAFICG ，先序遍歷結(jié)果為 ABDEHCFIG ，請畫出該二叉樹，并寫出實(shí)現(xiàn)步驟。 (5 分 )4. 給出下面有向圖的鄰接矩陣。（ 5 分）.得分評卷人四、程序題（共40 分）1.程序填空（ 5 分）下面是實(shí)現(xiàn)二分查找算法的函數(shù)，試將其補(bǔ)充完整。int binsearch(int s ,int k,int n) int low,high,mid; low=0;while()if(smid =k)

9、printf("searching success! n "); return(mid);else if(smid <k)elseprintf(" searching failed! n ");return(-1);2.已知一順序表L=78 ， 91，66，95，35， 88， 52， 100 ，編寫一函數(shù)void dellist(listtype *L， int.x) ：刪除順序表L 中第一個(gè)值小于x 的元素，若該表中沒有小于x 的元素則不作任何操作。（ 10分）3.設(shè)有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，表中各數(shù)據(jù)元素為無序的正整數(shù)，編寫下列2 個(gè)函數(shù)。（

10、10 分）（ 1） node *find_min_node(node *h)：找出頭指針h 指向的單鏈表中數(shù)據(jù)值最小的結(jié)點(diǎn)，打印該結(jié)點(diǎn)的數(shù)據(jù)值，并返回該結(jié)點(diǎn)指針；（5 分）（ 2）void switch_next_node(node *p)：若指針 p 指向的結(jié)點(diǎn)數(shù)據(jù)值為奇數(shù)，則將該結(jié)點(diǎn)與其直接.后繼結(jié)點(diǎn)的數(shù)值交換，若指針p 指向的結(jié)點(diǎn)無后繼結(jié)點(diǎn)或數(shù)據(jù)值為偶數(shù)，則不做任何操作；（ 5分）軟件技術(shù)基礎(chǔ)答案.一，填空1，邏輯結(jié)構(gòu)；數(shù)據(jù)操作集合2， 鏈?zhǔn)?；順?， 0 ；14，隊(duì)列；棧5， 366， 5 ； 7 ； 1023 。7， n-i+1； n-i8 ， front = (rear + 1)

11、% MAX，front=rear9， 圖10， 互斥條件；部分分配條件；不可剝奪條件11 ， pcb （進(jìn)程控制塊） ；后備12. 軟件設(shè)計(jì)；編程實(shí)現(xiàn)； 軟件測試二，選擇ADAACBBDCADCCDB三，簡答題1 ，（ 1 ）軟件設(shè)計(jì)的任務(wù)是將需求分析階段獲得的需求說明書轉(zhuǎn)換為計(jì)算機(jī)中可實(shí)現(xiàn)的系統(tǒng)，完成系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)，包括數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)，最好得到軟件設(shè)計(jì)說明書。（2分）（ 2 ）軟件設(shè)計(jì)通?？煞譃閮蓚€(gè)步驟：概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。（ 1 分）（ 3 ）概要設(shè)計(jì)完成軟件系統(tǒng)的模塊的劃分和模塊的層次結(jié)構(gòu)以及數(shù)據(jù)庫設(shè)計(jì)；詳細(xì)設(shè)計(jì)完成每個(gè)模塊的控制流程的設(shè)計(jì)。（2 分）2.,第一趟： 3， 12 ，

12、24，45， 1， 18第二趟： 3， 12， 24 ，45， 1， 18第三趟： 3， 12， 24， 45， 1， 18第四趟： 1， 3， 12， 24， 45 ， 18第五趟： 1， 3， 12， 18， 24，4534四，程序題（5 分）.1，下面是實(shí)現(xiàn)二分查找算法的函數(shù)，試將其補(bǔ)充完整。high=n-1;low<=highmid=(low+high)/2;low=mid+high=mid-1;2，typedefstructintdata 10;intnum ; listtype ;void dellist(listtype *L，int x);/* 刪除函數(shù)聲明*/main(

13、 ) listtype list=78，91， 66， 95， 35，88， 52，100,*L;/*初始化順序表*/int x;L=&list;l->num=8;scanf(“ %d” ,&x);dellist(L,x);void dellist(listtype *L， int x)int i,j;for(i=0;i<L->num;i+) if(L->datai<x) for (j=i+1; j<l->num; j+)L->dataj-1=L->dataj;L->num-;break;3，typedef struct nodeintdata;structnode *next;node;void main()node *head,*p;head=creat( );/* 創(chuàng)建單鏈表 */p=find_min_node(head);/* 查找數(shù)據(jù)值最小的結(jié)點(diǎn)*/.switch_next_node(p);node *find_min_node(node *h)int min;node *p,*t;if(h=NULL)return NULL;p=h->next;t=NULL;min=p->data;while(p!=NULL)if(p->data<min)