东北大学16春学期《数据结构Ⅰ》在线作业参考答案

东北大学16春学期《数据结构Ⅰ》在线作业参考答案一、单选题：1.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为(满分:5)A.1和5B.2和4C.4和2D.5和12.为便于判别有向图中是否存在回路，可借助于(满分:5)A.广度优先搜索算法B.最小生成树算法C.最短路径算法D.拓扑排序算法3.连通网的最小生成树是其所有生成树中(满分:5)A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树4.上溢现象通常出现在(满分:5)A.顺序栈的入栈操作过程中B.顺序栈的出栈操作过程中C.链栈的入栈操作过程中D.链栈的出栈操作过程中5.ALV树是一种平衡的二叉排序树，树中任一结点的(满分:5)A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度6.ISAM文件的周期性整理是为了空出(满分:5)A.磁道索引B.柱面索引C.柱面基本区D.柱面溢出区7.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到(满分:5)A.P=″SCIENCE″B.P=″STUDY″C.S=″SCIENCE″D.S=″STUDY″8.链栈与顺序栈相比，比较明显的优点是(满分:5)A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况9.当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为(满分:5)A.A．左子树的叶子结点B.B．左子树的分支结点C.C．右子树的叶子结点D.D．右子树的分支结点10.高度为5的完全二叉树中含有的结点数至少为(满分:5)A.16B.17C.31D.3211.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为(满分:5)A.0B.1C.48D.4912.快速排序在最坏情况下的时间复杂度是(满分:5)A.O(n2log2n)B.O(n2)C.O(nlog2n)D.O(log2n)13.for（i=0；i；i++）for（j=0；j；j++）c［i］［j］=0；for（i=0；i；i++）for（j=0；j；j++）for（k=0；k；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；上列程序的时间复杂度为(满分:5)A.O（m+n×t）B.O（m+n+t）C.O（m×n×t）D.O（m×t+n）14.根据数据元素的关键字直接计算出该元素存储地址的存储方法是(满分:5)A.顺序存储方法B.链式存储方法C.索引存储方法D.散列存储方法15.在计算机内实现递归算法时所需的辅助数据结构是(满分:5)A.栈B.队列C.树D.图16.除第一层外，满二叉树中每一层结点个数是上一层结点个数的(满分:5)A.1/2倍B.1倍C.2倍D.3倍17.一棵完全二叉树上有1001个结点，其中叶子结点的个数是(满分:5)A.250B.500C.254D.以上答案都不对18.若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列(满分:5)A.一定存在B.一定不存在C.不一定存在D.不确定19.以下说法不正确的是(满分:5)A.无向图中的极大连通子图称为连通分量B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D.有向图的遍历不可采用广度优先搜索20.数据元素及其关系在计算机存储器内的表示，称为数据的(满分:5)A.逻辑结构B.存储结构C.线性结构D.非线性结构16春学期《数据结构Ⅰ》在线作业2一、单选题：1.设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是(满分:5)A.8B.3C.5D.92.for（i=0；i；i++）for（j=0；j；j++）c［i］［j］=0；for（i=0；i；i++）for（j=0；j；j++）for（k=0；k；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；上列程序的时间复杂度为(满分:5)A.O（m+n×t）B.O（m+n+t）C.O（m×n×t）D.O（m×t+n）3.为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为(满分:5)A.05B.37C.41D.624.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到(满分:5)A.P=″SCIENCE″B.P=″STUDY″C.S=″SCIENCE″D.S=″STUDY″5.若要在单链表中的结点p之后插入一个结点s，则应执行的语句是(满分:5)A.s-next=p-next;p-next=s;B.p-next=s;s-next=p-next;C.p-next=s-next;s-next=p;D.s-next=p;p-next=s-next;6.设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为(满分:5)A.4B.5C.6D.77.下述哪一条是顺序存储结构的优点(满分:5)A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示8.设给定权值总数有n个，其哈夫曼树的结点总数为(满分:5)A.不确定B.2nC.2n+1D.2n-19.二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为(满分:5)A.470B.471C.472D.47310.抽象数据类型的三个组成部分分别为(满分:5)A.数据对象、数据关系和基本操作B.数据元素、逻辑结构和存储结构C.数据项、数据元素和数据类型D.数据元素、数据结构和数据类型11.数据结构中所定义的数据元素，是用于表示数据的(满分:5)A.最小单位B.最大单位C.基本单位D.不可分割的单位12.以下数据结构中，属于线性结构的是(满分:5)A.广义表B.二叉树C.稀疏矩阵D.串13.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为(满分:5)A.数组的元素处在行和列两个关系中B.数组的元素必须从左到右顺序排列C.数组的元素之间存在次序关系D.数组是多维结构，内存是一维结构14.索引非顺序文件的特点是(满分:5)A.主文件无序，索引表有序B.主文件有序，索引表无序C.主文件有序，索引表有序D.主文件无序，索引表无序15.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的(满分:5)A.层次遍历算法B.前序遍历算法C.中序遍历算法D.后序遍历算法16.下列编码中属于前缀编码的是(满分:5)A.{101000001}B.{101011010}C.{01011011}D.{010011}17.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是(满分:5)A.(rear-front)%m==1B.front==rearC.(rear-front)%m==m-1D.front==(rear+1)%m18.导致栈上溢的操作是(满分:5)A.栈满时执行的出栈B.栈满时执行的入栈C.栈空时执行的出栈D.栈空时执行的入栈19.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为(满分:5)A.O(n)B.O(e)C.O(n+e)D.O(n2)20.n个顶点的强连通图中至少含有(满分:5)A.n-1条有向边B.n条有向边C.n(n-1)/2条有向边D.n(n-1)条有向边16春学期《数据结构Ⅰ》在线作业3一、单选题：1.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是(满分:5)A.nB.2n-1C.2nD.n-12.为便于判别有向图中是否存在回路，可借助于(满分:5)A.广度优先搜索算法B.最小生成树算法C.最短路径算法D.拓扑排序算法3.在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是(满分:5)A.LL型B.LR型C.RL型D.RR型4.一个有向无环图的拓扑排序序列是(满分:5)A.一定唯一的B.一定不唯一的C.不一定唯一的D.都不对5.设给定权值总数有n个，其哈夫曼树的结点总数为(满分:5)A.不确定B.2nC.2n+1D.2n-16.以下属于逻辑结构的是(满分:5)A.顺序表B.哈希表C.有序表D.单链表7.执行下列程序段后，串X的值为S=〞abcdefgh〞;T=〞xyzw〞;substr(X,S,2,strlen(T));substr(Y,S,stelen(T),2);strcat(X,Y);(满分:5)A.〞cdefgh〞B.〞cdxyzw〞C.〞cdefxy〞D.〞cdefef〞8.下列数据结构中，属于非线性数据结构的是(满分:5)A.栈B.队列C.完全二叉树D.堆9.若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为(满分:5)A.1和n+1B.1和n/2C.－1和nD.－1和n+110..对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为(满分:5)A.39/15B.49/15.C.51/15D.55/1511.假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为(满分:5)A.n-1B.nC.n+1D.n+212.以下数据结构中，属于线性结构的是(满分:5)A.广义表B.二叉树C.稀疏矩阵D.串13.在一棵高度为k的满二叉树中，结点总数为(满分:5)A.2k-1B.2kC.2k-1D.log2kû+114.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是(满分:5)A.栈B.队列C.树D.图15.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系(满分:5)A.不一定相同B.都相同C.都不相同D.互为逆序16.倒排文件的主要优点是(满分:5)A.便于进行插入和删除运算B.便于进行文件的恢复C.便于进行多关键字查询D.节省存储空间17.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为(满分:5)A.0B.1C.48D.4918.含n个关键字的二叉排序树的平均查找长度主要取决于(满分:5)A.关键字的个数B.树的形态C.关键字的取值范围D.关键字的数据类型19.算法的时间复杂度主要取决于(满分:5)A.问题的规模B.待处理数据的初态C.难度D.A和B20.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为(满分:5)A.(rear-front-1)％nB.(rear-front)％nC.(front-rear+1)％nD.(rear-front+