数据结构真题.docx
- 文档编号:11208672
- 上传时间:2023-05-29
- 格式:DOCX
- 页数:18
- 大小:76.58KB
数据结构真题.docx
《数据结构真题.docx》由会员分享,可在线阅读,更多相关《数据结构真题.docx(18页珍藏版)》请在冰点文库上搜索。
数据结构真题
2007年山东省专升本考试数据结构真题
一、判断题(10分。
本大题共10小题,每小题1分,在小题左面用√表示是,×表示否)
1.线性表的顺序存储结构是一种随机存储结构。
()
2.一个栈的入栈序列是a,b,c,d,e,则dceab是一个不可能的输出序列。
()
3.广义表(a,(a,b),d,e,((i,j),k))的深度是2。
()
4.树是一种重要的线性数据结构。
()
5.按照二叉树的定义,具有三个结点的二叉树有5种。
()
6.已知一个有向图的邻接矩阵表示,计算第i个结点的出度的方法是求矩阵第i列非零元的个数。
()
7.将递归算法转换为对应的非递归算法时,通常需要使用队列。
()
8.在哈夫曼编码中,当两个字符出现的频率相同时,其编码也相同。
()
9.散列法存储的基本思想是由关键字的值决定数据的存储地址。
()
10.(101,88,46,70,34,39,45,58,66,10)是堆。
()
二、填空题(15分。
本大题共5小题,5个空,每个空3分,将正确答案填在空格处)。
1.将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中,已知每个元素占4个单元,则A[7,5]的地址为___________。
2.若某二叉树有20个叶结点,有30个只有一个孩子的结点,则该二叉树的总结点数为___________。
3.如果以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树,则其带权路径长度是___________。
4.在顺序存储的二叉树中,编号为i和编号为j的结点处在同一层的条件是___________。
5.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值为82的结点时,___________次比较后查找成功。
三、(10分)已知关键字序列为{46,57,84,32,73,36,15,48,90,20},要求:
(1)构造一棵二叉排序树;
(2)在等概率情况下,该二叉排序树查找成功的平均查找长度。
四、(8分)假设在长度大于1的循环链表中,既无头结点,也无头指针,p为指向该链表中某个结点的指针。
设计一个算法,删除p指向结点的前趋结点。
五.(7分)设算术表达式由字符串b表示,其中可以包括三种括号:
圆括号、方括号和花括号,嵌套的顺序任意,如{[()]()}是正确的。
请编写一个算法,实现判别给定表达式中所含括号是否正确配对。
2008年山东省专升本考试数据结构真题
一、单项选择题(10分、每题1分)
1、在一个单链表,已知p所指向的是q所指向结点的前驱结点,若在q和p之间插入s所指向的结点,则执行()
A、s->next=q->next;q->next=sB、q->next=s->next;s->next=q
C、p->next=s;s->next=qD、q->next=s;s->next=p
2、串是()
A、一些符号构成的序列B、一些字母构成的序列
C、一个以上的字符构成的序列D、任意有限个字符构成的序列
3、数组A[10][10]的下标下界为1,每个元素占2个字节,存储在起始地址为100的连续内存单元,则元素A[3][8]的地址为()
A、138B、154C、111D、145
4、已知广义表L=((x,y,z),a,(u,t,w)),则从L中取出原子项y的操作是()
A、head(tail(head(L)))B、head(head(tail(tail(tail(L)))))
C、head(tail(tail(tail(tail(L)))))D、head(tail(tail(head(tail(L)))))
5、已知完全二叉树有80个结点,则整个二叉树有____个度为2的结点。
()
A、39B、41C、40D、38
6、赫夫曼树中度为1的结点个数为()
A、0B、1C、2D、不确定
7、具有n个顶点的有向完全图,边的总数为()
A、nB、n(n-1)C、n-1D、n(n-1)/2
8、二分查找法适用于存储结构为____的,且按关键字排好序的线性表。
()
A、顺序存储B、链接存储C、顺序存储或链接存储D、索引存储
9、下列排序算法中,第一趟排序结束后,其最大或最小元素一定在其最终位置上的算法是()
A、归并排序B、直接插入排序C、快速排序D、起泡排序
10、一个有向无环图的拓扑序列个数是()
A、1个B、1个或多个C、0个D、多个
二、正误判断题(10分,正确打√,错误打×,每小题1分)
1、链表中结点数据域占的存储空间越多,存储密度越小。
()
2、带头结点和不带头结点的单链表在查找、删除、求长度等操作上无区别。
()
3、如果两个串串长相等且对应字符也相同,则这两个串相等。
()
4、压缩存储的三角矩阵和对称矩阵的存储空间不相同。
()
5、满二叉树是完全二叉树。
()
6、对于给定的树,与其对应的二叉树是唯一的。
()
7、线索二叉树的指针域中,指向前驱或后继的个数少于指向孩子的个数。
()
8、给定图的邻接矩阵存储不一定唯一。
()
9、若一个有向图的邻接矩阵主对角线以下的元素均为0,则该图拓扑有序序列存在。
()
10、对n个记录进行直接插入排序,其平均时间复杂度为O(nlog2n)。
()
三、填空题(10分,1题每空2分,其他题每空1分)
1、下列函数的功能是实现带头结点的单链表逆置。
voidturn(slink*L)
{
slink*p,*q;
p=_____________________________;
L->next=NULL;
while(___________________________)
{
q=p;
p=___________________________;
q->next=L->next;
L->next=q;
}
}
2、“算法”(Algorithm)就是对求解问题步骤的一种描述,也称为算法设计。
它具有以下五个特征有穷性,_____________,_______________,输入和输出。
3、评价算法好坏的五个方面_______________,_______________,正确性,可读性,健壮性。
四、操作计算题(10分,每题5分)
1、有一组关键字序列(24,19,56,13,97,59,41,85,1,87),写出用堆排序法进行升序排序的初始堆序列及第一趟排序后的堆序列。
2、给定如下图所示的带权无向图G1。
(1)画出该图的邻接矩阵
(2)给出采用普里姆算法从顶点3出发构造最小生成树的的过程。
五、算法设计题(10分)
给定二叉树,采用链式结构存储,编写算法voidcount(BitTreebt),实现功能:
统计二叉树中度为1的结点数目。
2009年山东省专升本考试数据结构真题
一、填空题(10分,每空0.5分)
1、根据数据元素之间关系的不同,数据的逻辑结构划分为______、______、______、______。
2、栈是一种特殊的线性表,它允许在表的一端进行____________操作,栈中元素的进出原则为__________________。
3、深度为k的二叉树其结点数最多有______个结点。
4、通常象交通、道路问题的数学模型是一种称为____________的数据结构。
5、算法的五个重要的特征是______、______、______、______、______。
6、两个字符串相等的充分必要条件是____________________________________。
7、在一棵二叉树中,度为零的结点个数为
,度为2的结点个数为
,则有
=______。
8、树的度是指__________________________________________的最大值。
9、在一个有向图中,某个结点的度是指该结点的______和______之和。
10、在线性表的二分查找法中要求线性表的存储结构必须是采用____________,且表中的元素必须是____________。
二、选择题(10分,每题1分)
1.一个具有10个顶点的无向完全图应有______条边。
()
A.9B.45C.55D.90
2.长度为n(1…n)的顺序循环队列中,front和rear分别指示队首和对尾,判断队列为满队列的条件是()
A.rear=frontB.(rear+1)%n=front
C.rear=0D.front=0
3.由______组成的集合是一个数据对象。
()
A.不同类型的数据项B.不同类型的数据元素
C.相同类型的数据项D.相同类型的数据元素
4.______是表示线性数据结构的。
()
A.循环链表B.邻接多重表
C.孩子链表D.单链表
5.设一个栈的入栈元素序列为a,b,c,d,e,则不可得到出栈的元素序列有()。
A.edcbaB.decbaC.dceabD.abcde
6.______又是一棵满二叉树。
()
A.二叉排序树B.深度为5有31个结点的二叉树
C.有15个结点的完全二叉树D.哈夫曼(Huffman)树
7.折半查找有序表(2,5,8,20,25,36,40,60),若查找元素60,需依次与表中元素______进行比较。
()
A.20,36,40,60B.25,40
C.25,40,60D.20,36,40
8.查找哈希(Hash)表,解决冲突的方法有()。
A.链地址法B.线性探测再散列法
C.直接地址法D.除留余数法
9.一个排序算法时间复杂度的大小______有关。
()
A.不与所需移动记录的数目
B.与该算法的稳定性
C.与所需比较关键字的次数
D.与所需辅助存储空间的大小
10.数据的基本单位是。
()
A.结点B.数据元素C.数据类型D.数据项
三、求解下列问题(10分,每题5分)
1.将下面的一个普通书转换成一棵二叉树,并写出它先序、中序、后序三种遍历的遍历序列。
转换后的二叉树:
先序遍历序列:
中序遍历序列:
后序遍历序列:
2.用克鲁斯卡尔算法将下面的图构造成最小生成树,画出生成过程。
四、程序填空(10分,每空1分)
1.将下面折半查找算法补充完整
算法说明:
已知r[1…n]是n个记录的递增有序表,用折半查找法查找关键字为k的记录,若查找失败返回零;否则返回该记录的序号值。
查找表顺序存储结构定义如下:
#defineMAXSIZE100
typedefstruct
{
keytypekey;
}Nodetype;
typedefNodetypeSqlist[MAXSIZE];
算法(C函数):
intbinsearch(Sqlistr,datatypek,intn)
{
intlow=1,high=n,mid;
while(_______________)
{
_______________;
if(r[mid].key==k)
_______________;
elseif(r[mid].key>k)
_______________
else
_______________
}
return(0);
}
2.将下面单链表的插入算法补充完整。
算法说明:
在带有头结点的单链线性表中第i个位置之前插入元素x:
typedef_______________
{
DataTypedata;
structnode*next;
}LNode,*LinkList;
intlistinsert(LinkListhead,inti,DataTypex)
{
LinkListp=head.s
intj=0;
while(p!
=NULL&&j { _______________; j++; } if(p==NULL)return(0); s=_______________malloc(sizeof(LNode)); s->data=x; _______________; _______________; return (1); } 五、算法设计(10分) 已知S为顺序栈。 写出S的存储结构类型描述。 编写算法实现将元素x入栈操作Push(S,x),入栈成功返回1,否则返回0和删除栈顶元素的出栈操作Pop(S)出栈成功返回1,否则返回0。 2010年山东省专升本考试数据结构真题 一、判断题(每小题1分,共5分) 1.算法的执行时间和所需的存储空间都是问题规模的函数,进行算法分析就是要找出这种函数关系。 () 2.完全二叉树只能采用顺序存储方法,不能采用链表存储方法。 () 3.在顺序循环队列的第i个元素之后插入一个元素是顺序循环队列的基本运算。 () 4.若一个叶子是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序遍历的最后一个结点。 () 5.直接插入排序的关键码比较次数与初始排列有关。 () 二、单项选择题(每小题2分,共10分) 1.以下数据结构中哪一个是线性结构() A.栈B.线索二叉树C.AOV网D.二叉排序树 2.若有a,b,c三个字符的字符序列执行入栈操作,则其所有可能的输出排列共有() A.4种B.5种C.6种D.其它 3.一棵树的广义表表示为a(b,c(e,f(g)),d),当用左孩子—右兄弟链表表示时,右指针域非空的节点个数为() A.1B.2C.3D.4 4.下面关于图的存储的叙述中正确的是() A.用邻接矩阵法存储图,占用的存储空间大小与图中结点个数和边数都有关 B.用邻接矩阵法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关 C.用邻接表法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关 D.用邻接表法存储图,占用的存储空间大小与图中边数和结点个数都有关 5.对长度为12的有序表采用顺序存储结构,折半查找技术,在等概率情况下,查找成功的平均查找长度是() A.37/12B.62/13C.49/12D.其它 三、应用题(每小题5分,共20分) 1、已知一棵三叉树的存储结构如下表所示,其中root=0,n=7。 画出该二叉树。 2、用克鲁斯卡尔算法求下图的最小生成树。 3、下图是一棵二叉排序树,规定当二叉排序树被删除的结点既有左子树,又有右子树时,以其中序前驱替代。 画出删除55后的二叉排序树。 4、已知散列表地址空间为HT[0..8],散列函数为H(key)=key%7,采用线性探测法处理冲突,将数据序列{107,27,28,42,3,25,99,38}依次存入散列表中。 试画出相应的散列表;并计算等概率下搜索成功的平均搜索长度。 散列表及其查找各关键字要比较的次数如下所示: 0 1 2 3 4 5 6 7 8 关键字 比较次数 搜索成功的平均搜索长度为: ASL= 四、算法设计题(每小题5分,共15分) 1.已知顺序栈s,简述f1函数功能,当输入80时,输出结果是多少? f1() {initstack(s);scanf(“%d”,&n); while(n){push(s,n%8);n=n/8)} while(! Emptystcak(s)){pop(s,x);printf(“%d”,x);} } 2.写出二叉树前序遍历非递归算法的设计思想,然后写出算法。 3.写出直接插入排序算法。 2011年山东省专升本考试数据结构真题 一、选择题(本大题共10小题,每小题1分,共10分) 1.数据结构,与所使用的计算机无关的是数据的哪种结构() A.存储B.物理C.逻辑D.物理和存储 2.线性表是() A.一个有限序列,可以为空B.一个有限序列,不能为空 C.一个无限序列,可以为空D.一个无限序列,不能为空 3.下列哪个选项的邻接矩阵必定是对称矩阵() A.有向图B.无向图C.AOV网D.AOE网 4.串是一种特殊的线性表,其特殊性体现在() A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符 5.不含任何结点的空树是() A.是一棵树B.是一棵二叉树C.是一棵树也是一棵二叉树D.既不是树也不是二叉树 6.已知一维数组A采用顺序存储结构,每个元素占用4个存储单元,第9个元素的地址为144,则第一个元素的地址是() A.108B.180C.176D.112 7.链表适用于哪种查找方法() A.顺序B.二分法C.顺序,也能二分法D.随机 8.用邻接表表示图,进行广度优先遍历时,通常是采用哪种结构来实现算法的。 () A.栈B.队列C.树D.图 9.任何一个无向连通图的最小生成树是() A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在 10.若某完全二叉树的结点个数为100,则第60个结点的度为() A.0B.1C.2D.不确定 二、填空题(本大题共5小题,每小题2分,共10分) 1、一棵深度为6的满二叉树有个分支点和个叶子。 2、一个字符串相等的充要条件是和。 3、从邻接矩阵A= 可以看出,该图共有个顶点。 如果是有向图,该图共有条弧。 4、栈的特点是,队列的特点是。 5、三元组表中的每个节点对应与稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素 的、和值。 三、简答题(本大题共2小题,每小题5分,共10分) 1、已知二叉树(如图)请给出它的3种遍历序列 先序: 中序: 后序 2、简述数据结构的概念? 在讨论数据结构时,一般会从哪三个方面进行? 四、操作题(本大题共2小题,每小题10分,共20分) 1、已知一组关键字为{19,14,23,1,68,20,84,27,55,11,10,79}设哈希函数为H(key)=keyMOD13,哈希表的地址范围为0-12用线性探测再散列法处理冲突。 完成问题: (1)构造哈希表。 1 2 3 4 5 6 7 8 9 10 11 12 (2)假定每个关键字的查找概率相等,求查找成功时的平均查找长度ASL。 2、已知某字符串S中共有8种字符(a,b,c,d,e,f,g,h)各种字符分别出现2次,1次,4次,5次,7次,3次,4次,9次。 试把它们作为叶子结点的权值构造一棵哈夫曼树,并求出其带权路径长度(WPL)。 山东省专升本考试计算机专业数据结构考试大纲 第1章绪论(理解) 1.1什么是数据结构 1.2数据结构的基本概念和常用的术语 1.3数据结构发展的历史以及数据结构在计算机科学中地位 1.4算法描述和算法分析 第2章线性表(熟练掌握) 2.1线性表的逻辑结构 2.2线性表的顺序存储结构 2.3线性表的链式存储结构 2.4线性表应用举例 第3章栈与队列(熟练掌握) 3.1栈 3.2表达式求值 3.3栈与递归过程 3.4队列 第4章串(掌握) 4.1串及其操作 4.2串的存储结构 4.3串的应用举例 第5章数组和广义表(掌握) 5.1数组的定义和运算 5.2数组的顺序存储结构 5.3矩阵的压缩存储 5.4广义表的定义 5.5广义表的存储结构 第6章树与二叉树(熟练掌握) 6.1树的结构定义和基本操作 6.2二叉树 6.3遍历二叉树和线索二叉树 6.4数和森林 6.5哈夫曼树及其应用 第7章图(掌握) 7.1图的定义和术语 7.2图的存储结构 7.3图的遍历 7.4图的连通性问题 7.5有向无环图的定义 7.6最短路径 第9章查找(掌握) 9.1静态查找表 9.2动态查找表 9.3哈希表 第10章内部排序(掌握) 10.1概述 10.2插入排序 10.3快速排序 10.4选择排序 10.5归并排序 10.6基数排序 10.7各种内部排序方法的比较讨论
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构
![提示](https://static.bingdoc.com/images/bang_tan.gif)