2012湖北文理学院计算机科学与技术专业专升本数据结构考试样题.doc

湖北专升本网 湖北文理学院计算机科学与技术专业专升本数据结构考试样卷一、下列叙述中，你认为正确的小题题号有： （10*1）。1、 顺序循环队列Q满的条件是：Q.front+1=Q.rear2、 哈夫曼树中没有度为1的结点。3、 两分法插入排序所需比较次数与待排序记录的初始排列状态有关。4、 当待排序记录已经基本有序时，快速排序的执行时间最省。5、 在等概率查找情况下，分块查找平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。6、 用树的前序遍历和中序遍历结果可以导出树的后序遍历；7、 树中所有结点的层数之和称为树的高度（深度）。8、 三元组表是稀疏矩阵的一种顺序存储结构。9、 直接插入排序是一种就地排序，它需要的辅助空间是O（n）10、 C = ( ( x , ( a , b ) ) , y )是一个长度为3的广义表。二、名词解释（5*3） 栈，折半查找，二叉排序树，关键路径，哈夫曼编码三、下列各小题提供的选项中，只有一个是正确的，请将你认为正确代码填入下列表格中（14*1.5）题号1234567891011121314选择1、若哈夫曼树中其叶结点个数为n,则非叶结点的个数为 。A n-1 B n C n+1 D log2n 2、最优查找树为平均查找路径长度w1h1+ w2h2+ wnhn最小的树,其中n表示 。 A 树中叶结点数 B 树中的全部结点数 C 所有非叶结点数 D 查找成功的结点数3、一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？A. 1，3，2，4 2，3，4，1 4，3，1，2 3，4，2，14、下列排序方法中，哪一种方法的比较次数与记录的初始排列状态无关？A. 直接插入排序 . 起泡排序 . 快速排序 直接选择排序 5、若一棵二叉树具有10个度为2的结点，则该二叉树叶结点个数是A. 9 11 12 不确定6、在顺序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找关键码12需做 次关键字比较。A、2 B、3 C、4 D、57、对包含N个元素的散列表进行检索，平均检索长度为 。A、为 o(log2N) B、为o(N) C、不直接依赖于N D、上述三者都不是8、假定有k个关键字互为同义词（发生冲突）,若用线性探测法把这k个关键字存入散列表中,至少要进行 次探测。 A k-1 B k C k+1 D k(k+1)/29、给定一个整数集合3，5，6，9，12，下列二叉树 是该整数集合对应的哈夫曼（Huffman）树。10、若需要在O(nlog2(n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是 A 快速排序 B 堆排序 C 归并排序 D 直接插入排序11、将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是 A n B 2n-1 C （n+1）/2 D n-112、下列 方法可以用来判断出一个有向图中是否有环（回路）A 深度优先遍历 B 拓朴排序 C 求最短路径 D 求关键路径 13、假设有两个串A和B，求B在A中首次出现的位置的操作，我们称为。A连接 B.模式匹配 C求子串 D求串长14、 如果待排序的记录的规模很大，则在下面的排序方式中，我们最好不要选择使用 。A 快速排序 B.直接插入排序 C.堆排序 D.归并排序四、 你认为正确的叙述填在各题的下划线上（10*1.5）。1、 串的主要存贮方式有：定长顺序存贮、 和块链存贮。2、 堆的存储表示是 （顺序的，还是链接的）。 3、 在n个记录的哈希表中进行查找，最少的比较次数是 。4、 n个顶点的连通图用邻接矩阵表示时,该矩阵至少有 个非零元素.5、 评价一个算法好坏的主要标准有 。6、 若压缩存贮下三角矩阵Am*n的首地址为a,每个元素占空间为b字节,则元素aij的地址为 。7、 栈和队列都是线性表，其中队列的特点是 。8、 若顺序二叉树中编号为n的结点的父结点和右儿子是存在的，则它们的编号应该分别是 9、 若一数组的记录数为400,采用分块查找，块长最好取 。10、 就排序算法的稳定性而言，希尔排序和快速排序分别是 。五、应用题（5*5）1、 假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的Huffman（哈夫曼）编码。2、 下图是用邻接表存储的图，画出此图，并写出从C点开始按深度(广度)优先遍历该图的结果。3、 试求按关键字序列（12，1，4，3，7，8，10，2）插入生成的二叉排序树和平衡二叉树。4、 哈希函数为：H(key)=3*key mod 11,开放定址的di=i*(7*key mod 10 +1) , 在区间0，10上构造关键字（22，41，53，46，30，13，01，67）的哈希表，并计算其平均查找长度。5、 判别以下序列是否为小顶堆，如不是，请把它们整理成一小顶堆： 30，24，36，12，91，53，47，85 ，96六、算法编程（3*5）1、 以带头结点的循环单链表来表示队列，且只设指向尾结点的尾指针L，试编写相应的队列初始化、入队和出队的算法。2、 在T所指的二叉排序树中