全真试题(二) 本试卷分两部分,第一部分为选择题,1页至2页,第二部分为非选择题,3页至10页,共10页;选择 题30分,非选择题70分,满分100分。考试时间150分钟。 第一部分选择题(共30分) 单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个选项中只有一个是符合 题目要求的,请将其代码填在题后的括号内。错选或未选均无分。 1、若结点的存储地址与其关键字之间存在的某种映射关系,则称这种存储结构为() A.顺序存储结构 B链式存储结构 C.索引存储结构 D.散列存储结构 2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素,元素的移动次数为 B n-1 C 3.对于只在表的首尾两端进行插入操作的线性表,宜采用的存储结构为( A.顺序表 B用头指针表示的单循环链表 C.用尾指针表示的单循环链表D单链表 4.若进栈序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同排列个数为() B.5 D.7 5.为查找某一特定单词在文本中出现的位置,可应用的串运算是 A.插入B删除C串联接D子串定位 6.已知函数Sub(sij)的功能是返回串s中从第i个字符起长度为j的子串,函数 Scopy(st)的功能为复制串 t到s。若字符串S=“ SCIENCESTUDY”,则调用函数 Scopy(PSub(S,1,7)后得到() A.P=“ SCIENCE”BP=“ STUDY”C.S=“ SCIENCE”DS=“ STUDY” 7.三维数组h[4[5J6按行优先存储方法存储在内存中,若每个元素占2个存储单元,且数组中第一个元 素的存储地址为120,则元素A[3]4[5]的存储地址为() A.356 B.385 C.360D.362 8.如右图所示广义表是一种() A线性表B纯表C结点共享表D递归表 9.下列陈述中正确的是() A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点 D二叉树中最多只有两棵子树,并且有左右之分 10.n个顶点的有向完全图中含有有向边的数目最多为() B Cn(n-1)/2 D n(n-1) 11.已知一个有向图如右所示 则从顶点a出发进行深度优先遍历, 不可能得到的DFS序列为() Aadbefc Badcefb Cadc bfe D. b 12.在最好和最坏情况下的时间复杂度均为O( nlogn)且稳定的排序方法是() A.快速排序B堆排序C归并排序D基数排序 13.不可能生成右图所示二叉排序树的关键字序列是()全真试题（二） 本试卷分两部分，第一部分为选择题，1 页至 2 页，第二部分为非选择题，3 页至 10 页，共 10 页；选择 题 30 分，非选择题 70 分，满分 100 分。考试时间 150 分钟。 第一部分 选择题（共 30 分） 一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）在每小题列出的四个选项中只有一个是符合 题目要求的，请将其代码填在题后的括号内。错选或未选均无分。 1、若结点的存储地址与其关键字之间存在的某种映射关系，则称这种存储结构为（ ） A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 2. 在长度为 n 的顺序表的第 i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为（ ） A.n-i+1 B.n-i C.i D.i-1 3. 对于只在表的首.尾两端进行插入操作的线性表，宜采用的存储结构为（ ） A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 4. 若进栈序列为 a，b，c，则通过入出栈操作可能得到的 a，b，c 的不同排列个数为（ ） A.4 B.5 C.6 D.7 5. 为查找某一特定单词在文本中出现的位置，可应用的串运算是（ ） A.插入 B.删除 C.串联接 D.子串定位 6. 已知函数 Sub(s,i,j)的功能是返回串 s 中从第 i 个字符起长度为 j 的子串，函数 Scopy(s,t)的功能为复制串 t 到 s。若字符串 S=“SCIENCESTUDY”，则调用函数 Scopy(P,Sub(S,1,7)后得到（ ） A.P=“SCIENCE” B.P=“STUDY” C.S=“SCIENCE ” D.S=“STUDY” 7. 三维数组 h[4][5][6]按行优先存储方法存储在内存中，若每个元素占 2 个存储单元，且数组中第一个元 素的存储地址为 120，则元素 A[3][4][5]的存储地址为（ ） A.356 B.385 C.360 D.362 8. 如右图所示广义表是一种（ ） A.线性表 B.纯表 C.结点共享表 D.递归表 9. 下列陈述中正确的是（ ） A.二叉树是度为 2 的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为 2 的结点 D.二叉树中最多只有两棵子树，并且有左右之分 10. n 个顶点的有向完全图中含有有向边的数目最多为（ ） A.n-1 B.n C.n(n-1)/2 D.n(n-1) 11. 已知一个有向图如右所示， 则从顶点 a 出发进行深度优先遍历， 不可能得到的 DFS 序列为（ ） A.a d b e f c B.a d c e f b C.a d c b f e D.a d e f c b 12. 在最好和最坏情况下的时间复杂度均为 O(nlogn)且稳定的排序方法是（ ） A.快速排序 B.堆排序 C.归并排序 D.基数排序 13. 不可能生成右图所示二叉排序树的关键字序列是（ ） p b a d c e f 1 2 3 5 4