《数据结构问题答疑材料辅导教师马》由会员分享，可在线阅读，更多相关《数据结构问题答疑材料辅导教师马（12页珍藏版）》请在金锄头文库上搜索。
1、2009-2010 学年第二学期数据结构问题答疑材料1、怎么实现顺序表的查询？ 答案：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关 键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字 和给定值比较都不等，则表明表中没有所查记录，查找不成功。2、什么是连通分量？答案：在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两 个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。3、有向图有 12 个顶点，图中弧为：(Cl, C2), (Cl, C4), (Cl, C3), (Cl, C,(C9
2、, C, (C9， C10)，(C9， C11)，(C4， C5)，(C2， C3)，(C10， C12)，(C11， C6)，(C3， C5)，(C3，C7), (C3, C8) , (C5 , C7) , (C6 , C8),该图的拓扑排序可能的序列是a、Cl-C2-C3-C4-C5-C7-C9-Cl0-Cll-C6-Cl2-C8b、C9-Cl0-Cll-C6-Cl-Cl2-C4-C2-C3-C5-C7-C8c、C7-C2-C3-C4-C5- Cl- -C9-Cl0-Cll-C6-Cl2-C8d、C8-Cl0-Cll-C6-Cl-Cl2-C4-C2-C3-C5-C7- C9e、以上都不正确
3、答案： ab4、已知权值W=2, 3, 4, 7, 8 , 9 构造出的哈夫曼树的带权路径长度WPL=?答案：先得构造哈弗曼树 然后计算带权路径长度。哈弗曼树的带权路径长度为树中所有叶 子节点的带权路径长度之和。 wpl=2*(7+8) +2*9+3*4+4*(2+3) =30+l8+l2+20=805、无向图有8 个顶点 V1V8,边为(Vl , V2), (Vl , V3), (V2 , V4), (V2 , V5), (V3 , V6),( V3V7)( V4V8)(V5V8)(V6 V7) 该图广度优先遍历序列有可能为a、 VlV2V3V4V5V6V7V8b、 VlV2V4V5V8V3
4、V6V7c、 V8V4V5V2VlV3V6V7d、 VlV3V2V7V6V5V4V8e、以上都有不可能答案：广度优先遍历连通图的基本思想是： stepl、从图中某个顶点V0出发，并访问此顶点； step2、从V0出发,访问V0的各个未曾访问的邻接点Wl , W2 ,Wk;然后，依次从 W1,W2,Wk出发访问各自未被访问的邻接点。 step3、重复step2 ,直到全部顶点都被访问为止。按上述步骤 可知 Vl V2 V3 V4 V5 V6 V7 V8； Vl V3 V2 V7 V6 V5 V4 V8 是可能的序列6、在一个单链表中 已知 p 所指结点 若在 p 之后插入 s 结点 则执行? 答
5、案： s-next=p-next; p-next=s 7、数据的逻辑结构中非线性结构有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、算法有哪些重要特性?4有输入5有输出答案： 1有穷性 2确定性3可行性 11、数据结构是一
6、门研究什么内容的学科？ 答案：数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对 象间的关系和施加于对象的操作等的学科。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、存储
7、结构相同E、以上都是答案：AB14、顺序查找适用于存储结构为的线性表A、散列B、顺序或者链式C、压缩D、索引答案： B15、设哈希表长m=16，哈希函数H (key) =key%13；表中已有3个结点H (19) =6H(27)=1H(23)=10 其余地址为空，如用线性探测再散列处理冲突，关键字14 的地址是 选项:a、1b、2c、3d、0e、以上都不正确答案： b解析： 14%13=1，因为 1 地址中已经有元素，所以需要再哈希求地址：(14+1) %13=216、最常用的哈希函数构造方法为A、除留余数法B、直接定址法C、折叠法D、数字分析法答案： A17、一个链式队列中，假设f和r分别为
8、队首和队尾指针,则插入s所指结点的运算是A、r-next=sB、r=sC、s=rD、s=r-nextE、s-next=r答案： AB18、广义表 L=( a, (x,y), (x) )的长度是,深度是A、33B、23C、32D、43E、34答案：A、33解析：广义表LS中的直接兀素的个数称为LS的长度;广义表LS中括号的最大嵌套层数称为 LS 的深度。19、在一个单链表中，已知 p 所指结点，若在 p 之后插入 s 结点，则执行A、s-next=p-nextB、p-next=sC、p-next = s-nextD、p-next=sE、p-next = p-next-next答案：AB 20、顺
9、序栈S为空的判定条件选项:a、S.top=S.baseb、S=S.basec、S.top=Sd、没有正确答案答案： a21、一个队列的入队序列是 1、 3、 4、 2，则队列的首次输出元素是（）A、3B、 2C、 1D、 4答案： C22、计算机算法指的是（1），它必须具备（2）（1）A.计算方法 B.排序方法 法（2）A.可执行性、可移植性、可扩充性C. 确定性、有穷性、稳定性 答案： C. B.这三个特性。C. 解决问题的步骤序列 D. 调度方B. 可执行性、确定性、有穷性D. 易读性、稳定性、安全性23、 从逻辑上可以把数据结构分为（）两大类。A. 动态结构、静态结构B.顺序结构、链式结
10、构C. 线性结构、非线性结构D.初等结构、构造型结构答案： C.24、数据结构是一门研究什么内容的学科？答案 .数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间 的关系和施加于对象的操作等的学科。25、数据的存储结构由哪四种基本的存储方法实现？答案：四种表示方法（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数 据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针 指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、 删除
11、等），但存储空间开销大（用于指针），另外不能折半查找等。（3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表， 索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态 特性。（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地 址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存 储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。26、线性表是具有n个（ ）的有限序列（n0）。A.表元素 B.字符 C.数据元素D.数据项E.信息项答案：C27、若长度为n的线性表采
12、用顺序存储结构，在其第i个位置插入一个新元素的算法的时间 复杂度为（ ） （1=i=n+1）。A. O（0） B. O（1）C. O（n）D. O（n2）答案： C28、线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表 的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线 性表中的元素，那么应采用哪种存储结构？为什么？答案 （1）选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的 影响，插入、删除时间复杂度为
13、0 （1）。（2）选顺序存储结构。顺序表可以随机存取，时间复杂度为0 （1）。29、若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什 么？答案：采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空 间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。30、 线性结构包括、 、 和。线性表的存储结构分成和答案：线性表 栈 队列 串顺序存储结构和链式存储结构31、对于栈操作数据的原则是（ ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 答案： B.32、一个栈的输入序列为123n,若输出序列的第一个元素是n,输出第i （1
14、=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、判断：栈与队列是一种特殊操作的线性表。（）答案：V 36、判断： 栈和队列都是线性表，只是在插入和删除时受到了一些限制。（ ） 答案：V 37、名词解释：栈。 答案：栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一 端叫栈底。最后插入的兀素最先删除，故栈也称后进先出（LIFO）表。38、名词解释：队列 答案：队列是允许在一端插入而在另一端删除的线
