全国高等教育自学考试数据结构试题及答案.docx
《全国高等教育自学考试数据结构试题及答案.docx》由会员分享，可在线阅读，更多相关《全国高等教育自学考试数据结构试题及答案.docx（12页珍藏版）》请在冰点文库上搜索。
全国高等教育自学考试数据结构试题及答案
全国2010年1月高等教育自学考试
数据结构试题
（课程代码：
02331）
一、单项选择题（本大题共15小题，每小题2分，共30分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1.
若一个算法的时间复杂度用T（n）表示，其中n的含义是（
B.语句条数
A.问题规模
C.循环层数
D.函数数量
2.
具有线性结构的数据结构是（
A.树
C.栈和队列
将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（
D.6个
若栈采用链式存储结构，则下列说法中正确的是
.需要判断栈满且需要判断栈空
.不需要判断栈满但需要判断栈空
.需要判断栈满但不需要判断栈空
.不需要判断栈满也不需要判断栈空
7.若串str=”Software"，其子串的数目是（
B.
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.下面是在顺序栈上实现的一个栈基本操作，该操作的功能是。
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）树，该树的带权路径长度为。
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）遍历左子树。
已知一棵二叉树如图所示，请给出其
四、算法阅读题（本大题共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=qwhile（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!
='\O'））{
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;jif（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）J{
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年1月高等教育自学考试
数据结构试题答案
（课程代码：
02331）
、单项选择题（本大题共15小题，每小题2分，共30分）
（2）如下图（3分）
【评分参考】以上答案不惟一，只要图形等价正确即可给分。
28.初始堆序列是（12,15,14,18,16,36,18,60,25,85）
【评分参考】错一个数扣1分，扣完5分为止。
【评分参考】以上
（2）中答案不惟一，给出的两个图都是对的，只要给出其中之一即可。
四、算法阅读题（本大题共4小题，每小题5分，共20分）
30.⑴'-►L.1―卜'：
「忙—.（3分）
【评分参考】错一个结点扣1分，扣完3分为止。
（2）将单链表的首结点（第一个结点）移到链尾（作为最后一个结点）。
或将链头元素移到链尾。
（2分）
31.
（1）1,0（2分）
（2）判断两个字符串是否相等。
若串相等，则返回O,否则返回1。
（3分）
32.
（1）A[]={2,4,6,7,8,10）（3分）
（2）该算法实现了对数组A进行冒泡排序。
（2分）
33.
（1）low<=high（2分）
（2）R[mid].key==K（2分）
（3）low=mid+l（1分）
五、算法设计题（本题10分）
34•参考答案
intSumNodes（BiTreeT）
{inti,j;
if（!
T）retumO;（空树处理，2分）
i=SumNodes（T->lchild）;（左右子树递归，6分）
j=SumNodes（T->rchild）;
retum（i+j+1）;（返回结果计算，2分）
}//endofSumNodes（...）
【评分参考】①若采用非递归算法实现程序，则不给分。
②若用其他的递归算法实现该功能，参照此评分标准给分
升级会员 