4《数据结构导论》复习题.docVIP

数据结构导论 模拟试题 一、考试题型及分值分布： 1、单项选择题(本大题共15小题，每小题2分，共30分) 2、填空题(本大题共13小题，每小题2分，共26分) 3、应用题(本大题共5小题，每小题6分，共30分) 4、算法设计题(本大题共2小题，每小题7分，共14分) 二、单项选择题和填空题样题参考 （一）单项选择题 1. 在二维数组中，每个数组元素同时处于（ ）个向量中。 A. 0 B. 1 C. 2 D. n 2. 已知单链表A长度为m，单链表B长度为n，它们分别由表头指针所指向，若将B整体连接到A的末尾，其时间复杂度应为（ ）。 A. O(1) B. O(m) C. O(n) D. O(m+n) 3. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 4. 若让元素1,2,3依次进栈，则出栈次序不可能出现( )种情况。 A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,2 5. 图的广度优先有哪些信誉好的足球投注网站类似于树的（ ）遍历。 A. 先根 B. 中根 C. 后根 D. 层次 6. 下面程序段的时间复杂度为( )。 for(int i=0; im; i++) for(int j=0; jn; j++) a[i][j] = i*j; A. O(m2) B. O(n2) C. O(m*n) D. O(m+n) 7. 设有两个串t和p，求p在t中首次出现的位置的运算叫做（ ）。 A. 求子串 B. 模式匹配 C. 串替换 D. 串连接 8 利用双向链表作线性表的存储结构的优点是（ ）。 A. 便于单向进行插入和删除的操作 B. 便于双向进行插入和删除的操作 C. 节省空间 D. 便于销毁结构释放空间 9. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行( )操作。 A. top-link=s; B. s-link=top-link; top-link=s; C. s-link=top; top=s; D. s-link=top; top=top-link; 10. 一棵具有35个结点的完全二叉树的高度为( )。假定空树的高度为-1。 A. 5 B. 6 C. 7 D. 8 11. 一个有n个顶点和n条边的无向图一定是( ) 的。 A．连通 B．不连通 C．无回路 D．有回路 12. 在一个长度为n的顺序表的任一位置插入一个新元素的时间复杂度为（ ）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 13. 已知广义表为A((a,b,c),(d,e,f))，从A中取出原子e的运算是（ ）。 A．Tail(Head(A)) B．Head(Tail(A)) C．Head(Tail(Head(Tail(A)))) D．Head(Head(Tail(Tail(A)))) 14. 在一棵树的静态双亲表示中，每个存储结点包含( )个域。 A 1 B 2 C 3 D 4 15. 有向图中的一个顶点的度数等于该顶点的( )。 A．入度 B．出度 C．入度与出度之和 D．(入度+出度)/２ 15. 与邻接矩阵相比，邻接表更适合于存储( )。 A．无向图 B．连通图 C．稀疏图 D．稠密图 17. 较快的数据有哪些信誉好的足球投注网站方法是（ ）有哪些信誉好的足球投注网站方法。 A. 顺序 B. 折半 C. 单链 D. 散列 18. 在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（ ）引起的。 A. 同义词之间发生冲突 B. 非同义词之间发生冲突 C. 同义词之间或非同义词之间发生冲突 D. 散列表“溢出” 19. 根据n个元素建立一个有序单链表的时间复杂度为（ ）。 A. O(1) B. O(n) C. O(n2) D. O(n