数据结构答疑材料.doc

数据结构答疑材料1、数据结构是一门研究_的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 （）A、数值 B、 非数值 C、 字符 D、数字答案：B2、快速排序的分区结果唯一吗？答案：不唯一，取决于枢轴元素的选取。3、小顶堆的堆顶元素是序列中 （ ）A、最大的元素B、次大的元素C、最小的元素D、次小的元素答案：C4、设s 1=“GOOD”,s2=“BYE”则字符串s1和s2连接后的结果是 （ ）a、BYE GOODb、GOOD BYE c、BYEDGOODd、GOODBYE答案：d5、 在一个单链表中，已知p所指结点，若在p之后插入s结点，则执行?答案：s-next=p-next; p-next=s6. 数据的逻辑结构中非线性结构有A、集合B、线形结构C、树形结构D、网状结构E、链式结构答案：C树形结构， D网状结构7. 线性结构中元素之间存在_关系，树形结构中元素之间存在_关系，图形结构中元素之间存在_关系A、一对一，多对多，一对多B、一对多，一对一，多对多C、一对一，一对多，多对多D、多对多，一对多，一对一E、以上都不正确答案：C、一对一，一对多，多对多8广义表（a）,a）的表尾是_ （ ）A、a B、b C、（a） D、(a)答案： C9 算法有哪些重要特性?答案：1有穷性2确定性 3可行性 4有输入5有输出10 数据结构是一门研究什么内容的学科？答案：数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。11设有一个空栈，现在有输入序列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。12 两个串相等的条件是A、长度相等 B、对应位置的字符相等 C、存储位置相同D、存储结构相同 E、以上都是答案：AB13顺序查找适用于存储结构为_的线性表A、散列 B、顺序或者链式 C、压缩 D、索引 答案：B14设哈希表长m=16，哈希函数H（key）=key%13；表中已有3个结点H（19）=6 H(27)=1 H(23)=10 其余地址为空，如用线性探测再散列处理冲突，关键字14的地址是 选项:a、1b、2c、3d、0e、以上都不正确答案：b解析：14%13=1，因为1地址中已经有元素，所以需要再哈希求地址：（14+1）%13=215 最常用的哈希函数构造方法为A、除留余数法B、直接定址法 C、折叠法 D、数字分析法答案：A16 一个链式队列中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算是_A、r-next=sB、r=sC、s=rD、s=r-nextE、s-next=r答案：AB17广义表L=( a, (x,y), (x) )的长度是_,深度是_A、 3 3B、C、 D、 E、 答案：A、 3 3解析： 广义表LS中的直接元素的个数称为LS的长度;广义表LS中括号的最大嵌套层数称为LS的深度。18在一个单链表中，已知p所指结点，若在p之后插入s结点，则执行_.A、s-next=p-nextB、 p-next=s C、p-next = s-nextD、p-next=s E、p-next = p-next-next答案：AB19顺序栈S为空的判定条件a、 S.top=S.baseb、S=S.basec、S.top=Sd、没有正确答案答案：a20、什么叫循环队列 如何区分空满循环队列?当队列采用顺序存储结构表示时，为避免空间浪费问题发生，便提出了循环队列，相当于把顺序队列头尾相接形成一个环状空间。判断循环队列是空还是满，通常有两种处理方法：其一是在存储区域中占用一个元素空间设一个标志位以区别队列是空还是满；其二是少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置（指环状的下一位置）上”作为队列呈满状态的标志。通常采用第二种方法。21一个队列的入队序列是1、3、4、2，则队列的首次输出元素是_。 ()A、3 B、 2 C、 1 D、 4答案：C22 计算机算法指的是（1），它必须具备（2） 这三个特性。(1) A计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 答案：C. B.23从逻辑上可以把数据结构分为（ ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构答案：C24数据的存储结构由哪四种基本的存储方法实现？ 答案：四种表示方法（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。（3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。25线性表是具有n个（ ）的有限序列（n0）。 A表元素 B字符 C数据元素 D数据项 E信息项 答案：C26若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=i=n+1)。A. O(0) B. O(1) C. O(n) D. O(n2) 答案：C27线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？答案：（1）选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O（1）。 （2）选顺序存储结构。顺序表可以随机存取，时间复杂度为O（1）。 28若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？答案：采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。29线性结构包括_、_、_和_。线性表的存储结构分成_和_。答案：线性表 栈 队列 串 顺序存储结构和链式存储结构30对于栈操作数据的原则是（ ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序答案：B.31一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ ）。A. 不确定 B. n-i+1 C. i D. n-i答案：B32有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 答案：C.33 栈和队列的共同点是（ ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点答案：C34 判断：栈与队列是一种特殊操作的线性表。（ ）答案：35判断： 栈和队列都是线性表，只是在插入和删除时受到了一些限制。（ ）答案：36 名词解释：栈。答案：栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。37 名词解释：队列答案：队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。38 若元素的进栈序列为：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出栈序列。39、什么叫串的模式匹配算法答案：就是给定一个串和子串，定位字串在串中位置的算法。40 下面关于串的的叙述中，哪一个是不正确的？（ ）A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储答案：B41 串的长度是指（ ）A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数答案：B42、设s =“I AM A STUDENT”,则字符串的长度 Length(s) ？A、11B、12C、14D、1543空格串是指_(1)_，其长度等于_(2)_。答案：(1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数44串是一种特殊的线性表，其特殊性表现在_(1)_；串的两种最基本的存储方式是_(2)_、_(3)_；两个串相等的充分必要条件是_(4)_。答案：(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等45描述以下概念的区别：空格串与空串答案：空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。46、广义表有两个特殊的基本运算答案： 取表头head(LS)：取表中的第一个数据元素，不能对空表操作。 取表尾tail(LS);取除表头外，其余数据元素构成的子表，不能对空表操作。47广义表（a,b,c,d）的表头是（ ），表尾是（ ）。A. a B.（） C.（a,b,c,d） D.（b,c,d）答案：C48广义表（a,(b,c),d,e）的表头为（ ）。 A. a B. a,(b,c) C. (a,(b,c) D. (a) 答案：A49、广义表（a,b,c,d）的表头是_，表尾是_A、b B、（a）C、a D、（b,c,d）E、b,c,d答案：B、（a） D、（b,c,d）50 已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE答案：D51、若采用孩子兄弟链表作为树的存储结构，则树的先根遍历应采用二叉树的_。A、层次遍历B、先序遍历C、中序遍历 D、后序遍历答案：B52、二叉树的5个性质 53 有关二叉树下列说法正确的是（ ）A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2答案：B55 一棵树高为K的完全二叉树至少有（ ）个结点A2k 1 B. 2k-1 1 C. 2k-1 D. 2k答案：C56 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。ACBEFDA B FEDCBA C CBEDFA D不定答案：A57 线索二叉树是一种（ ）结构。A 逻辑 B 逻辑和存储 C 物理 D线性答案：C58 由3 个结点可以构造出多少种不同的二叉树？（ ）A2 B3 C4 D5答案：D59 从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。答案：树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。60 树和二叉树之间有什么样的区别与联系？答案：树和二叉树逻辑上都是树形结构，区别有以上题1所述三点。二叉树不是树的特例。61 请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。答案：线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，也只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲（根无双亲），从这个意义上说存在一（双亲）对多（子女）的关系。广义表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表均属非线性结构。但在以下意义上，又蜕变为线性结构。如度为1的树，以及广义表中的元素都是原子时。另外，广义表从元素之间的关系可看成前驱和后继，也符合线性表，但这时元素有原子，也有子表，即元素并不属于同一数据对象。62 已知完全二叉树有30个结点，则整个二叉树有多少个度为0的结点？答案：1563、假设有向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（） A.n B.eC.2e D.ne答案：B64一个n个顶点的连通无向图，其边的个数至少为（ ）。An-1 Bn Cn+1 Dnlogn；答案：A65n个结点的完全有向图含有边的数目（）。An*n n（n） Cn2 Dn*（nl）答案：D66判断一个无向图是一棵树的条件是_。答案：有n个顶点，n-1条边的无向连通图67具有10个顶点的无向图，边的总数最多为_。答案：4568求图的最小生成树有两种算法，_算法适合于求稀疏图的最小生成树。答案：克鲁斯卡尔69下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括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）（Vi，V