还剩10页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
1.栈和队列的共同特点是(只允许在端点处插入和删除元素)
4.栈通常接受的两种存储结构是(线性存储结构和链表存储结构)
5.下列关于栈的叙述正确的是(D)A.栈是非线性结构B.栈是一种树状结构C.栈具有先进先出的特征D.栈有后进先出的特征
6.链表不具有的特点是(B)A.不必事先估计存储空间B.可随机访问任一元素C.插入删除不须要移动元素D.所需空间及线性表长度成正比
7.用链表表示线性表的优点是(便于插入和删除操作)8,在单链表中,增加头结点的目的是(便利运算的实现)
9.循环链表的主要优点是(从表中任一结点动身都能访问到整个链表)
10.线性表L=(al,a2,a3,……ai,……an),下列说法正确的是(D)A.每个元素都有一个干脆前件和干脆后件B.线性表中至少要有一个元素C.表中诸元素的排列依次必需是由小到大或由大到小D.除第一个和最终一个元素外,其余每个元素都有一个且只有一个干脆前件和干脆后件
11.线性表若接受链式存储结构时,要求内存中可用存储单元的地址(D)A.必需是连续的B.部分地址必需是连续的C.确定是不连续的D.连续不连续都可以
12.线性表的依次存储结构和线性表的链式存储结构分别是(随机存取的存储结构、依次存取的存储结构)
13.树是结点的集合,它的根结点数目是(有且只有1)
14.在深度为5的满二叉树中,叶子结点的个数为
(31)
15.具有3个结点的二叉树有(5种形态)
16.设一棵二叉树中有3个叶子结点,有8个度为1的结点,则该二叉树中总的结点数为
(13)
17.已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是(cedba)
18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为(DGEBHFCA)
19.若某二叉树的前序遍历访问依次是abdgcefh,中序遍历访问依次是dgbaechf,则其后序遍历的结点访问依次是(gdbehfca)
20.数据库爱惜分为平安性限制、完整性限制、并发性限制和数据的复原
1.在计算机中,算法是指(解题方案的精确而完整的描述)
2.在下列选项中,哪个不是一个算法一般应当具有的基本特征(无穷性)说明算法的四个基本特征是可行性、确定性、有穷性和拥有足够的情报
3.算法一般都可以用哪几种限制结构组合而成(依次、选择、循环)
4.算法的时间困难度是指(算法执行过程中所须要的基本运算次数)
5.算法的空间困难度是指(执行过程中所须要的存储空间)
6.算法分析的目的是(分析算法的效率以求改进)
7.下列叙述正确的是(C)A.算法的执行效率及数据的存储结构无关
8.算法的空间困难度是指算法程序中指令(或语句)的条数C.算法的有穷性是指算法必需能在执行有限个步骤之后终止D.算法的时间困难度是指执行算法程序所须要的时间
8.数据结构作为计算机的一门学科,主要探讨数据的逻辑结构、对各种数据结构进行的运算,以及(数据的存储结构)
9.数据结构中,及所运用的计算机无关的是数据的(C)A.存储结构B.物理结构C.逻辑结构D.物理和存储结构
10.下列叙述中,错误的是(B)return_v[i++]=stack l.top;stack l.pop;return_v[i]=;return return_v;int mainint argc,char*argv[]{cout«This isfishsky*s Chinesesite:://fishsky/cncout«reverseThis isfishskys Chinesesite:://fishsky/cn,H fishsky;return0;8,删除数组中重复的数字问题一个动态长度可变的数字序列,以数字0为结束标记,要求将重复的数字用一个数字代替,例如将数组1,1,1,222,2,2,7,7』,5,5,5,0转变成127,1,5,0问题比较简洁,要留意的是这个数组是动态的所以避开麻烦我还是用了STL的vectoro#include iostream#include vectorusingnamespace std;//remove theduplicated numbersin anintger aiTay,the arraywas endwith0;//e.g.1,1,1,2,2,54,4,4,4,1,0—l,2,5,4,l,0void staticremove_duplicatedint af],vectorint_st_st.push_backa[O];forint i=1;_st[_st.size-l]!=0;i++_st.push_backa[i];}当然假如可以变更原来的数组的话,可以不用STL,仅须要指针操作就可以了下面这个程序将修改原来数组的内容void staticremove_duplicated2int a[]ifa
[0]==0||a二二NULL return;int insert=1,current=1;whilea[current]!=0ifa[current]!=a[current-1]a[insert]=a[current|;insert++;current+4-;elsecurrent++;a[insert]=O;9,如何推断一棵二叉树是否是平衡二叉树问题推断一个二叉排序树是否是平衡二叉树解决方案依据平衡二叉树的定义,假如随意节点的左右子树的深度相差不超过1,那这棵树就是平衡二叉树首先编写一个计算二叉树深度的函数,利用递归实现templatetypename Tstaticint DepthBSTreeNodeT*pbsif pbs==NULLreturn0;elseint Id=Depthpbs-left;int rd=Depthpbs-right;return1+Id rdId:rd;下面是利用递归推断左右子树的深度是否相差1米推断是否是平衡二叉树的函数templatetypcname Tstaticbool isBa!anceBSTreeNodeT*pbsif pbs==NULLreturn true;int dis=Depthpbs-left-Depthpbs-right;if disl||dis-l return false;elsereturn isBalancepbs-leftisBalancepbs-right;
4.abstract classSomething{private abstractString doSomething;该段代码有错吗?答案错abstract的methods不能以private修饰abstract的methods就是让子类implement实现具体微小环节的,怎么可以用private把abstract method封锁起来呢?同理,abstract method前不能加finalo
5.看看下面的代码段错在哪里public classSomething{void doSomething{private Strings=n;int1=s.lengthQ;答案错局部变量前不能放置任何访问修饰符private,public,和protectedfinal可以用来修饰局部变量final如同abstract和strictfp,都是非访问修饰符,strictfp只能修饰class和method而非variable
6.下面该段代码是否有错,若是有错错在哪里?abstract className{private Stringname;public abstractboolean isStupidNameStringname{}答案错abstract method必需以分号结尾,且不带花括号A.数据的存储结构及数据处理的效率密切相关B.数据的存储结构及数据处理的效率无关C.数据的存储结构在计算机中所占的空间不愿定是连续的D.一种数据的逻辑结构可以有多种存储结构
11.数据的存储结构是指(数据的逻辑结构在计算机中的表示)
12.数据的逻辑结构是指(反映数据元素之间逻辑关系的数据结构)
13.依据数据结构中各数据元素之间前后件关系的困难程度,一般将数据结构分为(线性结构和非线性结构)
14.下列数据结构具有记忆功能的是(C)A.队列B.循环队列C.栈D.依次表
15.下列数据结构中,按先进后出原则组织数据的是(B)A.线性链表B.栈C.循环链表D.依次表
16.递归算法一般须要利用(队列)实现
17.下列关于栈的叙述中正确的是(D)A.在栈中只能插入数据B.在栈中只能删除数据C.栈是先进先出的线性表D.栈是先进后出的线性表
20.由两个栈共享一个存储空间的好处是(节约存储空间,降低上溢发生的机率)
21.应用程序在执行过程中,须要通过打印机输出数据时丁一般先形成一个打印作业,将其存放在硬盘中的一个指定(队列)中,当打印机空闲时,就会按先来先服务的方式从中取出待打印的作业进行打印
22.下列关于队列的叙述中正确的是(C)A.在队列中只能插入数据B.在队列中只能删除数据C.队列是先进先出的线性表D.队列是先进后出的线性表
23.下列叙述中,正确的是(D)A.线性链表中的各元素在存储空间中的位置必需是连续的B.线性链表中的表头元素确定存储在其他元素的前面C.线性链表中的各元素在存储空间中的位置不愿定是连续的,但表头元素确定存储在其他元素的前面D.线性链表中的各元素在存储空间中的位置不愿定是连续的,且各元素的存储依次也是随意的
24.下列叙述中正确的是(A)A.线性表是线性结构B.栈及队列是非线性结构C.线性链表是非线性结构D.二叉树是线性结构
26.线性表若接受链式存储结构时,要求内存中可用存储单元的地址(连续不连续都可以)
27.链表不具有的特点是(B)A.不必事先估计存储空间B.可随机访问任一元素C.插入删除不须要移动元素D.所需空间及线性表长度成正比
28.非空的循环单链表head的尾结点(由p所指向),满足(p-next=head)
29.及单向链表相比,双向链表的优点之一是(更简洁访问相邻结点)
30.在(D)中,只要指出表中任何一个结点的位置,就可以从它动身依次访问到表中其他全部结点A.线性单链表B.双向链表C.线性链表D.循环链表
31.以下数据结构属于非线性数据结构的是(C)A.队列B.线性表C.二叉树D.栈
32.树是结点的集合,它的根结点数目是(有且只有1)
33.具有3个结点的二叉树有(5种形态)
34.在一棵二叉树上第8层的结点数最多是
(128)注2K-I
35.在深度为5的满二叉树中,叶子结点的个数为
(16)注2n-l
36.在深度为5的满二叉树中,共有
(31)个结点注2n-l
37.设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为
(350)说明完全二叉树总结点数为N,若N为奇数,则叶子结点数为(N+l)/2;若N为偶数,则叶子结点数为N/
238.设有下列二叉树,对此二叉树中序遍历的结果是(B)A.ABCDEFB.DBEAFCC.ABDECFD.DEBFCA
39.已知二叉树后序遍历序列是dabec,中序遍历序列debac,它的前序遍历序列是(cedba)
40.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为(DGEBHFCA)
41.若某二叉树的前序遍历访问依次是abdgcefh,中序遍历访问依次是dgbaechf,则其后序遍历的结点访问依次是(gdbehfca)
42.串的长度是(串中所含字符的个数)
43.设有两个串p和q,求q在p中首次出现位置的运算称做(模式匹配)
44.N个顶点的连通图中边的条数至少为(N-1)
45.N个顶点的强连通图的边数至少有(N)
46.对长度为n的线性表进行依次查找,在最坏状况下所须要的比较次数为(N)
47.最简洁的交换排序方法是(冒泡排序)
48.假设线性表的长度为n,则在最坏状况下,冒泡排序须要的比较次数为(n(n.l)/2)
49.在待排序的元素序列基本有序的前提下,效率最高的排序方法是(冒泡排序)
50.在最坏状况下,下列依次方法中时间困难度最小的是(堆排序)
51.希尔排序法属于(插入类排序)
52.堆排序法属于(选择类排序)
53.在下列几种排序方法中,要求内存量最大的是(归并排序)
54.已知数据表A中每个元素距其最终位置不远,为节约时间,应接受(干脆插入排序)
55.算法的基本特征是可行性、确定性、有穷性和拥有足够的情报
1.一个算法通常由两种基本要素组成一是对数据对象的运算和操作,二是算法的限制结构
2.算法的困难度主要包括时间困难度和空间困难度
3.实现算法所需的存储单元多少和算法的工作量大小分别称为算法的空间困难度和时间困难度
4.所谓数据处理是指对数据集合中的各元素以各种方式进行运算,包括插入、删除、查找、更改等运算,也包括对数据元素进行分析
5.数据结构是指相互有关联的数据元素的集合
6.数据结构分为逻辑结构及存储结构,线性链表属于存储结构
7.数据结构包括数据的逻辑结构和数据的存储结构
8.数据结构包括数据的逻辑结构、数据的存储结构以及对数据的操作运算
9.数据元素之间的任何关系都可以用前趋和后继关系来描述10数据的逻辑结构有线性结构和非线性结构两大类
11.常用的存储结构有依次、链接、索引等存储结构
12.依次存储方法是把逻辑上相邻的结点存储在物理位置相邻的存储单元中
13.栈的基本运算有三种入栈、退栈及读栈顶元素
14.队列主要有两种基本运算入队运算及退队运算
15.在实际应用中,带链的栈可以用来收集计算机存储空间中全部空闲的存储结点,这种带链的栈称为可利用栈
16.栈和队列通常接受的存储结构是链式存储和依次存储
17.当线性表接受依次存储结构实现存储时,其主要特点是逻辑结构中相邻的结点在存储结构中仍相邻
18.循环队列主要有两种基本运算入队运算及退队运算每进行一次入队运算,队尾指针就进
118.当循环队列非空且队尾指针等于对头指针时,说明循环队列已满,不能进行入队运算这种状况称为上溢
19.当循环队列为空时,不能进行退队运算,这种状况称为下溢o
20.在一个容量为25的循环队列中,若头指针front=16,尾指针rear=9,则该循环队列中共有18个元素注当rearvfront时,元素个数=总容量一front-rear;当rearfront时,元素个数=rear—front
1.推断链表是否存在环型链表问题推断一个链表是否存在环,例如下面这个链表就存在一个环例如NI-N2-N3-N4-N5-N2就是一个有环的链表,环的起先结点是N5这里有一个比较简洁的解法设置两个指针pl,p2o每次循环pl向前走一步,p2向前走两步直到p2遇到NULL指针或者两个指针相等结束循环假如两个指针相等则说明存在环struct linkint data;link*next;;bool IsLooplink*head link*pl=head,*p2=head;if head二二NULL||head-next=二NULL return false;do{pl=pl-next;p2=p2-next-next;}whilep2p2-nextpl!=p2;ifpl==p2return true;elsereturn false;2,链表反转单向链表的反转是一个经常被问到的一个面试题,也是一个特殊基础的问题比如一个链表是这样的通过反转后成为5・4-
3.2・1最简洁想到的方法遍历一遍链表,利用一个帮助指针,存储遍历过程中当前指针指向的下一个元素,然后将当前节点元素的指针反转后,利用已经存储的指针往后面接着遍历源代码如下struct linka{intdata;linka*next;;void reverselinka*headifhead==NULLreturn;linka*pre,*cur,*ne;pre=head;cur=head-next;whilecur ne=cur-next;cur-next=pre;pre=cur;cur=ne;head-next=NULL;head=pre;还有一种利用递归的方法这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点源代码如下不过这个方法有一个缺点,就是在反转后的最终一个结点会形成一个环,所以必需将函数的返回的节点的next域置为NULL因为要变更head指针,所以我用了引用算法的源代码如下linka*reverselinka*p,linka*head ifp==NULL||p-next==NULLhead=p;return p;else{linka*tmp=reversep-next,head;tmp-next=p;return p;3,推断两个数组中是否存在相同的数字给定两个排好序的数组,怎样高效得推断这两个数组中存在相同的数字?这个问题首先想到的是一个Onlogn的算法就是随意选择一个数组,遍历这个数组的全部元素,遍历过程中,在另一个数组中对第一个数组中的每个元素进行binary search用C++实现代码如下bool findcommoninta[],int sizel,int b[],int size2int i;fbri=O;isizel;i++int start=0,end=size2-1,mid;whilestart=endmid=start+end/2;ifa[i]==b[mid]return true;else ifa[i]b[mid]end=mid-1;elsestart=mid+l;returnfalse;后来发觉有一个0n算法因为两个数组都是排好序的所以只要一次遍历就行了首先设两个下标,分别初始化为两个数组的起始地址,依次向前推动推动的规则是比较两个数组中的数字,小的那个数组的下标向前推动一步,直到任何一个数组的下标到达数组末尾时,假如这时还没遇到相同的数字,说明数组中没有相同的数字bool findcommon2int a||,int sizel,int b[J,int size2int i=0,j=0;whileisizeljsize2ifa[i]==b[j]return true;ifa[i]bUDj++;ifalijb[j]i++;returnfalse;4,最大子序列问题给定一整数序列Al,A2,...An可能有负数,求A1〜An的一个子序列Ai〜Aj,使得Ai到Aj的和最大例如整数序列211,-4,13,-5,2,-5,-3,12,-9的最大子序列的和为21对于这个问题,最简洁也是最简洁想到的那就是穷举全部子序列的方法利用三重循环,依次求出全部子序列的和然后取最大的那个当然算法困难度会达到023明显这种方法不是最优的,下面给出一个算法困难度为On的线性算法实现,算法的来源于Programming Pearls一书在给出线性算法之前,先来看一个对穷举算法进行优化的算法,它的算法困难度为022其实这个算法只是对对穷举算法略微做了一些修改其实子序列的和我们并不须要每次都重新计算一遍假设Sumi,j是Ali]...A[j]的和,那么Sumi,j+l=Sumi,j+A[j+l]利用这一个递推,我们就可以得到下面这个算法int max_subint af|,int sizeint i,j,v,max=a[O];fori=0;isize;i++v=0;forj=i;jsize;j++v=v+a[j];//Sumi,j+1=Sumi,j+A[j+1]ifvmaxmax=v;return max;那怎样才能达到线性困难度呢?这里运用动态规划的思想先看一下源代码实现int max_sub2inta[],int sizeint i,max=O,temp_sum=O;fori=0;isize;i++temp_sum4-=a[i];iftemp_summaxmax=temp_sum;else iftemp_sum0temp_sum=O;return max;6,按单词反转字符串并不是简洁的字符串反转,而是按给定字符串里的单词将字符串倒转过来,就是说字符串里面的单词还是保持原来的依次,这里的每个单词用空格分开例如Here isfishksy经过反转后变为fishksy isHere假如只是简洁的将全部字符串翻转的话,可以遍历字符串,将第一个字符和最终一个交换,其次个和倒数其次个交换,依次循环其实依据单词反转的话可以在第一遍遍历的基础上,再遍历一遍字符串,对每一个单词再反转一次这样每个单词又复原了原来的依次char*reverse_wordconst char*strint len=strlenstr;char*restr=new char[len+l];strcpy restr,str;inti,j;fori=0,j=len-1;ij;i++j-char temp=restr[i];restr[i]=restr[j];restr[j]=temp;int k=0;whileklen i=j=k;whilerestr[j]!=**restrj]!=n j++;k=j+l;j--;for;ij;i++,j-char temp=restr[i];restr[i]=restr[j];restr[j]=temp;return restr;假如考虑空间和时间的优化的话,当然可以将上面代码里两个字符串交换部分改为异或实现例如将char temp=restr[i];restr[i]=restr[j];restr[j]=temp;改为restr[i]A=restr|j|;restr[j]A=restr[i];restr[i]A=restr[j];7,字符串反转我没有记错的话是一道MSN的笔试题,网上无意中看到的,拿来做了一下题目是这样的,给定一个字符串,一个这个字符串的子串,将第一个字符串反转,但保留子串的依次不变例如输入第一个字符串This isfishsky*s Chinesesite:://fishsky/cnH子串“fishsky”输出nc/nc.moc.fishsky.www//:ptth:etis esenihCsfishsky sisihT一般的方法是先扫描一边第一个字符串,然后用stack把它反转,同时记录下子串出现的位置然后再扫描一遍把记录下来的子串再用stack反转我用的方法是用一遍扫描数组的方法扫描中假如发觉子串,就将子串倒过来压入堆栈最终再将堆栈里的字符弹出,这样子串又复原了原来的依次源代码如下#include iostream#include cassert#include stackusingnamespace std;//reverse thestring exceptthe substringtoken,.const char*reverseconst char*si,const char*tokenasserts1token;stackchar stack1;const char*ptoken二token,*head=si,*rear=si;while*head!=while*head!=*ptoken==*headptoken++;head++;if*ptoken==//contain thetokenconst char*p;forp=head-1;p=rear;p—stack l.push*p;ptoken=token;rear=head;elsestack l.push:}:rear;head=++rear;ptoken=token;char*return_v=new char[strlensl+l];inti=0;while!stackl.emptyO。