数据结构练习剖析.docx

?填空题?1.?在顺序表中访问任意一个元素的时间复杂度均为??O(1)?????，因此顺序表也称为???随机存取???的数据结构。2．二维数组a[4][3](下标从0开始)，假设a[0][0]的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a[2][1]地址是??????64????????。3.?直接插入排序用监视哨的作用是??防止数组下标越界?。4.?已知广义表Ls=(a, (b, c), (d, e)),?运用head和tail函数取出Ls中的原子d的运算是???????Head（Head（Tail（Tail（LS））））???????。5．对有14个元素的有序表A[1..14]进行折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有???????A[3]?????A[5]?????A[7]???????。6.?在AOV网中，顶点表示?活动??，边表示?活动之间的先后关系??。?????7.?有向图G可进行拓扑排序的判别条件是??有向无环图??。8.?若串S1=‘ABCDEFGHIJK’,S2=‘451223’,S3=‘####’,则执行Substring(S1,Strlength(S3),Index(S2,‘12’,1))的结果是??DEF??。选择题1.?在下列存储形式中，哪一个不是树的存储形式？（ D?）A．双亲表示法???????????B．孩子链表表示法???????C．孩子兄弟表示法???????D．顺序存储表示法?2.?查找n个元素的有序表时，最有效的查找方法是（?C?）。A．顺序查找????????????????B．分块查找???????C．折半查找????????????????D．二叉查找3.将所示的s所指结点加到p所指结点之后，其语句应为（?D??）。A．s-next=p+1 ; p-next=s;B．(*p).next=s; (*s).next=(*p).next;C．s-next=p-next ; p-next=s-next;D．s-next=p-next ; p-next=s;4.?在有向图的邻接表存储结构中，顶点v在链表中出现的次数是（?C?）。A.?顶点v的度?????????????B.?顶点v的出度????C.?顶点v的入度???????????D.?依附于顶点v的边数5.算法的时间复杂度为O（nlog2n）、空间复杂度为O(1)的排序算法是（?A?）。A.?堆排序????????B.?快速排序?????C.?归并排序?????D.直接选择设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≤j),?在一维数组B中下标k的值是（??B）：Ａ．i(i-1)/2+j-1????????Ｂ．i(i-1)/2+j????Ｃ．i(i+1)/2+j-1????????Ｄ．i(i+1)/2+j?2.由一个长度为11的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功的平均查找长度是（?C?）。A．29/11?????B. 31/11??????C. 33/11??????D.35/113.?AVL树是一种平衡的二叉排序树，树中任一结点的（?B??）。A.?左、右子树的高度均相同????????B.?左、右子树高度差的绝对值不超过1C.?左子树的高度均大于右子树的高度D.?左子树的高度均小于右子树的高度4.??下列四种排序方法中，不稳定的方法是（?D?）。A.?直接插入排序???????????????????B.?冒泡排序C.?归并排序?????????????????????????D.?堆排序5.?设树的度为4，其中度为1,2,3,4的结点个数分别为4, 2, ,1, 1,?则T中的叶子数为（?D??）。A．5??????????B．6???????????C．7???????????D．8判断题1.?顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ F?）2.??数组不适合作任何二叉树的存储结构。（?F?）3.??广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。（?F?）4.??在含有n个结点的树中，边数只能是n-1条。（?T ）5.??所谓一个排序算法是否稳定，是指该算法在各种情况下的效率是否相差不大。（?F?）6.??简单选择排序在最好情况下的时间复杂度为O(n)。（ F?）7.??在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ F??）8.??采用线性探测处理冲突，当从哈希表中删除一个记录时，不应将该记录所在位置置空，因为这会影响以后的查找。（ T?）9.??n个数存放在一维数组A[1..n]中，在进行顺序