数据结构期末考试题目（10套含答案）

【实例简介】
数据结构10套考试题目+答案解析，我们的期末考试题目基本都是从里面出的，全部刷一遍保证85+，分享给学弟学妹们
图 四、阅读算法(每题分,共分) 是不带头结点的单链表的头指针 请回答下列问题: ()说明语句的功能; 查询链表的尾结点 )说明语句组的功能; 将第一个结点链接到链表的尾部,作为新的尾结点 ()设链表表示的线性表为( )写出算法执行后的返回值所表示的线性 表 返回的线性表为( 该算法的功能是: 递归地后序遍历链式存储的二叉树 五、算法填空(共分) 叉搜索树的査找—递归算法: bool Find(BTreeNode* BST, Elem Type& item) if (BSt==NULL) return false;//查找失败 e⊥se f(item--BST->dataI item= bst >data;/查找成功 return true; else if(item<BST->data) return Find( BST->left, item) else return Find( BST->right, item if 六、编写算法(共分) 统计出单链表结点的值等于给定值的结点数。 int CountX(LNode* HL, ElemType x) 为计数器 出循环时中的值即为结点个数 数据结构试卷(二) 、选择题(24分) 下面关于线性表的叙述错误的是() (A)线性表采用顺序存储必须占用一片连续的存储空间 (B)线性衣采用链式存储不必占用片连续的存储空间 (C)线性表采用链式存储便于插入和删除操作的实现 D)线性表采用顺序存储便于插入和删除操作的实现 2.设哈夫曼树中的叶子结点总数为Ⅲ,若用二叉链表作为存储结构,则该哈夫曼树中总共 有()个空指针域。 (A)2m-1 (B)2m (C)2m+1 (D)4m 设顺序循坏队列Q0:M-1的头指针和尾指针分别为F和R,头指针F总是指向队头元素 的前一位置,尾指针R总是指向队尾元索的当前位置,则该循环队列中的元素个数为 (A)R-F (B)F-R (C)(R-F+M%M(D)(F-R+M)%M 设某棵二叉树的中序煸历序列为 前序遍历序列为 则后序谝历该二叉树 得到序列为() (A) BADC (B)BCDA (C) CDAB (D) CBDA 5.设某完全无向图中有n个顶点,则该完全无向图中有()条边 (A)n(n-1)/2(B)n(n-1) (C)n (D)n2-1 6.设某棵二叉树中有2000个结点,则该二叉树的最小高度为() (A)9 (B)10 ()11 (D)12 解析:区别:树的高度的定义,只有一个节点的树的高度为0(则该题选择B) 7.设某有向图中有n个顶点,则该有向图对应的邻接表中有()个表头结点。 (B) D)2n1 8.设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快 速排序的结果为() (A)2,3,5,8,6 (B)3,2,5,8,6 (C)3,2,5,6,8 (D)2,3,6,5,8 解析: pivots==i时则不交换,i+ 三、应用题(36分) 1.设·组初始记录关键字序列为(45,80,48,40,22,78),则分别给出第4趟简单选择 排序和第4趟直接插入排序后的结果 (②22,40,45,48,80,78),(22,40,45,48,80,78) 2.设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A 的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为11ink和 rlink) 3.设·组有序的记录关键宇序列为(13,18,24,35,47,50,62,83,90),查找方法用 二分查找,要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长 度 2,ASL=(1*1+2*2+3*4+4*2)=25/9 A.设一棵树T中边的集合为 ,,要求 用孩子兄弟表示法(叉链表〕表示出该树的存储结构并将该树转化成对应的叉树。 树的链式存储结构略,二叉树略 5.设有无向图G,要求给出用普里姆算法构造最小生成树所走过的边的集合。 6 6.设有一组初始记录关键字为(45,80,48,40,22,78),要求构造一棵二叉排序树并给 出构造过程 四、算法设计题(16分) 1.设有一组初始记录关键字序列(K,K2,…,K),要求没计一个算法能够在0(n)的时间 复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于K,右半部分的每 个关键字均大于等于K 设有一组初始记录关键字序列(K1,K2,…,Kn),要求设计一个算法能够在0(n)的时间复 杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于K1,右半部分的每个关 键字均大于等于K。 2.设有两个集合A和集合B,要求设计生成集合C=A∩B的算法,其中集合A、B和C用链 式存储结构表示 数据结构试卷(三) 、选择题(每题1分,共20分) 1.设某数据结构的二元组形式表示为 ,则数据结构A是()。 (A)线性结构(B)树型结构(C)物理结构(D)图型结构 下面程序的时间复杂为() ( (A)0() (B)0(n2) (D)0(n) 设指针变量指向单链表中结点,若删除单链表中结点 需要修改指针的操作序 列为() (A)g=p->next: p->data=q->data; p->next=q->next: free(g) (B)qp->next: q>data p->data; p->next g->next; free(q (C)g=p->next: p->next=g->next; free(q); (D)q=p->next: p->data=g->data; free(g); 4.设有n个待排序的记录关键字,则在堆排序中需要()个辅助记录单元。 (A)1 (B)n (C)logan (D)n 解析:每次进行一次交换,只需要一个temp的位置即可 5.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记 录的一趟快速排序结束后的结果为()。 (A)10,15,14,18,20,36,40,21 (B)10,15,14,18,20,40,36,21 (C)10,15,14,20,18,40,36,21 (D)15,10,14,18,20,36,10,21 注意:10的时候 pivots++ 6.设二叉排序树中有n个结点,则在二叉排序树的平均平均查找长度为() (A)0(1) (B)0(1ogn)(C) (D)0(mn2) 7.设无向图G中有个顶点条边,则其对应的邻接表中的表头结点和表结点的个数分别 为()。 (D )n,2e 8.设某强连通图有个顶点,则该强连通图中至少有()条边。 (A)n(n-1) (B)n+1 (C)n D)n(n+1) 注意:存在vi→vj,必然有vj→vi,但是到达的路径长度没有限制 9.设有5000个待排序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关 键字,则用下列()方法可以达到此目的 (A)快速排序(B)堆排序(C)归并排序(D)插入排序 10.下列四种排序中()的空间复杂度最大 (A)插入排序(B)冒泡排序(C)堆排序ABC0(1)(D)归并排序0(n) 快速排序0(1ogn) 三、计算题(每题10分,共30分) 已知二叉树的前序遍历序列是 ,中序遍历序列是 ,画出此 二叉树,并画出它的后序线索二叉树。 B NCLL (F) 知待散列的线性表为(,,,,),散列用的一维地址空为 假定 选用的散列函数是() ,若发生冲突采用线性探査法处理,试 .冲突 …冲突 冲突 ()计算出每一个儿素的散列地址并在下图中填写出散列表 ()求出在查找每一个元素概率相等情况下的平均查找长度。 ++ 已知序列( )请用快速排序写出每趟排序的结果 四、算法设计题(每题15分,共30分) 1.设计在单链表中删除值相同的多余结点的算法。 设计在单链表中删除值相同的多余结点的算法。 2.设计一个求结点x在二叉树中的双亲结点算法 设计一个求结点x在二叉树中的双亲结点算法。 【实例截图】
【核心代码】