至数据结构答案02331jpg概论.docx
- 文档编号:2663981
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:78
- 大小:1.67MB
至数据结构答案02331jpg概论.docx
《至数据结构答案02331jpg概论.docx》由会员分享,可在线阅读,更多相关《至数据结构答案02331jpg概论.docx(78页珍藏版)》请在冰点文库上搜索。
至数据结构答案02331jpg概论
全国2010年1月高等教育自学考试
数据结构试题及参考答案
课程代码:
02331
一、单项选择题(本大题共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)
4.在带头结点的双向循环链表中插入一个新结点,需要修改的指针域数量是(C)
A.2个B.3个
C.4个D.6个
5.假设以数组A[60]存放循环队列的元素,其头指针是front=47,当前队列有50个元素,则队列的尾指针值为(B)
A.3B.37
C.50D.97
6.若栈采用链式存储结构,则下列说法中正确的是(B)
A.需要判断栈满且需要判断栈空
B.不需要判断栈满但需要判断栈空
C.需要判断栈满但不需要判断栈空
D.不需要判断栈满也不需要判断栈空
7.若串str=”Software”,其子串的数目是(D)
A.8B.9
C.36D.37
8.设有一个10阶的下三角矩阵A,采用行优先压缩存储方式,all为第一个元素,其存储地址为1000,每个元素占一个地址单元,则a85的地址为(C)
A.1012B.1017
C.1032D.1039
9.允许结点共享的广义表称为(D)
A.纯表B.线性表
C.递归表D.再入表
10.下列数据结构中,不属于二叉树的是(A)
A.B树B.AVL树
C.二叉排序树D.哈夫曼树
11.对下面有向图给出了四种可能的拓扑序列,其中错误的是(C)
A.1,5,2,6,3,4B.1,5,6,2,3,4
C.5,1,6,3,4,2D.5,1,2,6,4,3
12.以v1为起始结点对下图进行深度优先遍历,正确的遍历序列是(D)
A.v1,v2,v3,v4,v5,v6,v7B.v1,v2,v5,v4,v3,v7,v6
C.v1,v2,v3,v4,v7,v5,v6D.v1,v2,v5,v6,v7,v3,v4
13.下列排序算法中不稳定的是(A)
A.快速排序B.归并排序
C.冒泡排序D.直接插入排序
14.一个有序表为(1,3,9,12,32,41,45,62,75,77,82,95,100),当采用折半查找方法查找值32时,查找成功需要的比较次数是(B)
A.2B.3
C.4D.8
15.采用ISAM组织文件的方式属于(D)
A.链组织B.顺序组织
C.散列组织D.索引组织
二、填空题(本大题共10小题,每小题2分,共20分)
请在每小题的空格中填上正确答案。
错填、不填均无分。
16.数据元素及其关系在计算机存储器内的表示称为__存储结构_______。
17.长度为n的线性表采用单链表结构存储时,在等概率情况下查找第i个元素的时间复杂度是___O(n)______。
18.下面是在顺序栈上实现的一个栈基本操作,该操作的功能是_________。
typedefstruct{
DataTypedata[100];
inttop;
}SeqStack;
DataTypef18(SeqStack*S)
{if(StackEmpty(S))
Error(”Stackisempty”);
returnS->data[S->top];
}
19.在串匹配中,一般将主串称为目标串,将子串称为___模式串______。
20.已知广义表C=(a(b,c),d),则:
tail(head(tail(C)))=___()______。
21.用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树,该树的带权路径长度为___221______。
22.已知有向图如下所示,其中顶点A到顶点C的最短路径长度是___35______。
23.对序列{55,46,13,05,94,17,42}进行基数排序,第一趟排序后的结果是_10,42,12,94,55,01,46,17。
24.高度为3的3阶B-树最少的关键字总数是__13_______。
25.VSAM通常作为大型索引顺序文件的标准组织,其动态索引结构采用的是___B+______。
三、解答题(本大题共4小题,每小题5分,共20分)
26.假设二叉树的RNL遍历算法定义如下:
若二叉树非空,则依次执行如下操作:
(1)遍历右子树;
(2)访问根节点;
(3)遍历左子树。
已知一棵二叉树如图所示,请给出其RNL遍历的结果序列。
GCFABDC
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指向带头结点的单链表。
Typedefstructnode{
DataTypedata;
structnode*next;
}*LinkList;
voidf30(LinkListLs)
{LinkListp,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程序如下。
intf31(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个整数,请阅读下列程序。
voidf32(intA[],intn)
{inti,j,k,x;
k=n-l;
while(k>0){
i=k;k=0;
for(j=O;j
if(A[j]>A[j+1]){
x=A[j];
A[j]=A[j+l];
A[j+1]=x;
k=j;
}//endofif
}//endofwhile
return;
}
请回答下列问题:
(1)当A[]={10,8,2,4,6,7}时,执行f32(A,6)后,数组A中存储的结果是什么?
(2)说明该算法的功能。
33.下面程序实现二分查找算法。
Typedefstruct{
KeyTypekey;
InfoTypeotherinfo;
}SeqList[N+1];
intBinSearch(SeqListR,intn,KeyTypeK)
{intlow=1,high=n;
while(
(1)){
mid=(1ow+high)/2;
if(
(2))
returnmid;
if(R[mid].key>K)
high=mid-1;
else
(3);
}
returnO;
}//BinSearch
请在空白处填写适当内容,使该程序功能完整。
(1)
(2)
(3)
五、算法设计题(本题10分)
34.已知二叉树采用二叉链表存储,其结点结构定义如下:
typedefstructNode{
ElmTypedata;
structNode*lchild,*rchild;
}*BiTree;
请编写递归函数SumNodes(BiTreeT),返回二叉树T的结点总数。
2010年10月
32、下面程序实现插入排序算法。
typedefstruct{
intkey;
Infootherinof;
}Seqlist;
voidInsertSort(SeqListR[],intn)
{/*待排序列保存在R[1..n]中*/
Seqlistx;
inti,j,k,lo,hi,mi;
for(i=2;i<=n;i++)
{
x=R[i];
lo=1;
hi=i-1;
/*用二分查找法找到待排序数据插入的位置*/
while(lo<=hi)
{
mi=(lo+hi)/2;
if(R[mi].key==x.key)break;
if(R[mi].key>x.key)hi=mi-1;
elselo=mi+1;
}
/*完成插入*/
if(mi=lo)k=i-mi;
elsek=i-mi-1;
for(j=0;j R[i-j]=R[i-j-1]; R[i-j]=x; } } 全国2011年1月高等教育自学考试 数据结构试题 课程代码: 02331 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。 错选、多选或未选均无分。 1.下列选项中与数据存储结构无关的术语是() A.顺序表B.链表 C.链队列D.栈 2.将两个各有n个元素的有序表归并成一个有序表,最少的比较次数是() A.n-1B.n C.2n-1D.2n 3.已知循环队列的存储空间大小为m,队头指针front指向队头元素,队尾指针rear指向队尾元素的下一个位置,则向队列中插入新元素时,修改指针的操作是() A.rear=(rear-1)%m;B.front=(front+1)%m; C.front=(front-1)%m;D.rear=(rear+1)%m; 4.递归实现或函数调用时,处理参数及返回地址,应采用的数据结构是() A.堆栈B.多维数组 C.队列D.线性表 5.设有两个串p和q,其中q是p的子串,则求q在p中首次出现位置的算法称为() A.求子串B.串联接 C.串匹配D.求串长 6.对于广义表A,若head(A)等于tail(A),则表A为() A.()B.(()) C.((),())D.((),(),()) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反,则该二叉树一定是 () A.结点均无左孩子的二叉树B.结点均无右孩子的二叉树 C.高度为n的二叉树D.存在度为2的结点的二叉树 8.若一棵二叉树中度为l的结点个数是3,度为2的结点个数是4,则该二叉树叶子结点的个数是() A.4B.5 C.7D.8 9.下列叙述中错误的是() A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次 B.图的遍历可以采用深度优先遍历和广度优先遍历 C.图的广度优先遍历只适用于无向图 D.图的深度优先遍历是一个递归过程 10.已知有向图G=(V,E),其中V={V1,V2,V3,V4},E={ A.V1,V2,V3,V4B.V1,V3,V2,V4 C.V1,V3,V4,V2D.V1,V2,V4,V3 11.平均时间复杂度为O(nlogn)的稳定排序算法是() A.快速排序B.堆排序 C.归并排序D.冒泡排序 12.已知关键字序列为(51,22,83,46,75,18,68,30),对其进行快速排序,第一趟划分完成后的关键字序列是() A.(18,22,30,46,51,68,75,83)B.(30,18,22,46,51,75,83,68) C.(46,30,22,18,51,75,68,83)D.(30,22,18,46,51,75,68,83) 13.某索引顺序表共有元素395个,平均分成5块。 若先对索引表采用顺序查找,再对块中元素进行顺序查找,则在等概率情况下,分块查找成功的平均查找长度是() A.43B.79 C.198D.200 14.在含有10个关键字的3阶B-树中进行查找,至多访问的结点个数为() A.2B.3 C.4D.5 15.ISAM文件系统中采用多级索引的目的是() A.提高检索效率B.提高存储效率 C.减少数据的冗余D.方便文件的修改 二、填空题(本大题共10小题,每小题2分,共20分) 请在每小题的空格中填上正确答案。 错填、不填均无分。 16.数据结构由数据的逻辑结构、存储结构和数据的____________三部分组成。 17.在单链表中某结点后插入一个新结点,需要修改_______________个结点指针域的值。 18.设栈S的初始状态为空,若元素a、b、c、d、e、f依次进栈,得到的出栈序列是b、d、c、f、e、a,则栈S的容量至少是________________。 19.长度为零的串称为________________。 20.广义表G=(a,b,(c,d,(e,f)),G)的长度为________________。 21.一棵树T采用孩子兄弟链表存储,如果树T中某个结点为叶子结点,则该结点在二叉链表中所对应的结点一定是________________。 22.一个有n个顶点的无向连通图,最少有________________条边。 23.当待排关键字序列基本有序时,快速排序、简单选择排序和直接插入排序三种排序方法中,运行效率最高的是________________。 24.在一棵深度为h的具有n个结点的二叉排序树中,查找任一结点的最多比较次数是______________。 25.不定长文件指的是文件的____________大小不固定。 三、解答题(本大题共4小题,每小题5分,共20分) 26.已知一棵二叉排序树(结点值大小按字母顺序)的前序遍历序列为EBACDFHG, 请回答下列问题: (1)画出此二叉排序树; (2)若将此二叉排序树看作森林的二叉链表存储,请画出对应的森林。 27.已知有向图的邻接表如图所示,请回答下面问题: (1)给出该图的邻接矩阵; (2)从结点A出发,写出该图的深度优先遍历序列。 28.已知待排记录的关键字序列为{25,96,11,63,57,78,44},请回答下列问题: (1)画出堆排序的初始堆(大根堆); (2)画出第二次重建堆之后的堆。 29.已知关键字序列为(56,23,41,79,38,62,18),用散列函数H(key)=key%11将其散列到散列表HT[0..10]中,采用线性探测法处理冲突。 请回答下列问题: (1)画出散列存储后的散列表: (2)求在等概率情况下查找成功的平均查找长度。 四、算法阅读题(本大题共4小题,每小题5分,共20分) 30.阅读下列程序。 voidf30(intA[],intn) { inti,j,m; for(i=1;i for(j=0;j { m=A[i*n+j]; A[i*n+j]=A[j*n+i]; A[j*n+i]=m; } } 回答下列问题: (1)已知矩阵B= ,将其按行优先存于一维数组A中,给出执行函数调 用f30(A,3)后矩阵B的值; (2)简述函数f30的功能。 31.假设以二叉链表表示二叉树,其类型定义如下: typedefstructnode{ chardata; structnode*Ichild,*rchild;∥左右孩子指针 }*BinTree; 阅读下列程序。 voidf31(BinTreeT) { InitStack(S);∥初始化一个堆栈S while(T||! StackEmpty(S) { while(T) { Push(S,T);T=T->lchild; } if(! StackEmpty(S)) { T=Pop(S);printf(“%c”,T->data);T=T->rchild; } } } 回答下列问题: (1)已知以T为根指针的二叉树如图所示, 请写出执行f31(T)的输出结果: (2)简述算法f31的功能。 32.阅读下列程序。 voidf32(intA[],intn) { inti,j,m=l,t; for(i=0;i { for(j=0;j printf(“%d”,A[j]); printf(“\n”); m=0: for(j=1;j if(A[j-1]>A[j]) { t=A[j-l]; A[j-1]=A[j]; A[j]=t; m=1; } } } 回答问题: 已知整型数组A[]={34,26,15,89,42},写出执行函数调用f32(A,5)后的输出结果。 33.已知顺序表的表结构定义如下: #defineMAXLEN100 typedefintKeyType; typedefstruct{ KeyTypekey; InfoTypeotherinfo; }NodeType; typedefNodeTypeSqList[MAXLEN]; 阅读下列程序。 Intf33(SqListR,NodeTypeX,intp,intq) {intm; if(p>q)return-1; m=(p+q)/2; if(R[m].key==X.key)returnm; if(R[m].key>X.key)returnf33(R,X,p,m-l); elsereturnf33(R,X,m+l,q); } 请回答下列问题: (1)若有序的顺序表R的关键字序列为(2,5,13,26,55,80,105),分别写出X.key=18和X.key=26时,执行函数调用f33(R,X,0,6)的函数返回值。 (2)简述算法f33的功能。 五、算法设计题(本题10分) 34.假设用带头结点的单循环链表表示线性表,单链表的类型定义如下: typedefstructnode{ intdata; structnode*next; }LinkNode,*LinkList; 编写程序,求头指针为head的单循环链表中data域值为正整数的结点个数占结点总数的比例,若为空表输出0,并给出所写算法的时间复杂度。 函数原型为: floatf34(LinkListhead): 全国2011年10月高等教育自学考试 数据结构试题 课程代码: 02331 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。 错选、多选或未选均无分。 1、在数据的逻辑结构中,树结构和图结构都是() A.非线性结构B.线性结构 C.动态结构D.静态结构 2.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为() A.O (1)B.O(logn) C.O(n)D.O(n2) 3.指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点,要将两个链表链接成一个新的单循环链表,应执行的操作为() A.p1->next=p2->next;p2->next=p1->next; B.p2->next=p1->next;p1->next=p2->next; C.p=p2->next;p1->next=p;p2->next=p1->next; D.p=p1->next;p1->next=p2->next;p2->next=p; 4.设栈的初始状态为空,入栈序列为1,2,3,4,5,6,若出栈序列为2,4,3,6,5,1,则操作过程中栈中元素个数最多时为() A.2个B.3个 C.4个D.6个 5.队列的特点是() A.允许在表的任何位置进行插入和删除 B.只允许在表的一端进行插入和删除 C.允许在表的两端进行插入和删除 D.只允许在表的一端进行插入,在另一端进行删除 6.一个链串的结点类型定义为 ﹟defineNodeSize6 typedefstructnode{ chardata[NodeSize]; structnode*next; }LinkStrNode; 如果每个字符占1个字节,指针占2个字节,该链串的存储密度为() A.1/3B.1/2 C.2/3D.3/4 7.广义表A=(a,B,(a,B,(a,B,……)))的长度为() A.1B.2 C.3D.无限值 8.已知10×12的二维数组A,按“行优先顺序”存储,每个元素占1个存储单元,已知A[1][1]的存储地址为420,则A[5][5]的存储地址为() A.470B.471 C.472D.473 9.在一棵二叉树中,度为2的结点数为15,度为1的结点数为3,则叶子结点数为() A.12B.16 C.18D.20 10.在带权图的最短路径问题中,路径长度是指() A.路径上的顶点数B.路径上的边数 C.路径上的顶点数与边数之和D.路径上各边的权值之和 11.具有n个顶点、e条边的无向图的邻接矩阵中,零元素的个数为() A.eB.2e C.n2-2eD.n2-1 12.要以O(nlogn)时间复杂度进行稳定的排序,可用的排序方法是() A.归并排序B.快速排序 C.堆排序D.冒泡排序 13.若希望在1000个无序元素中尽快求得前10个最大元素,应借用() A.堆排序B.快速排序 C.冒泡排序D.归并排序 14.对有序表进行二分查找成功时,元素比较的次数() A.仅与表中元素的值
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 答案 02331 jpg 概论