自考真题答案

3773考试网自学考试自考真题答案正文

[组图]全国2010年1月自考数据结构试题

来源:fjzsksw.com 2010-3-10 13:22:15

二、填空题(本大题共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的最短路径长度是_________。
全国2010年1月高等教育自学考试数据结构试题
23.对序列{55,46,13,05,94,17,42}进行基数排序,第一趟排序后的结果是_________。
24.高度为3的3阶B-树最少的关键字总数是_________。
25.VSAM通常作为大型索引顺序文件的标准组织,其动态索引结构采用的是_________。

三、解答题(本大题共4小题,每小题5分,共20分)
全国2010年1月高等教育自学考试数据结构试题26.假设二叉树的RNL遍历算法定义如下:
若二叉树非空,则依次执行如下操作:
(1)遍历右子树;
(2)访问根节点;
(3)遍历左子树。
已知一棵二叉树如图所示,请给出其RNL遍历的结果序列。
27.已知一个无向图G=(V,E),其中V={A,B,C,D,E,F},邻接矩阵表示如下所示。
全国2010年1月高等教育自学考试数据结构试题
请回答下列问题:
(1)请画出对应的图G。
(2)画出图G的邻接表存储结构。
28.已知一组待排记录的关键字序列为(16,12,18,60,15,36,14,18,25,85),用堆排序方法建小根堆,请给出初始建堆后的序列。
29.已知一棵二叉排序树如图所示。
请回答下列问题:
(1)画出插入元素23后的树结构;
(2)请画出在原图中删除元素57后的树结构。
全国2010年1月高等教育自学考试数据结构试题

四、算法阅读题(本大题共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指向的链表如下图所示,请画出执行本函数之后的链表的结果。
全国2010年1月高等教育自学考试数据结构试题
(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;j<i;j++)
if(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=(1ow+high)/2;
if( (2) )
return mid;
if(R[mid].key>K)
high=mid-1;
else
(3)
}
return O;
} //BinSearch
请在空白处填写适当内容,使该程序功能完整。
(1)
(2)
(3)

五、算法设计题(本题10分)
34.已知二叉树采用二叉链表存储,其结点结构定义如下:
typedef struct Node{
ElmType data;
struct Node *lchild,*rchild;
}*BiTree;
请编写递归函数SumNodes(BiTree T),返回二叉树T的结点总数。

上一页  [1] [2] 

触屏版 电脑版
3773考试网 琼ICP备12003406号-1