文档介绍:数据构造试卷(一)
一、单选题(每题 2 分,共20分)
栈和队列共同特点是( )。
用链接方式存储队列,在进行插入运算时( ).
A. 仅修改头指针 B. 头、尾指针都要修改
C. 仅修改尾指针 、尾指针也许都要修改
如下数据构造中哪一种是非线性构造?( )
A. 队列 B. 栈 C. 线性表 D. 二叉树
设有一种二维数组A[m][n],假设A[0][0]存储位置在644(10),A[2][2]存储位置在676(10),每个元素占一种空间,问A[3][3](10)存储在什么位置?脚注(10)表达用10进制表达。
A.688 B.678 C.692 D.696
树最适合用来表达( )。
二叉树第k层结点数最多为( ).
A.2k-1 +1 -1 D. 2k-1
若有18个元素有序表存储在一维数组A[19]中,第一种元素放A[1]中,现进行二分查找,则查找A[3]比较序列下标依次为( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
对n个记录文献进行迅速排序,所需要辅助存储空间大体为
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K %9作为散列函数,则散列地址为1元素有( )个,
A.1 B.2 C.3 D.4
设有6个结点无向图,该图至少应有( )条边才干保证是一种连通图。
二、填空题(每空1分,共26分)
普通从四个方面评价算法质量:_________、_________、_________和_________。
一种算法时间复杂度为(n3+n2log2n+14n)/n2,其数量级表达为________。
假定一棵树广义表表达为A(C,D(E,F,G),H(I,J)),则树中所含结点数为__________个,树深度为___________,树度为_________。
后缀算式9 2 3 +- 10 2 / -值为__________。中缀算式(3+4X)-2Y/3相应后缀算式为_______________________________。
若用链表存储一棵二叉树时,每个结点除数据域外,尚有指向左孩子和右孩子两个指针。在这种存储构造中,n个结点二叉树共有________个指针域,其中有________个指针域是存储了地址,有________________个指针是空指针。
对于一种具备n个顶点和e条边有向图和无向图,在其相应邻接表中,所含边结点分别有_______个和________个。
AOV网是一种___________________图。
在一种具备n个顶点无向完全图中,包具有________条边,在一种具备n个顶点有向完全图中,包具有________条边。
假定一种线性表为(12,23,74,55,63,40),若按Key % 4条件进行划分,使得同一余数元素成为一种子表,则得到四个子表分别为____________________________、___________________、_______________________和__________________________。
向一棵B_树插入元素过程中,若最后引起树根结点分裂,则新树比原树高度___________。
在堆排序过程中,对任一分支结点进行筛运算时间复杂度为________,整个堆排序过程时间复杂度为________。
在迅速排序、堆排序、归并排序中,_________排序是稳定。
三、计算题(每题 6 分,共24分)
在如下数组A中链接存储了一种线性表,表头指针为A [0].next,试写出该线性表