华工数据结构卷

一.选择题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.0 6．对于两个函数，若函数名相同，但只是（）不同则不是重载函数。A．参数类型B.参数个数C.函数类型D.函数个数7．若需要利用形参直接访问实参，则应把形参变量表明为（）参数。A．指针B.引用C.值D.地址·8．下面程序的时间复杂度为（）。！for(inti=0;i<m;i++)for(intj=0;j<n;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个结点的树，该树中所有结点的度数之和为}2.删去链表中除表头结点外的所有其他结点template<classType>voidList<Type>::MakeEmpty(){ListNode<Type>*q;while(first→link!=NULL){

q=firstlink;firstlink=qlink;//将表头结点后第一个结点从链中摘下deleteq;//释放它}last=first;//修改表尾指针} 3.删去链式队头结点（队头指针为QueueNode<Type>*front），并返回队头元素的值template<classType>TypeQueue<Type>::DeQueue(){assert(!IsEmpty()); //判队空的断言

QueueNode<Type>*p=______front____________________; Typeretvalue=p→data;//保存队头的值

__front=frontlink__; //新队头deletep;returnretvalue; }#4.最小堆的向下调整算法（没有）template<classType>voidMinHeap<Type>::FilterDown(intstart,intEndOfHeap){inti=start,j=2*i+1;//j是i的左子女Typetemp=heap[i];while(j<=EndOfHeap){if(j<EndOfHeap&&heap[j].key>heap[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为有序顺序表）！template<classType>intorderedList<Type>::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进行排序）（无）template<classType>voidInsertionSort(datalist<Type>&list){

for(inti=1;i<list.CurrentSize;i++)_______inter(list,i)_______;}

template<classType>viodInsert(datalist<Type>&list,inti){Element<Type>temp=list.Vector[i];intj=i;//从后向前顺序比较while(j>0&&temp.getKey()<list.Vector[j-1].getKey()){ ______list.vector[j]=list.vector[j-1]______;j--;}list.Vector[j]=temp;}7.直接选择排序的算法:（没）template<classType>voidSelectSort(datalist<Type>&list){

for(inti=0;i<list.CurrentSize-1;i++)___SelectExchange(list,i)____;}

template<classType>viodSelectExchange(datalist<Type>&list,constinti){intk=i;for(intj=i+1;j<list.CurrentSize;j++)if(list.Vector[j].getKey()<list.Vector[k].getKey())____k=j_______;//当前具有最小关键码的对象if(k!=i)Swap(list.Vector[i],list.Vector[k]);//交换}#8.判断一个带表头结点的双向循环链表L是否对称相等的算法如下所示：（无）intsymmetry(DblListDL){intsym=1;DblNode*p=DL->rLink,*q=DL->lLink;While(p!=q&&p->rLink!=q&&sym==1)if(p->data==q->data){____p=prLink_____;_______q=qlLink_________________;}elsesym=0;returnsym;}五、简答题给定权值集合{15,03,14,02,06,09,16,17},构造相应的霍夫曼树,并计算它的带权外部路径长度。！(Ⅰ)05171609061415F：17160906021415(Ⅰ)05171609061415F：17160906021415020303020303(Ⅱ)1716091415(Ⅱ)171609141520161415(Ⅲ)171120161415(Ⅲ)171109110605091106050203020306050605(Ⅴ)332029020329161720(Ⅳ)(Ⅴ)332029020329161720(Ⅳ)161711091514141109151617110915141411091505060506060506050203020302030203(Ⅰ)05171609061415F：17160906021415(Ⅰ)05171609061415F：17160906021415020303020303(Ⅱ)1716091415(Ⅱ)171609141520161415(Ⅲ)171120161415(Ⅲ)171109110605091106050203020306050605(Ⅴ)332029020329161720(Ⅳ)(Ⅴ)332029020329161720(Ⅳ)1617110915141411091516171109151414110915050605060605060502030203020302038282(Ⅶ)4933(Ⅵ)4933(Ⅶ)4933(Ⅵ)4933172920161716292017292016171629201411091511091514141109151109151406050605060506050302030203020302 此树的带权路径长度WPL=229。线性表可用顺序表或是链表存储，此两种存储表示各有哪些特点，优缺点？！P50设有一个输入数据的序列是{46,25,78,62,12,37,70,29}，试画出从空树起，逐个输入各个数据而生成的二叉搜索树。按顺序逐个输入46/\2578/\/123762/\2970对于如右图所示的有向图，试写出：！(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树；P178#5.用广义表的带表头结点的存储表示法表示下列集合。A=()B=(6,2) C=(‘a’,(5,3,‘x’))D=(B,C,A) E=(B,D)6.右图所示为一有向图，请给出该图的下述要求：（1）给出每个顶点的入度和出度；130222312431521614（2）以结点3为起始结点，分别画出该图的一个深度优先生成树和一个宽度优先生成树；（3）给出该图的邻接矩阵；（4）给出该图的邻接表；（5）给出该图的逆邻接表；7.已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，试构造出该二叉树。先序序列_BC_EF__中序序列BDE_AG_H后序序列e_DCb_GHf_A8.已某个不带权的无向图采用邻接矩阵存储方法依次将顶点的数据信息存放于一维数组ABCDEFGH中，边的信息存放于邻接矩阵中，邻接矩阵为

01100000

10