合肥工业大学研究生软件技术基础总复习题及参考答案

ii一、选择题软件技术基础总复习题及参考答案1、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址D。A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以2、栈和队列都是B。A、顺序存贮的线性结构B、限制存取点的线性结构C、链接存贮的线性结构D、限制存取点的非线性结构3、与线性表的链接存贮不相符合的特性是C。A、便于插、删运算B、存贮空间动态分配C、需要连续的存贮空间D、只能顺序查找4、设二叉树的根为第一层，则第i层上的结点数最多有d。A、２B、２+1C、２i-１D、２i-15、如将一棵有n个结点的完全二叉树按顺序存放方式，存放在下标编号为0,1,…,n-1的一维数组中，设某结点下标为k(k0)，则其双亲结点的下标是A。A、(k-1)/2B、(k+1)/2C、k/2D、k-16、由权值分别为3,8,6,2,5的叶子结点生成一棵霍夫曼树，它的带权路径长度为A。A、53B、48C、72D、247、设I和O分别表示入栈和出栈操作，栈的初态和终态都为空，则下列操作序列合法的有_D__。A、IOIOOIOIB、IOOIOIIOC、IIIOIOIOOD、IIOIIOOO8、二叉树的前序序列为EFHIGJK，中序序列为HFIEJKG，则二叉树的根为C。A、KB、GC、ED、H9、对有序表{-1,0,1,3,4,6,8,10,12}进行折半查找，则查找12需要比较的次数为B。A、3B、4C、5D、610、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行D。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;11、一个栈的入栈序列为a，b，c，则出栈序列不可能的是C。A、c,b,aB、b,a,cC、c,a,bD、a,c,b12、如果将一棵有n个结点的完全二叉树按层次遍历次序，存放在下标编号为0,1,…,n-1的一维数组中，设某结点下标为k(k0)，如果其左孩子存在，则其左孩子结点的下标是C。A、2k–1B、2kC、2k+1D、2k+213、用整数5,7,3,6,4作为五个树叶的权值，可以构造一棵带权路径长度值为C的霍夫曼树。A、78B、62C、57D、2514、设单链表中结点结构为(data,link)，若想删除结点*p的直接后继，则应执行下列哪一个操作A。A、p-link=p-link-link;B、p=p-link;p-link=p-link-link;C、p-link=p-link;D、p=p-link-link;15、顺序表是线性表的B。A、链式存储结构B、顺序存储结构C、索引存储结构D、散列存储结构16、若某线性表中最16、常用的操作是取第i个元素和找第i个元素的前趋元素，则采用A存储方式最节省时间。A、顺序表B、单链表C、双链表D、单循环链表17、当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行B语句修改top指针。A、top++;B、top--;C、top=0;D、top;18、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2.,则AA、n0=n2+1B、n2=n0+1C、n0=2n2+1D、n2=2n0+119、具有35个结点的完全二叉树的深度为A。A、5B、6C、7D、820、在有向图中，所有顶点的入度之和是所有顶点出度之和的B倍。A、0.5B、1C、2D、421、若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行B次比较。A、33B、45C、70D、9122、对含有B个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。A、0B、1C、2D、不存在这样的二叉树23、数据结构是一门研究非数值计算的程序设计问题中计算机的A以及它们之间的B和运算等的学科。①A.数据元素B.计算方法C.逻辑存储D.数据映像②A.结构B.关系C.运算D.算法24、数据结构在计算机内存中的表示是指A。A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系25、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法26、在数据结构中，从逻辑上可以把数据结构分成C。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构27、带头结点的单链表head为空的判定条件是B。A.head==NULLB.head-next==NULLC.head-next==headD.head!＝NULL28、在循环双链表的p所指结点之前插入s所指结点的操作是D。A.p-prior=s；s-next=p；p-priornext=s；s-prior=p-prior；B.p-prior=s；p-prior-next=s；s-next=p；s-prior=p-prior；C.s-next=p；s-prior=p-prior；p-prior=s；p-right-next=s；D.s-next=p；s-prior=p-prior；p-priornext=s；p-prior=s；29、需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是B。A.单链表B.静态链表C.线性链表D.顺序存储结构30、栈和队列的共同点是C。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点31、向一个栈顶指针为hs的链栈中插入一个s所指结点时，则执行C。A.hs-next=s;B.s-next=hs-next;hs-next=s;C.s-next=hs;hs=s;D.s-next=hs;hs=hs-next;32、判定一个环形队列qu（最多元素为MaxSize）为空的条件是C。A.qu-rear-qu-front==MaxSizeB.qu-rear-qu-front-l==MaxSizeC.qu-front==qu-rearD.qu-front==qu-rear+l33、若用一个大小为6的一维数组来实现环形队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是B。A.1和5B.2和4C.4和2D.5和134、在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算是C。A.r=f-next;B.r=r-next;C.f=f-next;D.f=rnext;35、下图所示二叉树的中序遍历序列是B。A.abcdgefB.dfebagcC.dbaefcgD.defbagc36、深度为5的二叉树至多有C个结点。A.16B.32C.31D.1037、对一个满二叉树，m个树叶，n个结点，深度为h，则D。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-138、下列说法正确的是A。A、链栈没有容量限制B、顺序栈没有容量限制C、链队有容量限制D、单向链表有容量限制39、在一个无向图中，所有顶点的度数之和等于所有边数的C倍。A.1/2B.1C.2D.440、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是D。A.nB.(n-1)2C.n-1D.n241、已知一个图如下图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为D；按广度搜索法进行遍历，则可能得到的一种顶点序列为B。①A.a，b，e，c,d，fB.a，c，f，e，b，dC.a，e，b，c，f，dD.a，e，d，f，c，b②A.a，b，c，e，d，fB.a，b，c，e，f，dC.a，e，b，c，f，dD.a，c，f,d，e，b42、顺序查找法适合于存储结构为B的线性表。A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储43、采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为D。A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)44、对有18个元素的有序表作折半查找，则查找A[3]的比较序列的下标为D。A.1、2、3B.9,5、2、3C.9、5、3D.9,4、2、345、有一数列2、3、4、5，按2、3、4、5顺序入队，出队的顺序是A。A.2345B.3245C.5342D.243546、在排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为C。A.希尔排序B.冒泡排序C.插入排序D.选择排序47、在下列算法中，C算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。A.堆排序B.冒泡排序C.插入排序D.快速排序48、在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为D。A.O(1)B.O(log2n)C.O(n2)D.O(n)49、在决定选取何种存储结构时，一般不考虑A。A.各结点的值如何．B.结点个数的多少C.对数据有哪些运算D.所用编程语言实现这种结构是否方便50、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B。A.数据元素具有同一特点B.不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等51、不带头结点的单链表head为空的判定条件是A。A.head==NULLB.head-next==NULLC.head-next＝headD.head!=NULL52、非空的循环单链表head的尾结点（由p所指向）满足C。A.p-next==NULLB.p==NULLC.p-next==headD.p==head53、某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用D存储方式最节省运算时间。A.单链表B．仅有头结点的单循环链表C.双链表D.仅有尾指针的单循环链表54、如果最常用的操作是取第i个结点及其前驱，则采用D存储方式最节省时间。A.单链表B.双链表C.单循环链表D.顺序表55、设线性表有n个元素，以下算法中，A在顺序表上实现比在链表上实现效率更高。A.输出第i(0=i=n-1)个元素值B:交换第0个元素与第1个元素的值C.顺序输出这n个元素的值D.输出与给定值x相等的元素在线性表中的序号56、最不适合用作链栈的链表是D。A.只有表头指针没有表尾指针的循环双链表B.只有表尾指针没有表头指针的循环双链表C.只有表尾指针没有表头指针的循环单链表D.只有表头指针没有表尾指针的循环单链表57、栈的特点是B，队列的特点是A。A.先进先出B.先进后出58、一个队列的入队序列是1，2，3，4，则队列的输出序列是B。A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，4，159、环形顺序队列中是否可以插入下一个元素，A。A、与队头指针和队尾指针的值有关B.只与队尾指针的值有关，与队头指针的值无关C.只与数组大小有关，与队首指针和队尾指针的值无关D.与曾经进行过多少次插入操作有关60、环形队列用数组A[0：MaxSize-1]存放其元素值，已知其头尾指针分别是front和rear.则当前队列中的元素个数是A。A.(rear-front+MaxSize)％MaxSizeB.rear-front+lC.(rear-front-1)％MaxSizeD.(rear-front)％MaxSize61、在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是B。A.f-next=s；f=s;B.r-next=s；r=s;C.s-next=r；r=s;D.s-next=f；f=s;62、按照二叉树的定义，具有3个结点的二叉树有C种。A.3B.4C