数据结构试题2011.docVIP

单项选择题：1－0小题，每小题2分，共40分。在每小题给出的四个选项中，请选出一项最符合题目要求的选项。 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（ D ）。 for(int i=1;in/2;) i=2*i; A.O(n2)B.O(n) C.O(nlog2n) D.O(log2n) 若某线性表最常用的操作是存取指定序号的元素和在进行插入和删除运算，则利用A ）存储方式最节省时间。 A.顺序表B.双链表 C.带头结点的双循环链表D.单循环链表 某线性表中最常用的操作是在插入一个元素和删除第一个元素，则采用D ）存储方式最节省运算时间。 A.单链表B.仅有头指针的单循环链表 C.双链表D.仅有尾指针的单循环链表 A.125436 B.325641 C.342165 D.546231 若用数组A[60]存放循环队列的元素，已知头指针值为，当前队列中有0个元素A.75 B.20 C.15 D.5 深度为6的完全二叉树（根结点的深度为0）至少有（ B ）个结点。? A.32?? B.64 C.127 D.128 解答：第0-5层全满，第6层1个，1+2+4+8+16+32+1=64个。 将一棵森林F转换为孩子兄弟链表表示的二叉树T，则F的后根遍历是T 的。 A.前序遍历B.中序遍历C.后序遍历D.层序遍历A.只有IIB.只有I和II C.只有III D.只有I和III? 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ A ）。 A. 85, 12, 81, 14, 84, 61 B. 82, 10, 81, 24, 78, 25 C. 11, 79, 67, 19, 26, 28 D. 2, 15, 61, 58, 23, 24 下列二叉树中，不满足平衡二叉树定义的是（??A ）。 A. B. C. D. ?下列叙述中，不符合m阶B-树定义要求的是（ D ）。 ?A．根结点至多有m-1个关键字???? B.所有叶结点都在同一层上?? ?C．各结点内关键字均升序或降序排列? D.每个结点至少有两棵非空子树 为提高散列（Hash）表的查找效率，可以采取的正确措施是（ D ）。 增大装载因子?? 设计冲突少的散列函数 处理冲突时尽量减少产生聚集（堆积）现象 A.只有IB.只有II C.只有I和II D.只有II和III?－小题。共分。（8分）假定用于通讯的电文仅由个字母C1, C2, …, C组成，各个字母在电文中出现的分别为, 3, 5, 6, 7，10, 12，试为这个字母设计哈夫曼树，要求画出哈夫曼树，写出各个字符的哈夫曼编码3 5 ∞ ∞ ∞ 4 ∞ 5 ∞ 3 2 ∞ ∞ 2 4 （1）写出图G的邻接矩阵A。（4分） （2）画出有向带权图G。（2分） （3）求图G的关键路径，并计算该关键路径的长度。（7分） （4）采用Dijkstra算法求编号为0的顶点到其余各顶点的最短路径。（5分） （3）关键路径为0—1(2(4(5，长度为3+4+2+4=13. （4）0(1:0,1,3 0(2:0,2,5 0(4:0,2,4,7 0(3:0,2,3,8 0(5:0,2,3,5,10 （9分）将关键字序列(SUN, MON, TUE, WED, THU, FRI, SAT)散列存储到一个下标从0开始的一维数组函数为：H(key) = 关键字中第一个字母在字母表中的序号 ，处理冲突采用探测再散列法……），要求装载因子为0.7请画出所构造的散列表。计算等概率情况下，查找成功的平均查找长度。为装填因子）： 和 计算查找成功，且计算正确，可共给2分。若解答部分正确，酌情给分。 算法设计题。2－2小题。共25分。要求：（12分）m个整数的递增有序数组a[m]和有n个整数的递减有序数组b[n]，试写出算法，将数组a和b归并为递增有序数组c[m+n] （要求算法的时间复杂度为O(m+n)）。 答：（1）?描述算法的基本设计思想（2）?描述算法的详细实现步骤（3）?根据设计思想和实现步骤，采用语言描述算法，关键处注释 （13分）设含有n个元素的线性表A=(a1, a2, a3,…, an-1, an)，用带头结点的单链表表示。试编写一个算法，对A进行调整，使得所有偶数项排在奇数项之前，即：当n为偶数时，A=(a2,a4,…,an,a1,a3,…,an-1)；当n为奇数时，A=(a2,a4,…,an-1,a1,a3,…,an)，并分析算法的时间复杂度。 答： （1）?描述算法的基本设计思想（2）?描述算法的详细实现