搜索
重庆理工大学考试试卷一、单项选择题（每题1分，共10分）1、对线性表进行折半查找最方便的存储结构是（）。A、顺序表B、有序的顺序表C、链表D、有序的链表2.将一棵有200个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为39的结点的左孩子编号为（）。A．78B.79C.80D.483.设数组A[0..M]作为循环队列SQ的存储空间，front为队头指针，rear为对尾指针，则执行出队操作的语句为（）。A．front=front+1B．front=(front+1)%mC．rear=rear+1D．rear=(rear+1)%m4．一个具有n个顶点的无向完全图的边数为（）。A．n(n+1)/2B．n(n-1)/2C．n(n-1)D．n(n+1)5．下面（）方法可以判断出一个有向图中是否有环（回路）？A.深度优先遍历B.拓朴排序C.求最短路径D.求关键路径6、深度为5的二叉树其结点数最多为（）。A．16B．30C．31D．327．设计一个判别表达式中左右括号是否配对出现的算法，采用（）数据结构最佳。A．线性表的顺序存储结构B．栈C．队列D．线性表的链式存储结构8．对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为（）的结点开始。A.100B.12C.60D.159.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（）A.1，3，2，4B.2，3，4，1C.4，3，1，2D.3，4，2，110．带权有向图用邻接矩阵A存储，则顶点I的入度等于A中（）。A．第I行非∞的元素之和B．第I列非∞的元素之和C．第I行非∞且非0的元素个数D．第I列非∞且非0的元素个数二、判断题（正确打√，错误打×；每空1分，共10分）1．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上一定相邻。（）2．空格串不是空串。（）3．在含n个结点的无向连通图对应的生成树中，有且仅含n条边。（）4．在树的孩子兄弟表示法中，其根结点的右子树总是为空。（）5.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。（）6．作进栈运算时，应先判别栈是否为空（）7．二叉排序树的查找和折半查找的时间复杂性相同。（）8.赫夫曼树是带权路径长度最短的树，含n个叶子结点的赫夫曼树共有2n-1个结点。（）9.设一个栈的输入序列为a，b，c，d，则借助一个栈所得的输出序列不可能是a，c，d，b.（）10.深度为7的二叉树至多有127个结点.（）三.填空题（每空1分，共10分）1.线索二叉树中，当某结点p的rtag=0时，rchild指向p的，rtag=1时，rchild指向p的。2.在不带头结点的单链表L中，指向第一个元素结点的指针是__________；在带头结点的循环单链表L中，链表为空（仅含头结点）的判定条件是。3.设广义表C=（（b，c，d），e），则C的表头是。4.具有201个结点的完全二叉树的深度为。5.数据结构的形式定义为(K，R)，其中K是的有限集，R是K上的有限集。6.二叉树的第i层上至多有个结点。7.设n行n列的下三角矩阵A已压缩到一维数组S[1..n*(n+1)/2]中（以行序为主存储，且A[0][0]=1），则A[i][j]对应在S中的存储位置是。四、解答题（每题5分，共30分）1．计算下列程序段的时间复杂度。s=0；for(i=0；im；i++)for(j=0；jn；j++)s+=B[i][j]；2.设有一序列28,17,2,60,12,51，请按该序列构成一棵二叉排序树，并求其查找成功时的平均查找长度。3．设给定权集W={1，2，4，5，6}，试构造关于W的一棵赫夫曼树，并求其加权路径长度WPL。4.已知序列{71，84，99，64}，请分别给出采用直接插入排序、冒泡排序、快速排序、简单选择排序、二路归并排序算法，对该序列作升序排列时的第一趟的结果。5.设图G=（V，E），V={1，2，3，4，5，6}，E={1，2，1，3，2，5，3，6，6，5，5，4}，请写出图G的拓扑序列（在同等情况下，按顶点序号较小值为优先）。6.设图G=（V，E），V={v1，v2，v3，v4，v5}，E={v1，v3，v2，v5，v5，v4，v2，v3，v1，v2}，请画出其邻接表,然后根据邻接表找出其深度优先遍历序列。五、算法填空（每空2分，共10分）1.二叉树中序遍历递归算法。#include“stdio.h”#include“malloc.h”structnode{chardata；structnode*lchild,*rchild；}bnode；typedefstructnode*blink；voidinorder(blinkbt){if(bt){inorder(bt-)；printf（“%c”,bt-data）；inorder(bt-)；}}2.快速排序算法#defindm100typedefstruct{intkey；intno；}rectype；typedefrectypeseqlist[m]；seqlistr；intpartition(seqlistr,inti,intj){rectypepivot=r[i]；while(ij){while(ij&&r[j].key=pivot.key)；if(ij)r[i++]=r[j]；while(ij&&r[i].key=pivot.key)；if(ij)r[j--]=r[i]；}；returni；}六、算法设计与分析（每小题10分，共30分）1、设n个十进制整数已存入数组A[n]中,请利用栈技术,用C语言函数形式写出将A[n]中各数据转换成八进制数并存入数组B[n]的算法:Convert(intA[],intB[],intn)。（注：算法中可调用栈操作的基本函数）2、设二叉树采用链式结构存储，根结点指针为bt，结点的左右孩子指针分别为lchild和rchild，请采用按层次遍历二叉树的方法，用C语言函数形式写出将二叉树bt中每一结点的左右孩子指针相互交换的算法：exchange(structnode*bt)。（注：算法中可调用队列操作的基本函数）3、对n个元素所构成的序列r[1..n]，元素类型定义如下：typedefstruct{intkey；intno；}rectype；试用C语言设计下列算法：（1）对序列r[i..j]进行一趟快速排序intpartition(rectyper[],inti,intj)，返回枢轴记录所在位置。（2）利用（1）中算法，完成快速排序算法voidquicksort(rectyper[],intlow,inthigh)即对r[low..high]进行快速排序，结果通过r返回。