中级数据库系统工程师数据结构与算法试卷（中级数据库系统工程师）.docVIP

试卷第 PAGE 1 页共 NUMPAGES 1 页 中级数据库系统工程师数据结构与算法试卷（中级数据库系统工程师） 姓名:_____________ 年级:____________ 学号:______________ 题型 选择题 填空题 解答题 判断题 计算题 附加题 总分 得分 评卷人 得分 1、循环队列用数组A［0…m-1］存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（ ） A.（rear-front+m）%m B.read-front+1 C.read-front-1 read-front2、设哈希表长m＝11，哈希函数H（key）＝key%11。表中已有4个结点：addr（15）＝4，addr（38）＝5，addr（61）＝6，addr（84）＝7，其余地址为空，如果二次探测再散列处理冲突，关键字为49的结点地址是（ ） A.8 B.3 C.5 93、一组记录的关键码为（46，79，56，38，40，84），则采用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ） A.38，40，46，56，79，84 B.40，38，46，79，56，84 C.40，38，46，56，79，84 40，38，46，84，56，794、将一棵有100个结点的完全二叉树从上到下、从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（ ） A.99 B.98 C.50 485、二叉树在线索化后，仍不能有效求解的问题是（ ） A.前序线索二叉树中求前序后继 B.中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前趋 后序线索二叉树中求后序后继6、在一个单链表head中，若要在指针p所指结点后插入一个q指针所指结点，则执行（ ） A.p-next＝q-next；q-next＝p； B.q-next＝p-next；p＝q； C.p-next＝q-next；p-next＝q； q-next＝next；p-next＝q；7、设二维数组a［0…m-1］［0…n-1］按列优先顺序存储在首地址为LOC（a［0］［0］）的存储区域中，每个元素占d个单元，则a［i］［j］的地址为（ ） A.LOC（a［0］［0］）+（j×n+i）×d B.LOC（a［0］［0］）+（j×m+i）×d C.LOC（a［0］［0］）+（（j-1）×n+i-1）×d LOC（a［0］［0］）+（（j-1）×m+i-1）×d8、如果一个栈的进栈序列是1，2，3，4且规定每个元素的进栈和退栈各一次，那么不可能得到的退栈序列为（ ） A.4，3，2，1 B.4，2，1，3 C.1，3，2，4 3，4，2，19、任何一个基于”比较”的内部排序的算法中，若对6个元素进行排序，在最坏情况下所需的比较次数至少为（ ） A.10 B.11 C.21 3610、堆是一种数据结构，（ ）是堆。 A.（10，50，80，30，60，20，15，18） B.（10，18，15，20，50，80，30，60） C.（10，15，18，50，80，30，60，20） （10，30，60，20，15，18，50，80）11、（ ）从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列。 A.二叉排序树 B.大顶堆 C.小顶堆 平衡二叉树12、若广义表L＝（（1，2，3）），则L的长度和深度分别为（ ） A.1和1 B.1和2 C.1和3 2和213、若对27个元素只进行3趟多路归并排序，则选取的归并路数为（ ） A.2 B.3 C.4 514、循环链表的主要优点是（ ） A.不再需要头指针了 B.已知某个结点的位置后，能很容易找到它的直接前驱结点 C.在进行删除操作后，能保证链表不断开 从表中任一结点出发都能遍历整个链表15、表达式a*（b+c）-d的后缀表达形式为（ ） A.abcd*+- B.abc+*d- C.abc*+d- -+*abcd16、若二叉树的先序遍历序列为ABDECF，中序遍历序列DBEAFC，则其后序遍历序列为（ ） A.DEBAFC B.DEFBCA C.DEBCFA DEBF