数据结构期中测试-2014级计算机网络技术用

1、数据结构期中测试 -2014 级计算机网络技术用1-11每小题 3 分，共 33分1. 下面关于线性表的叙述中， 错误 的是哪一个？（ ）A. 线性表采用顺序存储，必须占用一片连续的存储单元B. 线性表采用顺序存储，便于进行插入和删除操作C. 线性表采用链式存储，不必占用一片连续的存储单元D. 线性表采用链式存储，便于插入和删除操作2. 线性表的以下存储结构中，已知结点存储地址，求其前驱复杂度最高的的存储结构是 （）A. 顺序表B.双向链表C.单链表D.双向循环链表3. 设指针变量 p指向单链表中的某结点， q指向其后继节点， s指向一个新开辟的结点，能将 s 所指结点插入到 p所指结点后面的

2、操作为 （ ）A. s=p-next; q=s-next;B. s-next=p-next; p-next=s;C. q-next=s; s-next=p;D. p-next=s-next; s-next=q;4. 设入栈序列为 ABCD ，则以下序列中不可能是出栈序列的为()A.ABCD B.DCBA C.BDAC D.BACD5.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要 输出的数据依次写入该缓冲区， 而打印机则依次从该缓冲区中取出数据。构应该是（ ）A. 栈 B.队列 C.树6. 对于最大容量为 n的循环队列 Q ，队尾指针是()A.(Q.rear+1

3、) % n=Q.frontC.Q.rear+1=Q.front7. 深度为 K 的完全二叉树至少具有的顶点个数为K K-1 KA.2 -1 B.2 C.2 +1该缓冲区的逻辑结D.图Q.rear ，队头是 Q.front ，则队空的条件是B. Q.rear=Q.frontD.(Q.rear-1) % n=Q.front)K-1D.2 +18. 将树转换为对应的二叉树，若在二叉树中结点可能具有的关系是（ ）u是 v的父结点，则在原来的树中， u和 vA. 只能是兄弟关系B.只能是父子关系C. u 既可能是 v 的兄弟，也可能是 v 的父结点D. v 既可能是 u 的兄弟，也可能是 u 的父结点9

4、. 一棵二叉树具有 10个度为 2的结点， 5 个度为 1的结点，则度为 0 的结点个数是（ ）A.9 B.11 C.15 D. 不确定10. 有 n（ n 1）个叶子的 Huffman 树，其结点总数为（ ）A. 不确定B.2n C.2n+1 D.2n-111. n 个结点的线索二叉树上含有的线索数为（）A.2n B.n lC.nlD.n12-18 每小题 2 分，共 14 分12. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。A. 正确 B. 错误13. 单链表中引入头结点有利于简化结点插入以及删除操作的实现。A. 正确B. 错误14. 双循环链表中，任一个结点的前驱指针都

5、不为空。A. 正确B. 错误15. 栈采用顺序存储结构，执行入栈操作时会引起大量元素的移动。A. 正确B. 错误16. 二叉树的先序遍历序列与后序遍历序列不可能相同。A. 正确B. 错误17. 树的先根序遍历序列等同于它所对应二叉树的先序遍历序列。A. 正确B. 错误18. 二叉树可以用二叉链表存储，树与森林无法用二叉链表存储。A. 正确B. 错误以下每小问分值，在题后标出19. 已知一棵二叉树先序序列为 ABDEFCGHI ，中序序列为 DBFEAGHCI（1） 试画出该二叉树； 6 分（2） 试画出该二叉树对应的树或者森林； 6 分答案：（1）2)对应的森林为：20. 已知字符 A-F 的

6、出现频率依次为 2，3， 5，6，11，9，(1) 给出上述字符最优编码对应的 Huffman 树，并在叶子旁标注相应字符；(2) 计算上述 Huffman 树的带权路径长度。 3 分8分A(2) 带权路径长度为： 8721. 二叉树采用二叉链表存储结构，试写出一递归算法计算二叉树的深度。(1) 写出二叉链表的类型定义，数据域要求为整型 5 分(2) 写出完成问题的算法 10 分参考答案 :(1)typedef struct BiTNode int data;struct BiTNode *lchild,*rchild; BiTNode, * BiTree;(2) 算法描述 :int Tree

7、Depth(BiTree T)int d,d1,d2;if (T=NULL)d=0;else d1=TreeDepth(T-lchild);d2=TreeDepth(T-rchild);d=d1=d2?d1+1:d2+1;return d;22. 设 L 为一个带头节点的单链表 L ，表中各个元素取值均不相同，设计算法将表中元素值 最小的结点删除(1) 写出单链表的类型定义，数据域要求为整型 5 分(2) 写出完成问题的算法 10 分参考答案：(1)typedef struct LNode int data;struct LNode *next; LNode, * LinkList;(2) 算法描述 :void DelMin(LinkList L)LNode *p=L-next, *prep=L;LNode *p_min=L-next; p