数据结构问题答疑材料辅导教师马

1、2009-2010学年第二学期数据结构问题答疑材料1、怎么实现顺序表的查询？答案：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。2、什么是连通分量？答案：在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。3、有向图有12个顶点，图中弧为：(C1,C2),(01,C4),(01,03),(01,C12),(C9,012),(09,0

2、10),(09,011),(04,05),(02,03),(010,012),(011,06),(03,05),(03,07),(03,08),(05,07),(06,08),该图的拓扑排序可能的序列是a、01-02-03-04-05-07-09-010-011-06-012-08b、09-010-011-06-01-012-04-02-03-05-07-08c、07-02-03-04-05-01-09-010-011-06-012-08d、08-010-011-06-01-012-04-02-03-05-07-09e、以上都不正确答案：ab4、已知权值W=2,3,4,7,8,9构造出的哈夫曼

3、树的带权路径长度WPL=答案：先得构造哈弗曼树，然后计算带权路径长度。哈弗曼树的带权路径长度为树中所有叶子节点的带权路径长度之和。wpl=2*(7+8)+2*9+3*4+4*(2+3)=30+18+12+20=805、无向图有8个顶点V1-V8,边为(V1,V2),(V1,V3),(V2,V4),(V2,V5),(V3,V6),(V3,V7),(V4,V8),(V5,V8),(V6,V7),该图广度优先遍历序列有可能为a、V1,b、V1,c、V8,d、V1,V2,V3,V4,V5,V6,V7,V8V2,V4,V5,V8,V3,V6,V7V4,V5,V2,V1,V3,V6,V7V3,V2,V7,

4、V6,V5,V4,V8e、以上都有不可能答案：广度优先遍历连通图的基本思想是：一step1、从图中某个顶点V0出发，并访问此顶点；step2、从V0出发，访问V0的各个未曾访问的邻接点W1,WZ,Wk;然后，依次从W1,W2；,Wk出发访问各自未被访问的邻接点。一step3、重复step2,直到全部顶点都被访问为止。按上述步骤，可知V1,V2,V3,V4,V5,V6,V7,V8;V1,V3,V2,V7,V6,V5,V4,V8是可能的序列6、在一个单链表中，已知p所指结点，若在p之后插入s结点，则执行？答案：s->next=p->next;p->next=s7、数据的逻辑结构中

5、非线性结构有A、集合日线形结构C树形结构D网状结构E、链式结构答案：C树形结构，D网状结构8、线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系A、一对一，多对多，一对多日一对多，一对一，多对多C一对一，一对多，多对多D多对多，一对多，一对一E、以上都不正确答案：C一对一，一对多，多对多9广义表(a),a)的表尾是()AaB、bC(a)D(a)答案：C(a)10、算法有哪些重要特性？答案：1.有穷性2.确定性3.可行性4.有输入5.有输出11、数据结构是一门研究什么内容的学科？答案：数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和

6、施加于对象的操作等的学科。12、设有一个空栈，现在有输入序列1、2、3、4、5,经过push,push,pop,push,pop,push,pushpop,pop,pop后，输出序歹U是.选项：a、1、2、3、4、5b、2、3、5、4、1c54321d13425答案：b、2、3、5、4、1解析：1,2进栈，最先出栈的肯定是2。13、两个串相等的条件是A长度相等以对应位置的字符相等C存储位置相同D存储结构相同E、以上都是答案：AB14、顺序查找适用于存储结构为的线性表A散列以顺序或者链式C压缩D索引答案：B15、设哈希表长m=16哈希函数H(key)=key%13;表中已有3个结点H(19)=6

7、H(27)=1H(23)=10其余地址为空，如用线性探测再散列处理冲突，关键字14的地址是选项：a、1b、2c、3d、0e、以上都不正确答案：b解析：14%13=1,因为1地址中已经有元素，所以需要再哈希求地址：(14+1)%13=216、最常用的哈希函数构造方法为A除留余数法日直接定址法C折叠法D数字分析法答案：A17、一个链式队列中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算是A、r->next=sBr=sCs=rDs=r->nextE、s->next=r答案：AB18、广义表L=(a,(x,y),(x)的长度是,深度是A、33B>23C32D43E、3

8、4答案：A、3解析：广义表LS中的直接元素的个数称为LS的长度；广义表LS中括号的最大嵌套层数称为LS的深度。19、在一个单链表中，已知p所指结点，若在p之后插入s结点，则执行A、s->next=p->nextBp->next=sCp->next=s->nextDp->next=sE、p->next=p->next->next答案：AB20、顺序栈S为空的判定条件选项：a、S.top=S.baseb、S=S.basec、S.top=Sd、没有正确答案答案：a21、一个队列的入队序列是1、3、4、2,则队列的首次输出元素是()A3B、2C、1

9、D、4答案：C22、计算机算法指的是(1),它必须具备(1) A.计算方法B.排序方法法(2) A.可执行性、可移植性、可扩充性C.确定性、有穷性、稳定性答案：C.B.2)这三个特性。C. 解决问题的步骤序列D.8. 可执行性、确定性、有穷性D. 易读性、稳定性、安全性调度方两大类。.顺序结构、链式结构.初等结构、构造型结构23、从逻辑上可以把数据结构分为(A.动态结构、静态结构BC.线性结构、非线性结构D答案：C.24、数据结构是一门研究什么内容的学科？答案：.数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。25、数据的存储结构由哪四

10、种基本的存储方法实现？答案：四种表示方法(1)顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作(如插入、删除)效率较差。(2)链式存储方式。每个存储结点除包含数据元素信息外还包含一组(至少一个)指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作(如插入、删除等)，但存储空间开销大(用于指针)，另外不能折半查找等。(3)索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置(下标)或存储区间端点(下标)，兼有静态和动态特性。(4)散列存储方式。通过散列

11、函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。26、线性表是具有门个()的有限序列(n>0)。A.表元素B.字符C.数据元素D.数据项E.信息项答案：C27、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()(1<=i<=n+1)。A.O(0)B.0(1)C.O(n)D.O(n2)答案：C28、线性表有两种存储结构：一是顺序表，二是链表。试问：(1)如果有n个线性表同时并存，并且在

12、处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？(2)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？答案：.(1)选链式存储结构。它可动态申请内存空间，不受表长度(即表中元素个数)的影响，插入、删除时间复杂度为O(1)。(2)选顺序存储结构。顺序表可以随机存取，时间复杂度为O(1)。29、若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？答案：采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中

13、插入和删除操作不需要移动元素。30、线性结构包括、和。线性表的存储结构分成和答案：线性表栈队列串顺序存储结构和链式存储结构31、对于栈操作数据的原则是()。A.先进先出B.后进先出C.后进后出D.不分顺序答案：B.32、一个栈的输入序列为123n,若输出序列的第一个元素是n,输出第i(1<=i<=n)个兀素是(；A.不确定B.n-i+1C.iD.n-i答案：B33、有六个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.234156答案：C.34、栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.

14、只允许在端点处插入和删除元素D.没有共同点答案：C35、判断：栈与队列是一种特殊操作的线性表。（）答案：V36、判断：栈和队列都是线性表，只是在插入和删除时受到了一些限制。（）答案：V37、名词解释：栈。答案：栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。38、名词解释：队列答案：队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。39、若元素的进栈序列为：A、RCD、E,运用栈操作，能否得到出栈

15、序列B、CAE、D和DB、A、CE?为什么？答案：能得到出栈序列BCA、E、D,不能得到出栈序列D、B、AC、E。其理由为：若出栈序列以D开头，说明在D之前的入栈元素是A、B和C,三个元素中C是栈顶元素，B和A不可能早于C出栈，故不可能得到DBA、C、E出栈序列。40、下面关于串的的叙述中，哪一个是不正确的？（）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储答案：B41、已知串S='aaab',其Next数组值为（）。A.0123B.1123C.1231D,1211答案：A42、串的长度是指（）A.串中所

16、含不同字母的个数C.串中所含不同字符的个数串中所含字符的个数.串中所含非空格字符的个数答案：B43、空格串是指_（1）_,其长度等于（2）_q答案：（1）由空格字符（ASCII值32）所组成的字符串（2）空格个数44、串是一种特殊的线性表，其特殊性表现在（1）;串的两种最基本的存储方式是（2）、;两个串相等的充分必要条件是（4）q答案：（1）其数据元素都是字符（2）顺序存储（3）和链式存储（4）串的长度相等且两串中对应位置的字符也相等45、描述以下概念的区别：空格串与空串答案：空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的

17、长度是零。),表尾是()。C.(a,b,c,d)D.(b,c,d)46、广义表（a,b,c,d）的表头是A.aB.（）答案：C47、广义表(a,(b,c),d,e)的表头为()。A.aB.a,(b,c)C.(a,(b,c)D.(a)答案：A48、已知一算术表达式的中缀形式为（）A.-A+B*C/DEB.-A+B*CD/E答案：DA+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为-+*ABC/DED.-+A*BC/DE）.一棵二叉树的度可以小于22D.二叉树中任何一个结点的度都为249、有关二叉树下列说法正确的是（A.二叉树的度为2BC.二叉树中至少有一个结点的度为答案：B50、一棵

18、树高为K的完全二叉树至少有（）个结点A.2-1B.2k-1-1C.2k-1D.2答案：C51、已知一棵二叉树的前序遍历结果为ABCDEF中序遍历结果为CBAEDF则后序遍历的结果为（）。A.CBEFDAB.FEDCBAC.CBEDFAD,不定答案：A52、线索二叉树是一种（）结构。A.逻辑B逻辑和存储C.物理D.线性答案：C53、由3个结点可以构造出多少种不同的二叉树？（）A.2B.3C.4D.5答案：D54、从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。答案：树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只

19、是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树的区别有三：一是二叉树的度至多为2,树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。55、树和二叉树之间有什么样的区别与联系？1所述三点。二叉树不是树的特例。答案：树和二叉树逻辑上都是树形结构，区别有以上题56、请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。答案：线性表属于约束最强的线性结构，在非空线性表中，只有一个

20、“第一个”元素，也只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲（根无双亲），从这个意义上说存在一（双亲）对多（子女）的关系。广义表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表均属非线性结构。但在以下意义上，又蜕变为线性结构。如度为1的树，以及广义表中的元素都是原子时。另外，广义表从元素之间的关系可看成前驱和后继，也符合线性表，但这时元素有原子，也有子表，即元素并不属于同一数据对象。57、已知

21、完全二叉树有30个结点，则整个二叉树有多少个度为0的结点？答案：1558、一个n个顶点的连通无向图，其边的个数至少为（）。A.n-1B.nC.n+1D.nlogn;答案：A59、n个结点的完全有向图含有边的数目（）。A.n*nB.n（n+1）C.n/2D.n*（nl）答案：D60、判断一个无向图是一棵树的条件是答案：有n个顶点，n-1条边的无向连通图61、具有10个顶点的无向图，边的总数最多为答案：4562、求图的最小生成树有两种算法，算法适合于求稀疏图的最小生成树。答案：克鲁斯卡尔63、下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个节点V1,V2,Vn,用相邻矩阵A表

22、示，边的权全是正数。请在下列划线处填上正确叙述。(1) .若(Vi,Vj)是边，则A(i,j)的值等于,若(Vi,Vj)不是边，则A(i,j)的值是一个比任何边的权,矩阵的对角线元素全为0。(2) .构造最小生成树过程中，若节点Vi已包括进生成树，就把相邻矩阵的对角线元素A(i,i)置成，若(Vi,Vj)已包括进生成树，就把矩B$元素A(i,j)置成。(3) .算法结束时，相邻矩阵中的元素指出最小生成树的。答案：.(1)(V,V)边上的权值都大的数1负值(3)为负边64、n个顶点的无向连通图最少有多少条边？n个顶点的有向连通图最少有多少条边？答案：n-1,n65、下面关于二分查找的叙述正确的是

23、()A.表必须有序，表可以顺序方式存储，也可以链表方式存储C.表必须有序，而且只能从小到大排列B.表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只能以顺序方式存储答案：D66、设有一组记录的关键字为19,14,23,1,68,20,84,27,55,11,10,79,用链地址法构造散列表，散列函数为H(key)=keyMOD13,散列地址为1的链中有()个记录。A.1B.2C.3D.4答案：D67、设哈希表长为14,哈希函数是H(key尸key%11,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置

24、是()A.8B.3C.5D.9答案：D68、给定一组数据6,2,7,10,3,12以它构造一棵哈夫曼树，则树高为,带权路径长度WP面值为。答案：5,96答案：69、可以唯一的标识一个记录的关键字称为。答案：主关键字70、请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联答案：线性结构的基本特征为：j兀素；a日二一“取后兀索唯一的后继(后件)；唯一的前驱(前件)。1 .集合中必存在唯一的一个“第2 .集合中必存在唯一的一个3 .除最后一个元素之外，均有4 .除第一个元素之外，均有树的基本特征为：树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为

25、父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。广义表的主要特点：(1)广义表的元素可以是子表，而子表还可以是子表，由此，广义表是一个多层的结构。(2)广义表可以被其他广义表共享。如：广义表B就共享表A。在表B中不必列出表A的内容，只要通过子表的名称就可以引用该表。(3)广义表具有递归性，如广义表C。71、已知一棵完全二叉树共有1234个结点，试求：叶结点个数。答案：先求出勺深度为11,再求出1至IJ10层的结点数为1+2+4+8+16+32+64+128+256+512=1023个，用1234减去1023就

26、是第11层的结点为211个，则可求出第10层的叶子结点为512减去106得406个结点，如此叶子结点为211+406=617个。72、以下叙述中正确的是a、线性表的顺序存储结构优于链式存储结构b、线性表的链式存储结构优于顺序存储结构c、线性表的链式存储结构和顺序存储结构各有优缺点d、算法分析主要考虑其时间复杂度和空间复杂度e、在链表中设置头结点为了方便操作答案：c、d、e73、已知权值W=4,7,5,2,9)构造出的哈夫曼树的深度为答案：由这个序列构造的哈夫曼树为：28/1611/7956/24所以此哈夫曼树深度为474、对内部排序按排序原则不同可以分为a、插入排序b、交换排序c、选择排序d、

27、归并排序e、计数排序75、算法具有的重要特性a、有穷性b、确定性c、可行性d、输入e、输出76、什么是数据元素的有限集和D上关系的有限集？数据结构的形式定义：数据结本名称=(D,S)其中D为数据元素的有限集，S是D上关系的有限集.数据元素的有限集是指数据元素组成的那个有限集合；D上关系的有限集指的是D这个有限集合上的关系的一个集合，而这个集合也是有限的。77、广义表L=(a,(x,y),(x)的长度是3,深度是378、线性结构只能用顺序存储吗答案：还可以用链式79、无向图有8个顶点V1-V8,边为(V1,V2),(V1,V3),(V2,V4),(V2,V5),(V3,V6),(V3,V7),V4V8),(V5,a、V1,V2,V3V4V5,V6V7b、V1,V2V4V5V8V3V6c、V8,V4V5V2V1，V3V6d、V1,V3,V2,V7,e、以上都有小可能