《数据结构复习-学生版本有答案的》由会员分享，可在线阅读，更多相关《数据结构复习-学生版本有答案的（20页珍藏版）》请在金锄头文库上搜索。
1、第一章 引言 1 数据结构是一门研究非数值计算的程序设计问题中计算机的_(1)_ 以及它们之间的_(2)_ 和运算的学科。A B （1 ） A. 操作对象 B. 计算方法 C. 逻辑存储 D. 数据映象 （2 ） A. 结构 B. 关系 C. 运算 D. 算法 2 算法的五个要素：有穷性、确定性、 (3) 可行性、输入、输出 3 算法分析的目的是 (1) ，算法分析考虑哪两方面的问题 (2) C D （1 ）A) 找出数据结构的合理性 B) 研究算法中输入和输出关系 C) 分析算法的效率 D) 分析算法的易理解性 (2) A) 正确性和空间复杂性 B) 易读性和健壮性 C) 数据复杂性和程序复
2、杂性 D) 时间复杂性和空间复杂性 4 在数据结构中，逻辑上数据结构可分为_ B A) 动态结构和静态结构 B)线性结构和非线性结构 B)紧凑结构和非紧凑结构 D)内部结构和外部结构 第二章 线性表 1. 在一个单链表中，若删除 P 结点的后继结点，则_ A A). p-next = p-next-next; B). p = p-next; p-next = p-next-next; C). p-next = p-next D). p = p-next-next; 2. 写出在双向链表指针 P之后插入结点 S 的操作序列。 s-prior = p; s-next = p-next; p-nex
3、t-prior = s; p-next = s; 3. 线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_ 存储方式最节省运算时间。D A） 单链表 B）仅有头指针的单循环链表 C） 双链表 D）仅有尾指针的单循环链表 4. 有带头结点的单链表 la， lb，表中数据元素递增有序，写出将它们归并为一个递增有序单链表的算法。 算法 1： void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) /已知线性链表 La 和 Lb 的元素按值非递减排列 /归并 La 和 Lb 得到新的线链性表 Lc,Lc 的元素也
4、按值非递减排列。 pa=La-next; pb=Lb-next; Lc=pc=La; /用 La 的头结点作为 Lc 的头结点 while(pa & pb) If (pa-datadata) pc-next=pa;pc=pa;pa=pa-next; else pc-next=pb;pc=pb;pb=pb-next; pc-next=pa?pa:pb;/插入剩余段 free(Lb);/释放 Lb 的头结点 /MergeList_L 第三章 栈和队列 1. 队列操作的原则是 。 A A）先进先出 B）后进先出 C）只能进行插入 D）只能进行删除 2. 若已知一个栈的入栈序列是 1，2，3，.，n，
5、其输出序列为 p 1,p2,p3,pn,若p 1是n，则p i是 C A）i B)n-i C)n-i+1 D)不确定 3. 循环队列 A0.m-1存放其元素值，用 front 和 rear 分别表示队头及队尾，则当前队列中的元素数是 A A）(rear - front + m)%m B)rear - front + 1 C) rear - front - 1 D)rear-front 4. 在操作序列 push(1),push(2),pop,push(5),push(7),pop ,push(6)之后,栈顶元素和栈底元素分别是什么？ push(k)表示整数 k 入栈，pop 表示栈顶元素出栈。
6、 栈顶：6；栈底：1 5. 在操作序列 Qinsert(1),Qinsert(2),Qdelete,Qinsert(5),Qinsert(7),Qdelete, Qinsert(9).之后，队头元素和队尾元素分别是什么？队头：5；队尾 9 Qinsert(k)表示整数 k入队列,Qdelete 表示元素出队列。 6. 循环队列 A0.m-1存放其元素值，用 front 和 rear 分别表示队头及队尾， 则循环队列满的条件是_ A（空的条件是 Q.rear = Q.front） A）(Q.rear + 1)%m=Q.front B)Q.rear = Q.front + 1 C) Q.rear+
7、1 = Q.front D)Q.rear = Q.front 7. 写出链队列出队、入队算法 status L-pop(Linkstack &s,Elemtype &e) /此时队列的头是链表的头,s 指向头结点 if(!s-next) return Error; p=s-next; e=p-data; s-next=p-next; free(p); return OK; status L-push(Linkstack &s, Elemtype e)/ 此时队列的尾是链表的尾,s 指向尾结点 p=(Linkstack)malloc(sizeof(Lnode); /Lnode *p= new L
8、node; p-data=e; p-next=s-next; s-next=p; return OK; 第六章 树 1. 一棵二叉树高度为 h,所有结点的度或为 0,或为 2,则这棵二叉树最少有 个结点 B A）2h B）2h-1 C）2h+1 D）h+1 2. 表达式 a*(b+c)-d(它是对树按照中序遍历后的输出)的后缀表达式(是对树按照后序遍历后的输出) B A）abcd*+- B）abc+*d- C）abc*+d- D）-+*abcd 3. 下面说法正确的为 D （1）二叉树按某种方式线索化后，任一结点均有指向前驱和后继的线索 （2）二叉树的前序遍列序列中，任意一个结点均处在子孙结点
9、前 （3）二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值 A） （1） （2） （3） B） （1） （2） C） （1） （3） D）前面的可选答案都不对 4. 若某二叉树有 20 个叶子结点，有 30个结点仅有一个孩子，则该二叉树的总的结点数是 69 n0=n2+1,n=n0+n1+n2 5. 写出一棵满 k 叉树上的叶子结点数和非叶结点数之间的关系。n0=(k-1)*n1+1 树的总结点数：n = n0+n1；树的分叉数：n1*k = n = n1*k + 1 n0 + n1 = n1 * k + 1 = n0 = (k-1)*n1 + 1 6. 有 n 个结点的二叉树，用二叉
10、链表作为存储结构，空指针域有 个 n+1 7. 1). 写出前序遍历二叉树的递归算法 2). 如图二叉树, 给出按中序, 后序遍历树时的访问次序. 3).画出其先序线索树 E B F A D G I C 1) #include void preorder(Bitree *p) if(p != NULL) coutdata; preorder(p-lchild); preorder(p-rchild); 2) 中序：ABCDEGFI 后序：ACDBGIFE 3）先序访问次序：EBADCFGI E B F NULL A D C G I 9 二叉树的先序和中序遍历序列分别是 ABCDEFGH， CB
11、EDFAGH， 则后序遍历序列是 C A）HGFEDACB B）GHEDFCBA C）CEFDBHGA D）HGAFDEBC 此二叉树的形式如图ABC DE F GH11写出计算二叉树高度的递归算法。 int depth(Bitree *t) if(t = NULL) return(0); else hl = depth(t-lchild); hr = depth(t-rchild); if(hlhr) return(hl+1); else return(hr+1); 12写出计算二叉树叶子个数的递归算法。 void countleaf(Bitree *t, int *count) if(t!
12、=NULL) if(t-lchhild = NULL)&(t-rchild = NULL) *count+; countleaf (t-lchild,count); countleaf (t-rchild,count); 13写出二叉树左右子树交换的递归算法。 Bitree *swap(Bitree *b) Bitree *t, *t1, *t2; if(b = NULL) t = NULL; else t = new Bitree; t-data = b-data; t1 = swap(b-lchild); t2 = swap(b-rchild); t-lchild = t2; t-rchi
13、ld = t1; return t; 14写出按层次顺序（同一层自左向右）遍历二叉树的算法。 下述算法以二叉链表为存储结构。 #define maxlen 100 struct node Bitree *vecmaxlen; int front,rear; que; void trunslevel(Bitree *b) que.front = 0; que.rear = 0; if(b != NULL) coutdata; que.vecque.rear = b; que.rear+; while(que.frontlchild ! = NULL) coutlchild-data; que.v
14、ecque.rear = b-lchild; que.rear+; if(b-rchild ! = NULL) coutrchild-data; que.vecque.rear = b-rchild; que.rear+; 15 假设一棵二叉树的先序序列为 EBADCFHGIKJ 和 中序序列为 ABCDEFGHIJK， 请画出该树。 E B A D F H G I KJ C 16 假设一棵二叉树的中序序列为 DCBGEAHFIJK 和 后序序列为 DCEGBFHKJIA。 请画出该树。 A B I C G H J D E F K第七章 图 1.设图G 用邻接表存储，则拓扑排序的时间复杂度为_ B A) O(n) B) O(n+e) C) O(n2) D) O(n*e) 2无向图 G=（V，E） ，其中：V= a,b,c,d,
