全国2010年1月高等教育自学考试数据结构试题
编辑整理:东莞自考网 发表时间:2018-05-24 07:05:13 【大 中 小】 [添加招生老师微信]
《自考视频课程》名师讲解,轻松易懂,助您轻松上岸!低至199元/科!
全国2010年1月高等教育自学考试数据结构试题
课程代码:02331
一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.错选、多选或未选均无分.
1.若一个算法的时间复杂度用T(n)表示,其中n的含义是( )
A.问题规模
B.语句条数
C.循环层数
D.函数数量
2.具有线性结构的数据结构是( )
A.树
B.图
C.栈和队列
D.广义表
3.将长度为n的单链表连接在长度为m的单链表之后,其算法的时间复杂度为( )
A.O(1)
B.O(m)
C.O(n)
D.O(m+n)
4.在带头结点的双向循环链表中插入一个新结点,需要修改的指针域数量是( )
A.2个
B.3个 .
C.4个
D.6个
5.假设以数组A[60]存放循环队列的元素,其头指针是front=47,当前队列有50个元素,则队列的尾指针值为( )
A.3
B.37
C.50
D.97
6.若栈采用链式存储结构,则下列说法中正确的是( )
A.需要判断栈满且需要判断栈空
B.不需要判断栈满但需要判断栈空
C.需要判断栈满但不需要判断栈空
D.不需要判断栈满也不需要判断栈空
7.若串str="Software",其子串的数目是( )
A.8
B.9
C.36
D.37
8.设有一个10阶的下三角矩阵A,采用行优先压缩存储方式,all为第一个元素,其存储地址为1000,每个元素占一个地址单元,则a85的地址为 ( )
A.1012
B.1017
C.1032
D.1039
9.允许结点共享的广义表称为( )
A.纯表
B.线性表
C.递归表
D.再入表
10.下列数据结构中,不属于二叉树的是( )
A.B树
B.AVL树
C.二叉排序树
D.哈夫曼树
11.对下面有向图给出了四种可能的拓扑序列,其中错误的是( )
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为起始结点对下图进行深度优先遍历,正确的遍历序列是( )
A.v1,v2,v3,v4,v5,v6,v7
B.v1,v2,v5,v4,v3,v7,v6
C.v1,v2,v3,v4,v7,v5,v6
D.v1,v2,v5,v6,v7,v3,v4
13.下列排序算法中不稳定的是( )
A.快速排序
B.归并排序
C.冒泡排序
D.直接插入排序
14.一个有序表为(1,3,9,12,32,41,45,62,75,77,82,95,100),当采用折半查找方法查找值32时,查找成功需要的比较次数是( )
A.2
B.3
C.4
D.8
15.采用ISAM组织文件的方式属于( )
A.链组织
B.顺序组织
C.散列组织
D.索引组织
二、填空题(本大题共10小题,每小题2分,共20分)
请在每小题的空格中填上正确答案.错填、不填均无分.
16.数据元素及其关系在计算机存储器内的表示称为_________.
17.长度为n的线性表采用单链表结构存储时,在等概率情况下查找第i个元素的时间复杂度是_________.
18.下面是在顺序栈上实现的一个栈基本操作,该操作的功能是_________.
typedef struct{
DataType data[100];
int top;
}SeqStack;
DataType f18(SeqStack*S)
{ if(StackEmpty(S))
Error("Stack is empty");
return S->data[S->top];
}
19.在串匹配中,一般将主串称为目标串,将子串称为_________.
20.已知广义表C=(a(b,c),d),则:tail(head(tail(C)))= _________.
21.用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树,该树的带权路径长度为_________.
22.已知有向图如下所示,其中顶点A到顶点C的最短路径长度是_________.
23.对序列{55,46,13,05,94,17,42}进行基数排序,第一趟排序后的结果是_________.
24.高度为3的3阶B-树最少的关键字总数是_________.
25.VSAM通常作为大型索引顺序文件的标准组织,其动态索引结构采用的是_________.
三、解答题(本大题共4小题,每小题5分,共20分)
26.假设二叉树的RNL遍历算法定义如下:
若二叉树非空,则依次执行如下操作:
(1)遍历右子树;
(2)访问根节点;
(3)遍历左子树.
已知一棵二叉树如图所示,请给出其RNL遍历的结果序列.
27.已知一个无向图G=(V,E),其中V={A,B,C,D,E,F},邻接矩阵表示如下所示.
请回答下列问题:
(1)请画出对应的图G.
(2)画出图G的邻接表存储结构.
28.已知一组待排记录的关键字序列为(16,12,18,60,15,36,14,18,25,85),用堆排序方法建小根堆,请给出初始建堆后的序列.
29.已知一棵二叉排序树如图所示.
请回答下列问题:
(1)画出插入元素23后的树结构;
(2)请画出在原图中删除元素57后的树结构.
四、算法阅读题(本大题共4小题,每小题5分,共20分)
30.已知下列程序,Ls指向带头结点的单链表.
Typedefstruct node {
DataType data;
struct node * next;
} * LinkList;
void f30( LinkList Ls )
{ LinkList p, q;
q = Ls->next;
if ( q && q->next ) {
Ls->next = q->next;
p=q
while ( p->next )
p = p->next;
p->next = q;
q->next = NULL;
}
}
请回答下列问题:
(1)当Ls指向的链表如下图所示,请画出执行本函数之后的链表的结果.
(2)请简述算法的功能.
31.已知字符串处理函数f31程序如下.
int f31(char*strl,char*str2)
{ while(*strl==*str2&&(*strl!=’\0’)){
strl++;
str2++;
}
return(*strl-*str2 ? l∶0);
}
请回答下列问题:
(1)若调用语句是f31("abcde","abcdf’),则函数的返回值是什么?若调用语句是 f31("abcde","abcde"),则函数的返回值是什么?
(2)简述该函数的功能.
32.数组A[]中存储有n个整数,请阅读下列程序.
void f32(intA[],int n)
{ inti,j,k,x;
k=n-l;
while(k>0){
i=k; k=0;
for(j=O;jif(A[j]>A[j+1]){
x=A[j];
A[j]=A[j+l];
A[j+1]=x;
k=j;
}//end of if
}//end of while
return;
}
请回答下列问题:
(1)当A[]={10,8,2,4,6,7}时,执行f32(A,6)后,数组A中存储的结果是什么?
(2)说明该算法的功能.
33.下面程序实现二分查找算法.
Typedef struct{
KeyType key;
InfoType otherinfo;
}SeqList[N+1];
int BinSearch(SeqList R, int n,KeyType K)
{ int low=1,high=n;
while( (1) ){
mid=
[1]
本文标签:东莞自考 历年真题 全国2010年1月高等教育自学考试数据结构试题
转载请注明:文章转载自(http://www.dongguanzikao.com)
《东莞自考网》免责声明:
1、由于考试政策等各方面情况的调整与变化,本网提供的考试信息仅供参考,最终考试信息请以省考试院及院校官方发布的信息为准。
2、本站内容部分信息均来源网络收集整理或来源出处标注为其它媒体的稿件转载,免费转载出于非商业性学习目的,版权归原作者所有,如有内容与版权问题等请与本站联系。联系邮箱:812379481@qq.com