数据结构和C程序设计题库完整

word 完美格式 《数据结构》《数据结构》 Part1Part1 一一．选择．选择 1. 组成数据的基本单位是（） A）数据项 B）数据类型 C）数据元素 D）数据变量 2．算法分析的目的是（） A）找出数据结构的合理性 B）研究算法的输入/输出关系 C）分析算法的效率以求改进 D）分析算法的易读性 3．在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（） A）O(1) B）0(n) C）O(n^2) D）O(nlog2n) 4． 若线性表采用顺序存储结构， 每个元素占用 4 个存储单元， 第一个元素的存储地址为100， 则第 12 个元素的存储地址是（） A）112 B）144 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-next ；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）16 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 精心整理学习帮手 word 完美格式 15．静态查找表和动态查找表二者的根本差别在于（） A）它们的逻辑结构不同 B）施加在其上的操作不同 C）所包含的数据元素的类型不一样 D）存储实现不一样 二．填空二．填空 2 1．某程序的时间复杂性为(3n+nlog2n+n +8),其数量级表示为________。 2．线性表L=(a1,a2,…,an)采用顺序结构存储,假定在不同的位置上插入的概率相同，则插 入一个新元素平均需要移动的元素个数是_________ 。 3. 对于一株具有 n 个结点的树，该树中所有结点的度数之和为______。 4. 在一个图中,所有顶点的度数之和等于所有边数的______________倍。 5. 一棵二叉树有 67 个结点,这些结点的度要么是0， 要么是 2。 这棵二元树中度数为2 的结 点有______________个。 6．在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是_____。 7．采用堆排序、快速排序、冒泡排序，对初态有序的表，最省时间的是______ 。 8．设二叉树结点的先根序列为ABDECFGH，中根序列为 DEBAFCHG,则二元树中叶结点是 _________. 9．一个哈夫曼(Huffman)树有 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(n^2)。 （） 4． 表中的每一个元素都有一个前驱和后继元素。 （） 5． 进栈操作 push(x，s)作用于链接栈时，无须判满。 （） 6． 只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。 （） 7． 在索引顺序表查找方法中， 对索引顺序表可以使用顺序表查找方法， 也可以使用二分查 找方法。 （） 8． 数据元素是数据的最小单位。 （） 9． 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （） 10． 按中序遍历一棵二叉排序树所得到的中序遍历序列是一个递增序列。 （） 四．简答四．简答 1. 对于下图所示的树： (1) 写出先序遍历得到的结点序列；(2) 画出转换后得到的二叉树。 精心整理学习帮手 word 完美格式 2．请画出与下列二元树对应的森林。 五．算法设计五．算法设计 1．已知一个 int 类型的数组 arra，其长度为 n，要求用冒泡排序算法对其从小到大排序， 请实现该算法， （要求后面开始循环，大的数值下沉） 。 2．利用一个栈实现以下递归函数的非递归计算： 1 1n n   0 0    2 2x xn n   1 1 P n (x)=   2 2xP xP( (x x) )   2 2( (n n  1 1) )P P( (x x) )n n   1 1 n n 1 1n n 2 2   精心整理学习帮手 word 完美格式 Part2Part2 一一、、单单项项选选择择 1、 在数据结构的讨论中把数据结构从逻辑上分为（） A）内部结构与外部结构 B）静态结构与动态结构 C）线性结构与非线性结构 D）紧凑结构与非紧凑结构。 2、算法分析的目的是（） A）找出数据结构的合理性 B）研究算法中输入和输出的关系 C）分析算法的效率以求改进 D）分析算法的易懂性和文档性 3、在一个单链表中，若 q 结点是 p 结点的前驱结点，若在 q 与 p 之间插入结点 s，则执行 （） A）s→link = p→link; p→link = s; B）p→link = s; s→link = q; C）p→l