浙江省專升本2025年軟件工程專業(yè)實(shí)踐技能試卷（含答案）考試時(shí)間：______分鐘總分：______分姓名：______一、選擇題（本大題共10小題，每小題2分，共20分。在每小題列出的四個(gè)選項(xiàng)中，只有一項(xiàng)是最符合題目要求的，請將正確選項(xiàng)字母填在題后的括號內(nèi)。）1.下列關(guān)于棧的描述中，正確的是（）。A.棧是先進(jìn)先出（FIFO）的線性結(jié)構(gòu)B.棧具有插入和刪除操作，但只能在一端進(jìn)行C.棧具有插入和刪除操作，但只能在兩端進(jìn)行D.棧是一種邏輯結(jié)構(gòu)，但不是物理結(jié)構(gòu)2.在順序存儲的線性表中，插入一個(gè)元素時(shí)，最少需要移動的元素個(gè)數(shù)是（）。A.0B.1C.n（n為表長）D.n+13.下列數(shù)據(jù)結(jié)構(gòu)中，適合用來表示稀疏矩陣的是（）。A.順序表B.稀疏矩陣壓縮存儲（如三元組表）C.鏈棧D.二叉樹4.快速排序在最壞情況下的時(shí)間復(fù)雜度是（）。A.O(n)B.O(nlogn)C.O(n2)D.O(logn)5.下列關(guān)于線性鏈表的描述中，正確的是（）。A.鏈表中的元素在物理位置上必須連續(xù)B.鏈表必須有頭指針，但可以沒有尾指針C.鏈表必須有空指針域，但長度可以變化D.鏈表的插入和刪除操作需要移動元素6.在一棵二叉樹中，如果只有右子樹而沒有左子樹，則該二叉樹的后序遍歷序列與（）序列相同。A.前序遍歷B.中序遍歷C.層序遍歷D.以上都不相同7.下列關(guān)于數(shù)據(jù)庫的描述中，正確的是（）。A.關(guān)系模型中，每個(gè)元組都對應(yīng)一個(gè)屬性B.層次模型數(shù)據(jù)庫是非關(guān)系型數(shù)據(jù)庫C.數(shù)據(jù)庫三級模式結(jié)構(gòu)包括外模式、概念模式和內(nèi)模式D.SQL語言中，使用`INSERT`語句刪除數(shù)據(jù)8.下列關(guān)于操作系統(tǒng)的描述中，錯(cuò)誤的是（）。A.操作系統(tǒng)是系統(tǒng)軟件的核心B.進(jìn)程是資源分配的基本單位C.內(nèi)存管理主要解決內(nèi)存分配和回收問題D.操作系統(tǒng)提供了用戶與計(jì)算機(jī)硬件之間的接口9.下列關(guān)于計(jì)算機(jī)網(wǎng)絡(luò)協(xié)議的描述中，正確的是（）。A.TCP協(xié)議提供可靠的、面向連接的數(shù)據(jù)傳輸服務(wù)B.UDP協(xié)議提供可靠的、面向無連接的數(shù)據(jù)傳輸服務(wù)C.IP協(xié)議負(fù)責(zé)數(shù)據(jù)的路由選擇和傳輸D.HTTP協(xié)議工作在傳輸層10.在面向?qū)ο蟪绦蛟O(shè)計(jì)中，封裝的目的是（）。A.提高代碼的可重用性B.提高代碼的可維護(hù)性C.隱藏對象的內(nèi)部細(xì)節(jié)，僅對外暴露接口D.實(shí)現(xiàn)代碼的多態(tài)性二、填空題（本大題共5小題，每空2分，共20分。請將答案填寫在答題紙上對應(yīng)的位置。）1.在深度為5的二叉樹中，最多有______個(gè)結(jié)點(diǎn)。2.若一個(gè)棧的初始狀態(tài)為空，入棧序列為1,2,3,4,5，則出棧序列為______時(shí)，該棧的容量至少為______。3.對于給定的無向圖G=(V,E)，如果從頂點(diǎn)v出發(fā)到圖中其他所有頂點(diǎn)都只有一條路徑，則稱v為圖G的一個(gè)______頂點(diǎn)。4.在關(guān)系代數(shù)中，選擇操作用______符號表示，連接操作用______符號表示。5.在C/C++/Java等高級語言中，用于動態(tài)分配內(nèi)存的運(yùn)算符（或關(guān)鍵字）是______。三、簡答題（本大題共3小題，每小題6分，共18分。請將答案填寫在答題紙上對應(yīng)的位置。）1.簡述棧和隊(duì)列的主要區(qū)別。2.什么是算法？評價(jià)一個(gè)算法好壞的主要標(biāo)準(zhǔn)有哪些？3.簡述面向?qū)ο蟪绦蛟O(shè)計(jì)的三大基本特征（封裝、繼承、多態(tài)）及其含義。四、編程題（本大題共2小題，共42分。請將答案填寫在答題紙上對應(yīng)的位置。）1.（18分）閱讀以下C語言代碼段，回答問題。```c#include<stdio.h>#include<stdlib.h>typedefstructNode{intdata;structNode*next;}Node;voidprintList(Node*head){Node*p=head;while(p!=NULL){printf("%d",p->data);p=p->next;}printf("\n");}voiddeleteOdd(Nodehead){Node*p=*head;Node*prev=NULL;while(p!=NULL){if(p->data%2!=0){//如果數(shù)據(jù)為奇數(shù)if(prev==NULL){//刪除的是頭結(jié)點(diǎn)*head=p->next;free(p);p=*head;}else{//刪除的是中間或尾結(jié)點(diǎn)prev->next=p->next;free(p);p=prev->next;}}else{//數(shù)據(jù)為偶數(shù)prev=p;p=p->next;}}}intmain(){Node*head=(Node*)malloc(sizeof(Node));head->data=1;head->next=(Node*)malloc(sizeof(Node));head->next->data=2;head->next->next=(Node*)malloc(sizeof(Node));head->next->next->data=3;head->next->next->next=NULL;printf("Originallist:");printList(head);deleteOdd(&head);printf("Listafterdeletingoddnumbers:");printList(head);//釋放剩余鏈表內(nèi)存（假設(shè)有函數(shù)freeList實(shí)現(xiàn)）return0;}```問題：a.函數(shù)`deleteOdd`的功能是什么？b.在執(zhí)行`deleteOdd(&head);`后，鏈表`head`中剩余的結(jié)點(diǎn)數(shù)據(jù)是什么？c.函數(shù)`deleteOdd`在刪除結(jié)點(diǎn)時(shí)，如何處理被刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)`prev`？請說明刪除頭結(jié)點(diǎn)和刪除中間/尾結(jié)點(diǎn)時(shí)的處理方式有何不同。2.（24分）使用C語言編寫程序，實(shí)現(xiàn)以下功能：a.定義一個(gè)`Student`結(jié)構(gòu)體，包含學(xué)號（`charid[10]`）、姓名（`charname[20]`）和成績（`floatscore`）三個(gè)成員。b.聲明一個(gè)`Student`類型的數(shù)組`students`，用于存儲至少5個(gè)學(xué)生的信息。c.編寫一個(gè)函數(shù)`sortStudentsById`，該函數(shù)接收`Student`數(shù)組和數(shù)組的大小作為參數(shù)，根據(jù)學(xué)生的學(xué)號進(jìn)行升序排序。排序算法可以使用選擇排序或冒泡排序，請選擇其中一種實(shí)現(xiàn)。d.編寫一個(gè)`main`函數(shù)，在`main`函數(shù)中初始化`students`數(shù)組，包含至少5個(gè)學(xué)生的信息，調(diào)用`sortStudentsById`函數(shù)對數(shù)組進(jìn)行排序，最后打印排序后的學(xué)生信息（學(xué)號、姓名、成績）。每行打印一個(gè)學(xué)生的信息。---試卷答案一、選擇題1.B2.B3.B4.C5.C6.C7.C8.D9.A10.C二、填空題1.312.5,53.端點(diǎn)4.σ,?5.new(C++),malloc(C),allocate(Java)三、簡答題1.棧是先進(jìn)后出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，其操作受限只允許在棧頂進(jìn)行插入和刪除；隊(duì)列是先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，其操作受限只允許在隊(duì)尾進(jìn)行插入（enqueue）和在隊(duì)頭進(jìn)行刪除（dequeue）。棧常用于函數(shù)調(diào)用棧、表達(dá)式求值等；隊(duì)列常用于任務(wù)調(diào)度、消息隊(duì)列等場景。2.算法是指為解決特定問題而設(shè)計(jì)的一系列有限的、明確的指令序列。評價(jià)算法好壞的主要標(biāo)準(zhǔn)包括：正確性（算法能夠正確解決問題）、時(shí)間復(fù)雜度（算法執(zhí)行所需的時(shí)間隨輸入規(guī)模增長的變化趨勢）、空間復(fù)雜度（算法執(zhí)行所需的額外存儲空間隨輸入規(guī)模增長的變化趨勢）、可讀性和可維護(hù)性（算法代碼是否易于理解和修改）。3.封裝是指將數(shù)據(jù)（屬性）和操作數(shù)據(jù)的方法（行為）捆綁在一起，形成一個(gè)對象，并隱藏對象的內(nèi)部細(xì)節(jié)，只對外暴露有限的接口。繼承是指一個(gè)類（子類）可以繼承另一個(gè)類（父類）的屬性和方法，從而實(shí)現(xiàn)代碼復(fù)用和擴(kuò)展。多態(tài)是指同一個(gè)接口可以根據(jù)不同的對象而表現(xiàn)出不同的行為，通常通過方法重載（編譯時(shí)多態(tài)）和方法重寫（運(yùn)行時(shí)多態(tài)）實(shí)現(xiàn)。四、編程題1.a.函數(shù)`deleteOdd`的功能是從鏈表中刪除所有數(shù)據(jù)為奇數(shù)的結(jié)點(diǎn)。b.在執(zhí)行`deleteOdd(&head);`后，鏈表`head`中剩余的結(jié)點(diǎn)數(shù)據(jù)是2,4。c.函數(shù)`deleteOdd`在刪除結(jié)點(diǎn)時(shí)，通過一個(gè)前驅(qū)指針`prev`來追蹤當(dāng)前結(jié)點(diǎn)`p`的前一個(gè)結(jié)點(diǎn)。*刪除頭結(jié)點(diǎn)時(shí)（`p->data%2!=0`且`prev==NULL`）：直接將頭指針`*head`指向`head->next`，釋放原頭結(jié)點(diǎn)`p`的內(nèi)存，然后將`p`更新為新的頭結(jié)點(diǎn)`*head`，`prev`保持為`NULL`。*刪除中間或尾結(jié)點(diǎn)時(shí)（`p->data%2!=0`且`prev!=NULL`）：將`prev->next`指向`p->next`，釋放當(dāng)前結(jié)點(diǎn)`p`的內(nèi)存，然后將`p`更新為`prev->next`，`prev`保持不變。刪除尾結(jié)點(diǎn)時(shí)，`p`會最終變?yōu)閌NULL`。2.代碼實(shí)現(xiàn)如下：```c#include<stdio.h>#include<string.h>typedefstructStudent{charid[10];charname[20];floatscore;}Student;voidsortStudentsById(Studentstudents[],intsize){for(inti=0;i<size-1;i++){for(intj=0;j<size-1-i;j++){if(strcmp(students[j].id,students[j+1].id)>0){//交換兩個(gè)學(xué)生結(jié)點(diǎn)Studenttemp=students[j];students[j]=students[j+1];students[j+1]=temp;}}}}intmain(){Studentstudents[5]={{"S001","Alice",85.5},{"S003","Charlie",92.0},{"S002","Bob",78.0},{"S005","Eve",88.0},{"S004","Dave",95.5}};intsize=5;printf("Originalstudentinformation:\n");for(inti=0;i<size;i++){printf("ID:%s,Name:%s,Score:%.1f\n",students[i].id,students[i].name,students[i].score);}sortStudentsById(students,size);printf("\nSortedstudentinformationbyID:\n");for(inti=0;