数据结构试卷1数据构试卷1.doc

考试科目：数据结构与算法 （A卷） 注意事项：请将答案写在答题纸上，写在题册上的答案无效。 ………………………………………………………………………………………… 一、选择题(单选题，每题2分，共20分） 1、下列程序的时间复杂度为（　　　）。 int i=0, s=0； while（sn） { i++；s=s+i；} A. O（） B.O（n2） C. O（n） D.O（） 2. 二维数组A［10］［6］(即二维数组有10行，6列）采用行优先的存储方法，若每个元素占4个存储单元，已知元素A［3］［4］的存储地址为1000，则元素A［4］［4］的存储地址为（　　　） A.1020 B.1024 C.1036 D.1240 3.循环队列sq中，用数组elem［0…25］（循环队列长度为26）存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为11，则当前队列中的元素个数为（　　　）。 A.8 B. 16 C.17 D. 18 4.对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( )。 A. (e,f) 　　　 B. ((e,f))　　 C. (f) 　　　 　 D. ( ) 5.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）。 A. 0 B. 1 C. 48 D. 49 6.下列所示各图中是中序线索化二叉树的是( )。 7.在含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为（ ）。 A. e B.2e C. n2-e D. n2-2e 8.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，最后一个元素放在A[18]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 9.对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次快速排序的结果为（　　　） A.(5，1，4，3，6，2，8，7) B.(5，1，4，3，2，6，7，8) C.(5，1，4，3，2，6，8，7) D.(8，7，6，5，4，3，2，1) 10.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为 （35，51，24，13，68，56，42，77，93） （35，24，13，51，56，42，68，77，93） 所采用的排序方法是（ ）。 A. 插入排序 B. 冒泡排序 C. 快速排序 D. 归并排序 二、填空题（每题2分，共10分） 1、从空树起，依次插入关键字1l，27，35，48，31和34构造所得的平衡二叉树，在等概率查找的假设下，查找成功时的平均查找长度为__________。 2. 已知一棵哈夫曼树含有201个结点，则该树中有_________个叶子结点。 3、已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为_________。 4、已知一组关键字为{25，46，38，97，34，88，57，62，23，96}，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是______________。 5、对序列{55，46，13，05，94，17，42}进行基数排序，第二趟排序后的结果是_________。 三、应用题（每题6分，共30分） 1、给出字符串‘babababaa’在KMP算法中的next和nextval数组。 2、用迪杰斯特拉(Dijkstra)算法求下列图中从顶点V1到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。 3、如图所示的AOE网，在该网中，顶点表示事件，边表示活动，边上的权值表示活动持续的时间。求各个事件Vj的最早发生时间ve( j )和最迟发生时间vl( j )、活动ai的最早开始时间e( i )和最迟开始时间l( i )，并写求出所有关键路径。 4、采用哈希函数Ｈ(k)=k mod 13并用线性探测开放地址法处理冲突，在数组地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51构造哈希表，要求画哈希表示意图，并在等概率情况下查找成功的平均查找长度。 5. 已知3阶B-树如图所示。 画出插