DS考试大题集锦
- 格式：pdf
- 大小：158.23 KB
- 文档页数：13
DS考试⼤题集锦
三. 解答题（共38分）17．（5分）请直接在以下⼆叉树中添加后序线索。
18.（10分）已知⼀个长度为12的表为
（Ja n，F eb，M ar，Ap r，M ay，Ju n e，J uly，A ug，S ep，Oc t，N ov，D ec）
（1）试将表中元素依次插⼊到⼀棵初始为空的⼆叉排序树（字符串之间按字典顺序⽐较⼤⼩）。画出该⼆叉排序树，并求出等概率情况下查找成功的平均查找长度。
（2）设哈希表长度为13，哈希函数H（k）=?i/2?，其中i为关键字k中第⼀个字母在字母表中的序号（例如A和D的序号分别为1和4），⽤链地址法解决冲突。请画出通过依次插⼊表中元素所构造的散列表，并求出在等概率情况下查找成功的平均查找长度。20.（8分）若对序列（25，19，7，41，29，12，23，26）按升序排序，请分别给出
（1）步长为4的⼀趟希尔排序的结果；
（2）初始⼤根堆。22．（6分）函数f22定义如下，其中函数调⽤Insert(L, i, k)在顺序表L的第i位置插⼊k。
void f22(SqList &L, int i) {
if (i > 0) {
f22(L, i-1);
for (int k=1; k<=i; k++)
Insert(L, i, k);
}
}
设有空顺序表L ＝（），请写出调⽤递归函数f22(L,3)后
（1）L的长度：
（2）L ＝（）23.（6分）算法f23(L)将带头结点的单链表L逆置。请在画线处填空。
void f23(LinkList &L) {
LinkList p = L->next;
L->next = ;
while ( p ) {
LinkList s = ;
p->next = L->next;
L->next = ;
p = s;
}
}24.（6分）s是⼀个升序静态查找表，请简要说明函数调⽤f24(s, 1, s.length, k)的意义。
int f24(SSTable s, int low, int high, KeyType k) {
if (low>high) return 0;
int mid=(low+high)/2;
if (k==s.elem[mid].key) return mid;
if (k>s.elem[mid].key) return f24(s,mid+1,high,k);
else return f24(s,low,mid-1,k);
}
25．（6分）请对以下函数填空，实现求⼆叉树T中各结点的⼦孙总数，并填⼊结点的DescNum域中的算法。
int f25(BiTree T) {
if ( ) return -1;
else {
T->DescNum = f25(T->lchild) +
+
;
return T->DescNum;
}
}
26．（6分）图的邻接矩阵表⽰和算法f26描述如下：
#define MaxNum 5
typedef struct {
char vexs[MaxNum];
int arcs[MaxNum][MaxNum];
int n,e;
} MGraph;
int f26(MGraph G, int i) {
int d=0;
for (int j=0; j
if (G.arcs[i][j]) d++;
if (G.arcs[j][i]) d++;
}
return d;
}
已知⼀个图G的邻接矩阵如下所⽰，(1)给出执⾏算法调⽤f26(G,4)的返回值； (2)简述该算法返回值的意义。
27．（8分）请设计实现删除单链表中值相同的多余结点的算法，先简述算法思想，然后写出算法的C 语⾔描述。 17．（5分）后序线索
18.（10分）已知⼀个长度为12的表为
（Ja n ，F eb ，M ar ，Ap r ，M ay ，Ju n e ，J uly ，A ug ，S ep ，Oc t ，N ov ，D ec ） （3） 试将表中元素依次插⼊到⼀棵初始为空的⼆叉排序树（字符串之间按字典顺序⽐较⼤⼩）。画出该⼆叉排
序树，并求出等概率情况下查找成功的平均查找长度。 （4） 设哈希表长度为13，哈希函数H （k ）= ?i/2?，其中i 为关键字k中第⼀个字母在字母表中的序号（例如A 和D 的序号分别为1和4），⽤链地址法解决冲突。请画出通过依次插⼊表中元素所构造的散列表，并求出在等概率情况下查找成功的平均查找长度。
20.（8分）若对序列（25，19，7，41
，29，12，23，26）按升序排序，请分别给出
（3） 步长为4的⼀趟希尔排序的
结果； （4） 初始⼤根堆。
答：（1） （25，12，7，26，29，19，23，41）
（2） （41，29，23，26，25，12，7，19）（先乱搞⼀个2叉树，然后⼤的上去）22．（6分）函数f22定义如下，其中函数调⽤Insert(L, i, k)在顺序表L 的第i 位置插⼊k 。 void f22(SqList &L, int i) { if (i > 0) {f22(L, i-1);
Jan
Feb
Mar
Apr
June May
JulyAug
Sep
Oct Nov
Dec
成功的平均查找长度＝42/12
成功的平均查找长度＝18/12for (int k=1; k<=i; k++)
Insert(L, i, k);
}
}
设有空顺序表L ＝（），请写出调⽤递归函数f22(L,3)后
（1）L的长度：6
（2）L ＝（ 1，2，3，2，1，1）23.（6分）算法f23(L)将带头结点的单链表L逆置。请在画线处填空。
void f23(LinkList &L) {
LinkList p = L->next;
L->next = NULL ;
while ( p ) {
LinkList s = p->next ;
p->next = L->next;
L->next = p ;
p = s;
}
}
24.（6分）s是⼀个升序静态查找表，请简要说明函数调⽤f24(s, 1, s.length, k)的意义。
int f24(SSTable s, int low, int high, KeyType k) {
if (low>high) return 0;
int mid=(low+high)/2;
if (k==s.elem[mid].key) return mid;
if (k>s.elem[mid].key) return f24(s,mid+1,high,k);
else return f24(s,low,mid-1,k);
}
答：在s中递归折半查找k。25．（6分）请对以下函数填空，实现求⼆叉树T中各结点的⼦孙总数，并填⼊结点的DescNum域中的算法。
int f25(BiTree T) {if ( !T ) return -1;
else {
T->DescNum = f25(T->lchild) +
f25(T->rchild) +
2 ;
return T->DescNum;
}
}
26．（6分）图的邻接矩阵表⽰和算法f26描述如下：
#d ef in e Ma xN um5
typedef struct {
char vexs[MaxNum];
int arcs[MaxNum][MaxNum];
int n,e;
} MGraph;
int f26(MGraph G, int i) {
int d=0;
for (int j=0; j
if (G.arcs[i][j]) d++;
if (G.arcs[j][i]) d++;
}
return d;
}
已知⼀个图G的邻接矩阵如右所⽰，
(1)给出执⾏算法调⽤f26(G,4)的返回值；答：5；
(2)简述该算法返回值的意义。答：求图G第i顶点的度。
27．（8分）请设计实现删除单链表中值相同的多余结点的算法，先简述算法思想，然后写出算法的C 语⾔描述。 voidpurge(LList L) { // 删除链表中的“冗余”元素 LList s, q, p = L->next;
while ( p ) { // p 指向当前被考察的结点 q = p; while (q->next) // 考察 q 所指后继结点 if (q->next->data != p->data)
q = q->next; else // 修改指针并释放结点空间 { s=q->next; q->next=s->next; free(s); } p = p->next;
}// wh il e p
}//purge
1．（10分）⼰知有向图G 定义如下： G=（V ，E ） V={a,b,c,d,e,f}
E={,,,,,,,} (1)画出图G 。
（2）画出图G 的邻接矩阵。1
1
000000010000010010000000001110
（3）写出G 的全部拓扑有序序列。 afcbde afcdbe afcdeb afdc be afdc eb facbde facdbe facdeb fadc be fadc ebacbf de
acfbde
acfdbe
acfdeb
4．(10分）设哈希函数为H （key ）=ke y MOD 11,⽤线性探测再散列的⽅法处理冲突。请画出依次插⼊元素29，15，48，
47，23，41，73，37后，该哈希表的状态，并在各元素下⾯标出其冲突次数。0 1 2 3 4 5 6 7 8 9 10冲突次数：
1．（10分）写出在带头结点的单链表上实现线性表操作L E NGTH（L）的算法。
1. LE NG TH(L) （10分）
i nt L E NG TH(L)
{
i nt l e ngt h = 0;
Nodt * p = L->hea d;
whi l e (p) {
l engt h++;
p = p->nex t;
}
ret urn l e ngt h;
}
每⾏语句1分2．（10分）填空完成先序遍历建⽴⼆叉树的如下算法。
Status Cr eateB iT re e(B iT re e &T) {
scanf(&ch);
if (ch==' ') T = NU LL;
el se {
…… // ⽣成根结点
CreateB iT re e(……); // 构造左⼦树
CreateB iT re e(……); // 构造右⼦树
