自考数据结构02331历年试题及答案（2009--2015个人整理版） - 图文

全国2011年10月自学考试数据结构试题

一、单项选择题（本大题共15小题，每小题2分，共30分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1、在数据的逻辑结构中，树结构和图结构都是（ ） A.非线性结构 B.线性结构 C.动态结构 D.静态结构

2.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为（ ） A.O（1） B.Ｏ（log n） 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;p2－＞next=p1－＞next; 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.一个链串的结点类型定义为 ﹟define NodeSize 6 typedef struct node{

char data[NodeSize]; struct node*next; }LinkStrNode;

如果每个字符占1个字节，指针占2个字节，该链串的存储密度为（ ） A.1/3 B.1/2 C.2/3 D.3/4 7.广义表A=（a,B,(a,B,(a,B,……）））的长度为（ ） A.1 B.2 C.3 D.无限值

8.已知10×12的二维数组A，按“行优先顺序”存储，每个元素占1个存储单元，已知A[1][1]的存储地址为420，则A[5][5]的存储地址为（ ） A.470 B.471 C.472 D.473

9.在一棵二叉树中，度为2的结点数为15，度为1的结点数为3，则叶子结点数为（ ） A.12 B.16 C.18 D.20 10.在带权图的最短路径问题中，路径长度是指（ ） A.路径上的顶点数 B.路径上的边数 C.路径上的顶点数与边数之和 D.路径上各边的权值之和 11.具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为（ ） A.e B.2e C.n2-2e D.n2-1

12.要以O（n log n）时间复杂度进行稳定的排序，可用的排序方法是（ ） A.归并排序 B.快速排序 C.堆排序 D.冒泡排序

13.若希望在1000个无序元素中尽快求得前10个最大元素，应借用（ ） A.堆排序 B.快速排序 C.冒泡排序 D.归并排序 14.对有序表进行二分查找成功时，元素比较的次数（ ） A.仅与表中元素的值有关 B.仅与表的长度和被查元素的位置有关 C.仅与被查元素的值有关 D.仅与表中元素按升序或降序排列有关 15.散列文件是一种（ ）

A.顺序存取的文件 B.随机存取的文件 C.索引存取的文件 D.索引顺序存取的文件 二、填空题（本大题共10小题，每小题2分，共20分）

16.若一个算法中的语句频度之和为T（n）=3n3-200nlog2n+50n，则该算法的渐近时间复杂度为___O(n^3)_______. 17.在单链表中，除了第1个元素结点外，任一结点的存储位置均由___前驱节点的链指针__________指示。 18.栈的修改是按____后进先出______的原则进行。

19.字符串中任意个连续的字符组成的子序列称为该串的___子串_______。

20.假设一个10阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，若矩阵中的第一个元素a11在B中的存储位置k=0，则元素a55在B中的存储位置k=___34_______。k=10+9+8+7+1-1=34 21.在一棵具有n个结点的严格二叉树中，度为1的结点个数为__0________。 22.对于稀疏图，采用_____邻接表_____表示法较为节省存储空间。

23.在排序过程中，如果____需要在内外存之间交换数据_________，则称其为外部排序。 24.设有一组记录的关键字为｛19，14，23，1，68，12，10，78，25｝，用链地址法构造散列表，散列函数为h（key）=key％11,散列地址为1的链中有____4______个记录。

25.多关键字文件的特点是除主文件和主索引外，还建有____次关键字索引______。 三、解答题（本大题共4小题，每小题5分，共20分）

26.对于下列稀疏矩阵（注：矩阵元素的行列下标均从1开始）

?0?0???8??0??0007?100000?00??500?

?000?6?29??（1）画出三元组表；

（2）画出三元组表的行表。 (1) (2)

27.已知一个森林的前序遍历序列为CBADHEGF，后序遍历序列为ABCDEFGH。 （1）画出该森林；

（2）画出该森林所对应的二叉树。 (1) (2)

28.对关键字序列（429，653，275，897，170，908，473，256，726）进行基数排序，写出每一趟的排序结果。 29.对下列关键字序列

（87，25，310，08，27，132，68，96，187，133，70，63，47，135） 构造散列表，假设散列函数为h（key）=key％13,用拉链法解决冲突。 （1）画出该散列表；

（2）求等概率情况下查找成功的平均查找长度ASL;

（3）写出删除值为70的关键字时所需进行的关键字比较次数。 (1) (2) (3)

四、算法阅读题（本大题共4小题，每小题5分，共20分） 30.阅读下列算法，并回答问题：

（1）假设L=（3，7，7，11，20，20，20，51，51），写出执行函数f30（&L）后的L； （2）简述f30的功能。 void f30(SeqList*L)

{ ∥L为非空的有序表 int i=1,k=0;

while(i＜L－＞length） ｛

if(L－＞data[i]!=L－＞data[k]) L－＞data[++k]=L－＞data[i]; i++; }

L－＞length=k+1； } (1) (2)

31.阅读下列算法，并回答问题： （1）假设栈S=（3，8，6，2，5），其中5为栈顶元素，写出执行函数f31（&S）后的S； （2）简述函数f31的功能。

void f31(Stack *S){

Queue Q；InitQueue(&Q); while(!StackEmpty(S)) EnQueue(&Q,Pop(&S)); while(!QueueEmpty(Q)) Push(&S,DeQueue(&Q));

}

（1） （2）

32.假设具有n个结点的完全二叉树顺序存储在向量BT[1.. n]中，阅读下列算法，并回答问题： （1）若向量BT为： A B C D E F G 1 2 3 4 5 6 7 画出执行函数f32（BT,7,1）的返回结果; (2)简述函数f32的功能。

BinTree f32(DataType BT[],int n,int i) {

BinTree p;

if (i＞n) return NULL;

p=（BinTNode*）malloc(sizeof(BinTNode)); p－＞data=BT[i];

p－＞lchild=f32(BT,n,i*2); p－＞rchild=f32(BT,n,i*2+1); return p; } (1) (2)

33.已知有向图的邻接表和邻接矩阵定义如下： ﹟define MaxNum 50 typedef struct node { int adjvex;

struct node *next; } EdgeNode; typedef struct{ char vertex；

∥图的最大顶点数

∥邻接点域 ∥链指针域 ∥边表结点结构

∥顶点域