《数据结构和C程序设计》由会员分享，可在线阅读，更多相关《数据结构和C程序设计（9页珍藏版）》请在金锄头文库上搜索。
1、本文格式为Word版，下载可任意编辑数据结构和C程序设计 数据布局 Part1 一选择 1. 组成数据的根本单位是（ ） A）数据项 B）数据类型 C）数据元素 D）数据变量 2算法分析的目的是（ ） A）找出数据布局的合理性 B）研究算法的输入/输出关系 C）分析算法的效率以求提升 D）分析算法的易读性 3在一个具有n个结点的有序单链表中插入一个新结点并依旧有序的时间繁杂度是（ ） A）O(1) B）0(n) C）O(n2) D）O(nlog2n) 4若线性表采用依次存储布局，每个元素占用4个存储单元，第一个元素的存储地址为100，那么第12个元素的存储地址是（ ） A）112 B）144
2、C）148 D）412 5下面关于线性表的表达中，错误的是（ ） A） 依次表使用一维数组实现的线性表 B） 依次表务必占用一片连续的存储单元. C） 依次表的空间利用率高于链表 D） 在单链表中,每个结点只有一个链域. 6在需要经常查找结点的前驱与后继的处境下，使用（ ）对比适合 A） 单链表 B）双链表 C） 依次表 D）循环链表 7队列通常采用的两种存储布局是（ ） A） 依次存储布局和链式存储布局 B）散列方式和索引方式 C） 链表存储布局和线性存储布局 D）线性存储布局和非线性存储布局 8在一个单链表中，若删除p所指结点的后继结点，那么执行（ ） A）p-next=p-next-ne
3、xt； B）p=p-next；p-nex=p-next-next； C）p-next=p-next； D）p=p-next-next； 9若某线性表中最常用的操作是在结果一个元素之后插入一个元素和删除第一个元素，那么采用（ ）存储方式最节省运算时间 A）单链表 B）仅有头指针的单循环链表 C）双链表 D）仅有尾指针的单循环链表 10按二叉树的定义，具有三个结点的二元树共有（ ）种形态。 A）3 B）4 C）5 D）6 11任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ） A）发生变更 B）不发生变更 C）不能确定 D）以上都不对 12深度为5的二叉树至多有（ ）个结点 A）1
4、6 B）32 C）31 D）10 13在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（ ）个。 A）4 B）5 C）6 D）7 14对于一个具有n个顶点的无向图，若采用邻接表表示，那么存放表头结点的数组(顶点表)的大小为（ ） A）n B）n+1 C）n-1 D）n/2 15静态查找表和动态查找表二者的根本区别在于（ ） A）它们的规律布局不同 B）施加在其上的操作不同 C）所包含的数据元素的类型不一样 D）存储实现不一样 二填空 2 1某程序的时间繁杂性为(3n+nlog2n+n+8),其数量级表示为_。 2线性表L=(a1,a2,
5、an)采用依次布局存储,假定在不同的位置上插入的概率一致，那么插入一个新元素平均需要移动的元素个数是_ 。 3. 对于一株具有n个结点的树，该树中全体结点的度数之和为_。 4. 在一个图中,全体顶点的度数之和等于全体边数的_倍。 5. 一棵二叉树有67个结点,这些结点的度要么是0，要么是2。这棵二元树中度数为2的结点有_个。 6在一个无向图的邻接表中，若表结点的个数是m，那么图中边的条数是_。 7采用堆排序、快速排序、冒泡排序，对初态有序的表，最省时间的是_ 。 8设二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG,那么二元树中叶结点是_. 9一个哈夫曼(Huffman)树有
6、19个结点，那么其叶结点的个数是_。 10.栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过S栈，一个元素出栈后即进入队列Q，若6个元素出队列的依次是a3,a5,a4,a6,a2,a1，那么栈S至少理应容纳_ 个元素。 三判断 1线性表的链式存储布局优于依次行储布局。（ ） 2在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储布局。（ ） 3 对于n个记录的集合举行归并排序，存最坏的处境下所需要的时间是O(n2)。（ ） 4 表中的每一个元素都有一个前驱和后继元素。（ ） 5 进栈操作push(x，s)作用于链接栈时，无须判满。（ ）
7、 6 只有在初始数据为逆序时，冒泡排序所执行的对比次数最多。 （ ） 7 在索引依次表查找方法中，对索引依次表可以使用依次表查找方法，也可以使用二分查找方法。（ ） 8 数据元素是数据的最小单位。（ ） 9 依次存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 10 按中序遍历一棵二叉排序树所得到的中序遍历序列是一个递增序列。（ ） 四简答 1. 对于下图所示的树： (1) 写出先序遍历得到的结点序列；(2) 画出转换后得到的二叉树。 2请画出与以下二元树对应的森林。 五算法设计 1已知一个int类型的数组arra，其长度为n，要求用冒泡排序算法对其从小到大排序，请实现该算法，（要求
8、后面开头循环，大的数值下沉）。 2利用一个栈实现以下递归函数的非递归计算： 1n?0?2xn?1 Pn(x)=?2xP(x)?2(n?1)P(x)n?1n?1n?2? Part2 一、单项选择 1、 在数据布局的议论中把数据布局从规律上分为（ ） A）内部布局与外部布局 B）静态布局与动态布局 C）线性布局与非线性布局 D）紧凑布局与非紧凑布局。 2、算法分析的目的是（ ） A）找出数据布局的合理性 B）研究算法中输入和输出的关系 C）分析算法的效率以求提升 D）分析算法的易懂性和文档性 3、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，那么执行（ ） A）slink
9、= plink; plink = s; B）plink = s; slink = q; C）plink = slink; slink = p; D）qlink = s; slink = p; 4、假设想在4092个数据中只需要选择其中最小的5个，采用（ ）方法最好。 A）起泡排序 B）堆排序 C）锦标赛排序 D）快速排序 5、设有两个串t和p，求p在t中首次展现的位置的运算叫做（ ）。 A）求子串 B）模式匹配 C）串替换 D）串连接 6、将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。 A）栈 B）队列 C）循环队列 D）优先队列 7、在循环队列中用数组A0.m-1 存放队列元素，
10、其队头和队尾指针分别为front和rear，那么当前队列中的元素个数是（ ）。 A）( front - rear + 1) % m B）( rear - front + 1) % m C）( front - rear + m) % m D）( rear - front + m) % m 8、下面程序段的时间繁杂度为（ ） for (int i=0;ilink=p;p-link=s; B）s-link=p-link;p-link=s; C）s-link=p-link;p=s; D）p-link=s;s-link=p; 10、当利用大小为n 的数组依次存储一个队列时，该队列的最大长度为（ ） A）
11、n-2 B）n-1 C）n D）n+1 11、某二叉树的前序和后序序列正好相反，那么该二叉树确定是（ ）的二叉树。 A）空或只有一个结点 B）高度等于其结点数 C）任一结点无左孩子 D）任一结点无右孩子 12、对于任何一棵二叉树T，假设其终端结点数为n0，度为2的结点为n2，那么( ) A）n0= n2+1 B）n2= n0+1 C）n0= 2n2+1 D）n2=2n0+1 13、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ） A）24 B）73 C）48 D）53 14、对线性表举行折半探寻时，要求线性表务必（ ） A）以链接方式存储且结点按关键码有序
12、排列 B）以数组方式存储 C）以数组方式存储且结点按关键码有序排列 D）以链接方式存储 15、依次探寻算法适合于存储布局为（ ）的线性表。 A）散列存储 B）依次存储或链接存储 C）压缩存储 D）索引存储 二、填空 1、数据的存储布局被分为 、 、 、 四种。 2、一种抽象数据类型包括 和 两个片面。 3、栈、队列规律上都是 布局。 4、栈中存取数据的原那么 ，队列中存取数据的原那么 。 5、设目标串T=”abccdcdccbaa”,模式P=”cdcc”那么第 次匹配告成。 三、判断 1、 数据的规律布局是指各数据元素之间的规律关系，是用户按使用需要建立的。( ) 2、 线性表的规律依次与物理依次总是一致的。（ ） 3、 每种数据布局都应具备三种根本运算：插入、删除、探寻。（ ）
