数据结构导论历年真题Word格式文档下载.docx
《数据结构导论历年真题Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《数据结构导论历年真题Word格式文档下载.docx(24页珍藏版)》请在冰点文库上搜索。
next指针指向链尾结点B.h指向链尾结点
C.删除链尾前面的结点D.删除链尾结点
5.设顺序表有19个元素,第一个元素的地址为200,且每个元素占3个字节,则第14个元素的存储地址为()
A.236B.239C.242D.245
6.一个栈的入栈序列是a,b,c,d,e,则栈的输出序列不可能是()
A.dceabB.decba
C.edcbaD.abcde
7.元素大小为1个单元,容量为n个单元的非空顺序栈中,以地址高端为栈底,以top作为栈顶指针,则出栈处理后,top的值应修改为()
A.top=topB.top=n-1
C.top=top-1D.top=top+1
8.某二叉树的先根遍历序列和后根遍历序列正好相反,则该二叉树具有的特征是()
A.高度等于其结点数B.任一结点无左孩子
C.任一结点无右孩子D.空或只有一个结点
9.在完全二叉树中,若一个结点是叶结点,则它没有()
A.左孩子结点
B.右孩子结点
C.左孩子结点和右孩子结点
D.左孩子结点,右孩子结点和兄弟结点
10.邻接矩阵为对称矩阵的图是()
A.有向图B.带权有向图
C.有向图或无向图D.无向图
11.在一个具有n个顶点的无向图中,要连通全部顶点至少需要的边数为()
A.n-1B.n
C.n+1D.
12.若构造一棵具有n个结点的二叉排序树,最坏的情况下其深度不超过()
A.
B.n
C.
D.n+1
13.闭散列表中由于散列到同一个地址而引起的“堆积”现象,是()
A.由同义词之间发生冲突引起的
B.由非同义词之间发生冲突引起的
C.由同义词之间或非同义词之间发生冲突引起的
D.由散列表“溢出”引起的
14.一个序列中有10000个元素,若只想得到其中前10个最小元素,最好采用的排序方法是()
A.快速排序B.堆排序
C.插入排序D.二路归并排序
15.在排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为()
A.希尔排序B.插入排序
C.冒泡排序D.快速排序得分
二、填空题(本大题共13小题,每小题2分,共26分)
16.数据的逻辑结构通常包括集合、线性结构、____________和图状结构。
17.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1,指针s指向双链表中的一个结点(该结点既非头结点,也非尾结点),则删除s指针所指向结点的操作为“s->
tl->
r1=s->
r1;
”和“____________”。
18.对稀疏矩阵进行压缩存储的目的是节省____________。
19.在一个具有n个结点的单链表中查找值为m的某结点,若查找成功,则需平均比较的结点数为____________。
20.深度为15的满二叉树上,第11层有____________个结点。
21.对一棵有100个结点的完全二叉树按层编号,则编号为49的结点,它的左孩子的编号为____________。
22.一个具有4个顶点的无向完全图有____________条边。
23.一个有向图G中若有孤<
Vi,Vj>
、<
Vj,Vk>
和<
Vi,Vk>
,则在图G的拓扑序列中,顶点Vi,Vj和Vk的相对位置为____________。
24.在一棵二叉排序树上按____________遍历得到的结点序列是一个有序序列。
25.实现二分查找的存储结构仅限于顺序存储结构,且其中元素排列必须是____________的。
26.文件的检索有三种方式,它们是顺序存取、直接存取和____________存取。
27.在插入排序和选择排序中,若原始记录已基本有序,则较适合选用____________。
28.对n个元素的序列进行冒泡排序时,最多需进行____________趟。
三、应用题(本大题共5小题,每小题6分,共30分)
29.写出利用直接选择排序方法对一组关键码为(54,38,96,23,15,72,60)的记录进行排序时,每趟排序的结果。
30.已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC和DBFHGECA,试画出这棵二叉树。
31.设闭散列表容量为7(散列地址空间0..6),给定表(30,36,47,52,34),散列函数H(K)=Kmod6,采用线性探测法解决冲突,要求:
(1)构造散列表;
(2)求查找数34需要比较的次数。
32.如题32图所示,在栈的输入端有6个元素,顺序为A,B,C,D,E,F。
能否在栈的输出端得到序列DCFEBA及EDBFCA?
若能,给出栈操作的过程,若不能,简述其理由。
题32图
33.已知无向图G的邻接表如题33图所示,请画出该无向图,并写出其按广度优先搜索时的访问序列。
其中nil表示空。
题33图
四、算法设计题(本大题共2小题,每小题7分,共14分)
34.编写一个函数voidinsert(int*p,intsize,inta),其功能是将a插入指针变量p指向的长度为size的数组中。
设数组中的数据已按升序排序。
该函数要求实现的功能是:
首先采用折半查找的方法,找出要插入数据的位置;
然后按升序将数据插入该数组中。
35.某带头结点的单链表的结点结构说明如下:
typedefstructnode1
{
intdata;
structnode1*next
}node;
试设计一个算法intcopy(node*head1,node*head2),将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。
全国2007年1月高等教育自学考试数据结构导论试题
1.关于栈和队列的说法中正确的是()
A.栈和队列都是线性结构
B.栈是线性结构,队列不是线性结构
C.栈不是线性结构,队列是线性结构
D.栈和队列都不是线性结构
2.关于存储相同数据元素的说法中正确的是()
A.顺序存储比链式存储少占空间
B.顺序存储比链式存储多占空间
C.顺序存储和链式存储都要求占用整块存储空间
D.链式存储比顺序存储难于扩充空间
3.从逻辑关系来看,数据元素的直接前驱为0个或1个的数据结构只能是()
A.线性结构B.树形结构
C.线性结构和树型结构D.线性结构和图状结构
4.已知一个单链表中,指针q指向指针p的前趋结点,若在指针q所指结点和指针p所指结点之间插入指针s所指结点,则需执行()
A.q→next=s;
p→next=s;
B.q→next=s;
s→next=p;
C.q→next=s;
q→next=p;
D.q→next=s;
s→next=q;
5.在长度为n的线性表中删除一个指针p所指结点的时间复杂度是()
A.O(n)B.O
(1)
C.O(log2n)D.O(n2)
6.设一个栈的输入序列是a,b,c,d,则所得到的输出序列(输入过程中允许出栈)不可能出现的是()
A.a,b,c,dB.a,b,d,c
C.d,c,b,aD.c,d,a,b
7.关于串的叙述中,正确的是()
A.空串是只含有零个字符的串
B.空串是只含有空格字符的串
C.空串是含有零个字符或含有空格字符的串
D.串是含有一个或多个字符的有穷序列
8.在具有m个单元的循环队列中,队头指针为front,队尾指针为rear,则队满的条件是()
A.front==rearB.(front+1)%m==rear
C.rear+1==frontD.(rear+1)%m==front
9.设有二维数组A[n][n]表示如下:
,则A[i][i](0≤i≤n-1)的值为()
A.i*(i-1)/2B.i*(i+1)/2
C.(i+2)*(i+1)/2D.i2/2
10.高度为h的完全二叉树中,结点数最多为()
A.2h-1B.2h+1
C.2h-1D.2h
11.由m棵结点数为n的树组成的森林,将其转化为一棵二叉树,则该二叉树中根结点的右子树上具有的结点个数是()
A.mnB.mn-1
C.n(m-1)D.m(n-1)
12.在一个具有n个顶点的无向图中,每个顶点度的最大值为()
A.nB.n-1
C.n+1D.2(n-1)
13.关于无向图的邻接矩阵的说法中正确的是()
A.矩阵中非全零元素的行数等于图中的顶点数
B.第i行上与第i列上非零元素总和等于顶点Vi的度数
C.矩阵中的非零元素个数等于图的边数
D.第i行上非零元素个数和第i列上非零元素个数一定相等
14.设一组记录的关键字key值为{62,50,14,28,19,35,47,56,83},散列函数为H(key)=keymod13,则它的开散列表中散列地址为1的链中的结点个数是()
A.1B.2
C.3D.4
15.设有一组初始关键字值序列为(49,81,55,36,44,88),则利用快速排序的方法,以第一个关键字值为基准得到的一次划分为()
A.36,44,49,55,81,88B.44,36,49,55,81,88
C.44,36,49,81,55,88D.44,36,49,55,88,81
16.在数据结构中,各个结点按逻辑关系互相缠绕,任意两个结点可以邻接的结构称为_______。
17.每个存储结点只含一个数据元素,所有存储结点连续存放。
此外增设一个索引表,索引表中的索引指示各存储结点的存储位置或位置区间端点。
按这种方式组织起来的存储结构称为_______。
18.在顺序表上读表元算法的时间复杂度为_______。
19.双链表中前驱指针为prior,后继指针为next,在指针P所指结点前插入指针S所指的结点,需执行下列语句:
S→next=P;
S→prior=P→prior;
P→prior=S;
_______;
20.设数组A[0..8][0..8]的起始元素位置为a,每个元素占2L个存储单元,按行序为主序存储。
若元素A[i][j]的存储位置为a+66L,则元素A[j][i]的存储位置为_______。
21.有4个结点且深度为4的二叉树的形态共有_______种。
22.某二叉树的先根遍历序列为IJKLMNO,中根遍历序列为JLKINMO,则该二叉树中根结点的右孩子是_______。
23.第一个顶点和最后一个顶点相同的路径称为回路或者环,除第一个顶点和最后一个顶点外,其余顶点都不重复的回路,称为_______。
24.一个具有10个顶点的完全无向图中有_______条边。
25.一棵平衡二叉树中任一结点的平衡因子只可能是_______。
26.二分查找的时间复杂度为_______。
27.二路归并排序算法的时间复杂度为_______。
28.文件的基本存取单位是_______。
29.有一字符串序列为5*-x-y/x+2,利用栈的运算将其输出结果变为5x-*yx+/-2,试写出该操作的入栈和出栈过程(采用push(a)表示a入栈,pop(a)表示a出栈)。
30.某二叉树的先根遍历序列为ABIJCDFGHE,中根遍历序列为IJBADGFHCE,试画出该二叉树,并写出它的后序遍历序列。
31.用冒泡排序算法对数据序列(49,38,65,97,76,134,27,49)进行排序,写出整个冒泡排序的每一趟过程。
32.题32图所示二叉树是否为平衡二叉树?
若是,说明理由;
若不是,将其转换为平衡二叉树。
33.已知连通网的邻接矩阵A=
,试画出它所表示的连通网并画出该连通网的最小生成树。
34.设单链表的结点结构如下:
structnode{datatypedata;
structnode*next;
}
试编写一个函数intcount(structnode*head,datatypex)统计单链表中数据域为x的结点个数。
35.试写出直接插入排序算法。
全国2006年1月高等教育自学考试数据结构导论试题
1.数据结构中所定义的数据元素,是用于表示数据的( )
A.最小单位B.最大单位
C.基本单位D.不可分割的单位
2.数据的四种基本存储结构是指( )
A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构
B.顺序存储结构、索引存储结构、链式存储结构、散列存储结构
C.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构
D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构
3.对于长度为n的顺序表执行删除操作,则其结点的移动次数( )
A.最少为0,最多为n
B.最少为1,最多为n
C.最少为0,最多为n-1
D.最少为1,最多为n-1
4.在一个单链表中,若p所指结点是q所指结点的前驱结点,则删除结点q的正确操作是
( )
next=qB.p->
next=q->
next
C.p=q->
nextD.p->
5.有关栈的描述,正确的是( )
A.栈是一种先进先出的特殊的线性表
B.只能从栈顶执行插入、删除操作
C.只能从栈顶执行插入、栈底执行删除
D.栈顶和栈底均可执行插入、删除操作
6.二维数组A[10][20]采用按行为主序的存储方式,每个元素占4个存储单元,若A[0][0]的存储地址为300,则A[10][10]的地址为( )
A.700B.1120
C.1180D.1140
7.关于二叉树性质的描述,正确的是( )
A.二叉树结点的个数可以为0
B.二叉树至少含有一个根结点
C.二叉树若存在两个结点,则必有一个为根,另一个为左孩子
D.二叉树若存在三个结点,则必有一个为根,另两个分别为左、右孩子
8.具有4个结点的二叉树可有( )
A.4种形态B.7种形态
C.10种形态D.11种形态
9.若采用邻接表存储结构,则图的深度优先搜索类似于二叉树的( )
A.先根遍历B.中根遍历
C.后根遍历D.层次遍历
10.具有n个顶点的无向图,若要连通全部顶点,至少需要( )
A.(n-1)条边B.n条边
C.n(n-1)条边D.n(n-1)/2条边
11.下列四种基本的逻辑结构中,结构结点间不存在任何逻辑联系的是( )
A.集合B.线性结构
C.树形结构D.图形结构
12.闭散列表中由于散列到同一个地址而引起的“堆积”现象,是由( )
A.同义词之间发生冲突引起的
B.非同义词之间发生冲突引起的
C.同义词与非同义词之间发生冲突引起的
D.散列地址“溢出”引起的
13.ISAM文件组织方式是一种( )
A.专门适用于磁带的存取方法
B.专门适用于磁盘的存取方法
C.专门适用于光盘的存取方法
D.可适用于磁带、磁盘、光盘等多用途的存取方法
14.当待排序序列中记录数较多时,速度最快的排序方法是( )
A.冒泡排序法B.快速排序法
C.堆排序法D.归并排序法
15.若对序列(15,30,26,22,69,50,53,87)采用二路归并法排序,则进行一趟归并后产生的序列为( )
A.15,22,26,30,50,53,69,87B.15,30,22,26,50,69,53,87
C.15,26,30,22,50,69,53,87D.15,26,22,30,50,53,69,87
16.数据表示和________________是程序设计者所要考虑的两项基本任务。
17.一个算法通常可从正确性、易读性、健壮性和________________等四个方面评价、分析。
18.对长度为n的顺序表执行删除操作,其删除算法在最坏情况下的时间复杂性为________________。
19.串是一种特殊的线性表,串常见的存储结构有顺序存储和________________两种方式。
20.我们通常把队列中允许插入的一端称为________________。
21.二维数组在机器级的具体实现,通常均采用________________存储结构。
22.深度为k的满二叉树其叶子结点个数共有________________个。
23.二叉树通常采用________________两种存储结构表示。
24.若一个完全无向图具有n条边,则该图的顶点个数为________________。
25.查找表的逻辑组织结构实际上是________________结构。
26.对于具有n个元素的数据序列,采用顺序查找法,其平均查找长度为________________。
27.若构成索引文件的索引表有序而主文件无序,则该索引文件称为________________文件。
28.对于具有n个元素的有序序列,若采用冒泡排序,最多需要进行________________趟起泡。
29.试采用类C语言,给出二叉树的二叉链表结构描述。
30.试用Prim算法构造题30图的最小生成树,要求分步给出构造过程。
题30图
31.请按照数列{28,45,33,12,37,20,18,55}的先后插入次序,生成一棵二叉排序树。
32.已知一组键值序列(33,37,26,43,55,67,42,38),试采用堆排序法对该组序列作升序排序,给出建立的初始堆,以及第一次输出堆元素后筛选调整的堆。
33.已知一组键值序列(22,24,26,25,27,29,21,28),试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。
四、设计题(本大题共2小题,每小题7分,共14分)
34.试编写一个函数,以读取单链表的第i个元素。
35.若二叉树采用二叉链表表示,试给出二叉树先根遍历的非递归算法描述。
全国2005年10月高等教育自学考试数据结构导论试题
1.若要描述数据处理的变化过程,其正确的次序应为()
A.处理要求、基本运算和运算、算法
B.处理要求、算法、基本运算和运算
C.基本运算和运算、处理要求、算法
D.算法、处理要求、基本运算和运算
2.从运算类型角度考虑,属于引用型的运算是()
A.插入、删除B.删除、修改
C.查找、读取D.查找、删除
3.若在长度为n的顺序表中插入一个结点,则其结点的移动次数()
A.最少为0,最多为nB.最少为1,最多为n
C.最少为0,最多为n+1D.最少为1,最多为n+1
4.在一个单链表中,若p所指结点是q所指结点的前驱结点,则在结点p、q之间插入结点s的正确操作是()
A.s->
next=q;
next=s->
B.p->
next=s
C.s->
next;
D.s->
5.若有一串数字5、6、7、8入栈,则其不可能的输出序列为()
A.5、6、7、8B.8、7、6、5
C.8、7、5、6D.5、6、8、7
6.FORTRAN语言对数组元素的存放方式通常采用()
A.按行为主的存储结构B.按列为主的存储结构
C.按行或列为主的存储结构D.按行和列为主的存储结构
7.树是n个结点的有穷集合,()
A.树的结点个数可以为0,此时称该树为空树
B.树至少含有一个根结点,不能为空
C.树至少含有一个根结点和一个叶子结点
D.树至少含有一个根结点和两个叶子结点
8.深度为k的二叉树至多有()
A.2k个叶子B.2k-1个叶子
C.2k-1个叶子D.2k-1-1个叶子
9.具有10个顶点的有向完全图应具有()
A.20条弧B.50条弧
C.90条弧D.100条弧
10.从V1出发,对题10图按广度优先搜索遍历,则可能得到的一种顶点序列为()
A.V1V2V3V5V4V6
B.V1V2V3V5V6V4
C.V1V5V2V3V6V4
D.V1V3V6V4V5V2
11.适用于静态的查找方法为()
A.二分查找、二叉排序树查找
B.二分查找、索引顺序表查找
C.二叉排序树查找、索引顺序表查找
D.二叉排序树查找、散列法查找
12.采用二分查找法,若当前取得的中间位置MID的元素值小于被查找值,则表明待查元素可能在表的后半部分,下次查找的起始位置通常应()
A.从MID/2位置开始B.从MID位置开始
C.从MID-1位置开始D.从MID+1位置开始
13.磁盘是一种广泛使用的外部存储设备,对磁盘的存取操作()
A.只能用顺序方式B.只能用随机方式
C.既能用顺序方式也能用随机方式D.方式取决于具体的机器
14.当待排序序列中记录数较少或基本有序时,最适合的排序方法为()
A.直接插入排序法B.快速排序法
C.堆排序法D.归并排序法
15.若对序列(26,90,23,53,16,34,69,39,22)进行一趟排序后所得到的结果为(22,16,23,26,53,34,69,39,90),则该排序可能使用的方法是()
A.插入排序B.冒泡排序
C.快速排序D.选择排序
16.算法通常可分为程序、伪语言算法和__________三种类型。
17.时间复杂性描述量级中,若某算法达到__________量级,则该算法通常是不可计算的。
18.对顺序表执行删除操作,其删除算法的平均时间复杂性为__________。
19.若head表示循环链表的头指针,t表示尾结点,则头指针head与尾结点t之间的关系可表示