數(shù)據(jù)結(jié)構(gòu)期中考試含答案

一、單選題（共35題）

1、（2分）
一個(gè)棧的入棧序列是：a, b, c, d, e，則棧的不可能 的輸出序列是（ C ）。

A.edcba
B.decba
C.dceab
D.abcde

2、（2分）
建立一個(gè)含n個(gè)元素的單鏈表的時(shí)間復(fù)雜度是（ B ）。

A.O(1)
B.O(n)
C.O(n^2)
D.O(nlogn)

3、（2分）
下列序列中，不是線性表的是（ C ）。
A.（‘A’，‘B’，‘C’，‘D’，‘E’）
B.（‘AB’，‘CDE’）
C.（‘AB’，25，‘DE’）
D.（5，7，2，51，4）

4、（2分）
線性表L=(a₁，a₂,……a_n)，下列說法正確的是（ D ）。

A.每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼
B.表中諸元素的排列必須是由小到大或由大到小
C.線性表中至少有一個(gè)元素
D.除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。

5、（2分）
用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（　D ）。

A.僅修改頭指針
B.僅修改尾指針
C.頭、尾指針都要修改
D.頭、尾指針可能都要修改

6、（2分）
以下對(duì)數(shù)組的描述，正確的是（ C ）。

A.存取數(shù)組中各元素的時(shí)間各不相同
B.對(duì)數(shù)組元素可進(jìn)行訪問、插入和刪除操作
C.數(shù)組可看成是線性表的擴(kuò)展
D.數(shù)組各元素的數(shù)據(jù)類型可以不同

7、（2分）
設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧S，一個(gè)元素出棧后即進(jìn)入Q，若6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該是（　B ）。

A.2
B.3
C.4
D.6

8、（2分）
廣義表A=（a,b,(c,d),(e,(f,g))),則Head(Tail(Head(Tail(Tail(A)))))的值是（ C ）

A.（g)
B.(d)
C.d
D.c

9、（2分）
廣義表A=(a,b,(c,d),(e,(f,g)))，則Head(Tail(Head(Tail(Tail(A)))))的值為（ D ）。

A． (g)
B． (d)
C． c
D． d

10、（2分）
設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a₁₁為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a₈₅的地址為（ C ）。

A．13
B．32
C．33
D．40

11、（2分）
算法的時(shí)間復(fù)雜度與（ B ）有關(guān)。

A.程序設(shè)計(jì)語言
B.問題規(guī)模
C.計(jì)算機(jī)硬件性能
D.編譯程序質(zhì)量

12、（2分）
在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問任一點(diǎn)的存儲(chǔ)結(jié)構(gòu)是（ D ）。

A.單鏈表
B.雙向鏈表
C.循環(huán)鏈表
D.B和C

13、（2分）
若一個(gè)棧的進(jìn)棧序列為1，2，3，4，則合法 的出棧序列是（ C ）。

A.1，4，2，3
B.4，1，2，3
C.3，2，1，4
D.4，3，1，2

14、（2分）
從具有n個(gè)結(jié)點(diǎn)的單鏈表中查找值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，平均需比較（ D ）個(gè)結(jié)點(diǎn)。

A.n
B.n/2
C.(n-1)/2
D.(n+1)/2

15、（2分）
用雙向鏈表表示線性表時(shí)，較之單鏈表更容易進(jìn)行（ D ）。

A.結(jié)點(diǎn)的插入
B.結(jié)點(diǎn)的刪除
C.線性表的擴(kuò)充
D.對(duì)結(jié)點(diǎn)的訪問

16、（2分）
在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（ B ）。

A.p->prior=p->next->next; p->next=p->prior->prior;
B.p->next->prior=p->prior; p->prior->next=p->next;
C.p->next=p->next->next; p->next->prior=p;
D.p->prior->next=p; p->prior=p->prior->prior;

17、（2分）
在下面各種鏈表結(jié)構(gòu)中，能在O(1)時(shí)間內(nèi)完成在指定結(jié)點(diǎn)P之前插入元素X的結(jié)構(gòu)是（ D ）。

A.不帶表頭的單鏈表
B.單向循環(huán)鏈表
C.帶表頭結(jié)點(diǎn)的單鏈表
D.雙向循環(huán)鏈表

18、（2分）
若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（ C ）種情況。

A.5，4，3，2，1
B.2，1，5，4，3
C.4，3，1，2，5
D.2，3，5，4，1

19、（2分）
設(shè)廣義表L=((a,b,c))，則L的長(zhǎng)度和深度分別為（ C ）。

A．1和1
B．1和3
C．1和2
D．2和3

20、（2分）
在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ B ）。

A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)
B.線性結(jié)構(gòu)和非線性結(jié)構(gòu)
C.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

21、（2分）
以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是（ C ）。

A.順序隊(duì)列
B.鏈表
C.有序表
D.鏈棧

22、（2分）
一個(gè)隊(duì)列的輸入序列是1,2,3,4，則隊(duì)列的輸出序列是（ D ）。

A.3,2,4,1
B.4,3,2,1
C.1,4,3,2
D.1,2,3,4

23、（2分）
鏈?zhǔn)綏＝Y(jié)點(diǎn)為：(data,link)，top指向棧頂.若想摘除棧頂結(jié)點(diǎn)，并將刪除結(jié)點(diǎn)的值保存到x中,則應(yīng)執(zhí)行操作（ A ）。

A.x=top->data;top=top->link；
B.top=top->link;x=top->link；
C.x=top;top=top->link；
D.x=top->link；

24、（2分）
串下面關(guān)于串的的敘述中，（ B ）是不正確的？

A．串是字符的有限序列
B．空串是由空格構(gòu)成的串
C．模式匹配是串的一種重要運(yùn)算
D．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)

25、（2分）
在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的操作是（ C ）。

A.p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;
B.q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;
C.q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;
D.p->next=q; q->prior=p; p->next->prior=q; q->next=q;

26、（2分）
線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（ A ）的存儲(chǔ)結(jié)構(gòu)。

A.隨機(jī)存取
B.鏈?zhǔn)酱嫒?br /> C.索引存取
D.散列存取

27、（2分）
如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，在出棧操作時(shí)，則（ C ）。

A.必須判斷棧是否滿
B.不需要判斷棧是否空
C.必須判斷棧是否空
D.對(duì)棧不作任何判別

28、（2分）
數(shù)組A[0…4,-3…-1,5…7]中含有元素的個(gè)數(shù)（ B ）。

A．55
B．45
C．36
D．16

29、（2分）
設(shè)有一個(gè)遞歸算法如下
int fact(int n) { //n大于等于0
if(n<=0) return 1;
else return n*fact(n-1); }
則計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（ A ）。

A.n+1
B.n-1
C.n
D.n+2

30、（2分）
假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1…100,1…100]，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10，則LOC[5,5]=（ B ）。

A．808
B．818
C．1010
D．1020

31、（2分）
能在Ｏ(1)時(shí)間內(nèi)訪問線性表的第i個(gè)元素的存儲(chǔ)結(jié)構(gòu)是（ A ）。

A.順序存儲(chǔ)結(jié)構(gòu)
B.單向鏈表
C.單向循環(huán)鏈表
D.雙向鏈表

32、（2分）
一個(gè)遞歸算法必須包括（　C ）。

A.遞歸部分
B.迭代部分
C.終止條件和遞歸部分
D.終止條件和迭代部分

33、（2分）
循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0…m]中，則入隊(duì)列的操作為（ D ）

A.rear=rear+1
B.rear=(rear+)%m
C.rear=(rear+1)%m-1
D.rear=(rear+1)%(m+1)

34、（2分）
以下說法正確的是（ D ）。

A.數(shù)據(jù)元素是數(shù)據(jù)的最小單位
B.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位
C.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合
D.一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

35、（2分）
數(shù)組Ｑ［ｎ］用來表示一個(gè)循環(huán)隊(duì)列，ｆ為當(dāng)前隊(duì)列頭元素的前一位置，ｒ為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于ｎ，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（ D ）。

A.r-f
B.(n+f-r)%n
C.n+r-f
D.（n+r-f)%n

二、判斷題（共15題）

1、一個(gè)非空廣義表的表頭總是一個(gè)單元素。( × )
2、算法分析只從時(shí)間復(fù)雜度角度進(jìn)行分析，對(duì)空間開銷無所謂。( × )
3、按行順序存儲(chǔ)的N*M二維數(shù)組a中，其中a[i][j]的地址表達(dá)是： a+i * N+j。( × )
4、線性表中的每個(gè)結(jié)點(diǎn)都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。( × )
5、數(shù)據(jù)項(xiàng)是最小的、有獨(dú)立含義的、不可分割的單位。（ √ ）
6、棧和隊(duì)列都是帶限制操作的線性表。（ √ ）
7、帶頭結(jié)點(diǎn)head的循環(huán)單鏈表為空的判定條件是head->next ==head。 （ √ ）
8、空格串就是指長(zhǎng)度為0的串。( × )
9、串是一種特殊的線性表，其特殊性體現(xiàn)在數(shù)據(jù)元素是單個(gè)字符。（ √ ）
10、在表頭指針為head的單循環(huán)鏈表中，指針q指向尾結(jié)點(diǎn)的條件是 q->next == head。（ √ ）
11、數(shù)據(jù)結(jié)構(gòu)包含了數(shù)據(jù)之間的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。（ √ ）
12、廣義表((a,b,c))的深度和長(zhǎng)度是一致的。( × )
13、一個(gè)非空廣義表的表尾總是一個(gè)表元素。（ √ ）
14、鏈表的存取密度比順序表大。( × )
15、廣義表A=((a,b,c,d))的表尾tail(A)=(b,c,d)。( × )

總結(jié)

以上是生活随笔為你收集整理的数据结构试题期中期末考试【含答案】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。