数据结构试卷A

答题不允许超越边线否那么无效班级：姓名：学号：答题不允许超越边线否那么无效班级：姓名：学号：河北建筑工程学院2016—2017学年第一学期《数据结构》试卷〔A〕题号一二三四五六七八九总分得分单项选择〔每题1分，共25分〕1、算法的时间复杂度是指〔〕。A〕执行算法程序所需要的时间B〕算法程序中的指令条数C〕算法执行过程中所需要的根本运算次数D〕算法程序的长度2、下面〔〕的时间复杂度最好〔即执行时间最短〕。A〕O(n)B〕O()C〕O(n)D〕O(n2)3、在数据结构中，与所使用的计算机无关的是数据的〔〕结构。A〕逻辑B〕存储C〕逻辑和存储D〕物理4、下面程序段的时间复杂度为〔〕inti,j,m,n,a[][];for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A〕O(m2)B〕O(n2)C〕O(m*n)D〕O(m+n)5、在存储数据时，通常不仅需要存储各数据元素的值，而且还要存储〔〕。A〕数据的处理方法B〕数据元素的类型C〕数据元素之间的关系D〕数据的存储方法6、在一个长度为n的顺序存储的线性表中，删除第i个元素〔1≤i≤n+1〕时，需要依次前移〔〕个元素。A〕n-iB〕n–i+1C〕n–i-1D〕i16.假设一个链接队列的队头指针和队尾指针分别为front和rear，那么判别队列空的条件为〔〕。A〕front==rearB〕front!=NULLC〕rear!=NULLD〕front==NULL17.树中所有结点的度等于所有结点数加〔〕。A〕1B〕0C〕-1D〕218.按照二叉树的定义，具有3个结点的二叉树，共有〔〕种。A〕3B〕4C〕5D〕619.在一棵深度为h的完全二叉树中，所含结点个数不小于〔〕。A〕2hB〕2h+1C〕2h–1D〕2h-120.在一棵完全二叉树中，假设编号为i的结点存在左孩子，那么左孩子结点的编号为〔〕。A〕2i-1B〕2iC〕2i+2D〕2i+121.利用3，6，8，12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为〔〕。A〕38B〕58C〕29D〕5522.在一个具有n个结点的无向图中，假设具有e条边，那么所有顶点的度数之和为〔〕。A〕nB〕eC〕2eD〕n+e23.对顺序存储的有序表〔5，12，20，26，37，42，46，50，64〕，采用折半查找，那么查找元素26的查找长度为〔〕。A)2B)3C)4D)524.在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度的为〔〕。A〕O(1)B〕O(n2)C〕O(n)D〕O()25.对元素序列〔7，3，5，9，1，12，8，15〕进行快速排序，在进行第一遍划分后，得到的左区间中元素的个数为〔〕。A〕2B〕3C〕4D〕二、填空题〔每空2分，共30分〕1.在下面程序段中，s=s+p语句的执行次数为，p*=j语句的执行次数为，该程序段的时间复杂度为。inti=0,s=o;while(++i<=n){intp=1;for(intj=1;j<=i;j++)p*=j;s=s+p;}四、算法阅读题〔每题5分，共10分〕1.voidexam2(LinStack&s){InitStack(s);//初始化s栈Push(s,30);//向s栈压入30Push(s,40);Push(s,50);intx=Pop(s)+2*Pop(s);Push(s,x);inti,a[4]={5,8,12,15};for(i=0;i<4;i++)Push(s,a[i]);//将数组a各元素入栈while(!StackEmpty(s))cout<<Pop(s)<<′′;//依次出栈cout<<endl;}该算法的输出结果为：________________________________2.阅读以下二叉树操作算法，指出该算法的功能。unknown(BinTreeNode<Type>*t){BinTreeNode<Type>*p=t,*temp;if(p!=NULL){temp=p→leftchild;p→leftchild=p→rightchild;p→rightchild=temp;unknown(p→leftchild);undnown(p→rightchild);}}该算法的功能是：____________________________________答题纸一、单项选择〔每题1分，共25分〕1、______2、_______3、_______4、_______5、_______6、______7、_______8、_______9、_______10、_______11、______12、_______13、_______14、_______15、_______16、______17、_______18、_______19、_______20、_______21、______22、_______23、_______24、_______25、_______二、填空题〔每空2分，共30分〕1、〔〕、〔〕、〔〕2、〔〕3、〔〕、〔〕4、〔〕、〔〕5、〔〕、〔〕6、〔〕、〔〕、〔〕7、〔〕8、〔〕三、解答题〔每题5分，共20分〕1、2、四、算法阅读题〔每题5分，共10分〕1、〔〕2、〔〕五、算法设计题〔5+10，共15分〕7、线性表的链式存储比顺序存储最有利于进行〔〕操作。A〕查找B〕表尾插入或删除C〕按值插入或删除D〕表头插入或删除8、带头结点的单链表H为空的判定条件是〔〕。A〕H==NULLB〕H->next==NULLC〕H->next==HD〕H!=NULL9、在一个带头结点的单链表H中，假设要向表头插入一个由指针p指向的新结点，那么应执行的操作是〔〕A〕H=p;p->next=H;B〕p->next=H;H=p;C〕p->next=H;p=H;D〕p->next=H->next;H->next=p;10、设线性表有n个元素，以下算法中，〔〕在顺序表上实现比在链表上实现的效率更高。A〕输出第i〔0≤i≤n-1〕个元素B〕交换第0个元素与第1个元素的值C〕顺序输出这n个元素的值D〕输出与给定值x相等的元素在线性表中的序号11．二分查找要求节点〔〕A〕．有序、顺序存储B〕.有序、链接存储C〕．无序、顺序存储D〕.无序、链接存储12.栈的插入和删除操作在〔〕进行。A〕栈顶B〕栈底C〕任意位置D〕指定位置13.利用数组a[N]顺序存储一个栈时，用top表示栈顶元素的下标位置，用top==-1表示栈空，用top==N-1表示栈满，那么该数组所能存储栈的最大长度为〔〕。A〕N-1B〕NC〕N+1D〕N+214.假设让元素1，2，3，4依次进栈，那么出栈次序不可能出现〔〕的情况。A〕3，2，1，4B〕2，1，4，3C〕4，3，2，1D〕1，4，2，315.假设一个顺序循环队列的队头指针和队尾指针分别用front和rear表示，那么判别队空的条件为〔〕。A〕front+1==rearB〕rear+1==frontC〕front==0D〕front==rear2、一种数据结构的元素集合为D，它在D上的二元关系R为：D={a,b,c,d,e,f,g,h}R={<d,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,<e,f>}那么该数据结构具有结构。3．线性表的顺序存储结构称为；线性表的链式存储结构称为。4.在单链表中指针p所指结点的后面，插入一个指针q所指的结点时，首先把的值赋给q->next，然后把的值赋给p->next。5.往栈中插入一个元素称为运算。从栈中删除一个元素〔即删除栈顶元素〕称为运算。6.有7个带权结点，其权值分别为3，7，8，2，6，10，14，以它们为叶子，生成一棵哈夫曼树，那么带权路径长度为，高度为，双分支结点数为。7.对于线性表〔7，34，55，25，64，46，20，10〕进行散列存储时，假设选用H〔K〕=K%9作为散列函数，那么散列地址为1的元素有个。8.中缀算式〔3+4X〕-2Y/3对应的后缀算式为____________。三、解答题〔每题5分共20分〕1.一个无向图的顶点集为{a,b,c,d,e},其邻接矩阵如下所示abcde(1)画出该图的图形〔2〕根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应