山东开放大学数据结构期末考试复习题及参考答案.pdf

《山东开放大学数据结构期末考试复习题及参考答案.pdf》由会员分享，可在线阅读，更多相关《山东开放大学数据结构期末考试复习题及参考答案.pdf（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构期末考试复习题 注：找到所考试题直接看该试题所有题目和答案即可。查找按键：Ctrl+F 超越高度 一、单选题 1、当两个元素出现逆序的时候就交换位置，这种排序方法称为（）。A、插入排序 B、交换排序 C、选择排序 D、归并排序 正确答案：B 2、有关线性表的正确说法是（）。A、每个元素都有一个直接前驱和一个直接后继 B、线性表至少要求一个元素 C、表中的元素必须按由小到大或由大到下排序 D、除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继 正确答案：D 3、在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是（）。A、希尔排序 B、冒泡排序 C、插入

2、排序 D、选择排序 正确答案：D 4、串是（）。A、不少于一个字母的序列 B、任意个字母的序列 C、不少于一个字符的序列 D、有限个字符的序列 正确答案：D 5、向顺序栈中压入新元素时，应当（）。A、先移动栈顶指针，再存入元素 B、先存入元素，再移动栈顶指针 C、先后次序无关紧要 D、同时进行 正确答案：A 6、有一个长度为 10 的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。A、29/10 B、31/10 C、26/10 D、29/9 正确答案：A 7、已知一个有序表为11,22,33,44,55,66,77,88,99，则顺序查找元素 55 需要比较（）次

3、。A、3 B、4 C、5 D、6 正确答案：C 8、从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（）A、插入排序 B、选择排序 C、交换排序 D、归并排序 正确答案：A 9、对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（）。A、n B、e C、2n D、2e 正确答案：D 10、在一个栈顶指针为 top 的链栈中，将一个 p 指针所指的结点入栈，应执行（）。A、top-next=p;B、p-next=top-next;top-next=p;C、p-next=top;top=p;D、p-

4、next=top-next;top=top-next;正确答案：C 11、在一个链队中，假设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的运算为（）。A、f-next=s;f=s;B、r-next=s;r=s;C、s-next=r;r=s;D、s-next=f;f=s;正确答案：B 12、一个队列的入队序列是 1，2，3，4。则队列的输出序列是（）。A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 正确答案：B 13、带头结点的链表为空的判断条件是（）（设头指针为 head）。A、head=NULL B、head-next=NULL C、head-ne

5、xt=head D、head!=NULL 正确答案：B 14、在一个单链表中 p 所指结点之后插入一个 s 所指的结点时，可执行（）。A、p-next=s;snext=pnext B、p-next=snext;C、p=s-next；D、s-next=p-next;p-next=s;正确答案：D 15、一个队列的入队顺序是 a,b,c,d，则离队的顺序是（）。A、a,d,c,b B、a,b,c,d C、d,c,b,a D、c,b,d,a 正确答案：B 16.数据结构中，与所使用的计算机无关的是数据的（）。A.存储结构 B.物理结构 C.逻辑结构 D.物理和存储结构 正确答案：C 17.已知一个有

6、序表为11,22,33,44,55,66,77,88,99，则顺序查找元素 55 需要比较（）次。A.3 B.4 C.5 D.6 正确答案：C 18.图的深度优先遍历算法类似于二叉树的（）遍历。A.先序 B.中序 C.后序 D.层次 正确答案：A 19.常对数组进行的两种基本操作是（）。A.建立与删除 B.索引和修改 C.查找和修改 D.查找与索引 正确答案：C 20.若串 S=“English”，其子串的个数是（）。A.9 B.16 C.36 D.28 正确答案：D 二、填空题 1、哈夫曼树又称为 正确答案：第 1 空:最优二叉树 2、结点的度是指结点所拥有的 。正确答案：第 1 空:子树数

7、目或后继结点数 3、图常用的两种存储结构是 和 。正确答案：第 1 空:邻接矩阵 第 2 空:邻接表 4、将树中结点赋上一个有着某种意义的实数，称此实数为该结点的 。正确答案：第 1 空:权 5、在一个带权图中，两顶点之间的最段路径最多经过 条边。正确答案：第 1 空:n-1 6、关键字是记录某个 ，用它可以识别、确定一个记录。正确答案：第 1 空:数据项的值 7、广义表 A（a,b,c）,(d,e,f)）的表尾为 。正确答案：第 1 空:（d,e,f）8、循环队列队头指针在队尾指针 位置，队列是“满”状态 正确答案：第 1 空:下一个 9、查找是一种最简单的查找方法。正确答案：第 1 空:顺

8、序 10、为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为 。正确答案：第 1 空:栈 11、树中度大于 0 的结点称作 或 。答案：(1)分支结点(2)非终端结点 12、在队列的顺序存储结构中，当插入一个新的队列元素时，尾指 ，当删除一个元素队列时，头指针 。答案：(1)增 1(2)增 1 13、具有 m 个叶子结点的哈夫曼树共有 结点。答案：(1)2m-1 14、冒泡排序是一种比较简单的 方法。答案：(1)交换排序 15、在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种 的关系 答案：(1)多对多 三、简答题 1、简述栈和一般线性表的区别 正

9、确答案：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。2、写出以下运算式的后缀算术运算式:(A+B)*C-D/(E+F)+G 正确答案：AB+C*DEF+/-G+3、编写顺序查找算法。顺序查找算法如下：int search(NODE a,int n,int k)/*在 a0an-1中顺序查找关键字等于 k 的记录。查找成功时返回该记录的下标，失败时返回-1*/int search(NODE a,int n,int k)/*在 a0an-1中顺序查找关键字等于 k 的记录。查找成功时返回该记录的下标，失败时返回-1*/int

10、 i=0;while(i0)个元素 a1,a2ai an 的有限序列，其中 ai 或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当 ai 都是原子时，广义表退化成线性表。四、资料题 1、已知无向图 G 描述如下：G=（V，E）V=V1，V2，V3，V4，V5 E=（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）（1）画出 G 的图示；（2）然后给出 G 的邻接矩阵和邻接表；（3）写出每个顶点的度。正确答案：第 1 空:G 的图示 第 2 空:第 3 空:V1、V2、

11、V3、V4、V5 的度分别为：2，3，2，3，2 2、下面函数的功能是返回二叉树 BT 中值为 X 的结点所在的层号，请在划有横线的地方填写合适内容。int NodeLevel(struct BinTreeNode*BT,char X)if(BT=NULL)return 0;/*空树的层号为 0*/else if(BT-data=X)return 1;/*根结点的层号为 1*/*向子树中查找 X 结点*/else int c1=NodeLevel(BT-left,X);if(c1=1)_(1)_;int c2=_(2)_ _;if _(3)_;/若树中不存在 X 结点则返回 0 else re

12、turn 0;正确答案：第 1 空:return c1+1 第 2 空:NodeLevel(BT-right,X)第 3 空:(c2=1)return c2+1 2022 学年 9 月份考试数据结构复习题 一、单选题 1、数据结构中，与所使用的计算机无关的是数据的（）。A、存储结构 B、物理结构 C、逻辑结构 D、物理和存储结构 正确答案：C 2、在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是（）。A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序 正确答案：D 3、在一个单链表中，p、q 分别指向表中两个相邻的结点，且 q 所指结点是 p 所指结点的直接后继，现要删除 q

13、 所指结点，可用语句（）。A、p=q-next B、p-next=q C、p-next=q-next D、q-next=NULL 正确答案：C 4、已知一个有序表为11,22,33,44,55,66,77,88,99，则顺序查找元素 55 需要比较（）次。A、3 B、4 C、5 D、6 正确答案：C 5、从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（）A、插入排序 B、选择排序 C、交换排序 D、归并排序 正确答案：A 6、图的深度优先遍历算法类似于二叉树的（）遍历。A、先序 B、中序 C、后序 D、层次 正确答案：A 7、二叉树第

14、k 层上最多有（）个结点。A、2k B、C、-1 D、2 正确答案：B 8、常对数组进行的两种基本操作是（）。A、建立与删除 B、索引和修改 C、查找和修改 D、查找与索引 正确答案：C 9、若串 S=“English”，其子串的个数是（）。A、9 B、16 C、36 D、28 正确答案：D 10、一个队列的入队顺序是 a,b,c,d，则离队的顺序是（）。A、a,d,c,b B、a,b,c,d C、d,c,b,a D、c,b,d,a 正确答案：B 11、设有一个长度为 n 的顺序表，要删除第 i 个元素移动元素的个数为（）。A、n-i+1 B、n-i C、n-i-1 D、i 正确答案：B 12

15、、顺序查找方法适合于存储结构为（）的线性表。A、散列存储 B、索引存储 C、散列存储或索引存储 D、顺序存储或链接存储 正确答案：D 13、利用 3、6、8、12 这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为()。A、18 B、16 C、12 D、30 正确答案：A 14、设某一二叉树先序遍历为 abdec，中序遍历为 dbeac，则该二叉树后序遍历的顺序是（）。A、abdec B、debac C、debca D、abedc 正确答案：C 15、下列有关二叉树的说法正确的是（）。A、二叉树中度为 0 的结点的个数等于度为 2 的结点的个数加 1 B、二叉树中结

16、点个数必大于 0 C、完全二叉树中，任何一个结点的度，或者为 0 或者为 2 D、二叉树的度是 2 正确答案：A 16、算法的时间复杂度与（）有关。A、所使用的计算机 B、计算机的操作系统 C、算法本身 D、数据结构 正确答案：C 17、算法分析的目的是（）。A、找出数据结构的合理性 B、研究算法中的输入和输出的关系 C、分析算法的效率以求改进分析算法的易懂性和文档性 D、分析算法的易懂性和文档性 正确答案：C 18、链表不具有的特点是（）。A、可随机访问任一元素 B、插入删除不需要移动元素 C、不必事先估计存储空间 D、所需空间与线性表长度成正比 正确答案：A 19、在图的存储结构表示中，表

17、示形式唯一的是（）。A、n B、n+1 C、n-1 D、n/2 正确答案：C 20、对于顺序存储的有序表5，12，20，26，37，42，46，50，64，若采用折半查找，则查找元素 26 的比较次数是（）。A、2 B、3 C、4 D、5 正确答案：C 21、以下陈述中正确的是（）。A、串是一种特殊的线性表 B、串的长度必须大于零 C、串中元素只能是字母 D、空串就是空白串 正确答案：A 22、设有两个串 p 和 q，其中 q 是 p 的子串，q 在 p 中首次出现的位置的算法称为（）。A、求子串 B、连接 C、匹配 D、求串长 正确答案：C 23、串是（）。A、不少于一个字母的序列 B、任意个字母的序列 C、不少于一个字符的序列 D、有限个字符的序列 正确答案：D 解析：24、串的长度是指（）。A、串中所含不同字母的个数 B、串中所含字符的个数 C、串中所含不同字符的个数 D、串中所含非空格字符的个数 正确答案：B 25、两个字符串相等的条件是（）。A、两串的长度相等 B、两串包含的字符相同 C、两串的长度相等，并且两串包含的字符相同 D、两串的长度相等，并且对应位置上的字符相同 正确答案：D 二、填空题 1、树中度大于 0 的结点称作 或 。正确答案：第 1 空:分支结点 第 2 空: