《数据结构》Part1一．选择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）4125．下面关于线性表的叙述中，错误的是（）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）611．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）A）发生改变B）不发生改变C）不能确定D）以上都不对12．深度为5的二叉树至多有（）个结点A）16 B）32 C）31 D）1013．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）个。
A）4 B）5 C）6 D）714．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为（）A）n B）n+1 C）n-1 D）n/215．静态查找表和动态查找表二者的根本差别在于（）A）它们的逻辑结构不同B）施加在其上的操作不同C）所包含的数据元素的类型不一样D）存储实现不一样二．填空1．某程序的时间复杂性为(3n+nlog2n+n2+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) 画出转换后得到的二叉树。
2．请画出与下列二元树对应的森林。
五．算法设计1．已知一个int类型的数组arra，其长度为n，要求用冒泡排序算法对其从小到大排序，请实现该算法，（要求后面开始循环，大的数值下沉）。
2．利用一个栈实现以下递归函数的非递归计算：Pn (x)=⎪⎩⎪⎨⎧>==----11)()1(2)(22121nnnxPnxxPxnnPart2一、单项选择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→link = s→link; s→link = p; D）q→link = s; s→link = p;4、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。
A）起泡排序B）堆排序C）锦标赛排序D）快速排序5、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。
A）求子串B）模式匹配C）串替换D）串连接6、将一个递归算法改为对应的非递归算法时，通常需要使用（）。
A）栈B）队列C）循环队列D）优先队列7、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。
A）( front - rear + 1) % m B）( rear - front + 1) % mC）( front - rear + m) % m D）( rear - front + m) % m8、下面程序段的时间复杂度为（）for (int i=0;i<m;i++)for (int j=0;j<n;j++)a[i][j]=i*j;A）O(m2) B）O(n2) C）O(m*n) D）O(m+n)9、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( )。
A）s->link=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）n-2 B）n-1 C）n D）n+111、某二叉树的前序和后序序列正好相反，则该二叉树一定是（）的二叉树。
A）空或只有一个结点B）高度等于其结点数C）任一结点无左孩子D）任一结点无右孩子12、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2，则( )A）n0= n2+1 B）n2= n0+1 C）n0= 2n2+1 D）n2=2n0+113、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A）24 B）73 C）48 D）5314、对线性表进行折半搜索时，要求线性表必须（）A）以链接方式存储且结点按关键码有序排列B）以数组方式存储C）以数组方式存储且结点按关键码有序排列D）以链接方式存储15、顺序搜索算法适合于存储结构为（）的线性表。
A）散列存储B）顺序存储或链接存储C）压缩存储D）索引存储二、填空1、数据的存储结构被分为、、、四种。
2、一种抽象数据类型包括和两个部分。
3、栈、队列逻辑上都是结构。
4、栈中存取数据的原则，队列中存取数据的原则。
5、设目标串T=”abccdcdccbaa”,模式P=”cdcc”则第次匹配成功。
三、判断1、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。
( )2、线性表的逻辑顺序与物理顺序总是一致的。
（）3、每种数据结构都应具备三种基本运算：插入、删除、搜索。
（）4、深度为h的非空二叉树的第h层最多有2h-1个结点。
（）5、完全二叉树就是满二叉树。
（）6、最优二叉搜索树一定是平衡的二叉搜索树。
（）7、线性表中所有结点的类型必须相同。
（）8、连通分量是无向图中的极小连通子图。
（）9、空串与由空格组成的串没有区别。
（）10、带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。
（）四、简答1、在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？2、将下面的森林变换成二叉树。
3、有图如下，请画出其邻接多重表。
五．算法设计1、编写算法实现链表的创建、遍历、销毁。
2、编写算法，实现快速排序。
Part3一．选择1、在数据结构的讨论中把数据结构从逻辑上分为（）A）内部结构与外部结构 B）静态结构与动态结构C）线性结构与非线性结构 D）紧凑结构与非紧凑结构。
2、下面程序段的时间复杂度为（）for (int i=0;i<m;i++)for (int j=0;j<n;j++)a[i][j]=i*j;A）O(m2) B）O(n2) C）O(m*n) D）O(m+n)3、采用线性链表表示一个向量时，要求占用的存储空间地址（）A）必须是连续的 B）部分地址必须是连续的C）一定是不连续的 D）可连续可不连续4、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I 个结点的地址为（）。
A）da1+(I-1)*m B）da1+I*m C）da1-I*m D）da1+(I+1)*m5．下面关于线性表的叙述中，错误的是（）A）顺序表使用一维数组实现的线性表B）顺序表必须占用一片连续的存储单元C）顺序表的空间利用率高于链表D）在单链表中,每个结点只有一个链域6、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）A)s→link = p→link; p→link = s; B)p→link = s; s→link = q;C)p→link = s→link; s→link = p; D)q→link = s; s→link = p;7、设循环队列的结构如下：const int Maxsize=100;typedef int Data Type;typedef struct {Data Type data[Maxsize];Int front, rear;} Queue;若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句（）A)Q.front = = Q.rear; B)Q.front - Q.rear= = Maxsize;C)Q.front + Q.rear = = Maxsize; D)Q.front= = (Q.rear+1)% Maxsize;8、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。