軟件技術基礎試題及答案

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

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

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

4、 a; floatstruct node node1,node2則下列語句中正確是（A。 node1=node2 ;C. return (node1+node2) ;線性鏈表不具有的特點是（A?？呻S機訪問任一個結(jié)點Co插入與刪除時不必移動元素b；)oB.int * p=x;D. int *p= * x;則下列語句中不正確的語句是（BoD.b=a ;*pnode ;Dop= & a3;Bo pnode.a=10 ；scanf( %d%f”, node1 );B.不必事先估計所需存儲空間大小D.所需空間與線性表長度成正比若讓元素1 , 2,3依次進棧，則出棧次序不可能出現(xiàn)A. 3, 2,1

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

6、 =q ;C. p next =sfnext; s next =p ; D . qnext =s ; s-next =p ;9. 如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時（ ） 。A 必須判別棧是否滿B 對棧不作任何判別C.必須判別棧是否空D.判別棧元素的類型10. 設單鏈表中指針p 指著結(jié)點A ，若要刪除A 之后的結(jié)點（若存在）,則需要修改指針操作為（）.A 。 p->next=p >next- nextC p=p- next next11. 具有 6 個頂點的無向圖至少需要（A 。6C 412. 對線性表進行二分查找時，要求線性表必須滿足（A、以順序方式存儲C、 以順序方式存儲

7、， 且結(jié)點按關鍵字有序排列排列13. 對于進程的描述,下列說法錯誤的是（A 一個進程可以包含若干個程序C. 一個程序僅對應一個進程14. 臨界區(qū)是指并發(fā)進程中訪問共享變量的A 。管理信息Co數(shù)據(jù)15. 若當前進程因時間片用完而讓出處理機時，該進程應轉(zhuǎn)變?yōu)椋ˋ 、執(zhí)行B 、就緒B p=p- nextD p- next=p）條邊才能確保是一個連通圖。B 7D 5）。B 、以鏈接方式存儲D 、 以鏈接方式存儲,且結(jié)點按關鍵字有序）.B. 一個程序可能被多個進程執(zhí)行D 。進程是程序的一次執(zhí)行過程（）段。B 。信息存儲D. 程序該進程應轉(zhuǎn)變?yōu)椋–、阻塞）狀態(tài) .D 、喚醒第#頁，共10頁得分評卷人二、簡

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

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

10、，表中各數(shù)據(jù)元素為無序的正整數(shù)，編寫下列 2 個函數(shù)。 （ 10分）（ 1 ） node find_min_node（node h ） ：找出頭指針 h 指向的單鏈表中數(shù)據(jù)值最小的結(jié)點，打印該結(jié)點的數(shù)據(jù)值，并返回該結(jié)點指針； （5 分）第6頁，共10頁（ 2 ） void switch_next_node （ node *p） ：若指針 p 指向的結(jié)點數(shù)據(jù)值為奇數(shù)，則將該結(jié)點與其直接后繼結(jié)點的數(shù)值交換,若指針 p 指向的結(jié)點無后繼結(jié)點或數(shù)據(jù)值為偶數(shù)，則不做任何操作； （ 5分）第9頁，共10頁軟件技術基礎答案一，填空1,邏輯結(jié)構(gòu)；數(shù)據(jù)操作集合2,鏈式；順序 3, 0 ; 14,隊列；棧5, 3

11、66, 5 ; 7 ； 1023。7, n-i+1; ni8 , front =(rear + 1 ) % MAXfront=rear9,圖10,互斥條件；部分分配條件；不可剝奪條件11 , pcb （進程控制塊）；后備12。軟件設計；編程實現(xiàn) ；軟件測試第9頁共10頁ADAAC BBDCA DCCDB三,簡答題1 ,，完成系（1 ）軟件設計的任務是將需求分析階段獲得的需求說明書轉(zhuǎn)換為計算機中可實現(xiàn)的系統(tǒng)統(tǒng)的結(jié)構(gòu)設計，包括數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)，最好得到軟件設計說明書.（2分）（2）軟件設計通?？煞譃閮蓚€步驟：概要設計和詳細設計。（1分）（3）概要設計完成軟件系統(tǒng)的模塊的劃分和模塊的層次結(jié)構(gòu)以及數(shù)

12、據(jù)庫設計；詳細設計完成每個模塊的控制流程的設計。（2分）2.,第一趟：3, 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, 455 分）1 下面是實現(xiàn)二分查找算法的函數(shù)試將其補充完整。high=n 1 ； low<=high2,typedef struct int data 10; int num ; listtype ；void dellist(listtype *L ， int x) ； main ( ) lis

13、ttype list=78 ， 91， 66， 95， int x;L= list ；lnum=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 data j-1=L L- num- ； break;mid= ( low+high ) /2 ； low=mid+ high=mid 1；/* 刪除函數(shù)聲明 */35， 88 ， 52

14、 ， 100 L ；/* 初始化順序表*/data j 3，typedef struct node int data；struct node next ； node;void main()node *head,*p ；head=creat( ) ；/*創(chuàng)建單鏈表 /p=find_min_node ( head) ; /查找數(shù)據(jù)值最小的結(jié)點*/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 ！ =NUL