搜索
数据结构试题一一、单项选择题（每小题3分，共30分）1、在有n个叶子结点的哈夫曼树中，其结点总数为（）。A、不确定B、2nC、2n+1D、2n-12、下列序列中，（）是执行第一趟快速排序得到的序列（排序的关键字类型是字符串）。A、[da，ax，eb，de，bb]ff[ha，gc]B、[cd，eb，ax，da]ff[ha，gc，bb]C、[gc，ax，eb，cd，bb]ff[da，ha]D、[ax，bb，cd，da]ff[eb，gc，ha]3、若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（）存储方式节省时间。A、单链表B、双链表C、单循环链表D、顺序表4、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是（）。A、堆排序B、冒泡排序C、直接选择排序D、快序排序5、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A、空或只有一个结点B、高度等于其结点数C、任意结点无左孩子D、任意结点无右孩子6、下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（）。A、堆排序B、冒泡排序C、直接选择排序D、快序排序7、快速排序算法在最好情况下的时间复杂度为（）。A、O(n)B、O(n2)C、O(nlogn)D、O(logn)8、已知数据表A中每个元素距其最终位置不远，则采用（）排序算法最省时间。A、堆排序B、插入排序C、直接选择排序D、快序排序9、带权有向图G用邻接矩阵A存储，则顶点i的入度为A中（）。A、第i行非∞的元素之和B、第i列非∞的元素之和C、第i行非∞且非0的元素之和D、第i列非∞且非0的元素之和10、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。A、O(n)B、O(n2)C、O(nlogn)D、O(logn)二、判断题（认为对的在题后的括号内打“√”，错的打“ⅹ”，每小题１分，共10分）1.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问该图的每个顶点。()2.在索引顺序表上实现分快查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。()3、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。()4、图G的最小生成树的代价一定小于其他生成树的代价。()5、已知一棵树的先序序列和后序序列，一定能构造出该树。()6、对一个堆按层次遍历，不一定能得到一个有序序列。()7、设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。()8、不管ADT栈是用数组实现，还是用链表的指针实现，POP(S)与Push(x,S)的耗时均为O(n)。()9、如果删除二叉排序树中一个结点，再按照二叉排序树的构造原则重新插入上去，一定能得到原来的二叉排序树。()10、快速排序是排序算法中最快的一种。()三、填空题（每小题2分，共20分）1、在双向循环表中，在p所指的结点之后插入指针f所指的结点，其操作为：_________=p;f→next=p→next;_____=f;p→next=f。2、在有序表A[1…20]中，采用二分查找算法查找元素值等于A[12]的元素，所比较过的元素的下标依次为__________。3、若某串的长度小于一个常数，则采用_________存储方式最节省空间。4、在有n个顶点的有向图中，每个顶点的度最大可达_________。5、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为__________。6、设键值序列为{K1，K2，…，Kn},用筛选法建堆则必须从第_______个元素开始筛选。7、在二叉链表中判断某指针p所指结点为叶子结点的条件是_________。8、直接选择排序算法在最好情况下所作的交换元素的次数为________。9、有n个球队参加的足球联赛按主客场制进行比赛，共需进行_______比赛。10、下列排序算法中，占用辅助空间最多的是_________(堆排序，希尔排序，快速排序，归并排序)。四、简答题（每题10分，共60分）1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？2、设有一组关键字（17，13，14，153，29，35）需插入到表长为12的散列表中，请回答以下问题：（1）设计一个适合该散列表的散列函数。（2）用设计的散列函数将上述关键字插入到散列表中，并用线性探测法解决冲突，画出其结构；并指出用线性探测法解决冲突时构造散列表的装填因子为多少？3、对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问（1）图中有多少条边？（2）任意两个顶点i和j是否有边相连？（3）任意一个顶点的度是多少？4、已知下面二叉排序树的各结点的值依次为1…9，请标出各结点的值。5、具有3个结点的树和具有3个结点的二叉树,它们的所有不同形态有哪些？6、分析以下程序段中语句x=x+y的执行次数。x=0;y=0;for(inti=1;i=n;i++)for(intj=1;j=i;j++)for(intk=1;k=j;k++)x=x+y;五、算法设计题（每题15分，共30分）说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。1、假设以二叉链表作为二叉树存储结构，其类型定义如下：typedefstructnode{chardata;structnode*lchild,*rchild;//左右孩子指针}BinTNode,*BinTree;写一函数，完成以下功能：对二叉树中每个结点，如果其左孩子为空（右孩子不为空），则将其右孩子设置为左孩子。2、试设计将数组A[0…n-1]中所有奇数移到所有偶数之前的算法。要求不另增加存储空间且时间复杂度为O(n)。数据结构试题1参考答案一、1——5：DADAB6——10：CCBDD二、1——5：ⅹ√ⅹⅹ√6——10：√ⅹⅹⅹⅹ三、1、①f→prior，②p→next→prior2、1015123、顺序压缩4、2(n-1)5、1296、n/2的最小整数7、(p→lchild==NULL)&&(p→rchild==NULL)8、09、n(n-1)10、归并排序四、1、答案：在单链表中不能删除，而在双链表和单循环链表中可以删除p结点。双链表的删除时间复杂度为O(1)，单循环链表删除p结点的时间复杂度为O(n)。2、答案：（1）由于散列表的长度为12，则可选不超过表长的最大素数11作为除留余数法的模，则可得其散列函数为h(k)=k%11。（2）若用线性探测法解决冲突，则可构造出散列表如下：131435172915301234567891011此时，其装填因子为6/12=1/2，若用链式法解决冲突，则其散列表为：3、答案：（1）无向图的邻接矩阵所有数值之和除以2，为边数。有向图邻接矩阵各行数值之和为总边数。邻接表表示无向图内部顶点个数除以2，有向图内部顶点个数。（2）无向图中I行和J列的交叉点的值是否为1。有向图I行J列交叉点或I列和J行交叉点的值为1。（3）无向图顶点的度为每一行的数值之和；有向图顶点度为该行和该列数值之和。4答案：5、答案：具有3个结点的树的形态为：三个结点的两种树形态，无左右之分。具有3个结点的二叉树的形态为：5种形态，有左右之分。6：答案：五、1、答案：voidexchange(BinTreeT){if(T){if(!T→lchild&&T→rchild){T→lchild=T→rchild;T→rchild=NULL;}exchange(T→lchild);exchange(T→rchild);}}2、答案：intoddbefore(A,n)//将数组A[0…n-1]中所有奇数移到所有偶数之前intA[];{intc,i,j;i=0;j=n-1;//初始化i、jwhile(ij){while((A[i]%2==1)&&(ij))//A[i]为奇数时，i向右扫描i++;while((A[i]%2==0)&&(ij))//A[i]为偶数时，j向右扫描j--;if(ij)//A[i]与A[j]进行交换，i向右、j向左扫描；{c=A[i];A[i]=A[j];A[j]=c;i++;j--;}}return(1)}//oddbefore数据结构试题2一、单项选择题（每小题3分，共30分）1、下列排序算法中，（）排序在每趟结束后，不一定能选出一个元素放到其排好序的最终位置上。A、选择B、冒泡C、归并D、堆2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A、单链表B、仅有头指针的单循环链表C、双链表D、仅有尾指针的单循环链表3、串的长度是（）。A、串中不同字符的个数B、串中不同字母的个数C、串中所含字符的个数且字符个数大于0D、串中所含字符的个数4、有一个散列表，表长度m为100，采用除余法构造散列函数，即H(k)=k%P,(P小于等于m)，为使散列函数有较好的性能，P的选择应是（）。A、99B、97C、91D、935、在包括n个键值的二叉排序树中查找一个键值，其平均比较的量级为（）。A、O(n)B、O(logn)C、O(nlogn)D、O(n)6、对有14个元素的有序表A[1…14]作二分查找，查找A[4]时的被比较元素依次为（）。A、A[1]，A[2]，A[3]，A[4]B、A[1]，A[14]，A[7]，A[4]C、A[7]，A[3]，A[5]，A[4]D、A[7]，A[5]，A[3]，A[4]7、具有65个结点的完全二叉树其深度为（）。A、8B、7C、6D、58、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）。A、第i行非无穷元素之和B、第i列非无穷元素之和C、第i行非零且非无穷元素个数D、第i列非零且非无穷元素个数9、队列操作的原则是（）。A、先进先出B、后进先出C、只能进行插入D、只能进行删除10、若表R在排列前已按元素键值递增顺序排序，采用（）的比较次数少。A、直接插入排序B、快速排序C、归并排序D、选择排序二、判断题（认为对的，在题后的括号内打“√”，错的打“ⅹ”，每小题１分，共１０分）1、在栈空的情况下，不能做退栈运算，否则产生下溢。（）2、在快速排序算法中，取待排序的n个记录中的第一个的键值为基准，将所有记录分为两组，读记录就排在这两组的中间，这也是该记录的最终位置。（）3、在索引顺序表查找方法中，对索引顺序表可以使用顺序表查找方法，也可以使用二分查找方法。（）4、设有键值序列（k1，k2，…，kn），当in/2时，任何一个序列（k1，k2，…，kn）一定是堆。（）5、在向二叉排序树中插入一个新结点时，需要比较结点的次数可能大于此二叉树的高度h。（）6、在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。（）7、双循环链表中，任一结点的前驱指针均为不空。（）8、线性表采用链式存储方式和顺序存储方式，执行插入、删除运算的算法时间复杂度都是O(n),因而两种存储方式的插入、删除运算所花费的时间相同。（）9、如果有向图G=(V，E)的拓扑序列不唯一，则图中必有两条弧vi,vj和vj,vi存在。（）10、矩阵压缩存储的方法是用三元组表存储矩阵元素。（）三、填空题（每小题2分，共20分）1、设sq[1…maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置。作进栈操作时，必须判别____。如要把栈顶元素取到x中，需执行语句_____。2、设一个二叉树共有50个叶结点（终端结点），则共有_______个度为2的结点。3、在单链表中，若要在指针p所指结点(data，next)后插入指针s所指结点，则需要执行下列两条语句：s→next=p→next;_________。4、3个结点可构成_________棵不同形状的树。5、利用直接选择排序算法对n个记录进行排序，最坏情况下，记录交换的次数为_______6、如果含n个顶