自-2009多媒体-网络《数据结构》期末考题(answer) .doc免费

北京化工大学2０09／201０学年第一学期《数据结构》期末试题 班级: 　　 姓名： 　 　学号: 　 成绩: 一、选择题（共4０分)： 1 2 3 ４ 5 6 7 ８ 9 １0 Ｄ Ａ Ａ B C B A B C B 11 12 13 1４ 15 16 17 １8 1９ 20 Ｃ Ｂ A C Ｄ C C B Ｄ D 在长度为n的顺序表的第i（１≤i≤ｎ+1)个位置上插入一个元素，元素的移动次数为（　 ）。 A.ｉ-1 　 B.i 　　　 C.n-i 　 　D.ｎ-ｉ+1 已知一个顺序存储的线性表,设每个结点占k个存储单元，若第一个结点地址为 Lｏｃ1,则第i个结点的地址为( 　 ）。 A.Loc1 ＋（ｉ　–1)*　k 　　 　 　 Ｂ．Loｃ1+　i * k C.Lｏｃ1－　ｉ * ｋ 　 　Ｄ．Ｌoｃ1 +(i+１) * ｋ 将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点进行编号，根结点的编号为1,则编号为49的结点的左孩子编号为（ 　　）。 A.98 　 B.99 C．5０ 　　D 设长度为n的链队列用单循环链表表示,若只设尾指针，则出队操作的时间复杂度为（　　 )。 Ａ.Ｏ(1)　 Ｂ．O(ｌog２n) 　C.O(n)　 D．Ｏ(n2) 一个栈的入栈序列是ａ，ｂ,c,ｄ,e，则栈的不可能的输出序列是( 　 ）。 A．edcｂa B．decba C．dcｅaｂ 　 Ｄ.ａbcde。 深度为ｋ的二叉树,结点数最多有（ 　)个。 A.2k－1 B．2k －１ Ｃ．２k D.k 连通分量是（ ）的极大连通子图。 A．无向图 　 B．有向图 　 Ｃ.树　 　　D.图 下述几种排序方法中,要求内存量最大的是( ）。 A．插入排序 B．归并排序 　C．选择排序　　 D.冒泡排序 若在单链表中P所指结点不是最后结点,在p之后插入S所指结点，则执行( )。 A．　S－neｘｔ=P;Ｐ－next=S; 　B．S－＞ｎext=Ｐ-nexｔ；P-＞ｎext=S； C．S-next=Ｐ－＞nｅxt;P=S;　 D．P-＞neｘt=S；S-ｎeｘｔ=Ｐ; 10、已知图的邻接矩阵,则从顶点0出发按深度优先遍历的结点序列是（ 　 )。 1 １ 1 1 0 　1 　 　　　 　　A.　 0 2 4 ３ １ 5　6 ０ 0 1　 0　 0 1 　　　 　 Ｂ. ０　1 ３ 6 5 4 2 0　 0 0 　1　 ０　 ０ 　 　 　 　 1 1 0　　0 1 1　 0　 　 　　　　　 D． 0 3 6 １ 5 4 ２ 　 1 0 　1 １ 　0 1 ０ 　　 　0 0 　０　 1 1　 0 1 1　 1 0 ０　　0 　1　 0 11、若在线性表中采用折半查找法查找元素,该线性表应该( )。 　 A.　元素按值有序　　 　 　 　　 B.采用顺序存储结构 C. 元素按值有序，且采用顺序存储结构 D.　元素按值有序,且采用链式存储结构 1２、设语句x＋十的时间是单位时间，则语句: 　 for(i=l；i＝n;i+＋）　 X++; 　　 的时间复杂度为( )。 Ａ．O（l) B.O（ｎ) 　 C.O（ｎ２) 　 D.O(ｎ3) 1３、设Hａsh表长m=1４，Hａｓｈ函数Hash(key）＝kｅy%13，表中已有四个关键字,Aｄdｒ(15)＝2，Aｄdr(３8)=１2,Ａddr(6１)=９，Aｄdr(85)=１0,如果用二次探测法处理冲突,关键字为48的节点的地址是( ）。 A．8 　 Ｂ．9 C． 1４、判定一个循环队列QU(空间个数为ｍ)为空的条件是( 　 ）。 A.QU－＞reａr- QU一frｏnt＝=m　 　 B．QU－reａr—　QＵ－front－l==ｍ C．QＵ一＞front＝=ＱU一＞rear 　 　 　D．QU一fｒｏnt==QU-＞reaｒ＋l 15、假定在一棵二叉树中,双分支结点数为１5,单分支结点数为30，则叶子结点数为（ )。 A．15 　 B．４7 　C.１7 D． 16、在数据结构中，从逻辑上可以把数据结构分成( 　 )。 A.动态结构和静态结构 　 　　 B．紧凑结构和非紧凑结构 Ｃ.线性结构和非线性结构　 　 D.内部结构和外部结构 17、有8个结点的无向连通图最少有(