数据结构试卷样卷

《数据结构试卷样卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、安徽建筑工业学院试卷（样卷）共3页第1页总分一二三四五六七八阅卷教师考试课程：算法与数据结构班级：学号：姓名：复核教师一．单项选择题（共20题，每题1.5分，共30分）11．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（A）。2A、O(n)B、O(n/2)C、O(1)D、O(n)1.下面程序段的时间复杂度为(C)。for(inti=0;ilin

2、k==NULL;a[i][j]=i*j;C、first->link==first;D、first!=NULL;22A、O(m)B、O(n)C、O(m*n)D、O(m+n)13．当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（B）。2.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列(C)。A、n-2B、n-1C、nD、n+1A、1，3，2，4B、2，3，4，114．m阶B树中的m是指（C）。C、4，3，1，2D、3，4，2，1A、每个结点至少有m棵子树B、非终端结点中关键字的个数

3、3.采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（D）。C、每个结点至多有m棵子树D、m阶B树的深度（或高度）A、nB、n/２C、(n-1)/2D、(n+1)/215．在一棵树中，（C）没有前驱结点。4.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（B）A、分支结点B、叶结点C、树根结点D、空结点A、9B、11C、12D、不确定16．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子5.对矩阵压缩存储是为了（B）。的平衡因子为-1，右孩子的平

4、衡因子为0，则应作（B）型调整以使其平衡。A、方便压缩B、节省空间C、方便存储D、提高运算速度A、LLB、LRC、RLD、RR6.在已知待排序文件已基本有序的前提下，效率最高的排序方法是（A）17．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为A、直接插入排序B、直接选择排序C、快速排序D、归并排序（C）的值除以9。7.在有n个叶子结点的哈夫曼树中，其结点总数为（D）。A、20B、18C、25D、22Ａ、不确定Ｂ、2nＣ、2n+1Ｄ、2n-118．在有向图中每个顶点的度等于该顶点的

5、（C）。8.广义表((A,B,E,F,G))的表尾是(B)。A、入度B、出度A、(B,E,F,G)B、()C、（A，B，E，F，G）D、不存在C、入度与出度之和D、入度与出度之差9.折半查找要求查找表中各元素的关键字值必须是（A）排列。19．在基于排序码比较的排序算法中，（C）算法的最坏情况下的时间复杂度不高于O(nlog2n)。Ａ、递增或递减Ｂ、递增Ｃ、递减Ｄ、无序A、起泡排序B、希尔排序C、归并排序D、快速排序10.在一个单链表中，若p所指结点不是最后一个结点，在p之后插入t所指结点，则执行（B）20．当α的值

6、较小时，散列存储通常比其他存储方式具有（B）的查找速度。A、t->next=p；p->next=t；B、t->next=p->next；p->next=t；A、较慢B、较快C、相同C、t->nexr=p->next；p=t；D、p->next=t；t->next=p；注：1.请命题老师用黑色的墨水工整的书写，作图准确，以保证试卷字迹清晰。2.请命题老师在试题后面留出答题空间。3.学生不得在草稿纸上答题安徽建筑工业学院考试命题纸（样卷）卷共3页第2页考试课程：算法与数据结构班级：学号：姓名：二、填空题（每空1分，共1

7、0分）四、简答题（共4题，每题5分，共20分）1．在一棵树中，叶子结点没有后继结点。1.有一组关键字{50，52，85，22，96，17，36，55}，请用快速排序，写出第一趟排序结果。解：2．在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值{36，17，22，50，96，85，52，55}不超过1。3．n(n﹥0)个顶点的无向图最多有n(n-1)/2条边，最少有0条边。4．按策略划分内部排序方法可分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。5．n个结点的二叉树

8、采用二叉链表存放，共有空链域个数为__n+1____。6．已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是_1168____。2.将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二叉排序树中，画出最终的二叉排序树。7．在各种