《数据结构》复习题3.doc

一、判断题 1、已知一棵二叉树的前序序列和后序序列，一定能构造出该二叉树。( ) 2、数据的存储结构是数据及其逻辑结构在计算机中的物理表示。( ) 3、键值序列{A，C，D，E，F，E，F}是一个堆。( ) 4、栈是特殊的线性表，它的插入和删除分别在线性表的两端进行。( ) 5、线性表的链接存储其逻辑顺序与物理顺序总是一致的。（ ） 6、稀疏距阵压缩存储后，必会失去随机存取功能。（ ） 7、有向图用邻接表表示后，顶点i的出度等于邻接表中顶点i后链表的长度。( ) 8、向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（ ） 9、由树转换成二叉树，其根结点的右子树总是空的。( ) 10、归并排序的时间性能不随记录序列中关键字的分布而改变（与初始状态无关）。( ) 二、填空题（本题共10小题，每小题 2 分，共计 20分）。 （请将正确答案填入空格内，答案是确定和唯一的） 1、在数据结构中，从逻辑关系上可以把数据结构分成 集合、 、 、 、 2、设一个链栈的栈顶指针是top，栈中结点格式为data | next , 如果栈不为空，则出栈操作为 s=top； ; 。 3、实现查找的存储结构仅限于顺序存储结构，且其中元素排列必须是_______的48，65，50，36，45，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为________________________________________。 5、在一个长度为n的顺序表中，在第i个位置插入一个元素，则需要移动 个元素。 6、设单链表中指针p指向结点A，要删除A的后继结点(若存在)，则修改指针的操作为_______。 7、二维数组A［10］［20］, 采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［5］［6］的地址为 。 8、图的主要存储结构有两种，分别为： 和 。 9、已知二叉树中叶子数为40，仅有一个孩子的结点数为20，则总结点数是 。 10、快速排序平均时间复杂性为 ，平均空间复杂性 。 三、选择题） 1．线性表的顺序存储结构是一种( )的存储结构。 A．随机存取 B.顺序存取 C.索引存取 D.散列存取 2. 假设有两个串A和B，求B在A中首次出现的位置的操作，我们称为（ ）。 A.连接 B.模式匹配 C.求子串 D.求串长 3. 在有n个叶结点的哈夫曼树中，整棵树的结点个数为 。 A、2n ? B、2n-1 ? C、log2n ? D、2n+1 4. 在二叉树中，( )。 A. 无左孩子B. 无左孩子和右孩子. 无右孩子C. 有左孩子和右孩子 C. s-next=p-next; p=s; D. p-next=s; s-next=p; 7.设有一组初始关键字值序列为（49，81，55，36，44，88， 65），则利用希尔排序的方法，第一趟在子序列内进行插入排序的结果为（ ）。  A. 49，81，55，36，44，88，65 B. 36，44，49，55，65，81，88 C. 36，44，53，49，81，88，65 D. 88，81，65，55，49，44，36 8. 在顺序表{12、15、17、20、24、30、38、43、45、51、52}中，用二分法查找关键码38需做（ ） 次关键字比较。 A、2 B、3 C、4 D、5 9、散列技术中的冲突是指（ ）。 A、两个元素具有相同的序号 B、两个元素的键值不同，而其他属性相同 C、数据元素过多 D、不同键值的元素对应于相同的存储地址 10. 有n个结点的向图的边数最多为k=1; for（i=0；in；i++） for（j=0；jn；j++） A［i］［j］=k++； A. O（n2） B. O（n） C. O（2n） D. O（1） 13. 设循环队列的元素存放在一维数组Q[0‥30]中，队列非空时，front指示队头元素的前一个位置，re