发布时间 : 星期四 文章数据结构专升本模拟题及参考答案更新完毕开始阅读
A．v1，v2，v3，v5，v4 B．v1，v2，v3，v4，v5
C．v1，v3，v4，v5，v2 D．v1，v4，v3，v5，v2
8、为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用（ ）。
A．顺序存储 B．链式存储 C．索引存储 D．散列存储 9、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（ ）。
A．s B．s-1 C．s+1 D．n
10、如图所示，给出由7个顶点组成的无向图。从顶点A出发，对它进行深度优先搜索得到的顶点序列是（ ）。
A．A E C D B F G B．A G B F D E C C．A C E D B G F D．A B D G F E C
二、填空题
1. 设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共
有________个结点。
2. 有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是________，带权路径长度WPL为________。
3.设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为________________。 4. 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分 个结点最佳。
5、设G为具有N个顶点的无向连通图，则G中至少有 条边。
6、哈夫曼树（Huffman Tree）又称 。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL 。
7、树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则访问树的 ；依次先序遍历树的 。 三、应用题
1、给定权值集合{1, 4, 2, 6, 9,}, 构造相应的哈夫曼树, 并计算它的带权路径长度。
2、对关键字序列{10，6，3，2，5，4}，构造一棵平衡二叉（排序）树并画图（要求画出建树过程）。
3、设有一个有序文件，其中各记录的关键字为（1，2，3，4，5，6，7，8，9，10，11，12，13，14，15），当用折半查找算法查找关键字为3，8，19时，其比较次数分别为多少？
4、对有五个结点{ A,B, C, D, E}的图的邻接矩阵，
?010030?10???0????????60020?????10?0????????500?? （1）．画出逻辑图 ；
（2）．画出图的十字链表存储；
（3）．基于邻接矩阵写出图的深度、广度优先遍历序列； （4）．计算图的关键路径。
作业题（三）
一、单项选择题
1．串的长度是指（ ）
A．串中所含不同字母的个数 B．串中所含非空格字符的个数
C．串中所含不同字符的个数 D．串中所含字符的个数
2．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。
A. BA+141 B. BA+180 C. BA+222 D. BA+225
3．算法分析的两个主要方面是（ ）。
A．空间复杂性和时间复杂性 B．正确性和简明性
C．可读性和文档性 D．数据复杂性和程序复杂性
4．算法分析的目的是（ ）。
A．找出数据结构的合理性 B．研究算法中的输入和输出的关系
C．分析算法的效率以求改进 D．分析