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

数据结构课程（本科）期末针对性训练训练第一套 一、单项选择题，在括号内填写所选择的标号（每小题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个顶点的有向图最多可包含有( )条有向边。 An-1 Bn Cn(n-1)/2 Dn(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树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。 四、运算题（每小题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， E=, 在该图的邻接表表示中，每个顶点单链表各有多少个边结点。 顶点： a b c d e 边结点数： 4. 已知一个AOV网的顶点集V和边集G分别为： V=0,1,2,3,4,5,6,7; E=,; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列。 拓扑序列： 5. 已知有一个数据表为30,16,20,15,38,12,44,53,46,18,26,86，给出进行归并排序的过程中每一趟排序后的数据表变化。(0) 30 16 20 15 38 12 44 53 46 18 26 86(1)(2)(3)(4) 五、算法分析题（每小题6分，共12分） 1. 该算法功能为：从表头指针为la的、按值从小到大排列的有序链表中删除所有值相同的多余元素，并释放被删结点的动态存储空间。阅读算法，在划有横线的上面填写合适的内容。 void purge_linkst(ListNode *& la) ListNode *p,*q; if(la=NULL) return; q=la; p=la-link; while(p) if(p-dataq-data) q=p; p=p-link; else q-link= _; delete(p); p=_; 2. 已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data; BinTreeNode *left, *right; 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是从二叉树BT中查找值为X的结点，若查找成功则返回结点地址，否则返回空。阅读算法，在划有横线的上面填写合适的内容。 BinTreeNode* BTF(BinTreeNode* BT, ElemType x) if(BT=NULL) NULL; else if(BT-data=x) _; else BinTreeNode* t; if(t=BTF(BT-left, x) return t; if(t=_ ) return t; return NULL; 六、算法设计题（每小题6分，共12分） 1. Q 是一个由其队尾指针和队列长度标识的循环队列，请写出插入一个元素的算法。 struct CyclicQueue / 循环队列定义 ElemType elemM; /M为已定义过的整型常量 int rear; / rear指向队尾元素的后一个位置 int length; / length 指示队列中元素个数 ; bool EnCQueue(CyclicQueue& Q, ElemType x); /Q是一个循环队列，若队列不满，则将x插入并返回true；否则返回false。 /在下面写出该函数的函数体 2. 已知二叉搜索树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data; BinTreeNode *left, *right; 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数BST指向一棵二叉搜索树的根结点。试根据下面的函数声明编写一个递归算法，向BST树中插入值为item的结点，要求若树中不存在item结点则进行插入并返回1表示插入成功，若树中已存在item结点则不插入并返回0表示插入失败。 int Insert(BinTreeNode*& BST, const ElemType& item);答案供参考 一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1. B 2. C 3. B 4. D 5. C 6. D 7. B 8. D 9. D 二、填空题，在横线处填写合适内容（每小题2分，共14分） 1. 顺序 2. p-llink 3. 1 4.2 5. 右子树 6. 直接选择 7. O(n2) 三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题2分，共14分） 1. 对 2. 对 3. 对 4. 错 5. 错 6. 对 7. 错 四、运算题（每小题6分，共30分） 1. 先序：a,b,c,g,d,e,f /2分 中序：c,g,b,a,e,d,f /2分 后序：g,c,b,e,f,d,a /2分 2. 带权路径长度：131 3. 评分标准：每个数据对给1分，全对给6分。 顶点： a b c d e 边结点数： 1 1 2 1 2 4. 评分标准：若与答案完全相同得6分，若仍为一种拓扑序列则得3分，其他则酌情处理。 拓扑序列：1,3,6,0,2,5,4,7 5. 分步给分 (0) 30 16 20 15 38 12 44 53 46 18 26 86 (1) 16 3015 2012 3844 5318 4626 86 /1分 (2) 15 16 20 3012 38 44 5318 26 46 86 /1分 (3) 12 15 16 20 30 38 44 5318 26 46 86 /2分 (4) 12 15 16 18 20 26 30 38 44 46 53 86 /2分 五、算法分析题（每小题6分，共12分） 1. p-link、q-link /每空3分 2. return BT、BTF(BT-right, x) /每空3分 六、算法设计题（每小题6分，共12分） 评分标准：根据编程完整程度酌情给分。 1. bool EnCQueue(CyclicQueue& Q, ElemType x); if(Q.length=M) return false; /1分 Q.elemQ.rear=x; /2分 Q.rear=(Q.rear+1)%M; /4分 Q.length+; /5分 return true; /6分 2. int Insert(BinTreeNode*& BST, const ElemType& item) if(BST=NULL) BinTreeNode* p=new BinTreeNode; p-data=item; p-left=p-right=NULL; BST=p; return 1; /3分 else if(item=BST-data) return 0; /4分 else if(itemdata) return Insert(BST-left, item); /5分 else return Insert(BST-right, item); /6分 说明：函数体中的三个else保留字均可以被省略。训练第二套 一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1. 下面程序段的时间复杂度为( )。 for(int i=0; im; i+) for(int j=0; jlink=s; B. s-link=top-link; top-link=s; C. s-link=top; top=s; D. s-link=top; top=top-link; 6. 一棵具有35个结点的完全二叉树的高度为( )。假定空树的高度为-1。 A. 5 B. 6 C. 7 D. 8 7. 向具有n个结点的堆中插入一个新元素的时间复杂度为( )。 A. O(1) B. O(n) C. O(log2n) D. O(nlog2n) 8. 在一棵AVL树中，每个结点的平衡因子的取值范围是( )。 A. -11 B. -22 C. 12 D. 01 9. 一个有n个顶点和n条边的无向图一定是( ) 的。 A连通 B不连通 C无回路 D有回路 二、填空题，在横线处填写合适的内容（每小题2分，共14分） 1. 数据结构包括_、存储结构和对数据的运算这三个方面。 2. 一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的_存取的。 3. 将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则该一维数组需要至少具有_个元素。 4. 对于一棵具有n个结点的树，该树中所有结点的度数之和为_。 5. 在一棵高度为3的理想平衡二叉树中，最少含有_个结点，假定树根结点的高度为0。 6. 假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底层的结点数为_个。 7. 用邻接矩阵存储图，占用的存储空间与图中的_数有关。 三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题2分，共14分） 1. 算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。 2. 用字符数组存储长度为n的字符串，数组长度至少为n+1。 3. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 4. 邻接矩阵适用于稀疏图的表示，邻接表适用于稠密图的表示。 5. 对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。 6. 在索引顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。 7. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。 四、运算题（每小题6分，共30分） 1. 假定一棵二叉树广义表表示为a(b(c),d(e,f)，分别写出对它进行中序、后序、按层遍历的结果。 中序： 后序： 按层： 2. 一个一维数组a12中存储着有序表(15,26,34,39,45,56,58,63,74,76,80,86)，根据折半搜索所对应的判定树，写出该判定树中度为1的结点个数，并求出在等概率情况下进行成功搜索时的平均搜索长度。 度为1的结点个数： 平均搜索长度： 3. 假定一个线性序列为(38,42,55,15,23,44,30,74,48,26)，根据此线性序列中元素的排列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点、右子树为空的所有单支结点和所有叶子结点，请按照结点值从小到大的次序写出。 左子树为空的所有单支结点： 右子树为空的所有单支结点： 所有叶子结点： 4. 已知一个图的顶点集V和边集G分别为： V=1,2,3,4,5,6; E=,; 假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出： (1) 从顶点1出发进行深度优先搜索所得到的顶点序列； (2) 从顶点1出发进行广度优先搜索所得到的顶点序列。 (1)： (2)： 5. 已知一个数据序列为16,45,27,23,41,15,56,64，请把它调整为一个最大堆。 最大堆： 五、算法分析题（每小题6分，共12分） 1. 下面算法的功能为：将两个有序单链表合并成一个有序单链表并返回其表头指针。阅读算法，在划有横线的上面填写合适的内容。 ListNode* Merge1(ListNode*& p1, ListNode*& p2) ListNode* p=new ListNode, *f=p; while(p1!=NULL & p2!=NULL) if(p1-datadata) p-link=p1; _; else p-link=p2; p2=p2-link; _; if(p1!=NULL) p-link=p1; else p-link=p2; p1=p2=NULL; return f-link; 2. 已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data; BinTreeNode *left, *right; 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面算法的定义指出其功能。算法中参数BT指向一棵二叉树。 BinTreeNode* BTreeSwopX(BinTreeNode* BT) if(BT=NULL) return NULL; else BinTreeNode* pt=new BinTreeNode; pt-data=BT-data; pt-right=BTreeSwopX(BT-left); pt-left=BTreeSwopX(BT-right); return pt; 算法功能： 六、算法设计题（每小题6分，共12分） 1. 已知f为单链表的表头指针, 单链表中的结点结构为(data,link），并假定每个结点的值均为大于0的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若单链表为空则返回数值0。 int Max(LinkNode *f); 2. 设Q是一个由其队尾指针和队列长度标识的循环队列，按照下面队列定义和函数声明写出从此队列中删除一个元素的算法。 / 循环队列定义 struct CyclicQueue ElemType elemM; /M为已定义过的整型常量 int rear; /rear指向队尾元素的后一个位置 int length; /length 指示队列中元素个数 ; /若队列非空则删除队头元素并由引用参数x带回，同时返回true；否则若队列为空则返回false。 bool DelCQueue(CyclicQueue& Q, ElemType& x);答案供参考 一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1. C 2. C 3. B 4. B 5. C 6. A 7. C 8. A 9. D 二、填空题，在横线处填写合适的内容（每小题2分，共14分） 1. 逻辑结构 2. 下标（或顺序号） 3. n(n+1)/2 4. n-1 5. 8 6. 19 7. 顶点 三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题2分，共14分） 1. 错 2. 对 3. 对 4. 错 5. 对 6. 错 7. 对 四、运算题（每小题6分，共30分） 1. 中序：c,b,a,e,d,f /2分 后序：c,b,e,f,d,a /2分 按层：a,b,d,c,e,f /2分 2. 度为1的结点个数：5 /3分 平均搜索长度：37/12 /3分 3. 左子树为空的所有单支结点：15,23,42,44 /2分 右子树为空的所有单支结点：30 /2分 所有叶子结点：26,48,74 /2分 4. (1) 1,2,4,5,3,6 /3分 (2) 1,2,3,4,5,6 /3分 5. 最大堆： 64,45,56,23,41,15,27,16 五、算法分析题（每小题6分，共12分） 1. p1=p1-link、p=p-link /每空3分 2. 生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右子树（或左、右孩子的值）交换的结果。 六、算法设计题（每小题6分，共12分） 1. 评分标准：按注释酌情给分。 int Max(LinkNode *f) if(f=NULL) return 0; /1分 if(f-link=NULL) return f-data; /2分 int temp=Max(f-link); /4分 if(f-datatemp) return f-data; /5分 else return temp; /6分 2. 评分标准：按注释酌情给分。 bool DelCQueue(CyclicQueue& Q, ElemType& x) if(Q.length=0) return false; /1分 x=Q.elem(Q.rear-Q.length+M)%M; /4分 Q.length-; /5分 return true; /6分 训练第三套 一、单项选择题，在括号内填写所选择的标号（9小题，每小题2分，共18分） 1. 当一个作为实际参数传递的对象占用的存储空间较大并且需要修改时，则对应的形参应说明为( )。 A. 基本类型 B. 引用型 C. 指针型 D. 常值引用型 2. 在一个长度为n的顺序表的任一位置插入一个新元素的时间复杂度为（ ）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 3. 栈的插入和删除操作在( )进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 4. 已知广义表为A(a,b,c),(d,e,f)，从A中取出原子e的运算是（ ）。 ATail(Head(A) BHead(Tail(A) CHead(Tail(Head(Tail(A) DHead(Head(Tail(Tail(A) 5. 在一棵树的静态双亲表示中，每个存储结点包含( )个域。 A 1 B 2 C 3 D 4 6. 有向图中的一个顶点的度数等于该顶点的( )。 A入度 B出度 C入度与出度之和 D(入度+出度)/ 7. 与邻接矩阵相比，邻接表更适合于存储( )。 A无向图 B连通图 C稀疏图 D稠密图 8. 较快的数据搜索方法是（ ）搜索方法。 A. 顺序 B. 折半 C. 单链 D. 散列 9. 在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（ ）引起的。 A. 同义词之间发生冲突 B. 非同义词之间发生冲突 C. 同义词之间或非同义词之间发生冲突 D. 散列表“溢出” 二、填空题，在横线处填写合适内容（12小题，每小题1分，共12分） 1. 算法的一个特性是_，即算法必须在执行有限步之内结束。 2. 属性与操作相同的对象构成类，类中的每个对象称为该类的_。 3. 在单链表中, 除了表头结点外, 任意结点的存储位置由其直接_结点的指针域的值所指示。 4. 队列的删除操作在_进行。 5. 在一个非空广义表中，除第一个元素之外，由其他所有元素组成的表称为该广义表的_。 6. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有_个。 7. 在一个最小堆中，堆顶结点的值是所有结点中的_。 8. 在一棵具有n个结点的AVL树上进行插入或删除元素的时间复杂度大致为_。 9. 在对n个元素进行直接选择排序的算法中，记录比较总次数的时间复杂度为_。 10. 在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用_次调整算法。 11. 在索引表中，每个索引项至少包含有_域和地址域这两项。 12. 在一棵m阶的B树上，除树根结点外，每个结点的子树数至少为_棵。 三、判断题，在每小题前面打对号表示正确或打叉号表示失败（10小题，每小题1分，共10分） 1. 线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。 2. 在线性链表中删除结点时，只需要将被删结点释放，不需要修改任何指针。 3. 在用单链表表示的链式队列Q中，假定队头指针为Q-front，队尾指针为Q-rear，则链队为空的条件为Q-front=Q-rear。 4. 一棵AVL树的所有叶结点不一定在同一层次上，同样，平衡的m路搜索树的叶结点也不一定在同一层次上。 5. 一个广义表(a),(b),c),(d)的表尾是“(b),c),(d)”。 6. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，若对它分别进行中序遍历和后序遍历，则具有相同的结果。 7. 折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。 8. 对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。 9. 如果有向图中各个顶点的度都大于2，则该图中必有回路。 10. 堆排序是一种稳定的排序方法。 四、运算题（5小题，每小题6分，共30分） 1. 假定一棵二叉树的广义表表示为A(B(,D(G),C(E,F)，分别写出对它进行先序、中序、按层遍历的结果。 先序： 中序： 按层： 2. 已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组a12中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。3456586394 元素 比较次数 3. 假定一个线性序列为(56,27,34,95,73,16,50,62,65)，根据此线性序列中元素的排列次序生成一棵二叉搜索树，求出该二叉搜索树的高度（假定树根结点的高度为0）、度为2的结点个数、单支结点数和叶子结点个数。 高度： 度为2的结点个数： 单支结点数： 叶子结点数： 4. 已知一个带权图的顶点集V和边集G分别为： V=0,1,2,3,4,5; E=(0,1)19,(0,2)21,(0,3)14,(1,2)16,(1,5)5,(2,3)26,(2,4)11,(3,4)18,(4,5)6; 试根据普里姆算法从顶点0出发得到最小生成树，在下面填写依次得到的各条边。 _, _, _, _, _。 5. 设散列表的长度m=13；散列函数为H (K)=K mod m，给定的关键码序列为19,14,23,40,68,20,84,27,55,11，并假定采用的闭散列表为HTm，采用的解决冲突的方法为线性探查法，求出在最后得到的散列表中，关键码19,40,84和55的存储位置和对应的查找长度。 19,40,84,55的存储位置依次为： 19,40,84,55的查找长度依次为： 五、算法分析题（3小题，每小题6分，共18分） 1. 设单链表的存储结构为ListNode=(data,link)，表头指针为LH，所存线性表L=(a,b,c,d,e,f,g)，若执行unknown(LH)调用下面算法，则写出执行结束后的输出结果。 void unknown（LinkNode *Ha） /Ha为指向单链表的头指针 if(Ha) unknown(Ha-link); coutdata; 输出结果： 2. 下面算法的功能为：将两个有序单链表合并成一个有序单链表并返回其表头指针。阅读下列算法, 按标号填写空缺的内容，要求统一填写在算法后面的标记处。 ListNode* Merge1(ListNode*& p1, ListNode*& p2) ListNode* p=new ListNode, *f=p; while(p1!=NULL & p2!=NULL) if(p1-datadata) _(1)_; p1=p1-link; if(p1-datap2-data) p-link=p2; p2=p2-link; else p-link=p1; p1=p1-link; p=p-link; p-link=p2; p2=p2-link; _(2)_; if(p1!=NULL) p-link=p1; else _(3)_; p1=p2=NULL; return f-link; (1) (2) (3) 3. 已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data; BinTreeNode *left, *right; 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面算法的定义指出其功能。算法中参数BT指向一棵二叉树。 BinTreeNode* BTreeSwopX(BinTreeNode* BT) if(BT=NULL) return NULL; else BinTreeNode* pt=new BinTreeNode; pt-data=BT-data; pt-right=BTreeSwopX(BT-left); pt-left=BTreeSwopX(BT-right); return pt; 算法功能： 六、算法设计题（2小题，每小题6分，共12分） 1. Q 是一个由其队尾指针和队列长度标识的循环队列，请写出插入一个元素的算法。 struct CyclicQueue / 循环队列定义 ElemType elemM; /M为已定义过的整型常量 int rear; / rear指向队尾元素的后一个位置 int length; / length 指示队列中元素个数 ; bool EnCQueue(CyclicQueue& Q, ElemType x); /Q是一个循环队列，若队列不满，则将x插入并返回true；否则返回false。 /在下面写出该函数的函数体 2. 已知二叉搜索树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data; BinT