模拟试题(10套).docVIP

模拟试题1 一、选择题(20分) 1．组成数据的基本单位是( )。 (A)数据项 (B)数据类型 (C)数据元素 (D)数据变量 2．线性表的链接实现有利于( )运算。 (A)插入 (B)读表元 (C)查找 (D)定位 3．串的逻辑结构与( )的逻辑结构不同。 (A)线性表 (B)栈 (C)队列 (D)树 4．二叉树第i(i≥1)层最多有( )个结点 (A)2i， (B)2i (C)2i-1 (D)2i一1 5．设单链表中指针p指向结点A，若要删除A之后的结点(若存在)，则修改指针的 操作为( )。 (A)P一＞next＝p一＞next一＞next (B)p＝P一＞next (C)p＝P一＞next一＞next (D)p一＞next＝p 6．设一数列的输入顺序为1，2，3，4，5，6，通过栈操作不可能排成的输出序列为( ) (A)3，2，5，6，4，1 (B)l，5，4，6，2，3 (C)2，4，3，5，1，6 (D)4，5，3，6，2，1 7．设字符中S1＝‘ASCDEFG’，S2＝‘PQRST’，则运算S＝Concat(Sub(S1,2,Length(S2))，Sub(S1，Length(S2)，2))后结果为( )。 (A)‘BCQR’ (B)‘BCDEF’ (C)‘BCDEFG’ (D)‘BCDEFEF’ 8．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第1个 元素，其存储地址为1，每个元素占用1个地址空间，则a85的地址为( )。 (A)13 (B)33 (C)18 (D)40 9．如果结点A有3个兄弟，且B为A的双亲，则B的度为( )。 (A)3 (B)4 (C)5 (D)1 10．线索化二叉树中某结点D，没有左孩子的主要条件是( )。 (A)D一＞Lchild＝NULL (B)D一＞1tag＝1 (C)D一＞Rchild＝NULL (D)D一＞1tag＝0 二、填空题(每空2分，共22分) 1．对于一个以顺序实现的循环队列Q[0…m—1]，队首、队尾指针分别为f和r，其判空的条件是____________，判满的条件是______________。 2．循环链表的主要优点是__________________。 3．给定一个整数集合{3，5，6，9，12}，画出其对应的一棵Huffman树__________ 4．在双向循环链表中，在指针p所指的结点之后插入指针f所指的结点，其操作为________________ 5．下面为朴素的模式匹配算法，请在算法的下划线处填上正确的子句 int index(s,t) string *s，*t; { i＝j＝0; while((i＜s一＞len)＆＆(j＜t一＞len)) if (s一＞ch[i]==t一＞ch[j]){ i=i+1; j=j+1; } else { i=_________________; j=_________________; } if(j==t-len) return(i-t-len); else return(-1); } 6．一个n×n的对称矩阵，如果以行或列为主序存人内存，则其容量为_________。 7．设F是森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的结点有______________。 8．先序序列和中序序列相同的二叉树为_________________。 9．已知一棵二叉树的中序遍历结果为DBHEAFICG，后序遍历结果为DHEBIFGCA，画出该二又树___________________。 三、应用题(16分) 1．设二叉树的顺序存储结构如下：(4分) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 E A F ^ D ^ H ^ ^ C ^ ^ ^ G I ^ ^ ^ ^ B (1)根据其存储结构，画出二叉树。 (2)写出按先序、中序、后序遍历该二叉树所得的结点序列。 (3)画出二叉树的后序线索化树。 2．一棵完全二叉树共有21个结点，现顺序存放在一个矢