全国2010年1月高等教育自学考试数据结构试题
课程代码:02331

一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.错选、多选或未选均无分.
1.若一个算法的时间复杂度用T(n)表示,其中n的含义是（ ）
A.问题规模
B.语句条数
C.循环层数
D.函数数量

2.具有线性结构的数据结构是（ ）
A.树
B.图
C.栈和队列
D.广义表

3.将长度为n的单链表连接在长度为m的单链表之后,其算法的时间复杂度为（ ）
A.O(1)
B.O(m)
C.O(n)
D.O(m+n)

4.在带头结点的双向循环链表中插入一个新结点,需要修改的指针域数量是（ ）
A.2个
B.3个 .
C.4个
D.6个
5.假设以数组A[60]存放循环队列的元素,其头指针是front=47,当前队列有50个元素,则队列的尾指针值为（ ）
A.3
B.37
C.50
D.97

6.若栈采用链式存储结构,则下列说法中正确的是（ ）
A.需要判断栈满且需要判断栈空
B.不需要判断栈满但需要判断栈空
C.需要判断栈满但不需要判断栈空
D.不需要判断栈满也不需要判断栈空

7.若串str="Software",其子串的数目是（ ）
A.8
B.9
C.36
D.37

8.设有一个10阶的下三角矩阵A,采用行优先压缩存储方式,a_ll为第一个元素,其存储地址为1000,每个元素占一个地址单元,则a₈₅的地址为 （ ）
A.1012
B.1017
C.1032
D.1039

9.允许结点共享的广义表称为（ ）
A.纯表
B.线性表
C.递归表
D.再入表

10.下列数据结构中,不属于二叉树的是（ ）
A.B树
B.AVL树
C.二叉排序树
D.哈夫曼树

11.对下面有向图给出了四种可能的拓扑序列,其中错误的是（ ）

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

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.下面是在顺序栈上实现的一个栈基本操作,该操作的功能是_________.
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的最短路径长度是_________.

23.对序列{55,46,13,05,94,17,42}进行基数排序,第一趟排序后的结果是_________.
24.高度为3的3阶B-树最少的关键字总数是_________.
25.VSAM通常作为大型索引顺序文件的标准组织,其动态索引结构采用的是_________.  

三、解答题(本大题共4小题,每小题5分,共20分)

26.假设二叉树的RNL遍历算法定义如下:
若二叉树非空,则依次执行如下操作:
(1)遍历右子树；
(2)访问根节点；
(3)遍历左子树.
已知一棵二叉树如图所示,请给出其RNL遍历的结果序列.
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指向带头结点的单链表.
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指向的链表如下图所示,请画出执行本函数之后的链表的结果.

(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；jif(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=

[1]