程序设计导引习题集
文章目錄
- 綜合習題1【導論篇】
- 綜合習題2【導論篇】
- 選擇題
- 填空題
- 基礎練習【數據結構篇】
- 數據結構概述
- 選擇題
- 填空題
- 參考答案
- 線性表
- 單項選擇題
- 填空題
- 參考答案
- 鏈表
- 選擇題
- 填空題
- 參考答案
- 串
- 選擇題
- 填空題
- 參考答案
- 數組和稀疏矩陣
- 選擇題
- 填空題
- 參考答案
- 樹和二叉樹
- 選擇題
- 填空題
- 參考答案
- 圖
- 選擇題
- 填空題
- 參考答案
- 查找
- 選擇題
- 填空題
- 參考答案
- 內排序
- 選擇題
- 填空題
- 參考答案
綜合習題1【導論篇】
A． 128K B．64K C. 64KB D、128KB
A. 5 4 3 6 1 2
B. 4 5 3 2 1 6
C. 3 4 6 5 2 1
D. 2 3 4 1 5 6
綜合習題2【導論篇】
選擇題
① A、計算方法 B、排序方法C、解決問題的有限運算序列 D、調度方法
② A、可執行性、可移植性和可擴充性 B、可行性、確定性和有窮性 C、確定性、有窮性和穩定性 D、易讀性、穩定性和安全性
A、隨機存取 B、 順序存取 C、索引存取 D、散列存取
A、數據復雜性和程序復雜性 B、可讀性和文檔性
C、 時間復雜度和空間復雜度 D、正確性和簡單性
A、 110 B、108 C、100 D、120
A、 edcba B、decba C、dceab D、abcde
A、ST.TOP！=0 B、ST.TOP==0 C、ST.TOP！=M0 D、ST.TOP= =ST.BASE
A、ST.TOP！=M0 B、ST.TOP==0 C、ST.BASE！=M0 D、ST.TOP-ST.BASE=M0
A、4,3,2,1 B、1,2,3,4 C、1,4,3,2 D、3,2,4,1
A、QU.rear-QU.front= =m0 B、QU.rear-QU.front-1= =m0
B、 QU.front= =QU.rear D、QU.rear+1=QU.front
A、QU.rear-QU.front==m0 B、(QU.rear+1)%m0= =QU.front
C、 QU.front= =QU.rear D、QU.rear+1=QU.front
A、(rear-front+m)%m B、rear-front+1 C、rear-front-1 D、rear-front
A、都是先進后出 B、都是先進先出
C、只允許在端點處插入和刪除元素 D、都是操作受限的線性表
A、head= = NULL B、head.next= = NULL
C、head.next= = head D、head!=NULL
A、head= = NULL B、head.next= = NULL
C、head.next= = head D、head!=NULL
A、p.next= = NULL B、p= = NULL
C、p.next= = head D、p= =head
A、3 B、4 C、5 D、6
A、c，b，e，f，d，a B、a，e，d，f，b，c
C、b，d，c，e，a，f D、d，e，c，f，b，a
A、必須是連續的 B、部分地址必須是連續的
C、一定是不連續的 D、連續或不連續都可以
A、s->next=p;p->next=s; B、 s->next=p->next;p->next=s;
D、 s->next=p->next;p=s; D、p->next=s;s->next=p;
A、3 B、4 C、5【1+2+2】 D、6
A、16 B、32 C、31【2^5-1】 D、10
A、有序數據元素 B、無序數據元素
C、元素之間具有分支層次關系的數據 D、元素之間無聯系的數據
A、 15 B、 17 C、 16 D、 無法計算
填空題
④：非線性結構
無；一；無；一
前驅；一；后續；很多
有n個
邏輯關系
后進先出；先進先出
插入刪除的位置
一定，不一定【單鏈表可以順序存儲，也可以鏈式存儲】
1，3，5，7，9
線性；任意；棧尾；隊尾；隊頭
（1） 這棵樹根結點是_____k1_____
（2） 這棵樹的葉子結點是_____k2,4,5,7______
（3） 結點K3的深度是_____3_____
（4） 這棵樹的度是________
（5） 這棵樹的深度是_____4________
（6） 結點K3的子女是_______k5,6________
（7） 結點K3的雙親結點是_____k1____
基礎練習【數據結構篇】
數據結構概述
選擇題
1、數據結構被形式地定義為（D，R），其中D是_①_的有限集，R是D上的?_② 有限集。
① A、算法 B、 數據元素 C、數據操作 D、邏輯結構
② A、操作 B、 映像 C、存儲 D、關系
2、線性結構的順序存儲結構是一種_______的存儲結構，線性表的鏈式存儲結構是一種___的存儲結構
A、隨機存取 B、 順序存取 C、索引存取 D、散列存取
3、計算機算法指的是___①____，它必須具備輸入、輸出和__②__等5個特征。
① A、計算方法 B、排序方法C、解決問題的有限運算序列 D、調度方法
② A、可執行性、可移植性和可擴充性 B、可行性、確定性和有窮性 C、確定性、有窮性和穩定性 D、易讀性、穩定性和安全性
4、線性表的邏輯順序與存儲順序總是一致的，這種說法是_______
A、正確 B、 錯誤
5、每種數據結構都具有三個基本運算：插入、刪除和查找，這種說法_______
A、正確 B、 錯誤
6、下列算法是時間復雜度是（ ）
for(i=0;i<n;i++)
for(j=0;j<n;j++)
c[i][j]=i+j;
A、 O（1）B、O（n）C、O（log2n）D、O（n2）
7、算法指的是（ ）
A、 計算機程序B、解決問題的答案C、排序算法D、解決問題的有限運算序列
8、在n個結點的順序表中，算法的時間復雜度是O（1）的操作是（ ）
A、訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n）
B、在第i個結點后插入一個新結點（1≤i≤n）
C、刪除第i個結點（1≤i≤n）
D、將n個結點從小到大排序
9、算法分析的兩個主要方面是（ ）
A、數據復雜性和程序復雜性 B、可讀性和文檔性
C、時間復雜度和空間復雜度 D、正確性和簡單性
10、下列算法的時間復雜度是（ ）
i=1；j=0；
while (i+j<=n)
{ if(i>j) j++；
else i++； }
A、O（1）B、 O（n）C、O（log2n） D、O（n2）
11、
填空題
1、 數據的邏輯結構包括____①___、②___和___③____三種結構，樹形結構和圖形結構合稱為_____④__。
2、 在線性結構中，第一個結點__①___前驅結點，其余每個結點有且只有__②__個前驅結點，最后一個結點__③__后繼結點，其余每個結點有且只有_④__個后繼結點。
3、 在樹形結構中，樹根結點沒有___①___結點，其余每個結點有且僅有_②__個前驅結點；葉子結點沒有__③___結點，其余每個結點的后續結點可以___④____。
4、 在圖形結構中，每個結點的前驅結點數和后續結點數可以___①____。
5、 線性結構中元素之間存在____①___關系，樹形結構中元素之間存在____②__關系，兔形結構中元素之間存在___③___關系。
6、 下面程序段的時間復雜度是________
for ( i =0; i<n ; i++)
for (j=0; j<m ;j++)
A[i][j]=0;
7、數據結構是一門研究非數值計算的程序設計問題中計算機的 以及它們之間的 和運算等的學科。
8、在計算機中存儲數據結構時不僅要存儲數據元素的值，還要存儲數據元素之間的 。
9
參考答案
一、選擇題
1、①B ②D 2、 ①A ②B 3、 ①C ②B 4、 B 5、B
二、填空題
1、線性結構、樹形結構 、圖形結構 、非線性結構 2、沒有、1、沒有、1
3、前驅、1、后續、任意多個 4、任意多個 5、一對一、一對多、多對多 6、O(m*n)
線性表
單項選擇題
A、110 B、108 C、100 D、120
A、edcba B、decba C、dceab D、abcde
A、i B、n=i C、n-i+1 D、不確定
A、ST.TOP！=0 B、ST.TOP==0 C、ST.TOP！=M0 D、ST.TOP= =ST.BASE
A、ST.TOP！=M0 B、ST.TOP==0 C、ST.BASE！=M0 D、ST.TOP-ST.BASE=M0
A、4,3,2,1 B、1,2,3,4 C、1,4,3,2 D、3,2,4,1
A、QU.rear-QU.front= =m0 B、QU.rear-QU.front-1= =m0
C、QU.front= =QU.rear D、QU.rear+1=QU.front
A、QU.rear-QU.front==m0 B、(QU.rear+1)%m0= =QU.front
C、QU.front= =QU.rear D、QU.rear+1=QU.front
9、 循環隊列用數組A[0，m-1]存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數為_______
A、(rear-front+m)%m B、rear-front+1 C、rear-front-1 D、rear-front
10、棧和隊列的共同點是_____
A、都是先進后出 B、都是先進先出
C、只允許在端點處插入和刪除元素 D、沒有共同點
11、表達式a*(b+c)-d的中綴表達式是______
A、abcd*± B、abc+d- C、abc+d- D、-+*abcd
12不帶頭結點的單鏈表head為空的判定條件是：__________
A、head= = NULL B、head.next= = NULL
C、head.next= = head D、head!=NULL
13帶頭結點的單鏈表head為空的判定條件是-__________
A、head= = NULL B、head.next= = NULL
C、head.next= = head D、head!=NULL
14非空的循環單鏈表head的尾結點（由P所指向）滿足_______
A、p.next= = NULL B、p= = NULL
C、p.next= = head D、p= =head
15、從一個具有n個結點的單鏈表中查找其值等于x的結點時，在查找成功的情況下，需平均比較______個結點。
A、n B、n/2 C、(n-1)/2 D、(n+1)/2
16、在一個具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是_____
A、O(1) B、O(n) C、O(n2) D、O(nlog2n)
17、線性結構中，只有一個直接前驅和一個直接后繼的結點是（ ）
A、 第一個結點 B、最后一個結點
C、中央的結點 D、除第一個和最后一個之外的所有結點
18、設有一個順序棧S，元素s1,s2,s3,s4,s5,s6依次入棧，如果這六個元素的出棧順序是s2,s4,s3,s6,s5,s1，則棧的容量至少應該是（ ）
A、3 B、4 C、5 D、6
19、非空的循環單鏈表head的尾結點（由p指向）滿足（ ）
A、p->next= =null B、p= =null
C、p->next= =head D、p= =head
20、可以借助數據元素在存儲器中的相對位置來表示數據元素之間的邏輯關系的存儲表示方法是（ ）
A、 順序存儲結構B、 鏈式存儲結構C、 索引存儲結構D、散列存儲結構
21、與線性表的鏈式存儲結構相符的特性是（ ）
A、可以隨機訪問 B、不需要另外開辟空間來保存元素間的關系
C、存儲空間靜態分配 D、插入和刪除操作靈活
22、 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（ ）個元素。
A、 8 B、63.5 C、63 D、7
23、設一個棧的入棧序列是a，b，c，d，e，f，則不可能的出棧序列是（ ）。
A、c，b，e，f，d，a B、a，e，d，f，b，c
C、b，d，c，e，a，f D、d，e，c，f，b，a
24、線性表采用鏈式存儲結構時，要求內存中可用存儲單元的地址（ ）
A、必須是連續的 B、部分地址必須是連續的
C、一定是不連續的 D、連續或不連續都可以
25、
填空題
1、 在一個長度為n的向量中的第 i個元素(1<= i <=n)之前插入一個元素時，需向后移動______個元素。
2、 在一個長度為n的向量中刪除第i個元素時，需要向前移動______個元素。
3、 在具有n個單元的循環隊列中，隊滿是共有______個元素。
4、 棧的特點是______，隊列的特點是________
5、 在順序表中插入或刪除一個元素，需要平均移動（ ）個元素，具體移動的元素個數與（ ）有關。
6、 順序表中邏輯上相鄰的元素的物理位置（ ）相鄰。單鏈表中邏輯上相鄰的元素的物理位置（ ）相鄰。
7、 一個隊列的入隊序列是1,3,5,7,9，則出隊的輸出序列只能是
8、 線性表、棧和隊列都是 性數據結構；可以在線性表的 位置插入和刪除元素；對于棧應在 位置插入和刪除元素；對于隊列應在 位置插入元素，在 位置刪除元素。
9、
參考答案
一、選擇題
1、B 2、C 3、C 4、D 5、D 6、B 7、C 8、A 9、A 10、C 11、B
12、A 13、B 14、C 15、D 16、B
二、填空題
1、n-i+1 2、 n-i 3、 n-1 4 、 后進先出、先進先出
鏈表
選擇題
1、 向一個棧頂指針為HS的鏈棧中插入一個s所指結點時，應執行________
A、HS.next= s B、s.next = HS.next ;HS.next= s
C、s.next=HS;HS=s D、 s.next=HS;HS=HS.next
2從一個棧頂指針為HS的鏈棧中刪除一個結點時，用x保存被刪除結點的值，應執行____
A、x=HS;HS=HS.next B、x=HS.data
C、HS=HS.next;x=HS.data D、 x=HS.data;HS=HS.next
3、在一個鏈隊中，假設f和r分別為隊首和隊尾指針，則插入s所結點的運算是________
A、f.next=s;f=s B、r.next=s;r=s;
C、s.next=r;r=s; D、 s.next=f;f=s;
4、在一個鏈隊中，假設f和r分別為隊首和隊尾指針，則刪除一個結點的運算是________
A、r=f.next B、r=r.next
C、f=f.next D、f=r.next
5、非空的循環單鏈表head的尾結點（由p所指向）滿足___。
A、p->next= =NULL B、p= =NULL C、p->next= =head D、p= =head
6、設一個棧的輸入序列為a，b，c,d，則所得出棧的輸出序列不可能是（ ）
A、 a,b,c,d B、 d,a,b,c C、 a,c,d,b D、d,c,b,a
7、判斷一個循環隊列cq（最多元素為QueueSize）為滿隊列的條件是（ ）
A、cq.rear= =cq.front
B、cq.rear= = QueueSize
C、（cq.rear+1）% QueueSize= =cq.front
D、cq.rear% QueueSize+1= =cq.front
8、將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（ ）。
A、O(1) B、O(n) C、O(m) D、O(m+n)
9、在帶頭結點的單鏈表h中，若要向表頭插入一個由指針p所指向的結點，則執行（ ）
A、 h=p；p-〉next=h； B、 p-〉next=h ；h=p；
C、 p-〉next=h；p=h； D、 p-〉next=h-〉next；h-〉next=p；
10、在一個單鏈表中，若p所指結點不是最后結點，在p之后插入s所指結點，則執行（ ）
A、s->next=p;p->next=s; B、 s->next=p->next;p->next=s;
C、s->next=p->next;p=s; D、p->next=s;s->next=p;
11、若循環隊列用數組A[m]存放其元素值，已知其頭尾指針分別是front和rear,則當前隊列中的元素個數是（ ）。
A、(rear-front+m) mod m B、rear-front+1
C、rear-front-1 D、rear-front
12、若已知一個棧的入棧序列為1，2，3,…，n，其出棧的序列為p1 ,p2 ,p3 ,… ,pn，若p1=n，則pi(1≤i<n)為（ ）
A） i B） n-i C） n-i+1 D） 不確定
13、循環順序隊列中是否可以插入下一個元素，（ ）。
A、 與隊首指針和隊尾指針所在的位置有關
B、 只與隊尾指針所在的位置有關
C、 只與數組的大小有關，與隊首和隊尾指針所在的位置無關
D、 與曾經進行過多少次插入操作有關
填空題
1、在棧頂指針為HS的鏈棧中，計算該鏈棧中結點個數的函數是________
2、 對于一個具有n個結點的單鏈表，在已知p所指結點后插入一個新結點的時間復雜度是_______；在給定值為x的結點后插入一個新結點的時間復雜度為_________
3、 在單鏈表中，除了第一個元素（首元結點）外，任一結點的存儲位置由（ ）指示。
4、 已知L是無表頭結點的單鏈表，且P結點既不是首元結點，又不是尾元結點，則：
（1）在P結點后插入S結點的語句序列是（ ）；
（2）在P結點前插入S結點的語句序列是（ ）；
（3）在表首插入S結點（S為表中第一個結點）的語句序列是（ ）；
（4）在表尾插入S結點的語句序列是（ ）；
5、 已知L是帶表頭結點的非空單鏈表，且P結點既不是首元結點，又不是尾元結點，則：
（1）刪除P結點的直接后繼結點的語句序列是（ ）；
（2）刪除P結點的直接前驅結點的語句序列是（ ）；
（3）刪除P結點的語句序列是（ ）；
（4）刪除首元結點的語句序列是（ ）；
（5）刪除尾元結點的語句序列是（ ）；
6、 在單循環鏈表中，已知q指向p指向結點的前驅結點，若在q，p所指結點之間插入一個s所指向的新結點，則執行的操作是
7、在一個單鏈表中刪除P所指結點時，可執行以下操作：
q=p->next；
p->data=q->data；
；
Free(q)；
8、在一個鏈隊列Q中，假定Q.front和Q.rear分別為隊首和隊尾指針，則刪除隊列中一個結點的操作是 。
參考答案
一、選擇題
1、C 2、D 3、B 4、C
二、填空題
1、 int count(node *HS)
{
node *p;
int n=0;
p=HS;
while(p!=NULL)
{
n++;
p=p.next;
}
return n;
}
2、O(1),O(n)
串
選擇題
1、如下陳述中正確的是（ ）
A、 串是一種特殊的線性表B、 串的長度必須大于0
C、串中元素只能是字母D、空串就是空白串
2、設字符串s1=‘abcdefg’，s2=‘pqrst’，則運算s=strcat（substr（s1，2，length（s2）），substr（s1，length（s2），2））后串值為（ ）
A、‘bcdefef’B、‘bcpqrst’C、‘bcdefg’D、‘bcdef’
3、以下論述正確的是（ ）
A、空串和空格串是相同的 B、串中元素只能是26個英文字母
C、空串是零個字符的串 D、空串長度為1
4、設某串長度為n，則它的子串個數是（ ）
A、 n B、 n（n+1） C、 n（n+1）/2 D、 n（n+1）/2+1
5、設字符串s=‘sciencestudy’，則進行運算scopy（p，substr（s，1，7）后得到（ ）
A、 p=‘science’ B、p=‘study’ C、s=‘science’ D、 s=‘study’
6、若串s=”software”，則其子串的個數是（ ）
A、8 B、9 C、36 D、37
7、
填空題
1、串是一種特殊的線性表，其特殊性表現在_____________
2、設有兩個串p和q，求q在p中首次出現的位置的運算稱作________
3、設串s1=’ABCDEFG’,s2=’PQRST’,函數con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號 i 的字符開始的j個字符組成的子串,len(s)返回串s的長度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結果是___________
4、兩個串相等的充分必要是_________
5、空串是______________，其長度等于_______
7、 空格串是__________其長度等于_______
8、 設S=“A;/document/Mary.doc”，則strlen(s)= , “/”的字符定位的位序為 。
9、 設目標T=”abccdcdccbaa”，模式P=“cdcc”，則第 次匹配成功。
參考答案
一、選擇題
1、
二、填空題
1 數據元素是一個字符 2、模式匹配 3、BCDEFEF 4、兩個串的長度相等且對應位置的字符相同 5、零個字符的串，零 6、一個或多個空格組成的串，其包含的空格個數
數組和稀疏矩陣
選擇題
1、 遞歸函數f(n)=f(n-1)+n(n>1)的遞歸出口是_______
A、f(1)=0 B、f(1)=1 C、f(0)=1 D、f(n)=n
2、 遞歸函數f(n)=f(n-1)+n(n>1)的遞歸體是_______
A、f(1)=0 B、f(0)=1 C、f(n)=f(n-1)+n D、f(n)=n
3、 將遞歸算法轉換成對應的非遞歸算法時，通常需要采用________
A、棧 B、隊列 C、鏈表 D、樹
4、二維數組M的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍是從0到7，列下標j的范圍從0到9，則存放M需要存儲單元數為（ ）
A、360 B、480 C、240 D、320
5、假設有60行70列的二維數組a[1…60, 1…70]以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a[32,58]的存儲地址為（ ）。（無第0行第0列元素）
Ａ、16902 B、16904 C、14454 D、答案A, B, C均不對
6、已知廣義表A=（（a，b，c），（d，e，f）），則廣義表A的表尾是（ ）
Ａ、（d，e，f） B、（（d，e，f））
C、f D、（f）
7、設有一個二維數組A[10][15],數組按行存放，假設A[0][0]存放位置在644,每個元素占一個空間，則A[4][5]在（ ）位置.
A、 672 B、626 C、709 D、724
填空題
1、已知二維數組A[m][n]采用行序為主方式存儲，每個元素占據k個存儲單元，并且第一個元素的存儲地址是LOC(A[0][0])，則A[i][j]的地址是_________
2、已知二維數組A[10][20]采用列序為主方式存儲，每個元素占一個存儲單元，并且A[0][0]單元的存儲地址是200，則A[6][12]的地址是________
3、二維數組A[10…20][5…10]采用行序為主方式存儲，每個元素占四個存儲單元，并且A[10][5]的存儲地址是1000，則A[18][9]的地址是_______
4、 廣義表（（a）,a）的表頭是________，表尾是________.
5、 廣義表（（a））的表頭是_________，表尾是_________
6、 廣義表（a,b,c,d）的表頭是_________,表尾是__________
7、 廣義表（a,(a,b),d,e((i,j),k)）的長度是________,深度是_______
8、 三元素組表中的每個結點對應于稀疏矩陣的一個非零元素，它包含有三個數據項，分別表示該元素的 、 和 。
9、 GetHead((a,b),(c,d))=
10、假設有二維數組A6×8，每個元素用相鄰的6個字節存儲，存儲器按字節編址。已知A的起始存儲位置（基地址）為1000，則數組A的體積（存儲量）為 ；末尾元素A57的第一個字節地址 ；若按行存儲時，元素A14的第一個字節地址 ；若按列存儲時，元素A47的第一個字節地址為 。
11、GetHead【GetTail【((a,b),(c,d))】】= 。
12、三元組表中的每個結點對應于稀疏矩陣中的一個非零元素，它包含有三個數據項，分別表示該元素的 、 和 。
參考答案
一、 選擇題
1、B 2、 C 3、A
二、填空題
1、 LOC(A[0][0])+(n*i + j)k
2、 提示：LOC(A[0][0])+(mj + i)*k 232
3、 1208
4、 (a),(a)
5、 (a),()
6、 a,(b,c,d)
7、 5,3
樹和二叉樹
選擇題
1、 下面的4個二叉樹中，不是完全二叉樹
2、 在線索化的二叉樹中，t所指結點沒有左子樹的充要條件是____
A、t.left= = NULL B、t.ltag= = 1
C、t.ltag= =1 && t.left= = NULL D、以上都不對
3、 二叉樹按某種順序線索化后，任一結點均有指向其前趨和后繼的線索，這種說法______
A、正確 B、錯誤
4、 二叉樹的前序遍歷序列中，任意一個結點均在其子女結點的前邊，這種說法___________
A、正確 B、錯誤
5、 如下圖所示的二叉樹的中序遍歷序列是______________
A、abcdgef
B、dfegagc
C、dbaefcg
D、defbage
6、已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是_____
A、acbed B、decab C、deabc D、cedba
7、如果T2是由有序樹T轉換而來的二叉樹，那么T中結點的前序就是T2中結點的______
A、前序 B、中序 C、后序 D、層次序
8、如果T2是由有序樹T轉換而來的二叉樹，那么T中結點的后序就是T2中結點的______
A、前序 B、中序 C、后序 D、層次序
9、某二叉樹的前序遍歷結點訪問順序是abdgcefh,中序遍歷的結點訪問順序是dgbaechf,則后序遍歷的結點訪問順序是______
A、bdgcefha B、gdbecfha C、bdgaechf D、gdbehfca
10、按照二叉樹的定義，有3個結點的二叉樹有________中
A、3 B、4 C、5 D、6
11、深度為5的二叉樹至多有________個結點。
A、16 B、32 C、31 D、10
12、樹最適合用來表示__________
A、有序數據元素 B、無序數據元素
C、元素之間具有分支層次關系的數據 D、元素之間無聯系的數據
13、任何一個二叉樹的葉結點在先序，中序和后序遍歷中的相對次序________
A、不發生改變 B、發生改變 C、不能確定 D、以上都不對
14、對一個滿二叉樹，m個樹葉，n個結點，深度為h，則_________
A、n=h+m B、h+m=2n C、m=h-1 D、n=2h-1
15、設m,n為一棵二叉樹上的兩個結點，在中序遍歷時，n在m之前的條件是_______
A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孫
16、某二叉樹只有度為0和度為2的結點，其中度為2結點數為8個，則該二叉樹共有（ ）個結點
A、 15 B、 17 C、 16 D、 無法計算
17、某完全二叉樹共有68個結點，從樹根起，自上層到下層，每層從左到右給每個結點順序編號，編號為32的結點的左孩子的編號是（ ）
A、16 B、 64 C、 65 D、 無左孩子
18、若一棵二叉樹中只有10個度為2的結點，則該二叉樹中度為0的結點個數為（ ）
A、 9 B、10 C、11 D、不確定
19、將一棵有100個結點的完全二叉樹從上到下，從左到右依次對結點進行編號，根結點的編號為1，則編號為49的結點的左孩子編號為（ ）
A、49 B、50 C、98 D、99
20、若由樹轉化得到的二叉樹是非空的二叉樹，則二叉樹的形狀是（ ）
A、 根結點無右子樹 B、根結點無左子樹
C、 根結點只有左子樹或只有右子樹 D、左、右子樹都可能有
21、判斷線索二叉樹中某結點p有左孩子的條件是（ ）
A、p! = =null B、p->lchild!= =null
C、p->ltag= =0 D、p->ltag= =1
22、若一棵二叉樹中度為2的結點個數為10個，度為1的結點個數為20個，則該二叉樹中度為0的結點個數為（ ）個。
A、 9 B、11 C、19 D、21
23、設二叉樹根結點的層次為1，所有含有63個結點的二叉樹中，最小高度是（ ）。
A、 8 B 、7 C、6 D、 5
24、將一棵有100個結點的完全二叉樹從上到下，從左到右依次對結點進行編號，根結點的編號為1，則編號為49的結點的左孩子編號為（ ）。
A、49 B、 50 C、98 D、 99
25、設結點x和結點y是二叉樹T中的任意兩個結點，若在前序序列中x在y之前，而在中序序列中x在y之后，則x和y的關系是（ ）。
A、x是y的左兄弟 B、x是y的右兄弟 C、y是x的祖先 D、y是x的孩子
26、某二叉樹的中序序列和后序序列相同，則這棵二叉樹必然是（ ）。
A、空樹
B、 空樹或任一結點都沒有左孩子的非空二叉樹
C、空樹或任一結點都沒有右孩子的非空二叉樹
D、 空樹或僅有一個結點的二叉樹
27、一棵完全二叉樹中根結點的編號為1，而且編號為23的結點有左孩子但沒有右孩子，則該二叉樹共有（ ）個結點
A、24 B、45 C、46 D、 47
填空題
1、 有一棵樹如下圖所示，回答下面問題：
（1） 這棵樹根結點是__________
（2） 這棵樹的葉子結點是___________
（3） 結點K3的深度是__________
（4） 這棵樹的度是________
（5） 這棵樹的深度是_____________
（6） 結點K3的子女是_______________
（7） 結點K3的父結點是_________
2、 從概念上講，樹與二叉樹是兩種不同的數據結構，將樹轉化為二叉樹的基本目的是_____
3、 一棵二叉樹的結點數據采用順序存儲結構，存儲于數組T中，如下圖所示，則該二叉樹的鏈接表示形式為___________
4、深度為k的完全二叉樹至少有______個結點，至多有______個結點，若按自上而下，從左到右次序給結點編號，（從1開始），則編號最小的葉子結點的編號是______________
5、一棵二叉樹的第i（i>=1）層最多有________個結點，一棵有n（n>0）個結點的滿二叉樹共有______個葉子和_____個非終端結點。
6、現有按中序遍歷二叉的的結果是abc,問有_________種不同形態的二叉樹可以得到這一遍歷結果，這些二叉樹是______________(畫出相應的圖形結構)
7、以數據集{4，5，6，7，10，12，18}為結點權值所構成的哈夫曼樹為___________,其帶權路徑長度為___________________
8、深度為6的二叉樹至多有 個結點。
9、一棵具有257個結點的完全二叉樹，它的深度為 。
10、深度為h的二叉樹最多有 個結點，最少有 個結點。
11、在一棵二叉樹中，度為2的結點個數為n2個，度為1的結點個數為n1個，則該二叉樹中度為0的結點個數為 個。
參考答案
一、 選擇題
1、C 2、 B 3、B 4、A 5、B 6、D 7、A 8、B
9、D 10、C 11、C 12、C 13、A 14、D 15、C
二、填空題
1、 K1,K2K5K7K4,2,3,4,K5K6,K1
2、 樹可采用二叉樹的存儲結構并利用二叉樹的已有算法解決樹的有關問題
3、
4、 2k-1, 2k-1, 2k-2+1
5、 2i-1, 2[log2n], 2[log2n]-1
6、 5種
7、 路徑長度為165
哈夫曼樹為：
圖
選擇題
1、 在一個圖中,所有頂點的度數之和等于所有邊數的_________倍。
A、1/2 B、1 C、2 D、4
2、 在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的_________倍。
A、1/2 B、1 C、2 D、4
3、 一個有n個頂點的無向圖最多有_____條邊。
A、n B、n(n-1) C、n(n-1)/2 D、2n
4、 具有6個結點的無向圖至少應有__________條邊才能確保是一個連通圖。
A、5 B、6 C、7 D、8
5、 對于一個具有n個結點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是_______
A、n B、(n-1)2 C、n-1 D、n2
6、對于一個具有n個頂點和e條邊的無向圖，若采用鄰接矩陣表示，則表頭向量的大小為_____,所有鄰接表中的結點總數是________
①A、n B、n+1 C、n-1 D、n+e
②A、e/2 B、e C、2e D、n+e
7、已知一個圖如右所示，若從頂點a 出發按深度搜索法進行遍歷，則可能得到的一種頂點序列為_________;按寬度搜索法進行遍歷，則可能得到的一種頂點序列為________.
①A、a,b,e,c,d,f B、a,c,f,e,b,d C、a,e,b,c,f,d D、a,e,d,f,c,b
②A、a,b,c,e,d,f B、a,b,c,e,f,d C、a,e,b,c,f,d D、a,c,f,d,e,b
8、已知一有向圖的鄰接表存儲結構如右圖所示
(1)、根據有向圖的深度優先遍歷算法，從頂點v1出發，所得到的頂點序列是_________
A、v1,v2,v3,v5,v4 B、v1,v2,v3,v4,v5
C、v1,v3,v4,v5,v2 D、v1,v4,v3,v5,v2
(2)、根據有向圖的寬度優先遍歷算法，從頂點v1出發，所得到的頂點序列是_____________
A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5
C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v2
9、采用鄰接表存儲的圖的深度優先遍歷算法類似于二叉樹的______________
A、先序遍歷 B、中序遍歷 C、后序遍歷 D、按層遍歷
10、采用鄰接表存儲的圖的寬度優先遍歷算法類似于二叉樹的______________
A、先序遍歷 B、中序遍歷 C、后序遍歷 D、按層遍歷
11、在一個圖G中，所有頂點的度數之和等于所有邊數的（ ）倍。
A、1/2 B、 1 C、2 D、 4
13、設38是二叉排序樹T中關鍵字最小的數據結點，則該結點
A、 沒有左子樹 B、 沒有右子樹 C、是葉結點 D、 不能確定
14、設圖G是具有n個頂點的有向圖，則圖G最多有（ ）條邊。
A、 n(n-1) B、n-1 C、n(n+1) D、n+1
15、關鍵路徑是AOE網中 ( )
A、 從源點到匯點的最短路徑B、 從源點到匯點的最長路徑
C、 最長的回路D、 最短的回路
16、在一個具有n個頂點的無向圖中，要連通全部頂點至少要（ ）條邊。
A、 n B、n+1 C、n-1 D、n/2
17、（ ）鄰接矩陣是對稱矩陣。
A、 有向圖 B、無向圖 C、AOV網 D、AOE網
18、具有6個頂點的連通圖的廣度優先生成樹，其邊數為（ ）。
A、6 B、5 C、7 D、4
19、具有n個頂點e條邊的無向圖的鄰接表，其邊表結點的總數為（ ）
A、n B、e C、 2e D、 n+e
20、在含有n個頂點e條邊的無向圖的鄰接矩陣中，零元素的個數為（ ）
A、 e B、2e
C、n2-e D、n2-2e
21、判定一個有向圖中是否存在回路的方法是（ ）。
A、拓撲排序 B、廣度優先遍歷
C、 求關鍵路徑方法 D、 Dijkstra方法
22、具有五層結點的二叉平衡樹至少有（ ）個結點。
A、 10 B、12 C、15 D、17
23、下述編碼哪一組不是前綴碼（ ）？
A、00，01，10，11
B、 0，10，110，111
C、 0，1，00，11
D、 1，01，001，000
填空題
1、在無權圖G的鄰接矩陣A中,若(vi,vj)或<vi,vj>屬于圖G的邊集，則對應元素A[i][j]等于_______，否則等于__________
2、在無向圖G的鄰接矩陣A中，若A[i][j]=1,則A[j][i]=________
3、已知一個圖的鄰接矩陣表示，計算第i個結點的入度的方法是____________
4、 已知一個圖的鄰接矩陣表示，刪除所有從第i個結點出發的邊的方法是_______________
5、 n個頂點e條邊的圖采用鄰接矩陣存儲，深度優先遍歷算法的時間復雜度為 ；若采用鄰接表存儲時，該算法的時間復雜度為 。
6、判斷一個有向圖中是否存在環的操作是 。
7、無向圖G中頂點數n，則圖G最多有__ _條邊。
8、具有n個頂點的無向連通圖的深度優先生成樹，其邊數是（ ）條。
參考答案
一、 選擇題
1、C 2、 B 3、C 4、A 5、D 6、A,C 7、D,B 8、C,B 9、A 10、D
二、填空題
1、 1,0
2、 1
3、 求矩陣第i列非0 元素之和
4、 將矩陣第i行全部置0
查找
選擇題
1、 如圖所示的4個二叉樹，是平衡二叉樹
2、 順序查找法適合于存儲結構為__________的線性表。
A、散列存儲 B、順序存儲或鏈式存儲 C、壓縮存儲 D、索引存儲
3、 對線性表進行二分查找時，要求線性表必須___
A、以順序方式存儲 B、以鏈接方式存儲
C、以順序方式存儲，并且結點按關鍵字有序排序
D、以鏈接方式存儲，并且結點按關鍵字有序排序
4、 采用順序查找法查找長度為n的線性表時，每個元素的平均查找長度為________
A、n B、n/2 C、(n+1)/2 D、(n-1)/2
5、 采用二分法查找長度為n的線性表時，每個元素的平均查找長度為_________
A、O(n2) B、O(nlog2n) C、O(n) D、O(log2n)
6、 有一個有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當用二分法查找值為82的結點時，次比較后查找成
A、1 B、2 C、4 D、8
7、 設哈希表長m=14，哈希函數H(key)=key%11，表中有4個結點：
add(15)=4 add(38)=5 add(61)=6 add(84)=7 其余地址為空，如果利用二次探測在散列處理沖突，關鍵字為49的結點地址為
A、8 B、3 C、5 D、9
8、有一個長度為12的有序表，按二分查找法對該表進行查找，在表內個各元素等概率的情況下查找成功所需的平均比較次數為__________
A、35/12 B、37/12 C、39/12 D、43/12
9、采用分塊查找時，若線性表中共有625個元素，查找每個元素的概率相同，假設采用順序查找來確定結點所在的塊時，每塊應分為______個結點最佳。
A、10 B、25 C、6 D、625
10、具有五層結點的二叉平衡樹至少有_______個結點。
A、10 B、12 C、15 D、17
11、對表長為n的線性表進行順序查找，在等概率的情況下，查找成功的平均查找路徑長度是（ ）。
A、 log2n B、 (n+1)/2 C、 n(n+1)/2 D、 n2
12、有一個散列表，表的長度M為100，采用除余法構造散列函數，即：H(k)=K mod P (P<=M)。為使散列函數具有較好的特性，P的選擇應該是（ ）。
A、9 B、95 C、97 D、91
13、設有有序表（5，13，19，21，37，56，64，78，80，88，90），則按折半查找法查找21，須比較（ ）次。
A、4 B、3 C、 2 D、1
22、在等概率的條件下，順序查找法在查找成功時的平均查找長度為（ ）
A、n B、 2n C、 n/2 D、 (n+1)/2
23、下列排序算法中，（ ）算法可能在初始序列有序時，花費的時間反而最多。
A、 堆排序 B、 冒泡排序
C、 快速排序 D、 插入排序
填空題
1、順序查找法的平均查找長度為__________,二分查找法的平均查找長度為_________,分塊查找法(以順序查找確定塊)的平均查找長度為_________,分塊查找法(以二分查找確定塊)的平均查找長度為_________,哈希表查找法采用鏈接法處理沖突時的平均查找長度為_______.
2、 對于長度為n的線性表，若進行順序查找，則時間復雜度為________，若采用二分法查找，則時間復雜度為_________,若采用分塊查找（假定總塊數和每塊長度均接近于n的平方根），則時間復雜度為____________
3、 已知一個有序表(13,18, 24, 35, 47, 50, 62, 83, 90, 115, 134)，當二分檢索值為90的元素時的比較次數是 次。
參考答案
一、 選擇題
1、B 2、B 3、C 4、C 5、D 6、C 7、D 8、B 9、B 10、C
二、填空題
1、 (n+1)/2, ((n+1)*log2(n+1))/n-1, (s2+2s+n)/2s log2(n/s+1)+s/2 1+ɑ
2、 O(n), O(log2n), O(n^1/2)）
內排序
選擇題
1、 在待排序的元素序列基本有序的前提下，效率最高的排序方法是____________
A、插入排序法 B、快速排序法 C、堆排序 D、歸并排序
2、 一組紀錄的排序碼為（46，79，56，38，40，84），則用堆排序法建立的初始堆為_____。
A、79,46,56,38,40,80 B、84,79,56,38,40,46
C、84,79,56,46,40,38 D、84,56,79,40,46,38
3、一組紀錄的排序碼為（46，79，56，38，40，84），則用快速排序法，以第一個記錄為基準得到的一次劃分結果為_____。
A、38，40，46，56，79，84 B、40，38，46，79，56，84
C、40，38，46，56，79，84 D、40，38，46，84，56，79
4、一組記錄的排序碼（25，48，16，35，79，82，23，40，36，72），其中包含有5個長度為2的有序表，按歸并排序的方法對該序列進行一趟歸并后的結果為_________
A、16 25 35 48 23 40 79 82 36 72 B、16 25 35 48 79 82 23 36 40 72
C、16 25 48 35 79 82 23 36 40 72 D、16 25 35 48 79 26 36 40 72 82
5、排序方法中，從未排序序列中依次取出元素與已排序序列(初始時為空)中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為________
A、希爾排序 B、起泡排序 C、插入排序 D、選擇排序
6、排序方法中，從未排序序列中依次取出元素與已排序序列(初始時為空)的一端的方法，稱為________
A、希爾排序 B、起泡排序 C、插入排序 D、選擇排序
7、用某種排序方法對線性表（25，48，21，47，15，27，68，35，20）進行排序時，元素序列的變化情況如下：
（1）、25，48，21，47，15，27，68，35，20
（2）、20，15，21，25，47，27，68，35，84
（3）、15，20，21，25，35，27，47，68，84
（4）、15，20，21，25，27，35，47，68，84
則所采用的排序方法是___________
A、選擇排序 B、希爾排序 C、歸并排序 D、快速排序
8、 下述幾中排序方法中，平均查找長度最小的是________
A、插入排序 B、選擇排序 C、快速排序 D、歸并排序
9、 下述幾種排序方法中，要求內存量最大的是_______
A、插入排序 B、選擇排序 C、快速排序 D、歸并排序
10、快速排序方法在______情況下最不利于發揮其長處。
A、要排序的數據量太大 B、要排序的數據中含有多個相同值
C、要排序的數據已基本有序 D、要排序的數據的個數為奇數
11、在待排序的記錄關鍵字序列基本有序的前提下，下列效率最高的排序方法是（ ）。
A、 選擇排序 B、 插入排序 C、 快速排序 D、 歸并排序
12、在下列排序方法中，（ ）是穩定的排序方法。
A、快速排序 B、堆排序 C、希爾排序 D、歸并排序
13、設有有序表（5，13，19，21，37，56，64，78，80，88，90），則按折半查找法查找21，須比較（ ）次。
A、 4 B、3 C、 2 D、 1
22、設有字符序列{Q、H、C、Y、P、A、M、S、R、D、F、X}，問新序列{F、H、C、D、P、A、M、Q、R、S、Y、X}是下列哪個排序算法一趟掃描的結果。（ ）
A、起泡排序 B、初始步長為4的shell的排序
C、二路歸并排序 D、以第一個元素為分界元素的快速排
填空題
1、在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需比較_____次。
2、在利用快速排序法對一組記錄（54，38，96，23，15，72，60，45，83）進行快速排序時，遞歸調用而使用的棧的所能達到的最大深度為___________,共需遞歸調用的次數為_____，其中第二次遞歸調用是對____________一組進行快速排序。
3、在堆排序，快速排序和歸并排序中，若只從存儲空間考慮，則應首先選取________方法，其次選取_________方法，最后選取___________方法；若只從排序結果的穩定性考慮，則應選取_____________方法；若只從平均情況下的排序最快考慮，則應選取_________方法；若只從最壞情況下排序最快，并且要節省內存考慮，則應選取_________方法。
4、在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數排序中，排序時不穩定的有______________________
5、在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數排序中，平均比較次數最少的排序是______________________，需要內存容量最多的是__________
6、在插入和選擇排序中，若初始數據基本正序，則選用________________;若初始數據基本反序，則選用_______________
7、對n個元素的序列起泡排序時，最少的比較次數是______________.
8、在堆排序、快速排序和歸并排序中，若只從最壞情況下最快并且要節省內存考慮，則應選取 方法。
9、在堆排序和快速排序中，若初始記錄接近正序或反序，則選用 ；若初始記錄基本無序，則最好選用 。
參考答案
一、 選擇題
1、A 2、B 3、C 4、 A 5、C 6、D 7 、D 8、C 9、D 10、C
二、填空題
1、 3
2、 2，4，（23，38，15）
3、 堆排序，快速排序，歸并排序，歸并排序，快速排序，堆排序
4、 希爾排序、選擇排序、快速排序和堆排序
5、 快速排序，基數排序
6、 插入排序，選擇排序
7、 n-1
總結
- 上一篇： 手把手教你制作一个操作系统
- 下一篇： 前端学习（2031）vue之电商管理系统