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

1、軟件技術(shù)基礎(chǔ)得分評卷人班級姓名一、填空題（每空1分，共25分）成績1. 數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科，主要研究數(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ù)組的大小應(yīng)設(shè)為。6. 按照二叉樹的定義，具有3個結(jié)點的二叉樹形態(tài)有

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

3、D, R）描述的數(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.二、選擇題（每小題1分，共10分）已知：int x;下列語句正確的是（B. int *p=x;A. i nt *p=&x;2.3.C. int p=&x;D. i nt *p=*x;int a =1,2,3,4,5,b5,*p;則下列語句中不正確的語句是（A. p=b

4、+1;B.p=&a3;C. p=a;D.b=a;設(shè)有以下說明語句C. retur n (no de1+ no de2);D. scanf( %d %f ”,nodel);4.線性鏈表不具有的特點是（A.可隨機訪問任一個結(jié)點B 不必事先估計所需存儲空間大小C.插入與刪除時不必移動元素D 所需空間與線性表長度成正比5.若讓元素1 , 2, 3依次進棧,則出棧次序不可能出現(xiàn)（）種情況。structnodeint a; float b; ;struct nodeno de1, no de2,*p node;則下列語句中正確是（B. pnode.a=10 ;A.node1=node2 ;C. 3

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

6、next; st next =p ; D . qt next =s ; st next =p ;9. 如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時（）。A 必須判別棧是否滿B對棧不作任何判別C.必須判別棧是否空D判別棧元素的類型10. 設(shè)單鏈表中指針p指著結(jié)點A，若要刪除A之后的結(jié)點（若存在），則需要修改指針操作為（ ）。B . p=p->nextD . p->next=p）條邊才能確保是一個連通圖。B. 7D. 5A. p->next=p->next->nextC. p=p->next->next11. 具有 6 個頂點的無向圖至少需要（A. 6C. 4

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

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

9、ot;search ing success! n ”);return(mid);else if(smid <k) elseprintf(” searchi ng 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.設(shè)有一個帶頭結(jié)點的單鏈表，表中各數(shù)據(jù)元素為無序的正整數(shù)，編寫下列2 個函數(shù)。( 10 分)(1) node *find_m

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

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

12、18第三趟：3，12，24，45，1，18第四趟：1，3，12，24，45，18第五趟：1，3，12，18，24，45四，程序題（ 5 分）1，下面是實現(xiàn)二分查找算法的函數(shù)，試將其補充完整。high=n-1; low<=high mid=(low+high)/2; low=mid+ high=mid-1; 2，typedef struct int data 10;int num ; listtype ;void dellist(listtype *L ， int x); /* 刪除函數(shù)聲明 */main( ) listtype list=78 ，91，66， 95，35，88，52，10

13、0,*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 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!=NULL)if(p->data<min)t