電子科技大學(xué)-軟件技術(shù)基礎(chǔ)試題帶答案

1、得分一、填空題（共 20分，共10題，每空1分）存儲(chǔ)結(jié)構(gòu)，若經(jīng)常需要1 .若經(jīng)常需要對(duì)線性表進(jìn)行插入和刪除運(yùn)算，則最好采用鏈?zhǔn)綄?duì)線性表進(jìn)行查找運(yùn)算，則最好采用順序存儲(chǔ)結(jié)構(gòu)。2 .在操作過(guò)程中會(huì)出現(xiàn) “假溢出”現(xiàn)象的是順序隊(duì)列 結(jié)構(gòu)，解決此問(wèn)題的方法是采用循環(huán)對(duì)列。3.已知一棵二叉樹的順序存儲(chǔ)結(jié)構(gòu)為地址編號(hào)12345678910111213結(jié)點(diǎn)ABCDEFGH則元素G的父結(jié)點(diǎn)是 D4 .假定一個(gè)有向圖的頂點(diǎn)的集合為1,2,3,4,5,6,邊的集合為<1,2> , <1,3>, <2,5> , <3,2>, <3,4> ,<4,6&

2、gt;, <5,1>, <5,6>,則出度為2的頂點(diǎn)個(gè)數(shù)為 3,入度為1的頂點(diǎn)個(gè)數(shù)為 4。5 .二分查找算法適用于順序存儲(chǔ)的 數(shù)據(jù)結(jié)構(gòu)，且數(shù)據(jù)的組織應(yīng)該按查找的關(guān)鍵字有序。6 . 虛擬存儲(chǔ)方式分為：分頁(yè)存儲(chǔ) 、分段存儲(chǔ)、段頁(yè)存儲(chǔ) 。7 .用戶通過(guò)操作系統(tǒng)提供的命令接口、 系統(tǒng)調(diào)用、圖形用戶接口來(lái)使用計(jì)算機(jī)。8 .文件的物理結(jié)構(gòu)分為：連續(xù)、 鏈接、 索引 。9 .因特網(wǎng)是由許多大小 不同、類型不同的網(wǎng)絡(luò)互連而成。10 . 有表score （stuid, name,engish）,寫出查詢姓名和英語(yǔ)成績(jī)的查詢語(yǔ)句 Select name,English from score

3、11 .主建、選擇題（共30分，共30題，每題1分）1 .線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（A.必須是連續(xù)的B.部分地址必須是連續(xù)的C. 一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以2 .下面哪個(gè)結(jié)構(gòu)不是線性結(jié)構(gòu)（ B ）。A.隊(duì)列B.圖C線性表D.棧3 . 一個(gè)下圖所示的雙鏈表，定義 P為指針變量，則 P->next->next->.prior和P->prior->next指向的數(shù)據(jù)域的值分別是（ B ）A . 80 和 20B. 64 和 47 C. 64 和 20 D. 80 和 474 .在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（C

4、）倍。A. 1/2B. 1C. 2D. 45 . 一棵樹中，樹的的深度是（ A ）。A.結(jié)點(diǎn)的最大層次值B.子樹總的數(shù)目 C.結(jié)點(diǎn)的數(shù)目 D.結(jié)點(diǎn)子樹的最大數(shù)6 . 一棵二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，數(shù)組下標(biāo)從0開始，若存放某結(jié)點(diǎn)的數(shù)組元素下標(biāo)為11,則存放它的父結(jié)點(diǎn)的數(shù)組元素下標(biāo)為（C ）。A. 3B. 4 C. 5 D. 67 .對(duì)鏈?zhǔn)酱鎯?chǔ)的數(shù)據(jù)實(shí)現(xiàn)平均速度較快的查找，應(yīng)該將數(shù)據(jù)以（D ）形式存放。A.雙鏈表B.循環(huán)鏈表C.二叉鏈表D.二叉排序樹8 . 一個(gè)棧的入棧序列是a,b,c,d,e,且每個(gè)字符只進(jìn)棧一次，則棧的不可能的輸出序列是（C ）A. e,d,c,b,a B. d,e,c,b,aC

5、. d,c,e,a,bD. a,b,c,d,e9 . 一個(gè)所有非終端節(jié)點(diǎn)都有非空的左右子樹的二叉樹，葉子節(jié)點(diǎn)的個(gè)數(shù)為n,那么二叉樹上的節(jié)點(diǎn)總數(shù)為（D ）A,不確定 B. 2n C, 2n+1 D. 2n-110 .在排序算法中設(shè)置一個(gè)變量來(lái)記錄排序過(guò)程中是否有元素交換存放位置，從而可以提前結(jié)束排 序操作的是（ A ）。A.冒泡排序B.歸并排序C.簡(jiǎn)單插入排序D.簡(jiǎn)單選擇排序11 .進(jìn)程的狀態(tài)是可以轉(zhuǎn)換的，而以下哪個(gè)狀態(tài)轉(zhuǎn)換是不可能的（ c ）。A.就緒執(zhí)行B.執(zhí)行就緒C.等待執(zhí)行D.等待就緒12 .下面（d ）不是操作系統(tǒng)的特征。A.并發(fā)性B.共享性C.虛擬性D.確定性13 .臨界資源是（ b

6、 ）。A.以同步關(guān)系使用的共享資源B.以互斥關(guān)系使用的共享資源C.以共享關(guān)系使用的資源D.允許多個(gè)進(jìn)程使用的共享資源14 .進(jìn)程由程序塊、進(jìn)程控制塊和（ A ）三部分組成。A.數(shù)據(jù)塊8. 作業(yè)C.文件D.設(shè)備15 .作為編程人員，在程序設(shè)計(jì)中可以通過(guò)（ D ）獲得操作系統(tǒng)服務(wù)。A. 命令接口B.作業(yè)調(diào)度C.進(jìn)程調(diào)度D.系統(tǒng)調(diào)用16 .下面哪一種說(shuō)法對(duì)IP地址而言是正確的 CA.它恰好分為兩類B.它包含一個(gè)長(zhǎng)度固定的主機(jī)地址C.它是層次結(jié)構(gòu)的地址D.它有48比特長(zhǎng)17 .網(wǎng)絡(luò)中ARP的作用是在給定D 時(shí)找到A.域名，IP地址B.物理地址，IP地址C.IP地址，域名D.IP地址，物理地址18 .以

7、下哪種類型的尋址方式是專門為傳輸層所用的？CA.物理地址B.IP地址C.應(yīng)用程序端口D.A 和 B19 .域名解析實(shí)現(xiàn) BA.域名到物理地址的解析B.域名到IP地址的解析C. IP地址到物理地址的解析D. A 和 B20 .如果IP地址為22 ,則該工作站的子網(wǎng)掩碼可能為：CA. B. C. D. 4021 .在局域網(wǎng)中，計(jì)算機(jī)接收帶有如下地址的幀DA.目標(biāo)地址為廣播地址B.目標(biāo)地址為網(wǎng)絡(luò)地址C.目標(biāo)地址為該計(jì)算機(jī)硬件地址D. A和 C22 .以太網(wǎng)采用 D 來(lái)確定對(duì)傳輸介質(zhì)的控制

8、A.令牌B.優(yōu)先級(jí)C.先后次序D.載波偵聽沖突檢測(cè)23 .當(dāng)數(shù)據(jù)鏈路層將幀從一條鏈路發(fā)送到另一條鏈路時(shí)，它檢查 DA.主機(jī)地址B. IP地址C.域名D.物理地址24 .在數(shù)據(jù)管理技術(shù)的發(fā)展過(guò)程中，經(jīng)歷了人工管理階段，文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段。在這幾個(gè)階 段中，（C）是數(shù)據(jù)獨(dú)立性最高的階段A.人工B.文件系統(tǒng)C.數(shù)據(jù)庫(kù)系統(tǒng)D.數(shù)據(jù)項(xiàng)管理25 .數(shù)據(jù)庫(kù)中存儲(chǔ)的是 CA.數(shù)據(jù)B.數(shù)據(jù)模型C.數(shù)據(jù)以及數(shù)據(jù)之間的聯(lián)系D.信息26 .數(shù)據(jù)庫(kù)的特點(diǎn)之一是數(shù)據(jù)的共享，嚴(yán)格的講，這里的數(shù)據(jù)共享是指DA.同一個(gè)應(yīng)用中的多個(gè)程序共享一個(gè)數(shù)據(jù)集合B.多個(gè)用戶、同一種語(yǔ)言共享數(shù)據(jù)C.多個(gè)用戶共享一個(gè)數(shù)據(jù)文件D.多種

9、應(yīng)用、多種語(yǔ)言、多個(gè)用戶相互覆蓋地使用數(shù)據(jù)集合27 .關(guān)于數(shù)據(jù)庫(kù)系統(tǒng)的正確敘述AA.數(shù)據(jù)庫(kù)系統(tǒng)減少了數(shù)據(jù)冗余B.數(shù)據(jù)庫(kù)系統(tǒng)避免了一切冗余C.數(shù)據(jù)庫(kù)系統(tǒng)中數(shù)據(jù)的一致性是數(shù)據(jù)類型的一致D.數(shù)據(jù)庫(kù)系統(tǒng)比文件系統(tǒng)能管理更多的數(shù)據(jù)28 .數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）是：CA.數(shù)學(xué)軟件B.應(yīng)用軟件C.系統(tǒng)軟件D.操作系統(tǒng)的一部分29 .常見的數(shù)據(jù)模型有：DA.大型、中型、小型B.數(shù)據(jù)、圖形、多媒體C.西文、中文、兼容D.層次，網(wǎng)狀、關(guān)系30.下面那個(gè)協(xié)議是應(yīng)用層協(xié)議DA.B.IPTCPC.D.UDPHTTP操作。（5分）共36分）2.設(shè)單鏈表結(jié)點(diǎn)結(jié)構(gòu)定義如下，現(xiàn)要在單鏈表中刪除指針p所指結(jié)點(diǎn)的直接后繼（此結(jié)

10、點(diǎn)及其直接后繼均存在），給出各操作語(yǔ)句。（5分）2、3、4、5依次進(jìn)棧，在輸出端得到序列 32451,給出應(yīng)進(jìn)行的各入棧和出棧Push 1; push 2; push 3; pop 3; pop 2; push 4; pop 4; push 5; pop 5; pop 1 （每句 0.5 分）struct node int data;struct node *next;（1分）（1分）struct node *q;q=p->next;p->next=p->next->next;（2分）free（q）;（1分）先:中:后:3.給出下圖二叉樹的先序、2, 8, 12, 16

11、, 20,12, 16, 8, 20, 2,16, 12, 20, 8, 9,（每個(gè)2分）中序和后序遍歷序列，其中左右子樹的遍歷先左后右。13,13,10,32,9, 109, 32, 1032, 13, 2（6分）4.以關(guān)鍵字序列(53, 12, 80, 64, 32, 92, 17, 75, 45, 26)為例，寫出快速排序的各趟結(jié)果。（8分）26 , 12, 45, 17, 32 53 92, 75, 64, 8017 , 12 26 45, 32 53 80, 75, 64 9212, 17, 26, 32, 45, 53 64, 75 80 9212, 17, 26, 32, 45,

12、 53, 64, 75, 80, 92(每趟2分)5 .已知一個(gè)圖的邊集為 (1, 2), (1, 4), (1, 7), (2, 3), (2, 4), (3, 5), (3, 6), (4,5), (5, 8), (6, 8), (7, 8) ,畫出這張圖的鄰接矩陣和鄰接表結(jié)構(gòu)示意圖，并給出從 2開始的深度優(yōu)先和廣度優(yōu)先遍歷序列(鄰接點(diǎn)編號(hào)小的先訪問(wèn))。(8分)010 110 11010 0110 000 1100 1010 0 00 0 100 0 0 0110 010 0 00 0 0 10 0 0 10 0 0 18（2分）（2分）（2分）（2分）深度：2, 1, 4, 5, 3,

13、6, 8, 7廣度：2, 1, 3, 4, 7, 5, 6, 86 .已知有一組序列為（17 , 26 , 38 , 27 , 46 , 72 , 82 , 93 ）,設(shè)哈希表長(zhǎng) m=14 ,哈希函數(shù)H（key尸key%11。利用二次探測(cè)再散列處理沖突，建立哈希表。（4分）地址012345678910111213key4682263817277293（每個(gè)0.5分）四、編程題（共14分）對(duì)一個(gè)班級(jí)學(xué)生數(shù)學(xué)成績(jī)進(jìn)行管理：由給出的數(shù)據(jù)結(jié)構(gòu)和初始化的按數(shù)學(xué)成績(jī)遞增有序的成績(jī)表，編寫程序：1 .完成插入一個(gè)學(xué)生數(shù)據(jù)的函數(shù)，要求插入操作后學(xué)生數(shù)據(jù)依然遞增有序。（5分）要插入的學(xué)生數(shù)據(jù)為：studyid:

14、 21; name:王強(qiáng)；mathscore: 872 .完成主函數(shù) main:實(shí)現(xiàn)成績(jī)表數(shù)據(jù)的初始化（調(diào)用給出的初始化函數(shù)： initlist ）、實(shí)現(xiàn)成績(jī)表數(shù)據(jù)插入操作（調(diào)用第1題中編寫的函數(shù)）并輸出成績(jī)表中的所有數(shù)據(jù)。（9分）#include "string.h"#define STUDENTNUMBER 30/學(xué)生數(shù)據(jù)結(jié)構(gòu)typedef struct int studyid;char name10;float mathscore;STUDENT;/班級(jí)學(xué)生表結(jié)構(gòu)typedef structSTUDENT dataSTUDENTNUMBER;int num;listt

15、ype;/ 初始化班級(jí)學(xué)生表中數(shù)據(jù)void initlist(listtype *p) p->data0.studeyid=10;strcpy(p->," 李一 ");p->data0.mathscore=82;p->data1.studeyid=2;strcpy(p->," 張二 ");p->data1.mathscore=85;p->data2.studeyid=5;strcpy(p->," 趙三 ");p->data2.mathscore=88;/*班級(jí)中按數(shù)學(xué)成績(jī)遞增有序的學(xué)生總共有20位*/p->num=20;void charu(listtype *p, STUDENT x) int i;for(i=p->num-1;p->datai.mathscore>=x.mathscore;i-)p->datai+1=p->datai;p-datai+1=x;p