数据结构第一次测验.pdfVIP

临沂师范学院2011-2012学年度第一学期 《数据结构》平时测试试题一 一、判断题 1.线性表的长度是线性表所占用的存储空间的大小。( ) 2.顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。( ) 3.线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是 O(N)， 因而两种存储方式的插入、删除运算所花费的时间相同。( ) 4.双循环链表中，任一个结点的后继指针均指向其逻辑后继。( ) 5.在链队列中，即便不设置尾指针也能进行入队列操作。( ) 6.在顺序表中取出第i个元素所花费的时间与i 成正比。( ) 7.已知指针P 指向链表L 中某结点，执行语句P=P-next 不会删除该链表中结点。( ) 8.在带头结点的单循环链表中，任一结点的后继指针均不空。( ) 9.完全二叉树中，若一个结点没有左孩子，则它必是树叶。( ) 10.二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。( ) 11.设与一棵树T 所对应的二叉树为BT，则与T 中的叶子结点所对应的BT 中的结点也一定 是叶子结点。( ) 12.当一棵具有n 个叶子结点的二叉树的WPL 值为最小时，称其树为Huffman 树，且其二叉 树的形状必是唯一的。( ) 13.二叉树的前序遍历并不能唯一确定这棵树，是因为我们不知道该树的根结点是哪一个。 ( ) 14.对于有n 个结点的二叉树，其高度为log n。( ) 2 二、选择题 1. 通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。以下解 释错误的是( ) A、正确性 算法应能正确地实现预定的功能(即处理要求) B、易读性 算法应易于阅读和理解 以便于调试 修改和扩充 C、健壮性 当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运 行结果 1 D、高效性 即达到所需要的时间性能 2. 数据的存储结构是指 （ ） A、数据所占的存储空间量 B、数据的逻辑结构在计算机中的表示 C、数据在计算机中的顺序存储方式 D、存储在外存中的数据 3.下列属于线性数据结构的是( ) A.队列 B.树 C.图 D.不确定 4.线性表是具有n 个( )的有限序列 A．表元素 B．字符 C．数据元素 D．数据项 5. 对于顺序表的优缺点，以下说法错误的是 （ ） A、无需为表示结点间的逻辑关系而增加额外的存储空间 B、可以方便地随机存取表中的任一结点 C、插入和删除运算较方便 D、容易造成一部分空间长期闲置而得不到充分利用 6. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以 （ ）为标准操作 A、结点移动 B、条件判断 C、算术表达式 D、赋值语句 7．若线性表最常用的操作是存取第i个元素及其前驱的值，则采用( )存储方式节省时间 A.单链表 B.双向链表 C.单循环链表 D.顺序表 8. 单链表的每个结点中包括一个指针 link，它指向该结点的后继结点。现要将指针 q 指向 的新结点插入到指针p 指向的结点之后，下面的操作序列中哪一个是正确的？( ) A、p-link q-link;q p-link; B、p-link q;q-link p-link; C、q-link p-link; p-link