至数据结构答案02331jpg概论文档格式.docx
- 文档编号:4956972
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:78
- 大小:1.67MB
至数据结构答案02331jpg概论文档格式.docx
《至数据结构答案02331jpg概论文档格式.docx》由会员分享,可在线阅读,更多相关《至数据结构答案02331jpg概论文档格式.docx(78页珍藏版)》请在冰点文库上搜索。
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->
p=q
while(p->
next)
p=p->
p->
next=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<
i;
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;
k;
R[i-j]=R[i-j-1];
R[i-j]=x;
全国2011年1月高等教育自学考试
数据结构试题
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。
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={<
V1,V2>
,<
V1,V3>
V2,V3>
V2,V4>
V3,V4>
},图G的拓扑序列是()
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.方便文件的修改
请在每小题的空格中填上正确答案。
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.不定长文件指的是文件的____________大小不固定。
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)求在等概率情况下查找成功的平均查找长度。
30.阅读下列程序。
voidf30(intA[],intn)
inti,j,m;
for(i=1;
n;
for(j=0;
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);
rchild;
(1)已知以T为根指针的二叉树如图所示,
请写出执行f31(T)的输出结果:
(2)简述算法f31的功能。
32.阅读下列程序。
voidf32(intA[],intn)
inti,j,m=l,t;
for(i=0;
i<
n-l&
m;
i++)
j<
j++)
printf(“%d”,A[j]);
printf(“\n”);
m=0:
for(j=1;
n-i;
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的功能。
34.假设用带头结点的单循环链表表示线性表,单链表的类型定义如下:
intdata;
structnode*next;
}LinkNode,*LinkList;
编写程序,求头指针为head的单循环链表中data域值为正整数的结点个数占结点总数的比例,若为空表输出0,并给出所写算法的时间复杂度。
函数原型为:
floatf34(LinkListhead):
全国2011年10月高等教育自学考试
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;
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 概论