数据结构考试用.pdf

《数据结构考试用.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1．一个数组元素a[i]与（*(a+i)）的表示等价。2.某算法仅含并列的程序段1和程序段2，程序段1的执行次数3n2，程序段2的执行次数为0.01n3，则该算法的时间复杂度为（O(n3)）。3．设有一个nxn的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（（i+3）*i/2）处。4．给定有n个元素的向量，建立一个有序单链表的时间复杂度是（O（n2））。5．假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断对空

2、的条件为（front==rear）。6．如果一个第归函数过程中只有一个第归语句，而且它是过程体的最后语句，则称这种第归为（尾第归），它很容易被改写为非第归过程。7．在一棵具有n个结点的二叉树的第i层上（假定根结点为第0层，i大于等于0而小于等于树的高度），最多具有（2i）个结点。8．利用3，6，8，12这四个值作为叶子结点的权，生成一棵霍夫曼树，该树的带权路径长度为（55）。9．从具有n个结点的AVL树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为（O（log2n））。10．对于具有e条边的无向图，它的邻

3、接表中有（2e）个边结点。11．图的深度优先搜索类似于树的（先根）次序遍历。12．一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序（以位于最左位置的对象为基础）所得到的第一次划分结果为（{40，38，46，79，56，84}）。1.向顺序栈中压入新元素时，应当（先移动栈顶指针，再存入元素）。2.设有向图与n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时总的计算时间为（O(n+e)）。3.一个对象序列的排序码为{46，79，56，38，40，84},采用快速排序以位于最左位置的对象为基

4、准而得到的第一次划分结果为（{40,38,46,56,79,84}）。4.线性链表不具有的特点是（随机访问）。5.设有一个10阶的对称矩阵Ａ[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组Ｂ[]中，Ａ[0][0]存入Ｂ[0]中，则Ａ[8][5]在Ｂ[]中(41)位置。6.设Ｆ是一个森林，Ｂ是由Ｆ转换得到的二叉树，Ｆ中有n个非叶结点，则Ｂ中右指针域为空的结点有（n+1）个。7.具有65个结点的完全二叉树的高度为（6）。（根的层次号为0）8.若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（

5、直接插入排序）方法比较次数最少。9.在一个无向图中，所有顶点的度数之和等于所有边数的（2）倍。10.对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为（R[6],R[2],R[4],R[3]）。1．基本数据类型是计算机已经实现了的数据结构。2．二维数组是一种非线性结构，其中的每一个数组元素最多有两个个直接前驱（或直接后继）。3．链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的指针域的值。4．队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称

6、为先进先出表。5．如果一个过程直接或间接地调用自己，则称这个过程是一个递归的过程。6．假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度为4。假定树根结点的层次为0。7．在一个堆的顺序存储中，若一个元素的下标为i（0≤i≤（n—1）/2），则它的左子女元素的下标为2i+1。8．根据n个元素从空树开始建立一棵二叉搜索树的渐进时间复杂度在最好情况下为O（nlog2n）。9．N（n>0）个顶点的无向图中顶点的度的最大值不超过n—1。10．每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做二路归并排序。11．快

7、速排序在最坏情况下的空间复杂度为O（n）。12．若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则二级索引表的长度为25。（错）1．数据元素是数据的最小单位。（错）2．在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。（对）3．链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。（错）4．递归方法和递推方法本质上是一回事，例如求n！时既可用递推的方法，也可用递归的方法。（错）5．在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具

8、有相同的结果。（错）6．对具有n个结点的堆进行插入一个元素运算的时间复杂度为O（n）。（对）7．在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，则得到的是最优二叉树。（对）8．用边表示活动的网络（AOE网）的关键路径是指从源点到终点的路径长度最长的路径。（错）9．对一个有向图进行拓扑排序，一