必威体育精装版数据结构作业题1_5套计算机专业.docVIP

东北农业大学网络教育学院 数据结构作业题（一） 一、选择题（每题2分，共20分） 1．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。 A、O(n) B、O (n/2) C、O (1) D、O (n2) 2．带头结点的单链表first为空的判定条件是（ ）。 A、first == NULL; B、first-link == NULL; C、first-link == first; D、first != NULL; 3．在一棵树中，（ ）没有前驱结点。 A、分支结点 B、叶结点 C、树根结点 D、空结点 4．在有向图中每个顶点的度等于该顶点的（ ）。 A、入度 B、出度 C、入度与出度之和 D、入度与出度之差 5．对于长度为9的有序顺序表，若采用折半有哪些信誉好的足球投注网站，在等概率情况下有哪些信誉好的足球投注网站成功的平均有哪些信誉好的足球投注网站长度为（ ）的值除以9。 A、20 B、18 C、25 D、22 6．下列程序段的时间复杂度为（ ）。 s=0； for(i=1；in；i++) for(j=1；jn；j++) s+=i*j； A、O (1) B、O (n) C、O (2n) D、O (n2) 7．栈是一种操作受限的线性结构，其操作的主要特征是（ ）。 A、先进先出 B、后进先出 C、进优于出 D、出优于进 8．假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（ ）。 A、(rear-front-1)％n B、(rear-front)％n C、(front-rear+1)％n D、(rear-front+n)％n 9．高度为5的完全二叉树中含有的结点数至少为（ ）。 A、16 B、17 C、31 D、32 10．如图所示有向图的一个拓扑序列是( ) A、ABCDEF B、FCBEAD C、FEDCBA D、DAEBCF 二、填空题（每空1分，共20分） 1．n (n﹥0) 个顶点的无向图最多有 条边，最少有 条边。 2．在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过 。 3．已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为 。 4．在二叉树的第i层上至多有 结点。 5．对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为 ，右孩子结点的编号为 ，双亲结点的编号为 。 6．数据的存储结构被分为 、 、 和 四种。 7．假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则树中所含的结点数为 个，树的深度为 ，树的度为 。 8．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要 条边。 9．在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着 、 和 的联系。 10．一棵含999个结点的完全二叉树的深度为 。 三、运算题（每题5分，共10分） 1．设有一个10?10的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。 2．已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a[12]中，根据折半有哪些信誉好的足球投注网站过程填写成功有哪些信誉好的足球投注网站下表中所给元素34, 56, 58, 63, 94时的比较次数。 元素值3456586394比较次数 四、应用题（每题10分，共50分） 1．设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。 （1）用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。 （2）用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。 2．判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。 （1