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

2009-2010学年第二学期数据结构问题答疑材料1、怎么实现顺序表的查询？ 答案：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关 键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字 和给定值比较都不等，则表明表中没有所查记录，查找不成功。2、什么是连通分量？答案：在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两 个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。3、有向图有 12 个顶点，图中弧为：(Cl, C2)，(Cl, C4), (Cl, C3), (Cl, C12), (C9, C12), (C9 , C10), (C9, C11), (C4, C5), (C2, C3), (C10, C12), (C11, C6), (C3, C5), (C3,C7), (C3, C8), (C5, C7), (C6, C8),该图的拓扑排序可能的序列是a、C1C2C3C4C5C7C9C10C11C6C12C8b、C9C10C11C6C1C12C4C2C3C5C7C8c、C7C2C3C4C5 C1- -C9C10C11C6C12C8d、C8C10C11C6C1C12C4C2C3C5C7 C9e、以上都不正确答案：ab4、已知权值W=2, 3, 4, 7, 8, 9 构造出的哈夫曼树的带权路径长度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,V2,V3,V4,V5,V6,V7,V8b、V1,V2,V4,V5,V8,V3,V6,V7c、V8,V4,V5,V2,V1,V3,V6,V7d、V1,V3,V2,V7,V6,V5,V4,V8e、以上都有不可能答案：广度优先遍历连通图的基本思想是： step1、从图中某个顶点V0出发，并访问此顶点； step2、从V0出发，访问V0的各个未曾访问的邻接点W1, W2,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、数据的逻辑结构中非线性结构有A、集合B、线形结构C、树形结构D、网状结构E、链式结构 答案：C树形结构，D网状结构8、线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系A、一对一，多对多，一对多B、一对多，一对一，多对多C、一对一，对多，多对多D、多对多，一对多，一对一E、以上都不正确答案：C、一对一，一对多，多对多9、广 义 表 (a) ,a ) 的 表 尾 是 ( )A、aB、bC、(a)D、 (a)答案： C、(a)10、算法有哪些重要特性？答案：1.有穷性2确定性3可行性4有输入5有输出 11、数据结构是一门研究什么内容的学科？答案：数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对 象间的关系和施加于对象的操作等的学科。12、设有一个空栈，现在有输入序列 1、2、3、4、5,经过 push,push,pop,push,pop,push,push, pop,pop,pop后，输出序列是.选项：a、1、 2、 3、 4、 5b、2、 3、 5、 4、 1c、5、4、3、2、1d、1、3、4、2、5答案：b、2、3、5、4、1解析：1, 2进栈，最先出栈的肯定是2。13、两个串相等的条件是A、长度相等B、对应位置的字符相等C、存储位置相同D、存储结构相同E、以上都是答案：AB14、顺序查找适用于存储结构为的线性表A、散列B、顺序或者链式C、压缩D、索引答案：B15、设哈希表长m=16，哈希函数H(key)=key%13；表中已有3个结点H (19) =6H(27)=1 H(23)=10其余地址为空，如用线性探测再散列处理冲突，关键字14的地址是选项：a、1b、2c、3d、0e、以上都不正确答案：b解析：14%13=1,因为1地址中已经有元素，所以需要再哈希求地址：(14+1)%13=216、最常用的哈希函数构造方法为A、除留余数法B、直接定址法C、折叠法D、数字分析法答案：A17、一个链式队列中，假设f和r分别为队首和队尾指针,则插入s所指结点的运算是A、rnext=sB、r=sC、s=rD、s=rnextE、snext=r答案：AB18、广义表L=( a,(:x,y), (x)的长度是,深度是A、33B、23C、32D、43E、34答案：A、33解析：广义表LS中的直接兀素的个数称为LS的长度;广义表LS中括号的最大嵌套层数称为LS的深度。19、在一个单链表中，已知p所指结点，若在p之后插入s结点，贝y执行.A、s-next=p-nextB、p-next=sC、p-next = s-nextD、p-next=sE、p-next = p-next-next答案：AB 20、顺序栈S为空的判定条件选项：a、S.to p=S.baseb、S=S.basec、S.top=Sd、没有正确答案答案：a21、一个队列的入队序列是1、3、4、2,则队列的首次输出元素是（）A、3B、 2C、 1答案：C22、计算机算法指的是（1）,它必须具备（2）（1）A.计算方法B.排序方法法（2）A.可执行性、可移植性、可扩充性C.确定性、有穷性、稳定性答案：C. B.D、 4这三个特性。C. 解决问题的步骤序列D.调度方B. 可执行性、确定性、有穷性D. 易读性、稳定性、安全性23、从逻辑上可以把数据结构分为（）两大类。A.动态结构、静态结构B.顺序结构、链式结构C. 线性结构、非线性结构 D.初等结构、构造型结构 答案：C.24、数据结构是一门研究什么内容的学科？答案.数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间 的关系和施加于对象的操作等的学科。25、数据的存储结构由哪四种基本的存储方法实现？答案：四种表示方法（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数 据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针 指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、 删除等），但存储空间开销大（用于指针），另外不能折半查找等。（3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表， 索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态 特性。（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地 址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存 储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。26、线性表是具有*个（）的有限序列（n0）。A.表元素 B.字符 C.数据元素D.数据项E.信息项答案：C27、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）（1二i=n+l）。A. 0（0） B. 0（1）C. O（n）D. O（n2）答案：C28、线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表 的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线 性表中的元素，那么应采用哪种存储结构？为什么？答案.（1）选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的 影响，插入、删除时间复杂度为0 （1）。（2）选顺序存储结构。顺序表可以随机存取，时间复杂度为0 （1）。29、若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什 么？答案：采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空 间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。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. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 6答案：C.34、栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点答案：C35、判断：栈与队列是一种特殊操作的线性表。（）答案：V36、判断：栈和队列都是线性表，只是在插入和删除时受到了一些限制。（）答案：V37、名词解释：栈。答案：栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一 端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。38、名词解释：队列答案：队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除 的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。39、若元素的进栈序列为：A、B、C、D、E,运用栈操作，能否得到出栈序列B、C、A、E、D和D、B、A、C、E?为什么？答案：能得到出栈序列B、C、A、E、D,不能得到出栈序列D、B、A、C、E。其理由为：若 出栈序列以D开头，说明在D之前的入栈元素是A、B和C,三个元素中C是栈顶元素，B 和A不可能早于C出栈，故不可能得到D、B、A、C、E出栈序列。40、下面关于串的的叙述中，哪一个是不正确的？（）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储 答案：BA0123B1123C1231答案：A41、已知串S= aaab，其Next数组值为（）。D121142、串的长度是指（ ）A.串中所含不同字母的个数C串中所含不同字符的个数B. 串中所含字符的个数D. 串中所含非空格字符的个数答案：B 43、空格串是指，其长度等干 （2）。答案：（1）由空格字符（ASCII值32）所组成的字符串（2）空格个数44、串是一种特殊的线性表，其特殊性表现在（1）；串的两种最基本的存储方式是-、（3）_ ；两个串相等的充分必要条件是（4）。答案（1）其数据元素都是字符（2）顺序存储（3）和链式存储（4）串的长度相等且两串中对应位 置的字符也相等 45、描述以下概念的区别：空格串与空串答案：空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格 的个数。空串是不含任何字符的串，即空串的长度是零。)，表尾是(C. (a,b,c,d)D. (b,c,d)C. (a,(b,c)D. (a)46、广义表（a,b,c,d）的表头是A. aB.（） 答案：C47、广义表（a,（b,c）,d,e）的表头为（ A. aB. a,（b,c）答案：A48、已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-其前缀形式为 （）A. -A+B*C/DEB. -A+B*CD/E C. -+*ABC/DED. -+A*BC/DE答案：D49、有关二叉树下列说法正确的是（）A. 二叉树的度为2B. 棵二叉树的度可以小于2C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2 答案：B50、一棵树高为K的完全二叉树至少有（）个结点D. 2kA. 2k -1B. 2k-i - 1C. 2k-i答案：C 51、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF,则后序遍历的结果 为（ ）。A. CBEFDAB. FEDCBAC. CBEDFAD.不定答案：A 52、线索二叉树是一种（ ）结构。A.逻辑 B.逻辑和存储 C.物理 D.线性答案：C53、由3 个结点可以构造出多少种不同的二叉树？（ ） A2B3C4D5答案：D54、从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基 本目的是什么，并指出树和二叉树的主要区别。答案：树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不 同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示， 并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子 树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制； 三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。55、树和二叉树之间有什么样的区别与联系？答案：树和二叉树逻辑上都是树形结构，区别有以上题1所述三点。二叉树不是树的特例。56、请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。答案：线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素， 也只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外， 每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女， 但只有一个双亲（根无双亲，从这个意义上说存在一（双亲）对多（子女）的关系。广义 表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广 义表也是层次结构。从逻辑上讲，树和广义表均属非线性结构。但在以下意义上，又蜕变为 线性结构。如度为1的树，以及广义表中的元素都是原 子时。另外，广义表从元素之间的关系可看成前驱和后继，也符 合线性表，但这时元素有原子，也有子表，即元素并不属于同一 数据对象。57、已知完全二叉树有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表示，边的权全是正数。请在下列划线处填上正确叙述。(1) .若(Vi, Vj)是边，则A (i, j)的值等于，若(Vi, Vj)不是边，则A (i,j)的值是一个比任何边的 ,矩阵的对角线元素全为0。(2) ,构造最小生成树过程中，若节点Vi已包括进生成树，就把相邻矩阵的对角线元素A (i, i)置成,若(Vi, Vj)已包括进生成树，就把矩阵元素A (i, j)置成。(3) ,算法结束时，相邻矩阵中的元素指出最小生成树的。答案：.(1) (V ,V)边上的权值 都大的数 (2)1负值(3)为负 边i j64、n个顶点的无向连通图最少有多少条边？ n个顶点的有向连通图最少有多少条边？ 答案：n-1, n65、下面关于二分查找的叙述正确的是()A. 表必须有序，表可以顺序方式存储，也可以链表方式存储C.表必须有序，而且只 能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只能以顺序方式存储答案：D66、设有一组记录的关键字为19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79，用链地址法构造散列表，散列函数为H (key) =key MOD 13,散列地址为1的链中有()个记录。A, 1B. 2C. 3D. 4答案：D67、设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15, 38, 61,84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突， 则放入的位置是()A, 8B, 3C, 5D, 9答案：D68、给定一组数据6, 2, 7, 10, 3, 12以它构造一棵哈夫曼树，则树高为，带权路径长度WPL的值为。答案：5,96答案：69、可以唯一的标识一个记录的关键字称为。答案：主关键字70、请分析线性表、树、广义表的主要结构特点,以及相互的差异与关联 答案：线性结构的基本特征为:1集合中必存在唯一的一个“第一元素”；2集合中必存在唯一的一个“最后元素” ；3除最后一个元素之外，均有唯一的后继（后件） 4除第一个元素之外，均有唯一的前驱（前件）。树的基本特征为: 树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构 中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。广义表的主要特点：（1）广义表的元素可以是子表，而子表还可以是子表，由此，广义表是一个多层的结构。（2）广义表可以被其他广义表共享。如：广义表B就共享表A。在表B中不必列出表A的 内容，只要通过子表的名称就可以引用该表。（3）广义表具有递归性，如广义表C。71、已知一棵完全二叉树共有1234个结点，试求：叶结点个数。答案：先求出树的深度为11，再求出1到10层的结点数为1+2+4+8+16+32+64+128+256+512=1023 个，用 1234 减去 1023 就是第 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、归并排序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 个顶点 V1V8，边为(VI, V2), (VI, V3), (V2, V4), (V2, V5), (V3, V6)，(V3, V7), (V4, V8), (V5, V8), (V6, V7),该图广度优先遍历序列有可能为a、V1,V2,V3,V4,V5,V6,V7,V8b、V1,V2,V4,V5,V8,V3,V6,V7c、V8,V4,V5,V2,V1,V3,V6,V7d、V1,V3,V2,V7,V6,V5,V4,V8e、以上都有不可能答案：a,d80、已知权值W=2, 3, 4, 7, 8, 9 构造出的哈夫曼树的带权路径长度WPL=?a、80b、33c、87d、113e、以上都不正确答案：a、8081、有向图有 12 个顶点，图中弧为：(Cl, C2), (C1, C4), (C1, C3), (C1, C12), (C9,C12), (C9, C10), (C9, C11), (C4, C5), (C2, C3), (C10, C12), (C11, C6), (C3, C5),(C3, C7), (C3, C8), (C5, C7), (C6, C8),该图的拓扑排序可能的序列是a、C1C2C3C4C5C7C9C10C11C6C12C8b、C9C10C11C6C1C12C4C2C3C5C7C8c、C7C2C3C4C5 C1- -C9C10C11C6C12C8d、C8C10C11C6C1C12C4C2C3C5C7 C9e、以上都不正确答案：a,b82、下述正确的是a、有向图可以用邻接矩阵表示b、第一个顶点的入度为第一列中非零元素之和c、第一个顶点的出度为第一行中非零元素之和d、有向图不能用邻接表e、以上都不正确答案： ABC 83、对顺序查找叙述正确的是a、逐个进行比较b、元素较多时，查找效率低c、算法简单，适应面广d、不要求表的存储结构e、记录是否有序均可 答案：ABCDE84、在单链表中，若删除p所指结点的后继结点，贝y执彳丁a、q = p-next,p-next 二 q-next, free(q)b、q = p-next, p-next 二 p-next-next,free(q)c、s-next=p-next,free(p)d、p-next=s,free(p)e、q = p-next, q-next 二 p-next,free(q) 答案：AB85、广义表(a,b,c,d)的表头是_a，表尾是_(b,c,d)86、生成平衡二叉树时平衡旋转类型有四种，LL、RR、LR、RL