首页
下载
赚积分
充值
当前位置：
首页
>
所有资源
>
《数据结构》所有资源
>
国家开放大学11252《数据结构》期末考试题库及答案（课程号：02272）
国家开放大学11252《数据结构》期末考试题库及答案（课程号：02272）2025年春
下载打印版题库
适用科目：《数据结构》 课程号：02272 试卷号：11252
（点击下列按钮即可跳转对应的题型位置）
单选(735)
简答(6)
判断(438)
填空(402)
综合(102)
程序(59)
[单选]
1. 最小生成树指的是（）。
[单选]
2. 字符串的基本函数不包括（）。
[单选]
3. 字符串（）是“abcd321ABCD”的子串。
[单选]
4. 字符串a1=“AEIJING“,a2=“AEI“,a3=“AEFANG“,a4=“AEFI“中最大的是（）。
[单选]
5. 字符串“DABcdabcd321ABC“的子串是（）。
[单选]
6. 子串“acd”在主串“abdcacdefac”中的位置是（）。
[单选]
7. 直接插入排序在最好情况下的时间复杂度为O（）
[单选]
8. 执行下面程序段时，执行S语句的次数为（）。
[单选]
9. 这四个值作为叶子结点的权,生成一棵哈夫曼树,该树中所有叶子结点中的最长带权路径长度为（）。
[单选]
10. 折半搜索与二叉排序树的时间性能（）。
[单选]
11. 折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,则它将依次与表中（）比较大小,查找结果是失败。
[单选]
12. 栈在（）中有所应用。
[单选]
13. 栈和队列的主要区别在于（）。
[单选]
14. 栈和队列的共同特点是（）。
[单选]
15. 栈顶指针通常命名为（）
[单选]
16. 栈的基本运算包括（）
[单选]
17. 栈的插入和删除操作在（）进行。
[单选]
18. 栈的操作特性决定了它是一种（）的线性表。
[单选]
19. 战和队列的共同特点是（）。
[单选]
20. 在最坏情况下，折半查找与二叉排序树查找性能比较，（）。
[单选]
21. 在有序表{21,23,2,33,4,45,4,7,7,78,8,9,106}中,用折半查找值43时,经（）次比较后查找成功。
[单选]
22. 在有序表{2,4,7,14,34,43,47,64,75,80,90,97,120}中,用折半查找法查找值80时,经（）次比较后查找成功。
[单选]
23. 在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86时，经（）次比较后查找成功。
[单选]
24. 在有序表{10,14．34．43．47．64．75．80．90}中,用折半查找法查找值80时,经（）次比较后查找成功。
[单选]
25. 在有序表{1,3,8,13,33,42,46,63,76,78,86,97,100}中,用折半查找值86时,经（）次比较后查找成功。
[单选]
26. 在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。
[单选]
27. 在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。
[单选]
28. 在有向图的邻接表中,每个顶点邻接表链接着该顶点所有（）邻接点。
[单选]
29. 在有向图的邻接表中,每个顶点邻接表链接着该顶点所有（）邻接点。
[单选]
30. 在一棵树中，度为0的结点称作（）。
加载更多
[简答]
1. 栈、队列和线性表的区别是什么？
[简答]
2. 有5个元素,其入栈次序为：A、B、C、D、E,在各种可能的出栈次序中,以元素C、D最先的次序有哪几个？
[简答]
3. 设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是多少？
[简答]
4. 解释顺序存储结构和链式存储结构的特点,并比较顺序存储结构和链式存储结构的优缺点。
[简答]
5. 简述数据的逻辑结构和存储结构的区别与联系,它们如何影响算法的设计与实现？
[简答]
6. 简述广义表和线性表的区别和联系。
加载更多
[判断]
1. 最小生成树是指边数最少的生成树。
[判断]
2. 字符串属于线性的数据结构
[判断]
3. 字符串a1=〝heijing〞,a2=〝hen〞,a3=〝heifang〞,a4=“heni〞最小的是a2。
[判断]
4. 中序遍历一棵完全二叉树树可得到一个有序序列。
[判断]
5. 中序遍历一棵完全二叉树可得到一个有序序列。
[判断]
6. 只有用面向对象的计算机语言才能描述数据结构算法。
[判断]
7. 直接选择排序是一种不稳定的排序方法。
[判断]
8. 折半查找只适用与有序表,包括有序的顺序表和有序的链表。
[判断]
9. 折半查找方法运用在升序序列比降序序列效率更高，所以降序序列最好先转换为升序序列。
[判断]
10. 折半查找方法适用于按值有序的线性链表的查找。
[判断]
11. 折半查找的前提条件是，查找表中记录相应的关键字值必须有序或者部分有序。
[判断]
12. 折半查找的前提条件是，查找表中记录相应的关键字值必须有序或者部分有序。
[判断]
13. 栈允许进行插入和删除的一端称为栈顶
[判断]
14. 栈是限定在表的一端进行插入和删除操作的线性表，又称为先进后出表。
[判断]
15. 栈是限定在表的一端进行插入和删除操作的线性表，又称为先进后出表。
[判断]
16. 栈是限定在表的一端进行插入和删除操作的线性表,又称为先进后出表。
[判断]
17. 栈是限定在表的两端进行插入和删除操作的线性表，又称为先进先出表。
[判断]
18. 栈可以作为实现程序设计语言过程调用时的一种数据结构。
[判断]
19. 栈和队列是一种操作受限的线性表。
[判断]
20. 栈和队列都是特殊的线性表，但它们对存取位置的限制不同。
[判断]
21. 栈和队列都是特殊的线性表,但它们对存取位置的限制不同。
[判断]
22. 栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。
[判断]
23. 栈和队列都是操作受限制的线性表。
[判断]
24. 栈和队列的存储方式,既可以顺序存储也可以链式存储。
[判断]
25. 栈的特点是先进后出,队列的特点是先进先出。
[判断]
26. 栈的插入删除在栈底进行。
[判断]
27. 在只有度为0和度为k的结点的k叉树中,设度为0的结点有n0个,度为k的结点有nk个,则有n0=nk+1。
[判断]
28. 在栈满的情况下不能做进栈操作,否则将产生”上溢”。
[判断]
29. 在有序顺序存储的线性表中查找一个元素，用折半查找速度一定比顺序查找快。
[判断]
30. 在有序顺序存储的线性表中查找一个元素,用折半查找速度一定比顺序查找快。
加载更多
[填空]
1. 组成串的数据元素只能是（）。
[填空]
2. 字符串a1=“teijing“,a2=“tef“,a3=“teifang“,a4=“tefi“最小的是（）。
[填空]
3. 字符串a1=“heijing“．a2=“hef“．a3=“heifang“,a4=“hefi“中最小的是（）。
[填空]
4. 中序遍历一棵（）树可得到一个有序序列。
[填空]
5. 中序遍历二叉树的的操作定义为；若二叉树为空,则为空操作,否则进行如下操作,中序遍历二叉树的（）；访问而叉树的（）,中序遍历二叉树的（）。
[填空]
6. 中序遍历二叉排序树可得到一个（）的序列。
[填空]
7. 中序遍历（）树可得到一个有序序列。
[填空]
8. 折半查找只适用于（）的有序表。
[填空]
9. 折半查找又称为（）。使用该查找算法的前提条件是,查找表中记录相应的关键字值必须按（）。
[填空]
10. 栈元素的进、出栈次序是：后进（）。
[填空]
11. 栈又称为后进先出表,队列又称为（）表。
[填空]
12. 栈和队列的操作特点分别是（）和（）。
[填空]
13. 则该树共有（）个结点
[填空]
14. 则当队尾指针rear=（）时,队列为空,当rear=（）时,队列有6个元素。
[填空]
15. 在作入栈运算时应先判别栈是否（）。
[填空]
16. 在作出栈运算时应先判别栈是否（）。
[填空]
17. 在栈的ADT定义中,除初始化操作外,其他基本操作的初始条件都要求（）。
[填空]
18. 在有向图的邻接矩阵上,由第i行可得到第i个结点的出度,而由第j列可得到第回答个结点的入度。
[填空]
19. 在有向图G中,若任意两个顶点Vi和Vj都连通,从VI到Vj和从Vj到Vi都存在路径,则称该图为（）。
[填空]
20. 在一棵树中,每个结点的（）或者说每个结点的（）称为该结点的（）,简称为孩子。
[填空]
21. 在一棵二叉树中,若编号为i的结点存在右孩子,则右孩子的顺序编号为（）。
[填空]
22. 在一棵二叉树中,若编号为1的结点是其双亲结点的左孩子,则i结点的双亲结点的顺序编号为（）。
[填空]
23. 在一棵二叉树中,若编号为1的结点存在右孩子,则右孩子的顺序编号为（）。
[填空]
24. 在一个有向图中,所有顶点入度之和等于所有顶点出度之和的（）倍。
[填空]
25. 在一个无向图中,若存在一条边,则称Vi和Vj为该边的两个端点,并称他们互为（）。
[填空]
26. 在一个图中每条边可以表上具有某种含义的数值,该数值称为（）。
[填空]
27. 在一个顺序栈中,若栈顶指针等于（）,则为空栈；
[填空]
28. 在一个链式栈中,若栈顶指针等于NULL,则为（）；
[填空]
29. 在一个链式队列中,若队头指针与队尾指针的值相同,则表示该队列为（）或该队列只含有一个结点。
[填空]
30. 在一个链队中,设f和r分别为队头和队尾指针,则删除一个结点的操作为（）。(结点的指针域为next)
加载更多
[综合题]
1. 有一棵树如图所示，回答下面问题：
[综合题]
2. 由如图所示的二叉树，回答以下问题：
[综合题]
3. 以给定权重值1,2,12,13,20,25为叶结点,建立一棵哈夫曼树。
[综合题]
4. 以4,5,6,13,11,12作为叶结点的权,构造一棵哈夫曼树。
[综合题]
5. 以3，4，5，8，9，作为叶结点的权，构造一棵哈夫曼树。该树的带权路径长度为（）
[综合题]
6. 以3,4,5,8,9,作为叶结点的权,构造一棵哈夫曼树。
[综合题]
7. 以3,4,5,8,9,10作为叶结点的权,构造一棵哈夫曼树。
[综合题]
8. 以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树。权重值为4的叶结点的哈夫曼编码为（）
[综合题]
9. 以2,3,4,7,8,9作为叶结点的权,构造一棵哈夫曼树。
[综合题]
10. 以2,3,4,7,8,9作为叶结点的权,构造一棵哈夫曼树(要求每个结点的左子树根结点的权
[综合题]
11. 以1,2,3,6,7,8作为叶结点的权,构造一棵哈夫曼树是如下哪个图？
[综合题]
12. 以1,2,3 ,6,7,8作为叶结点的权,构造一棵哈夫曼树是如下哪个图？（）。
[综合题]
13. 已知一个无向图的邻接矩如下所示,写出从顶点0出发按深度优先搜索遍历得到的顶点序列。
[综合题]
14. 已知序列(70,83,100,105,10,32,7,9),请写出对此序列采用插入排序法进行升序排序时各趟的结果。
[综合题]
15. 已知序列(17,18,60,40,7,32,73,65,85)请给出采用冒泡排序法对该序列作升序排列时的每一趟结果。
[综合题]
16. 已知序列(10,18,4,3,6,12,1,9,15,8),请写出对此序列采用归并排序法进行升序排序时各趟的结果。
[综合题]
17. 已知无向图G描述如下：
[综合题]
18. 已知图G的邻接矩阵如下所示：从顶点1出发的广度优先搜索序列为（）。
[综合题]
19. 已知某二叉树的先序遍历序列是aecdb,中序遍历序列是eadcb,试画出该二叉树。
[综合题]
20. 已知某二叉树的先序遍历结果是：A,B,D,G,C,E,H,L,I,K,M,F和J,它的中序遍历结果是：G,D,B,A,L,H,E,K,I,M,C,F和J,请画出这棵二叉树,并写出该二叉树后续遍历的结果。
[综合题]
21. 已知某二叉树的后序遍历序列是febch.给出该二叉树的根结点？
[综合题]
22. 已知某带权图的邻接矩阵如下所示：
[综合题]
23. 一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序的方法建立的初始堆为（）（堆顶元素是最小元素,采用树的形式建堆）。
[综合题]
24. 一组记录的关键字序列为（45，40，65，43，35，95），利用快速排序的方法，以第一个记录为基准得到的一趟划分的结果为（）。
[综合题]
25. 一组记录的关键字序列为（42，37，62，40，32，92），利用快速排序算法，以第一个关键字为分割元素，经过一次划分后结果为（）。
[综合题]
26. 一组记录的关键字序列为{6,9,7,4,5,8}，利用堆排序（堆顶元素是最小元素）的方法建立初始堆是如下哪个图？（）
[综合题]
27. 一组记录的关键字序列为{6,9,7,4,5,8},利用堆排序(堆顶元素是最小元素)的方法建立初始堆。(要求用完全二叉树表示)
[综合题]
28. 一组记录的关键字序列为{47,80,57,39,41,46,48},
[综合题]
29. 一组记录的关键字序列为{46,79,56,38,40,84}
[综合题]
30. 一组记录的关键字序列为{45,40,65,43,35,95}写出利用快速排序的方法,
加载更多
[程序选择填空题]
1. 在下面空格处填写一条语句，以使下面的循环队列出队算法完整。
[程序选择填空题]
2. 在下面空格处填写一条语句，以使下面的顺序队列入队算法完整。
[程序选择填空题]
3. 在下面空格处填写一条语句，以使下面的进栈算法完整。void Push(struct SeqStack*s,ElemType x)
[程序选择填空题]
4. 在下面空格处填写一条语句，以使下面的串连接算法完整。
[程序选择填空题]
5. 在下面空格处填写一条语句，以使下面的串复制算法完整。
[程序选择填空题]
6. 在下面空格处填写一条语句，以使下面的串比较算法完整。
[程序选择填空题]
7. 在下面空格处填写一条语句，以使下面的出栈算法完整。ElemType Pop(struct SeqStack*s,ElemType x)
[程序选择填空题]
8. 在下面空格处填写一条语句,以使下面的循环队列入队算法完整。
[程序选择填空题]
9. 在下面空格处填写一条语句,以使下面的循环队列入队算法完整。
[程序选择填空题]
10. 在下面空格处填写一条语句,以使下面的链式队列全部元素出队的算法完整。
[程序选择填空题]
11. 在下面空格处填写一条语句,以使下面的进栈算法完整。
[程序选择填空题]
12. 在下面空格处填写一条语句,以使下面的串连接算法完整。 char *strcat(char *s1,char *s2) {
[程序选择填空题]
13. 在下面空格处填写适当的语句，以使下面的循环队列的入队和出队算法完整。define MAXSIZE 100;
[程序选择填空题]
14. 以下直接插入排序算法对存放在a[0],a[1],•••,a[n-1]中，长度为n的记录序列按关键字key由小到大排序。void disort (NODE a[ ], int n)
[程序选择填空题]
15. 以下为求二叉树深度的算法,完成程序中空格部分。
[程序选择填空题]
16. 以下是中序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。
[程序选择填空题]
17. 以下是用尾插法建立带头结点且有n个结点的单向链表的程序,结点中的数据域从前向后依次为1,2,3,……,n,完成程序中空格部分。
[程序选择填空题]
18. 以下是冒泡排序算法对存放在a[1],a[2],...,a[n]中序列按关键字key由小到大排序，完成程序中空格部分。
[程序选择填空题]
19. 以下是采用选择排序对10个数按照从小到大排列的代码,(1)处应该是（）。
[程序选择填空题]
20. 以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行排序，其中n是元素个数，要求按升序排列。void bsort (NODE a[ ], int n)
[程序选择填空题]
21. 以下利用直接插入排序算法对存放在a[0],a[1],...,a[n-1]中,长度为n的记录序列按关键字key由小到大排序,完成程序中空格部分。
[程序选择填空题]
22. 以下函数在head为头指针的具有头结点的单向链表中删除第i个结点,
[程序选择填空题]
23. 以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格选项。
[程序选择填空题]
24. 以下函数在a[0]到a[n-1]中,用折半查找算法查找关键字等于k的记录,查找成功区回该记录的下标,失败时返回-1,完成程序中的空格。
[程序选择填空题]
25. 以下函数在a[0]到a[n-1]中,用折半查找算法查找关键字等于k的记录,查找成功返回该记录的下标,失败时返回-1,完成程序中的空格选项。
[程序选择填空题]
26. 以下函数为直接选择排序算法，对a[1],a[2],…a[n]中的记录进行直接选择排序。typedef struct
[程序选择填空题]
27. 以下函数为链队列的入队操作,x为要入队的结点的数据域的值,front、rear分别是链队列的队头、队尾指针
[程序选择填空题]
28. 以下程序是中序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。
[程序选择填空题]
29. 以下程序是中序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中,左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。
[程序选择填空题]
30. 以下程序是折半插入排序的算法，设待排序的记录序列存放在a[1],…a[n]中，以a[0]作为辅助工作单元，程序是要把a[i] 插入到已经有序的序列a[1],…a[i-1]中。 void binsort (NODE a[ ],int n)
加载更多