数据结构试卷B及答案__黄河科技学院

《数据结构》课程试题（B卷） 一、单选题（每小题1分，共20分） 1.一个栈的输入序列是abcde，则栈的不可能的输出序列是___ __。 A.edcba B. abcde C. adebc D .bacde 2.子串是­­­_____ _。 A. 串中若干个连续字母构成的序列 B. 串中一些字符构成的序列 C. 串中任意个连续字符组成的序列 D. 串中一个以上连续字符组成的序列 3．下列排序算法中，算法不稳定的是_______。 A.直接插入排序 B.折半插入排序 C.冒泡排序D.快速排序 4．关键路径是指事件结点网络中的­­­________。 A.从开始结点到完成结点的最长路径 B.从开始结点到完成结点的最短路径 C.最长的回路且按拓扑排序 D. 最短的回路 5．二叉树采用二叉链表存储方式进行存储，具有n个结点的二叉树中共 个非空的指针。 A. 2n B. 2n+1 C. n-1 D. n+1 6．深度为h的满二叉树的共有 个结点。 A． 2h-1-1 B．2h-1 C．2h-1 D．2h 7．对于后序遍历与中序遍历结果相同的二叉树为 。 A．一般二叉树 B．根结点无左孩子的二叉树 C．所有结点只有左子数的二叉树 D．所有结点只有右子树的二叉树 8．适用于折半查找的表的存储方式及元素排列要求为 ; A．链接方式存储，元素无序 B．顺序方式存储，元素有序 C．顺序方式存储，元素无序 D． 链接方式存储，元素有序 9. 散列表的地址区间为0-9, 散列函数为H (x)=x mod 10。采用线性探测法处理冲突，并将关键字序列26，25，71，32，2，12，51依次存储到散列表中。元素56存放在散列表中的地址是 。 A.8 B.5 C.6 D.7 10．下列四个序列中，哪一个是大根堆 。 A.75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C.75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 11具有n个顶点的无向完全图的边数为 。 A. n*(n-1) B. n*n C. n*(n-1)/2 D. (n*n)-1 12．线性表采用链式存储时，其存储地址 。 A.必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D.连续与否均可以 13．若给定的关键字集合为{20,15,14,18,21, 6,40,1}，一趟快速排序结束时，键值的排列为 。 A．20,15,14,18,21,1,40,6 B、15,14,18,20,6, 40,1,21 C、15,14,18,20,6,21,1,40 D、15,14,40,20,6,21,1,18 14．队列操作的原则是 。 A. 先进后出 B.先进先出C.只能进行插入 D.只能进行删除 15．任一带权连通图的最小生成树 。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 16．给定权的集合{1，3，4，2，6，5，7}，所构造出的哈夫曼树的带权外部路径长度为___________。 A .47 B . 74 C. 89 D.98 17．假设h（key），h1（key）是不同的散列函数，散列表冲突的条件是 。 A. h（keyi）=h（keyj） B.keyi≠keyj ，h（k