《数据结构考试试题总结 期末》由会员分享，可在线阅读，更多相关《数据结构考试试题总结 期末（8页珍藏版）》请在金锄头文库上搜索。
1、数据结构考试模拟题(单独整理)一、选择题1以下结构中逻辑结构不是线性结构的是（ D ）A 栈 B 队列 C 串 D 线索二叉树/ 数据的逻辑结构分为线性结构和非线性结构。/ 线性结构：数组，链表，栈，队列，优先级队列/ 非线性结构：树，图，网络2如下算法的最坏时间复杂度为（ C ）for(i=n-1;i=1;-i)for(j=1;jaj+1)aj与 aj+1对换;其中 n 为正整数。A 0(n) B 0(nlogn) C 0(n2 ) D 0(n3)3下列说法错误的是（ C ）A 采用顺序存储占用一片连续的存储空间，可随机存取B 采用链式存储在进行插入和删除错做是不需要移动元素，但只能顺序访问
2、各元素C 满二叉树采用顺序存储结构会浪费大量存储时间D 3 阶 B-树中节点内关键字的个数为 1 或者 24设指针变量 p 指向单链表节点 A，则删除节点 A 的后继结点 B 需要的操作为（ A ）A p-next=p-next-nextB p=p-nextC p=p-next-nextD p-next=p5设入栈序列为 123，则可能的出栈序列不包括（ D ）A 123 B 132 C 213 D 3126某二叉树有 n 各叶子节点，且当中不存在度为 1 的节点，则该二叉树中共有节点数（ C ）A (n-1)/2 B (n+1)/2 C 2n-1 D 2n+17对于一个具有 n 各顶点和 e
3、 条边的无向图，若采用邻接表存储结构进行表示，则除去链表中表节点（弧节点）的数目为（ C ）A e/2 B e C 2e D n+e8对于含 n 个顶点的带权有向图 G，下列说法错误的是（ B ）A 拓扑排序可用于检查图 G 中是否存在有向回路B 关键路径是源点到汇点的最短路径 /最长路径C 位于关键路径上的任意活动的延期大都将影响整个工程的进度D 只需执行一次 Floyd 算法，便可求出任意一对顶点间的最短距离/Floyd 算法的时间复杂度为 O(n3)9以下关于折半查找的说法错误的是（ C ）A 折半查找算法宜在有序顺序表上实现，而不宜在有序单链表上实现B 折半查找的判定树一定是二叉排序树
4、 /二叉排序树的左子树一定比根节点小，右子树一定比根节点大，且每个节点都符合这个规律C 折半查找的判定树一定是满二叉树D 折半查找的判定树一定是平衡二叉树/折半查找的判定树一定是二叉排序树且为平衡二叉树，平衡二叉树是二叉排序树的真子集10下列排序算法中时间复杂度不受数据初始状态影响而恒为 O（n logn）的是（ C ）A 直接插入排序 B 冒泡排序 C 归并排序 D 快速排序11以下排序方法中稳定的是（ B ）A 希尔排序 B 基数排序 C 堆排序 D 快速排序排序方法 平均时间 最坏情况 描述简单排序（直接插入排序等）O(n2) O(n2) 最简答快速排序（快速排序、冒泡排序）O(nlog
5、n)(快速排序)O(n2)（冒泡排序）时间最快O(nlogn) O(nlogn)选择排序(1)堆排序(2)简单选择排序O(n2) O(n2)不稳定归并排序 O(nlogn) O(nlogn) 算法的时间复杂度不受数据初始状态的影响恒为 O(nlogn)希尔排序 O(n2) O(n2)基数排序 O( d(n+rd) ) O( d(n+rd) ) 基数排序是稳定的内部排序方法*以上仅供参考二、填空题1长度为 n 的有序顺序表中进行顺序排序查找的时间复杂度为_O(n) _,折半查找的时间复杂度为_O(logn) _;2 双向循环链表中结点的指针域为 prior 和 next，一直指针变量 p 指向双
6、向循环链表某结点指向一新节点，将 s 所致结点插入到 p 所指结点后面的语句序列 s-next=p-next:_:_:p-next=s;3顺序栈 S 的栈底指针为 S.base，栈顶指针为 S.top，栈空的判定条件是_ S.top=S.base _.栈空：S.top=S.base栈满：S.top-S.base=S.length=S.size栈长：S.top-S.base=S.length4设循环队列 Q 分配有 M 个存储单元，Q.front 和 Q.rear 分别为队头元素下标和队尾元素下标，则循环队列队满的判定条件是_(Q.rear+1)%maxsize=Q.front ；/循环的队列，
7、队空： Q.rear=Q.front 队满： (Q.rear+1)%maxsize=Q.front求队首指针：Q.front=(Q.rear-Q.length+1+maxsize)%maxsize求队长： Q.length=(Q.rear-Q.front+maxsize)%maxsize5已知 n*n 阶上三角矩阵 A，矩阵元素的行、列下标为 1n，将其上三角元素逐行存储于一维数组 S 中（从 0 号单元开始存储） ，则对角线元素 aii 在数组 S 中对应元素的下标为_;6 对于下图所示的树，其对应的二叉树所含叶节点数为_2_; 如上图 A 的第一个孩子为 B，C 是 B 的兄弟，E 是 C
8、 的孩子（第一个） ，F 是 E 的兄弟，G 是 F 的孩子，D 是 C 的兄弟根据二叉树中：左孩子，右兄弟 的原则 (（在由树转换为二叉树的前提下） ，没有树的前提下，则二叉树为“左孩子，右孩子”)7设权值集合 W=(15,3,2,6,9),据此所得 Huffman 数的带权路径长度为_71_;解法：15*1+9*2+6*3+ （2+3）*4=71ABCE DFG20931525 611358 有向图 G 中边的集合 E=,则该图的一个拓扑序列为1 4 2 3 ；用箭头表示 1 到 2,2 到 3,1 到 4，4 到 2,4 到 3，拓扑排序为包含所有节点的最长路径则最长的路径是 1-4-2
9、-3根据上图，拓扑排序则为：第一步：1 没有前驱，则把 1 拿出来，并把 1 的两条线去掉第二步：把 1 以及两条线去掉后，4 没有前驱，把 4 拿出来，然后把 4 和两条指线去掉第三步：经过第二步，2 没有前驱，则把 2 拿出来，并把 2 的一条线去掉9设一组记录的关键字序列为（34,76,45,18,26,54,92） ，则由这组记录关键字生成的二叉排序树的深度为_4_；10 补全算法：输入十进制整数 n，将其转换为八进制整数Void conversion()Scanf(“%d”,n);InitStack(S);While(n!=0)Push（S,n%8）;n=n/8;while(!Sta
10、ckEmpty(S)Pop(S,e) ;printf(“%d”,e);三、应用题1设二叉树先序序列为 ABDEFCGHI,中序序列为 DBFEAGHCI,画出该二叉树，并给出后序序列 先(根) 序遍历: 树非空则访问根结点,后递归地先序遍历其左子树；再递归地先序遍历其右子树；空则无操作。 中(根) 序遍历: 树非空则递归地中序遍历根左子树；后访问根结点,再递归地中序遍历右子树；空则无操作。s2-s1-s324312432 33 后(根) 序遍历: 树非空则递归地后序遍历根左子树；后递归地后序遍历右子树,再访问根结点；空则无操作s2-s3-s1Example:先序输出:1 2 3 4中序输出:3
11、 2 1 4后序输出:3 2 4 11234中序：先左，再根节点，再右后序序列：DFEBHGTCA本题中，先序序列为 ABDEFCGHI中序序列为 DBFEAGHCI1因为先序序列中 A 在最前，则 A 为根节点2在中序序列中 DBEF 在 A 的左边，则为 A 的左子数，GHCI 在 A 的右边，则为 A 的右子树确定每一项的位置，根据先序序列中的每一项，从前往后确定。3确定 B 的位置：B 在 A 的之后，且在 A 的左子树中，B 为 A 的左子树的根节点，即 A 的左孩子；4确定 D 的位置：中序序列中，D 在 B 之前，则 D 为 B 的左孩子；5确定 E 的位置：中序序列中， E 在
12、 B 之后，则 E 为 B 的右孩子；6确定 F 的位置：中序序列中，F 在 B 之后，则为 B 的左子树中的项，F 又在 E 之前，则为 E 的左孩子；7确定 C 的位置：CGHI 在 A 为根节点的右子树中，根据先序序列，则 C 为 A 的右子树的根节点；8确定 G 的位置：中序序列中，在 C 之前，则 G 为 C 的左子树的根节点，即 C 的左孩子；9确定 H 的位置：中序序列中，H 在 C 之前，则为 C 的左子数中的项，H 在 G 之后，则为 G 的右孩子；10确定 I 的位置：中序序列中，I 在 C 之后，则 I 为 C 的右孩子 ABD IFE GHC后序序列：从左往右，从下往上
13、，最后访问根DFEBHGTC2图的邻接矩阵如下所示，分别画出自顶点 A 出发进行遍历所得的深度优先生成树和广度优先生成树，假设邻接点按由小到大的顺序排列深度优先生成树：A-B B-EE-C然后返回B-F F-D广度优先生成树：A-B A-F B-E E-C返回 FF-D3 设一组初始记录关键字集合为（25,17,15,27,32,68） ，散列表的长度为 7，散列函数 H(k)=k mod 7,要求分别用线性探测和连地址法作为解决冲突的方法构造哈希表，并求平均查找长度。线性探测：0 1 2 3 4 5 63 1 1 1 2 1 ASL=（3+1+1+1+2+1）/ 6=9/6=3/2链地址法：
14、68 15 17 25 32 272ABE DCFABEDCFALS=(1+1+1+1+1+2)/6=7/64 设初始记录关键字序列为（20,18,22,16,30,19） ，现对其由小到大进行排序，写出快速排序时以 20 为枢轴进行一趟快速排序后的结果：并画出堆排序时初始大顶堆对应的二叉树。第一次：19 18 16 20 30 22大顶堆：略四、算法设计题要求：（1）用自然语言说明所采用算法的思想（2）给出每个算法所设计的存储结构定义，并作必要的注释或说明；（3）用 C 语言或伪代码写出对应的算法程序，并做必要的注释。1、 二叉树采用二叉链表存储结构，设计算法统计二叉树的深度思路：如果树为空树则深度为 0，否则，先递归计算出左子树的深度，再计算出右子树的深度，最后，树的深度为两子树深度的最大值加 1存储结构定义：typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;C 源代码：int TreeDepth(BiTree T)/递归法求树的深度if(T=NULL)d=0;elsed1=TreeDepth(T-lchild1);d2=TreeDepth(T-rchi
