2、.对长度为10的表作选择(简单选择)排序,共需比较(A)次关键字。A.45B.90C.10D.1104.下列算法suanfa2(n)的时间复杂度为(A)。intsuanfa1(intn){inti,x=0；for(i=0；i<5；i++)for(j=1；j<=n；j++)x+=2；returnx；}A.O(n)B.O(n5)C.O(5n)D.O(n2)5.线性表在(B)时,宜用顺序表作存储结构。A.经常作插入、删除B.经常随机存取C.无足够连续存储空间D.经常作动态查找6.设广义表LS=((a,b),c,(d,e)),执行操作
3、GetTail(GetHead(LS))后的结果是(A)。A.(b)B.bC.(c,(d,e))D.(a,b)7.深度为k的满二叉树有(C)个叶子。A.k2-1B.2K-1-1C.2K-1D.k28.有16个顶点的无向图最多可能有(D)个连通分量。A.32B.8C.256D.169.(C)是'Hua**Zhong**Da'的子串。A.HuaB.zhongC.'*Da'D.'HuaZhongDa'第8页（共8页）10.字符串的长度指的是串中(B)的个数。A.不同字符B.字符C.字母D.字母和数字二、多项选择题1.设哈希(Hash
4、)函数为H(k)=kMOD7,其中k是关键字,MOD为取模(求余)运算，下列关键字(ACD)是同义词。A.29,22,15B.1,2,3,4C.23,16,9D.7,14,492.一个算法具有(AC)等特点。A.可行性B.健壮性C.确定性D.至少有一个输入量3.对单链表可以进行(BCD)的操作A.折半查找B.顺序查找C.删除结点D.插入结点4.若依次进栈的元素为a,b,c,d,可得到出栈的元素序列(ACD)。A.a,b,c,dB.c,a,b,dC.b,c,d,aD.d,c,b,a三、填空题1.有向图的存储结构有___邻接表、逆
5、邻接表、十字链表__等表示法。2.若7行6列的数组a以列序为主序顺序存储，基地址为1024,每个元素占2个存储单元,则第3行第5列的元素(假定无第0行第0列)的存储地址是_1084_。3.折半查找有序表(4,6,7,8,9,10,12,20,24,37,77,110),若查找值为9的元素,它将依次与表中元素___10,7,8,9_比较大小；若查找值为80的元素,它将依次与表中元素___10,24,77,110__比较大小。4._____树中各结点的层的最大值___称为树的深度。10.有n(n>0)个结点的完全二叉树的深度为él
6、og2(n+1)ù或ëlog2n+1û或ëlog2nû+1。5._______线性表中元素的数目______称为线性表的长度。6.____限定在表头作删除,在表尾作插入_____的线性表称为队列。7.设n个元素的线性表顺序存储,若在它的第i个(1≤i≤n)元素之后插入一个新元素,共需移动____n-i___个元素。8.构造Hash函数的方法有直接定址法、随机数法、_数字分析法、除留余数法、平方取中法、折叠法__等。9.对n个记录的表进行简单选择排序,共计需要进行__n(n-1)/2_次比较关键字,在最坏情况下,共计交换___n
7、-1___对记录。10.字符串A中_连续字符组成子序列_称为串A的子串,_仅由空格字符组成的字符串称为空格串。11.深度为k(k>0)的满二叉树共有_____2k-1-1__个非叶子。12.在有向图G中,以顶点i为__弧尾的弧_的数目称为i的出度。四、画图题第8页（共8页）1.试画出下列稀疏矩阵以行序为主序的三元组表。稀疏矩阵参考答案：1.行序为主序的三元组表。行号列号值13182133424536612342.下列树的双亲表示法:参考答案：2.下列树的双亲表示法:3.试画出下列有向图G的逆邻接表。有向图G参考答案：3.有向图
8、的逆邻接表:第8页（共8页）4.二叉树T的顺序存储结构:参考答案：4.二叉树T的顺序存储结构:5.已知二叉树的前序遍历序列和中序遍历序列分别是：B,A,C,D,E,F和B,D,C,E,A,F试画出该二叉树。参考答案：5.前序遍历序列和中序遍历序列分别是：B,A,C,D,E,F
