答案西安交通大学2020春《数据结构》在线作业

.在二叉排序树中插入一个关键字值的平均时间复杂度为()。A.O(n)B.O(1og2n)C.O(nlog2n)D.O(n2)答案：B.设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,则在结点A和结点B插入结点X的操作序列为()。A.s->next=p->next;p->next=-sB.q->next=s;s->next=pC.p->next=s->next;s->next=pD.p->next=s;s->next=q答案：B.字符串的长度是指()。A.串中不同字符的个数B.串中不同字母的个数C.串中所含字符的个数D.串中不同数字的个数答案：C.设某无向图有n个顶点，则该无向图的邻接表中有()个表头结点。A.2nB.nC.n/2D.n(n-1)答案：B.用链接方式存储的队列，在进行插入运算时()。A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改答案：D.下列程序段的时间复杂度为()。I=0,s=0;while(s<n){s=s+i;i++;}A.O(n1/2)B.O(n1/3)C.O(n)D.O(n2)答案：A.如果要求频繁的对线性表进行插入和删除操作，则线性表应该采用()存储结构。A.散列.顺序C.链式D.任意答案：C.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为()。A.8B.7C.6D.5答案：B.设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列()存储方式最节省运算时间。A.单向链表B.单向循环链表口双向链表口.双向循环链表答案：D10.以下数据结构中哪一个是非线性结构?()A.队列B.栈C.线性表D.二叉树答案：D.每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里，这种存储结构称为()结构。A.顺序结构B.链式结构C.索引结构D.散列结构答案：A.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为()。A.q=p->next;p->data=q->data;p->next=q->next;free(q)B.q=p->next;q->data=p->data;p->next=q->next;free(q)C.q=p->next;p->next=q->next;free(q)D.q=p->next;p->data=q->data;free(q)答案：A.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为()。A.O(n)B.O(nlog2n)C.O(1)D.O(n2)答案：C14.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为()。A.24B.71C.48D.53答案：B15.对一棵二叉排序树进行()遍历，可以得到该二叉树的多有结点按值从小到大排列的序列。A.前序B.中序C.后序D.按层次答案：B.若目标串的长度为n,模式串的长度为[n/3],则执行模式匹配算法时，在最坏情况下的时间复杂度是()。A.O(1)B.O(n)C.O(nA2)D.O(nA3)答案：C.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，打印机依次从该缓冲区中取出数据打印，则该缓冲区的结构应该是()。A.线性表B.数组C.堆栈D.队列答案：D18.线性链表各结点之间的地址()。A.必须连续B.一定不连续C.部分地址必须连续D.连续与否无所谓答案：D.在二叉排序树中插入一个结点的时间复杂度为()。A.O(1)B.O(n)C.O(log2n)D.O(n2)答案：B.设指针变量p指向双向链表中结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为()。A.p->right=s;s->left=p;p->right->left=s;s->right=p->rightB.s->left=p;s->right=p->right;p->right=s;p->right->left=sC.p->right=s;p->right->left=s;s->left=p;s->right=p->rightD.s->left=p;s->right=p->right;p->right->left=s;p->right=s答案：D.设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为()。A.2，3，5，8，6B.3，2，5，8，6C.3，2，5，6，8D.2，3，6，5，8答案：C.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为()。A.O(1)B.O(n)C.O(m)D.O(m+n)答案：C.对于线性表(7，34，55，25，64，46，20，10)进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有()个。A.1B.2C.3D.4答案：D.下列各个排序算法中，要求辅助空间最大的是()。A.希尔排序法B.快速排序法C.堆排序法D.二路归并排序法答案：D25.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是()。A.直接选择排序B.直接插入排序C.快速排序D.起泡排序答案：C.一个栈的输入序列为123...n，若输出序列的第一个元素是n，输出i(1<=i<=n)个元素是()。A.不确定B.n-i+1C.iD.n-i答案：B.链式栈与顺序栈相比，一个比较明显的优点是()。A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便答案：B.程序段如下：s=i=0;do{i=i+1;s=s+i;}while(i二n);其时间复杂度为()。A.O(n)B.O(nlog2n)C.O(n2)D.O(n3/2)答案：A.一个具有n个顶点的无向图最多有()条边。A.nX(n-1)/2B.nX(n-1)C.nX(n+1)/2D.n2答案：A.数组A[0..4,-1..-3,5..7]中含有元素的个数()。A.55B.45C.36D.16答案：B.快速排序是排序算法中平均性能最好的一种排序。()A.错误B.正确答案：B.有向图的邻接表和逆邻接表中表结点的个数不一定相等。()A.错误B.正确答案：A33.顺序查找法适用于存储结构为顺序或链接存储的线性表。()A.错误B.正确答案：B34.对具有n个元素的序列来采用冒泡排序法进行排序，排序的趟数为n-1。()A.错误B.正确答案：A35.顺序表用一维数组作为存储结构，因此顺序表是一维数组。()A.错误B.正确答案：A36.栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。()A.错误B.正确答案：B.入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。()答案：B.在B+树中查找和在B-树中查找的过程完全相同。()A.错误B.正确答案：A39.图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。()A.错误B.正确答案：B40.为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。()A.错误B.正确答案：B41.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。()A.错误B.正确答案：B.磁带是顺序存取的外存储设备。()A.错误B.正确答案：B.图可以没有边，但不能没有顶点。()答案：B.分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。()A.错