長沙理工大學計算機與通訊工程學院
2014-2015學年一學期資料結構期末考試試卷(a卷)
班級學號姓名得分
題目部分，(捲麵共有32題,100分,各大題標有題量和總分)
一、應用題(2小題,共16分)
1．乙個線性表為b=（12，23，45，57，20，03，78，31，15，36），設雜湊表為ht[0..12]，雜湊函式為h（key）= key % 13並用線性探查法解決衝突，請畫出雜湊表，並計算等概率情況下查詢成功的平均查詢長度。
2．分析下面各程式段的時間複雜度
（1） s1(int n)
return(s);
}（2） s2(int n)
x=0;
y=0; for (k=1;k<=n;k++)
x++; for (i=1;i<=n;i++) for (j=1;j<=n;j++)
y++;
二、判斷正誤(7小題,共14分)
1．線性鍊錶的刪除演算法簡單，因為當刪除鏈中某個結點後，計算機會自動地將後續的各個單元向前移動。（ ）
2．順序隊和迴圈隊關於隊滿和隊空的判斷條件是一樣的。（ ）
3．**索二叉樹中，任一結點均有指向其前趨和後繼的線索。（ ）
4．設一棵樹t可以轉化成二叉樹bt，則二叉樹bt中一定沒有右子樹。（ ）
5．雜湊技術的查詢效率主要取決於雜湊函式和處理衝突的方法。（ ）
6．資料的邏輯結構和資料的儲存結構是相同的。（ ）
7．邏輯結構與資料元素本身的內容和形式無關。（ ）
三、單項選擇題(10小題,共20分)
1．單鏈表的儲存密度（ ）。
a． 大於1 b． 等於1 c．小於1 d． 不能確定
2．兩個指標p和q，分別指向單鏈表的兩個元素，p所指元素是q所指元素前驅的條件是（ ）。
a．p->next==q->next b．p->next== q c．q->next== p d．p== q
3．字串的長度是指（ ）。
a 串中不同字元的個數 b 串中不同字母的個數
c 串中所含字元的個數 d 串中不同數字的個數
4．線索二叉樹中某結點r沒有左孩子的充要條件是（ ）。
a r.lchild=null b r.ltag=0 c r.ltag=1 d r.rchild=null
5．設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有（ ）。
a 20 b 256 c 512 d 1024
6．下面關於工程計畫的aoe網的敘述中，不正確的是（ ）
a 關鍵活動不按期完成就會影響整個工程的完成時間
b 任何乙個關鍵活動提前完成，那麼整個工程將會提前完成
c 所有的關鍵活動都提前完成，那麼整個工程將會提前完成
d 某些關鍵活動若提前完成，那麼整個工程將會提前完
7．設有向無環圖g中的有向邊集合e=，則下列屬於該有向圖g的一種拓撲排序序列的是（ ）。
a 1，2，3，4 b 2，3，4，1 c 1，4，2，3 d 1，2，4，3
8．設有一組初始記錄關鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關鍵字生成的二叉排序樹的深度為（ ）。
a 4 b 5 c 6 d 7
9．一趟排序結束後不一定能夠選出乙個元素放在其最終位置上的是（ ）。
a 堆排序 b 氣泡排序 c 快速排序 d 希爾排序
10．演算法分析的兩個主要方面是（ ）。
a. 空間複雜性和時間複雜性 b. 正確性和簡明性
c. 可讀性和文件性 d. 資料複雜性和程式複雜性
四、演算法設計題(3小題,共24分)
1．設計判斷單鏈表中元素是否是遞增的演算法。
2．設計兩個有序單鏈表的合併排序演算法。
3．設計乙個求結點x在二叉樹中的雙親結點演算法。
五、填空題(8小題,共16分)
1．可由乙個尾指標唯一確定的鍊錶有（ ）、（ ）。
2．棧的插入和刪除只能在棧的棧頂進行，後進棧的元素必定先出棧，所以又把棧稱為（ ）表；佇列的插入和刪除運算分別在佇列的兩端進行，先進佇列的元素必定先出佇列，所以又把佇列稱為（ ）表。
3．在串 s="structure" 中，以 t 為首字元的子串有（ ）個。
4．二維陣列a[10][20]採用列序為主方式儲存，每個元素佔乙個儲存單元，並且a[0][0]的儲存位址是200，則a[6][12]的位址是
5．一棵二叉樹的第i（i≥1）層最多有（ ）個結點；一棵有n（n>0）個結點的滿二叉樹共有（ ）個葉子結點和（ ）個非終端結點。
6．對n個元素進行氣泡排序，在（ ）情況下比較次數最多，其比較次數為（ ）。
7．圖形結構的元素之間存在（ ）的關係。
8．演算法分析的目的是（ ）
六、簡答題(2小題,共10分)
1．設一數列的輸入順序為123456，若採用堆疊結構，並以a和d分別表示入棧和出棧操作，試問通過入出棧操作的合法序列， 能否得到輸出順序為154623的序列。
2．下列程式段的功能實現子串t在主串s中位置的演算法，要求在下劃線處填上正確語句。
int index(char s[ ], char t[ ])
else
if (j==strlen(t)) return(i-strlen(t)); else return (-1);
}長沙理工大學計算機與通訊工程學院
2014-2015學年一學期資料結構期末考試試卷(a卷)
答案部分，(捲麵共有32題,100.0分,各大題標有題量和總分)
一、應用題(2小題,共10分)
1．查詢成功的平均查詢長度：asl succ=14/10= 1.4
2．o(n) o(n2)
二、判斷正誤(7小題,共14分)
1．錯2．錯
3．錯4．對
5．錯6．錯
7．對。因此邏輯結構是資料組織的主要方面。
三、單項選擇題(10小題,共20分)
1．c2．b
3．c4．c
5．c6．b
7．a8．a
9．d10．a
四、演算法設計題(3小題,共24分)
1．int isriselk(lklist *head)
2．void mergelklist(lklist *ha,lklist *hb,lklist *&hc)
;ha=ha->next;}
else ;hb=hb->next;}
if(ha==0) s->next=hb; else s->next=ha;
}3．typedef struct node bitree; bitree *q[20]; int r=0,f=0,flag=0;
void preorder(bitree *bt, char x)
else
}void parent(bitree *bt,char x)
五、填空題(8小題,共16分)
1．迴圈鍊錶 ，雙鏈表
2．後進先出先進先出
資料結構》期末考試試卷 含答案
一 選擇題 每小題2分，共24分 1 計算機識別 儲存和加工處理的物件被統稱為 a a.資料b.資料元素 c.資料結構d.資料型別 2 棧和佇列都是 a a 限制訪問位置的線性結構b 順序儲存的線性結構 c 鏈式儲存的線性結構d 限制訪問位置的非線性結構 3 鏈棧與順序棧相比，比較明顯的優點是 d ...
2023年資料結構期末考試試卷答案
蝸牛 更多免費學習資料等待您的光臨！資料結構期末考試試卷 a 一 選擇題 每小題2分，共24分 1 計算機識別 儲存和加工處理的物件被統稱為 a a.資料b.資料元素 c.資料結構d.資料型別 2 棧和佇列都是 a a 限制訪問位置的線性結構b 順序儲存的線性結構 c 鏈式儲存的線性結構d 限制訪問...
資料結構2019級期末考試 A
2010級夜大資料結構期末考試試題 a卷 姓名學號序號 成績 注意事項 本試卷滿分100分，考試時間120分鐘 一.單項選擇題，每題有乙個正確選擇。每題2分，共20分 1.下列資料結構中是線性結構。a二叉樹 b 樹 c佇列 d 圖 2.以下關於演算法的說法不正確的是 a 乙個演算法應包含有限個步驟 ...