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

《山东开放大学数据结构期末考试复习题及参考答案.docx》由会员分享，可在线阅读，更多相关《山东开放大学数据结构期末考试复习题及参考答案.docx（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

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

3、：C21、以下陈述中正确的是（）oA、串是一种特殊的线性表B、串的长度必须大于零C、串中元素只能是字母D、空串就是空白串正确答案：A22、设有两个串p和q,其中q是p的子串，q在p中首次出现的位置的算法称为（）。A、求子串B、连接C、匹配D、求串长正确答案：C23、串是（）oA、不少于一个字母的序列B、任意个字母的序列C、不少于一个字符的序列D、有限个字符的序列正确答案：D解析：24、串的长度是指（）oA、串中所含不同字母的个数B、串中所含字符的个数C、串中所含不同字符的个数D、串中所含非空格字符的个数正确答案：B25、两个字符串相等的条件是（）oA、两串的长度相等B、两串包含的字符相同C、两

4、串的长度相等，并且两串包含的字符相同D、两串的长度相等，并且对应位置上的字符相同正确答案：D二、填空题1、树中度大于。的结点称作 或 。正确答案：第1空：分支结点第2空：非终端结点2、哈夫曼树又称为正确答案：第1空：最优二叉树3、在一棵树中，每个结点的子树的根或者说每个结点的称为该结点的孩子结点，简称为孩子。正确答案：第1空：后继结点4、树中度等于。的结点称作或 。正确答案：第1空：叶子结点第2空：终端结点5、图常用的两种存储结构是和 。正确答案：第1空：邻接矩阵第2空：邻接表6、在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 ，当删除一个元 素队列时，头指针 。正确答案：第1空：增

5、1第2空：增17、在对一组记录(50, 40, 95, 20, 15, 70, 60, 45, 80)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需要比较次。正确答案：第1空：38、关键字是记录某个，用它可以识别、确定一个记录。正确答案：第1空：数据项的值9、具有m个叶子结点的哈夫曼树共有结点。正确答案：第1空：2m-l10、串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是。正确答案：第1空：字符11、在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以 用操作正确答案：第1空：q-next=p-next12、冒泡排序是一种比较简单的方法。

6、正确答案：第1空：交换排序13、单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点 的指针域由空指针改为 ；当单向链表不带头结点时，则把单向链表中尾结点的指针域由 空指针改为指向 。正确答案：第1空：头结点的指针第2空：指向第一个结点的指针14、在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种 的 关系正确答案：第1空：多对多15、数据结构中的数据元素存在多对多的关系称为结构。正确答案：第1空：图状结构;图结构16、分块查找又称为，它是一种介于顺序查找和折半查找之间的查找方法。正确答案：第一空：索引顺序查找17、在有序表A1.18中，采用二分查找

7、算法查找元素值等于A1刀的元素，所比较过的元 素的下标依次是。正确答案：第一空：9, 14, 16 , 1718、栈是限定在表的一端进行插入和删除操作的线性表，又称为 。正确答案：第一空：后进先出表19、在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 ，当删除一个元素 队列时，头指针。正确答案：第一空：增1第二空：增120广义表A (a,b,c) ,(df)的表尾为。正确答案：第一空：(d,e,f)三、简答题1、编写顺序查找算法。顺序查找算法如下：int search(NODE aJnt n, int k)/*在a0中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失败时 返

8、回-1*/)正确答案：顺序查找算法如下：int search(NODE a,int n, int k)/*在a0an-l中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失败时 返回-1*/(int i=0;while(idata=X) return 1; /*根结点的层号为 1*/*向子树中查找X结点*/else (int cl=NodeLevel(BT-left,X);if(cl=l) (1)；int c2=(2);if _0)；若树中不存在X结点则返回0else return 0;)正确答案：第一空：return cl+1第二空：NodeLevel(BT-right,X)第三空：

9、(c2=l) return c2+l2、阅读下面算法，在划线处填入正确的代码内容int write(LinkQueue *q)QueueNode *p;if (q-front=q-rear) /* 队空*/printf( underflow”)；exit(0);)while (q-front-next != NULL)p=q-front-next;(1) printf( 4d”，p-data);(2) )(3) ; /*队空时，头尾指针指向头结点*/)正确答案：第一空：q-front-next=p-next;第二空：free(p);第三空：q-rear=q-front一、单选题1、一维数组A采

10、用顺序存储结构，每个元素占用6个字节，第6个元素的存 储地址为100,则该数组的首地址是（）。A、 6428B、 7090答案：C2、下述几种排序方法中，平均情况下占用内存量最大的是（）方法。A、插入排序B、选择排序C、快速排序D、归并排序答案：D3、在数据结构中，从逻辑上可以把数据结构分为（）。A、 动态结构和静态结构紧凑结构和非紧凑结构B、 线性结构和非线性结构内部结构和外部机构答案：C4、在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（ 倍。A、 邻接矩阵表示法邻接表表示法B、 逆邻接表表示法邻接表和逆邻接表答案：B5、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查

11、找长度为 ()OnA、 n/2C、(n+l)/2D、(n-l)/2答案：c6、一个存储结点存储一个()。A、 数据项数据元素B、 数据结构数据类型答案：B7、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点 邻接表中的结点总数为()。A、nB、eC、2nD、2e答案：D8、 一个顺序表第一个元素的存储地址是90,每个元素的长度为2,则第6个元素的地址是（）。A、 98100B、 102106答案：B9、常对数组进行的两种基本操作是（）。A、 建立与删除索引和修改B、 查找和修改查找与索引答案：C10、在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（） 存储比较合适

12、。A、链式B、顺序C、堆结构D、无法确定 答案：A n、在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是（ ）。A、希尔排序B、冒泡排序C、插入排序D、选择排序答案：D12、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓 冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据 打印，该缓冲区应该是一个（）结构。A、 堆栈队列B、 数组线性表答案：B13、向顺序栈中压入新元素时，应当（）。A、 先移动栈顶指针，再存入元素先存入元素，再移动栈顶指针B、 先后次序无关紧要同时进行答案：A14、哈希函数有一个共同的性质，即函数值应当以（）取其值域的每个

13、值。A、 最大概率最小概率B、 平均概率同等概率答案：D15、算法分析的目的是()。A、 找出数据结构的合理性研究算法中的输入和输出的关系B、 分析算法的效率以求改进分析算法的易懂性和文档性分析算法的易懂性和文档性答案：C16、设二维数组A5 6按行优先顺序存储在内存中，已知A00起始地 址为1000,每个数组元素占用5个存储单元，则元素A44的地址为()O1140A、 11451120B、 1125答案：A17、在正常情况下，冒泡排序的时间复杂度为()。A、 0(log2n)0(n)C 0(n log2n)D、0(n2) 答案：DB、4C、5D、6正确答案：C8、从未排序序列中依次取出元素与

14、已经排好序的序列中的元素作比较。将其放入已排序序 列的正确的位置上，此方法称为（）A、插入排序B、选择排序C、交换排序D、归并排序正确答案：A9、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的 结点总数为（）oA、nB、eC、2nD、2e正确答案：D10、在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）。A、top-next=p;B、p-next=top-next; top-next=p;C、p-next=top; top=p;D、 p-next=top-next; top=top-next;正确答案：C11、在一个链队中，假设f和r分别为队

15、头和队尾指针，则插入s所指结点的运算为（）oA、f-next=s; f=s;B、r-next=s;r=s;C、s-next=r;r=s;D s-next=f;f=s;正确答案：B12、一个队列的入队序列是L 2, 3, 4o则队列的输出序列是（）oA、 4,3,2,11,2,3,4B、 1,4,3,23,2,4,1正确答案：B13、带头结点的链表为空的判断条件是（）（设头指针为head）。A、head = =NULLB、head-next= =NULLC head-next= =headD、head!=NULL正确答案：B14、在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）oA

16、、p-next= s; sanext= pa next18、在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删结点的值, 则执行（）。Ax=top;top=top-next;x=top-data;B、 top=top-next; x=top-data;Dx=top-data; top=top-next;答案：B19、以下陈述中正确的是（）。A、 串是一种特殊的线性表串的长度必须大于零B、 串中元素只能是字母空串就是空白串答案：A20、设有一个20阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以 行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素瓯2在一 维数组B中的下标

17、是（）41A、 3218B、 38答案：D二、填空题1、将树中结点赋上一个有着某种意义的实数，称此实数为该结点的 O答案：权2、分块查找又称为，它是一种介于顺序查找和折半查找之间的查 找方法。答案：索引顺序查找3、每个结点只包含一个指针域的线性表叫 o答案：单链表4、在一个单链表中p所指结点之后插入一个s所指结点时，应执行 和p-next=s;的操作。答案： s-next=p-next5、栈是限定在表的一端进行插入和删除操作的线性表，又称为 o答案：后进先出表6、在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针，当删除一个元素队列时，头指针。答案：增17、假设以S和X分别表示入栈和出栈

18、操作，则对输入序列a, b,c,d,e 一系列栈操作SSXSXSSXXX之后，得到的输出序列为 o答案：bceda8、空串的长度是 o答案：09、在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为 o （结点的指针域为next）答案： f=f-next10、在有序表A1.18中，采用二分查找算法查找元素值等于A17的元素,所比较过的元素的下标依次是 o答案：9,14,16 ， 1711、在对一组记录（50, 40, 95, 20, 15, 70, 60, 45, 80）进行直接插入排序时，当把第7个记录60插入到有序表时,为寻找插入位置需要比较 次o答案：312、向一个栈顶指针

19、为h的链栈中插入一个s所指结点时，可执行 和h二s;操作。（结点的指针域为next） 答案： s-next=h13、树中度等于0的结点称作 或答案：叶子结点终端结点14、广义表 A （ （a, b,c） , （d, e, f）的表尾为 。答案：（d,e,f）15、具有m个叶子结点的哈夫曼树共有 结点。答案：2m-1三、简答题1、头指针、头结点、第一个结点（或称首元结点）的区别是什么？答案：头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点） 是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头 结点或为首元结点）的指针。2、已知某二叉树的先序遍历结果是：A,

20、 B, D, G, C, E, II, L, I, K, M, F和 J,它的中序遍历结果是：G, D, B, A, L, H, E, K, I, M, C, F和J,请画出 这棵二叉树，并写出该二叉树后续遍历的结果。.答案：（1）二叉树图形表示如下：. ,(2)该二叉树后序遍历的结果是：G、D、B、L、H、K、四、资料题1、下列是在具有头结点单向列表中删除第i个结点 语句。int delete(NODE *head, int i)NODE *p,*q;int j;q=head;j=0;while(q! =NULL)&(j找到要删除结点的直接前驱，q=q-next;j+；M、 I、 E、 J、

21、 F、 C 和 A。,请在空格内填上适当的并使q指向它*/Aif (q=NULL)return (0);free (p);return (1);答案：第1空：p=q-next第2空：q-next=p-nextB、p-next=sanext;C、p=s-next；D、s-next=p-next; p-next=s;正确答案：D15、一个队列的入队顺序是a,bed,则离队的顺序是（）。A、a,d,c,bB、a,b,c,dC、d,c,b,aD、cbda正确答案：B16.数据结构中，与所使用的计算机无关的是数据的（）。A.存储结构B.物理结构C.逻辑结构D.物理和存储结构正确答案：C.已知一个有序表为

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

23、：邻接表4、将树中结点赋上一个有着某种意义的实数，称此实数为该结点的。正确答案：第1空：权5、在一个带权图中，两顶点之间的最段路径最多经过条边。正确答案：第1空：n-16、关键字是记录某个，用它可以识别、确定一个记录。正确答案：第1空：数据项的值7、广义表A (a,b,c) z(dzezf)的表尾为。正确答案：第1空：(d,e,f)8、循环队列队头指针在队尾指针位置，队列是“满”状态正确答案：第1空：下一个9、查找是一种最简单的查找方法。正确答案：第1空：顺序10、为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为 。正确答案：第1空：栈11、树中度大于。的结点称作或

24、。答案：分支结点非终端结点12、在队列的顺序存储结构中，当插入一个新的队列元素时，尾指，当删除一个元素队 列时，头指针。答案：增1增113、具有m个叶子结点的哈夫曼树共有结点。答案：(l)2m-l14、冒泡排序是一种比较简单的 方法。答案：交换排序15、在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种的关系答案：(1)多对多三、简答题1、简述栈和一般线性表的区别正确答案：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以 在线性表的任何位置进行插入和删除操作。2、写出以下运算式的后缀算术运算式XA+B)*C-D/(E+F)+G正确答案：AB+

25、C*DEF+/-G+3、编写顺序查找算法。顺序查找算法如下：int search(NODE a,int n, int k)/*在a0an-l中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失败时 返回-1*/)int search(NODE a,int n, int k)/*在a0an.l中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失败时 返回-1*/int i=0;while(i0)个元素al,a2aian的有限序列，其中ai或者是 原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性 表可以看成广义表的特殊情况，当ai都是原子时，广义表退

26、化成线性表。四、资料题1、已知无向图G描述如下：G= (V, E)V=V1, V2, V3, V4, V5E= (VI, V2), (VI, V4), (V2, V4), (V3, V4), (V2, V5), (V3, V4), (V3, V5) (1)画出G的图示；(2)然后给出G的邻接矩阵和邻接表；(3)写出每个顶点的度。正确答案：第1空：G的图示0第2空：0第3空：VI、 V2、 73、V4、 V5 的度分别为：2, 3, 2, 3, 22、下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请在划有横线的地方填写 合适内容。int NodeLevel(struct BinTree

27、Node* BT, char X)(if(BT=NULL) return 0;/*空树的层号为 0*/else if(BT-data=X) return 1; /*根结点的层号为 1*/*向子树中查找X结点*/else int cl=NodeLevel(BT-left,X);if(cl=l) (1)；int c2=;if (3)；若树中不存在X结点则返回0else return 0;)正确答案：第1空：return cl+1第2空：NodeLevel(BT-right,X)第3空：(c2=l) return c2+l2022学年9月份考试数据结构复习题一、单选题1、数据结构中，与所使用的计算机

28、无关的是数据的（）oA、存储结构B、物理结构C、逻辑结构D、物理和存储结构正确答案：C2、在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是（）oA、希尔排序B、冒泡排序C、插入排序D、选择排序正确答案：D3、在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直 接后继，现要删除q所指结点，可用语句（）。A、p=q-nextB、p-next=qC、p-next=q-nextD、q-next=NULL正确答案：C4、已知一个有序表为11,22,33,44,55,66,77,88,99,则顺序查找元素55需要比较（）次。A、3B、4C、5D、6正确答案：C5、

29、从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（）A、插入排序B、选择排序C、交换排序D、归并排序正确答案：A6、图的深度优先遍历算法类似于二叉树的（）遍历。A、先序B、中序C、后序D、层次正确答案：A7、二叉树第k层上最多有（）个结点。A、2kB、C、-1D、2正确答案：B8、常对数组进行的两种基本操作是（）oA、建立与删除B、索引和修改C、查找和修改D、查找与索引正确答案：C9、若串S= English”,其子串的个数是（）oA、9B、16C、36D、28正确答案：D10、一个队列的入队顺序是a,b,c,d,则离队的顺序是（）oA、

30、a,d,c,bB、ahc,dC、d,c,b,aD、c,b,d,a正确答案：Bn、设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）oA、n-i+1B、n-iC、n-i-1D、i正确答案：B12、顺序查找方法适合于存储结构为（）的线性表。A、散列存储B、索引存储C、散列存储或索引存储D、顺序存储或链接存储正确答案：D13、利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的 最长带权路径长度为（）oA、18B、16C、12D、30正确答案：A14、设某一二叉树先序遍历为abdec,中序遍历为dbeac,则该二叉树后序遍历的顺序是（）oabdecA、 deb

31、acC debcaD、 abedc正确答案：C15、下列有关二叉树的说法正确的是（）oA、二叉树中度为0的结点的个数等于度为2的结点的个数加1B、二叉树中结点个数必大于0C、完全二叉树中，任何一个结点的度，或者为0或者为2D、二叉树的度是2正确答案：A16、算法的时间复杂度与（）有关。A、所使用的计算机B、计算机的操作系统C、算法本身D、数据结构正确答案：C17、算法分析的目的是（ ）oA、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进分析算法的易懂性和文档性D、分析算法的易懂性和文档性正确答案：C18、链表不具有的特点是（）。A、可随机访问任一元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正比正确答案：A19、在图的存储结构表示中，表示形式唯一的是（）oA、nB、n+1C、n-1D、n/2正确答案：C20、对于顺序存储的有序表5, 12, 20, 26, 37, 42, 46, 50, 64,若采用折半查找，则