数据结构期末试题(B).doc

《数据结构期末试题(B).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、汕头职业技术学院2008-2009学年第二学期期末试卷计算机系班级_______________学号_____姓名__________b5E2RGbCAP题号一二三四五六七八总分评卷人得分一、判断题<每小题1分，共15分）1、数据的物理结构是指数据在计算机内的实际存储形式。<）2、分配给单链表的内存地址必须是连续的。<）3、在有n个元素的顺序表中，删除任意一个元素所需移动结点的平局次数为n-1。<）4、对于单循环链表

2、，从表中任一结点都能扫描表中的全部结点。<）5、栈是一种对进栈、出栈操作总次数做了限制的线性表。<）6、无论是顺序队列还是链接队列，插入和删除元素运算的时间复杂度都是O(1）。<）7、表示稀疏矩阵的三元组顺序中，各元素的排列顺序与矩阵元素值的大小有关。<）8、完全二叉树中只有度为0和度为2的结点。<）9、已知二叉树的先序序列和后序序列，并不能唯一确定这棵二叉树。<）10、哈夫曼树中，权值较大的叶结点一般都离根结点较远。<）11、如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是完全有向图。<）12、

3、有向图的遍历不可采用广度优先搜索方法。<）13、顺序表和单链表表示的有序表均可使用二分查找法来提高查找速度。<）14、只有在记录的关键字的初始状态为逆序排列的情况下，直接选择排序过程中元素的移动次数才会达到最大值。<）p1EanqFDPw15、内排序中的快速排序方法，在任何情况下均可得到最快的排序效果。<）二、选择题<每小题2分，共40分）1．___________中任何两个结点之间都没有逻辑关系。A>集合B>图状结构C>树型结构D>线性结构2．计算机算法指的是__________。A>计算方法B>调

4、度方法C>排序方法D>解决某一问题的有限运算序列3．下面____________的时间复杂性最好，即执行时间最短。A>O(n>B>O(nlog2n>C>O(log2n>D>O(n3>4．在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1>位置插入一个新元素时，需要从后向前依次后移_________个元素。DXDiTa9E3d-4-/4A>n-iB>iC>n-i-1D>n-i+l5．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，插入一个元素时平均移动表中的_______个

5、元素。RTCrpUDGiTA>n/2B>(n-1>／2C>(n+1>／2D>n6．单链表要求内存中可用存储单元的地址。A>必须是连续的B>一定是不连续的C>部分地址必须是连续的D>可以是连续的，也可以是不连续的7．在一个单链表中，若要删除p指针所指向结点的后继结点，则执行________。A>p->next=pB>p=p->next->nextC>p->next=p->next->nextD>p=p->next；p->next=p->next->next5PCzVD7HxA8．若某链表最常用的操作是在

6、最后一个结点之后插入一个结点和删除最后一个结点，则采用______存储方式最节省时间。jLBHrnAILgA>单链表B>双链表C>单循环链表D>带头结点的双循环链表9．采用链接方式存储线性表的优点是_________。A>便于随机存取B>花费的存储空间较顺序存储少C>便于插入和删除操作D>数据元素的物理顺序和逻辑顺序相同10．在下面栈的基本运算中，不是加工型运算的是_______。A>初始化B>进栈C>退栈D>判栈空11．在顺序栈中进行退栈操作时，___________。A>谁先谁后都可以B>先移动栈

7、顶指针，后取出元素C>不分先后，同时进行D>先取出元素，后移动栈顶指针12．假设一个栈的输入序列为A，B，C，D，E，则下列序列中不可能是栈的输出序列的是_______。A>B，C，D，A，EB>E，D，A，C，BC>B，C，A，D，ED>A，E，D，C，B13．在由n个单元组成的顺序存储的循环队列sq中，假定f和r分别为队头指针和队尾指针，则判断队满的条件是_______。xHAQX74J0XA>f==(r十1>％nB>(r-1>％n==fC>f==rD>(f+1>％n==rLDAYtRyKfE14

8、．树最适合于表示__________。A>有序数据元素B>无序数据元素C>元素之间无联系的数据D>元素之间具有分支层次关系的数据15．在一棵深度为k的完全二叉树中，所含结点个数不小于_________。A>2kB>2k+1C>2k-1D>2k-116．在下列存储形式中，_______不是树的存储形式。A>双亲表示法B>顺序存储表示C>孩子兄弟表示法D>孩子链表表示法17．对于长度为8的顺序存储结构的有序表，若采用二分查找法查找，在等概率的情况下的平均查找