考題解答07年福建专升本数据结构.doc

第二部分 数据结构（共100分） 一、单项选择题（本大题共12小题，每小题2分，共24 分） 在每小题列出的四个备选项中只有一个符合题目要求，请将正确答案代码填写在答题纸相应的位置上。写在试卷上不得分。 1．在待排序记录已基本有序的前提下,下述排序方法中效率最高的是： A)直接插入排序 　 B)简单选择排序 　　 C)快速排序 　 D)归并排序 2．以下哪一个术语与数据的存储结构无关？ A)栈 B)闭散列表 C)线索二叉树 D)双向链表 3．有6个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列： A)5,4,3,6,1,2 B)4,5,3,1,2,6 C)3,4,6,5,2,1 D)2,3,4,1,5,6 4．下述哪一条是顺序存储方式的优点？ A)存储密度大 B)插入运算方便 C)删除运算方便 D)可方便地用于各种逻辑结构的存储表示 5．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为:A) 顺序表 B) 用头指针表示的单循环链表C) 用尾指针表示的单循环链表 D) 单链表 6．对包含n个元素的散列表进行查找，平均查找长度 A)为O(log2n) B)为O(n) C)为O(nlog2n) D)不直接依赖于n 7．下列哪一种图的邻接矩阵是对称矩阵？ A)有向图 B)无向图 C)AOV网 D)AOE网 8. 设表 (a1, a2, a3, ......, a32) 中的元素已经按递增顺序排好序，用二分法检索与一个给定的值k相等的元素，若a1ka2，则在检索过程中比较的次数是： A) 3 B) 4 C) 5 D) 69. 具有3个结点的二叉树最多可有多少种不同的形态。 A）2 B）3 C）4 D）5 10．对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号， 则可采用的编号方法是： A、先序遍历 B、中序遍历 C、后序遍历 D、从根开始进行层次遍历 11. 在长度为n的顺序表的第i ( 1≤ i ≤n+1 )个位置上插入一个元素，元素的 移动次数为： A) n-i+1 B) n-i C) i D) i-1 12. 对于一个无向图，下列说法正确的是 A)每个顶点的入度大于出度； B)每个顶点的度等于其入度与出度之和； C)无向图的邻接矩阵一定是对称矩阵； D)有向图中所有顶点的入度之和大于所有顶点的出度之和； 二、填空题（本大题共10小题，每空2分，共22 分） 请在答题纸相应的位置上填写正确答案。写在试卷上不得分。 设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K % P（P=M）, 为使函数具有较好性能，P应选 97 N个结点的二叉树采用二叉链表存放，共有空指针域个数为 N+1 若一个算法中的语句频度之和为T(n) = 3720n+4nlogn，则算法的时间复杂度为_______O(nlogn)_________ 。 已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是： 将 第i列 累加。 深度为6（根深度为1）的二叉树至多有 63 个结点。 一棵具有n个叶子结点的哈夫曼树中，结点总数为 2n-1 。 设单链表结点的定义如下： struct node{ int data, struct node *next; }; 要在一个单链表中p所指结点之后插入一个子链表，子链表第一个结点的地址为s，子链表最后一个结点的地址为t, 则应执行操作： t-next=p-next;________ 和 _________ p-next=s； 。 设单链表结点的定义如19题，现有一个含头结点的单链表，头指针为head, 则判断该单链表是否为空表的条件为 head-next==NULL 。 n个顶点的连通无向图至少有 n-1 条边。 在顺序存储结构的线性表中插入一个元素，平均需要移动 n/2 个元素. 三、应用题：（本大题共4小题，每小题8分，共32 分） 请在答题纸相应的位置上填写正确答案。写在试卷上不得分。 23． 已知有向图如