厦门理工-数据结构c语言版期末考试复习试题.pdf

该【厦门理工-数据结构c语言版期末考试复习试题 】是由【青山代下】上传分享，文档一共【13】页，该文档可以免费在线阅读，需要了解更多关于【厦门理工-数据结构c语言版期末考试复习试题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..厦门理工《数据结构与算法》复****题一、选择题。,从逻辑上可以把数据结构分为C。。,与所使用的计算机无关的是数据的A结构。,通常不仅要存储各数据元素的值,而且还要存储C。,一般不考虑A。。。,算法分析的两个主要方面是A。(1)(2)(n2)。s=0;for(I=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;(n*m)。for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;1:..(logn)。3i=0;while(i<=n)i=i*3;,正确的是B。,这意味着B。,。。==NULLBhead->next==->next==headDhead!=。==NULLBhead->next==->next==headDhead!=,则采用D存储方式最节省运算时间。,插入和删除不需要移动元素的线性表,其存储结构是B。(由p所指向)满足C。->next====->next====。->prior=s;s->next=p;p->prior->next=s;s->prior=p->->prior=s;p->prior->next=s;s->next=p;s->prior=p->->next=p;s->prior=p->prior;p->prior=s;p->prior->next=->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s2:..,则采用D存储方式最节省时间。。(1)(n)(n2)(nlog2n)(n>1)的单链表上,设有头和尾两个指针,执行B操作与链表的长度有关。,双链表的优点之一是D。、,即删除第一个元素,在最后一个元素的后面插入新元素,则最好使用B。(1≤i≤n+1),元素的移动次数为:A。–i+––、尾两端进行插入操作的线性表,宜采用的存储结构为C。?C。,错误的是哪一个?B。A线性表采用顺序存储,必须占用一片连续的存储单元B线性表采用顺序存储,便于进行插入和删除操作。C线性表采用链式存储,不必占用一片连续的存储单元D线性表采用链式存储,便于进行插入和删除操作。。:..,算法的时间复杂度是O(1)的操作是A。(1<=i<=n)个结点和求第i个结点的直接前驱(1<i<=n)(1<=i<=n)(1<=i<=n),在其第i个位置插入一个新元素的算法的时间复杂度为C。(0)(1)(n)(n2),访问结点和增加、删除结点的时间复杂度为C。(n)O(n)(n)O(1)(1)O(n)(1)O(1)(a1,a2,…,an)以链式方式存储,访问第i位置元素的时间复杂度为C。(0)(1)(n)(n2),增加一个头结点的目的是为了C。,正确的操作是B。->next=s;s->next=p->->next=p->next;p->next=s;->next=s;p->next=s->->next=s->next;p->next=。,队列的特点是A。。,b,c,d,e,则栈的不可能的输出序列是C。,元素依次进栈的顺序为A、B、C、D、E。下列C是不可能的出栈序列。,B,C,D,,C,D,E,,A,B,C,,D,C,B,?:..,2,3,,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为C。--i+(最多元素为MaxSize)为空的条件是B。->top!=-->top==-->top!=->top==(最多元素为MaxSize)为满的条件是D。->top!=-->top==-->top!=->top==,2,3,4,则队列的输出序列是B。,3,2,,2,3,,4,3,,2,4,(最多元素为MaxSize)为空的条件是C。->rear–qu->front==->rear–qu->front-1==->rear==qu->->rear=qu->front-,若front与rear分别表示对头元素和队尾元素的位置,则判断循环队列空的条件是C。==rear+==front+====,应执行D操作。->next=s;->next=h;->next=h;h=s;->next=h->next;h->next=s;,可以变为CBA时,经过的栈操作为B。,pop,push,pop,push,,push,push,pop,pop,,push,pop,pop,push,,pop,push,push,pop,,现两栈共享空间V[1m],top[1]、top[2]分别代表第1和第2个栈的栈顶,栈1的底在V[1],栈2的底在V[m],则栈满的条件是B。A.|top[2]-top[1]|=[1]+1=top[2][1]+top[2]=[1]=top[2]、右括号是否配对出现的算法,采用D数据结构最佳。。。:..,且当前rear和front的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为B。“先进先出”特性是指D。、删除操作时,,,链栈有一个比较明显的优势是A。,其头指针指向队头结点,尾指针指向队尾结点,则在进行出队操作时C。、、=‘software’,其子串的数目是B。。,其特殊性体现在B。,求q在p中首次出现的位置的运算称为B。,每个元素的长度为3个字节,行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放的存储器内,该数组按行存放,元素A[8][5]的起始地址为C。++++,每个元素的长度为3个字节,行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放的存储器内,该数组按行存放,元素A[5][8]的起始地址为C。++++:froataverage[]=newfloat[30];假设该数组的内存起始位置为200,average[15]的内存地址是C。:..[1…m,1…n]按行存储在数组B中,则二维数组元素A[i,j]在一维数组B中的下标为A。*(i-1)+*(i-1)+j-*(j-1)*m+i-×90的稀疏矩阵,非0元素有10,设每个整型数占2个字节,则用三元组表示该矩阵时,所需的字节数是B。[0…4,-1…-3,5…7]中含有的元素个数是A。。,采用压缩存储方式,以行序为主存储,a为第一个元素,其存储地址1,1为1,每个元素占1个地址空间,则a的地址为B。8,,即C。。。,m个叶子,n个结点,深度为h,则D。=h+mBh+m=2nCm=h-1Dn=2h-、中序和后序遍历序列中的相对次序A。,每个结点必须设置一个标志来说明它的左、右链指向的是树结构信息,还是线索化信息,若0标识树结构信息,1标识线索,对应叶结点的左右链域,应标识为__D__。,正确的是D。①只有一个结点的二叉树的度为0;②二叉树的度为2;③二叉树的左右子树可任意交换;④深度为K的顺序二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.②③④C.②④D.①④7:..,它有m个结点,B的根为p,p的右子树的结点个数为n,森林F中第一棵树的结点的个数是A。--n-+,5个度为1的结点,则度为0的结点的个数是B。。,所有顶点的度数之和等于所有边数的C倍。,所有顶点的入度之和等于所有顶点的出度之和的B倍。,后序序列为BDCAFGE,则其左子树中结点数目为:+B*C–D/E,后缀形式为ABC*+DE/–,其前缀形式为D。A.–A+B*C/DEB.–A+B*CD/EC–+*ABC/DED.–+A*BC/,如图所示,若从顶点a出发按深度搜索法进行遍历,则a可能得到的一种顶点序列为____D___;按广度搜索法进行遍历,则可能得到的一种顶点序列为___A___;bec①,b,e,c,d,,c,f,e,b,,e,b,c,f,d,,e,d,f,c,bdf②,b,c,e,d,,b,c,e,f,,e,b,c,f,d,,c,f,d,e,。。。-(n-1)/((a),a)的表头是C,表尾是C。()C(a)D((a))((a))的表头是C,表尾是B。()C(a)D((a))8:..。,要求线性表必须B。A以顺序方式存储B以顺序方式存储,且结点按关键字有序排列C以链式方式存储D以链式方式存储,,每个元素的平均查找长度为D。AO(n2)BO(nlogn)CO(n)DO(logn){1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值为82的结点时,C次比较后查找成功。、小于其右孩子的值。这种说法B。+树的叙述中,不正确的结论是A。AB树和B+树都能有效的支持顺序查找BB树和B+树都能有效的支持随机查找CB树和B+树都是平衡的多叉树DB树和B+。,不包含指针。,它反映了散列表的饱满程度。。。。。。。,从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为C。。冒泡排序C插入排序D。,关键字比较的次数与记录的初始排列次序无关的是D。。下列关键码序列D是一个堆。,31,53,23,16,,53,31,72,16,,53,23,94,31,,31,23,94,53,729:..101B排序。。。(n为元素个数)(n)(logn)(nlogn)(n2)22二、填空题。、树形结构和图状结构三种类型,树形结构和图状结构合称非线性结构。、线性结构、树形结构和图状结构4种。,第一个结点没有前驱结点,其余每个结点有且只有1个前驱结点;最后一个结点没有后续结点,其余每个结点有且只有1个后续结点。,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。,树根结点没有前驱结点,其余每个结点有且只有1个前驱结点;叶子结点没有后续结点,其余每个结点的后续结点可以任意多个。、链式、索引和散列存储。、可读性、健壮性和时间复杂度与空间复杂度。,通常从时间复杂度和空间复杂度两个方面考察。、确定性、可行性、输入和输出。,需向前移动n-i-1个元素。,要删除某一指定的结点,必须找到该结点的前驱结点。,每个结点有两个指针域,一个指向前驱结点,另一个指向后继结点。,需要平均移动n个数据元素,移动数据元素的个数与位置有关。,且很少进行插入和删除操作,但要求以最快的速度存取线性表的元10:..顺序存储结构。,将线性链表分成单链表和双链表。;链式存储结构是通过指针表示元素之间的关系的。->next->next=L。.栈是限定仅在表尾进行插入或删除操作的线性表,其运算遵循后进先出的原则。,其长度等于零。空白串是由一个或多个空格字符组成的串,其长度等于其包含的空格个数。。。”在主串”datastructure”中的位置是5。,行下标i的范围从0到8,列下标j的范围从1到10,则存放M至少需要540个字节;M的第8列和第5行共占108个字节。,即三元组表和十字链表。((a),((b),c),(((d))))的长度是3,深度是4。,度为零的结点的个数为n0,度为2的结点的个数为n2,则有n0=n2+1。,空链域的个数为__n+1__。-1_个结点。。,有30个结点仅有一个孩子,则该二叉树的总结点个数为69。,中序序列是dgbaechf,其后序序列为gdbehfca。,右线索指向其遍历序列中的后继。,平均查找长度与结点个数n无关的查找方法是散列查找法。11:..34索引表,然后查找相应的块表。,构造树的过程即为对无序序列进行排序的过程。,边的总数最多为__45__。,其从顶点v1出发的深度优先搜索序列为_v1v2v3v6v5v4_,其从顶点v1出发的广度优先搜索序列为_v1v2v5v4v3v6__。vvv∧1254vvv∧235vv∧36v4∧vvvv∧5463v6∧。一个索引隶属于某个数据记录集,它由若干索引项组成,索引项的结构为关键字和关键字对应记录的地址。-1,当前选择的边的权值是候选边中最小的,选中的边加入树中不产生回路三项原则。,除根结点外,每个结点最多有m棵子树,最少有m/2棵子树。三、判断题。,一般不考虑各结点的值如何。(√)(ADT)包括定义和实现两方面,其中定义是独立于实现的,定义仅给出一个ADT的逻辑特性,不必考虑如何在计算机中实现。(√)。(√),因此它不如链式存储方式好。(×),结点和结点内部的存储空间可以是不连续的。(×)。(×)。(×)。(×)。(×)。(×)。(×)。(×),进行插入、删除操作时,在链表中比在顺序表中效率高。(√)。(×)12:..15p,则可用下述语句将新结点s插入结点p的后面:p->next=s;s->next=p->next;(×),是一种先进后出的结构。(×)串是一种特殊的线性表,其特殊性体现在可以顺序存储。(×)。(×)。(×),存取时间越长。(×),在不考虑压缩存储的情况下,所占用的存储空间大小只与图中结点个数有关,而与图的边数无关。(√)。(×)。(√)(((a),b),c)的表头是((a),b),表尾是(c)。(√),任意一个结点均处在其孩子结点的后面。(√)。(×),任意一个结点均处在其孩子结点的前面。(√),总是以前序遍历顺序存储结点。(×),则可以恢复该二叉树。(×),权值最小的结点离根结点最近。(×)。(√),从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点。(×),存在多个具有相同键值的记录,若经过排序,这些记录的相对次序仍然保持不变,称这种排序为稳定排序。(√),任意结点左右子树的高度差(绝对值)不超过1。(√)。(×)。(×),要求线性表必须以链式方式存储,且结点按关键字有序排列。(×)。(√)、小于其右孩子的值。(×),其中树高最小的二叉排序树是最佳的。(√)(n)。(×)13