数据结构试卷样卷

1、安 徽 建 筑 工 业 学 院 试 卷（试卷 A） 共 3 页 第 1 页总 分二三一二三四五六七（样卷）八阅卷教师考试课程：算法与数据结构 班级： 05计算机 学号： 姓名： 复核教师一 单项选择题（共20题，每题1.5分，共30分）1. 下面程序段的时间复杂度为( C )。 for(int i=0;i<m;i+) for(int j=0;j<n;j+) aij=i*j; A、O(m2) B、O(n2) C、O(m*n) D、O(m+n) 2. 一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列( C )。A、 1，3，2，4 B、2，3，4，1C、 4，3

2、，1，2 D、3，4，2，1 3. 采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。A、 nB、 n/ C、(n-1)/2 D、(n+1)/2 4. 若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（ B ）A、 9B、 11C、 12D、不确定 5. 对矩阵压缩存储是为了（ B ）。A、方便压缩 B、节省空间 C、方便存储 D、提高运算速度 6. 在已知待排序文件已基本有序的前提下，效率最高的排序方法是（ A ） A、 直接插入排序 B、 直接选择排序 C、 快速排序 D、 归并排序 7. 在有n个叶子结点的哈夫曼树中，其结点总数为（ D ）。、

3、 不确定 、2n 、2n+1 、2n-1 8. 广义表( (A , B, E, F , G)的表尾是( B )。 A、(B, E , F, G) B、( )C、（A，B， E，F，G） D、不存在 9. 折半查找要求查找表中各元素的关键字值必须是（ A ）排列。、 递增或递减 、递增 、递减 、无序 10. 在一个单链表中，若p所指结点不是最后一个结点，在p之后插入t所指结点，则执行（ B ） A、 t->next=p；p->next=t； B、 t->next=p->next；p->next=t；C、 t->nexr=p->next；p=t

4、； D、 p->next=t；t->next=p； 11在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ A ）。A、 O(n)B、 O(n/2)C、 O(1)D、 O(n2)12带头结点的单链表first为空的判定条件是（ B ）。A、 first = NULL; B、 first->link = NULL;C、 first->link = first; D、 first != NULL;13当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ B ）。A、 n-2 B、 n-1C、 n D、 n+114m阶B树中的m是指（ C ）。A、 每

5、个结点至少有m棵子树 B、 非终端结点中关键字的个数C、 每个结点至多有m棵子树 D、 m阶B树的深度（或高度）15在一棵树中，（ C ）没有前驱结点。 A、 分支结点 B、 叶结点 C、 树根结点 D、 空结点16在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（ B ）型调整以使其平衡。A、LL B、 LR C、 RL D、 RR17对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ C ）的值除以9。 A、 20 B、 18 C、 25 D、 2218在有向图中每个顶点的度等于

6、该顶点的（ C ）。A、 入度 B、 出度C、 入度与出度之和D、 入度与出度之差19在基于排序码比较的排序算法中，（ C ）算法的最坏情况下的时间复杂度不高于O(nlog2n)。A、 起泡排序B、 希尔排序C、 归并排序D、 快速排序20当的值较小时，散列存储通常比其他存储方式具有（ B ）的查找速度。A、 较慢B、较快C、 相同注：1.请命题老师用黑色的墨水工整的书写，作图准确，以保证试卷字迹清晰。2.请命题老师在试题后面留出答题空间。 3.学生不得在草稿纸上答题安 徽 建 筑 工 业 学 院 考 试 命 题 纸（A）卷 共 3 页 第 2 页考试课程： 算法与数据结构 班级： 05计算机

7、 学号： 姓名： 二、 填空题（每空1分，共10分）1在一棵树中， 叶子 结点没有后继结点。2在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不超过 1 。3 n (n0) 个顶点的无向图最多有 n(n-1)/2 条边，最少有 0 条边。4按策略划分内部排序方法可分为五类： 插入排序 、 选择排序 、交换排序、归并排序和分配排序。5n个结点的二叉树采用二叉链表存放，共有空链域个数为_ n+1 _ 。 6已知二维数组A2010采用行序为主方式存储,每个元素占2个存储单元,并且A105的存储地址是1000,则A189的存储地址是_ 1168 _ 。7在各种查找

8、方法中，平均查找长度与结点个数无关的是_ 哈希查找法 _ 。 8树的存储结构中，常用的链表结构有孩子表示法、双亲表示法和 孩子兄弟表示法 三种。三、判断题（共10题，每题1分，共10分）1. （ T ）有回路的有向图不能完成拓扑排序。 2. （ F ）一棵树的度是指该树中所有结点的度的和。 3. （ T ）在完全二叉树中，一个结点若没有左孩子，则它一定没有右孩子。  4. （F ）在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 5. （ F ）能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序表上相同。6. （ F ）通常递归的算法简单、易懂、容易编

9、写，而且执行的效率也高。7. （ T ）直接选择排序是一种不稳定的排序方法 。 8. （ T ）一个广义表的表尾总是一个广义表。 9. （ F ）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。 10.（ T ）由树转化成二叉树，其根的右子孩指针总是空的。四、简答题（共4题，每题5分，共20分）1.有一组关键字50，52，85，22，96，17，36，55，请用快速排序，写出第一趟排序结果。解：36，17，22，50，96，85，52，55 2.   将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二叉排序

10、树中，画出最终的二叉排序树。 3.已知叶子结点值2，3，5，6，9，11，构造哈夫曼树，计算其带权路径长度。WPL=11×2+6×2+9×2 +5×3 +2×4+3×4=87注：哈夫曼树的左右子树可以互换注：1.请命题老师用黑色的墨水工整的书写，作图准确，以保证试卷字迹清晰。2.请命题老师在试题后面留出答题空间。 3.学生不得在草稿纸上答题安 徽 建 筑 工 业 学 院 考 试 命 题 纸（A）卷 共 3 页 第 3 页考试课程： 算法与数据结构 班级： 05计算机 学号： 姓名： 4.已知某二叉树的前序序列为CBADEGFH，中序序

11、列为ABCEFGHD，请画出对应的二叉树并给出其后序序列。后序序列为ABFHGEDC。评分标准：画出二叉树4分 给出后序序列1分 五、算法设计题（30分） 1 编写一个直接插入排序算法。（10分）解：typedef struct int rMAXSIZE +1； int length； SqList；void StraightInsertSort(SqList *S) int i，j；for(i=2；i<=S->length；i+) S->r0=S->ri； j= i-1; while (S->r0 < S->rj) S->rj+1=S->

12、rj；j- ; S->rj+1=S->r0； 2设二叉树以二叉链表形式存储，请编写一个求叶子结点总数的算法。（10分）（要求写出二叉树的二叉链表存储表示，并在此基础上实现）。typedef struct BiTNodeTElemType data;struct BiTNode *Lchild, *Rchild; bitnode, *BinTree; 1分int leafNum=0; 2分void countLeaf(BinTree t) if (t=Null) return; 3分if (t->Lchild=Null && t->Rchild=Null) leafNum+; 5分else countLeaf(t->Lchild); 7分countLeaf(t->Rchild); 8分 3、设计一个算法，就地逆置带头结点的单链表head。（要求写出单链表的链式存储结构）（10分） 解： typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList; void Inve