资源描述：
《数据结构2008答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、西安电子科技大学考试时间120分钟试题题号一二三四五六七八九十总分分数1.考试形式：闭（开）卷；2.本试卷共四大题，满分100分。班级学号姓名任课教师一、单选题（15 小题，每题2 分，共30 分）1.计算机算法指的是（C）。A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法2.链表不具有的特点是（B）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比3.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）
2、个元素是（B）。A.不确定B.n-i+1C.iD.n-i4.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时(D)。A．仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头、队尾指针都可能要修改5.最大容量为n的循环队列，队尾指针是rear，队头指针是front，则队空的条件是（B）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front6.串的长度是指（B
3、）。A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数7.设A为一个10阶的对称矩阵，采用压缩存储方式，以行序为主序，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（B）。A.13B.33C.18D.408.广义表运算式Tail(((a,b),(c,d)))的操作结果是（C）。A.(c,d)B.c,dC.((c,d))D.d第1页共8 页9.在一棵高度为h的完全二叉树中，所含结点个数不小于(A)。h1h+1hhA.2
4、B. 2 C. 2 1 D. 2 10.设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1，M2和M3，则与森林F对应的二叉树根结点的右子树上的结点个数是（D）。A．M1B．M1+M2C．M3D．M2+M311.引入二叉线索树的目的是（A）。A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲D．使二叉树的遍历结果唯一12.要连通具有n个顶点的有向图，至少需要（B）条边。A．n-lB．nC．n+lD．2n13.对线性表进行二分查找时，要求线性
5、表必须（B）。A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序14.如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用下列排序算法中(D)算法最快。A.归并排序B.希尔排序C.快速排序D.基数排序15.某内排序方法的稳定性是指(D)。A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（nlogn）的排序方法D．以上都不对二、填空题(共15 分，每空1 分)1. 数据的逻辑结构是指数据对
6、象中数据元素之间的逻辑关系, 数据的物理结构是指数据元素在存储空间中的存储方式。2. 在一个具有 n个结点的有序单链表中插入一个新结点并保持链表有序的算法时间复杂度为O(n)。3. 一棵满二叉树中共有 n个结点，其中 m个叶子结点，则 n和m的关系为n=2m1 。4. 广义表(a, (a, b), d, e, ((f, g), k))的长度是5 ，深度是3 。5. 已知 S = 'abaabcac', 则其 next 函数值为01122312 。h16. 高度为 h的 3 阶 B树中叶子结点的数目
7、至少为2 。7. 将两个长度分别为 m和 n的递增有序表归并成一个递增有序表（m£ n），需要的元素比较次数最少为m 。8. 用 S表示入栈操作，X表示出栈操作，若元素的入栈顺序为 1、2、3、4，则得到出栈序列 1、3、4、2时，S和 X操作串是SXSSXSXX 。9. 用 n个单元的一维数组构成一个循环队列，已知队头指针 front 指向当前队头元素所在的位置，队尾指针 rear指向当前队尾元素的下一位置，则队列中现有的元素个数为(rearfront+n)%n 。10. 在 n个结点的线索二叉
8、树中，线索的数目是n+1 。第2页共8 页11. 在有 17 个元素构成的有序表 A[1..17]中进行折半查找，则找到的元素为 A[8]时，被比较的元素的下标依次为9,4,6,7,8 或9,5,7,8 。12. 一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。13. 快速排序在待排元素已经有序的情况下排序性能最差。三、简答题（7小题，共45分）1.（4 分）已知如下森林，画出对应的二叉树。答案：2. （6 分）有一份电文中共使用
