上海交通大學2023年研究生考試資料結構及程式設計技術試題
一、1〕填空（12分）
函式p（n）判定n是否為質數
p（n）＝ture 如果n是質數
false 如果n不是質數
其中n大於等於2，請在程式劃線處填入正確語句：
type numtype=2 maxitn;
function p1(x,k:numtype):boolean;
begin
if _______then p1:=ture
else p1and
p1(x,k+1)
end;
function p(x:numtype):boolean;
begin
p:=p1(x
end;
2）（8分）
函式f定義如下：
function f(x:integer):integer;
var y,u:integer;
begin
y:=0;u:=1;
while u<=x do
begin
y:=y-1;
u:=u+2*y+1
end;
f:=y
end問：a。f（12）＝？ b。f的功能？
二（20分）
設檔案中存有一語法正確的pascal源程式，其中字母均為小寫。請寫一程式，輸出中第乙個保留字begin所在行。
提示：設open語句格式為
open（《檔案變數》，《檔名》）
三（共30分，每題6分）
1、 已知一棵四次樹，其結點資料場之值為一英文大寫字母。現給出該二叉樹的前序周遊結構（按前序列印資料場之值）及每個結點的次數如下：
前序：a,b,c,f,g,d,h,j,k,m,n,e,i
次數：4,0,2,0,0,1,1,3,0,0,1,0,1,0
試畫一圖形表示該四次樹。
2、 有人說：「佇列和棧都是優先佇列的特殊情況」，這句話對嗎？如果不對，請說明理由。如果正確，回答為什麼並給出如果用優先佇列實現棧和佇列的方法。
3、 已知如圖所示的有向圖，試求出：
每個結點的最早完成時間te值及最晚完成時間tl值。
求出關鍵活動及關鍵路徑。
4、採用多階段合併分類法合併若干條磁帶上的檔案為一有序檔案，當最初合併段不是標準fibonacci數時。可以補充適當的空段。試問，補充的空段在各條磁帶上應如何分布？為什麼？
5、 有一棵完全二叉樹，其葉子結點分布在最下面二層上。設葉子結點個數為l，請問該二叉樹由根至所有葉子結點的路徑長度之和為多少？給出證明。
四（15分）
已知一棵分類二叉樹，其結點資料之值為一正整數。現給定乙個正整數，設計乙個完整的過程刪除設計之值為該正整數的結點並仍保持分類二叉樹的特性不變。
五（15分）
以數偶形式給出乙個無向圖的所有的邊並設該無向圖的頂點的資料之值為一正整數。比如，輸入數偶<1,2>表示資料之值為1及2的兩個結點之間有一條無向邊。設計乙個過程，要求實現：
1、以鄰接多重表的形式存貯該無向圖。2、對該圖進行深度為主的遍歷（列印結點資料場之值）。
碩士研究生入學考試科目《資料結構與程式設計》考試大綱
有些事，明知是錯的，也要去堅持，因為不甘心 有些人，明知是愛的，也要去放棄，因為沒結局 有時候，明知沒路了，卻還在前行，因為習慣了。通訊原理 入學考試初試 複試 大綱 一 考試說明 1.參考教材 通訊原理 第5版 主編 樊昌信，出版社 國防工業出版社，2001 2.題型及分數比例 題型比例 簡答題 ...
2023年資料結構期末考試題及答案
一 選擇題 1 在資料結構中，從邏輯上可以把資料結構分為 c a 動態結構和靜態結構 b 緊湊結構和非緊湊結構 c 線性結構和非線性結構 d 內部結構和外部結構 2 資料結構在計算機記憶體中的表示是指 a a 資料的儲存結構 b 資料結構 c 資料的邏輯結構 d 資料元素之間的關係 3 在資料結構中...
2023年資料結構期末考試題及答案
一 選擇題 1 在資料結構中，從邏輯上可以把資料結構分為 c a 動態結構和靜態結構 b 緊湊結構和非緊湊結構 c 線性結構和非線性結構 d 內部結構和外部結構 2 資料結構在計算機記憶體中的表示是指 a a 資料的儲存結構 b 資料結構 c 資料的邏輯結構 d 資料元素之間的關係 3 在資料結構中...