《数据结构》模拟试卷（4）选择题（每小题2分，共20分）1、在决定选取何种存储结构时，一般不考虑（）。A、各结点的值如何B、结点的个数的多少C、对数据有哪些运算D、所用编程语言实现这种结构是否方便2、带头结点的双循环链表L为空表的条件是（）。A、L==NULLB、L→next==NULLC、L→prior==NULLD、L→next==L3、如果最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。A、单链表B、双向链表C、单循环链表D、顺序表4、向一个栈顶指针为hs的链栈中插入一个s所指向的结点时，则执行（）A、hs→next=s;B、s→next=hs→next;hs→next=s;C、s→next=hs;hs=s;D、s→next=hs;hs=hs→next;5、在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算是（）A、r=f→next;B、r=r→next;C、f=f→next;D、f=r→next;6、设矩阵A是一个对称矩阵，为了节省内存，将其下三角部分按行序存放在一维数组B[1..n(n+1)/2]中，对下三角部分中的任一元素a(i>j)在一维数组B中的下标K的值是（）A、i(i-1)/2+j-1B、i(i-1)/2+jC、i(i+1)/2+j-1D、i(i+1)/2+j7、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。A、2hB、2h-1C、2h+1D、h+18、根据5个字符使用频率设计的哈夫曼编码，不可能的是（）A、111，110，10，01，00B、000，001，010，011，1C、100，11，10，1，0D、001，000，01，11，109、一个有n个顶点的无向图最多有（）条边。A、nB、n(n-1)C、n(n-1)/2D、2n10、采用折半查找法查找长度为n的有序表时，每个元素的平均查找长度为（）。A、nB、nlognC、nD、logn二、填空题（每空2分，共30分）1、下面程序段的时间复杂度是________.I=s=0;While(s<n){i++;s+=i;}2、向一个长度为n的顺序表中的第i个元素（0≤i≤n-1）之前插入一个元素时，需向后移动____个元素。3、在一个单链表中的p所指结点之前插入一个s所指结点时，可执行以下操作：(1)s→next=p→next;(2)p→next=s;(3)t=p→data;(4)p→data=_____________;(5)s→data=_________;4、环形队列用数组A[0..MaxSize-1]存放其元素值。已知其头、尾指针分别为front和rear，则当前队列中元素个数是_________________________.5、设n行n列的下三角矩阵A已压缩存储到一维数组S[n(n+1)/2]中，若按行序为主序存储，则A[i][j]对应的S中的存储位置是_____________.(矩阵行、列均从0开始)6、已知广义表L=((x,y,z),(u,t,w)),从L中取出原子t的运算是_______________________。7、深度为k的完全二叉树至少有_______个结点，至多有______个结点。按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是________。8、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,那么它的先序遍历序列是_________。9、n个顶点的连通图至少有_______条边。10、已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是__________________________。11、分块查找中，若索引表及各块内均用顺序查找，则有偿使用900个元素的线性表分成____块最好。若分成25块，其平均查找长度为___________。三、简答题（每小题6分，共30分）1、稀疏矩阵A如下所示，请给出A的三元组表示和带行指针向量的单链表表示：1500220-150133000A==000-600000000910000000280002、设A是含有n个元素的整型数组，写出求该数组中最大元素的递归定义。3、请画出广义表LS=(a,(b,(c,())),(d,e))的存储结构图。4、有一份电文共使用6个字苻a,b,c,d,e,f,它们的出现频率依次为2，3，4，7，8，9。试画出对应的哈夫曼树，并求出每个字符的哈夫曼编码。5、对如右所示连通图，用普里姆算法从顶点1开始求最小生成树。写出按次序产生的边。四、算法设计题(每小题10分，共20分)1、有一个单链表（不同结点的数