山东开放大学数据结构期末考试复习题及参考答案.docx
《山东开放大学数据结构期末考试复习题及参考答案.docx》由会员分享,可在线阅读,更多相关《山东开放大学数据结构期末考试复习题及参考答案.docx(18页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 山东 开放 大学 数据结构 期末考试 复习题 参考答案
限制150内