自考数据结构02331历年试题及答案.doc

自考数据结构02331历年试题及答案

资料仅供参考
自考数据结构02331历年试题及答案( -- 个人整理版)
全国 1月自学考试数据结构试题
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.下列程序段的时间复杂度为( )9
s=0；
for(i=1；i单链表的头指针为head，则判定该表为空表的条件是( )22
A.head==NULL； B.head->next==NULL；
C.head!=NULL； D.head->next==head；
3.栈是一种操作受限的线性结构，其操作的主要特征是( )32
A.先进先出 B.后进先出
C.进优于出 D.出优于进
4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( )
A.(rear-front-1)％n B.(rear-front)％n
C.(front-rear+1)％n D.(rear-front+n)％n
5.判断两个串大小的基本准则是( )52
A.两个串长度的大小 B.两个串中首字符的大小
C.两个串中大写字母的多少 D.对应的第一个不等字符的大小
6.二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为( )60
A.1012 B.1017
C.1034 D.1036
a00
a01
a02
a03
a04

a32

7.高度为5的完全二叉树中含有的结点数至少为( )72
A.16 B.17
C.31 D.32
8.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( )
A.5 B.8
C.11 D.18
9.下列所示各图中是中序线索化二叉树的是( A )81A

10.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为( )108
A.(v0，v1，v2，v5，v4v3)
B.(v0，v1，v2，v3，v4，v5)
C.(v0，v1，v5，v2，v3，v4)
D.(v0，v1，v4，v5，v2，v3)
11.如图所示有向图的一个拓扑序列是( )
A.ABCDEF
B.FCBEAD
C.FEDCBA
D.DAEBCF
12.下列关键字序列中，构成大根堆的是( )
A.5，8，1，3，9，6，2，7 B.9，8，1，7，5，6，2，33
C.9，8，6，3，5，l，2，7 D.9，8，6，7，5，1，2，3
13.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( )172
A. B.
C. D.
14.已知一个散列表如图所示，其散列函数为H(key)=key％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( D )d 197

15.数据库文件是由大量带有结构的( )206
A.记录组成的集合 B.字符组成的集合
C.数据项组成的集合 D.数据结构组成的集合

二、填空题(本大题共10小题，每小题2分，共20分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.估算算法时间复杂度时考虑的问题规模一般是指算法求解问题的____输入量_____。 8
17.在双向循环链表中插入一个新的结点时，应修改_____4____个指针域的值。 28
18.若进栈序列为a，b，c，且进栈和出栈能够穿插进行，则可能出现___5______个不同的出栈序列。5
19.链串的结点大小定义为结点的_____数据域____中存放的字符个数。 54
20.广义表(a，(d，(c)))的深度为___3 ______。67
21.在含有3个结点a，b，c的二叉树中，前序序列为abc且后序序列为cba的二叉树有____4_____棵。4
22.若用邻接矩阵表示有向图，则顶点i的入度等于矩阵中_________。第i列非零元素的个数107
23.对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为5的一趟希尔排序的结果为_________。
15，12，11，10，8，16，18，17
24.索引顺序查找的索引表由各分块中的最大关键字及各分块的_____起始位置____构成。173
25.VSAM文件的实现依赖于操作系统中的_____分页____存取方法的功能。 215
三、解答题(本大题共4小题，每小题5分，共20分)
26.假设有一个形如

的8×8矩阵，矩阵元素都是整型量(次对角线以上的元素都是0)。
若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组B中，请回答下列问题：
(1)B数组的体积至少是多少?
(2)若a18存储在B[0]中，a56存储在B[k]中，则k值为多少?
(1) （1+8）*8/2=36 存放次对角线以上的零为37
(2) 12
27.对关键字序列(5，8，1，3，9，6，2，7)按从小到大进行快速排序。
(1)写出排序过程中前两趟的划分结果；
(2)快速排序是否是稳定的排序方法?
(1)
第一趟划分结果；(2，3，1)，5，(9，6，8，7)
第二趟划分结果；(1，2，3)，5，(9，6，8，7)
第三趟划分结果；(1，2，3)，5，(7，6，8，9)
第四趟划分结果 1，2，3，5，6，7，8，9
第一趟划分过程
2
3
1
5
9
6
8
7

1
2
3
5
9
6
8
7

1
2
3
5
7
6
8
9

1
2
3
5
6
7
8
9

↑j
↑i

(5，8，1，3，9，6，2，7)
1．(2，8，1，3，9，6，5，7)
2．(2，5，1，3，9，6，8，7)
3．(2，3，1，5，9，6，8，7)
4．(2，3，1，5，9，6，8，7)
第二趟划分过程
(2，3，1，5，9，6，8，7)
1．(1，2，3，5，7，68，9)
(2)非稳定

2
3
1
5
9
6
8
7

1
2
3
5

5
7
6
8
9

5
6
7
8
9

↑j

↑i

第一趟：（2，3，1）5 （9，6，8，7）

第二趟： 1，2，3，5 （9，6，8，7）

第三趟：1，2，3，5，（7，6，8），9

第四趟：1，2，3，5，6，7，8，9

28.假设通信电文使用的字符集为{a，b，c，d，e，f，g，h}，各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。要求：
(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值)；

(2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码。
(1)
(2)
29.已知3阶B—树如图所示，
非根 【1，2】P184
根 【1，2】
(1)画出将关键字6插入之后的B—树；

1,3
6
9
5,8

(2)画出在(1)所得树中插入关键字2之后的B—树。

1,2,3
6
9
5,8

1,3
6
9
5,8

1,2,3
6
9
2,5,8

1
6
9
2,5,8
3

1
6
9
2
3
5
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;
}
}
}
}
(1)2

8
5
7

(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( "% c ", G - > adjlist[ i] vertex)；
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
C
D
E

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 +l].key) {
t = R[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;
}
x=max->data;
}
}
delete_L(Lnode *L,int i)
{Lnode *p,*q;
int j;
Elemtype x;
P=L;j=0;
While(p->next!=null&&j<=i-1)
{p=p->next;j++;}
If(! P->next||i<1)
{ Printf("\n删除位置错误！");return(-1);}
Else{q=p->next;x=q->data;
P->next=q->next;free(q);
Return(x);
}
}/*delete_L*/

全国 10月自学考试数据结构真题
一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项
中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均
无分。

1. 按值可否分解，数据类型一般可分为两类，它们是(c)
A. 静态类型和动态类型
B. 原子类型和表类型
C. 原子类型和结构类型
D. 数组类型和指针类型
2.

A. A f(n)是0(g(n))
B. B g(n)是0(f(n))
C. C h(n)是0(nlogn)
D. D h(n)是0(n2)
答案：C

3. 指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程
序段是()
A. p->next=r；q->next=r->next；r->next=q；
B. p->next=r；r->next=q；q->next=r->next；
C. r->next=q；q->next=r->next；p->next=r；
D. r->next=q；p->next=r；q->next=r->next；
答案：A

4. 若进栈次序为a，b，c，且进栈和出栈能够穿插进行，则可能出现的含3个元素的出栈序列
个数是()
A. 3
B. 5
C. 6
D. 7
答案：B
5. 假设以数组A［n］存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指
针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为()
A. rear==front
B. (front+1)％n==rear
C. rear+1==front
D. (rear+1)％n==front
答案：D

6. 串的操作函数str定义为：

A. 3
B. 4
C. 5
D. 6
答案：C

7. 二维数组A［10］［6］采用行优先的存储方法，若每个元素占4个存储单元，已知元素
A［3］［4］的存储地址为1000，则元素A［4］［3］的存储地址为()
A. 1020
B. 1024
C. 1036
D. 1240
答案：A

8. 对广义表L= (a，())执行操作tail(L)的结果是()
A. ()
B. (())
C. a
D. (a)
答案：B

9. 已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为()
A. FEDCBA

B. ABCDEF
C. FDECBA
D. FBDCEA
答案：A


10. 已知森林F={T1，T2，T3，T4，T5}，各棵树Ti(i=1，2，3，4，5)中所含结点的个数分别
为7，3，5，1，2，则与F对应的二叉树的右子树中的结点个数为()
A. 2
B. 3
C. 8
D. 11
答案：D

11. 若非连通无向图G含有21条边，则G的顶点个数至少为()
A. 7
B. 8
C. 21
D. 22
答案：B

12. 如图所示的有向图的拓扑序列是()
A. c，d，b，a，e
B. c，a，d，b，e
C. c，d，e，a，b
D. c，a，b，d，e
答案：B

13. 对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次划
分的结果为()
A. (5，1，4，3，6，2，8，7)
B. (5，1，4，3，2，6，7，8)
C. (5，1，4，3，2，6，8，7)
D. (8，7，6，5，4，3，2，1)
答案：C

14. 分块查找方法将表分为多块，并要求()
A. 块内有序
B. 块间有序
C. 各块等长
D. 链式存储
答案：B

15. 便于进行布尔查询的文件组织方式是()
A. 顺序文件
B. 索引文件
C. 散列文件
D. 多关键字文件
答案：D


二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）请
在每个空格中填上正确答案。错填、不填均无分。

1. 数据的链式存储结构的特点是借助_指针__表示数据元素之间的逻辑关系。
2. 如果需要对线性表频繁进行_插入__或__删除_操作，则不宜采用顺序存储结构。
3. 如图所示，能够利用一个向量空间同时实现两个类型相同的栈。其中栈1为空的条件是
top1=0，栈2为空的条件是top2=n-1，则“栈满”的判定条件是_ top1>top2(或top2=top1-1或top1=top2+1)。

4. 静态存储分配的顺序串在进行插入、置换和__联接_等操作时可能发生越界。
5. 广义表L=（a，（b，( )））的深度为_3__。
6. 任意一棵完全二叉树中，度为1的结点数最多为_1__。
7. 求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中_边__的数目正相关。

8. 在5阶B树中，每个结点至多含4个关键字，除根结点之外，其它结点至少含_2__个关键字。
9. 若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是_稳定__的。
10. 常见的索引顺序文件是__ ISAM _文件和_ VSAM __文件。
三、解答题(本大题共4小题，每小题5分，共20分)

1. 　

答案：

2. 由字符集{s，t，a，e，i}及其在电文中出现的频度构建的哈夫曼树
如图所示。
已知某段电文的哈夫曼编码为，
请根据该哈夫曼树进行译码，写出原来的电文。
答案：eatst(说明：每个字母1分)（5分）

3. 已知无向图G的邻接表如图所示，
(1)画出该无向图；

(2)画出该图的广度优先生成森林。

4. 对序列(48，37，63，96，22，31，50，55，11)进行升序的堆排序，写出构建的初始(大根
)堆及前两趟重建堆之后的序列状态。
初始堆：
第1趟：
第2趟：
答案：初始堆：（96，55，63，48，22，31，50，37，11）（2分）
第1趟：（63，55，50，48，22，31，11，37，96）（2分）

第2趟：（55，48，50，37，22，31，11，63，96）（1分）

四、算法阅读题(本大题共4小题，每小题5分，共20分)

1. 阅读下列算法，并回答问题：

(1)无向图G如图所示，写出算法f30(&G)的返回值；
(2)简述算法f30的功能。
#define MaxNum 20
int visited［MaxNum］；
void DFS(Graph *g，int i)；
/*从顶点vi出发进行深度优先搜索，访问顶点vj时置visited［j］为1*/
int f30(Graph *g)
{int i，k；
for (i=0； in； i++)／*g->n为图g的顶点数目*／
visited［i］=0；
for (i=k=0； in; i++)
if (visited［i］==0)
{k++；
DFS(g，i)；
}
return k；
}
(1)
(2)
答案：（1）3（3分）
（2）返回无向图g中连通分量的个数。（2分）
2. 假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下：
typedef struct Node {
int id;/*学号*/
int score；/*成绩*/
struct Node *next；
} LNode， *LinkList；
阅读算法f31，并回答问题：
(2)简述算法f31的功能。
void f31(LinkList A, LinkList B)
{LinkList p, q
p=A->next;
q=B->next;
while (p && q)
{if (p->idid)
p=p->next;
else if (p->id >q->id)
q=q->next;
else
{ if (p->score <60)
if (q->score <60)
p->score=q->score;
else p->score=60;
p=p->next;
q=q->next;
}
}
}
(1)
(2)
答案：

3. 阅读下列算法，并回答问题：
(1)设串s=＂OneWorldOneDream＂，t=＂One＂，pos是一维整型数组，写出算法
f32(s，t，pos)执行之后得到的返回值和pos中的值；
(2)简述算法f32的功能。
int strlen(char*s)； /*返回串s的长度*/
int index(char*st，char*t)；
／*若串t在串st中出现，则返回在串st中首次出现的下标值，否则返回-1*/
int f32(char*s, char*t, int pos［］)
{ int i, j, k, ls, lt;
ls=strlen(s);
lt=strlen(t);
if (ls==0||lt==0) return-1;
k=0;
i=0;
do {
j=index(s+i, t);
if (j>=0)
{ pos［k++］=i+j;
i+=j+it;
}
}while(i+it<=is && j >=0
return k;
}
(1)
(2)


答案：（1）2；pos［0］=0,pos［1］=8(说明：每个值1分)（3分）
（2）返回串t在s中出现的次数，并将每次出现的位置依次存放在数组pos中。（2分）

4. 二叉排序树的存储结构定义为以下类型：
typedef int KeyType;
typedef struct node {
KeyType key;/*关键字项*/
InfoType otherinfo;/*其它数据项*/
struct node *lchild, *rchild;/*左、右孩子指针*/
} BSTNode, *BSTree；
阅读算法f33，并回答问题：
(1)对如图所示的二叉排序树T，写出f33(T，8)返回的指针所指结点的关键字；
(2)在哪些情况下算法f33返回空指针?
(3)简述算法f33的功能。
BSTNode *f33(BSTree T, KeyType x)
{ BSTNode *p;
if (T==NULL) return NULL;
p=f33(T>lchild, x);
if (p!=NULL) return p;
if (T->key >x) return T;
return f33(T->rchild, x);
}
(1)
(2)
(3)

答案：（1）10（2分）
（2）T是空树或T中所有结点的关键字均不大于给定值x时，返回空指针。（2分）
（3）如果二叉排序树T中存在含有关键字大于给定值x的结点，则返回指针指向它们中关键字最
小的结点，否则返回空指针。（1分）

五、算法设计题（本题10分）

1. 假设线性表采用顺序存储结构，其类型定义如下：
#define ListSize 100
typedef struct {
int data［ListSize］;
int length;
} SeqList, *Table;
编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。
答案：参考答案一：
void f34(Table L)(或者参数说明为：SeqList *L,1分)
{ int i,j,t;
i=0;（初始化，1分）
j=L->length-1;
while(idata［i］%2)（1分）
i++;
while(idata［j］%2==0)（1分
j--;
if(idata［i］;（交换，2分）
L->data［i］=L->data［j］;
L->data［j］=t;
i++;(i和j,1分)
j--;
}
}(其它，如“L->”表示，1分)
}
参考答案二：
void f34(SeqList*L)(或者参数说明为：Table L,1分)
{ int i,j=0,t;(初始化，1分)
for(i=0;ilength;i++)(循环控制，2分)
if(L->data［i］%2)/*奇数*/（奇数处理框架，1分）
{ if(i!=j)(避免同一元素交换，1分)
{ t=L->data［i］;(交换，2分)
L->data［i］=L->data［j］;
L->data［j］=t;
j++;（1分）
}（其它，如“L->”表示，1分）
}

全国 1月自学考试数据结构试题
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．若一个算法的时间复杂度用T(n)表示，其中n的含义是（ A ）
A．问题规模 B．语句条数
C．循环层数 D．函数数量
2．具有线性结构的数据结构是（ C 线性结构有：顺序表、栈和队列、串
A．树 B．图
C．栈和队列 D．广义表
3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（ B ）
A．O(1) B．O(m)
C．O(n) D．O(m+n)
插入到长度为m的单链表，需找到表尾，时间复杂度为o(m)，连接的时间复杂度为0(1),因此总的时间复杂度为0(m)
4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ C ）
A．2个 B．3个
C．4个 D．6个
void DInsertBefore(DListNode *p,DataType x)//在带头结点的双链表中，将值为x的新结点插入结点*p之前，设p≠NULL {DListNode *s=malloc(sizeof(ListNode));①
s->data=x;②s->prior=p->prior; ③s->next=p;④p->prior->next=s;⑤p->prior=s; } ⑥
5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ B ）
A．3 B．37
C．50 D．97
对于循环向量中的循环队列，写出经过队头队尾指针表示的队列长度公式。（front指向实际队头，rear指向实际队尾的下一元素位置。）当rear≥front时，队列长度L=rear-front；当rearSoftware”，其子串的数目是（ D ）
A．8 B．9
C．36 D．37
8．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为 （ C ）
A．1012 B．1017
C．1032 D．1039
在n阶方阵A这个下三角矩阵中，第i（i从0开始）行（0≤i1)/2+j。
若i二叉树的是（ A ）
A．B树 B树是一种平衡的多叉树 B．AVL树 AVL树是自平衡二叉查找树
C．二叉排序树 D．哈夫曼树 哈夫曼树是最优二叉树
11．对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ）

A．1，5，2，6，3，4 B．1，5，6，2，3，4
C．5，1，6，3，4，2 D．5，1，2，6，4，3
12．以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ D ）

A．v1，v2，v3，v4，v5，v6，v7 B．v1，v2，v5，v4，v3，v7，v6
C．v1，v2，v3，v4