数据结构试卷A

共8页第1页2009级《数据结构》课程试题（A卷）合分人：复查人：一、单选题：（每题2分，共30分）（说明：将认为正确答案的字母填写在每小题后面的括号内）分数评卷人1.数据元素是（）。A.数据不可分割的最小单位B.性质相同的数据集合C.数据的逻辑关系D.数据的基本单位，通常作为一个整体处理2.表长为n的顺序存储的线性表，当在任何位置插入一个元素概率相等时，插入一个元素所需移动元素的平均个数为（）．A.nB.(n-1)/2C.n/2D.O(n)3.在双循环链表的*p结点之后插入*s结点的操作是()A.p-next=s;s-prior=p;p-next-prior=s;s-next=p-nextB.p-next=s;p-next-prior=s;s-prior=p;s-next=p-nextC.s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;D.s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;4.一个栈的入栈序列是abcde,则栈的不可能的输出序列是（）A.edcbaB.decbaC.dceabD.abcde5.循环队列的队满条件为（）A.（sq.rear+1）%maxsize==(sq.front+1)%maxsizeB.(sq.rear+1)%maxsize==sq.front+1;C.(sq.rear+1)%maxsize==sq.frontD.Sq.rear==sq.front6.关于串的堆分配存储的描述正确的是（）A.串的堆分配存储是把串建成一个堆B.串的堆分配存储在进行字符串连接时，会出现截维现象C.串的堆分配存储是在程序执行过程中动态分配一组地址连续的存储单元存放串值字符序列题号一二三四总分分数共8页第2页D.串的堆分配存储是为串分配一个静态数组7.二维数组A[10..20,5..10]采用行序为主的方式存储,每个数据元素占4个存储单元,且A[10,5]的存储地址是1000,则A[18,9]的存储地址是()A.1208B.1212C.1368D.13648.已知完全二叉树有26个结点，则整棵二叉树有（）个度为1的结点。A.0B.1C.2D.139.设森林T中有4棵树，结点个数分别是n1、n2、n3、n4，当把森林T转换成一棵二叉树后，根结点的右子树上有（）个结点。A．n1-1B.n1C.n1+n2+n3D.n2+n3+n410.哈夫曼树的带权路径长度是（）A.所有结点权值之和B.所有叶结点带权路径长度之和C.带权结点的值D.除根以外所有结点权值之和11.在含n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为（）。A.eB.2eC.n2-eD.n2-2e12.一个具有N个顶点的无向图中，要连通全部顶点至少需要（）条边。A.NB.N+1C.N-1D.N/213.在长为ｎ的顺序表中顺序查找，在查找不成功时，与关键字比较的次数为（）。Ａ．ｎ＋１Ｂ．１Ｃ．ｎＤ．ｎ－１14.在采用链地址法处理冲突所构成的哈希表上查找某一关键字，在查找成功的情况下，所探测的这些位置上的键值（）。Ａ．一定都是同义词Ｂ．不一定都是同义词Ｃ．都相同Ｄ．一定都不是同义词15.用某种排序方法对关键字序列{25，84，21，47，15，27，68，35，20}进行排序时，关键字序列的变化情况如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84则采用的排序方法是（）。A．选择排序B．希尔排序C．归并排序D．快速排序共8页第3页二、按要求解答下列问题：（每小题5分，共30分）分数评卷人1.算法效率和算法使用的策略、问题规模、书写语言、算法运行的软硬件环境等有关系，简要说明使用算法时间复杂度度量算法效率的思想。2.证明：对任何一棵二叉树T，如果终端结点数为n0，度为2的结点数为n2，则n0=n2+13.假设有5项活动，每项活动要求的前驱活动如下：C1：无；C2：C1，C3；C3：C1；C4：C3，C5C5：C2，C3；试根据上述关系，（1）画出相应的有向图：（2）写出拓扑排序序列；共8页第4页4.含12个结点的平衡二叉树的最大深度是多少（设根结点的深度为1）？画出一颗这样的树。5.判别下面的每个结点序列是否表示一个堆，如果不是，请把它调整为一个堆。（1）100，90，80，60，85，75，20，25（2）100，70，50，20，90，75，60，256.关键字序列：22、41、53、46、30、13、01、67，h(key)=keymod11,表长为11，用线性探测再散列处理冲突，试填写下表并计算每个关键字的冲突次数、比较次数和平均查找长度。012345678910哈希表冲突次数比较次数ASL=共8页第5页三、应用题：（共10分）分数评卷人已知AOE网代表某个工程，如下图，解答下列问题：（1）画出该AOE网的邻接表；（2）指出该网的关键路径和该工程最早几天完成；（3）如果要求整个工期提前2天完成，该如何安排各个活动的时间，写出所有可能的调整方案？（要求应该尽可能少地改变活动的原有时间，并假设每个活动的持续时间要么不提前，要么只能提前1天；）a3=2a5=6a4=4a1=4V4V1V3V2a2=3共8页第6页四、算法设计题：（每题10分，共30分）分数评卷人1.已知二叉排序树T非空，树中的每个结点的结构为：StructNode{intdata;StructNode*lchild,*rchild;}试编写算法对二叉排序树中的数据按从大到小顺序输出。共8页第7页2.已知Q是非空队列，S是一空栈，编写一个算法，仅用队列和栈的基本操作和少量工作变量将队列Q的元素逆置。共8页第8页3．给定整型数组B[m][n],已知B中数据在每一维方向上都是按从小到大的次序排列，且整型变量x在B中存在，编写程序找出满足B[i][j]=x的i,j值，要求比较次数不超过m+n次。