雲南師範大學2013—2014學年上學期統一考試
_《資料結構》__期中試卷
學院_旅地學院_專業_gis_ 年級_11_ 學號姓名
考試方式（閉卷或開卷）：閉卷考試時量：90分鐘試卷編號（a、b卷）：a
一、 單項選擇題（每小題2分，共30分）
1、 評價乙個演算法時間效能的主要標準是
a 演算法易於除錯b 演算法易於理解
c演算法的時間複雜度d 演算法的穩定性和正確性
2、 資料結構通常是研究資料的
a邏輯結構和儲存結構b儲存和抽象
c抽象和操作d邏輯與操作
3、 設兩個字串的串值分別為s1=「abcdefg」,s2=「pqrst」，則strconcat (t,s1,s2)則新串t的結果
a abcdefgpqrstb bcdefg
c bcpqrstd bcdefef
4、 設有一順序棧s，元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素出棧的順序是s2,s4,s3,s6,s5,s1，則棧的容量至少應該是
a 2b 3
c 4d 5
5、 廣義表c=(a,(b,c,d))的元素為
a a,(b,c,db a, b,c,d
c a,(b,c),dd （a,b）,c,d
6、 for（i=1；i<=n；i++）
for（j=1；j<=n；j++）
以上程式段的的時間複雜度為
a o(n3b o(n2)
c o(nd o(1)
7、 對於乙個頭指標為h的帶頭結點的單鏈表，判定該錶為空表的條件是（ ）
a h==nullb h!=null
c h→next ==hd h→next==null
8、 在單鏈表中，兩個指標q和p分別指向單鏈表的兩個元素，p所指的元素是q所指元素的前驅的條件是
a q->next = = p->nextb p->next = = q
c q->next = = pd p = =q
9、 可用帶表頭結點的鍊錶來表示表，也可用不帶表頭結點的鍊錶來表示表，前者的主要好處是
a 可以加快對錶的遍歷b 使空表和非空表的處理統一
c 提高訪問結點的速度d 節省儲存空間
10、 稀疏矩陣一般的壓縮儲存有兩種，即
a 一維陣列和二維陣列b 一維陣列和三元組
c 二維陣列和十字鍊錶d 三元組和十字鍊錶
11、 若進棧序列為a,b,c,d,進棧過程中可以出棧,則不可能出棧的乙個序列是（）
a cbadb bdca
c cdbad adbc
12、 資料結構中,與所使用的計算機無關的是資料的下列哪種結構
a 順序b 物理
c 邏輯d 儲存
13、 對於乙個頭指標為h的帶頭結點的單鏈表，判定該錶為空表的條件是（ ）
a h==nullb h!=null
c h→next ==hd h→next==null
14、 在乙個順序表中，若表的第乙個元素的儲存位址是210，每乙個元素的長度為3，則第5個元素的儲存位址是
a 219b 225
c 222d 228
15、 迴圈佇列用陣列a[m]存放元素，已知其頭尾指標分別為front和rear，則當前佇列中的元素個數是
a rear-front+1b rear-front-1
c rear-frontd (rear-front+m) % m
2 填空題（每小題2分，共30分）
1是資料的基本單位，有時也稱之為結點、元素、頂點、記錄等。
2、 乙個資料元素可由若干個組成。
3、 鍊錶相對於順序表的優點有在進行資料元素插入和刪除操作時不需要和在需要空間時可以臨時開闢。
4、 資料結構被形式地定義為（d, r），其中r是d上的有限集合。
5、 順序表示的線性表中，每個資料元素占用n個儲存單元，第乙個元素的位置用loc(a1)表示，則第i個資料元素儲存位置loc(ai
6、 在長度為n的順序表中刪除乙個元素時,等概率情況下的平均移動元素的次數是
7、 僅允許在表的同一端進行插入和刪除運算的線性表被稱為
8、 兩個串相等的充分必要條件是
9、 棧中能進行插入刪除的一端叫另一端稱為
10、 棧也稱為的線性表。
11、 佇列中能進行插入的一端叫能進行刪除的一端叫
12、 串是一種特殊的線性表，是資料元素型別為線性表
13、 一般對於二維陣列有兩種儲存方式
14、 c＝（a，（b，c，d））為一長度為的廣義表。
15、 用鍊錶表示線性表,表中元素之間的邏輯關係是通過鍊錶中結點的來實現的。
3 演算法設計題（每題10分，共20分）
1、 以下函式是對線性表的操作，請填空使函式完整（不改變原結構）。
#include <>
typedef struct nodelnode;
lnode *search(lnode *h,int i) /***性表h中查詢第i個節點，成功返回其指標，否則返回空*/
if((p=='\0') || j>i)
return (null);
}void insert(lnode *h,int x,int y) /***性表h中值為x的節點前插入y，若x不存在則插入在最後*/
if(p!=null)
int delete(lnode *h,int i) /***性表h中刪除第i個節點，成功返回1，否則0*/
if(!p) return 0;
free(p);
h->data--;
return 1;
}2、 以下程式是利用棧的特性將十進位制數x轉換為h進製，請填空使程式完整（不改變程式的結構）。
#define m 100
typedef struct
sqstack;
void init(sqstack *s)/*初始化棧*/
int empty(sqstack *s) /*棧為空返回1，否則返回0 */
int pop(sqstack *s,int *y) /*出棧*/
main()
printf("\n");
while(!empty(a))
if(*y<10)
printf("%d",*y);
else
printf("%c",*y-10+97);
}}4 應用題（每小題10分，共20分）
1、 以下程式是稀疏矩陣的轉置，請填空使程式完整（不改變程式的結構）。
#include<>
#include<>
#define m 100
#define row 20 /*稀疏矩陣的行*/
#define col 30 /*稀疏矩陣的列*/
typedef structtriple三元組結構*/
typedef structtsmatrix;
void datain(tsmatrix *m)
ij}m->mu=row;m->nu=col;
m->tu=n-1;
}void dataout(tsmatrix m)
}int trans(tsmatrix m,tsmatrix *t){ /*轉置函式:m轉置為t*/
int q,col,p;
資料結構試卷 A
密封線密封線 考生姓名准考證號原所在單位 嘉應學院考試卷 a 電腦科學與技術專業資料結構試題 題號得分評卷人 二 判斷題 本大題共10小題，每小題1.5分，共15分，正確的在答題框內打上 t 錯誤的在答題框內打上 f 題號答案12 3456 78910 得分一二三 四五六七 總分複核人 一 單選題 ...
《資料結構》課程模擬試卷2019
學號姓名教師得分 一 填空 30分左右 1.由85個節點構成的完全二叉樹，其深度為其中第6層的節點數為 個。2 關鍵字1，2，3，5，13，18，27，對其進行折半查詢，那麼查詢關鍵字13的比較次數是 次。3 有一棵二叉樹，它的中序遍歷為 4，5，2，1，6,3，前序遍歷為 1，2，4，5，3，6那...
《資料結構》模擬試卷一
a.98b.99c.50d.48 8 下列序列中，a 是執行第一趟快速排序後得到的序列 排序的關鍵字型別是字串 a.da ax eb de bb ff ha gc b.cd eb ax da ff ha gc bb c.gc ax eb cd bb ff da ha d.ax bb cd da ff...