数据结构课程(本科)期末针对性训练(4份含答案)(g).docVIP

数据结构课程（本科）期末针对性训练 训练第一套 一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1. 若需要利用形参直接访问实参，则应把形参变量说明为( )参数。 A. 指针 B. 引用 C. 传值 D. 常值 2. 在二维数组中，每个数组元素同时处于（ ）个向量中。 A. 0 B. 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 == 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 6. 在一棵高度为5(假定树根结点的高度为0)的完全二叉树中，所含结点个数至少等于( )。 A. 16 B. 64 C. 31 D. 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. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有________个结点。 4. 假定一棵树的广义表表示为a(b,c,d(e,f),g(h))，则结点f的层数为_________。假定树根结点的层数为0。 5. 从一棵二叉有哪些信誉好的足球投注网站树中有哪些信誉好的足球投注网站一个元素时，若给定值大于根结点的值，则需要向根的________继续有哪些信誉好的足球投注网站。 6. 每次从第i至第n个元素中顺序挑选出一个最小元素，把它交换到第i个位置，此种排序方法叫做_____________排序。 7. 快速排序在最坏情况下的时间复杂度为____________。 三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题2分，共14分） 1. 数据的逻辑结构与数据元素本身的内容和形式无关。 2. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。 3. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，则对它分别进行前序遍历和按层遍历时具有相同的结果。 4. 能够在链接存储的有序表上进行折半有哪些信誉好的足球投注网站，其时间复杂度与在顺序存储的有序表上相同。 5. 邻接表表示只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 6. 在索引顺序结构上实施分块有哪些信誉好的足球投注网站，在等概率情况下，其平均有哪些信誉好的足球投注网站长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。 7. 向一棵B树 四、运算题（每小题6分，共30分） 1. 假定一棵二叉树广义表表示为a(b(c(,g)),d(e,f))，分别写出对它进行先序、中序和后序遍历的结果。 先序： 中序： 后序： 2. 有7个带权结点，其权值分别为3,7,8,2,6,10,14，试以它们为叶子结点生成一棵霍夫曼树，求出该树的带权路径长度。 带权路径长度： 3. 已知图G=(V,E)，其中 V={a,b,c,d,e}，