五．算法设计
1、编写算法实现链表的创建、遍历、销毁。 2、编写算法，实现快速排序。
Part3
一．选择
1、 在数据结构的讨论中把数据结构从逻辑上分为 （ ） A）内部结构与外部结构 B）静态结构与动态结构 C）线性结构与非线性结构 D）紧凑结构与非紧凑结构。 2、下面程序段的时间复杂度为（ ） for (int i=0;i 2 B）O(n) 2 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)*m 5．下面关于线性表的叙述中，错误的是（ ） 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，则当前队列中的元素个数是（ ）。 A)( front - rear + 1) % m C)( front - rear + m) % m A)栈 B)( rear - front + 1) % m D)( rear - front + m) % m C)循环队列 D)优先队列 9、将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。 B)队列 10、下列广义表是线性表的有（ ） A)E（a,(b,c)） B)E(a,E) C)E(a,b) D)E(a,L( ) ) 11、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ ）。 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)以链接方式存储且结点按关键码有序排列 B)以数组方式存储 C)以数组方式存储且结点按关键码有序排列 D)以链接方式存储 15．静态查找表和动态查找表二者的根本差别在于（ ） A）它们的逻辑结构不同 B）施加在其上的操作不同 C）所包含的数据元素的类型不一样 D）存储实现不一样 二．判断 1、数据元素是数据的最小单位（ ）。 2、数据结构是指相互之间存在一种或多种关系的数据元素的全体（ ）。 3、线性表的逻辑顺序与物理顺序总是一致的（ ） 4、每种数据结构都应具备三种基本运算：插入、删除、搜索（ ）。 5、空串与由空格组成的串没有区别。（ ） 6、深度为h的非空二叉树的第h层最多有2h-1个结点（ ） 7、完全二叉树就是满二叉树。（ ） 8、最优二叉搜索树一定是平衡的二叉搜索树。（ ） 9、快速排序是对起泡排序的一种改进。( ) 10、B-树是一种动态索引结构，它既适用于随机搜索，也适用于顺序搜索。（ ） 三．简答 1、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ。 （1）试画出这棵二叉树； （2）给出这棵二叉树的后序遍历序列。 2、已知一颗树如下图所示，请用孩子兄弟存储表示法表示该树。 四．算法设计 已知一个int类型的数组arra，其长度为n，要求用冒泡排序算法对其从小到大排序，请实现该算法，（要求后面开始循环，大的数值下沉）。 Part4 一、单项选择 2、 在数据结构的讨论中把数据结构从逻辑上分为 （ ） A)内部结构与外部结构 B)静态结构与动态结构 C)线性结构与非线性结构 D)紧凑结构与非紧凑结构。 2、下面程序段的时间复杂度为（ ） int f(unsigned int n) { if(n= =0 || n= =1) return 1; else return n*f(n-1); } A)O(1) B)O(n) C)O(n) 2 D)O(n!) 3、一个数组元素a[i]与（ ）的表示等价。 A) *（a+i） B) a+i C) *a+i D) &a+i 4、若需要利用形参直接访问实参，则应把形参变量说明为（ ）参数。 A) 指针 B) 引用 C) 值 D) 变量 5、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ ）。 A) 80 B) 100 C) 240 D) 270 6、在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移( )个元素。 A) 1 - i B) n - i + 1 C) n – j - 1 D) i 7、设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q 与*p之间插入结点*s，则应执行下列哪一个操作（ ） A) s->link=p->link; p->link=s; B) q->link=s; s->link=p C) p->link=s->link; s->link=p; D) p->link=s; s->link=q; 8、设单循环链表中结点的结构为（data,link）,且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是( )。 A) current->link =null B) first->link=current C) first=current D) current->link=first 9、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( )。 A) c,b,a B) b,a,c C) c,a,b D) a,c,b 10、设链式栈中结点的结构为（data, link）,且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列（ ）操作。 A) x=top->data; top=top->link; C) x=top; top=top->link; B) top=top->link; x=top->data; D) x=top->data; 11、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r ,则判断队空的条件为( )。 A) f+1= =r B) r+1= =f C) f= =0 D) f= =r 12、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（ ） A) n-2 B) n-1 C) n D) n+1 13、某二叉树的前序和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A) 空或只有一个结点 B) 高度等于其结点数 C) 任一结点无左孩子 D) 任一结点无右孩子 14、顺序搜索算法适合于存储结构为（ ）的线性表。 A) 散列存储 C) 压缩存储 B) 顺序存储或链接存储 D) 索引存储 15、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ ）。 A) 求关键路径的方法 B) 求最短路径的Dijkstra方法 C) 深度优先遍历算法 二、判断 1、从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构（ ）。 2、每种数据结构都应具备三种基本运算：插入、删除、搜索（ ）。 3、非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。（ ） D) 广度优先遍历算法 4、将T在S中首次出现的位置作为T在S中的位置的操作称为串的模式匹配。（ ） 5、已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。（ ） 6、线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。（ ）7、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关（ ）。 8、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（ ） 9、连通分量是无向图中的极小连通子图。（ ） 10、快速排序是对起泡排序的一种改进。( ) 三、） 1、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码。 2、将下面的森林变换成二叉树。 四．算法设计 已知一个int类型的数组arra，其长度为n，要求用选择排序算法对其从小到大排序，请实现该算法。