自考数据结构历年试题和答案.doc

自考数据结构历年试题和答案.doc

《自考数据结构历年试题和答案.doc》由会员分享，可在线阅读，更多相关《自考数据结构历年试题和答案.doc（100页珍藏版）》请在冰点文库上搜索。

全国2012年10月高等教育自学考试

数据结构试题

课程代码：

02331

请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分

注意事项：

1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。

如需改动，用橡皮擦干净后，再选涂其他答案标号。

不能答在试题卷上。

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

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题

纸”的相应代码涂黑。

错涂、多涂或未涂均无分。

1．一个算法的时间耗费的数量级称为该算法的

A．效率 B．难度

C．可实现性 D．时间复杂度

2．顺序表便于

A．插入结点 B．删除结点

C．按值查找结点 D．按序号查找结点

3．设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是

A．p->next->next==head B．p->next==head

C．p->next->next==NULL D．p->next==NULL

4．设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为

A．（rear-front+m）％m B．rear-front+1

C．（front-rear+m）％m D．（rear-front）％m

5．下列关于顺序栈的叙述中，正确的是

A．入栈操作需要判断栈满，出栈操作需要判断栈空

B．入栈操作不需要判断栈满，出栈操作需要判断栈空

C．入栈操作需要判断栈满，出栈操作不需要判断栈空

D．入栈操作不需要判断栈满，出栈操作不需要判断栈空

6．A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a0,0的存储地址为1，每个元素占一个存储单元，则a7,5的地址为

A．25 B．26

C．33 D．34

7．树的后序遍历等价于该树对应二叉树的

A．层次遍历 B．前序遍历

C．中序遍历 D．后序遍历

8．使用二叉线索树的目的是便于

A．二叉树中结点的插入与删除 B．在二叉树中查找双亲

C．确定二叉树的高度 D．查找一个结点的前趋和后继

9．设无向图的顶点个数为n，则该图边的数目最多为

A．n-l B．n（n-1）／2

C．n（n+1）／2 D．n2

10．可进行拓扑排序的图只能是

A．有向图 B．无向图

C．有向无环图 D．无向连通图

11．下列排序方法中稳定的是

A．直接插入排序 B．直接选择排序

C．堆排序 D．快速排序

12．下列序列不为堆的是

A．75,45,65,30,15,25 B．75,65,45,30,25,15

C．75,65,30,l5,25,45 D．75,45,65,25,30,15

13．对线性表进行二分查找时，要求线性表必须是

A．顺序存储 B．链式存储

C．顺序存储且按关键字有序 D．链式存储且按关键字有序

14．分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同

的序列是

A．（4,1,2,3,5） B．（4,2,3,l,5）

C．（4,5,2,1,3） D．（4,2,1,5,3）

15．下列关于m阶B树的叙述中，错误的是

A．每个结点至多有m个关键字

B．每个结点至多有m棵子树

C．插入关键字时，通过结点分裂使树高增加

D．删除关键字时通过结点合并使树高降低

非选择题部分

注意事项：

用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

二、填空题（本大题共10小题，每小题2分，共20分）

16．数据元素之间的逻辑关系称为数据的______结构。

17．在线性表中，表的长度定义为______。

18．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1、2、3、4，为了得到

1、3、4、2的出栈顺序，相应的S和X的操作序列为______。

19．在二叉树中，带权路径长度最短的树称为______。

20．已知广义表G，head（G）与tail（G）的深度分别为4和6，则G的深度是______。

21．一组字符（a,b,c,d）在文中出现的次数分别为（7，6，3，5），字符＇d＇的哈夫曼编码的长度为______。

22．在一个具有n个顶点的无向图中，要连通全部顶点至少需要______条边。

23．直接选择排序算法的时间复杂度是______。

24．对于长度为81的表，若采用分块查找，每块的最佳长度为______。

25．用二叉链表保存有n个结点的二叉树，则结点中有______个空指针域。

三、解答题（本大题共4小题，每小题5分，共20分）

26．假设Q是一个具有11个元素存储空间的循环队列（队尾指针指向队尾元素的下一

个位置，队头指针指向队头元素），初始状态Q.front=Q.rear=0；写出依次执行

下列操作后头、尾指针的当前值。

a,b,c,d,e,f入队，a,b,c,d出队；

（1）Q.front=______；Q.rear=______。

g,h,i,j,k,l入队，e,f,g,h出队；

（2）Q.front=______；Q.rear=______。

M,n,o,P入队，i,j,k,l,m出队；（3）Q.front=______；Q.rear=______。

27．已知一个无向图如题27图所示，以①为起点，用普里姆（Prim）算法求其最小生成树，画出最小生成树的构造过程。

28．用归并排序法对序列（98,36,-9,0,47,23,1,8）进行排序，问：

（1）一共需要几趟归并可完成排序。

（2）写出第一趟归并后数据的排列次序。

29．一组记录关键字（55,76,44,32,64,82,20,16,43），用散列函数H（key）=key％11将记录

散列到散列表HT[0..12]中去，用线性探测法解决冲突。

（1）画出存入所有记录后的散列表。

（2）求在等概率情况下，查找成功的平均查找长度。

四、算法阅读题（本大题共4小题，每小题5分，共20分）

30．顺序表类型定义如下：

#defineListSize100

typedefstruct{

intdata[ListSize]；

intlength；

}SeqList；

阅读下列算法，并回答问题：

voidf30（SeqList*L）

{inti,j；

i=0；

while（ilength）

if（L->data[i]％2!

=0）

{for（j=i+1;jlength;j++}

L->data[j-1]=L->data[j];

L->length--;

}

elsei++

}

（1）若L->data中的数据为（22,4,63,0,15,29,34,42,3）,则执行上述算法后L->data中的数据以及L->length的值各是什么？

（2）该算法的功能是什么？

31.有向图的邻接矩阵类型定义如下：

#defineMVN100∥最大顶点数

typedefintEType;∥边上权值类型

typedefstruct{

ETypeedges[MVN][MVN];∥邻接矩阵，即边表

intn;∥图的顶点数

｝MGraph;∥图类型

例如，一个有向图的邻接矩阵如下所示：

阅读下列算法，并回答问题：

Voidf31（MGraphG）

{

Inti,j,k=0;

Step1:

for（i=0;i

for（j=0;j

if（G.edges[i][j]==1）k++;

printf（“%dn”,k）;

step2:

for（j=0;j

{k=0;

for（i=0;i

if（G.edges[i][j]==1）k++;

printf（“%dn”,k）;

}

}

（1）stepl到step2之间的二重循环语句的功能是什么?

（2）step2之后的二重循环语句的功能是什么?

32．阅读下列算法，并回答问题：

voidf32（intr[]，intn）

{

Inti，j；

for（i=2；i

{r[0]=r[i]；

j=i-l；

while（r[0]

{r[j+l]=r[j]；

j=j-1；

}

r[j+l]=r[0]；

}

}

（1）这是哪一种插入排序算法?

该算法是否稳定?

（2）设置r[0]的作用是什么?

33．顺序表类型定义如下：

typedefintSeqList[100]；

阅读下列算法，并回答问题：

voidf33（SeqListr，intn）

{inta,b，i；

if（r[0]

{a=r[0]；b=r[1]；>

else{a=r[1]；b=r[0]；}

for（i=2；i

if（r[i]

elseif（r[i]>b）b=r[i]；

printf（＂a=％d，b=％d。

n＂，a，b）；

}

（1）给出该算法的功能；

（2）给出该算法的时间复杂度。

五、算法设计题（本题10分）

34．二叉树的存储结构类型定义如下

typedefstructnode{

intdata；

structnode*lchild，*rchild；

}BinNode；

typedefBinNode*BinTree；

编写递归算法，求只有一个孩子结点的结点总数，并计算这些结点的数据值的和。

函数的原型为：

voidf34（BinTreeT,int*count,int*sum）

*count和*sum的初值为0。

2012年1月高等教育自学考试全国统一命题考试

数据结构试题

课程代码：

02331

考生答题注意事项：

1.本卷所有试卷必须在答题卡上作答。

答在试卷和草稿纸上的无效。

2.第一部分为选择题。

必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。

3.第二部分为非选择题。

必须注明大、小题号，使用0.5毫米黑色字迹笔作答。

4.合理安排答题空间，超出答题区域无效。

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

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

错选、多选或未选均无分。

1.每个结点有且仅有一个直接前趋和多个（或无）直接后继（第一个结点除外）的数据结构称为

A.树状结构 B.网状结构

C.线性结构 D.层次结构

2.某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素，则最节省运算时间的存储结构是

A.单链表 B.双链表

C.仅有头指针的单循环链表 D.仅有尾指针的单循环链表

3.已知一个栈的入栈序列是1，2，3，…，n，其输出序列为pl，p2，p3….，pn，若p1是n，则pi是

A.i B.n-i

C.n-i+l D.不确定

4.下面关于串的叙述中，正确的是

A.串是一种特殊的线性表 B.串中元素只能是字母

C.空串就是空白串 D.串的长度必须大于零

5.无向完全图G有n个结点，则它的边的总数为

A.n2 B.n（n-1）

C.n（n-1）/2 D.（n-1）

6.若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点数是

A.9 B.11

C.15 D.不确定

7.如图所示，在下面的4个序列中，不符合深度优先遍历的序列是

A.acfdeb

B.aebdfc

C.aedfbc

D.aefdbc

8.无论待排序列是否有序，排序算法时间复杂度都是O（n2）的排序方法是

A.快速排序 B.归并排序

C.冒泡排序 D.直接选择排序

9.已知二叉排序树G，要输出其结点的有序序列，则采用的遍历方法是

A.按层遍历 B.前序遍历

C.中序遍历 D.后序遍历

10.用ISAM和VSAM组织的文件都属于

A.散列文件 B.索引顺序文件

C.索引非顺序文件 D.多关键字文件

11.对序列（15，9，7，8，20，-1，4）进行排序，第一趟排序后的序列变为（4，9，-1，8，20，7，15），则采用的排序方法是

A.选择 B.快速

C.希尔 D.冒泡

12.当采用分块查找时，数据的组织方式为

A.数据分成若干块，每块内数据有序

B.数据分成若干块，每块中数据个数必须相同

C.数据分成若干块，每块内数据有序，块间是否有序均可

D.数据分成若干块，每块内数据不必有序，但块间必须有序

13.下述编码中不是前缀码的是

A.（00，01，10，11） B.（0，1，00，11）

C.（0，10，110，111） D.（1，01，000，001）

14.若一个栈以向量V[1..n]存储，初始栈顶指针top为n+l，则x进栈的正确操作是

A.top=top-1；V[top]=x B.V[top]=x；top=top+1

C.top=top+1；V[top]=x D.V[top]=x；top=top-1

15.在一个以head为头结点指针的非空单循环链表中，指针p指向链尾结点的条件是

A.p->data=-1 B.p->next=NULL

C.p->next->next=head D.p->next=head

二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）请在每个空格中填上正确答案。

错填、不填均无分。

16.在数据的逻辑结构和存储结构中，与计算机无关的是______。

17.线性表L=（a1,a2,…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。

18.设循环队列的容量为50（序号从0到49），现经过一系列的入队和出队运算后，有①front=11，rear=29；②front=29，rear=11；在这两种情况下，循环队列中的元素个数分别是______和______。

19.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______。

20.已知三对角矩阵A[10][10]的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[6][7]的地址为______。

21.若以（4，5，6，7，8）作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。

22.有向图G如图所示，它的两个拓扑排序序列分别为______和______。

23.一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为______。

24.已知广义表A=（x，（（a，b），c，）），函数head（head（tail（A）））的运算结果是______。

25.索引顺序文件既可以顺序存取，也可以______。

三、解答题（本大题共4小题，每小题5分，共20分）

26.对关键字序列（26，18，60，14，7，45，13，32）进行降序的堆排序，写出构建的初始堆（小根堆）及前两趟重建堆之后序列状态。

初始堆：

第一趟：

第二趟：

27.设散列函数为H（key）=key％11，散列地址空间为0··10，对关键字序列（27，13，55，32，18，49，24，38，43）用线性探查法解决冲突，构建散列表。

现已有前4个关键字构建的散列表如下所示，请将剩余5个关键字填入表中相应的位置。

28.已知一棵二叉树的前序遍历和中序遍历序列分别为：

ABCDEFG和CBDAEGF，请画出此二叉树，并给出后序遍历序列。

29.已知如图所示的带权无向图，请画出用普里姆算法从顶点1开始的最小生成树的构造过程。

四、算法阅读题（本大题共4小题，每小题5分，共20分）

30.阅读下列算法，并回答下列问题：

（1）简述该算法的功能；

（2）写出分别输入字符串：

"abcba"和"abcbde"，调用算法函数的返回值。

intsymmetry（void）

{inti=0,j,k；.

charstr[80]；

SeqStacks；

InitStack（&s）；

gets（str）；

while（str[i]!

='＼0'）i++；

for（j=0;j

push（&s,str[j]）；

if（i％2!

=0）k=i/2+1；

elsek=i／2；

for（j=k;j

if（str[j]!

=pop（&s））

return0；

return1；

}

（1）

（2）

31.下列算法是利用二分查找方法在递减有序表R中插入元素x，并保持表R的有序性。

请在空缺处填入适当的内容，使其成为一个完整的算法。

typedefstruct{

KeyTypekey；

InfoTyepotherinfo；

}RecType；

typedefRecTypeSeqList[Maxlen]

voidBinInsert（SeqListR,int*n，RecTypex）

{intlow=1，high=*n；

intmid，i;

while（low<=high）

{mid=（low+high）/2；

if（x.key>R[mid].key）

（1）；

else

（2）；

}

for（i=*n；i>=low；i--）

R[i+1]=R[i]；

（3）；

++（*n）；

}

（1）

（2）

（3）

32.阅读下列算法，并回答下列问题：

（1）简述该算法中标号s1所指示的循环语句的功能；

（2）简述该算法中标号s2所指示的循环语句的功能。

LinkListInsertmnode（LinkListhead，charx，intm）

{

LinkNode*p，*q，*s;

inti;charch；

p=head->next；

s1：

while（p&&p->data!

=x）

p=p->next；

if（p==NULL）printf（"error\n"）；

else{

q=p->next；

s2：

for（i=1；i<=m；i++）

{

s=（LinkNode*）malloc（sizeof（LinkNode））；

scanf（"％c"，&ch）；

s->data=ch；

p->next=s；

p=s；

}

p->next=q；

}

returnhead；

}

（1）

（2）

33.阅读下列算法，并回答下列问题：

（1）该算法采用的是何种排序方法?

（2）算法中的R[n+1]的作用是什么?

typedefstruct{

KeyTypekey；

InfoTypeotherinfo；

}RecType；

typedefRecTypeSeqList[MaxLen]；

voidsort（SeqListR，intn）

{//n

intk，i；

for（k=n-1;k>=1;k--）

if（R[k].key>R[k+l].key）

{

R[n+1]=R[k]；

for（i=k+1；R[i].key

R[i-1]=R[i];

R[i-l]=R[n+1]；

}

}

（1）

（2）

五、算法设计题（本题10分）

34.假设以单链表表示线性表，单链表的类型定义如下：

typedefstructnode{

DataTypedata；

Structnode*next；

}LinkNode，*LinkList；

编写算法，在一个头指针为head且带头结点的单链表中，删除所有结点数据域值为x的结点。

函数原型为：

LinkListdelnode（LinkListhead，DataTypex）

全国2011年10月高等教育自学考试

数据结构试题

课程代码：

02331

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

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

错选、多选或未选均无分。

1、在数据的逻辑结构中，树结构和图结构都是（）

A.非线性结构 B.线性结构

C.动态结构 D.静态结构

2.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为（）

A.O

（1） B.Ｏ（logn）

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.队列的特点是（