資源簡介

第一章 認識數據和數據結構 章節測試
一、選擇題
1．數據元素及其關系在計算機存儲器內的表示，也稱為數據的（ ）
A．線性結構 B．物理結構 C．邏輯結構 D．空間結構
2．下到關于數據結構與算法效率的描述，不正確的是（ ）
A．數據元素是數據的基本單位
B．數據的存儲結構應能體現其邏輯結構
C．使用數組結構存儲插入、刪除較多的數據時，效率較低
D．某單向鏈表（結點數>2）設有頭尾指針，在該鏈表尾節點后插入一個新節點時需要遍歷多個結點
3．在Python程序中，列表(List)就是一批變量的集合。已知列表m[2,4,0,23,1,20]，那么m[1]表示的元素是（ ）
A．1 B．2 C．4 D．20
4．下列關于線性表的描述，正確的是（ ）
A．鏈表在訪問、插入、刪除節點操作時，算法效率比數組高
B．棧是一種“先進先出，后進后出”的線性表結構
C．循環隊列是首尾相連的隊列，數據入隊時無需考慮是否會“溢出”
D．字符串是元素個數有限的線性表結構
5．以下說法錯誤的是（ ）
A．棧是一種先進后出的數據結構 B．隊列是一種先進先出的數據結構
C．C++ STL中的map查詢時間復雜度為0(1) D．使用哈希時，可能會發生哈希沖突
6．下列場景中蘊含的數據結構思想與圖一致的是（　　）
圖一：排隊做核酸
A．Excel執行撤銷操作 B．編號不重復的名單
C．尋寶游戲路線 D．打印機任務面板
7．下列有關數據結構的說法，正確的是（　　）
A．數組、鏈表、隊列、棧、樹均為線性表
B．數組和鏈表的存儲空間都是固定不變的
C．在數組中，可通過數組名和下標直接訪問數組元素
D．鏈表中的一個節點就是一個元素，同一鏈表中每個節點的結構可以不相同
8．下列有關數據結構的說法不正確的是：（　　）
A．頻繁進行數據插入和刪除操作，鏈表效率要比數組高
B．單擊瀏覽器“后退”按鈕可回到剛才瀏覽過的網頁， 說明網頁數據是采用棧進行組織的
C．隊列是一種先進先出的線性表，插入一端為隊首，刪除一端為隊尾
D．使用數組在進行數據插入和刪除操作時，不一定會引起數據移動
9．下列關于數據結構的說法不正確的是（ ）
A．數據結構是指數據的組織形式 B．二維數組屬于線性數據結構
C．鏈表是一種優于數組的數據結構 D．隊列是限定僅在一端進行插入，在另一端進行刪除的線性數據結構
10．下列關于數據結構的說法，正確的是（ ）
A．用程序實現問題解決時只能采用一種數據結構
B．數據的邏輯結構是指數據元素間的關系
C．鏈表比數組更適合大量數據元素的隨機訪問
D．數組不必占用一片連續存儲的單元
11．已知Python列表a=［'W'，'o'，'r'，'d'］，依次執行a.pop()、a.append(1)、a.append(d)操作，列表a的值為（　　）
A．［'W'，'o'，'r'，'d'］
B．［'W'，'o'，'r'，'1'，'d'］
C．［'o'，'r'，'d'，'1'，'d'］
D．［'1'，'d'，'o'，'r'，'d'］
12．圖形結構中的每一個結點（ ）
A．無直接后繼結點 B．無直接前驅結點
C．只有一個直接前驅結點和一個直接后繼結點 D．可能有多個直接前驅結點和多個直接后繼結點
13．下列對數據結構的描述不正確的是（ ）
A．數據的邏輯結構是數據元素在計算機存儲器中的存儲方式
B．對同一事物構造的數據結構不同，數據處理的過程就不同
C．數據的存儲結構不同，對數據進行同一操作的實現方法也不同
D．順序存儲結構是最基本的存儲方法
14．以下數據結構中哪一個是非線性結構？（ ）
A．隊列 B．列表
C．樹 D．線性表
15．以下選項中，屬于integer類型常量的是（ ）
A．123 B．3.1415
C．’ 1.23E+04’ D．True
16．如下圖所示，從圖中可知中國的人均GDP處于上漲狀態。以上采用的數據分析方法是（ ）
A．平均分析和交叉分析 B．對比分析和交叉分析
C．平均分析和對比分析 D．對比分析和結構分析
17．除了首元素沒有前趨元素，尾元素沒有后續元素外其他所有元素都只有一個前趨元素和后續元素，這種數據結構屬于（ ）
A．樹結構 B．圖結構 C．線性結構 D．集合結構
18．下列關于數據結構的說法正確的是（ ）
A．同一數據元素中各數據項的數據類型一定相同
B．跳躍表是立足鏈表、借鑒二分查找的思想而形成的數據結構
C．若入棧序列為 abcd，則出棧序列可能為 dbca
D．在瀏覽器中執行“后退”、“前進”操作的原理與隊列的特點相同
19．一份有效的數據分析報告，能夠幫助用戶（ ）
A．了解事物發展現狀，預判事物發展趨勢 B．有效判斷所需解決問題的影響因素
C．有針對性地選擇解決問題的方案 D．以上都是
20．在一個單向鏈表（如圖)中，若在尾指針tail所指節點之后插入新節點(r所指節點），則執行的操作是(　　)
A．tail所指節點的data3值賦為r所指節點的data4值
B．r所指節點的next值賦為tail
C．r所指節點的next值賦為－l
D．tail所指節點的next賦為r,r所指節點的next值賦為－l
21．一個棧的入棧序列為1，2，3，4，5，其出棧序列為s1，s2，s3，s4，s5。若s2是3，則s1不可能是（ ）
A．1 B．2 C．4 D．5
22．下列關于數據和信息的說法正確的是（ ）
A．數據是信息的載體，數據是信息所表示的意義 B．數據是信息的載體，信息是數據所表示的意義
C．信息是數據的載體，數據是信息所表示的意義 D．信息是數據的載體，信息是數據所表示的意義
23．用兩個列表a、b分別保存單向鏈表中的數據區域和指針區域。如下圖所示，在節點x與節點y之間插入一個新節點，操作步驟正確的是（ ）
①b[i]= b[y] ②b[i]= b[x] ③b[y]= i
④b[x]=i ⑤b[i]= x ⑥b[i]= y
A．③⑥ B．④② C．①③ D．②④
24．有如下python程序段：
a=[[3,2],[2,3],[7,1],[1,0]]
p=head=0
while a[p][1]!=head:
print(a[p][0],end="->")

print(a[p][0])
上述程序段要遍歷鏈表中的所有元素，劃線處應添加的代碼是（）
A．p+=1 B．a[p][1]+=1 C．p=a[p][1] D．a[p][1]=a[a[p][1]][1]
25．下列關于數據結構的說法，正確的是（ ）
A．基本數據類型是在程序設計時利用結構數據類型構造出的新類型
B．數據結構設計主要考慮數據之間的存儲結構
C．Python列表中數據的存儲結構和邏輯結構相同
D．行優先的6行10列方陣a首地址為SA，每個元素占10個字節，那么a[2][3]的起始地址為SA+230
二、操作題
26．張三是一名計算機專業的大學生，為了幫助同學們學習專業相關的英語詞匯，編寫一個簡易字典程序。該程序中存放詞匯數據庫，在學習中輸入英文單詞，可以獲得中文翻譯結果。程序中的詞匯數據庫采用鏈表方式存儲，首字母相同時按升序排序。查找單詞時，首先根據首字母找到同首字母最小單詞所在鏈表，再按照鏈表順序查找該單詞。
（1）根據題意，部分的單詞庫數據邏輯結構如圖所示，查找單詞“byte”的過程是“binary”→“bit”→“byte”，補充圖中空白單元格的值為
列表索引 數據區域 指針區域
0 audio 音頻 -1
1 binary 二進制數 6
2 byte 字節 -1
3 cursor 光標 -1
4 access 存取 1
5 cache 高速緩存 3
6 bit 比特 ________
（2）wordlist（data，info）函數實現將詞匯數據庫data以鏈表的方式按字母序升序排列。info表示詞匯數據庫中各字母開頭的最小單詞位置，如info[0]表示字母a開頭的最小單詞在詞匯數據庫data中的位置。實現該功能的程序如下，請在劃線處填入合適的代碼。
def wordlist（data，info）：
n=len（data）
for i in range（n）：
data[i]．append（—1） #data[i]追加一個元素—1
for i in range（n）：
d=data[i][0]
①
if info[k] ==-1：
info[k] = i
else：
head=info[k]
q=head
while②
p=q
q=data[q][2]
if q！=head：
data[p][2]=i
data[i][2]=q
else：
data[i][2]=head
③
return data，info
（3）searchword（data，info，key）函數實現單詞的查找。程序如下，請在劃線處填入合適的代碼。
def searchword（data，info，key）：
k=ord（key[0]）—ord（"a"）
head=info[k]
p=head
while p！=-1：
if data[p][0]==key：
return
p=data[p][2]
return"沒有找到該單詞"
讀取詞匯數據庫，存入列表data中，列表的每個元素包含2個數據項，分別為英文單詞和中文翻譯，如data=[['audio'，'音頻']，['binary'，'二進制數']…]，數據讀取存入的代碼略。
’’’
info=［-1]*26
data，info=wordlist（data，info）
key=input（"請輸入查找單詞："）．lower() #轉化為小寫字母
res=searchword（data，info，key）
print（key，“查找結果是：”，res）
27．有個火車站的鐵軌調度方法如下：火車從一方1,2,3,4…依次進入，由于每個火車皮要去的目標車站不一樣，想讓車皮到站后能以最少的時間從火車上脫離，就讓最近到的車皮放在整列火車的最后。因此需要轉換站來達成這樣的目標，轉換站只能在同一個地方進與出。例如有四個車皮1,2,3,4進入，2,4,3,1到站，即2號車皮目的地最遠，4號車皮倒數第二遠，3號車皮倒數第三遠，1號車皮最近。
為了能快速指揮車輛進出站轉換，小王編寫例如下程序
a=[1,2,3,4,5,6] #待車皮進站
b=[3,2,1,6,5,4] #出站順序
stack=[0]*len(a)
top=0
stack[top]=a[0]
s=str(a[0])+"進"
ha=1;hb=0
while :
while top>-1 and :
s=s+str(stack[top])+"出"
top-=1
if hatop+=1
stack[top]=a[ha]
s=s+str(a[ha])+"進"
ha+=1
elif ha==len(a) and top>-1 and :
print("無法調度")
break
if top==-1:
print(s)
代碼顯示結果：1進2進3進3出2出1出4進5進6進6出5出4出
(1)修改加框處代碼
(2)將劃線處代碼補充完整，使功能完善
28．雙向鏈表也叫雙鏈表，也是鏈表的一中，它的每個數據都有兩個指針，分別指向前驅節點和后繼節點。在python中用二維列表來模擬雙向鏈表，用包含3個元素的列表來表示每一個節點，其中第一個元素存儲數據，后兩個元素分別存儲指向前驅節點和后繼節點的指針。若沒有前驅或后繼節點則對應的指針值為-1。下列程序產生了一些兩位隨機正整數，并依次存儲到雙向鏈表a中。現要求刪除其中值為偶數的節點，請完善代碼：
import random
a=[]
head=-1
for i in range(8):
node=[ ① ,head,-1]
a.append(node)
if head!=-1:
a[head][2]=i
head= ②
p=head=0
while p!=-1:
if a[p][0]%2==0:
if ③ :
a[a[p][1]][2]=a[p][2]
if a[p][2]!=-1:
a[a[p][2]][1]=a[p][1]
if head==p:
head= ④
p=a[p][2]
參考答案
1．B
2．D
3．C
4．D
5．C
6．D
7．C
8．C
9．C
10．B
11．B
12．D
13．A
14．C
15．A
16．C
17．C
18．B
19．D
20．D
21．D
22．B
23．D
24．C
25．D
26．2 k=ord(d[0])—ord(“a”) q != -1 and d>data[q][0] info[k]=i data[p][1]
27．top>-1 and hb<=len(b) stack[top]==b[hb] hb+=1 stack[top]!=b[hb]
28．random.randint(10,99) i a[p][1]!=-1 a[p][2]

展開更多......

收起↑