1 / 25 数据结构课程（本科）期末针对性训练训练第一套一、单项选择题，在括号内填写所选择的标号（每小题2 分，共 18 分） 1. 若需要利用形参直接访问实参，则应把形参变量说明为( )参数。 A. 指针 B. 引用 C. 传值 D. 常值 2. 在二维数组中，每个数组元素同时处于（）个向量中。A. 0B. 1 C. 2 D.n 3. 已知单链表A 长度为 m，单链表 B 长度为 n，它们分别由表头指针所指向，若将 B整体连接到 A 的末尾，其时间复杂度应为（）。 A.O(1)B. O(m) C. O(n) D. O(m+n) 4. 假定一个链式队列的队头和队尾指针分别为front和 rear ，则判断队空的条件为( )。 A. front==rearB. 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 6. 在一棵高度为5( 假定树根结点的高度为0) 的完全二叉树中，所含结点个数至少等于( )。 A. 16 B. 64C. 31D. 32 7. 向具有 n 个结点的二叉搜索树中插入一个结点的时间复杂度大致为( )。A. O(1) B. O(log2n ) C. O(n) D. O(nlog2n) 8. 具有 n 个顶点的有向图最多可包含有( )条有向边。A．n-1 B．n C． n(n-1)/2 D．n(n-1) 9. 图的广度优先搜索类似于树的（）遍历。A. 先根 B. 中根 C. 后根 D. 层次二、填空题，在横线处填写合适的内容（每小题2 分，共 14 分）1. 链表只适用于 ____________查找。2. 设双向循环链表中每个结点的结构为(data,llink,rlink),则结点 *p 的前驱结点的地址为__________。3. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有________个2 / 25 结点。 4. 假定一棵树的广义表表示为a(b,c,d(e,f),g(h))，则结点f 的层数为 _________。假定树根结点的层数为0。5. 从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向根的 ________继续搜索。6. 每次从第 i 至第 n 个元素中顺序挑选出一个最小元素，把它交换到第i 个位置，此种排序方法叫做 _____________ 排序。7. 快速排序在最坏情况下的时间复杂度为____________。三、判断题， 在每小题前面打对号表示正确或打叉号表示错误（每小题 2 分，共 14 分） 1. 数据的逻辑结构与数据元素本身的内容和形式无关。 2. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。3. 在一棵...
VIP
