20121b普教《数据结构》b数据结构试题.doc

湖北文理学院 2011－2012 学年度下学期 《数据结构与算法》试卷B 专业：计算机科学与技术 姓名： 学号： 班级： 题 目 一 二 三 四 五 总分 满 分 10 20 18 22 30 100 得 分 得分 评卷人 一、判断题（本题共10小题，每小题1分，共计10分）。 （正确的打√，错的打×） 1、空串和空格串是相同的。( ) 2、数据的存储结构是数据及其逻辑结构在计算机中的物理表示。( ) 3、大顶堆（最大堆）中，最大值一定为根结点。( ) 4、栈是特殊的线性表，它的插入和删除分别在线性表的两端进行。( ) 5、稀疏矩阵一般采用三元组顺序表方法压缩存储。( ) 6、 若二叉排序树（有哪些信誉好的足球投注网站树）中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。( ) 7、有向图用邻接表表示后，顶点i的出度等于邻接表中顶点i后链表的长度。( ) 8、链接线性表是顺序存取的线性表。( ) 9、哈希函数进行模除取余时，最好取素数进行模除。（ ） 10、归并排序是一种稳定的排序算法。（ ） 得分 评卷人 二、填空题（本题共10小题，每小题 2 分，共计 20分）。 （请将正确答案填入空格内，答案是确定和唯一的） 1、在数据结构中，从逻辑上可以把数据结构分成 和 。 2、限在表尾进行插入和删除操作的线性表称为 。 3、实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是_______的 。 7、深度为k二叉树中最多可有 个结点。 8、任意写出二叉树的两种存储结构，分别是 和 。 9、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数是 。 10、快速排序平均时间复杂性为 ，平均空间复杂性 。 得分 评卷人 三、选择题（本题共18小题，每小题 1分，共计 18 分）。 （从下列答案中选出一个正确答案，并将对应的字母填入括号内） 1．线性表的顺序存储结构是一种( )的存储结构。 A．随机存取 B.顺序存取 C.索引存取 D.散列存取 2. 假设有两个串A和B，求B在A中首次出现的位置的操作，我们称为（ ）。 A.连接 B.模式匹配 C.求子串 D.求串长 3. 先遍历左子树，再遍历右子树，然后再访问该结点，这种遍历称为（ ）。 A.前序遍历 B.中序遍历 C.层次遍历 D.后序遍历 4.在完全二叉树中，若一个结点是叶结点，则它没有( ) A. 左孩子结点B. 右孩子结点C. 左孩子结点和右孩子结点D. 左孩子结点，右孩子结点和兄弟结点A．左孩子一定为空指针 B. 右孩子一定为空指针 C. 左、右指针均为空 D. 左、右指针均不为空 7. 设有5000个元素，希望用最快的速度挑选出前10个最大的，采用（ ）方法最好。 A．快速排序 B.堆排序 C. 希尔排序 D.归并排序 8. 在顺序表{12、15、17、20、24、30、38、43、45、51、52}中，用二分法查找关键码20需做（ ） 次关键字比较。 A、2 B、3 C、4 D、5 9、散列技术中的冲突是指（ ）。 A、两个元素具有相同的序号 B、两个元素的键值不同，而其他属性相同 C、数据元素过多 D、不同键值的元素对应于相同的存储地址 10. 有n个结点的无向图的边数最多为在表长为n的顺序表上做插入运算，平均要移动的结点数为（ ）A. n/4 B. n/3 C. n/2 D. n 14. 下面程序段的时间复杂度为( ) 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） 15．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（ ）A. front==rear