《軟件技術(shù)基礎(chǔ)試題及答案.doc》由會員分享，可在線閱讀，更多相關(guān)《軟件技術(shù)基礎(chǔ)試題及答案.doc（10頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

軟件技術(shù)基礎(chǔ) 系 班級 姓名 成績 得分 評卷人 一、填空題（每空1分，共25分） 1. 數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科，主要研究數(shù)據(jù)的 、存儲結(jié)構(gòu)以及 三方面內(nèi)容。 2. 當(dāng)對一個(gè)線性表經(jīng)常進(jìn)行插入或刪除操作時(shí)，則宜采用 存儲結(jié)構(gòu)；而經(jīng)常進(jìn)行的是訪問操作，而很少進(jìn)行插入或刪除操作時(shí)，則宜采用 存儲結(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)先順序壓縮存儲在一維數(shù)組中，則數(shù)組的大小應(yīng)設(shè)為 。 6. 按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹形態(tài)有 種；具有65個(gè)結(jié)點(diǎn)的完全二叉樹其深度為 ; 深度為10的完全二叉樹最多有 個(gè)結(jié)點(diǎn) 7. 在長度為n的順序表的第i個(gè)位置上插入一個(gè)元素，元素的移動次數(shù)為 ；刪除第i個(gè)元素時(shí)，需要從前向后依次前移 個(gè)元素。(1≤i≤n+1) 8. 順序存儲結(jié)構(gòu)的循環(huán)隊(duì)列中，設(shè)front 和rear分別為隊(duì)頭和隊(duì)尾指示器，該隊(duì)列中能存放的最大元素的個(gè)數(shù)為M AX-1，則判斷隊(duì)列為滿的條件為 ，而判斷隊(duì)列為空的條件是 。 9. 設(shè)D={A，B，C，D，E}，R={，，，}，結(jié)構(gòu)（D，R）描述的數(shù)據(jù)結(jié)構(gòu)是 。 10. 系統(tǒng)出現(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},b[5],*p; 則下列語句中不正確的語句是（ ）。 A. p=b+1; B.p=&a[3]; C. p=a; D.b=a; 3. 設(shè)有以下說明語句 struct node{ int a；float b；}； struct node node1,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ì)所需存儲空間大小 C. 插入與刪除時(shí)不必移動元素 D．所需空間與線性表長度成正比 5. 若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能出現(xiàn)（ ）種情況。 A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，2 6. 有向圖的鄰接表中，頂點(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í)行（ ）。 A．s→next=p→next；p→next=s； B．p→next =s；s→next =q； C．p→next =s→next；s→next =p； D．q→next =s；s→next =p； 9. 如果以鏈表作為棧的存儲結(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->next B．p=p->next C．p=p->next->next D．p->next=p 11. 具有6個(gè)頂點(diǎn)的無向圖至少需要（ ）條邊才能確保是一個(gè)連通圖。 A. 6 B．7 C．4 D．5 12. 對線性表進(jìn)行二分查找時(shí)，要求線性表必須滿足（ ）。 A、以順序方式存儲 B、以鏈接方式存儲 C、以順序方式存儲，且結(jié)點(diǎn)按關(guān)鍵字有序排列 D、以鏈接方式存儲，且結(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.信息存儲 C.數(shù)據(jù) D.程序 15. 若當(dāng)前進(jìn)程因時(shí)間片用完而讓出處理機(jī)時(shí)，該進(jìn)程應(yīng)轉(zhuǎn)變?yōu)椋? ）狀態(tài)。 A、執(zhí)行 B、就緒 C、阻塞 D、喚醒 得分 評卷人 二、簡答題（ 每題5分，共20分） 1 . 軟件設(shè)計(jì)的任務(wù)是什么？分為哪幾個(gè)步驟？每個(gè)步驟的任務(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(s[mid] ==k) { printf("searching success! \n "); return(mid); } else if(s[mid] num=8; scanf(“%d”,&x); dellist(L,x); } void dellist(listtype *L，int x) {int i,j; for(i=0;inum;i++) { if(L->data[i]num; j++) L->data[j-1]=L->data[j]; 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é)點(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->datadata; } p=p->next; } printf("min=%d\n",t->data); return t; } void switch_next_node(node *p) { node *q; int t; q=p->next; if(q==NULL || p->data%2==0) return; t=p->data; p->data=q->data; q->data=t; }