发布时间 : 星期五 文章全国自考数据结构历年试题及部分答案(2009--2013) - 图文更新完毕开始阅读
根 【1，2】
(1)画出将关键字6插入之后的B—树；
5,8 1,3 6 9
(2)画出在(1)所得树中插入关键字2之后的B—树。
5,8 1,3 6 9 2,5,8 5,8 1,2,3 6 9 1,2,3 6 9 2,5,8 1 3 6 9 5 2 8
四、算法阅读题(本大题共4小题，每小题5分，共20分)
30.假设以带头结点的单链表表示线性表，单链表的类型定义如下：
typedef int DataType; typedef struct node { DataType data;
struct node * next; } LinkNode, * LinkList; 阅读下列算法，并回答问题：
(1)已知初始链表如图所示，画出执行f30(head)之后的链表；
题30图
(2)简述算法f30的功能。
void f30( LinkList head) { LinkList p,r, s; if (head - > next) { r = head - > next;
p = r->next;
r - > next = NULL; while (p) { s =p;
p = p->next;
if ( s - > data% 2 = = 0) { s - > next = head - > next; head - > next = s; } else {
s - > next = r - > next; r->next = s; r =s; } } } }
2 8 5 7
(1)(2)
31.假设以二叉链表表示二叉树，其类型定义如下：
typedef struct node { DataType data;
struct node * lchild, * rchild; //左右孩子指针 } * BinTree ;
阅读下列算法，并回答问题：
(1)已知以T为根指针的二叉树如图所示， 写出执行f31(T)之后的返回值； (2)简述算法f31的功能。 int f31 ( BinTree T) { int d;
if ( ! T) return 0;
d = f31 ( T - > lchild) + f31 ( T - > rchild) ; if (T - > lchild && T - > rchild) return d + 1 ; else
return d; (1)3
(2)统计度为2的结点个数 32.设有向图邻接表定义如下：
typedef struct {
VertexNode adjlist[ MaxVertexNum ] ; int n，e； ／／图的当前顶点数和弧数 }ALGraph； ／／邻接表类型 其中顶点表结点VertexNode 边表结点EdgeNode结构为： 阅读下列算法，并回答问题：
(1)已知某有向图存储在如图所示的邻接 表G中，写出执行f32(＆G)的输出； (2)简述算法f32的功能。 int visited[ MaxNum ];
void DFS(ALGraph * G, int i) { EdgeNode * p;
visited [ i ] = TRUE ;
if (G - > adjlist[ i]. firstedge = = NULL) printf( \； else {
p = G - > adjlist[ i]. firstedge; while (p ! = NULL) {
if ( ! visited[p -> adjvex] ) DFS( G, p - > adjvex) ; p = p->next;
} } }
void f32 ( ALGraph * G) { int i;
for (i = 0; i < G->n; i ++) visited [ i ] = FALSE ; for (i = 0; i < G->n; i++)
if ( ! visited[i] ) DFS(G, i) ; }
(1)ABECD
(2)图的深度优先搜寻 A
B E
C
D
33.下列算法f33的功能是对记录序列进行双向冒泡排序。算法的基本思想为，先从前往后通过交换将关键字最大的记录移
动至后端，然后从后往前通过交换将关键字最小的记录移动至前端，如此反复进行，直至整个序列按关键字递增有序为止。请在空缺处填入合适的内容，使其成为完整的算法。
#define MAXLEN 100 typedef int KeyType; typedef struct { KeyType key;
InfoType otherinfo; } NodeType ;
typedef NodeType SqList[ MAXLEN ]; void f33 ( SqList R, int n) { int i,j,k; NodeType t; i =0; j =n-l;
while (i < j) {
for ( (1) ) k=i;k
R[k] = R[k +1]; R[k +1] = t; } j--;
for (k =j; k > i; k -- )
if ( (2) ) { R[k].key < R[k-l].key t = R[k];
R[k] = R[k-1]; R[k-1] = t;
}
(3) ; i++
} } (1) (2) (3)
五、算法设计题(本大题10分)
34.假设以带头结点的单链表表示线性表，单链表的类型定义如下：
typedef int DataType; typedef struct node { DataType data;
struct node * next; } LinkNode, * LinkList;
编写算法，删除线性表中最大元素(假设最大值唯一存在)。函数原型为：
void f34(LinkList head) {
LinkNode *p,*max,*q; P=head->next; max=head->next; while(P) {
P=p->next;
If(p->data>max->data) max=p; }