数据结构试卷(2008A)

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

1、班级:＿＿＿＿＿＿姓名:＿＿＿＿＿＿学号:＿＿＿＿＿＿第2页共页第1页共10页2008--2009学年第1学期期考试(A卷)课程名称：数据结构考试方式：开卷（）闭卷（√）题号一二三四五六七八九十总分统分人签名得分密封线考生注意事项：1、本试卷共页，请查看试卷中是否有缺页。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、选择题(每个选项1分，共20分)下列各题A)、B)、C)、D)四个选项中，只有一个选项是正确的，请将正确选项写在答题纸相应的位置上，答在试卷上不得分。得分评卷人1.从逻辑上可以把数据结构分为（)两大类。A.动态结构、静态结构B.顺序结构、链式结构C.线性结构

2、、非线性结构D.初等结构、构造型结构2.线性表是()。A.一个有限序列，可以为空；B.一个有限序列，不能为空；C.一个无限序列，可以为空；D.一个无序序列，不能为空。3.用链表表示线性表的优点是（）。A.便于随机存取B.花费的存储空间较顺序存储少C.便于插入和删除D.数据元素的物理顺序与逻辑顺序相同4.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表(C)双链表(D)仅有尾指针的单循环链表5.对于栈操作数的原则是（）A.先进先出B.后进先出C.后进后出D.部分顺序6.采用顺序存储的两个栈的

3、共享空间S[1..m]，top[i]代表第i个栈（i=1，2）的栈顶，栈的底在S[1]、栈2的底在S[m]，则栈满的条件是（）。A．top[2]-top[1]=0B．top[1]+1=top[2]C．top[2]-top[1]=mD．top[1]=top[2]7.一个入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。A.edcbaB.decbaC.dceabD.abcde8.串的长度是指()A．串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数9.数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首

4、地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（）。A.80B.100C.240D.27010.线索化二叉树中，某结点*p没有孩子的充要条件是（)。A.p->lchild=NULLB.p->ltag二1且p->rtag=1C.p->ltag=0D.p->lchild=NULL且p->ltag=111.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（)。A.490B.501C.500D.49512.若一棵二叉树的先序遍历序列为abdgcefh;中序遍历的序列为dgbaechf,则后序遍历的结果为（）。A.gcefhaB.gdbecfhaC.bdgaechfD.g

5、dbehfca13.一个具有567个结点的二叉树的高h为（）。A.9B:10C:9～566之间D.10～567之间班级:＿＿＿＿＿＿姓名:＿＿＿＿＿＿学号:＿＿＿＿＿＿第4页第3页1.n条边的无向图的邻接多重表的存储中，边结点的个数有（）。A.nB.2nC.n/2D.n×n2.最短路径的生成算法可用（）A.普里姆算法B．克普斯卡尔算法G迪杰斯特拉算法D.哈夫曼算法3.下面关于求关键路径的说法不正确的是（)。A.求关键路径是以拓扑排序为基础的B．一个事件的最早开始时间与以该事件为尾的弧的活动最早开始时间相同C.关键活动一定位于关键路径上D.一个事件的最迟开始时间为以该事件为尾的弧的活动

6、最迟开始时间与该活动的持续时间的差4.顺序查找适用于存储结构为（）的线性表。A.顺序存储或链式存储B.压缩存储C.散列存储D.索引存储5.散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率6.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，每块应分（）个结点最佳。A.10B.25C.6D.6257.一组记录的排序码为（46，79，56，38，40，84），则利用快速排序的方法，以第1个记录为基准得到的一次划分的结果为（)。A.38，40，46，56，79，84B.40，

7、38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，79二．判断题(本大题共10小题，每小题1分，共10分)请在每小题的括号中填上正确答案。错填、不填均无分。得分评卷人1.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）2.顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。()3.任何一个递归过程都可以转换成非递归过程。（）4.稀疏矩阵压缩存储后，会失去随即存储功能