数据结构0111101211作业题.DOC

《数据结构》复习题（一） 一、判断题（下列各题，你认为正确的，请在前面的括号内打√，错误的打×。每题1分，共10分） （ ）1. 数据的存贮结构是数据的逻辑结构的存贮映象。 （ ）2. 用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系。 （ ）3. 非线性结构中，至少存在一个元素不止一个直接前趋或不止一个直接后继。 （ ）4. 树的最大特点是层次结构。 （ ）5. 队列的特点是先进先出。 （ ）6. 图的最小生成树是唯一的。 （ ）7. 线性表是广义表的特殊形式。 （ ）8. 后序序列和中序序列能唯一确定一棵二叉树。 （ ）9. 散列表是一种链式存贮结构。 （ ）10. 快速排序并非在任何情况下都比其它排序方法速度快。 二、填空题（每空2分，共20分） 1． 数据的存贮结构的四种形式为 存贮、 存贮、 存贮和 存贮。 2．所有插入和删除都在表的一端进行的线性表称为 。 3．n个结点的完全二叉树，其深度h= 。 4．对于顺序循环队列Q[M]，下标从0到M-1，头尾指针分别为F和R，入队时，队尾指针循环加1可表示为R= 。 5．散列法既是一种查找方法，又是一种 方法。 6．n个顶点的有向完全图具有 条弧。 7．n个元素的顺序查找的平均查找长度为 。 三、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题3分，共15分）。 1．若进栈序列为1，2，3，4，则不可能得到的出栈序列是（ ） （1）3,2,1,4 （2）3,2,4,1 （3）4,2,3,1 （4） 2,3,4,1 2．对于下列二叉树，其后序序列为（ ） （1）ABDECFG （2）DBEAFCG （3）DEBFGCA （4）GFCEBDA 3．对于下列AOV网，不能出现的拓扑序列为（ ） （1） 1 2 3 4 51 2 4 3 5 （3）2 4 1 3 5 （4）2 1 4 3 5 4．深度为k的完全二叉树所含叶结点的个数最多为 （ ） （1）2k （2） 2k-1 （3） k （4） 2k 5．衡量查找算法效率的主要标准是 （ ） （1） 元素个数 （2） 所需的存贮量 （3） 平均查找长度 （4） 算法难易程度 四、应用题（25分） 1．将下列森林转化为二叉树。（3分） 2．对下图： （1）写出其邻接矩阵。（2分） （2）按Kruskal算法求其最小生成树；并写出相应的边集数组。（4分） 3．请画出后序和中序序列相同的二叉树的所有形态。（3分） 4．散列函数为H（k）=k%7，散列表的地址从0到6，用线性探查法解决冲突，建立散列表ht。给定关键字序列 {32，13，49，55，22，38，21} 要求：（1）构造散列表（只画出表，不写算法）；（5分） （2）求出平均查找长度。（2分） 5．用直接选择排序方法对下列关键字进行排序，请写出每一趟排序的结果。（6分） 68 45 20 90 15 10 50 五、算法设计（在下列算法的横线上填上适当的表达式或语句或运算符。每空3分，共30分） 1．在带头结点的head单链表的结点a之后插入新元素x struct node { elemtype data; node *next; }; void lkinsert (node *head, elemtype x) { node *s, *p; s=──────────────────────; s-data=_____; p=head-next; while (p!=NULL) ( p-data!=a ) ___________________; if (p==NULL) cout“不存在结点a”; else {__________________________; __________________________; } } 2．快速排序 void qksort (int R[ ], int p, int q) // 按递增序对R[p] ~R[q] 进行快速排序 {