黑龙江大学数据结构考试卷

ZP 选择题共13题，每题2分 1、一个三元组表用于表示一个 A.线性表 B.广义表 2、允许对队列进行的操作有 双向链表 A.删除队首元素B.取出最近进队的元素 C.在最早入队元素之前插入 C. D.稀疏矩阵 元素D.排序 。 3、设广义表上 La, f,g,e, c,d,则表达式 Tail HeadTail L的值 为 A. d B. e C. gD. e 4、假设8行10列的二维数组分别以行序和以列序为主序顺序存 储时，其首 地址相同， A. a[5, 3] 那么以行序为主序时元素a[3,5]的地址与以列为主序时元素 的地址相同。 B. a[8, 3] 5、深度为5的满二叉树共有 C. a[l,4] D.以上都不对 个分支结点。 D. 31 A. 32 B. 15C. 6、若树T有a个度为1的结点，b个度为2的结点，c个度为3的结点，则该树 有 个叶子结点。 A. l2b3c B. a2b3c C. 2b3c D. lb2c 7、若二叉树T的前序遍历序列和中序遍历序列分别是b,d,c,a,e,f c, d, e, a, b, f,则其后序遍 历序列是 A. c, e, a, d, f, b 上都不对 8、边数很多的稠密图， A.邻接矩阵B. 30 。 B. f, e, a, c, d, b C. e, a, c, d, f, b D. 适宜用表示。 邻接表 C,逆邻接表D.邻接多重表 9、对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。 A. 3B. 4C. 5D. 6 10、查找哈希表，不会发生冲突的哈希函数是 A.除留余数法B.伪随机探测再散列法C,直接地址法 D.线性探 测再散列法 11、对有序单链表使用查找法进行查找。 A.折半 B.分块C.哈希 D.顺序 D. 0n2 12、直接插入排序在最好情况下的时间复杂度为 A. 0log2B. 0nC. 0nlog2 13、以下排序方法中所需辅助空间最大的是 A.直接插入排序B.堆排序 C.归并排序D.希尔排序 一、 填空题共14个空，每空1分 。 1、在单链表中设置头结点的作用是 2、设环形队列存放在数组q中，数组q的长度为n,下标从0〜nT。队头指针 head指向队头结点，队尾指针tail指向队尾结点后一个空闲结点。环形队列的 队空标志为（），队满标志为（），该队列的长度为（）。 3、设有算术表达式xa*（y-b）-c/d,该表达式的前缀表示为（），后缀表 示为（）。 4、对关键码序列FBJGEAIDCH进行升序排列，则堆排序时，初始建堆结果的序列 为（）。设关键码序列中有n个元素，则堆排序的平均执行时间 为（）。 5、有n个顶点的有向强连通图最多有（）条边，最少有（） 条边。 6、在m阶B-树中，除了根和叶子外，每个结点的子结点数目的范围在（） 之间，同时，具有k个子结点的非叶结点含有（）个键值。而在m 阶B树中，具有k个子结点的结点含有（）键值。 7、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。 三、.判断对错题（共5题，每题1分） 1、数据的逻辑结构与数据元素本身的形式和内容无关。（） 2、哈夫曼树的所有子树也均是哈夫曼树。（） 3、线性表的逻辑顺序总与其物理顺序一致。（） 4、理想情况下散列表等概率查找成功的平均查找长度是0（1） o （） 5、求n个数中最大的k （kn个）数，起泡排序比直接选择排序要好。 （） 四、应用题（共6道题，1-3题4分，4-6题6分，总分为30分） 1、有5个元素，其入栈次序为A,B,C,D,E,在各种可能的出栈序列中，第一个 出栈元素为C且第二个出栈元素为D的出栈序列有哪几个 2、以下表顺序建立二叉排序树，并求在等概率情况下查找成功的平均查找长度。 （90, 60, 20, 50, 40, 30, 10, 110, 100, 70, 120, 80） 3、求一个有向无环图的拓扑序列时，其结果为何不唯一 4、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率为0.07、 0.19、0.02、0.06、0.32、0.03、0.21、0.10。试为这 8 个字母设计哈夫曼 编码。使用等长编码表示电文是另一种编码方案。比较两种方案的优缺点。 5、已知带权无向图，利用克鲁斯科尔（Kruskal）算法，画出该无向最小生成树 的每一步。 6、对一组关键字26, 5, 37, 1, 62, 11, 59, 15采用快速排序方法进行排序， 用第一关键字做划分元素，请写出每趟划分的结果。 五、.算法设计题（共3道题，1题7分2题8分3题10分，共25分） 1、设n个十进制整数已存入数组A[n]中，请利用栈技术，写出将A[n]中个数据 转换成八进制数并存入数组B [n]的算法。 2、已知rQ是一个小堆顶，试写一算法，使得增加一个元素以后， （rb r2, , rn, r仍是一个堆。 3、设有以标准形式存储的二叉数T,分别计算T的深度和宽度。（注空的二叉 树的深度为T,非空的二叉树的深度为其左、右子树的深度的较大者加1;空的 二叉树的宽度为0,对一棵非空的二叉数各层所包含的节点个数分别进行计数， 其中的最大者即为此非空的二叉树的宽度）。