搜索
一.选择题1.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。A．8B.63.5C.63D.72.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，则A[3][3]在（）位置，（10）表明用10进数表示。！P113A．692（10）B.626（10）C.709（10）D.724（10）·3.一个有序顺序表有255个对象，采用顺序搜索查表，平均搜索长度为（）。？A．128B.127C.126D.255·4.含5个结点（元素值均不相同）的二叉树搜索树有（）种。A．54B.42C.36D.655．N个顶点的连通图至少有（）条边。A．N－1B.NC.N＋1D.06．对于两个函数，若函数名相同，但只是（）不同则不是重载函数。A．参数类型B.参数个数C.函数类型D.函数个数7．若需要利用形参直接访问实参，则应把形参变量表明为（）参数。A．指针B.引用C.值D.地址·8．下面程序的时间复杂度为（）。！for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;A．O(m2)B.O(n2)C.O(m*n)D.O(m+n)·9.下面算法的时间复杂度为（）。！intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A．O(1)B.O(n)C.O(n2)D.O(n!)10.设单链表中结点的结构为(data,link)。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s,则应执行下列哪一个操作（）。！A．s-link=p-link;p-link=s;B.q-link=s;s-link=p;C.p-link=s-link;s-link=q;D.p-link=s;s-link=q;11.设单链表中结点的结构为(data,link)。若想摘除结点*p的直接后继，则应执行下列哪一个操作（）。！A．p-link=p-link-link;B.p=p-link;p-link=p-link-linkC.p-link=p-link;D.p=p-link-link;12.栈的插入和删除操作在（）进行。！A．栈顶B.栈底C.任意位置D.指定位置13．若让元素1，2，3依次进栈，则出栈次序不可能出现哪种情况（）。！A．3，2，1B.2，1，3C.3，1，2D.1，3，2#14．广义表A(a),则表尾为（）。A．aB.(())C.空表D.（a）#15．下列广义表是线性表的有（）。A．E(a,(b,c))B.E(a,E)C.E(a,b)D.E(a,L())16.折半搜索与二叉搜索树（即二叉排序树）的时间性能（）。A．相同B.完全不同C.有时不相同D.不确定17．采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（）。！A．O(nlog2n)B.O(n)C.O(log2n)D.O(n)18.采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。！A．中序遍历B.前序遍历C.后序遍历D.按层次遍历19．每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做（）排序。！A．插入B.选择C.交换D.外排序20．采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）。A．中序遍历B.前序遍历C.后序遍历D.按层次遍历二.填空题1.算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应具有输入、输出、___确定性________、有穷性和可执行性等特性。！·2.在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是_______2____。！3.队列的插入操作在______队尾_____进行，删除操作在____队头_______进行。4.当用长度为n的数组顺序存储一个栈时，若用top==n表示栈空，则表示栈满的条件为_____top==0______。！5.对序列(49,38,65,97,76,27,13,50)采用快速排序法进行排序，以序列的第一个元素为基准元素得到的划分结果是___[132738]45[50657697]_______________。！6.对于一棵具有n个结点的树，该树中所有结点的度数之和为___n-1__________。7.在一个堆的顺序存储中，若一个结点的下标为i，则它的左子女结点的下标为______2i+1____，右子女结点的下标为___2i+2_______。·8.请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用折半查找关键码12需做_____4_________次关键码比较。！9.若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100,则第12个元素的存储地址是_____144_____________。10.在一个长度为n的顺序表中，向第i个元素（1≤i≤n＋１）之前插入一个新元素时，需要向后移动_____n-i+1_______个元素。？11.设有两个串p和q，求q在p中首次出现的位置的运算称作____求子串_______。·12.以折半搜索方法搜索一个线性表时，此线性表必须是___顺序________存储的__有序_________表。·13.在一个无向图中，所有顶点的度数之和等于所有边数的____2_______倍。14.判定一个循环队列QU(最多元素为m)为满队列的条件是__QU-front==(QU-rear+1)%m____。___________。#15．设有广义表【不要求广义表】D(a,b,D)，其长度为___3________，深度为___________。16．在一个具有n个顶点的无向完全图中，要连通所有顶点则至少需要___n-1____条边，在一个具有n个顶点的有向完全图中，包含有_n(n-1)____条边。17.对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为____n*n_______。18.对于一个具有n个顶点和e条边的连通图，其生成树中顶点数和边数分别为____n_______和____n-1_______。19.在直接选择排序中，记录比较次数的时间复杂度为___O(n*n)________，记录移动次数的时间复杂度为_____O(n)______。20．快速排序在平均情况下的空间复杂度为___O(logn)________，在最坏情况下的空间复杂度为________O(n)___。21.当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的____时间复杂度_______。25.在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是___m/2_________条。26.对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为_______n的平方____。三、判断题（y）1.直接选择排序是一种不稳定的排序方法。（n）2.折半搜索只适用于有序表，包括有序的顺序表和有序的链表。（y）3.数据的逻辑结构与数据元素本身的内容和形式无关。（n）4.数据结构是指相互之间存在一种或多种关系的数据元素的全体。（n）5.线性表的逻辑顺序与物理顺序总是一致的。（y）6.线性表若采用链式存储表示时所有存储单元的地址可连续可不连续。（y）7.二叉树是数的特殊情形。（y）8.若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。（n）9.若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。（n）10.任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。（n）11.对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。（y）12.最优二叉搜索树的任何子树都是最优二叉搜索树。（y）13.在二叉搜索树上插入新结点时，不必移动其它结点，仅需改动某个结点的指针，使它由空变为非空即可。（y）14.有n（n≥1）个顶点的有向强连通图最少有n条边。（n）15.连通分量是无向图中的极小连通子图。（n）16.二叉树中任何一个结点的度都是2。（n）17.单链表从任何一个结点出发，都能访问到所有结点。四、程序阅读填空1.在顺序表中第i个位置插入新元素x！templateclassTypeintSeqListType::Insert(Type&x,inti){if(i0||ilast+1||last==MaxSize-1)return0;//插入不成功else{last++;for(intj=last;ji;j--)data[j]=data[j-1];data[i]=x;return1;//插入成功}}2.删去链表中除表头结点外的所有其他结点templateclassTypevoidListType::MakeEmpty(){ListNodeType*q;while(first→link!=NULL){q=firstlink;firstlink=qlink;//将表头结点后第一个结点从链中摘下deleteq;//释放它}last=first;//修改表尾指针}3.删去链式队头结点（队头指针为QueueNodeType*front），并返回队头元素的值templateclassTypeTypeQueueType::DeQueue(){assert(!IsEmpty());//判队空的断言QueueNodeType*p=______front____________________;Typeretvalue=p→data;//保存队头的值__front=frontlink__;//新队头deletep;returnretvalue;}#4.最小堆的向下调整算法（没有）templateclassTypevoidMinHeapType::FilterDown(intstart,intEndOfHeap){inti=start,j=2*i+1;//j是i的左子女Typetemp=heap[i];while(j=EndOfHeap){if(jEndOfHeap&&heap[j].keyheap[j+1].key)j++;//两子女中选小者if(temp.key=heap[j].key)break;else{heap[i]=heap[j];i=j;j=2*j+1____；}}__heap[i]=temp;____;}5．基于有序顺序表的折半搜索递归算法（Element为有序顺序表）！templateclassTypeintorderedListType::BinarySearch(constType&x,constintlow,constinthigh)const{intmid=-1;if(low=high){____mid=(low+high)/2______;if(Element[mid].getKey()x)mid=BinarySearch(__x,mid+1,high_____);elseif(Element[mid].getKey()x)mid=BinarySearch(x,low,mid-1);}returnmid;}6.直接插入排序的算法（按关键码Key非递减顺序对数据表list进行排序）（无）templateclassTypevoidInsertionSort(datalistType&list){for(inti=1;ilist.CurrentSize;i++)_______inter(list,i)_______;}templateclassTypeviodInsert(datalistType&l