1、*學院學期期末試題數據結構(C語言) 一選擇題（102分）：共10小題，請將答案填入題中的括號中，每小題只有一個正確答案，錯選或不選均不給分。1組成數據的基本單位是（ ）數據項 數據類型C數據元素 D數據變量2下面程序段的時間復雜度為（ ）。 for(i=1;i=n;i+) for(j=i;jnext=p-next-next Bp=p-nextCp=p-next-next Dp-next=p5若讓元素1，2，3依次進棧，則出棧次序不可能出現（ ）種情況。 A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，26在一個循環順序隊列中，隊首指針指向隊首元素的（ ）位置。A、當前 B、后面

2、C、前一個 D、后一個7假定一個鏈隊的隊首和隊尾指針分別為front和rear，則判斷隊空的條件是（ ）。A、front=NULL B、front!=NULL C、rear!=NULL D、front=rear8二叉樹第i(i1)層最多有（ ）個結點。 A2i B 2i-1 C2i D2i -19如果結點A有3個兄弟，而且B為A的雙親，則B是度為（ ）4 3C5 D110當待排序序列的關鍵碼是隨機分布時，下列哪種排序算法的平均時間復雜度最優（ ）。A直接插入排序 B直接選擇排序C快速排序 D冒泡排序二填空題（30分）：每空2分1. 數據的邏輯結構被分為 、 、 和 四種。2在一個長度為n的順序

3、表中插入一個元素，最少需移動 個元素，最多需移動_個元素。3雙向循環鏈表的優點是 4隊列的原則是 。5順序存儲的隊列如果不采用循環方式，則會出現 問題。6具有64個結點的完全二叉樹的深度為 。7設一顆完全二叉樹共有50個葉子結點，則它共有_個度為2的結點。8二叉樹采用_序遍歷可以得到結點的有序序列。9在一個具有n個頂點的無向完全圖中，包含有 條邊，在一個具有n個頂點的有向完全圖中，包含有 條邊。 10快速排序算法在最差的情況下其時間復雜度是 。三判斷題（52分）1任意一棵滿二叉樹一定也是完全二叉樹。( )2進棧操作時，必須判斷棧是否已滿。( )3一個程序的時間復雜度是指該程序運行時間與問題規模

4、的對應關系。( )4采用鏈式結構存儲線性表時，其地址可以是不連續的。( )5折半查找法的前提之一是線性表有序。( ) 四應用題（45分）1 試比較順序存儲和鏈式存儲的優缺點。（5分）2 簡述棧和隊列這兩種數據結構的相同點和不同點。（5分）3 已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG和DECBHGFA，試畫出這棵二叉樹。（5分）4 對于給定的一組關鍵碼：83，40，63，13，84，35，畫出用冒泡排序對上述序列進行操作的各趟結果。（5分）五算法設計題（20分）1編寫算法，將任意十進制數轉換成其他進制，要求寫出完整代碼，可采用順序棧或鏈棧實現。（12分）2編寫一算法完成瑟夫生死者

5、游戲。（8分）瑟夫生死者游戲的描述：N個旅客同乘一條船，因為嚴重超載，加上風浪大，危險萬分；因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無奈，大家只得同意這種辦法，并擬定N個人圍成一圈，由第一個人數起，依次報數，數到第r人，便把他投入海中，然后再從他的下一個人數起，數到第r人，再將他仍進海里，如此循環的進行，直到剩下N/2個乘客為止。問哪些位置是將被扔下大海的位置。8答案及評分標準：數據結構(C語言)答案及評分標準一選擇題（102分）：每小題只有一個正確答案，錯選或不選均不給分。12345678910CDBACCDBAC二填空題（30分）：每空2分。1集合 線性結構 樹

6、型結構 圖型結構 20 n3既可以方便的找到后繼結點又可以方便的找到前驅結點。4先進先出5假溢出677498中9n(n-1)/2 n(n-1)10O(n2)。三判斷題（52分）1；2；3；4；5四應用題（45分）1順序存儲查找效率高，插入和刪除效率低；鏈式存儲插入和刪除效率高，查找效率低。2棧和隊列都是操作受限的線性表。棧是先進后出，操作在一端進行；隊列是先進先出，插入在一端，刪除在另一端進行。3HBFCADEA4 83 40 63 13 84 35 13 83 40 63 35 84 13 35 83 40 63 84 13 35 40 83 63 84 13 35 40 63 83 84

7、13 35 40 63 83 84五算法設計題（20分）1（12分）#define Maxsize 100typedef struct int dataMaxsize; int top;SeqStack;SeqStack *Init_SeqStack() SeqStack *s; s=(SeqStack *)malloc(sizeof(SeqStack); s-top=-1; return s;/*入棧*/int Push_Seqstack(SeqStack *s,int x) if(s-top=Maxsize-1)return 0; else s-top+; s-datas-top=x; r

8、eturn 1; /*出棧*/int Pop_SeqStack(SeqStack *s,int *x) if(Empty_SeqStack(s) return 0; else *x=s-datas-top; s-top-; return 1; /*判空棧*/int Empty_SeqStack(SeqStack *s) if(s-top=-1) return 1; else return 0;void conversion(int N,int r) SeqStack *p; int y; p=Init_SeqStack(); while(N) if(Push_Seqstack(p,N%r)=1

9、) N=N/r; else break; while(!Empty_SeqStack(p) Pop_SeqStack(p,&y); printf(%d,y); void main() int M,t; printf(please input a number:n); scanf(%d,&M); printf(please input t:n); scanf(%d,&t); conversion(M,t); getch();2（8分）typedef struct node int data; struct node *next;ListNode,*LinkList;LinkList Create

10、List(int n);void DeleteNode(LinkList L,int n,int k);void PrintList(LinkList L);main() int n,k; LinkList H; printf(請輸入總人數：); scanf(%d,&n); printf(請輸入報數上限:); scanf(%d,&k); H=CreateList(n); DeleteNode(H,n,k); PrintList(H); getch(); LinkList CreateList(int n) int i; LinkList L=NULL; ListNode *s,*R=NULL; for(i=1;idata=i; if(L=NULL) L=s; else R-next=s; R=s; if(L!=NULL) R-next=L; return L;void DeleteNode(LinkList L,int n,int k) int i,j=0; ListNode *q,*p=L; printf(不幸投入大海的有：); for(i=1;i=n/2;i+) for(j=1;jnext; q=p-next; p-next=q-next; printf(%4d,q-data); if(i%10=0) printf(n); free(q); p=p-next