资源描述：
《成人大专数据结构复习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、成人大专《数据结构》复习题一、单选题1．在一个顺序队列中，队首指针指向队首元素的( )位置。A．后一个B．前一个C．当前D．不一定2．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行( )。A．q—＞next＝p—＞next；p—＞next＝q5B．p—＞next＝q—＞next；q＝p；C．q—＞next＝p—＞next；p—＞next＝q；D．p—＞next＝q—＞next；q—＞next＝p；3．设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为( )。AO(n)BO(1)CO(n2)DO(lo
2、g2n)4．向堆中插入一个元素的时间复杂度为( )。AO(log2n)BO(n)CO(1)DO(nlog2n)5．由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。A．51B．23 C．53D．746．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（）条边。A．nB．2n C．n-1D．n+17．已知一个后缀算术表达式为：32153+6/-2+@ ，则它运算之后的结果是（ ）。A．2B．31 C．18D．208．假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为（ ）。
3、A．f+1==rB．r+1==f C．f==0D．f==r9．堆排序首先需要进行初始（ ）。 A．交换B．建堆 C．筛选8．若让元素1,2，3依次进栈，则出栈次序不可能出现（ ）种情况。 A．3,2，1B．2,1，3 C．3,1，2D．1,3，210．每次从待排序的区间中选出具有最小排序码的元素，把该元素与该区间的第一个元素交换位置。这种排序方法称为（ ）排序。 A．气泡 B．直接选择 C．直接插入D．快速11．图中各个元素之间的关系是（ ）的关系。 A．不一定B．一对多 C．一对一D．多对
4、多二、填空题1．.数据的逻辑结构被分为________________、________________、_______________和________________四种。2．在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的________________、________________和________________三项。3．假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则树中所含的结点数为________________个，树的深度为________________，树的度为_____________
5、___。4．在索引表中，若一个索引项对应主表中的一条记录，则称此索引为______________索引，若对应主表中的若干条记录，则称此索引为______________索引。5．对于一棵具有n个结点的树，该树中所有结点的度数之和为_____________。6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定_____________该结点的值，右子树上所有结点的值一定_____________该结点的值。三、运算题1．假定一个待散列存储的线性表为(27,16,59,46,78,32,51,22)，散列地址空间为HT[11]，若采用除
6、留余数法构造散列函数和线性探查法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。2．已知一个带权图的顶点集V和边集G分别为：V＝{O，1，2，3，4，5，6，7}；E＝{(o，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9}；则求出该图的最小生成树的权。最小生成树的权为： 3．已知一组元素的排序码为(49，75，16，53，12，26，30，38，91，65，25，33)写出利用快速排序方法进行第一次划分后元素后的排列结果。4．假定一棵二叉树的广义表表示为p(a(e,d)
7、，c(f(h)，g))，分别写出先根、中根、后根、按层遍历的结果。先根：中根：后根：四、算法分析题1．假定线性表La的类型为List，元素类型ElemType为int，La初始值为{26,31,49,72}，Insert()为向线性表的合适位置插入元素的函数，试写出每个程序段执行后所得到的线性表La。Insert(La,56);DeleteFront(La);InsertRear(La,DeleteFront(La));TraverseList(La);2．从一维数组A[n]中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否
8、则返回—1。intBinsch(ElemTypeA[]，intlow，inthigh，KeyTypeK){if(low＜high）{in
