可做奧鵬院校所有作業(yè)，畢業(yè)論文，咨詢請?zhí)砑観Q：3230981406 微信：aopopenfd777
21春學(xué)期《數(shù)據(jù)結(jié)構(gòu)Ⅱ》在線平時(shí)作業(yè)1
試卷總分:100 得分:100
一、單選題 (共 20 道試題,共 100 分)
1.在圖采用鄰接表存儲時(shí)，求最小生成樹的 Prim 算法的時(shí)間復(fù)雜度為
A.O(n)
B.O(n+e)
C.O(n2)
D.O(n3)
2.已知一組關(guān)鍵字為{25,48,36,72,79,82,23,40,16,35}，其中每相鄰兩個(gè)為有序子序列。對這些子序列進(jìn)行一趟兩兩歸并的結(jié)果是
A..{25,36,48,72,23,40,79,82,16,35}
B..{25,36,48,72,16,23,40,79,82,35}
C..{25,36,48,72,16,23,35,40,79,82}
D..{16,23,25,35,36,40,48,72,79,82}
3.連通圖是指圖中任意兩個(gè)頂點(diǎn)之間
A.都連通的無向圖
B.都不連通的無向圖
C.都連通的有向圖
D.都不連通的有向圖
答案:A
4.數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲器內(nèi)的表示，稱為數(shù)據(jù)的
A.邏輯結(jié)構(gòu)
B.存儲結(jié)構(gòu)
C.線性結(jié)構(gòu)
D.非線性結(jié)構(gòu)
5.設(shè)順序存儲的線性表共有123個(gè)元素，按分塊查找的要求等分成3塊。若對索引表采用順序查找來確定塊，并在確定的塊中進(jìn)行順序查找，則在查找概率相等的情況下，分塊查找成功時(shí)的平均查找長度為
A.21
B.23
C.41
D.62
6.在待排關(guān)鍵字序列基本有序的前提下，效率最高的排序方法是
A.直接插入排序
B.快速排序
C.直接選擇排序
D.歸并排序
答案:A
7.已知廣義表LS=((a，b，c)，(d，e，f))，運(yùn)算head和tail函數(shù)取出元素e的運(yùn)算是
A.head(tail(LS))
B.tail(head(LS))
C.head(tail(head(tail(LS))))
D.head(tail(tail(head(LS))))
8.．用DFS遍歷一個(gè)無環(huán)有向圖，并在DFS算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是
A.逆拓?fù)溆行?br/>B.拓?fù)溆行?br/>C.無序的
D.A和B
答案:A
9.如果在數(shù)據(jù)結(jié)構(gòu)中每個(gè)數(shù)據(jù)元素只可能有一個(gè)直接前驅(qū)，但可以有多個(gè)直接后繼，則該結(jié)構(gòu)是
A.棧
B.隊(duì)列
C.樹
D.圖
10.在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系
A.不一定相同
B.都相同
C.都不相同
D.互為逆序
11.二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，其行下標(biāo)i=0，l，…，8，列下標(biāo)為j=1，2．…．10。設(shè)每個(gè)字符占一個(gè)字節(jié),若按行先存儲，元素A[8，5]的起始地址與A按列存儲時(shí)起始地址相同的元素是
A.A[8，5]
B.A[3，10]
C.A[5，8]
D.A[0，9]
12.若要在單鏈表中的結(jié)點(diǎn)p之后插入一個(gè)結(jié)點(diǎn)s，則應(yīng)執(zhí)行的語句是
A.s->next=p->next; p->next=s;
B.p->next=s; s->next=p->next;
C.p->next=s->next; s->next=p;
D.s->next=p; p->next=s->next;
答案:A
13.一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個(gè)數(shù)是
A.0
B.1
C.2
D.3
14.連通網(wǎng)的最小生成樹是其所有生成樹中
A.頂點(diǎn)集最小的生成樹
B.邊集最小的生成樹
C.頂點(diǎn)權(quán)值之和最小的生成樹
D.邊的權(quán)值之和最小的生成樹
15.若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是
A.1234
B.4132
C.4231
D.4213
16.為使平均查找長度達(dá)到最小,當(dāng)由關(guān)鍵字集合{05,11,21,25,37,40,41,62,84}構(gòu)建二叉排序樹時(shí),第一個(gè)插入的關(guān)鍵字應(yīng)為
A.5
B.37
C.41
D.62
17.若一個(gè)有向圖的鄰接距陣中,主對角線以下的元素均為零,則該圖的拓?fù)溆行蛐蛄?br/>A.一定存在
B.一定不存在
C.不一定存在
D.不確定
答案:A
18.若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則節(jié)省時(shí)間的存儲方式是
A.順序表
B.雙鏈表
C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表
D.單循環(huán)鏈表
答案:A
19.希爾排序的增量序列必須是
A.遞增的
B.隨機(jī)的
C.遞減的
D.非遞減的
20.對長度為n的關(guān)鍵字序列進(jìn)行堆排序的空間復(fù)雜度為
A.O（log2n）
B.O（1）
C.O（n）
D.O（n*log2n）
21春學(xué)期《數(shù)據(jù)結(jié)構(gòu)Ⅱ》在線平時(shí)作業(yè)2
試卷總分:100 得分:100
一、單選題 (共 20 道試題,共 100 分)
1.下列程序段 for(i=1;i<=n;i++) A[I,j]=0; 的時(shí)間復(fù)雜度是
A.O(1)
B.O(0)
C.O(1+n)
D.O(n)
2.以下數(shù)據(jù)結(jié)構(gòu)中，屬于線性結(jié)構(gòu)的是
A.廣義表
B.二叉樹
C.稀疏矩陣
D.串
答案:A
3.某二叉樹的先序序列和后序序列正好相反，則該二叉樹的特點(diǎn)一定是
A.空或只有一個(gè)結(jié)點(diǎn)
B.高度等于其結(jié)點(diǎn)數(shù)
C.任一結(jié)點(diǎn)無左孩子
D.任一結(jié)點(diǎn)無右孩子
4.在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q 和p之間插入結(jié)點(diǎn)s，則執(zhí)行操作
A.s->next=p->next;p->next=s;
B.s->next=p; q->next=s
C.q->next=s;s->next=p;
D.p->next=s;s->next=q;
5.在以單鏈表為存儲結(jié)構(gòu)的線性表中，數(shù)據(jù)元素之間的邏輯關(guān)系用
A.數(shù)據(jù)元素的相鄰地址表示
B.數(shù)據(jù)元素在表中的序號表示
C.指向后繼元素的指針表示
D.數(shù)據(jù)元素的值表示
6.已知一個(gè)散列表如圖所示，其散列函數(shù)為H(key)=key％11，采用二次探查法處理沖突，則下一個(gè)插入的關(guān)鍵字49的地址為
A.2
B.3
C.8
D.9
7.若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為
A.1和 5
B.2和4
C.4和2
D.5和1
8.引入二叉線索樹的目的是
A.加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度
B.為了能在二叉樹中方便的進(jìn)行插入與刪除
C.為了能方便的找到雙親
D.使二叉樹的遍歷結(jié)果唯一
答案:A
9.下面說法錯(cuò)誤的是
(1）算法原地工作的含義是指不需要任何額外的輔助空間
（2）在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法
（3）所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界
（4）同一個(gè)算法，實(shí)現(xiàn)語言的級別越高，執(zhí)行效率就越低
A.(1)
B.(1),(2)
C.(1),(4)
D.(3)
10.有關(guān)二叉樹下列說法正確的是
A.二叉樹的度為2
B.一棵二叉樹的度可以小于2
C.二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2
D.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2
11.按排序過程中依據(jù)的原則分類，快速排序?qū)儆?br/>A.插入類的排序方法
B.選擇類的排序方法
C.交換類的排序方法
D.歸并類的排序方法
12.若一棵二叉樹有11個(gè)葉子結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)是
A.10
B.11
C.12
D.15
答案:A
13.若在9階B-樹中插入關(guān)鍵字引起結(jié)點(diǎn)分裂，則該結(jié)點(diǎn)在插入前含有的關(guān)鍵字個(gè)數(shù)為
A.4
B.5
C.8
D.9
14.對于順序存儲的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為
A.O(n) O(n)
B.O(n) O(1)
C.O(1) O(n)
D.O(1) O(1)
15.判斷兩個(gè)串大小的基本準(zhǔn)則是
A.兩個(gè)串長度的大小
B.兩個(gè)串中首字符的大小
C.兩個(gè)串中大寫字母的多少
D.對應(yīng)的第一個(gè)不等字符的大小
16.已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為
A.DEBAFC
B.DEFBCA
C.DEBCFA
D.DEBFCA
17.在關(guān)鍵字序列(12，23，34，45，56，67，78，89，91)中二分查找關(guān)鍵字為45、89和12的結(jié)點(diǎn)時(shí)，所需進(jìn)行的比較次數(shù)分別為
A.4，4，3
B.4，3，3
C.3，4，4
D.．3，3，4
18.若采用孩子兄弟鏈表作為樹的存儲結(jié)構(gòu)，則樹的后序遍歷應(yīng)采用二叉樹的
A.層次遍歷算法
B.前序遍歷算法
C.中序遍歷算法
D.后序遍歷算法
19.如果在排序過程中，每次均將一個(gè)待排序的記錄按關(guān)鍵字大小加入到前面已經(jīng)有序的子表中的適當(dāng)位置，則該排序方法稱為
A.插入排序
B.歸并排序
C.冒泡排序
D.堆排序
答案:A
20.將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是
A.n
B.2n-1
C.2n
D.n-1
答案:A
21春學(xué)期《數(shù)據(jù)結(jié)構(gòu)Ⅱ》在線平時(shí)作業(yè)3
試卷總分:100 得分:100
一、單選題 (共 20 道試題,共 100 分)
1.深度為h的滿m叉樹的第k層的結(jié)點(diǎn)(1=<k=<h)數(shù)有
A.mk-1
B.mk-1
C.mh-1
D.mh-1
答案:A
2.數(shù)據(jù)結(jié)構(gòu)中所定義的數(shù)據(jù)元素，是用于表示數(shù)據(jù)的
A.最小單位
B.最大單位
C.基本單位
D.不可分割的單位
3.希爾排序的增量序列必須是
A.遞增的
B.隨機(jī)的
C.遞減的
D.非遞減的
4.在關(guān)鍵字序列(12，23，34，45，56，67，78，89，91)中二分查找關(guān)鍵字為45、89和12的結(jié)點(diǎn)時(shí)，所需進(jìn)行的比較次數(shù)分別為
A.4，4，3
B.4，3，3
C.3，4，4
D.．3，3，4
5.下列序列中，不構(gòu)成堆的是
A.（1，2，5，3，4，6，7，8，9，10）
B.（10，5，8，4，2，6，7，1，3）
C.（10，9，8，7，3，5，4，6，2）
D.（1，2，3，4，10，9，8，7，6，5）
6.若有序表的關(guān)鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在二分查找關(guān)鍵字b的過程中，先后進(jìn)行比較的關(guān)鍵字依次為
A.f,c,b
B.f,d,b
C.g,c,b
D.g,d,b
答案:A
7.在下列各種文件中，不能進(jìn)行順序查找的文件是
A.順序文件
B.索引文件
C.散列文件
D.多重表文件
8.帶行表的三元組表是稀疏矩陣的一種
A.順序存儲結(jié)構(gòu)
B.鏈?zhǔn)酱鎯Y(jié)構(gòu)
C.索引存儲結(jié)構(gòu)
D.散列存儲結(jié)構(gòu)
答案:A
9.在一個(gè)單鏈表中，若刪除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行操作
A.q=p->next;p->next=q->next;free(q);
B.p=p->next;p->next=p->next->next;free(p);
C.p->next=q->next;free(p->next);
D.p=p->next->next;free(p->next);
答案:A
10.用二叉鏈表表示具有n個(gè)結(jié)點(diǎn)的二叉樹時(shí)，值為空的指針域的個(gè)數(shù)為
A.n-1
B.n
C.n+l
D.2n
11.已知含10個(gè)結(jié)點(diǎn)的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成功的平均查找長度等于
A.1.0
B.2.9
C.3.4
D.5.5
12.一個(gè)有向無環(huán)圖的拓?fù)渑判蛐蛄惺?br/>A.一定唯一的
B.一定不唯一的
C.不一定唯一的
D.都不對
13.用有向無環(huán)圖描述表達(dá)式(A+B)*((A+B)/A)，至少需要頂點(diǎn)的數(shù)目為
A.5
B.6
C.8
D.9
答案:A
14.若一個(gè)有向圖的鄰接距陣中,主對角線以下的元素均為零,則該圖的拓?fù)溆行蛐蛄?br/>A.一定存在
B.一定不存在
C.不一定存在
D.不確定
答案:A
15.在目標(biāo)串T［0..n-1］=″xwxxyxy″中，對模式串P［0..m-1］=″xy″進(jìn)行子串定位操作的結(jié)果是
A.1
B.2
C.3
D.5
16.數(shù)據(jù)的不可分割的最小標(biāo)識單位是
A.數(shù)據(jù)項(xiàng)
B.數(shù)據(jù)記錄
C.數(shù)據(jù)元素
D.數(shù)據(jù)變量
答案:A
17.如果求一個(gè)連通圖中以某個(gè)頂點(diǎn)為根的高度最小的生成樹，應(yīng)采用
A.深度優(yōu)先搜索算法
B.廣度優(yōu)先搜索算法
C.求最小生成樹的prim算法
D.拓?fù)渑判蛩惴?br/>
18.已知循環(huán)隊(duì)列的存儲空間為數(shù)組data[21]，且當(dāng)前隊(duì)列的頭指針和尾指針的值分別為8和3，則該隊(duì)列的當(dāng)前長度為
A.5
B.6
C.16
D.17
19.n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有
A.n-1條有向邊
B.n條有向邊
C.n(n-1)/2條有向邊
D.n(n-1)條有向邊
20.下列陳述中正確的是
A.二叉樹是度為2的有序樹
B.二叉樹中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無左右之分
C.二叉樹中必有度為2的結(jié)點(diǎn)
D.二叉樹中最多只有兩棵子樹，并且有左右之分
