数据结构考试试卷（A）.doc

"数据结构考试试卷（A）.doc" 本资源为数据结构考试试卷（A），包含三部分：填空题、单项选择题和解答题。总共有 12 个填空题，15 个单项选择题和 5 个解答题，涵盖了数据结构的基本概念、数据元素的存储结构、栈、队列、数组、广义表、哈夫曼树、图论、排序算法等方面的知识点。 一、填空题 1. 数据结构通常有四种基本的结构，分别是：数组、链表、栈和队列。 2. 数据元素在计算机中的两种不同的存储结构：顺序存储结构和链式存储结构。 3. 在线性结构中，开始结点（ head ）前驱结点，其余每个结点有且只有一个前驱结点。 4. 设有一个空栈，现输入序列为 E，D，C，B，A，经过 push，push，pop，push，pop，push，pop 后，栈顶元素是 A。 5. 在队列中入队操作由 front 指针进行控制，出队操作由 rear 指针进行控制。 6. 一维数组的元素起始地址 LOC[6]=1000，元素长度为 4，LOC[3]的起始地址为 1008。 7. 广义表 ((a, b), c, d, (e, f)) 的表尾是 (e, f)。 8. 具有 m 个叶结点的哈夫曼树共有 2m-1 个结点。 9. 强连通分量是强连通图的极大连通子图。 10. n 个结点的无向图的边数最多有 n*(n-1)/2 条。 11. 用迪杰斯特拉算法求某一顶点到其余各顶点间的最短路径是按照路径长度非递减次序来得到最短路径。 12. 希尔排序属于插入排序，快速排序属于交换排序，堆排序属于选择排序。 二、单项选择题 1. 在插入运算中，使用顺序表比链表好。 2. 在一个单链表中，已知*q 结点是*p 结点的前驱结点，若在*q 和*p 之间插入结点*s，则执行 q->next=s;s->next=p。 3. 设有一顺序栈 S，元素 s1,s2,s3,s4,s5,s6 依次入栈，如果 6 个元素的先后出栈顺序是 s2,s3,s4,s6,s5,s1，则栈的容量至少应该是 6。 4. 空串和空格串是相同的。 5. 稀疏矩阵的一般的压缩方法有二维数组、广义表、三元组表和一维数组。 6. 深度为 5 的二叉树至多有 2^5-1=31 个结点。 7. 将一颗有 100 个结点的完全二叉树从上往下，从左往右依次对结点进行编号，根结点的编号为 1，则编号为 49 的结点的右孩子编号为 98。 8. 最短路径算法可用迪杰斯特拉算法实现。 9. 通常把查找过程中对关键字需要执行的比较次数作为衡量一个查找算法效率优劣的标准。 10. 设有 10000 个无序的元素，希望以最快的速度挑选出其中前 10 个最大的元素，最好选用的排序方法是堆排序。 11. 计算机算法必须具备输入输出和解决问题的有限运算步骤。 12. 树最适合用来表示现有元素之间具有分支层次关系的数据。 13. 完全二叉树可能是满的。 14. 下列说法正确的是：图的结点关系是任意的，在拓扑排序中，弧头结点可能会出现在弧尾结点之前。 15. 由普通树转换成二叉树是非空的二叉树，则转换后的二叉树根结点可能有左右子树。 三、解答题 1. 将图中的森林转换成与之对应的一棵二叉树。 2. 某密码电文由 8 个字母组成，每个字母在电文中出现的频率分别是：{7、19、2、6、32、3、21、10}，将这 8 个字母设计相应的哈夫曼树，并写出其编码。 3. 所示为无向连通网，要求用普里姆算法构造出它的最小生成树。 4. 写出有向图中三种不同的拓扑排序序列。 5. 对下列一组关键字{46、58、15、45、90、18、10、62}按非递减序进行快速排序，试写出快速排序的每一趟的排序结果。 四、算法题 1. 写出单链表中的结点的就地逆置算法。 2. 写出对一组关键字{46、58、15、45、90、18、10、62}的快速排序算法。