资源描述：
《数据结构试卷及答案2套》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6页共6页数据结构试卷1一、单项选择题：(每小题2分，共20分)1.在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的数据平均比较次数为________。A.nB.n/2C.(n+1)/2D.(n-1)/22.不带头结点的单链表first为空的判定条件是_________。A.first->next==NULL;B.first==NULL;C.first->next==first;D.first!=NULL;3.栈的插入和删除操作在__________进行。A.栈顶B.栈底C.任意位置D.指定位置4.假定一个链式队列的队头和队尾指针
2、分别为front和rear，则判断队空的条件为__________。A.front==rearB.front!=NULLC.rear!=NULLD.front==NULL5.设有一个广义表A((x,(a,b)),(x,(a,b),y))，运算Head(Head(Tail(A)))的执行结果为________。A．yB．(a,b)C．(x,(a,b))D．x6.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于_________。A.nB.n-1C.n+1D.2*n7.利用n个值作为叶结点的权重，生成的霍夫曼树中共包含有_________个结点。A.nB.n+1C
3、.2*nD.2*n-18.设无向图的顶点个数为n，则该图最多有________条边。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)9.任何一个无向连通图的最小生成树_________。A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在10.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为_______排序法。A．选择B.二路归并C.交换D.插入二、填空题（每空1分，共20分）1.数据结构是一门研究非数值计算的程序设计问题中计算机的____________以及它们之间的______
4、_____和运算等的学科。2.顺序表中逻辑上相邻的元素的物理位置________相邻。单链表中逻辑上相邻的元素的物理位置__________相邻。3.在单链表中，除了首元结点外，任一结点的存储位置由___________________指示。4.________答案参见我的新浪博客：http://blog.sina.com.cn/s/blog_3fb788630100muda.html第6页共6页是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。5.设有二维数组A[0..19,0..10]，其每个元素占两个字节，第一个元素的存储地址为1000，
5、若按行优先顺序存储，则元素A[4,6]的存储地址为________，按列优顺序存储，元素A[4,6]的存储地址为__________。6.按照二叉树的定义，有3个结点的二叉树有________种形态。7.具有n(n>0)个结点的完全二叉树的深度为__________。8.含有n个顶点e条边的无向连通图，利用Kruskal算法生成最小代价生成树其时间复杂度为__________，利用Prim算法生成最小代价生成树时间复杂度为__________。9.从有序表(12,18,30,43,56,78,82,95)中折半查找元素56时，其查找长度为________。10.快速
6、排序在平均情况下的时间复杂度为___________，在最坏情况下的时间复杂度为____________。三、应用题（每小题5分，共30分）1.输入下列整数序列，17，31，13，11，20，35，25，8，4，11，24，40，27，画出建立的二叉排序树，最后分别图示将9插入，86删除后的二叉排序树。2.已知二叉树T的中序遍历序列为DIGJLKBAECHF，后序遍历序列为ILKJGDBEHFCA,请画出该二叉树，并写出先序序列。1563243图13.对于如图1所示的有向图，试给出(1)每个顶点的入度和出度；(2)邻接矩阵；(3)邻接表；4.试对图2所示的AOE网络
7、，解答下列问题。(1)求每个事件的最早开始时间Ve（i）和最迟开始时间Vl(i)。(2)求每个活动的最早开始时间e()和最迟开始时间l()。图2(3)确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。5.字符a,b,c,d,e,f,g的使用频度分别是0.07,0.09,0.12,0.22,0.20,0.27,0.03，写出a,b,c,d,e,f,g的Huffman编码(在构造哈夫曼树时，要求左子树根结点的权值小于等于右子树根结点的权值)。6.设哈希函数H(K)=k%13,给定键值序列为87,25,31,8,27,13,68
