2020年10月全国自考数据结构试题及答案解析.doc
??????????????????????精品自学考料推荐??????????????????
全国 2018 年 10 月高等教育自学考试
数据结构试题
课程代码： 02331
一、单项选择题（本大题共15 小题，每小题 2 分，共 30 分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选
均无分。
1．数据结构是（）
A．一种数据类型
B．数据的存储结构
C．一组性质相同的数据元素的集合
D．相互之间存在一种或多种特定关系的数据元素的集合
2．算法分析的目的是（）
A．辨别数据结构的合理性
B．评价算法的效率
C．研究算法中输入与输出的关系
D．鉴别算法的可读性
3．在线性表的下列运算中，不．改变数据元素之间结构关系的运算是（）
A ．插入
B ．删除
C．排序 D ．定位
4．若进栈序列为 1， 2， 3，4， 5， 6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）
A ． 3，2， 6， 1， 4， 5
B ．3， 4， 2，1， 6， 5
C． 1， 2， 5， 3，4， 6 D ．5， 6， 4， 2， 3，1
5．设串 sl=″ Data Structures with Java ″ ,s2=″it ″，则子串定位函数index(s1,s2)的值为
（）A ． 15 B ．16
C． 17 D ．18
6．二维数组 A[8][9] 按行优先顺序存储，若数组元素A[2][3] 的存储地址为 1087，A[4][7] 的存储地址为1153，则数组元素 A[6][7] 的存储地址为（）
A ． 1207
B ．1209
1
C． 1211 D ．1213
7．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（）
A ．队列
B ．栈
C．线性表 D ．有序表
8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（）
A ．不一定相同
B ．都相同
C．都不相同 D ．互为逆序
9．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（）
A ．层次遍历算法
B ．前序遍历算法
C．中序遍历算法 D ．后序遍历算法
10．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（）
A ．图中每个顶点的入度
B ．图中每个顶点的出度
C．图中弧的条数 D ．图中连通分量的数目
11．图的邻接矩阵表示法适用于表示（）
A ．无向图
B ．有向图
C．稠密图 D ．稀疏图
12．在对n 个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i 趟排序之前，无序区中关键字元素的个数为（）
A ． i
B ．i+1
C． n-i D ．n-i+1
13．下列排序算法中，其时间复杂度和记录的初始排列无关的是（）
A ．插入排序
B ．堆排序
C．快速排序 D ．冒泡排序
14．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字 b 的过程中，先后进行比较的关键字依次为（）
A ． f,c,b
B ．f,d,b
C． g,c,b D ．g,d,b
15．若在文件中查询年龄在60 岁以上的男性及年龄在55 岁以上的女性的所有记录，则查询条件为（）
A ．（性别 =“男”） OR(年龄 > 60)OR （性别 =“女”） OR（年龄 >55）
B ．（性别 =“男”） OR(年龄 > 60)AND （性别 =“女”） OR（年龄 >55 ）
C．（性别 =“男”） AND( 年龄 > 60)OR （性别 =“女”） AND （年龄 >55 ）
2
D ．（性别 =“男”） AND( 年龄 > 60)AND （性别 =“女”）AND （年龄 >55）
二、填空题（本大题共10 小题，每小题 2 分，共 20 分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16．称算法的时间复杂度为O(f(n)) ，其含义是指算法的执行时间和_______的数量级相同。
17．在一个长度为n 的单链表L 中，删除链表中*p 的前驱结点的时间复杂度为_________。
18．假设为循环队列分配的向量空间为Q[20] ，若队列的长度和队头指针值分别为13 和 17，则当前尾指针的值为______ 。
19．设 s=″ I AM A ATHLETE ″ ,t=″ GOOD ″，则执行下列串操作序列之后得到的sub1 为________。
substr (sub1,s,5,2)； substr(sub2,s,6,8); strcpy(t1,t);
strcat(t1,sub2); strcat(sub1,t1);
20．广义表的深度是指_______。
21．一棵含999 个结点的完全二叉树的深度为_______。
22．含 n 个顶点的无向连通图中至少含有______条边。
23．对表长为9000 的索引顺序表进行分块查找，假设每一块的长度均为15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为_____。
24．若对关键字序列（ 43， 02， 80， 48，26， 57，15， 73， 21， 24， 66）进行一趟增量为 3 的希尔排序，则得到的结果为 ______。
25． ISAM 文件由主索引、______、 ______和主文件组成。
三、解答题（本大题共 4 小题，每小题 5 分，共 20 分）
26．某广义表的表头和表尾均为（a,(b,c)），画出该广义表的图形表示。
27．已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。
（1）画出该二叉树；
（2）画出与（ 1）求得的二叉树对应的森林。
（1）
（2）
28．已知带权图的邻接表如下所示，其中边表结点的结构为：
3
依此邻接表从顶点 C 出发进行深度优先遍历。
（1）画出由此得到的深度优先生成树；
（2）写出遍历过程中得到的从顶点C 到其它各顶点的带权路径及其长度。
（1）
（2）
29．从空树起，依次插入关键字37， 50， 42， 18， 48， 12， 56， 30， 23，构造一棵二叉排序树。
（ 1）画出该二叉排序树；
（ 2）画出从（ 1）所得树中删除关键字为37 的结点之后的二叉排序树。
（1）
（2）
四、算法阅读题（本大题共 4 小题，每小题 5 分，共 20 分）
30．已知用有序链表存储整数集合的元素。阅读算法f30，并回答下列问题：
（ 1）写出执行f30（ a,b）的返回值，其中 a 和 b 分别为指向存储集合{2 ， 4， 5，7， 9， 12} 和 {2 ， 4， 5， 7， 9} 的链表的头指针；
（2）简述算法 f30 的功能；
（3）写出算法 f30 的时间复杂度。
int f30(LinkList ha,LinkList hb)
{
//LinkList是带有头结点的单链表
//ha 和 hb 分别为指向存储两个有序整数集合的链表的头指针
LinkList pa,pb;
pa=ha->next;
pb=hb->next;
while(pa && pb && pa->data==pb->data)
{ pa=pa->next;
4
pb=pb->next;
}
if(pa==NULL && pb==NULL) return 1;
else return 0;
}
(1)
(2)
(3)
31．已知稀疏矩阵采用带行表的三元组表表示，其形式说明如下：
#define MaxRow100//稀疏矩阵的最大行数
typedef struct {
int i,j,v;//行号、列号、元素值
}TriTupleNode;
typedef struct{
TriTupleNode data[MaxSize];
int RowTab[MaxRow+1];//行表
int m,n,t;//矩阵的行数、列数和非零元个数
}RTriTupleTable;
下列算法f31 的功能是，以行优先的顺序输入稀疏矩阵的非零元（行号、列号、元素值），建立稀疏矩阵的带行表的三元组表存储结构。请在空缺处填入合适内容，使其成为一个完整的算法。（注：矩阵的行、列下标均从 1 起计）
void f31(RTriTupleTable *R)
{ int i,k;
scanf(″ %d %d %d ″ ,&R->m,&R->n,&R->t);
R->RowTab[1]=0;
k=1;//k 指示当前输入的非零元的行号
for(i=0;①；i++)
{ scanf(″ %d %d %d ″ ,②，③，&R->data[i].v);
while(k
{④；
R->RowTab[k]=i;
5
}
}
}
①
②
③
④
32．已知二叉树的存储结构为二叉链表，其类型定义如下：typedef struct NodeType {
DataType data;
struct NodeType *lchild,*rchild;
}BinTNode,*BinTree;
阅读算法F32，并回答下列问题：
(1) 对于如图所示的二叉树，画出执行算法f32 的结果；
（ 2）简述算法f32 的功能。
BinTree f32(BinTree bt1)
{
BinTree bt2;
if(bt1==NULL)
bt2=NULL;
else {
bt2=(BinTNode *)malloc(sizeof(BinTNode));
bt2->data=bt1->data;
bt2->rchild=f32(bt1->lchild);
6
bt2->lchild=f32(bt1->rchild);
}
return bt2;
}
(1)
(2)
33．假设有向图采用邻接表表示法，其定义如下：
typedef struct {
VertexNode adjlist[MaxVertexNum];
int n,e;// 图的当前顶点数和弧数
} ALGraph;//邻接表类型
其中顶点表结点VertexNode 结构为：vertex firstedge
边表结点 EdgeNode 结构为：adjvexnext
下列算法f33 的功能是，对以邻接表表示的有向图进行拓扑排序。
（1）阅读算法 f33，并在空缺处填入
合适的内容，使其成为一个完
整的算法；
（2）对于如图所示的邻接表，将执行
算法 f33 后的 topo[ ] 结果填入给
定的数组中。
void f33(ALGraph G , int topo [ ]){
int i,j,k,count=0;
int indegree[MaxVertexNum];
EdgeNode *p;//p 为指向边表结点的指针
Queue Q;//Q 为队列
FindIndegree(G, indegree);//求各顶点的入度，并置于入度向量indegree
7
InitQueue(&Q);
for(i=0;i if(!indegree[i])EnQueue(&Q,i); while(!QueueEmpty(&Q)){ j=①; topo[j]=++count; for(p=G .adjlist[j].firstedge;p;p=->next){ k=p->adjvex; if(!(--indegree[k]))②; } } if(count } （1）① ② （2）topo 01234567 五、算法设计题（本大题10 分） 34．假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node{ DataType data; struct node *next }LinkNode, *LinkList; 编写算法，从有序表 A 中删除所有和有序表 B 中元素相同的结点。 8