资源描述：
《数据结构-2009(A)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构－A一．单项选择题（2×10=20分）1.在带头结点的单链表中，若*p不是尾结点，在其后插入*s结点的操作是。A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;C.s->next=p->next;p=s;D.p->next=s;s->next=p;2.设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为 。A.2B.3C.4D.53.实现链式队列的最简单的方法是采用
2、。A.只带表尾指针的循环单链表B.只带表头指针的循环单链表C.只带表尾指针的非循环单链表D.只带表头指针的非循环单链表4．广义表((a),a)的表头是①，表尾是②。A.(a)B.aC.()D.((a))5.在一棵二叉树中，双分支的结点数为15，单分支结点数为30，则叶子结点数为。A.15B.16C.17D.476.在无向图中，所有顶点的度数之和是所有边数的 倍。A.0.5B.2C.1D.47.在一个具有6个顶点的无向图中，至少有 条边才能确保是一个连通图。A.5B.6C.7D.88.若对有R[1..18]有序表作二分查
3、找，则查找R[3]的比较序列的下标为。A.1，2，3B.9，5，2，3C.10，5，3D.9，4，2，39.设哈希表长m=14，哈希函数H(key)=keymodll。表中已有4个结点addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空，如用平方探测再散列法处理冲突，则关键字为49的结点的地址是。A.8B.3C.5D.910.若表R在排序前已按关键字正序排序，则方法的比较次数最少。A.直接插入排序B.快速排序C.归并排序D.选择排序二．填空题（2×5=10分）1.已知图G的邻接表
4、如图1所示，其从顶点1出发的深度优先搜索序列为①，其从顶点1出发的广度优先搜索序列为②。图1图G的邻接表2．有如图2所示的二叉树，其前序遍历序列是①，中序遍历序列是②，后序遍历序列是③。图2一棵二叉树三．问答题（共40分）1.（12分）将{3,5,8,2,6,1,9,4,7,0}中的关键字依次插入初态为空的二又排序树中，请画出所得到的二又排序树T。然后画出删去3之后的二叉排序树T1，若再将3插入T1中得到的二叉排序树T2是否与T相同?最后给出T2的先序、中序和后序序列。2.（8分）对于给定的一组关键字{83,40,63,13,
5、84,35,96,57,39}，试用归并排序进行排序，写出每一趟的结果。3.（8分）在具有n个结点的k次树（高度至少为2）的孩子链存储结构中，有多少个空指针?4、（12分）在堆排序、快速排序和归并排序中：（1）若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？（2）若只从排序结果的稳定性考虑，则应选取哪种排序方法？（3）若只从平均情况下排序最快考虑，则应选取哪种排序方法？（4）若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？四．算法设计题（2×15=30分）1．有一个学
6、生成绩线性表（a1,a2,…,an）用带头结点的单链表h存储（ai均为整数），编写一个算法，由其中所有成绩不及格的元素构成的另一个单链表h1，要求不破坏h的结点，该算法格式为：voidfun(LinkList*h,LinkList*&h1)2．以二叉链作为二叉树的存储结构，编写一个算法，将二叉树T复制到T1中，要求不破坏T的结点，该算法格式为：voidcopytree(BTNode*T，BTNode*&T1)
