1、軟件技術(shù)基礎系 班級 姓名 成績 得分評卷人一、填空題（每空1分，共25分）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個結(jié)點的二

2、叉樹形態(tài)有 種；具有65個結(jié)點的完全二叉樹其深度為 ; 深度為10的完全二叉樹最多有 個結(jié)點7. 在長度為n的順序表的第i個位置上插入一個元素，元素的移動次數(shù)為 ；刪除第i個元素時，需要從前向后依次前移 個元素。(1in+1)8. 順序存儲結(jié)構(gòu)的循環(huán)隊列中，設front 和rear分別為隊頭和隊尾指示器，該隊列中能存放的最大元素的個數(shù)為MAX-1，則判斷隊列為滿的條件為 ，而判斷隊列為空的條件是 。9. 設D=A，B，C，D，E，R=，結(jié)構(gòu)（D，R）描述的數(shù)據(jù)結(jié)構(gòu)是 。10. 系統(tǒng)出現(xiàn)死鎖一定是同時保持了 ， ， 和環(huán)路條件這四個必要條件。11. 操作系統(tǒng)通過 記載、跟蹤、控制進程的執(zhí)行，它是

3、進程存在的唯一標志。作業(yè)調(diào)度程序是從處于 狀態(tài)的作業(yè)中選取一個作業(yè)并把它裝入主存。12A.軟件生命周期瀑布模型一般可分為問題分析、 、 、 和軟件維護五個階段。,得分評卷人二、選擇題（每小題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=a; D.b=a; 3. 設有以下說明語句struct node int a；float b；stru

4、ct node node1,node2,*pnode;則下列語句中正確是（ ）。A. node1=node2； B. pnode.a=10； C. return (node1+node2)； D. scanf(“%d %f”,node1);4. 線性鏈表不具有的特點是（ ）。A. 可隨機訪問任一個結(jié)點B不必事先估計所需存儲空間大小C. 插入與刪除時不必移動元素D所需空間與線性表長度成正比5. 若讓元素1，2，3依次進棧，則出棧次序不可能出現(xiàn)（ ）種情況。A3，2，1 B2，1，3C3，1，2 D1，3，26. 有向圖的鄰接表中，頂點Vi的出度是（ ）。A. 依附于Vi的弧數(shù) B.Vi鏈表中的鄰

5、接結(jié)點個數(shù)C. Vi在表結(jié)點中出現(xiàn)的次數(shù) D. Vi度的一半7. 某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹。A空或只有一個結(jié)點B深度等于其結(jié)點數(shù)C任一分支結(jié)點均無左子樹D任一分支結(jié)點均無右子樹8. 在一個單鏈表中,若指針p指向某一結(jié)點，指針q指向p的前驅(qū)結(jié)點，要在q與p之間插入一個由s所指的結(jié)點，則執(zhí)行（ ）。Asnext=pnext；pnext=s；Bpnext =s；snext =q；Cpnext =snext；snext =p；Dqnext =s；snext =p；9. 如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時（ ）。A必須判別棧是否滿B對棧不作任何判別C必須

6、判別棧是否空D判別棧元素的類型10. 設單鏈表中指針p指著結(jié)點A，若要刪除A之后的結(jié)點（若存在），則需要修改指針操作為（ ）。A. p-next=p-next-next Bp=p-nextCp=p-next-nextDp-next=p11. 具有6個頂點的無向圖至少需要（ ）條邊才能確保是一個連通圖。A. 6B7C4D512. 對線性表進行二分查找時，要求線性表必須滿足（ ）。 A、以順序方式存儲 B、以鏈接方式存儲C、以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列 D、以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排列13. 對于進程的描述，下列說法錯誤的是（ ）。A一個進程可以包含若干個程序 B. 一個程序可

7、能被多個進程執(zhí)行C一個程序僅對應一個進程 D.進程是程序的一次執(zhí)行過程14. 臨界區(qū)是指并發(fā)進程中訪問共享變量的（ ）段。 A.管理信息 B.信息存儲 C.數(shù)據(jù) D.程序15. 若當前進程因時間片用完而讓出處理機時，該進程應轉(zhuǎn)變?yōu)椋?）狀態(tài)。A、執(zhí)行 B、就緒 C、阻塞 D、喚醒得分評卷人二、簡答題（ 每題5分，共20分）1 . 軟件設計的任務是什么？分為哪幾個步驟？每個步驟的任務是什么？ 2. 用簡單插入排序法，對關(guān)鍵字值序列為：12，3，24，45，1，18按從小到大的順序進行排列，試寫出每趟排序的結(jié)果。（5分）3.已知一棵二叉樹的中序遍歷結(jié)果為DBHEAFICG，先序遍歷結(jié)果為ABDEH

8、CFIG，請畫出該二叉樹，并寫出實現(xiàn)步驟。(5分)4. 給出下面有向圖的鄰接矩陣。（5分）得分評卷人四、程序題（共40分）1.程序填空（5分）下面是實現(xiàn)二分查找算法的函數(shù)，試將其補充完整。int binsearch(int s ,int k,int n) int low,high,mid; low=0; while( ) if(smid =k) printf(searching success! n ); return(mid); else if(smid k) else printf( searching failed! n ); return(-1); 2.已知一順序表L=78，91，66

9、，95，35，88，52，100，編寫一函數(shù)void dellist(listtype *L，int x)：刪除順序表L中第一個值小于x的元素，若該表中沒有小于x的元素則不作任何操作。（10分）3.設有一個帶頭結(jié)點的單鏈表，表中各數(shù)據(jù)元素為無序的正整數(shù)，編寫下列2個函數(shù)。（10分）（1）node *find_min_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é)點無后

10、繼結(jié)點或數(shù)據(jù)值為偶數(shù)，則不做任何操作；（5分）軟件技術(shù)基礎答案一，填空1，邏輯結(jié)構(gòu)； 數(shù)據(jù)操作集合 2， 鏈式 ； 順序 3，0 ；1 4，隊列 ；棧 5， 36 6， 5 ； 7 ； 1023 。 7， n-i+1 ； n-i 8， front = (rear + 1) % MAX ， front=rear 9， 圖 10， 互斥條件 ；部分分配條件；不可剝奪條件 11， pcb（進程控制塊）；后備 12. 軟件設計；編程實現(xiàn) ； 軟件測試 二，選擇ADAAC BBDCA DCCDB三，簡答題1， （1）軟件設計的任務是將需求分析階段獲得的需求說明書轉(zhuǎn)換為計算機中可實現(xiàn)的系統(tǒng)，完成系統(tǒng)的結(jié)構(gòu)

11、設計，包括數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)，最好得到軟件設計說明書。（2分）（2）軟件設計通?？煞譃閮蓚€步驟：概要設計和詳細設計。（1分）（3）概要設計完成軟件系統(tǒng)的模塊的劃分和模塊的層次結(jié)構(gòu)以及數(shù)據(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，45 3 4四，程序題（5分）1，下面是實現(xiàn)二分查找算法的函數(shù)，試將其補充完整。 high=n-1; lownum=8; scanf(“%d”,&x); de

12、llist(L,x); void dellist(listtype *L，int x)int i,j; for(i=0;inum;i+) if(L-dataix) for (j=i+1; jnum; j+) L-dataj-1=L-dataj; L-num-; break;3，typedef struct nodeint 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;mi