四川小自考 四川小自考课程购买入口

全国2007年10月高等教育自学考试数据结构导论试

发布日期:2018-05-24 编辑整理:四川小自考 【字体: 【加入自考交流群】

全国2007年10月高等教育自学考试
数据结构导论试题
课程代码:02142

一、单项选择题(本大题共15小题,每小题2分,共30)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.错选、多选或未选均无分.
1.在数据结构中,从逻辑上可以把数据结构分成( )
A.线性结构和非线性结构
B.紧凑结构和非紧凑结构
C.动态结构和静态结构
D.内部结构和外部结构

2.for(i=0;i<m;i++)
for(j=0;j<n;j++)
A[i][j]=i*j;
上面算法的时间复杂度为( )
A.O(m2)
B.O(n2)
C.O(m×n)
D.O(m+n)

3.设顺序表有9个元素,则在第3个元素前插入一个元素所需移动元素的个数为( )
A.5
B.6
C.7
D.9

4.设p为指向双向循环链表中某个结点的指针,p所指向的结点的两个链域分别用p→llink和p→rlink表示,则同样表示p指针所指向结点的表达式是( )
A.p→llink
B.p→rlink
C.p→llink→llink
D.p→llink→rlink

5.一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的存储地址是( )
A. 110
B. 108
C. 100
D. 120

6.设有一个栈,按A、B、C、D的顺序进栈,则可能为出栈序列的是( )
A.DCBA
B.CDAB
C.DBAC
D.DCAB

7.在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top为栈顶指针,则当做出栈处理时,top变化为( )
A.top++
B.top--
C.top不变
D.top=0

8.除根结点外,树上每个结点( )
A.可有任意多个孩子、一个双亲
B.可有任意多个孩子、任意多个双亲
C.可有一个孩子、任意多个双亲
D.只有一个孩子、一个双亲

9.题9图中树的度为( )
全国2007年10月高等教育自学考试数据结构导论试(图1)
A.2
B.3
C.5
D.8

10.有4个顶点的无向完全图的边数为( )
A.6
B.12
C.16
D.20

11.设图的邻接矩阵为全国2007年10月高等教育自学考试数据结构导论试(图2),则该图为( )
A.有向图
B.无向图
C.强连通图
D.完全图

12.在对查找表的查找过程中,若被查找的数据元素不存在,则把该数据元素插入到集合中.这种方式主要适合于( )
A.静态查找表
B.动态查找表
C.静态查找表与动态查找表
D.静态查找表或动态查找表

13.用散列函数求元素在散列表中的存储位置时,可能会出现不同的关键字得到相同散列函数值的冲突现象.可用于解决上述问题的是( )
A.线性探测法
B.除留余数法
C.平方取中法
D.折叠法

14.排序算法中,第一趟排序后,任一元素都不能确定其最终位置的算法是( )
A.选择排序
B.插入排序
C.冒泡排序
D.快速排序

15.在排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端的方法,称为( )
A.希尔排序
B.归并排序
C.插入排序
D.选择排序

二、填空题(本大题共13小题,每小题2分,共26)
请在每小题的空格中填上正确答案.错填、不填均无分.
16.如果操作不改变原逻辑结构的"值",而只是从中提取某些信息作为运算结果,则称该类运算为__________型运算.
17.设有指针head指向不带表头结点的单链表,用next表示结点的一个链域,指针p指向与链表中结点同类型的一个新结点.现要将指针p指向的结点插入表中,使之成为第一个结点,则所需的操作为"p→next=head;"和"__________".
18.单链表中逻辑上相邻的两个元素在物理位置上__________相邻.
19.在一个长度为n的数组中删除第i个元素(1≤i≤n)时,需要向前移动的元素的个数是__________.
20.设F、C是二叉树中的两个结点,若F是C的祖先结点,则在采用后根遍历方法遍历该二叉树时,F和C的位置关系为:F必定在C的__________.
21.若用后根遍历法遍历题21图所示的二叉树,其输出序列为__________. 

全国2007年10月高等教育自学考试数据结构导论试(图3)
 
22.具有n个顶点的连通图至少需有__________条边.
23.在无向图G的邻接矩阵A中,若A[i][j]等于1,则A[j][i]等于__________.
24.设顺序表的表长为n,且查找每个元素的概率相等,则采用顺序查找法查找表中任一元素,在查找成功时的平均查找长度为__________.
25.在索引顺序表上的查找分两个阶段:一是查找__________,二是查找块.
26.文件的基本运算有检索和修改两类.而检索又有三种方式,它们是__________存取、直接存取和按关键字存取.
27.在对一组关键字为(54,38,96,23,15,72,60,45,83)的记录采用直接选择排序法进行排序时,整个排序过程需进行__________趟才能够完成.
28.冒泡排序是一种稳定排序方法.该排序方法的时间复杂度为__________.

三、应用题(本大题共5小题,每小题6分,共30)
29.分别写出题29图中二叉树的先根、中根、后根遍历序列.

全国2007年10月高等教育自学考试数据结构导论试(图4)
 
30.设要将序列(Q,H,C,Y,P,A,M,S,R)按字母升序排序,请分别画出采用堆排序方法时建立的初始堆,以及第一次输出堆顶元素后经过筛选调整的堆的完全二叉树形态.
31.如题31图所示,输入元素为A,B,C,在栈的输出端得到一个输出序列ABC,试写出在栈的输入端三个可能的输入序列.
全国2007年10月高等教育自学考试数据结构导论试(图5)

32.已知无向图G的邻接矩阵如题32图所示.请画出该无向图,并写出按深度优先搜索时的访问序列.
全国2007年10月高等教育自学考试数据结构导论试(图6)
 
33.对长度为20的有序表进行二分查找,试画出它的一棵判定树.

四、算法设计题(本大题共2小题,每小题7分,共14分)
34.下面程序段为删除循环链表中第一个info域值等于x的结点,请填上程序中缺少的部分.循环链表的结构如题34图所示:

全国2007年10月高等教育自学考试数据结构导论试(图7)
 
struct node{ int info;struct node *link; }
int Delete (struct node *head, int x)
{ struct node *p, *q; /*p:当前处理的结点;q:p的前驱结点*/
if (! head ) return (0);
if (head→link ==head)
{ if (head→info==x)
{ free (head);head=NULL;return (x)
}
return (0);
}
p=head; q=head;
while (q→link!=head) q=(1) ;
while (p→link!=head)
{ if (p→info==x)
{ (2) ;
if (p==head) head=(3) ;
free (p);return (x);
}
else { q=p ;(4;}
}
return (0);
}
35.设以二叉链表为二叉树的存储结构,结点的结构如下

lchild

data

rchild

其中data域为整数,试设计一个算法void change(bitreptr r): 若结点左孩子的data域的值大于右孩子的data域的值,则交换其左、右子树.

点击查看全部真题 >>

扫码登录


扫码关注“四川小自考”微信公众号

即可查看全部内容

二维码以过期,请重新刷新

本文标签:四川小自考 历年真题 全国2007年10月高等教育自学考试数据结构导论试

转载请注明:文章转载自(http://www.scxzk.net

本文地址:http://www.scxzk.net/html/lnzt/12025.html

小编提示:添加【四川小自考】指导老师微信,即可了解2023年四川小自考政策资讯小自考报名入口准考证打印入口成绩查询时间以及领取历年真题资料个人专属备考方案等相关信息!

四川小自考指导老师微信
(添加“四川小自考”指导老师微信,在线咨询报名报考等相关问题)

《四川小自考网》免责声明:

1、由于各方面情况的调整与变化,本网提供的考试信息仅供参考,考试信息以省考试院及院校官方发布的信息为准。

2、本网信息来源为其他媒体的稿件转载,免费转载出于非商业性学习目的,版权归原作者所有,如有内容与版权问题等请与本站联系。联系邮箱:812379481@qq.com

相关《全国2007年10月高等教育自学考试数据结构导论试》的文章

四川小自考-便捷服务