1樓：百度文庫精選
內容來自使用者:廖德娟_2011
資料結構輔導試題一
一、簡答問題：
1．四類資料結構
2．線性結構與非線性結構有何差別？
3．簡述演算法的定義與特性。
4．設有1000個無序元素，僅要求找出前10個最小元素，在下列排序方法中（歸併排序、基數排序、快速排序、堆排序、插入排序）哪一種方法最好，為什麼？
二、判斷正誤：（每小題1分，共5分）正確在（）內打√，否則打。1．（）二叉排序樹或是一棵空樹，或是具有下列性質的二叉樹：
若它的左子樹非空，則根結點的值大於其左孩子的值，
若它的右子樹非空，則根結點的值大於其右孩子的值。
2．（）索引順序表的特點是塊內可無序，塊間要有序。
3．（）子串是主串中任意個連續字元組成的序列。
4．（）線性結構只能用順序結構存放，非線性結構只能用鍊表存放。
5．（）快速排序的樞軸元素可以任意選定。
三、單項選擇題：(每小題1分，共4分)
1．棧s最多能容納4個元素。現有6個元素按a、b、c、d、e、f的順序進棧,問下列哪乙個序列是可能的出棧序列?
a)e、d、c、b、a、f b)b、c、e、f、a、d
c)c、b、e、d、a、f d)a、d、f、e、b、c
2．將一棵有100個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點編號為1，則編號為49的結點的左孩子的編號為：a3．9. p->next==la 10.
> key = k; s-> lchild = null; s-> rchild
2樓：劇桃戰碩
一.判斷題
（）1.某線性表採用順序儲存結構，元素長度為4，首位址為100，則下標為12的（第13個）元素的儲存位址為148。
正確。第0個元素位址為100，則第i個元素位址為100+4*i，將12代入得148。
（）2.在任何一種線性鍊表上都無法進行隨機訪問。
錯誤。比如只要知道順序表首位址和每個資料元素所佔儲存單元的個數，就可以求出第i個資料元素的儲存位址來，這也是順序表具有按資料元素的序號隨機訪問的特點。
（）3.順序棧是一種規定了元素進棧順序的棧。
錯誤。按儲存結構來分，堆疊分為順序棧和鏈棧，其中棧的順序儲存結構簡稱為順序棧，它是運算受限的順序表，卻並沒有規定元素進棧順序。
（）4.迴圈列表中每乙個元素都有後繼。
正確。注意，這裡可能有筆誤，應寫為「迴圈鍊表」而非「迴圈列表」。
（）5.刪除乙個二叉樹中的乙個結點，再重新插入上去，一定能得到原來的二叉排序樹。
錯誤。二.填空題。
6.下面程式的時間複雜度為___________。
for(int
i=1;
i<=m;
i++)
for(int
j=1;
j<=n;
j++)
s+=i
法則1：for迴圈：乙個for迴圈的執行時間至多是該for迴圈內語句（包含測試）的執行時間乘以迭代的次數。
法則2：巢狀迴圈：從裡向外分析這些迴圈。在一組巢狀迴圈內部的一條語句總的執行時間為該語句的執行時間乘以該組所有迴圈的大小的乘積。
對於此處巢狀的for迴圈，根據以上法則，時間複雜度為o(m*n)。
7.在長度為n的順序表的第i（1≤i≤n+1）個位置上插入乙個元素，元素的移動次數是____________。
從第i個元素（原來的）到第n個元素，每個元素後移一位，一共需要n+1-i次。
8.在乙個具有n個結點的有序單鏈表中插入乙個新結點，並讓插入後的單鏈表仍然有序，則該操作的時間複雜性數量級為______。
找到節點位置，o(n)；單鏈表插入操作，o(n)；總的時間複雜度為o(n+n)=o(n)。
9.若用s[1]～s[n]作為兩個順序棧的共同儲存空間，左右兩個棧的棧頂分別為t1和t2，則判斷某個棧是否可以插入新元素的條件是_________________。
當程式中同時使用兩個棧時，可以將兩個棧的棧底設在向量空間的兩端，讓兩個棧各自向中間延伸。當乙個棧裡的元素較多，超過向量空間的一半時，只要另乙個棧的元素不多，那麼前者就可以占用後者的部分儲存空間。
此處判斷某個棧是否可以插入新元素的條件是&t1!=&t2
10.設森林t中有三棵樹，第一，二，三棵樹的結點個數分別為n1,n2,n3,將森林轉換成二叉樹後，其根結點的左子樹上有____________個結點。
將乙個森林轉換為二叉樹的具體方法是：①
將森林中的每棵樹變為二叉樹；②
因為轉換所得的二叉樹的根結點的右子樹均為空，故可將各二叉樹的根結點視為兄弟從左至右連在一起，就形成了一棵二叉樹。
個人認為此處可以填3個答案，n1-1或者n2-1或者n3-1。
11.在帶權值有向圖的鄰接矩陣中，第i行上非零元素的個數等於_______________。
當節點vi與某節點vj相鄰接,則a(i,j)取非0值。
12.在各種查詢方法中，平均查詢長度與結點個數n無關的查詢方法是_____________。
雜湊（hash）查詢。
資料結構考題
3樓：凌雲紫冥
答案保證正確，
1、在雙向迴圈鍊表的p所指結點之後插入s所指結點的操作是（d）。
ap->right=s;s->left=p;p->right->left=s;s->right=p->right;
bp->right=s;p->right->left=s;s->left=p;s->right=p->right;
cs->left=p;s->right=p->right;p->right=s;p->right->left=s;
ds->left=p;s->right=p->right;p->right->left=s;p->right=s;
2、二維陣列a中，每個元素的長度為3個位元組，行下標i從0到7，列下標j從0到9，從首位址sa開始連續存放在儲存器內，存放該陣列至少需要的位元組數是（c）。
a80b100
c240
d270
3、在乙個單鏈表中，若刪除p所指結點的後續結點，則執行（a）。
ap->next=p->next->next;
bp=p->next;p->next=p->next->next;
cp->next=p->next;
dp=p->next->next；
4、資料結構ds(data struct)可以被形式地定義為ds=（d，r），其中d是（b）有限集合，r是d上的關係有限集合。
a演算法b資料元素
c資料操作
d資料物件
5、不帶頭結點的單鏈表head為空的判定條件是（a）。
ahead= =null
bhead->next= =null
chead->next= =head
dhead!=null
資料結構練習題，資料結構考試題
這幾年級的題啊 出士 6.c 7.不懂 8.a 9.b 10.d 11.d 12.d 資料結構考試題 void inorder bitree root else 這就是中序遍歷的演算法 include include define maxsize 64 typedef char datatype t...
資料結構試卷，資料結構試題及答案
給你找了一份自考的資料結構試卷和答案試卷 http content.edu edu.com.cn res 2006 11 16 00000d2t.shtml答案 http edu.資料結構試題及答案 文庫精選 內容來自使用者 go你好陌生人 資料結構試卷 一 填空殖 每空1分共20分 1.資料的物理...
資料結構概論試題求解，資料結構概論 試題求解
1.c 2.c.3.c 4.c 5.a 6.a 7.b 8.b 9.b 10.b 11.a 12.b 13.b 14.b 15.b 16.a 17.c 18.d 19.c 20.d 21.b 22.c 23.b 2,b,乙個串的子串數目為 連續字元相加的和，以及空串，即 8 7 6 5 4 3 2 ...