《数据结构1-6章习题Word版》由会员分享，可在线阅读，更多相关《数据结构1-6章习题Word版（21页珍藏版）》请在金锄头文库上搜索。
1、算法与数据结构第1-6章课堂测验（双号）一、选择题1、已知一个栈的进栈序列是1,2,3,n,其输出序列是p1,p2,pn,若p1=n,则pi的值。（ c ）(A) i (B) n-i(C) n-i+1 (D) 不确定2、设n个元素进栈序列是1,2,3,n,其输出序列是p1,p2,pn,若p1=3,则p2的值。（ c ）(A) 一定是2(B) 一定是1(C) 不可能是1 (D) 以上都不对3、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ b ） A.6 B.11 C.15 D.不确定4、在下述结论中，正确的是（ d ）只有一个结点的二叉树的度为0; 二叉树的度为2
2、；二叉树的左右子树可任意交换;深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A. B. C. D.5、一棵树高为K的完全二叉树至少有（）个结点。（ a ） A.2k 1 B.2k-1 +1 C.2k-1 D.2k二、简答题1 简述下列术语：线性表，顺序表，链表。2 线性表：最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。3 顺序表：是指用一组连续的存储单元一次存储线性表中的数据元素。物理结构和逻辑结构都相邻。4 链表：逻辑结构相邻的数据元素物理结构不一定相邻。采用指针的形式连接起来。2 何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么
3、?不需要经常大量的修改表或需要随机存取的情况下可以选用顺序表；相反需要经常大量的修改表，但不是频繁的随机存取的情况下可选用链式表。3链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解?答：有序。有序性体现在通过指针数据元素有序的相连。物理上不一定要相邻。4设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。void ListInsert(SqList A,SqList B,SqList C)ElemType *p,*q,*s;P=&A;q=&B;s=&C;wh
4、ile(p.next!=NULL|q.next!=NULL)if(p.next.datafront=0;q-count=0; int EnQu(QuType *&q,ElemType x)/*进队*/ int rear;if (q-count=MaxSize) return 0; /*队满上溢出*/else rear=(q-front+q-count+MaxSize)%MaxSize; /*求队尾位置*/ rear=(rear+1)%MaxSize; /*队尾位置进1*/ q-datarear=x; q-count+; return 1; int DeQu(QuType *&q,ElemTyp
5、e &x)/*出队*/if (q-count=0)/*队空下溢出*/ return 0;else q-front=(q-front+1)%MaxSize; x=q-dataq-front; q-count-; return 1;int QuEmpty(QuType *q)/*判空*/ return(q-count=0);1 设有一个栈，元素进栈的次序为a, b, c。问经过栈操作后可以得到哪些输出序列？cba； abc； acb；bac； bca；2循环队列的优点是什么?如何判断它的空和满?优点：可以克服顺序队列的“假上溢”现象，能够使存储队列的向量空间得到充分利用。判断循环队列的空或满不能以
6、头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。三是设置一计数器记录队列中元素的总数，不仅可判别空或满，还可以得到队列中元素的个数2 设有一个静态顺序队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？3 队列为空：front=rear。队满：rear=MAX -1或front=rear4 (队首指针front ，一个队尾指针rear)55 设有一个静态循环队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？6 循环队列为空：front=rea
7、r 。 循环队列满：(rear+1)%MAX=front。7 (队首指针front ，一个队尾指针rear)85设Q0,6是一个静态顺序队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。a, b, c, d入队a, b, c出队i , j , k , l , m入队d, i出队n, o, p, q, r入队其中l,m,n,o,p,q,r均由于队列假溢出问题无法入队6假设Q0,5是一个循环队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。
8、d, e, b, g, h入队d, e出队i , j , k , l , m入队b出队n, o, p, q, r入队假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树的树边集合为 (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) ，用树型表示法表示该树，并回答下列问题： 哪个是根结点? 哪些是叶子结点? 哪个是g的双亲? 哪些是g的祖先? 哪些是g的孩子? 那些是e的子孙? 哪些是e的兄弟? 哪些是f的兄弟? b和n的层次各是多少? 树的深度是多少? 以结点c为根的子树的深度是多少?根节
9、点：a 叶子节点：i ,d , j, f , l g 的双亲节点:c g 的祖先：c , a g 的孩子：j e 的子孙：ie的兄弟：d f的兄弟：g , hb的层次：2 树的深度：4 以结点c为根的子树的深度：3一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：各层的结点数是多少?编号为i的结点的双亲结点(若存在)的编号是多少?编号为i的结点的第j个孩子结点(若存在)的编号是多少?编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? (1) 设层号为i的结点数目为m=k(i-1
10、) (2) 编号为i的结点的双亲结点的编号是：(i+k-2)/k(不大于(i+k-2)/k的最大整数。也就是(i+k-2)与k整除的结果.以下/表示整除。 (3) 编号为i的结点的第j个孩子结点编号是：k*(i-1)+1+j; (4)编号为i的结点有右兄弟的条件是(i-1)能被k整除 右兄弟的编号是i+1.三、算法理解 1、已知P结点是某双向链表的中间节点，画图并写出下列操作的语句序列。（1）在P结点后插入S结点。（2）删除P结点的后继结点Q。结点结构如下：PriorDataNext （其中Prior、Data、Next分别为前驱节点指针、数据域、后继节点指针。）答：（1）P-Next-Prior=S; S-Next=P-Next; P-Next=S; S-Prior=P;(2) Q=P-Next; P-Next=P-Next-Next; P-Next-P
