2008 2009 学年第__一_学期期末考查试卷 [a]卷

《2008 2009 学年第__一_学期期末考查试卷 [a]卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、密封线内禁止答题南京信息职业技术学院试卷2008/2009学年第__一_学期期末考查试卷[A]卷课程名称：数据结构考试时间：100分钟命题人边长生2008年12月15日审批人年月日使用班级：90718D成绩：。。题号一二三四总分阅卷人得分一、选择题（40分，每题2分）1、数据的基本单位是。A．数据结构B.文件C.数据元素D.数据项2、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为。A．O(n)B．O(1)C．O(n2)D．O(log2n)3、采用链式存储结构存储时，要求占用的存储空间地址。A.必须是连续的B.部分地址必须是连续的C.一定是不连

2、续的D.可连续可不连续4、若让元素1，2，3依次进栈，则出栈次序不可能出现种情况。A．3，2，1B．2，1，3C．3，1，2D．1，3，25、链式栈与顺序栈相比，一个比较明显的优点是。A.通常不会出现栈满的情况B.插入操作更加方便C.不会出现栈空的情况D.删除操作更加方便6、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是。A.110B.108C.100D.1207、在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是。A.p->next=s;s->prior=p;p->next->prior=s;s->next

3、=p->next;B.s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;C.p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;8、在一个顺序队列中，队首指针指向队首元素的________位置。　　A.前一个B.后一个C.当前D.末尾9、稀疏矩阵的压缩存储可以使用下列哪种存储方式：。A.二维数组B.三维数组C.三元组D.散列10、设有

4、两个串t和p，求p在t中首次出现的位置的运算叫做。A.求子串B.模式匹配C.串替换D.串连接11、一颗二叉树上第5层的结点数最多为。A.8B.16C.15D.3212、在一棵二叉树中，度数为2的结点数等于n2，度数为1的结点数等于n1，那么度数为0的结点数等于是_______。A.n1+1B.n1+2C.n2+1D.n2+213、在一棵完全二叉树中，若编号为i的结点存在左孩子，则左孩子结点的编号。A.2i-1B.2iC.2i+1D.2i+214、由带权为9,2,5,7的四个叶子结点构造一棵哈夫曼树，则该树的带权路径长度为。A.23B.37C.46D.441

5、5、设a，b为一颗二叉树上的两个结点，在中序遍历时，a在b前的条件是：　　A.a在b右方B.a在b左方C.a是b的祖先D.a在b的子孙16、在一个具有n个顶点的有向完全图中，所含的弧数为。A．nB.n*(n-1)C.n*(n+1)D.n*(n-1)/2数据结构考查试卷B卷第4页共4页密封线内禁止答题17、n个顶点的连通图至少有条边。A.n-1B.nC.n+1D.018、顺序查找法适合于存储结构为的线性表。A.散列存储B.顺序存储或链接存储C.索引存储D.压缩存储19、对线性表进行对分查找时，要求线性表必须。A.以顺序存储方式存储B.以链式存储方式存储C.以

6、顺序存储方式存储，且数据元素有序D.以链式存储方式存储，且数据元素有序20、在建立某高校网站时，为方便浏览，建立了校-系-教研室的链接，则这数据结构属于。A．线性结构B．树结构C．图结构D．集合结构选择题答案1234567891011121314151617181920二、填空题（14分，每空2分）1、在一个单链表中删除p所指结点的下一个结点时，应执行以下操作：q=p->next;p->next=；Deleteq；2、在最优二叉树中有n个叶子结点，则树中共有个结点。3、在一棵树中，______结点没有后继结点。4、在一个图中，所有顶点的度数之和等于所有边的

7、数目的_________倍。5、函数insert_sort(inta[],intcount)是用直接插入排序法对指定数组的前count个元素从小到大排序。voidinsert_sort(inta[],intcount){inti,j,t;for(i=1;i=0&&t

8、中出现的概率为7%，数据结构考查试卷B卷第4页共4页密封线内禁止答