还剩13页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构考试内部题库含答案解析(全考点)
1.以下属于逻辑结构的是():顺序表•A・哈希表•B:・:有序表•C・:单链表•D解析顺序表、哈希表和单链表是三种不同的数据结构,既描述逻辑结构,又描述存储结构和数据运算而有序表是指关键字有序的线性表,仅描述元素之间的逻辑关系,它既可以链式存储,又可以顺序存储,故属于逻辑结构答案C)
2、链式存储设计时,结点内的存储单元地址(・一定连续•A:・:一定不连续•B・不一定连续•C:・:部分连续,部分不连续•D答案B
2、从一个具有n个结点的单链表中检索其值等于x的结点时,在检索成功的情况下,需平均比较的结点个数是•A:n/2•B:n•C:n+l/2•D:n-l/2解析由于单链表只能进行单向顺序查找,以从第一个节点开始查找为例,查找第个节点需要比较的节点数,m fm=m查找成功的最好情况是第一次就查找成功,只用比较个节1点,最坏情况则是最后才查找成功,需要比较个节点所n以一共有种情况,平均下来需要比较的节点为n1+2+3+...+n-l+n/n=n+l/2答案C
3.当n足够大时,下述函数中渐近时间最小的是—o・•A:Tn=nlogn-1000logn.•B:Tn=nlog3-1000logn・•C:Tn=-lOOOIogn.•D:Tn=2nlogn-1000logn解析四个选项时间复杂度依次为、、ABCD0n0n、所以足够大时,时间复杂度最00n n no小的是选0n,Bo答案B
4.倒排文件包含有若干个倒排表,倒排表的内容是—o・一个关键字值和该关键字的记录地址•A:・:一个属性值和该属性的一个记录地址•B・:一个属性值和该属性的全部记录地址•C・:多个关键字和它们相对应的某个记录的地址•D解析有倒排索引的文件我们称为倒排索引文件,简称倒排文件倒排索引,也常被称为反向索引,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射倒排索引源于实际应用中需要根据属性的值来查找记录这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址答案C
5、下述编码中不是前缀码的是—o・•A:{0,10,110,111・•B:{0,1,00,11}・•C:{1,01,000,001・•D:{00,01,10,11}解析前缀编码是指对字符集进行编码时,要求字符集中任一字符的编码都不是其他字符的编码的前缀选项中和不符B00合前缀码要求答案B
6、下面程序段的时间复杂度是i=s=0;whilesni++;s+=i;•A:OlognB:oO••C:0n解析第一次执行完第二次第三次s+=i s=l s=3=l+2第四次第次s=6=1+2+3s=10=l+2+3+4k那么当=的时々房停止,也就l+2+3+4+...+k=L n是□所以复杂度是k=答案B
7、在有向图中每个顶点的度等于该顶点的—o:入读•A出度•B::入读与出度之和•C入读与出度之差•D:O\//\解析在有向图中每个顶点的度等于该顶点的入度与出度之和答案C
8、具有n个顶点的无向完全图有一条边・•A:n・•B:n*n-l/2・•C:n*n+l/2・•D:n*n/2解析具有个顶点的无向完全图有条弧n n*n-l/2答案B
9、下列程序段的时间复杂度是一ocount=0;fork=l;k=n;k*=2for j=l;j=n;j++count++;•A:0n•B:0nr™I•C:0n n•D:0ZJ解析内层循环条件与外层循环的变量无关,各自独立j=n每执行一次自增每次内层循环都执行次j1n外层循环条件,增量定义为可知循环k=n k*=2,I!■|次数满足即内层循环的t kJ=n,gp t=n时间复杂度为,外层循环的时间复杂度为0n0对于嵌入循环,根据乘法规则可知,该程序的时no间复杂度Tn=n*n=0n*0—n=0n答案C
10.一个算法所需时间由下述递归方程表示,试求出该算法的时间复杂度的级别或阶式中n是问题的规模,为简单起见,设n是2的整数次幕解析设「根据题目所给定义有n=k—O,4•——1卜」-一•一I1—!|!I[・一——♦・•一,|[•-♦一由此可得M=2U+I—I=U U+2I LT TT一般递推公式二匚口,进而得O=r_+iTr-n「一一「-r-即T—hl—ITI—l+k——=k+lL卜―][・■—||a*9lir.lW«|I.JJfl!______A也就是Tn=2{n}+{n n}=nn+1,OnlI no解析链式存储设计时,各个不同结点的存储空间可以不连续,但结点内的存储单元地址必须连续答案A
3、对于两种不同的数据结构,逻辑结构或物理结构一定不相同吗?数据的运算也是数据结构的一个重要方面对于两种不同的数据结构,它们的逻辑结构和物理结构完全有可能相同比如二叉树和二叉排序树,二叉排序树可以采用二叉树的逻辑表示和存储方式,前者通常用于表示层次关系,而后者通常用于排序和查找虽然它们的运算都有建立树、插入结点、删除结点和查找结点等功能,但对于二叉树和二叉排序树,这些运算的定义是不同的,以查找结点为例,二叉树的时间复杂度为而二叉排序树的时间复杂度为0n,Ologc\n
4、试举一例,说明对相同的逻辑结构,同一种运算在不同的存储方式下实现时,其运算效率不同线性表既可以用顺序存储方式实现,又可以用链式存储方式实现在顺序存储方式下,在线性表中插入和删除元素,平均要移动近一半的元素,时间复杂度为;而在链式存储方式下,插入和删除0n的时间复杂度都是
015、下面关于倒排文件的说法中正确的是一o:倒排文件是对主关键字建立索引.•A・倒排文件是对次关键字建立索引B:・倒排文件的优点是维护简单C:・:采用倒排文件是为了节省存储空间•D解析倒排文件用记录的非主属性也叫副键来查找记录而组织的文件叫倒排文件,即次索引倒排文件中包括了所有副键值,并列出了与之有关的所有记录主键值,主要用于复杂查询倒排文件的优点是检索记录较快特别是对某些询问,不用读取记录,就可得到解答答案B
6、下列术语中与数据的存储结构无关・:循环队列•A・:堆栈•B:散列表.•C・:单链表•D解析数据的存储结构有顺序存储、链式存储、索引存储和散列存储栈是一种抽象数据类型,可采用顺序存储或链式存储,是一种逻辑结构散列表和单链表表示几种数据结构,既描述逻辑结构,又描述存储结构答案B
7.下面程序的时间复杂度为一ofor i=1,s=0;in;i++{t=1;for j=1;j=i;j++s=s+t;}•A:0nn2B:0n
4.D:0解析分析代码内层循环执行次,外层循环执行次,从取i ni1到得知执行最内层循环语句总次数为no1+n*n2o nN,即o o答案B
8、下面算法的时间复杂度是一oVoid funint nint iwhile sn;++is=s+i;•A:0n2n•B:0•C:0•D:Onlogn解析最底层的代码为到达的过程刚好是S=s+i,s n这样累加起来的,根据等差队列之1+2+3+4….+m和的公式,()故约等于根号所以此题l+m*m=2n,m n,选C答案C
9、下面算法的空间复杂度为—float averfloat a[n]{int j;一for j=n;j0;jH nprintf%
8.2f a[j];A•A:01c\n,•B:Olog•C:0n2n•D:0解析函数体定义中出现数组,数组在初始化时需要分配空间,此时空间复杂度为所以选0n,Co答案C10,已知程序如下所示,程序运行时使用栈来保存调用过程的信息,自栈底到栈顶保存的信息依次对应的是int Sint n{return n=00:Sn-1+n;void main{coutS1;・•A:main-Sl-S0・•B:S0-Sl-main・•C:main-S0-Sl・•D:Sl-S0-main解析程序都是从函数开始的,进入函数后执行之main mainSl,后递归执行S0答案Ao
1.下列函数的时间复杂度是一int funcintninti=0,sum=O;whilesumn sum+=++i;return i;•A:Ologn•B:0•C:0n•D:Onlogn解析〃〃相当于〃++;进行sum+-++i;i sum=sum+io到第趟循环,显然需要进k sum=l+k*k/2l+k*k/2n,行口趟循环,因此这也是该函数的时间复杂度。