数字结构数据结构题目

1、数据结构题目(手打整理版)鸣谢、同学的拍摄一、选择题（10*2=20 分）1. 在一个长度为 n 的顺序表中顺序搜素一个值为 x 的元素时，在等概率的情况下，搜索成功的数据平均比较次数为_ C 。等差数列求和：（1+2+3+。+n）/2n=(n+1)/2A、nB、n/2C、(n+1)/2D、(n-1)/2间的B关系。2. 树型结构对应的是数据元：书上 146.。可以复习链式和树和图各个之间的元素关系。A、一一对应B、一对多C、多对多D、离散3. 设有一个二维数组 A1020，按行存放与续的空间中，A00的地址是200，每个数组元素占2 个字，则A62的地址为_ D 。10代 表 有 十 行 ，

2、 20代 表 每 行 有20个元 素 ， 所 以A62=(6*20+2)*2+200=444.因为数组是从 A【0】【0】开始，所以前面应该是有六行。（特别注意）A、226B、322C、341D、4444. 非空的循环单链表的尾结点（由 p 所指向）满足_D。因为要循环，所以尾节点必须要指向头结点。应该是这样，如果有什么疑问，再去看看书上关于循环链表的程序，看看是怎么回事，书上的东西是标准，重视。可能这道题目打错了，NULL 不该有那么多。A、p-next=NULL B、p=NULL C、p-next=NULL D、p=5. 设有一个广义表 A(x，(a，b)，(x，(a，b)，y)，运算 H

3、ead(Head(A)的执行结果为 A。书上 126 页关于广义表的定义，重点复习 5.3.1.。理解！重点！A、xB、(a，b)C、(x，(a，b)D、A6. 在一棵具有 n 个结点的二叉树，二叉链表中的空指针域个数等于 C。自己可以画一棵简单的二叉树，看看规律。符合一般性就好了。如果问题，看看关于二叉树的空指针到底是怎么回事，书上 161 页图 7.9A、nB、n-1C、n+1D、2*n7. 在一棵完全二叉树中，若为 i 的结点存在左孩子，则左孩子为_A _。同理，也可以花一颗很简单的完全二叉树，结点的自己看出来。A、2iB、2i-1C、2i+1D、2i+28.通图的生成树是包含图中所有顶

4、点的一个C子图。书上 210 页生成树和最小生成树的概念。A、极小B、连通C、极小连通D、无环9.对 5 个不同的数据元素进行直接排序，最多需要进行次比较。（B）了解直接排序的含义。书上 276 页有两个公式，好好看看。A、8B、10C、15D、2510. 设散列地址空间为 0m-1，k 为表项的关键码，散列函数采用除留余数法，即 Hash(k)=k%p。为了减少发生的频率，一般取 p 为 B。书上 264 页，除留余数法。A、mB、小于等于 m 的最大质数C、大于 m 的最小质数D、小于等于 m 的最大合数二、填空题（6*1=6 分）1. 对于长度为 18 的有序顺序表，若采用折半搜索，啧搜

5、索第 15 个元素的搜索次数为_4。书上 238 页，看看二分查找的程序和概念，这很重要！再看看例题 9.1、注意，结合程序和例题看，自己动手做做到底是怎么回事，这个程序一定要背下来，重点！2. 在一棵树中，根结束没有前驱结点，_叶子结点没有后继结点。3. 从一个顺序结构的循环队列中增加一个元素时，需要队列长度加一。这个我是自己写的，不一定对，你别人的、4. 已知二叉树有 16 个叶子结点， 该二叉树总结点数至少有1+2+2*2+2*2*2+2*2*2*2_个。（这其实就是一个满二叉树）5.一棵树德广义表表示为 a(b(c,d(e,f),g(h),i(j,k(x,y)，结点k 的所有先祖的结点

6、数为2个重点！。书上 126 页关于广义表的定义，重点复习 5.3.1.。理解！重点！最好能结合画出他的树的样子。三、（6 分）给出一组关键字 T=（35,67,18,29,53,44,9,21）要求从小到大进行排序，试给出快速排序。（选第一个为枢轴）重点体会 283 页的快速排序的过程，只要满足左边小，右边大就好！四、（6 分）已知一组关键字为4，9,1,0,8,6,3,5,2,7，按表中的元素顺序依次到一颗初始为空的二叉排序树中，画出该二叉排序树，并求在等概率情况下查找成功的平均查找长度。书上 245 页，例题 9.1、好好看看。了解二分查找的过程，会画这棵二叉查找树。重点！看看二分查找的

7、程序，在 238 页，变化图边看程序，程序是指导。这个程序是重点。最好能背下来！初始排列3567第 1 趟排序结果5344第 2 趟排序结果918292135534467918212935446753五、（8 分）已知一颗二叉树的静态数组表示（即顺序表示）如下，其中#表示空指针，请画出该二叉树，并分别写出该二叉树的前序、中序和后序遍历的序列。0123456789101112前序序列： ABDEGHCFH中序序列：DBGEHAFLC后序序列：_DGHEBLFCA_ABCDEFHGL书上 165 页。看看二叉树遍历的定义、重点。再仔细看看做做这道题。重点！ABCDEF#GH#L六、（8 分）假定无

8、向图 G 有 6 个顶点0,1,2,3,4,5，9 条边依次为0，1，0,2，0,4，1,2，2,3，2,4，3,4，4,5。（1）请画出该无向图；（2）建立图 G 的邻接表；（注意：邻接顶点按升序）（3）根据邻接表，写出总顶点 3 出发，按深度优先搜索法进行遍历的结点序列。（3）邻接表好好看看书上 202 图 8.6，再自己做做题目。七、八、应用 Prim（姆）算法求解连通图的最小生成树。要求按如下格式在构造最小生成树过程中顺序选出的各条边，并画出最小生成204315321450树。0612345012345其实这个和离散差不多。结合知识去做吧。好好看看书吧。始顶点号终顶点号权值22九、算法

9、设计题（4 小题，共 34 分）1.（10 分）设计算法，对包含 n 个的数组 R0,n-1实现递增有序的直接选择排序，数据类型和函数参考如下。typedef char InfoType10;typedef struct/*类型*/key;/*关键字项*/Info Typedata;/*其他数据项，类型为 InfoType*/Rectype;void SelectSort(RecType R,n)/*对 R0,n-1按递增有序进行直接选择排序*/程序：286 页，看看程序和过程。其实就是以前学习的选择法。最好你会写这个程序。！重点啊。2.（8 分）设计算法，在有序表 R0,n-1中进行二分查找

10、法查找关键字为 k 的。成功时返回的位置，失败时返回-1。数据类型和函数如下。typedef structKeyType key;/*KeyType 为关键字的数据类型*/InfoType data;/*其他数据*/NodeType;Typedef NodeType SeqListMAXL;/*顺序表类型*/BanSearch (SeqList R,n,KeyType k)程序：书上 238 页.。重点！最好能记下来。这个很重要！3.（8 分）设计函数 F 的算法判断已知字符串是否为回文串，例如：字符串“abcde”经过 F 处理后，返回-1，字符串“abcba”经过 F 处理后，返回 1.（

11、字符串的数据结构自定）/文件名：exp1-3.cpp#include #include #define MAX 100/字符串的最大长度func(char s)flag=1;i,j,slen=strlen(s);/slen 为字符串 s 的长度for (i=0,j=slen-1;ilchild=NULL&b-rchild=NULL)n=n+1;LeafNpdes(b-lchild);LeafNpdes(b-rchild);最后在给你提及个意见:去复习下以下内容，可能会出现在天空选择，判断题里面。1. 逻辑结构类型。书上 5 页2.结构类型。书上 7 页3.算法：书上 11 页4. 算法设计的目标：书上 14 页、5. 栈的定义。“先进后出”，一定要理解。比如：asdfgh 近栈，出栈的顺序应该是 hgfdsa去看看书上的题目，60 页的例题3.1 和 3.26. 还有队列，：“先进先出”比如 asdfhg 进入队列，出来的时候也是按照 asdfhg7. 重点是二叉树和查找以及排序。二分查找一定要背下来。排序的几种排序一定要搞清楚它属于哪一类，不能，多去看看，试着背几个程序。8.排序：直接排序，二分排序，排序，重点看看直接排序的过程。注意排序的