全国2008年1月高等教育自学考试数据结构试题
《自考视频课程》名师讲解,轻松易懂,助您轻松上岸!低至199元/科!
全国2008年1月高等教育自学考试
数据结构试题
课程代码:02331
一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.错选、多选或未选均无分.
1.逻辑上通常可以将数据结构分为( )
A.动态结构和静态结构
B.顺序结构和链式结构
C.线性结构和非线性结构
D.初等结构和组合结构
2.在下列对顺序表进行的操作中,算法时间复杂度为O(1)的是( )
A.访问第i个元素的前驱()
B.在第i个元素之后插入一个新元素()
C.删除第i个元素()
D.对顺序表中元素进行排序
3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是( )
A.head= =NULL
B.head–>next= =NULL
C.head!=NULL
D.head–>next= =head
4.已知栈的最大容量为4.若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为( )
A.5,4,3,2,1,6
B.2,3,5,6,1,4
C.3,2,5,4,1,6
D.1,4,6,5,2,3
5.与线性表相比,串的插入和删除操作的特点是( )
A.通常以串整体作为操作对象
B.需要更多的辅助空间
C.算法的时间复杂度较高
D.涉及移动的元素更多
6.假设以三元组表表示稀疏矩阵,则与如图所示三元组表对应的4×5的稀疏矩阵是(注:矩阵的行列下标均从1开始)( )
7.以下有关广义表的表述中,正确的是( )
A.由0个或多个原子或子表构成的有限序列
B.至少有一个元素是子表
C.不能递归定义
D.不能为空表
8.树的先根序列等同于与该树对应的二叉树的( )
A.先序序列
B.中序序列
C.后序序列
D.层序序列
9.假设有向图含n个顶点及e条弧,则表示该图的邻接表中包含的弧结点个数为( )
A.n
B.e
C.2e
D.n·e
10.如图所示的有向无环图可以得到的不同拓扑序列的个数为( )
A.1
B.2
C.3
D.4
11.下列排序方法中,稳定的排序方法为( )
A.希尔排序
B.堆排序
C.快速排序
D.直接插入排序
12.对下列关键字序列进行快速排序时,所需进行比较次数最少的是( )
A.(1,2,3,4,5,6,7,8)
B.(8,7,6,5,4,3,2,1)
C.(4,3,8,6,1,7,5,2)
D.(2,1,5,4,3,6,7,8)
13.含n个关键字的二叉排序树的平均查找长度主要取决于( )
A.关键字的个数
B.树的形态
C.关键字的取值范围
D.关键字的数据类型
14.下列查找算法中,平均查找长度与元素个数n不直接相关的查找方法是( )
A.分块查找
B.顺序查找
C.二分查找
D.散列查找
15.可有效提高次关键字查找效率的文件是( )
A.顺序文件
B.倒排文件
C.散列文件
D.VSAM文件
二、填空题(本大题共10小题,每小题2分,共20分)
请在每小题的空格中填上正确答案.错填、不填均无分.
16.数据的存储结构是其逻辑结构___________.
17.输入线性表的n个元素建立带头结点的单链表,其时间复杂度为___________.
18.假设循环队列的元素存储空间大小为m,队头指针f指向队头元素,队尾指针r指向队尾元素的下一个位置,则在少用一个元素空间的前提下,表示"队满"的条件是___________.
19.给定串的联接操作函数:char *strcat(char *to, char *from);
//将串from联接到串to的末尾,并返回联接后的串
若字符串s1=〞point〞,s2=〞of〞,则strcat(s1,strcat)(s2,s1))的操作结果是___________.
20.假设二维数组A[8][10]按行优先顺序存储,若每个元素占2个存储单元,元素A[0][0]的存储 地址为100,则元素A[4][5]的存储地址为___________.
21.假设一棵完全二叉树含1000个结点,则其中度为2的结点数为___________.
22.已知一个有向网如图所示,从顶点1到顶点4的最短路径长度为___________.
23.在快速排序、堆排序和归并排序中,最坏时间复杂度为O(n2)的排序算法有___________.
24.假设散列表的表长为11,散列函数为H(key)=key%7,若用线性探测处理冲突,则探查地址序列hi的计算公式为___________.
25.VSAM文件由___________,___________和数据集三部分组成.
三、解答题(本大题共4小题,每小题5分,共20分)
26.已知广义表的图形表示如图所示.
1.写出该广义表L;
2.分别写出该广义表的深度和长度.
1.____________________________
2.____________________________
27.已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF
1.画出该二叉树的二叉链表存储表示;
2.写出该二叉树的后序序列.
(1)_______________________________
(2)_______________________________
28.已知有向图的邻接表如图所示
1,写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列;
画出该有向图的逆邻接表.
(1)_______________________________
(2)_______________________________
29.依次读入给定的整数序列{7,16,4,8,20,9,6,18,5},完成下列操作:
1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树的平均查找长度ASL;
2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树.写出满足上述要求的序列中的第一个元素.
(1)____________________________
(2)____________________________
四、算法阅读题(本大题共4小题,每小题5分,共20分)
30.假设以带头结点的单链表表示线性表,阅读下列算法f30,并回答问题:
1.设线性表为( a1, a2, a3, a4, a5, a6, a7 ), 写出执行算法f30后的线性表;
2.简述算法f30的功能.
void f30(LinkList L)
{
//L为带头结点单链表的头指针
LinkList p,q;
P =L;
while (p &&p–>next){
q = p–>next;
p–>next =q–>next;
p =q–>next;
free(q);
}
}
(1)____________________________
(2)____________________________
31.算法f31的功能是借助栈结构实现整数从10进制到8进制的转换,阅读算法并回答问题:
1.画出n为十进制的1348时算法执行过程中栈的动态变化情况;
2.说明算法中while循环完成的操作.
void f31(int n) //n为非负的十进制整数
{
int e;
SeqStack S;
InitStack(& S);
do{
Push(& S,n%8);
n =n/8;
}while (n);
while ( ! StackEmpty(& S)){
e =Pop(& S);
printf (〞%ld〞,e);
}
}
(1)___________________________________
(2)___________________________________
32.已知以二叉链表作二叉树的存储结构,阅读算法f32,并回答问题:
1.设二叉树T如图所示,写出执行f32(T)的返回值;
2.简述算法f32的功能.
int f32(BinTree T)
{
int m, n;
if(! T)
return 0;
else{
m= f32(T–>lchild);
n = f 32(T–>rchild);
if(m>n)return m +1;
else return n+1;
}
}
(1)_________________________
(2)_________________________
33.设有向图邻接表定义如下;
typedef struct{
VertexNode adjlist[Max VertexNum];
int n,e; //图的当前顶点数和弧数
} ALGraph; //邻接表类型
阅读下列算法f33,并回答问题:
(1)已知有向图G的邻接表如图所示,
写出算法f33的输出结果;
(2)简述算法f33的功能.
void dfs (ALGraph *G,int v)
{
EdgeNode * p;
visited[v]=TRUE;
printf(〞%c〞,G–>adjlist[v]·vertex);
for(p =G–>adjlist[v])·firstedge; p; p=p–>next)
if(! visited[p–>adjvex])
dfs (G, p–>adjvex);
}
void f33(ALGraph *G)
{
int v,w;
for(v=0; v
for(w=0;w
visited[w]=FALSE;
printf(〞%d: 〞,v);
dfs(G,v);
printf(〞﹨n〞);
}
}
(1)______________________________
(2)______________________________
五、算法设计题(本大题10分)
34.假设以单链表表示线性表,单链表的类型定义如下:
typedef struct node {
DataType data;
struct node *next;
} LinkNode, *LinkList;
编写算法,将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表,并分析算法的时间复杂度.
本文标签:河南自考 历年真题 全国2008年1月高等教育自学考试数据结构试题
转载请注明:文章转载自(http://www.hazikao.net)
《河南自考网》免责声明:
1、由于各方面情况的调整与变化,本网提供的考试信息仅供参考,考试信息以省考试院及院校官方发布的信息为准。
2、本网信息来源为其他媒体的稿件转载,免费转载出于非商业性学习目的,版权归原作者所有,如有内容与版权问题等请与本站联系。联系邮箱:812379481@qq.com。