全国2010年1月自考数据结构试题及答案.doc

更多优质自考资料尽在百度贴吧自考乐园俱乐部
（
全国2010年1月自考数据结构试题及答案
课程代码：02331

一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．若一个算法的时间复杂度用T(n)表示，其中n的含义是（ A ）
A．问题规模 B．语句条数
C．循环层数 D．函数数量
2．具有线性结构的数据结构是（ C ）
A．树 B．图
C．栈和队列 D．广义表
线性结构有：顺序表、栈和队列、串
3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（ C ）
A．O(1) B．O(m)
C．O(n) D．O(m+n)
4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ D ）
A．2个 B．3个
C．4个 D．6个
5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ D ）
A．3 B．37
C．50 D．97
6．若栈采用链式存储结构，则下列说法中正确的是（ B ）
A．需要判断栈满且需要判断栈空
B．不需要判断栈满但需要判断栈空
C．需要判断栈满但不需要判断栈空
D．不需要判断栈满也不需要判断栈空
7．若串str=”Software”，其子串的数目是（ D ）
A．8 B．9
C．36 D．37
8．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为 （ C ）
A．1012 B．1017
C．1032 D．1039
P61中
在n阶方阵A这个下三角矩阵中，第i（i从0开始）行（0≤i n(n+1)/2-1]中。
若i≥j，则aij在左下三角矩阵中，sa[k]与aij的对应关系是k=i(i+1)/2+j。
若iD ）P67
A．纯表 B．线性表
C．递归表 D．再入表
10．下列数据结构中，不属于二叉树的是（ B ）B树是一种平衡的多叉树
A．B树 B．AVL树 AVL树是自平衡二叉查找树
C．二叉排序树 D．哈夫曼树 哈夫曼树是最优二叉树
11．对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ）辅导书中P97第10题

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为起始结点对下图进行深度优先遍历，正确的遍历序列是（ D ）

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 ）P164
A．快速排序 B．归并排序
C．冒泡排序 D．直接插入排序
稳定：直接插入、冒泡、归并、基数
不稳定：直接选择、希尔、快速、堆
14．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，查找成功需要的比较次数是（ B ） mid1=45，mid2=9，mid3=32
A．2 B．3
C．4 D．8
15．采用ISAM组织文件的方式属于（ D ）P211-212
A．链组织 B．顺序组织
C．散列组织 D．索引组织

二、填空题(本大题共10小题，每小题2分，共20分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16．数据元素及其关系在计算机存储器内的表示称为存储结构。P1
17．长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是O(n)。
18．下面是在顺序栈上实现的一个栈基本操作，该操作的功能是_取栈顶元素_。P34
typedef struct{
DataType data[100]；
int top；
}SeqStack；
DataType StackTop(SeqStack*S)
{ if(StackEmpty(S))
Error(”Stack is empty”)；
return S->data[S->top]；
}
19．在串匹配中，一般将主串称为目标串，将子串称为_模式串_。P55
20．已知广义表C=(a(b，c)，d)，则：tail(head(tail(C)))= __( )__。
P66中
若广义表LS非空（n≥1）（通常用圆括号将广义表括起来，用逗号分割其中的元素。用大写字母表示广义表，用小写字母表示原子。），则a1是LS的表头，其余元素组成的表称为LS的表尾。
长度：元素的个数
深度：表展开后所含括号的层数（从最里面往最外面数）
21．用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为___231__。
22．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是__35__。

23．对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是42,13,94,55,0546,17。

24．高度为3的3阶B-树最少的关键字总数是__7__。
一颗高度为h的k阶B-树中最多可容纳多少个关键字？
解 要使高为h的k阶B-树容纳最多的关键字，则每个结点中的关键自数据就必须达到最大值k-1.因此这时的
25．VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是__B+树__。P214
三、解答题(本大题共4小题，每小题5分，共20分)
26．假设二叉树的RNL遍历算法定义如下：
若二叉树非空，则依次执行如下操作：
(1)遍历右子树；
(2)访问根节点；
(3)遍历左子树。
已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。
GCFABD
P77页图6.11中的中序序列LNR、前序序列NLR、后序序列LRN
27．已知一个无向图G=(V，E)，其中V={A，B，C，D，E，F}，邻接矩阵表示如下所示。

请回答下列问题：
(1)请画出对应的图G。P103中的图7.7
0 1 2 3 4 5
A B C D E F
0 A 0 1 0 1 0 0
1 B 1 0 1 1 1 0
2 C 0 1 0 0 0 1
3 D 1 1 0 0 1 0
4 E 0 1 0 1 0 1
5 F 0 0 1 0 1 0

(2)画出图G的邻接表存储结构。P105中图7.8

28．已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，请给出初始建堆后的序列。
P154中，注：n=10，从第└n/2┘（1≤i≤ ）个结点起进行调整。若i=5，则与i=10或i=11进行互换；即i与2i或2i+1中的关键字进行互换。

29．已知一棵二叉排序树如图所示。

请回答下列问题：
(1)画出插入元素23后的树结构；

(2)请画出在原图中删除元素57后的树结构。

四、算法阅读题(本大题共4小题，每小题5分，共20分)
30．已知下列程序，Ls指向带头结点的单链表。
Typedef struct 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”)，则函数的返回值是什么?
答：
A的ASCII 065
A的ASCII 097
若调用语句是 f31(”abcde”，”abcde”)，则函数的返回值是什么?
答：由于字符串结束标识'\0'对应的ASCII码是0，则*strl-*str2=0
再按照条件表达式的形式为
逻辑表达式？表达式1：表达式2
若逻辑表达式的值为非零，则条件表达式的值等于表达式1的值；若逻辑表达式的值为零，则条件表达式的值等于表达式2的值。
则函数的返回值是0。
(2)简述该函数的功能。
答：如果两个字符串结点*strl和*strl中的字符相等，且字符串结点*strl中的字符不等于字符串结束标识'\0'，则两个字符串结点*strl和*strl中的字符指针自加运算。如果条件不满足，则字符串结点*strl和*strl中的字符相减。若逻辑表达式的值为非零，则条件表达式的值等于1；若逻辑表达式的值为零，则条件表达式的值等于0。
32．数组A[]中存储有n个整数，请阅读下列程序。
void f32(intA[]，int n)
{ int i，j，k，x；
k=n-l；
while(k>0){
i=k； k=0；
for(j=O；jA[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中存储的结果是什么?
答：数组A中存储的结果是10。
(2)说明该算法的功能。
答：数组A[]中存储有n个整数，当k=n-1时，则第k个向量是最后一个整数。
当k>0时，即数组A[]非空时，设i=k，k=0，如果j=0，且j整数和第j+1个整数。如果第j个整数大于第j+1个整数，则通过语句
x=A[j]；
A[j]=A[j+l]；
A[j+1]=x；
进行交换，同时令k=j。
如果j大于等于i（即j大于等于k）时，则结束执行if语句和while语句，并返回。
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)low<=high ){
mid=(1ow+high)／2；
if( (2)R[mid].key==K )
return mid；
if(R[mid].key>K)
high=mid-1；
else
(3)low=mid+1 ；
}
return O；
} ／／BinSearch
请在空白处填写适当内容，使该程序功能完整。
(1) low<=high
(2) R[mid].key==K
(3) low=mid+1
五、算法设计题(本题10分)
34．已知二叉树采用二叉链表存储，其结点结构定义如下：
typedef struct Node{
ElmType data；
struct Node *lchild，*rchild；
}*BiTree；
请编写递归函数SumNodes(BiTree T)，返回二叉树T的结点总数。
int SumNodes(BiTree T){
//T的初值指向某二叉链表的根结点
if(! T)
//T为空
return 0;
else
return SumNodes(T->lchild)+ SumNodes(T->rchild)+1;
}

自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部