数据结构练习题附答案(8页).doc

《数据结构练习题附答案(8页).doc》由会员分享，可在线阅读，更多相关《数据结构练习题附答案(8页).doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-数据结构练习题附答案-第 1 页习题B 一、填空题1.在二叉树的二叉链表表示中，指针p所指结点为叶子结点的条件是 。2.在有序表A1.12中，采用二分查找算法查等于A12的元素，所比较的元素下标依次为 。3一个栈的输入序列为1,2,3,n，若输出序列的第一个元素是n，输出第i（1=inext=top; D. top=top-next;13.具有10个叶结点的二叉树中有 B 个度为2的结点，A.8 B.9 C.10 D.ll14.某栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是 D 。A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d

2、, c，a，b15. 数组A05,06的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5,5的地址是 B 。A1180 B1175C1205 D1210三、判断题1. 无向图中所有顶点的度数之和等于所有边数的2倍。 （ t ）2. 折半查找中要求表必须有序，表可以顺序方式存储，也可以链表方式存储。 （ f ）3. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（ f ）4. 通过拓扑排序可以判断有向图中是否有环的存在。 （ t ）5. 二叉树是指度为2的有序树。 （ f ）6. 线性表的顺序存储结构比链式存储结构更好

3、。（ f）7. 由树转化成二叉树，该二叉树的右子树不一定为空。（ f）8. 顺序表查找指的是在顺序存储结构上进行查找。（f ）9. 当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（t ）10. 非空的双向循环链表中任何结点的前驱指针均不为空。（t ）四、应用题1.已知无向网G，如右图所示，完成如下要求：（1）写出无向网G的邻接矩阵；（2）画出无向网G的最小生成树。2.请根据给出的关键字序列：43，12，72，8，16，50，80，完成如下要求：（1）画出相应的二叉排序树；（2）若要查找50需和哪些关键字进行比较。3.Seven with weight node, weights ar

4、e 4,7,5,2,8,9,14, try to structure a tree leaf nodes Hoffman tree, try drawing out generated Hoffman tree, and calculated with weight WPL path length.（10 points） 4. 某无向图的顶点表为(1,2,3,4)，下图为其邻接矩阵表，请画出该无向图。5在如下数组A中链接存储了一个线性表，A0为头结点，试写出该线性表。A 0 1 2 3 4 5 6 7data605078903440next35720416已知一组关键字(19,14,23,1,

5、68,20,84,27,55,11,10,79)，哈希函数为：H(key)=key MOD 13, 用链地址法处理冲突，要求：（1）试构造这组关键字的散列表；（8分）答案在课件上。（2）试求出查找成功的平均查找长度。（2分）五、算法分析与设计题1.已知循环队列Q的结构如下所示：struct QueueElemType baseMAXSIZE; /ElemType为元素类型 int front,rear; /front为队头指针，rear为队尾指针试写出以下内容：（1） 判空条件；（2分）（2） 判满条件；（2分）（3） 入队时的指针变化情况；（2分）（4） 出队时的指针变化情况；（2分）（5）

6、 队长。（2分）2.已知待排序的关键字序列为12，2，16，30，28，10，16*，20，6，18，完成如下要求：（1）写出折半插入排序算法；（2）写出使用折半插入排序方法每趟排序结束后关键字序列的状态；3.Please write down the code of the pivot position of the sub table rlow.high in quick sort. 4. 假定电文字符集为A,B,C,D,E,F,G,H,它们在电文中出现的次数分别为19,6,12,5,38,3,13,4）,为这8个字符设计哈夫曼编码。画出哈夫曼树并给出编码。要求在构造哈夫曼树的过程中,权值

7、较小结点放在左侧,编码时左分支生成代码0,右分支生成代码1。习题B答案一、填空题1.p-lchild=NULL&p-rchild=NULL(或者!p-lchild&!p-rchild，或者p指针所指结点的左右孩子指针均为空) 2.6,9,11,12 3.n-i+14.n-1 5.50 6.L-next=NULL(或者!L-next) 7.n 8. 顺序 链式（不论先后顺序） 9. 9 3 3 10. 0 11. 5 12. 0二、单选题1-5 BCDCA 6-10CBBCC 11-15 DDBDB三、判断题四、应用题1.（1）（2）2.（1）（2）43，72， 503（1）（2）WPL=9*2

8、+5*3+2*4+4*4+14*2+7*3+8*3=1304. 14235. 线性表（78，50，40，60，34，90）6.（2）ASL=(1*6+2*4+3+4)/12=1.75五、 算法分析与设计题1.（1）Q.front=Q.rear （2）(Q.rear+1)%MAXSIZE=Q.front （3）Q.rear=(Q.rear+1)%MAXSIZE （4）Q.front=(Q.front+1)%MAXSIZE （5）(Q.rear-Q.front+MAXSIZE)%MAXSIZE 2.（1）答案在书上。（2）初始序列：12 22 16 30 28 10 16* 20 6 18 第1趟

9、排序结果：12 22 16 30 28 10 16* 20 6 18 第2趟排序结果：12 16 22 30 28 10 16* 20 6 18 第3趟排序结果：12 16 22 30 28 10 16* 20 6 18 第4趟排序结果：12 16 22 28 30 10 16* 20 6 18 第5趟排序结果：10 12 16 22 28 30 16* 20 6 18 第6趟排序结果：10 12 16 16* 22 28 30 20 6 18 第7趟排序结果：10 12 16 16* 20 22 28 30 6 18 第8趟排序结果：6 10 12 16 16* 20 22 28 30 18 第9趟排序结果：6 10 12 16 16* 18 20 22 28 304. 10038622512133718819871183456A：111B：11011C：100D：11010E：0F：11000G：101H：11001