数据结构相关习题
文章目錄
- 線性結構
- 線性表
- 棧和隊列
- 串和數組、廣義表
- 非線性結構
- 樹
- 圖
- 數據運算
- 查找
- 排序
線性結構
線性表
1、某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用 _______存儲方式最節省運算時間。
A．單鏈表
B．僅有頭指針的單循環鏈表
C．雙鏈表
D．僅有尾指針的單循環鏈表
解答：D
A、B、C：單鏈表只能單向遍歷，只能由鏈表頭向鏈表尾遍歷，因此要找到最后一個元素必須遍歷整個表；
D：要插入結點，只要改變一下指針即可，要刪除頭結點，只要將指針移動到頭結點即可。
2、設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，則選用（）最節省時間。
A.單鏈表
B.單循環鏈表
C.帶尾指針的單循環鏈表
D.帶頭結點的雙循環鏈表
解答：D
在鏈表的末尾插入結點或刪除尾結點時，需要修改其相鄰結點的指針域，因此需要尋找尾結點和尾結點的前驅節點。
A、B：對于單鏈表或單循環鏈表，尋找尾結點的時間復雜度均為O(n)；
C ：對于帶尾指針的單循環鏈表，可以直接通過尾指針定位到尾結點進行插入，時間復雜度為O(1)，但在刪除時還是需要遍歷表來找到尾結點的直接前驅結點，時間復雜度為O(n)；
D：對于帶頭結點的雙循環鏈表，可以通過時間復雜度O(1)直接定位到尾結點或尾結點的前驅節點
3、已知兩個長度分別為m 和 n 的升序鏈表，若將它們合并為一個長度為 m+n 的降序鏈表，則最壞情況下的時間復雜度是（ ）。
A.O(n)
B.O(m+n)
C.O(min(m ,n))
D.O(max(m,n))
解答：D
該算法的思想和有序表合并的算法思想一樣，兩個表比較，一個表比較到頭了，另一個表直接插入表尾。
最好的情況就是較短的表先到頭了，長的表不用比較直接插入到最后，此時時間復雜度為O(min(m ,n))；
最壞的情況就是較長的表先到頭了，短的表不用比較直接插入到最后，此時的時間復雜度為O(max(m ,n))；
4、若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為（ ）(1<=i<=n+1)。
A.O(1)
B.O(n)
C.O(n*n)
D.O(√n)
解答：B
5、判斷：插入和刪除操作是線性表的基本操作。這兩種操作在數組中也經常使用。
解答：錯。數組本身不能進行插入和刪除，因為數組的長度是不可變的。（在某些語言中）
6、線性表有兩種存儲結構：一是順序表，二是鏈表。試問：
（1）如果有 n個線性表同時并存，并且在處理過程中各表的長度會動態變化，線性表的總數也會自動地改變。在此情況下，應選用哪種存儲結構？ 為什么？
（2）若線性表的總數基本穩定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應采用哪種存儲結構？為什么？
7、在單鏈表中設置頭結點的作用是什么？
（1）便于首元結點的處理。首元結點的地址保存在了頭結點的指針域中，則對鏈表的第一個數據元素的操作就可以和其他數據元素的操作一樣，無需特殊化處理。 （2）便于空表和非空表的統一處理。無論是空表還是非空表，頭指針都是指向頭節點的非空指針。棧和隊列
1、數組Q[n]用來表示一個循環隊列，front為當前隊列頭元素的前一位置，rear為隊尾元素的位置，假定隊列元素中的元素個數小于n，計算隊列中元素個數的公式為（）
A.r-f
B.(n+f-r)%n
C.n+r-f
D.(n+r-f)%n
解答：D
當rear>front時，循環隊列的長度：Q.rear-Q.front;
當rear<front時，循環隊列的長度:分為兩類計算 0+Q.rear和MAXSIZE-Q.front即Q.rear-Q.front+MAXSIZE;
總的來說，總長度是(Q.rear-Q.front+MAXSIZE)%MAXSIZE
2、若用一個大小為6的數組來實現循環隊列，且當rear和front的值分別是0和3，當從隊列中刪除一個元素,再加入兩個元素后, rear 和 front 的值分別為（）
A.1 和 5
B.2 和 4
C.4 和 2
D.5 和 1
解答：B
3、判斷：棧和鏈表是兩種不同的數據結構。
解答：錯。 棧是邏輯結構的概念，鏈表是物理存儲結構，二者不是一類事物
4、棧是一種線性表，它的特點是 （ A ） 。設用一維數組A[1,…,n]來表示一個棧，A[n]為棧底，用整型變量T指示當前棧頂位置，A[T]為棧頂元素。往棧中推入（PUSH）一個新元素時，變量T的值 （ B ） ；從棧中彈出（POP）一個元素時，變量T的值（ C ） 。設棧空時，有輸入序列a，b，c，經過PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 （D ） ，變量T的值是（ E ） 。
供選擇的答案：
A： ① 先進先出 ②后進先出 ③進優于出 ④出優于進 ⑤ 隨機進出
B，C： ① 加1 ②減1 ③不變 ④清0 ⑤ 加2 ⑥減2
D： ① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥ a,c
E： ① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2
解答： ② ② ① ⑥ ④
棧是一種線性表，它的特點是 后進先出 。設用一維數組A[1,…,n]來表示一個棧，A[n]為棧底，用整型變量T指示當前棧頂位置，A[T]為棧頂元素。往棧中推入（PUSH）一個新元素時，變量T的值 減1 ；從棧中彈出（POP）一個元素時，變量T的值 加一 。設棧空時，有輸入序列a，b，c，經過PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 a,c ，變量T的值是 n-1 。
5、在做進棧運算時，應先判別棧是否（ A ） ；在做退棧運算時，應先判別棧是否（ B ） 。當棧中元素為n個，做進棧運算時發生上溢，則說明該棧的最大容量為（ C ） 。
為了增加內存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續的內存空間時，應將兩棧的（ D ）分別設在這片內存空間的兩端，這樣，只有當（ E ）時，才產生上溢。
供選擇的答案：
A，B：①空 ② 滿 ③ 上溢 ④ 下溢
C： ①n-1 ② n ③ n+1 ④ n/2
D： ① 長度 ②深度 ③ 棧頂 ④ 棧底
E：①兩個棧的棧頂同時到達棧空間的中心點 ②其中一個棧的棧頂到達棧空間的中心點
③兩個棧的棧頂在達棧空間的某一位置相遇 ④兩個棧均不空，且一個棧的棧頂到達另一個棧的棧底
解答：② ① ② ④ ③
在做進棧運算時，應先判別棧是否 滿 ；在做退棧運算時，應先判別棧是否 空 。當棧中元素為n個，做進棧運算時發生上溢，則說明該棧的最大容量為 n 。
為了增加內存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續的內存空間時，應將兩棧的 棧底 分別設在這片內存空間的兩端，這樣，只有當 兩個棧的棧頂在達棧空間的某一位置相遇 時，才產生上溢。
6、 設有4個數據元素a1、a2、a3和a4，對他們分別進行棧操作或隊操作。在進棧或進隊操作時，按a1、a2、a3、a4次序每次進入一個元素。假設棧或隊的初始狀態都是空。
現要進行的棧操作是進棧兩次，出棧一次，再進棧兩次，出棧一次；這時，第一次出棧得到的元素是 （ A ），第二次出棧得到的元素是 （ B ） ；類似地，考慮對這四個數據元素進行的隊操作是進隊兩次，出隊一次，再進隊兩次，出隊一次；這時，第一次出隊得到的元素是 （ C ） ，第二次出隊得到的元素是 （ D ） 。經操作后，最后在棧中或隊中的元素還有 （ E ） 個。
供選擇的答案： A～D：①a1 ②a2 ③ a3 ④a4 E： ①1 ②2 ③ 3 ④ 0
解答：② ④ ① ② ②
設有4個數據元素a1、a2、a3和a4，對他們分別進行棧操作或隊操作。在進棧或進隊操作時，按a1、a2、a3、a4次序每次進入一個元素。假設棧或隊的初始狀態都是空。
現要進行的棧操作是進棧兩次，出棧一次，再進棧兩次，出棧一次；這時，第一次出棧得到的元素是 a2 ，第二次出棧得到的元素是 a4 ；類似地，考慮對這四個數據元素進行的隊操作是進隊兩次，出隊一次，再進隊兩次，出隊一次；這時，第一次出隊得到的元素是 a1 ，第二次出隊得到的元素是 a2 。經操作后，最后在棧中或隊中的元素還有 2 個。
7、假設一個數組squ[m]存放循環隊列的元素。若要使這m個分量都得到利用，則需另一個標志tag，以tag為0或1來區分尾指針和頭指針值相同時隊列的狀態是“空”還是“滿”。試編寫相應的入隊和出隊的算法。
解答：大致思路：設置tag標志，當隊滿時tag=1；隊空時tag=0。
初始時，令tag=0，如果有元素入隊，執行Q.rear=(Q.rear+1)%MAXSIZE操作，操作執行完畢后Q.rear==Q.front，則證明隊列為滿，修改tag=1。
如果有元素出隊，執行Q.front=(Q.front+1)%MAXSIZE操作，操作執行完畢后Q.rear=Q.front，則證明隊空，修改tag=0。
簡單來說，一開始隊空，tag=0，若從rear一端增加到和front指針相同時，表示入隊已滿，則令tag=1；
若從front一端加到與rear指針相同時，則令tag=0，表示出隊已空。
8、將編號為0和1的兩個棧存放于一個數組空間V[m]中，棧底分別處于數組的兩端。當第0號棧的棧頂指針top[0]=-1時該棧為空；當第1號棧的棧頂指針top[1]=m時，該棧為空。兩個棧均從兩端向中間增長。試編寫雙棧初始化，判斷棧空、棧滿、進棧和出棧等算法的函數。雙棧數據結構定義如下：
typedef struct {int top[2],bot[2]; //棧頂和棧底指針SElemType *V; //棧數組int m; //棧可容納的最大元素 }DblStack;
解答：棧頂指針指向的是棧頂元素，因此大致思路：
棧空時：top[0]=-1;top[1]=m;
棧滿時：top[0]+1=top[1];
左棧進棧：S.top[0]++;S.V[S.top[0]]=e; 左棧出棧：e=S.V[S.top[0]];S.top[0]–;
右棧進棧：S.top[1]–;S.V[S.top[1]]=e; 右棧出棧：e=S.V[S.top[1]];S.top[1]++;
串和數組、廣義表
1、串是一種特殊的線性表,其特殊性體現在()
A.數據元素是一個字符
B.可以順序存儲
C.數據元素可以是多個字符
D.可以鏈接存儲
解答：A
串是一種特殊的、類型受限的線性表,其特殊性體現在數據元素是一個字符。而線性表中每一個元素是屬于某個數據對象的（可以是字符集、實數集等）。
B、D：串可以使用順序存儲，也可用鏈表來存儲。由于串的數據元素是一個字符,它只有8位二進制數, 因此用鏈表存儲時,通常一個結點中存放的不是一個字符,而是一個子串,例如: 在編輯系統中,整個文本編輯區可以看成是一個串,每一行是一個子串,構成一個結點。
2、設矩陣 A 是一個對稱矩陣，為了節省存儲，將其下三角部分按行序存放在一維數組 B[ 1,n(n-1)/2 ] 中，對下三角部分中任一元素 a i,j (i≥j), 在一維數組 B 中下標 k 的值是( )。
A.i(i-1)/2+j-1
B.i(i-1)/2+j
C.i(i+1)/2+j-1
D.i(i+1)/2+j
解答：B
下標從1開始，下三角的元素前面有i-1行，元素個數為1+2+3+……+i-1=i(i-1)/2；位于第j列，本行前面又有j個元素，故一共有i(i-1)/2+j個元素。
3、串 ‘ababaaababaa’ 的naxt數組為（）
A.012345678999
B.012121111212
C.011234223456
D.0123012322345
解答： C
4、串 ‘ababaabab’ 的nextval為( )
A.010104101
B.01002101
C.010100011
D.010101011
解答：A
5、有一個100階的三對角矩陣M，其元素mij(1<=i<=100,1<=j<=100)按行優先次序壓縮存入下標從0開始的一維數組IV中，元素m30,30在IV中的下標是：（）
A. 86
B. 87
C. 88
D. 89
解答：B
對三角矩陣除了第一行和最后一行是每行2個元素外，中間的每行都是三個元素，如圖：
因此m30,30=2+3*28+2=88。由于下標從0開始，因此m30,30在IV中的下標是88-1=87
6、將一個三對角矩陣A[1……100，1……100]按行優先存入一維數B[1…298]中，A中元素A66,65(即該元素下標i=66，j=65)，在B數組中的位置k為()。
A．198
B．195
C．197
D．196
解答：B
圖同上題。k=2+64*3+1=195
7、假設以行優先順序存儲三維數組 R[6][9][6]，其中元素 R[0][0][0]的地址為 2100，且每個元 素占 4 個存儲單元，則存儲地址為 2836 的元素是（ ）。
A.R[3][3][3]
B. R[3][3][4]
C. R[4][3][5]
D. R[4][3][4]
解答：
8、從供選擇的答案中，選出應填入下面敘述 （ ？ ）內的最確切的解答，把相應編號寫在答卷的對應欄內。
有一個二維數組A，行下標的范圍是0到8，列下標的范圍是1到5，每個數組元素用相鄰的4個字節存儲。存儲器按字節編址。假設存儲數組元素A[0,1]的第一個字節的地址是0。
存儲數組A的最后一個元素的第一個字節的地址是 （ A ） 。若按行存儲，則A[3,5]和A[5,3]的第一個字節的地址分別是 （ B ） 和 （ C ） 。若按列存儲，則A[7,1]和A[2,4]的第一個字節的地址分別是 （ D ） 和 （ E ） 。
供選擇的答案：
A～E：①28 ② 44 ③ 76 ④ 92 ⑤ 108 ⑥ 116 ⑦ 132 ⑧ 176 ⑨ 184 ⑩ 188
解答：⑧ ③ ⑤ ① ⑥
A：占用的總的存儲空間=（8-0+1）*（5-1+1）*4=180
最后一個元素的第一個字節的地址=180-4=176
B：按行存儲，Loc（3，5）=0 +【（3-0）*5+（5-1）】*4=76
C：按行存儲，Loc（5，3）=0 +【（5-0）*5+（3-1）】*4=108
D：按列存儲，Loc（7，1）=0 +【（1-1）*9+（7-0）】*4=28
E：按列存儲，Loc（2，4）=0 +【（4-1）*9+（2-0）】*4=116
9、從供選擇的答案中，選出應填入下面敘述 （ ？ ） 內的最確切的解答，把相應編號寫在答卷的對應欄內。
有一個二維數組A，行下標的范圍是1到6，列下標的范圍是0到7，每個數組元素用相鄰的6個字節存儲，存儲器按字節編址。那么，這個數組的體積是 （ A ）個字節。假設存儲數組元素A[1,0]的第一個字節的地址是0，則存儲數組A的最后一個元素的第一個字節的地址是 （ B ） 。若按行存儲，則A[2,4]的第一個字節的地址是 （ C ） 。若按列存儲，則A[5,7]的第一個字節的地址是 （ D ） 。
供選擇的答案：
A～D：①12 ②66 ③72 ④96 ⑤114 ⑥120 ⑦156 ⑧234 ⑨276 ⑩282 (11)283 (12)288
解答：（12）⑩ ③ ⑨
A：體積=（6-1+1）*（7-0+1）*6=288
B：Loc（6，7）=266-6=282
C：Loc（2，4）=0 +【（2-1）*8+（4-0）】*6=72
D：Loc（5，7）=0 +【（7-0）*6+（5-1）】*6=276
10、編寫一個實現串的置換操作Replace (&S, T, V)的算法。
解答：
大致思路：將S中的子串逐個提取出來和T比較，如果提取出的子串和T相等，就把子串之前的串、串V、子串之后的串鏈接在一起。
11、寫出將字符串反序的遞推或遞歸算法，例如字符串為“abcsxw”，反序為“wxscba”
解答：
大致思路：
非線性結構
樹
1、對n(n大于等于2)個權值均不相同的字符構成哈夫曼樹，關于該樹的敘述中，錯誤的是（）
A. 該樹一定是一棵完全二叉樹
B. 樹中一定沒有度為1的結點
C. 樹中兩個權值最小的結點一定是兄弟結點
D. 樹中任一非葉結點的權值一定不小于下一任一結點的權值
解答：A
A.哈夫曼樹是一顆二叉樹，但并不一定是完全的二叉樹。
B.哈夫曼樹中只有度為2的結點和度為0的葉子結點。
C.哈夫曼樹的構造是從下到上，從小到大，所以最小權值的兩個結點一定用于底部，是兄弟結點。
D.哈夫曼樹必須使權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點，任一非葉子結點的權值是等于其自己孩子結點權值之和，因此一定大于或等于下一層的任一結點的權值。
2、判斷：若二叉樹用二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中只有n-1個非空指針域。
解答：對
n個節點的二叉鏈表一共有2n個鏈域，n個節點，分支數為n-1（除了根節點每個結點都有一個分支進入），即非空鏈域有n-1個，那么空鏈域有2n-(n-1)=n+1個
3、已知一棵完全二叉樹的第6層（設根為第1層）有8個葉結點，則完全二叉樹的結點個數最多是（）
A.39
B.52
C.111
D.119
解答：C
第6層有8個葉子結點，如果要結點個數最多，那么就要完全二叉樹一共有7層，前6層是滿的，那么第6層一共有32個結點，其中8個葉子結點，則第7層有（32-8）*2=48個結點。則完全二叉樹的結點個數最多是1+2+4+…+32+48=111
4、將森林轉換為對應的二叉樹，若在二叉樹中，結點u是結點v的父結點的父結點，則在原來的森林中，u和v可能具有的關系是 （）
I．父子關系
II.兄弟關系
III. u的父結點與v的父結點是兄弟關系
A. 只有II
B. I和II
C. I和III
D. I、II和III
解答：B
將森林轉換成二叉樹的步驟：1、樹中所有相鄰兄弟結點之間架一條連線；2、對樹中的每個結點，只保留其與第一個孩子結點之間的連線，刪除其他連線；3、調整樹的形態和角度。
因此，如果在二叉樹中結點u是結點v的父結點的父結點，那么在森林中結點u和結點v是兄弟結點；結點u是結點v的雙親結點
5、已知一棵有2011個結點的樹，其葉結點個數為116，該樹對應的二叉樹中無右孩子的結點個數是（）
A．115
B．116
C．1895
D．1896
解答：
6、 編寫遞歸算法，計算二叉樹中葉子結點的數目。
解答：
大致思路：
7、 寫出求二叉樹深度的算法。
解答：
大致思路：
8、編寫按層次順序（同一層自左至右）遍歷二叉樹的算法。
解答：
大致思路：借助隊列。如果結點存在的話，將其入隊。如果隊不為空，證明仍有結點未被訪問到，就將隊頭元素出隊，訪問隊頭元素。如果隊頭元素，即剛剛訪問過的結點有左右孩子，就將其左右孩子按順序入隊；如果沒有左右孩子，就繼續判斷是否存在沒有訪問過的結點，即判斷隊是否為空。
9、編寫算法判別給定二叉樹是否為完全二叉樹。
解答：
大致思路：
圖
1、圖的BFS生成樹的樹高比DFS生成樹的樹高（）
A.小
B.相等
C.小或相等
D.大或相等
解答：C
對于一些特殊的圖，比如只有一個頂點的圖，其BFS生成樹的樹高和DFS生成樹的樹高相等。而對于一般的圖，（BFS）廣度優先搜索的樹高小于（DFS）深度優先搜索的樹高。
2、若無向圖G=（V,E）中含有7個頂點，要保證圖G在任何情況下都是連通的，則需要的邊數最少是（）
A.6
B.15
C.16
D.21
解答：C
要保證無向圖G在任何情況下都是連通的，即任意變動圖G中的邊，G始終保持連通。考慮極端的情況，圖G的6個頂點構成完全連通子圖G1，即每個點能夠支出的邊是滿的，這樣 6 個點的情況下，邊和點的關系是滿的。則G1有6*5/2=15條邊，再添一條邊第7個頂點必然與G1構成連通圖，所以邊數最小為16。
3、下列關于最小生成樹的說法中，正確的是（）
Ⅰ.最小生成樹的代價唯一
Ⅱ.權值最小的邊一定會出現在所有的最小生成樹中
Ⅲ.用普里姆算法從不同頂點開始得到的最小生成樹一定相同
Ⅳ.使用普里姆算法和克魯斯卡爾算法的得到的最小生成樹總不相同
A.僅Ⅰ
B.僅Ⅱ
C.僅Ⅰ、Ⅲ
D.僅Ⅱ、Ⅳ
解答：A
（1）最小生成樹的形狀不唯一，因為可能存在權值相同的邊，但是代價一定是唯一的。
（2）如果所有邊權值都相同且當邊數>頂點數-1時，則總有權值最小的邊不能出現在最小生成樹中。
（3）如果多條邊權值相同，那么從不同頂點出發得到的最小生成樹就不一定相同。
（4）可能相同也可能不相同。
4、下圖所示的AOV網表示一項包含8個活動的工程。通過同時加快若干活動的進度可以縮短整個工程的工期。下列選項中，加快其進度就可以縮短工程工期的是（）
A.c 和 e
B. d 和 e
C. f和 d
D. f 和 h
解答：C
一共有三條關鍵路徑，bfh、bdeh和bdcg，三條均為27。只有所有關鍵路徑上的活動時間同時減少，才能縮短工期。縮短f可以縮短bfh這條路徑，縮短d則可以縮短bdcg和bdeh這兩條路徑，其他選項無法使三條一起縮短。
5、如果n個頂點的圖是一個環，則它有____ 棵生成樹。
解答：n
n個頂點形成的環有n條邊，若得到生成樹只需要刪除這n條邊中的任意一條即可，所以得到n棵生成樹。
6、編寫算法，由依次輸入的頂點數目、弧的數目、各頂點的信息和各條弧的信息建立有向圖的鄰接表。
解答：
//---------------------鄰接表----------------------------- //邊結點 typedef struct ArcNode {int adjvex; //該邊所指向的頂點位置struct ArcNode * nextarc; //指向下一條邊的指針 }ArcNode;//頂點信息 typedef struct VNode {VerTexType data; //頂點值ArcNode * firstarc; //指向第一條依附該頂點的邊的指針 }VNode,AdjList[MVNum]; //AdjList表示鄰接表類型//鄰接表 typedef struct {AdjList vertices;int vexnum,arcnum; //圖的當前頂點數和邊數 }ALGraph;//有向圖的鄰接表，依次輸入的頂點數目、弧的數目、各頂點的信息和各條弧的信息 Status Build_AdjList(ALGraph &G) {int vnum,anum;cout<<"請輸入頂點數目：";cin>>vnum;if(vnum<0){cout<<"頂點數不能為負！！"<<endl;return ERROR;}G.vexnum=vnum;cout<<"請依次輸入頂點的名稱：";for(int i=0;i<G.vexnum;i++){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL; //初始化表頭結點的指針域為NULL} //------------------------------------------------- cout<<"請輸入弧的數目：";cin>>anum;if(anum<0){cout<<"弧數不能為負！！"<<endl;return ERROR;}G.arcnum=anum;cout<<"請依次輸入各邊依附的兩個頂點："<<endl;for(int i=0;i<G.arcnum;i++){int v1,v2;cin>>v1,v2;//找到兩頂點在鄰接表中的位置int i=LocateVex(G,v1);//LocateVex()是返回頂點v在圖G中的位置的函數int j=LocateVex(G,v2);ArcNode *p1=new ArcNode; //生成一個新的邊結點p1p1->adjvex=j;//邊p1所指向的頂點位置為j//將新結點*p1插入頂點vi的邊表頭部p1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1;ArcNode *p2=new ArcNode; //生成一個新的邊結點p2p2->adjvex=i;//將新結點*p2插入頂點vj的邊表頭部p2->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2;}return OK; }7、試在鄰接矩陣存儲結構上實現圖的基本操作：DeleteArc(G,v,w) ，即刪除一條邊的操作。
解答：
//-------------------鄰接矩陣---------------------------- typedef struct {VerTexType vexs[MVNum]; //頂點表ArcType arcs[MVNum][MVNum]; //鄰接矩陣int vexnum,arcnum; //圖得當前點數和邊數 }AMGraph;//刪除一條邊 Status DeleteArc(AMGraph &G,int v,int w) {if(LocateVex(G,v)<0 || !LocateVex(G,w)<0)return ERROR;G.arc[v][w]=0;G.arc[w][v]=0;G.arcnum--;return OK; }8、試基于圖的深度優先搜索策略寫一算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點vi到頂點vj的路徑（i≠j）
解答：
大致思路：可以利用深度優先搜索遍歷的算法遞歸遍歷鄰接表來進行判斷。引入變量level來記錄遞歸的層數，設置visited[n]為訪問標志數組，已訪問的頂點的值記為true。遞歸算法結束的條件為頂點vi=vj，表明首位相遇，存在路徑。如果遞歸結束的條件不成立，則從vi邊鏈表的第一個邊結點開始，獲取vi的鄰接點，對vi的尚未訪問的鄰接點遞歸調用。遞歸進行一次，level的值增加1。如果遞歸之后level的值為1，表明vi到vj不存在路徑。
數據運算
查找
| 順序查找 | O(n) | 對表結構無任何要求，既適用于順序結構，也適用于鏈式結構，無論記錄是否按關鍵字有序均可應用，但效率較低，不適合n很大的情況 |
| 折半查找 | O( log2(n)) | 比較次數少，查找效率 ，但必須采用順序存儲結構，而且表中的元素按關鍵字有序排列；不適合于數據元素經常變動的線性表 |
| 分塊查找 | O( log2(n)) | 要求塊間有序，塊內無序 ；既能較快查找，又能適用于動態變化的要求。查詢效率介于順序查找和折半查找之間 |
| 二叉排序樹查找 | O( log2(n)) | 數據要是二叉排序樹存儲 。二叉排序樹的查找過程與折半查找過程類似，查找效率在平均情況下相同，但因采用樹的二叉鏈表表示，因此適合經常做插入和刪除的動態查找表。二叉排序樹在形態均勻時性能最好，而形態為單支樹時查找性能退化為與順序查找相同 |
| 哈希查找 | 最理想的情況下：O(1) | 需要創建哈希表，根據鍵值方式(Key value)進行查找，通過哈希函數，定位數據元素。 |
1、對22個記錄的有序表進行折半查找，當查找失敗時，至少需要比較（）次關鍵字
A.3
B.4
C.5
D.6
解答：B
22 個記錄的有序表，其折半查找的判定樹深度為 log2(22) + 1=5，且該判定樹不是滿二叉樹，即查找失敗時至多比較 5 次，至少比較 4 次
2、在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡結點為A，并已知A的左孩子的平衡因子為0右孩子的平衡因子為1，則應作（ ）型調整以使其平衡。
A．LL
B．LR
C．RL
D．RR
解答：C
1.插入點位于A的左孩子的左子樹中:LL 右旋。
2.插入點位于A的右孩子的右子樹中:RR 左旋。
3.插入點位于A的左孩子的右子樹中:LR 較低的先左旋，再右旋。
4.插入點位于A的右孩子的左子樹中:RL 較低的先右旋，再左旋。
在本題中：A是最低的不平衡點，A的左孩子的平衡因子為0，右孩子的平衡因子為1，如果插入一個結點，變成不平衡，那么只能在右孩子的左孩子下面插入結點，使A的右孩子平衡因子變為2。即插入結點的位置符合的是 RL。因而需要做RL調整。
3、在下圖所示的平衡二叉樹中，插入關鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關鍵字37所在節點的左邊、右子結點中保存的關鍵字分別是（）
解答：C
插入一個新的結點之后，變成了：
沿著葉子結點45往上走，查找到的第一個不平衡的結點為24，其平衡因子為-2.53是24的右孩子，37是53的左孩子，因此這是一個RL型不平衡。于是先把53順時針旋轉到37的右孩子，再把24逆時針旋轉到37的左孩子。得到：
剩下的48按照平衡二叉樹中序遍歷遞增的原則，48掛在53的左孩子處。最后得到：
4、若平衡二叉樹的高度為6，且所有非葉子結點的平衡因子均為1，則該平衡二叉樹的結點總數為（）
A.12
B.20
C.32
D.33
解答：B
平衡二叉樹的最小結點數：f(n)=f(n-1)+f(n-2)+1。其中 f(1)=1, f(0)=0。（n為深度）
深度為2時，f(2)=f(1)+f(0)+1=2；f(3)=f(2)+f(1)+1=4;
以此類推得到： f(4)=7,f(5)=12,f(6)=20。
5、折半搜索與二叉排序樹的時間性能（）
A.相同
B. 完全不同
C. 有時不相同
D. 數量級都是O（log2n）
解答：C
不一定相同。 二叉排序樹不一定是平衡樹，它是只要求了左右子樹與根結點存在大小關系，但是對左右子樹之間沒有層次差異的約束，因此通過二叉排序樹進行查找不一定能夠滿足logn的，例如一棵只有多層左子樹的二叉排序樹。 只有是一棵平衡的二叉排序樹時，其查找時間性能才和折半查找類似。
6、
7、設哈希（ Hash ）表的地址范圍為 0 ～ 17 ，哈希函數為： H （ K ）＝ K MOD 16 。 K 為關鍵字，用線性探測法再散列法處理沖突，輸入關鍵字序列：(10，24，32，17，31，30，46，47，40，63，49）造出Hash表，試回答下列問題：
⑴畫出哈希表的示意圖；
⑵若查找關鍵字63，需要依次與哪些關鍵字進行比較？
⑶若查找關鍵字60，需要依次與哪些關鍵字比較？
⑷假定每個關鍵字的查找概率相等，求查找成功時的平均查找長度。
解答：
8、折半查找適不適合鏈表結構的序列，為什么？用二分查找的查找速度必然比線性查找的速度快，這種說法對嗎？
解答：（1）不適合。折半查找只適合順序存儲的有序表，單鏈表搜索時只能從頭結點開始逐步向后搜索。
（2）不對。二分查找的速度在一般情況下會快一些，但是在某些特殊情況下，如要查找的元素位于表中的第一個，這時線性查找的速度就更快些。
排序
1、對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列進行同樣的排序操作，直到子序列為空或只剩下一個元素為止。這樣的排序方法是（）。
A. 直接選擇排序
B. 直接插入排序
C. 快速排序
D. 冒泡排序
解答：C
2、將 5 個不同的數據進行排序，至多需要比較（ ）次。
A. 8
B. 9
C.10
D. 25
解答：C
首先隨便選擇一個數為基數，再選擇一個數和它比較就是1次，選擇第三個數最多比較2次就可以確定位置，選擇第四個數最多比較3次就能夠確定位置，最后一個數最多比較4次同樣可以確定位置。因此最多一共比較1+2+3+4=10
總結
- 上一篇： 企业10大HR软件分析对比(精)
- 下一篇： 数据库挖掘