1. 哪位大俠有新版農大《數據結構》和《C#》在線作業答案可否貢獻一下
一 單項選擇題
1.
設有數據邏輯結構為：Data=(D,R);
D={d1,d2,d3,d4,d5,d6,d7 }
R={<d1,d2>,<d2,d1>,<d1,d4>,<d4,d1>,<d2,d3>,<d3,d2>,<d2,d6>,<d6,d2>,<d2,d7>,<d7,d2>,<d3,d7><d7,d3><d4,d6><d6,d4>,<d5,d7>,<d7,d5>}
試分析該數據結構屬於哪種邏輯結構？（ c）
(5.0 分)
a 圖結構
b 線性邏輯結構
c 網路結構
d 樹結構
2.
判斷下列程序段的時間復雜度數量級（b ）。
for(i=1;i<n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;
(5.0 分)
a O(1)
b O(n3)
c O(n2)
d O(n)
3.
在一個長度為n的順序存儲線性表中，向第i個元素（1<=i<=n+1）位置插入一個新元素時，需要從後向前依次後移（a ）個元素。
(5.0 分)
a n-i+1
b i
c n-i
d n-i-1
4.
在一個單鏈表中，若要在p所指向的結點之後插入一個新結點，則需要相繼修改（d ）個指針域的內容。
(5.0 分)
a 3
b 4
c 1
d 2
5.
當利用大小為N的數組順序存儲一個棧時，假定用top==N表示棧空，則向這個棧插入一個元素時，首先應執行（b ）語句修改top指針。
(5.0 分)
a top=0
b top--
c top=N-1
d top++
6.
在規定順序環形隊列一般狀態隊頭指針指向第一個數據元素之前的空位，隊尾指針指向末尾元素的前提下，假定一個順序循環隊列的隊首和隊尾指針分別用front和rear表示，則判斷隊空的條件為（b ）。
(5.0 分)
a rear+1 == front
b front+1 == rear
c front == 0
d front == rear
7.
下述編碼中不是前綴編碼的是（a ）。
(5.0 分)
a {0,01,00,11}
b {1,01,000,001}
c {0,10,110,111}
d {00,01,10,11}
8.
在一棵二叉樹上第5層的結點數最多為（c ）。
(5.0 分)
a 32
b 8
c 16
d 15
9.
Huffman樹是帶權路徑長度最小的數，樹中權重（b ）的結點，距離根結點（ ）。
(5.0 分)
a 較高，較遠
b 較高，較近
c 較低，較近
10.
在一個具有n個頂點的有向圖中，若所有頂點的出度之和為S，則所有頂點的入度之和為（b ）。
(5.0 分)
a S-1
b S
c n
d S+1
11.
採用鄰接表存儲的圖的深度優先遍歷演算法，類似與二叉樹的（b ）。
(5.0 分)
a 按層遍歷
b 先序遍歷
c 中序遍歷
d 後續遍歷
12.
已知有向圖如下，則該圖的一種拓撲序列為（b ）。
(5.0 分)
a 1-2-3-4-5-6
b 1-4-6-2-5-3
c 1-4-2-3-6-5
d 1-2-4-6-3-5
13.
對下圖從頂點a出發進行深度優先遍歷，正確的廣度優先遍歷結點序列為（c ）。
(5.0 分)
a adcbef
b adefbc
c adbcef
d abcefb
14.
對長度為3的順序表進行查找，查找第一個元素的概率是1/2，查找第二個元素的概率是1/3，查找第三元素的概率是1/6，則查找任意元素的平均查找長度為（b ）。
(5.0 分)
a 4/3
b 5/3
c 7/3
d 2
15.
多種排序方法中：（ ）法從未排序的序列中依次取出元素，與已排序序列（初始為空）中的元素作比較，將其放入已排序序列的正確位置；（d ）法從未排序的序列中挑選元素，並將其依次放入已排序序列的正確位置。
(5.0 分)
a 插入排序，選擇排序
b 歸並排序，堆排序
c 基數排序，快速排序
d 冒泡排序，shell排序
16.
用希爾排序對數據序列{15,9,7,8,20，-1,4}進行排序，進行第一趟排序後，數據序列變為{15，-1,4,8，20,9,7}，你認為採用的排序asp（數據段長度）為（ ）。
(5.0 分)
a 3
b 4
c 1
d 2
17.
一組記錄關鍵字為{46,79,56,38,40,84}，應用快速排序法，以第一個關鍵字作為排序對象（樞軸），得到結果為（b ）。
(5.0 分)
a 40,38,46,84,56,79
b 38,40,46,56,79,84
c 40,38,46,56,79,84
d 40,38,46,79,56,84
18.
一個無序數據序列12,36,41,20,80,55 採用順序表存儲數據，採用堆排序演算法建立的初始大根堆為（d ）。
(5.0 分)
a 80,36,20,12,55,41
b 80,12,20,55,36,41
c 80,12,55,20,36,41
d 80,36,15,20,12,41
19.
給定三個演算法頻度函數：
f(n)=100n3+n2+1000
g(n)=25n3+4000n2
h(n)=n1.01+1000nlg(n)
指出演算法時間復雜度數量級描述中錯誤的是（c ）。
(5.0 分)
a g(n)=O(n3)
b f(n)=O(n3)
c h(n)=O(n1.01)
d h(n)=O(nlg(n))
20.
在數據結構中，從邏輯上可以把數據結構分成（b ）。
(5.0 分)
a 內部結構和外部結構
b 線性結構和非線性結構
c 動態結構和靜態結構
d 緊湊結構和非緊湊結構
一 單項選擇題
1.
設有數據邏輯結構為：Data=(D,R);
D={d1,d2,d3,d4,d5,d6,d7,d8,d9,d10}
R={<d1,d2>,<d1,d3>,<d1,d4>,<d2,d5>,<d2,d6>,<d3,d7>,<d3,d8>,<d3,d9>,<d4,d10>}
試分析該數據結構屬於哪種邏輯結構？（c ）
(5.0 分)
a 線型邏輯結構
b 非線性邏輯結構
c 樹結構
d 網路結構
2.
計算機演算法必須具備輸入、輸出、（b ）等5個特徵。
(5.0 分)
a 確定性、有窮性和穩定性
b 可行性、確定性和有窮性
c 易讀性、安全性、穩定性
d 可行性、可移植性和可擴展性
3.
在一個長度為n的順序存儲線性表中，刪除值為x的元素，問進行比較和數據移動的總操作次數為（b ）。
(5.0 分)
a (n+1)/2
b n
c n+1
d n/2
4.
帶頭結點的鏈表L為空的判定條件為（b ）。
(5.0 分)
a L！=NULL
b L->next==NULL
c L==NULL
d L->next==L
5.
消除遞歸不一定需要使用棧的說法是（a ）的。
(5.0 分)
a 正確
b 錯誤
6.
在解決計算機主機與列印機之間速度不匹配問題時通常設置一個列印數據緩沖區，主機將要輸出的數據一次寫入該緩沖區，而列印機則從該緩沖區中取出數據列印。該緩沖區應該是一個（a ）結構。
(5.0 分)
a 隊列
b 堆棧
c 數組
d 線性表
7.
樹中所有結點的度的總和等於結點總數加（c ）。
(5.0 分)
a 1
b 0
c -1
d 2
8.
某二叉樹先序遍歷結點訪問順序是 abdgcefh,中序遍歷的節點訪問順序是 dgbaechf, 則其後序遍歷的結點訪問順序是（ a）。
(5.0 分)
a gdbehfa
b bdgcefha
c gdbecfha
d bdgaechf
9.
利用3,6,8,12這四個值，作為葉子結點的權重，生成一棵Huffman樹，該樹的帶權路徑長度為（b ）。
(5.0 分)
a 55
b 58
c 38
d 29
10.
最小生成樹指的是連通圖中（d ）。
(5.0 分)
a 定點相對較少的生成樹
b 邊數最少的生成樹
c 連通子圖
d 所有生成樹中權值之和最低的生成樹
11.
無向圖G=（V，E），V={a,b,c,d,e}，E={<a,b>, <a,c>, <d,c>, <d,e>, <b.e>, <c,e>}, 對該圖進行拓撲排序，下列序列中（d ）不是拓撲序列。
(5.0 分)
a d,a,b,c,e
b a,b,d,c,e
c a,d,c,b,e
d a,b,c,d,e
12.
已知有向圖的鄰接表如下：
根據有向圖深度優先遍歷原則，從定點V1出發，所得到的定點序列是（ d）。
(5.0 分)
a 1-2-3-5-4
b 1-2-3-4-5
c 1-4-3-5-2
d 1-3-4-5-2
13.
對下圖從頂點a出發進行深度優先遍歷，不可能的深度優先遍歷結點序列為（ c）。
(5.0 分)
a adefbc
b adcbfe
c adbefc
d adcefb
14.
下述序列中，（d ）是執行第一趟快速排序後所得到的序列。
(5.0 分)
a 【68,11,18,69】【23,93,73】
b 【93,73】【68,11,69,23,18】
c 【68,11,69,23】【18,93,73】
d 【68,11,69,23,18】【93,73】
15.
如果待排序序列中兩個數據元素具有相同的值在排序前後他們的相互位置發生顛倒，則稱該排序演算法是不穩定的。（ ）和（b ）就是不穩定的排序演算法。
(5.0 分)
a 冒泡排序，歸並排序
b shell排序，簡單選擇排序
c 直接插入排序，簡單選擇排序
d shell排序，直接插入排序
16.
對線性表進行折半查找時，要求線性表必須（c ）。
(5.0 分)
a 以鏈接式存儲結構存儲
b 以鏈接式存儲結構存儲，且數據元素有序
c 以順序存儲結構存儲，且數據元素有序
d 以順序存儲結構存儲
17.
下面的序列中（ a）序列是堆。
(5.0 分)
a {1,2,8,4,3,9,10,5}
b {1,5,10,6,7,8,9,2}
c {9,8,7,6,4,8,2,1}
d {9,8,7,6,5,4,3,7}
18.
給出下列典型時間復雜度數量級從低到高的順序。（c ）
O(1), O(n), O(n2), O(n3), O(nlg(n)), O(lg(n)), O(2n)
(5.0 分)
a O(1)< O(lg(n))< O(nlg(n)) < O(n)< O(n2)< O(n3)< O(2n)
b O(1)< O(lg(n))< O(n)< O(2n)< O(n2)< O(n3)< O(nlg(n))
c O(1)< O(lg(n))< O(n)<O(nlg(n))< O(n2)< O(n3)< O(2n)
d O(1)< O(2n) < O(n)<O(lg(n))< O(n2)< O(n3)< O(nlg(n))
19.
數據結構是一門研究非數值計算程序設計問題中（ c）以及它們之間的關系和運算等的課程。
(5.0 分)
a 數據對象
b 數據映像
c 邏輯存儲
d 計算方法
20.
線性表是（d ）。
(5.0 分)
a 一個無限序列，不能為空
b 一個有限序列，可以為空
c 一個無限序列，可以為空
d 一個有限序列，不能為空
2. 求數據結構（用面向對象方法與C++語言描述）第二版 殷人昆主編 課後答案
第一章 習題答案
2、××√
3、（1）包含改變數定義的最小范圍
（2）數據抽象、信息隱蔽
（3）數據對象、對象間的關系、一組處理數據的操作
（4）指針類型
（5）集合結構、線性結構、樹形結構、圖狀結構
（6）順序存儲、非順序存儲
（7）一對一、一對多、多對多
（8）一系列的操作
（9）有限性、輸入、可行性
4、（1）A（2）C（3）C
5、語句頻度為1+（1+2）+（1+2+3）+…+（1+2+3+…+n）
第二章 習題答案
1、（1）一半，插入、刪除的位置
（2）順序和鏈式，顯示，隱式
（3）一定，不一定
（4）頭指針，頭結點的指針域，其前驅的指針域
2、（1）A（2）A：E、A
B：H、L、I、E、A
C：F、M
D：L、J、A、G或J、A、G
（3）D（4）D（5）C（6）A、C
3、頭指針：指向整個鏈表首地址的指針，標示著整個單鏈表的開始。
頭結點：為了操作方便，可以在單鏈表的第一個結點之前附設一個結點，
該結點的數據域可以存儲一些關於線性表長度的附加信息，也可以什麼都不存。
首元素結點：線性表中的第一個結點成為首元素結點。
4、演算法如下：
int Linser(SeqList *L,int X)
{ int i=0,k;
if(L->last>=MAXSIZE-1)
{ printf(「表已滿無法插入」)；
return(0);
}
while(i<=L->last&&L->elem[i]<X)
i++;
for(k=L->last;k>=I;k--)
L->elem[k+1]=L->elem[k];
L->elem[i]=X;
L->last++;
return(1);
}
5、演算法如下：
#define OK 1
#define ERROR 0
Int LDel(Seqlist *L,int i,int k)
{ int j;
if(i<1||(i+k)>(L->last+2))
{ printf(「輸入的i，k值不合法」);
return ERROR;
}
if((i+k)==(L->last+2))
{ L->last=i-2;
ruturn OK;
}
else
{for(j=i+k-1;j<=L->last;j++)
elem[j-k]=elem[j];
L->last=L->last-k;
return OK;
}
}
6、演算法如下：
#define OK 1
#define ERROR 0
Int Delet(LInkList L,int mink,int maxk)
{ Node *p,*q;
p=L;
while(p->next!=NULL)
p=p->next;
if(mink<maxk||(L->next->data>=mink)||(p->data<=maxk))
{ printf(「參數不合法」);
return ERROR;
}
else
{ p=L;
while(p->next-data<=mink)
p=p->next;
while(q->data<maxk)
{ p->next=q->next;
free(q);
q=p->next;
}
return OK;
}
}
9、演算法如下：
int Dele(Node *S)
{ Node *p;
P=s->next;
If(p= =s)
{printf(「只有一個結點，不刪除」)；
return 0;
}
else
{if((p->next= =s)
{s->next=s;
free(p);
return 1;
}
Else
{ while(p->next->next!=s)
P=p->next;
P->next=s;
Free(p);
return 1;
}
}
}
第三章 習題答案
2、（1）
3、棧有順序棧和鏈棧兩種存儲結構。
在順序棧中，棧頂指針top=-1時，棧為空；棧頂指針top=Stacksize-1時，棧為滿。
在帶頭結點鏈棧中，棧頂指針top-〉next=NULL，則代表棧空；只要系統有可用空間，鏈棧就不會出現溢出，既沒有棧滿。
5、
#include<seqstack1.h>
#include "stdio.h"
void main( )
{
char ch,temp;
SeqStack s;
InitStack(&s);
scanf("%c",&ch);
while(ch!='@'&&ch!='&')
{
Push(&s,ch);
scanf("%c",&ch);
}
while(ch!='@'&&!IsEmpty(&s))
{
Pop(&s,&temp);
scanf("%c",&ch);
if(ch!=temp)
break;
}
if(!IsEmpty(&s))
printf("no!\n");
else
{
scanf("%c",&ch);
if(ch=='@') printf("yes!\n");
else printf("no!\n");
}
}
12、（1）功能：將棧中元素倒置。
（2）功能：刪除棧中的e元素。
（3）功能：將隊列中的元素倒置。
第四章習題答案
1、StrLength(s)操作結果為14；SubString(sub1,s,1,7)操作結果為sub1=』I AM A 』；
SubString(sub2,s,7,1)操作結果為sub2=』 』；StrIndex(s,』A』,4) 操作結果為5；
StrReplace(s,』STUDENT』,q) 操作結果為』I AM A WORKER』；
StrCat(StrCat(sub1,t), StrCat(sub2,q)) 操作結果為』I AM A GOOD WORKER』；
2、
int StrReplace(SString S,Sstring T,SString V)
{
int i=1; //從串S的第一個字元起查找串T
if(StrEmpty(T)) //T是空串
return ERROR;
do
{
i=Index(S,T,i); //結果i為從上一個i之後找到的子串T的位置
if(i) //串S中存在串T
{
StrDelete(S,i,StrLength(T)); //刪除該串T
StrInsert(S,i,V); //在原串T的位置插入串V
i+=StrLength(V); //在插入的串V後面繼續查找串T
}
}while(i);
return OK;
}
第五章習題答案
1、（1）數組A共佔用48*6=288個位元組；
（2）數組A的最後一個元素的地址為1282；
（3）按行存儲時loc（A36）=1000+[（3-1）*8+6-1]*6=1126
（4）按列存儲時loc（A36）=1000+[（6-1）*6+3-1]*6=1192
9、（1）（a，b）（2）（（c，d））（3）（b）（4）b（5）（d）
10、D
第六章 習題答案
1、三個結點的樹的形態有兩個；三個結點的二叉樹的不同形態有5個。
2、略
3、證明：分支數=n1+2n2+…+knk （1）
n= n0+n1+…+nk （2）
∵n=分支數+1 （3）
將（1）（2）代入（3）得
n0= n2+2n3+3n4+…+（k-1）nk+1
4、
註：C結點作為D的右孩子（畫圖的時候忘記了，不好意思）
5、n0=50，n2=n0-1=49，所以至少有99個結點。
6、（1）前序和後序相同：只有一個結點的二叉樹
（2）中序和後序相同：只有左子樹的二叉樹
（3）前序和中序相同：只有右子樹的二叉樹
7、證明：∵n個結點的K叉樹共有nk個鏈域，分支數為n-1（即非空域）。
∴空域=nk-（n-1）=nk-n+1
8、對應的樹如下：
9、（答案不唯一）
哈夫曼樹如下圖所示：
哈夫曼編碼如下：
頻率 編碼
0.07 0010
0.19 10
0.02 00000
0.06 0001
0.32 01
0.03 00001
0.21 11
0.10 0011
11、對應的二叉樹如下：
12、求下標分別為i和j的兩個桔點的最近公共祖先結點的值。
typedef int ElemType;
void Ancestor(ElemType A[],int n,int i,int j)
{while(i!=j)
if(i>j) i=i/2;
else j=j/2;
printf("所查結點的最近公共祖先的下標是%d,值是%d",i,A[i]);
}
15、編寫遞歸演算法，對於二叉樹中每一個元素值為X的結點，刪去以它為根的子樹，並釋放相應的空間。
void Del_Sub(BiTree T)
{ if(T->lchild) Del_Sub(T->lchild);
if(T->rchild) Del_Sub(T->rchild);
free(T);
}
void Del_Sub_x(BiTree T,int x)
{ if(T->data==x) Del_Sub(T);
else
{if(T->lchild) Del_Sub_x(T->lchild,x);
if(T->rchild) Del_Sub_x(T->rchild,x);
}
}
22、
int Width(BiTree bt)
{if (bt==NULL) return (0);
else
{BiTree p,Q[50];
int front=1,rear=1,last=1;
int temp=0, maxw=0;
Q[rear]=bt;
while(front<=last)
{p=Q[front++]; temp++;
if (p->lchild!=NULL) Q[++rear]=p->lchild;
if (p->rchild!=NULL) Q[++rear]=p->rchild;
{last=rear;
if(temp>maxw) maxw=temp;
temp=0;}
}
return (maxw);
}
}
第七章 習題答案
1、（1）頂點1的入度為3，出度為0；
頂點2的入度為2，出度為2；
頂點3的入度為1，出度為2；
頂點4的入度為1，出度為3；
頂點5的入度為2，出度為1；
頂點6的入度為2，出度為3；
（2）鄰接矩陣如下：
0 0 0 0 0 0
1 0 0 1 0 0
0 1 0 0 0 1
0 0 1 0 1 1
1 0 0 0 0 0
1 1 0 0 1 0
（3）鄰接表
（4）逆鄰接表
2、答案不唯一
（2）深度優先遍歷該圖所得頂點序列為：1，2，3，4，5，6
邊的序列為：（1，2）（2，3）（3，4）（4，5）（5，6）
（3）廣度優先遍歷該圖所得頂點序列為：1，5，6，3，2，4
邊的序列為：（1，5）（1，6）（1，3）（1，2）（5，4）
3、
（1）每個事件的最早發生時間：
ve(0)=0,ve(1)=5,ve(2)=6, ve(3)=12, ve(4)=15, ve(5)=16,
ve(6)=16, ve(7)=19, ve(8)=21, ve(9)=23
每個事件的最晚發生時間:：
vl(9)=23, vl(8)=21, vl(7)=19, vl(6)=19, vl(5)=16, vl(4)=15,
vl(3)=12, vl(2)=6, vl(1)=9, vl(0)=0
（2）每個活動的最早開始時間：
e(0,1)=0, e(0,2)=0, e(1,3)=5, e(2,3)=6, e(2,4)=6, e(3,4)=12, e(3,5)=12,
e(4,5)=15, e(3,6)=12, e(5,8)=16, e(4,7)=15, e(7,8)=19, e(6,9)=16, e(8,9)=21
每個活動的最遲開始時間：
l(0,1)=4, l(0,2)=0, l(1,3)=9, l(2,3)=6, l(2,4)=12, l(3,4)=12, l(3,5)=12, l(4,5)=15, l(3,6)=15, l(5,8)=16, l(4,7)=15, l(7,8)=19, l(6,9)=19, l(8,9)=21
（3）關鍵路徑如下圖所示：
4、頂點1到其餘頂點的最短路經為：
1-〉3最短路經為1，3；長度為15
1-〉2最短路經為1，3，2；長度為19
1-〉5最短路經為1，3，5；長度為25
1-〉4最短路經為1，3，2，4；長度為29
1-〉6最短路經為1，3，2，4，6；長度為44
13、A(7)B(3)C(2)D(11)E(8)
14、略
15、略
第八章 查找
1、畫出對長度為10的有序表進行折半查找的判定樹，並求其等概率時查找成功的平均查找長度。
解：
ASL=(1+2*2+4*3+3*4)/10=2.9
5、
解：（1）插入完成後的二叉排序樹如下：
ASL=(1+2*2+3*3+3*4+2*5+1*6)/12=3.5 ？？？？
(2)ASL=(1+2*2+3*4+4*5)=37/12
(3)
12、
解：哈希表構造如下：
0 1 2 3 4 5 6 7 8 9 10
22 41 30 01 53 46 13 67
H(22)=(22*3)%11=0
H(41)=(41*3)%11=2
H(53)=(53*3)%11=5
H(46)=(46*3)%11=6
H(30)=(30*3)%11=2 與(41)沖突
H1(30)=(2+1)%11=3
H(13)=(13*3)%11=6 與46沖突
H1(13)=(6+1)%11=7
H(01)=(01*3)%11=3 與30沖突
H1(01)=(3+1)%11=4
H(67)=(67*3)%11=3 與30沖突
H1(67)=(3+1)%11=4 與01沖突
H2(67)=(3+2)%11=5 與53沖突
H3(67)=(3+3)%11=6 與46沖突
H4(67)=(3+4)%11=7 與13沖突
H5(67)=(3+5)%11=8
ASLsucc=(1*4+2*3+6)/8=2
ASLunsucc=(2+8+7+6+5+4+3+2)/8=37/8
第九章 排序
1、以關鍵字序列（503，087，512，061，908，170，897，275，653，426）為例，手工執行以下排序演算法，寫出每一趟派結束時的關鍵字狀態。
（1）直接插入排序（2）希爾排序（增量序列為5，3，1）（3）快速排序（4）堆排序（5）歸並排序
解：（1）略
（2）增量為5的排序結果：170，087，275，061，426，503，897，512，653，908
增量為3的排序結果：061，087，275，170，426，503，897，512，653，908
增量為1的排序結果：061，087，170，275，426，503，512，653，897，908
（3）一次劃分後：{426 087 275 061 170}503{897 908 653 512}
分別進行：{170 087 275 061}426 503 {512 653} 897 {908}
{061 087}170{275}426 503 512 {653} 897 908
061 087 170 275 426 503 512 653 897 908
（4）略
7、已知一組關鍵字：（40，27，28，12，15，50，7），要求採用快速排序法從小到大排序。請寫出每趟排序後的劃分結果。
解：初始狀態：40 27 28 12 15 50 7
一次劃分：{7 27 28 12 15} 40 {50}
依次劃分：7 {27 28 12 15} 40 50
7 {15 12} 27 {28} 40 50
7 12 15 27 28 40 50
16、（1）A3 B1 C4 D2 E7
(2)C
(3)C
17、對，錯，對
數據結構課程設計指導書
一、設計內容
1.飛機訂票系統（限1 人完成）
【問題描述】
設計一個飛機訂票系統，可以模擬處理飛機訂票過程中的各種操作。
【基本要求】
通過此系統可以實現如下功能：
1)錄入
可以錄入航班情況（數據可以存儲在一個數據文件中，數據結構、具體數據自定）。
2)查詢
可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；
可以輸入起飛抵達城市，查詢飛機航班情況。
3)訂票（訂票情況可以存在一個數據文件中，結構自己設定）
可以訂票，如果該航班已經無票，可以提供相關可選擇航班。
4)退票
可退票，退票後修改相關數據文件。
客戶資料有姓名，證件號，訂票數量及航班情況，訂單要有編號。
5)修改航班信息
當航班信息改變可以修改航班數據文件
根據以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能。
2.文章編輯（限1 人完成）
【問題描述】
輸入一頁文字，程序可以統計出文字、數字、空格的個數。
【基本要求】
靜態存儲一頁文章，每行最多不超過80個字元，共N行；
1)分別統計出其中英文字母數和空格數及整篇文章總字數；
2)統計某一字元串在文章中出現的次數，並輸出該次數；
3)刪除某一子串，並將後面的字元前移；
4)用指定的字元串替換某一子串；
5)存儲結構使用線性表，分別用幾個子函數實現相應的功能；
6)輸入數據的形式和范圍：可以輸入大寫、小寫的英文字母、任何數字及標點符號。
7)輸出形式：①分行輸出用戶輸入的各行字元；②分4行輸出"全部字母數"、"數字個數"、"空格個數"、"文章總字數"；③輸出刪除某一字元串後的文章；④輸出替換某一字元串後的文章。
3.宿舍管理查詢軟體（限1 人完成）
【問題描述】
為宿舍管理人員編寫一個宿舍管理查詢軟體。
【基本要求】
1) 程序設計要求：
①採用交互工作方式
②建立數據文件，數據文件按關鍵字（姓名、學號、房號）進行排序(冒泡、選擇、插入排序等任選一種)
2) 查詢菜單: (用二分查找實現以下操作)
①按姓名查詢
②按學號查詢
③按房號查詢
3) 輸出任一查詢結果（可以連續操作）
4.全國交通咨詢模擬
【問題描述】
處於不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時間盡可能的短，出門旅遊的遊客則期望旅費盡可能省，而老年旅客則要求中轉次數最少。編制一個全國城市間的交通咨詢程序，為旅客提供兩種或三種最優決策的交通咨詢。
【設計要求】
1)提供對城市信息進行編輯（如：添加或刪除）的功能。
2)提供對列車時刻表進行編輯（增設或刪除）的功能。
3) 提供兩種最優決策：最快到達和最省錢到達。
4)旅途中耗費的總時間應該包括中轉站的等候時間。
5)咨詢以用戶和計算機的對話方式進行。由用戶輸入起始站、終點站、最優決策原則，輸出信息：最快需要多長時間才能到達或者最少需要多少旅費才能到達，並詳細說明於何時乘坐哪一趟列車到何地。
測試數據：參考教科書7.6節圖7.33的全國交通圖，自行設計列車時刻表。
【實現提示】
1) 對全國城市交通圖和列車時刻表進行編輯，應該提供文件形式輸入和鍵盤輸入兩種方式。列車時刻表則需根據交通圖給出各個路段的詳細信息，例如：基於教科書7.6節圖7.33的交通圖，對從北京到上海的火車，需給出北京至天津、天津至徐州及徐州至上海各段的出發時間、到達時間及票價等信息。
2) 以鄰接表作交通圖的存儲結構，表示邊的結構內除含有鄰接點的信息外，還應包括交通工具、路程中耗費的時間和花費以及出發和到達的時間等多種屬性。
5.哈夫曼編碼/解碼器（限1 人完成）
【問題描述】
設計一個利用哈夫曼演算法的編碼和解碼系統，重復地顯示並處理以下項目，直到選擇退出為止。
【基本要求】
1) 將權值數據存放在數據文件(文件名為data.txt，位於執行程序的當前目錄中)
2) 分別採用動態和靜態存儲結構
3) 初始化：鍵盤輸入字元集大小n、n個字元和n個權值，建立哈夫曼樹；
4) 編碼：利用建好的哈夫曼樹生成哈夫曼編碼；
5) 輸出編碼；
6) 設字元集及頻度如下表：
字元 空格 A B C D E F G H I J K L M
頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20
字元 N O P Q R S T U V W X Y Z
頻度 57 63 15 1 48 51 80 23 8 18 1 16 1
【進一步完成內容】
1) 解碼功能；
2) 顯示哈夫曼樹；
3) 界面設計的優化。
6.走迷宮游戲
【問題描述】
以一個m×n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。
【基本要求】
1．首先用二維數組存儲迷宮數據，迷宮數據由用戶輸入。
2．一個以鏈表作存儲結構的棧類型，然後編寫一個求解迷宮的遞歸或非遞歸程序。求得的通路以三元組（i，j，d）形式輸出，其中：（i，j）指示迷宮中的一個坐標，d表示走到下一坐標的方向（東、南、西、北四個方向所用代表數字，自行定義）。
3．可以用多種方法實現，但至少用兩種方法，用三種以上可加分。
【實現提示】
1．計算機解迷宮問題通常用的是「窮舉求解」方法，即從入口出發，順著某一個方向進行探索，若能走通，則繼續往前進；否則沿著原路退回，換一個方向繼續探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設定的迷宮沒有通路。
迷宮的入口點的下標為（1，1），出口點的下標為（m，n）。為處理方便起見，可在迷宮的四周加一圈障礙。對於迷宮的任一位置，均可約定有東、南、西、北四個方向可通。
2．有一種簡單走出迷宮的方法，把手放在右邊的牆上開始前進，始終不要把手從牆上移開。如果迷宮向右拐，你也順著牆向右拐。只要不把手從牆上移開，最終就會到達迷宮的出口。當然這樣得到的路徑可能不是一個最短的路徑，但它可以最終得到結果，換句話說，這種方法走不出迷宮的風險是最小的。
7.作業評分系統
【問題描述】
設計一個可以給小學生出題並且可以給出分數的系統軟體。
【基本要求】
利用棧求表達式的值，可供小學生作業，並能給出分數。
1) 建立試題庫文件，隨機產生n個題目；
2) 題目涉及加減乘除，帶括弧的混合運算；
3) 隨時可以退出；
4) 給出作業分數。
【進一步完成內容】
1）保留歷史分數，能回顧歷史，給出與歷史分數比較後的評價。
2）界面設計的優化。
8.散列表的設計與實現
【問題描述】
設計散列表實現電話號碼查找系統。
【基本要求】
1)設每個記錄有下列數據項：電話號碼、用戶名、地址；
2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立散列表；
3)採用一定的方法解決沖突；
4)查找並顯示給定電話號碼的記錄；
5)查找並顯示給定用戶名的記錄。
【進一步完成內容】
1) 系統功能的完善；
2) 設計不同的散列函數，比較沖突率；
3) 在散列函數確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。
9.停車場管理
【問題描述】
設停車場是一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內按車輛到達時間的先後順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內已停滿n輛汽車，則後來的汽車只能在門外的便道上等待，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內某輛車要離開時，在它之後進入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。
【基本要求】
以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數據序列進行模擬管理。每一組輸入數據包括三個數據項：汽車「到達」或「離去」信息、汽車牌照號碼以及到達或離去的時刻。對每一組輸入數據進行操作後的輸出信息為：若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內停留的時間和應交納的費用（在便道上停留的時間不收費）。棧以順序結構實現，隊列以鏈表結構實現。
【測試數據】
設n=2，輸入數據為：(『A』,1,5),(『A』,2,10),(『D』,1,15),(『A』,3,20),(『A』,4,25),
(『A』,5,30),(『D』,2,35),(『D』,4,40),(『E』,0,0)。其中：『A』表示到達（Arrival）；『D』表示（Departure）；『E』表示輸入結束（End）。
【實現提示】
需另設一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結構實現。輸入數據按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數據項：汽車的牌照號碼和進入停車場的時刻。
10.八皇後問題
【問題描述】
求出在一個n×n的棋盤上，放置n個不能互相捕捉的國際象棋「皇後」的所有布局。
這是來源於國際象棋的一個問題。皇後可以沿著縱橫和兩條斜線8個方向相互捕捉。如圖所示，一個皇後放在棋盤的第4行第3列位置上，則棋盤上凡打「×」的位置上的皇後就能與這個皇後相互捕捉，也就是下一個皇後不能放的位置。
1 2 3 4 5 6 7 8
× ×
× × ×
× × ×
× × Q × × × × ×
× × ×
× × ×
× ×
× ×
從圖中可以得到以下啟示：一個合適的解應是在每列、每行上只有一個皇後，且一條斜線上也只有一個皇後。
【實現提示】
求解過程從空配置開始。在第1列至第m列為合理配置的基礎上，再配置第m+1列，直至第n列配置也是合理時，就找到了一個解。接著改變第n列配置，希望獲得下一個解。另外，在任一列上，可能有n種配置。開始時配置在第1行，以後改變時，順次選擇第2行、第3行、…、直到第n行。當第n行配置也找不到一個合理的配置時，就要回溯，去改變前一列的配置。
二、時間安排
2005~2006(一)第19周進行。
第一天： 分析題目，查閱資料；
第二天：演算法設計、編碼；
第三天：編碼、調試運行；
第四天：調試運行，撰寫設計報告；；
第五天：答辯。
三、設計工作要求
1．對學生的要求
(1) 要求學生認真閱讀設計任務書，了解所做的設計內容及要求，認真主動完成課設的要求。有問題及時主動通過各種方式與教師聯系溝通。
(2)學生要發揮自主學習的能力，充分利用時間，安排好課設的時間計劃，並在課設過程中不斷檢測自己的計劃完成情況，及時向教師匯報。
(3)查閱相關的參考文獻；獨立完成設計任務。
(4)認真撰寫課程設計說明書，要求文字通順、有邏輯性、真正反映設計的水平，設計要有創新。
(5)設計完成後上交相關內容要求：
①上交源程序：學生按照課程設計的具體要求所開發的所有源程序（應該放到一個文件夾中）。
②課程設計說明書：到教務處網站下載課程設計報告紙及封面。格式及要求見附錄。
2．對教師的要求
(1)做好設計題目的選題工作，使題目達到一定的綜合性要求，工作量合理；
(2)加強指導，嚴格考勤、考核；
(3)做好答辯、設計報告的評審以及成績評定工作。
附錄：
課程設計說明書，格式及要求如下：
一、封面；
二、目錄；
三、設計任務書；
四、說明書正文，主要內容包括：
1．設計題目；
2．設計目的；
3．演算法思想分析；
4．演算法描述與實現；
5．結論
3. 數據結構作業，要求：1.計算二叉樹葉子節點的個數 2.交換二叉樹所有孩子節點的左…詳見問題補充
判斷是否是葉子結點。如果一個結點既沒有左子樹，也沒有右子樹，那麼此結點就是葉子結點，反之，如存在一個左子樹，或一個右子樹，那麼就是非葉子結點。這是判斷的邏輯。然後只需要對樹進行遍歷即可，就是3問題提到的樹的遍歷，樹的遍歷分為前中後三種遍歷。邏輯是很好掌握的主要使用遞歸的方式實現， 這個網上有很多。你可以自己看下，不懂可以繼續問我。不難。還是要遍歷整個樹分為以下情況進行遍歷。若一個結點即存在左子樹，又存在右子樹，那麼讓左子樹的指針指向右子樹；右子樹的指針指向左子樹。可能需要一個temp指針，做交換的載體temp=Lchlid;Lchild=Rchild;Rchild=temp;即完成了交換。首先掌握前序遍歷和中序遍歷的思想方法，根據這個判斷出樹是很好辦，首先你可以根據前序建立一個樹，然後當遇到不確定此結點是左子樹還是右子樹的時候使用中序的順序進行確定。循環此演算法即可得到該樹。樹的數據結構是遞推的，所以解決此類問題，要有遞歸思想，你對遞歸理解的越透徹，解決樹的問題就越輕松。
4. 求大工11秋《數據結構》在線作業1、2、3
大工11秋《數據結構》在線作業1
一,單選題
1. B
2. B
3. B
4. A
5. A
6. C
7. B
8. B
9. C
10.B
二,判斷題
1.B
2.A
3.B
4.B
5.B
6.A
7.B
8.B
9.B
10.A
大工11秋《數據結構》在線作業2
一,單選題
1. difference(A,B,C)表示求集合A和B的差集C。若A={b,c,d},B={c,e},則difference(A,B,C)運算後C=( )。
A. {b,c,d,e}
B. {c}
C. {b,d}
D. {b,c,c,d,e}
正確答案：C
2. 具有6個頂點的無向圖至少應有（）條邊才能確保是一個連通圖。
A. 5
B. 6
C. 7
D. 8
正確答案：A
3. min(A)，函數的返回值是集合A的所有元素中按線性序最小的那個元素。則min({2,3,4})=( )
A. 2
B. 3
C. 4
D. 0
正確答案：A
4. index(s,t)表示子串定位運算。若串t是串s的子串，則函數返回值是串t在串s中第一次出現的開始位置，否則返回值是0。若s="ababa",t="ba",則index(s,t)=( )。
A. 0
B. 1
C. 2
D. 3
正確答案：C
5. 在一棵二叉樹上第5層的結點數最多為（）,設樹根為第1層。
A. 16
B. 15
C. 8
D. 32
正確答案：A
6. intersection(A,B,C)表示求集合A和B的交集C。若A={b,c,d},B={c,e},則intersection(A,B,C)運算後C=( )。
A. {b,c,d,e}
B. {c}
C. {b,d}
D. {b,c,c,d,e}
正確答案：B
7. 在一個具有n個頂點和e條邊的無向圖的鄰接表中，邊結點的個數為（）。
A. n
B. ne
C. e
D. 2e
正確答案：D
8. union(A,B,C)表示求集合A和B的並集C。若A={b,c,d},B={c,e},則union(A,B,C)運算後C=( )。
A. {b,c,d,e}
B. {c}
C. {b,d}
D. {b,c,c,d,e}
正確答案：A
9. 在一個具有n個頂點和e條邊的有向圖的鄰接表中，保存頂點單鏈表的表頭指針向量的大小至少為（）。
A. n
B. 2n
C. e
D. 2e
正確答案：A
10. concat(s,t)表示連接運算。將串t連接在串s之後，形成新的串s。若s="beg",t="in",則concat(s,t)之後，s="( )"。
A. begin
B. bein
C. begn
D. beggin
正確答案：A
二,判斷題
1. 樹中的結點數等於所有結點的度數加1。
A. 錯誤
B. 正確
正確答案：B
2. 有向圖用鄰接表表示，頂點i的度是對應頂點i鏈表中結點個數。
A. 錯誤
B. 正確
正確答案：A
3. 字典是一種特殊的集合，其中每個元素由關鍵碼和屬性組成。
A. 錯誤
B. 正確
正確答案：B
4. 有向圖用鄰接表表示，頂點i的出度是對應頂點i鏈表中結點個數。
A. 錯誤
B. 正確
正確答案：B
5. 一個圖的鄰接矩陣表示是惟一的。
A. 錯誤
B. 正確
正確答案：B
6. 有向圖的鄰接矩陣一定是對稱矩陣。
A. 錯誤
B. 正確
正確答案：A
7. 無向圖的鄰接矩陣一定是對稱矩陣。
A. 錯誤
B. 正確
正確答案：B
8. 一個圖的鄰接表表示是惟一的。
A. 錯誤
B. 正確
正確答案：A
9. 非空二叉樹上葉子結點數等於雙分支結點數加1。
A. 錯誤
B. 正確
正確答案：B
10. 連通圖的生成樹不一定是惟一的。
A. 錯誤
B. 正確
正確答案：B
大工11秋《數據結構》在線作業3
一,單選題
1. 下述幾種排序方法中，要求內存量最大的是（）。
A. 插入排序
B. 選擇排序
C. 堆排序
D. 歸並排序
正確答案：D
2. 堆排序是一種（）排序。
A. 插入
B. 選擇
C. 交換
D. 歸並
正確答案：B
3. 在長度為n的順序表中進行順序查找，查找失敗時需與關鍵字比較次數是( )。
A. n
B. 1
C. n-1
D. n+1
正確答案：D
4. 用起泡排序方法對n個記錄按排序碼從小到大排序時，當初始序列是按排序碼從大到小排列時，與排序碼總比較次數是（）。
A. n-1
B. n
C. n+1
D. n(n-1)/2
正確答案：D
5. 對線性表進行順序查找時，要求線性表的存儲結構是（）。
A. 倒排表
B. 索引表
C. 順序表或鏈表
D. 散列表
正確答案：C
6. 對於順序存儲的有序表(5,12,20,26,37,42,46,50,64),若採用折半查找，則查找元素26的查找長度為( ).
A. 2
B. 3
C. 4
D. 5
正確答案：C
7. 哈希表的平均查找長度和（）無直接關系。
A. 哈希函數
B. 裝填因子
C. 哈希表記錄類型
D. 處理沖突的方法
正確答案：C
8. 排序方法中，從未排序序列中挑選元素，並將其依次放入已排序序列（初始時為空）的一端的方法，稱為（）。
A. 希爾排序
B. 歸並排序
C. 插入排序
D. 選擇排序
正確答案：D
9. 磁帶適合存儲的文件類型是（）。
A. 索引文件
B. 順序文件
C. 散列文件
D. 倒排文件
正確答案：B
10. 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為（）。
A. 插入排序
B. 冒泡排序
C. 希爾排序
D. 選擇排序
正確答案：A
二,判斷題
1. 散列表既是一種查找方法，又是一種存儲方法。
A. 錯誤
B. 正確
正確答案：B
2. 在散列文件中刪除記錄時，只要對被刪記錄作一標記即可。
A. 錯誤
B. 正確
正確答案：B
3. 散列文件中存放一組記錄的存儲單位稱為桶。
A. 錯誤
B. 正確
正確答案：B
4. 二分查找對線性表的存儲結構無任何要求。
A. 錯誤
B. 正確
正確答案：A
5. 直接選擇排序屬於選擇類排序，是一種穩定的排序方法。
A. 錯誤
B. 正確
正確答案：A
6. 哈希表查找無須進行關鍵字的比較。
A. 錯誤
B. 正確
正確答案：A
7. 對快速排序來說，初始序列為正序和反序都是最壞情況。
A. 錯誤
B. 正確
正確答案：B
8. 在執行某個排序過程中，出現排序碼朝著最終位置相反方向移動，則該演算法是不穩定的。
A. 錯誤
B. 正確
正確答案：A
9. 堆排序是一種不穩定的排序方法。
A. 錯誤
B. 正確
正確答案：B
10. 若待排序記錄已按排序碼基本有序，則應採用直接插入排序或起泡排序。
A. 錯誤
B. 正確
正確答案：B