数据结构模拟试题6

1、数据结构模拟试题(六) 20分，非选择题80分，满分100分 本试卷分两部分，第一部分为选择题，第二部分为非选择题；选择题 考试时间150分钟。 第一部分选择题 、单项选择题(本大题共 20小题，每小题1分，共20 分) 在每小题列出的四个选项中只有一个选项是符合题目要来的，请将正确选项前的字母旗在题后的括号内 1 .每一个存储节点不仅含有一个数据元素，还包含一组指针，该存储方式是【】 A.顺序存储B.链式存储 C.索引存储D.散列存储 2下列算法的时间复杂度是【】 for (i = 0 ； i next = s； f = S ； B. f next = s； r = S ； C. S nex

2、t = r ； r = S ； D. S next = f ； f = S ； 6. 一个栈的入栈序列是 1,2,3,4 ，则栈的不可能的输出序列是 :【 】 A. 3, 4, 2, l B.3, 2, 4, l C. l, 2, 3, 4 D. 4, 3, 1, 2 7. 设 s3 =” 1AM”，s4 = =” A TEACHER,贝U strcmp (s3,s4 ) =【 】 A. I AM B. I AM A TEACHER C. I AMA TEACHERD. A TEACHER 若采用折半(二分)查找，则 时间复杂度为。 16. ISAM的中文意思是 ，采用索引结构。 三、名词解释

3、(本大题共 5小题，每题3分，共15分) 1存储密度 2栈的“上溢” 3带状矩阵 4完全二叉树 5.图 四、简答题(本大题共 5小题，每题5分，共25分) 1简述在单循链表上尾指针取代头指针的作用。 2简述栈的基本运算。 3串的链式存储与串的顺序存储相比，在哪些操作上效率更高？ 4以数据集 4, 5, 6, 7, 10, 12, 18为节点数值构造霍夫曼树。 5设数据序列为 D = 13 , 28, 72, 5, 16, 8, 7, 9, 34，请为D组织散列表。散列函数为 H (K) =K%7 散列表的长度为 10 个单元，起始地址为 0，要求用线性探测再散列来解决冲突。并计算查找成功的平均

4、查 找长度。 五、应用题(本大题共 2 小题，每题 10 分，共 20 分) 1输入一字符串，检查其中是否含有匹配的小括号。当括号匹配时，按逆序输出括号中的字符，否则输出 错误信息。 2设有链式存储结构的二叉树，计算其中有双后继节点的节点的个数。 数据结构模拟试题(六)参考答案 、单选题答案 1. B 2 . B 3. D 4. B 5. B 6. D 7 . D 8 . C 9 . D 10 .D 11. B 12 .D 13 .B 14 .A 15 .B 16. B 17 .D 18 .C 19 .B 20 .B 、填空题 1.存储 2.起始 3.逻辑 4. p next S 5.栈队列

5、6. 2 7. n* ( nI ) /2 I 8. 5 3 9. 2k-1 10.高度或深度 11 .递增 12.零 13. 0(n) 14. 3 15. 0( n) 0(Iog 2n) 16.索引顺序存取方法 静态 三、名词解释 1指节点数据本身所占的存储量和整个节点结构所占的存储量之比。 2当栈满的时候，不能进栈，否则将产生空间溢出，简称“上溢”。上溢是一种出错状态，应该设法避免。 3所有非零元素均集中在以主对角线为中心的带状区域的矩阵。 4在一棵二叉树中， 除最底层外， 其余层都是满的， 并且最底层或者满的或者在右边缺少连续若干个节点。 5图G由两个集合V和E组成，记为G=( V, E

6、),其中V是顶点(节点)的有穷非空集合，E是由V中 顶点的序偶组成的有穷集，这些序偶称为边。 四、简答题 1 在用头指针表示的单循环链表中，找开始节点ai的时间是0( 1)，然而要找到终端节点。则需从头指针 开始遍历整个链表，其时间是O(n) 。在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头 指针表示的单循环链表就显得不够方便。如果改用尾指针来表示单循环链表，则查找开始节点ai终端节点 an都很方便，查找时间都是 0( I )o 2 队列的基本运算用以下六种： Initstake( S) 构造一个空栈 S StakeEmPty( S) 判栈空。若S为空栈，则返回真值，否则返回假值

7、。 stakeFuII( S) 判栈满。若S为满栈，则返回真值，否则返回假值。此操作只适用于栈的顺序存储结构。 Push( S， x) 进栈。若栈S非满，则将元素X插入S的栈顶。 Pop( S) 退栈。若栈S非满，则删去S的栈顶元素，并返回该元素。 StakeTop ( S) 取栈顶元素。若栈 S非空，则返回栈项元素，但不改变栈的状态。 3答：链式存储在串的插入和删除操作上效率较高，因为它只需做查找工作，而不需移动后面的元素。 4. 5性探测再散列的散列表如下图： 0123456789 28 8 72 16 7 5 13 9 34 1 1 1 2 5 1 1 6 3 查找成功的平均查找长度为A

8、SL = 119 ( l *5 + 2+3+5+ 6)= 2.33 五、应用题 l converts。 char s; setstack(stack); scanf(%c, scanf(%c, break; case ) : while (top(stack.)1=) pintf(“ C ,ch); if(empty(stack) printf(“ C ,ch); else ch=pop(stack); scanf( “ %c， break; default:if(!empty(stack) push(stack); scanf(“ %c， if(!empty( stack) printf(“no match ” ); 2. int twochild(bt tree) int num1,num